如何根据位置遍历网格顶点？

Question

我正在使用 Point Cloud Free Viewer 在 Unity 中可视化点云。它有一个脚本，它可以解析 .off 文件并在不进行三角剖分的情况下创建网格。但是，代码创建了多个网格，因为它的索引格式是 16 位。我修改了使用 32 位格式的代码，我有一个包含 200 万个点的网格：

我想要做的是创建一个类似几何体的网格，并根据点密度为这个点云着色。我想通过乘以最大和最小 x、y、z 值之间的差异并将该体积分成相等的框来找到该点云的粗略体积。这些盒子中的每一个都将根据它们包含的点数进行着色。如果有人能给我提供线索，我会很高兴。我尝试了 KDTree 方法，但它有点慢，因为我有 200 万分。我也尝试在创建网格之前对点进行排序，但这也需要太多时间。考虑到它们是随机索引的，有没有一种方法可以根据位置遍历网格顶点而不访问所有顶点？我相信我正在寻找像 mesh.bounds.contains() 这样的解决方案，但我不知道是否存在像空间搜索这样的方法。

Answer 1

不是真的，一个完整的解决方案，更多的是对我追求的方向的提示：首先将你的顶点池分成更小的组，即分成立方体（可能是单独的网格），预先计算，然后你只需要在内部搜索一个小得多的区域，在初步搜索一组与您的区域相邻（或接触）的立方体之后。

Answer 2

我觉得你想要一个 octree。

首先，将所有点加载到内存中（200 万个点确实不多 - 假设是双倍，即 2,000,000 * 3 * 8 字节 ~= 45 MB）。在解析文件并将点加载到内存中时，记录最小和最大 x、y 和 z 坐标。然后，您可以构建以 N*LogN 为界的八叉树。然后，对于您的每个网格体积，您可以非常快速地查询树以仅获取该区域中的点。我很确定这是执行您想要的操作的最有效方法。

我建议查看 quadtree 文章以了解其对 queryRange 的实现，以了解如何完成此操作。八叉树只是四叉树的三维实现，因此底层代码或多或少相同（每个节点包含 8 个子节点而不是 4 个）。

Answer 3

对于那些以后可能会访问这个问题的人，我根据 Nico 的评论找到了一个非常快速的解决方案。我通过使用此脚本解析我的扫描文件来遍历整个点

 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;

    }

这是我使用的变量和变量FindPointIndex 函数。

    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;
}

然后我可以再次遍历点以增加每个点的索引，以查看每个网格包含多少点，如下所示：

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

最后使用这个直方图我可以用另一个循环给点云上色。

如何根据位置遍历网格顶点？

How to traverse mesh vertices based on their location?

c#

traversal

mesh

unity3d

point-clouds