A method for processing point clouds having variable spatial distributions of scan lines includes receiving a point cloud portion corresponding to an object in a vehicle environment, the point cloud portion including scan lines arranged according to a particular spatial distribution. The method also includes constructing a voxel grid corresponding to the received point cloud portion. The voxel grid includes a plurality of volumes in a stacked, three-dimensional arrangement, and constructing the voxel grid includes (i) determining an initial classification of the object, (ii) setting one or more parameters of the voxel grid based on the initial classification, and (iii) associating each volume of the plurality of volumes with an attribute specifying how many points, from the point cloud portion, fall within that volume. The method also includes generating, using the constructed voxel grid, signals descriptive of a current state of the environment through which the vehicle is moving.