从“三角形Soup”中找到独特的顶点

Question

我正在使用两个库(Opencascade和DWF Toolkit)构建CAD文件转换器。

然而，我的问题是平台无关的：

已知：

我已经生成了一个网格，它是通过我的应用程序构建的模型的三角形面列表。每个三角形由三个顶点定义，这些顶点由三个浮点数(x、y和z坐标)组成。由于三角形形成了网格，大多数顶点被多个三角形共享。

目标：

我需要找到唯一顶点的列表，并生成一个由三个索引元组组成的面数组，这些索引在该列表中。

我想要做的是：

//step 1: build a list of unique vertices
for each triangle
   for each vertex in triangle
      if not vertex in listOfVertices
         Add vertex to listOfVertices

//step 2: build a list of faces 
for each triangle
   for each vertex in triangle
      Get Vertex Index From listOfvertices
      AddToMap(vertex Index, triangle)

虽然我已经有一个实现方法可以做到这一点，但是第一步（生成唯一顶点列表）非常慢，时间复杂度为O(n!)，因为每个顶点都要与列表中的所有顶点进行比较。我想：“嘿，让我们使用std::map构建我的顶点组件的哈希映射表，那应该可以加快速度！” ，但是发现从三个浮点值生成唯一键不是一项微不足道的任务。

在这里，stackoverflow的专家们发挥了作用：我需要一种能够处理3个浮点数的哈希函数，或者任何其他能够从3D顶点位置生成唯一值的函数。

- sum1stolemyname

---

这个顶点唯一性需要多强壮呢？我的意思是，你只是想节省空间，还是需要非常强壮的拓扑结构。假设顶点Va和Vb获得不同的ID pn和pq，但实际上它们是“相同”的，这会成为一个障碍吗？ - Tarydon

是的，因为我正在尝试导出拓扑网格。如果源中的单个顶点在目标中存在多次，则从它构建的三角形将不共享边缘 - 拓扑可能变得开放。 - sum1stolemyname

Answer 1

三种解决方案。当然还有其他的方法。

1. 使用哈希映射。仅在“相同”意味着完全相同时才有效。
2. 使用二进制空间分割来划分点。
3. 使用常规网格来划分你的点。

在第2和第3种情况下，如果您想指定一些公差，您需要搜索树或网格的多个部分。在BSP情况下，这意味着检查是否在分隔平面的公差范围内，如果是，则递归进入两个部分。在网格情况下，这意味着检查所有邻近的单元格是否在公差范围内。这两种方法都不太难，但意味着使用“现成的”解决方案将更加困难。

- Michael Anderson

---

花了我一点时间才明白空间划分如何帮助我 - 这是一个有趣的方法。+1 - sum1stolemyname

我还使用了两个坐标的多重映射来创建一个隐式的空间索引，一个在X轴上，一个在Y轴上，这种方法很强大，但是当处理最大问题（数百万个顶点）时，O(n lg n)的缩放比例并不能满足我的需求。我想我会尝试使用八叉树或者莫顿索引等一些空间索引的方法。 - Walter Nissen

奇怪的是，我实际上又在做类似的事情。我在2D-4D中使用最近邻搜索。输入是数千万个点。一个KD树（二进制空间分割）实现为每个叶节点大约有16个顶点的线性堆，可以给我每个核心每秒大约10K次查询。构建时间为几秒钟，但我认为在这种情况下，您实际上可以将搜索和构建合并。 - Michael Anderson

Answer 2

将所有顶点存储在一个数组中，然后执行unique(sort(array))。这应该是O(k n log(n))的，其中k是共享顶点的平均三角形数量，通常k<7。

我唯一能想到的警告是，你的unique函数应该能够接受指向比较函数的指针，因为你可能希望将顶点视为相等。

distance(vertex1, vertex2) < threshold

但这似乎是可以接受的。

- AVB

---

这样做效率要高得多。（第一种方法需要35秒，改进后的方法只需要1.5秒） - sum1stolemyname

如果你想捕捉距离在阈值范围内的点，这段代码中存在一个不好的错误。靠近彼此的点没有保证能够“排序”到一起。事实上，我认为你可以证明对于任何排序函数，都会存在任意接近的点排序到列表中相距较远的位置... 这不是好的情况。 - Michael Anderson

@Michael：继续去证明它吧。 - AVB

如果您只需要一个简单排序的情况，考虑这个二维点数组按照传统排序的顺序返回{ [1,1], [1,10], [1.0001,1] }，然而[1.0001,1]比[1,10]更接近[1,1]。但由于列表中的分离，unique将会忽略它。（如果您真的想要一个任意排序函数的一般情况的证明，我可能可以构造一个，但它会很复杂 - 您可能需要数学学位才能理解它。） - Michael Anderson

使用哈希（用于相等条件检查），而不是数组，更绝对不是链表。 - Steven Lu

Answer 3

获取哈希的常见方法是将浮点数的每个位模式乘以质数，然后将它们相加。就像这样：

unsigned int hash_point(float x, float y, float z)
{
   unsigned int* px = (unsigned int*)&x;
   unsigned int* py = (unsigned int*)&y;
   unsigned int* pz = (unsigned int*)&z;

   return (*px)*PRIME1 + (*py)*PRIME2 + (*pz)*PRIME3;
}

请注意，这里认为sizeof(unsigned int)等于sizeof(float)。这里的示例仅用于说明主要思想，您应根据自己的需求进行调整。

- Kirill V. Lyadvinsky

---

当 x、y 和 z 不是整数时，用质数乘以它们并不能帮助太多。 - Tarydon

正确。您应该乘以浮点数的位模式，而不是浮点数本身。 - Kirill V. Lyadvinsky

请注意，一些数字具有多个比特模式表示，例如0和-0相同但具有不同的比特模式。这意味着它们将哈希到不同的值。尽管如此，这可能或可能不会是您的应用程序的问题。 - Michael Anderson

我曾经看到过（例如在此处）使用XOR而不是添加项来完成它。 - Steven Lu