How to traverse mesh vertices based on their location?

Question

I am using Point Cloud Free Viewer to visualize Point Clouds in Unity. It has a script and it parses .off files and creates meshes without triangulating. However, the code creates multiple meshes since its index format is 16bit. I modified the code for utilizing 32 bit format and i have a mesh with 2 million points:

What i want to do is creating a grid like geometry and color this point cloud based on point density. I want to find a rough volume of this point cloud by multiplying differences between max and min x,y,z values and divide this volume into equal boxes. Each of these boxes will be colored based of how many points they contain. I would be happy if someone can offer me a lead. I tried KDTree approach but it is a bit slow since i have 2 million points. I also tried sorting points before creating the mesh but it takes too much time as well. Is there a way to traverse mesh vertices based on the location without visiting all vertices considering they are indexed randomly? I believe i am looking for a solution like mesh.bounds.contains() but i do not know if a method like spatial search exists.

Answer 1

For those who might visit this question later i found a really fast solution based on Nico's comment. I am traversing whole points by parsing my scan file using this script

 for (int i = 0; i < numPoints; i++)
    {
        buffer = sr.ReadLine().Split();

        points[i] = new Vector3(float.Parse(buffer[0]) , float.Parse(buffer[1]) , -float.Parse(buffer[2]) );

        //Finding minX, minY, minZ
        if (points[i].x < minX)
            minX = points[i].x;
        if (points[i].y < minY)
            minY = points[i].y;
        if (points[i].z < minZ)
            minZ = points[i].z;
        //Finding maxX, maxY, maxZ
        if (points[i].x > maxX)
            maxX = points[i].x;
        if (points[i].y > maxY)
            maxY = points[i].y;
        if (points[i].z > maxZ)
            maxZ = points[i].z;

    }

Here is my and variables i use with itFindPointIndex function.

    deltaX = maxX - minX;
    deltaY = maxY - minY;
    deltaZ = maxZ - minZ;
    gridCountX = Mathf.CeilToInt(deltaX / gridSize);
    gridCountY = Mathf.CeilToInt(deltaY / gridSize);
    gridCountZ = Mathf.CeilToInt(deltaZ / gridSize);
    Resolution = gridCountX * gridCountY * gridCountZ;
    Histogram = new int[Resolution];

 int FindPointIndex(Vector3 point)
{
    //Finds the grid index of the point 
    int index = Mathf.FloorToInt((point.x - minX) / gridSize) + ((Mathf.FloorToInt((point.z - minZ) / gridSize)) * gridCountX)
           + Mathf.FloorToInt((point.y - minY) / gridSize) * gridCountX * gridCountZ;
    if (index < 0)
    {
        index = 0;
    }
    return index;
}

Then i can traverse the points again to increment index for each of them to see how many points each grid holds like this:

 for (int i = 0; i < numPoints; i++)
    {
        Histogram[FindPointIndex(points[i])]++;                                      
    }

At the end using this histogram i can color the point cloud with another loop.