A method for processing point clouds having variable spatial distributions of scan lines includes receiving a point cloud frame generated by a sensor configured to sense an environment through which a vehicle is moving. The point cloud frame includes scan lines arranged according to a particular spatial distribution. The method also includes either generating an enhanced point cloud frame with a larger number of points than the received point cloud frame, or constructing, by one or more processors and based on points of the received point cloud frame, a three-dimensional mesh. The method also includes generating, by performing an interpolation function on the enhanced point cloud frame or a virtual surface provided by the three-dimensional mesh, a normalized point cloud frame, and generating, using the normalized point cloud frame, signals descriptive of a current state of the environment through which the vehicle is moving.