代码之家 › 专栏 › 技术社区 › sum1stolemyname

从“三角形汤”中查找唯一顶点

geometry algorithm c++

sum1stolemyname · 技术社区 · 15 年前

我正在两个库(OpenCascade和dwf工具包)的基础上构建一个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)

虽然我确实有这样一个实现,但是步骤1(生成唯一顶点列表)在o(n!),因为每个顶点都会与列表中已有的所有顶点进行比较。我想:“嘿,让我们用std::map构建顶点组件的哈希图,这应该可以加快速度!”,只发现从三个浮点值生成唯一键不是一项简单的任务。

在这里,stackoverflow的专家们开始发挥作用:我需要某种在3个浮点上工作的散列函数,或者任何其他从三维顶点位置生成唯一值的函数。

3 回复 | 直到 9 年前

AVB 15 年前

转储数组中的所有顶点,然后执行 unique(sort(array)) . 这应该是o(k n log(n)),其中k是共享顶点的三角形的平均数,通常为k<7。

我能想到的唯一警告就是 unique 函数应该能够获取指向比较函数的指针,因为如果

distance(vertex1, vertex2) < threshold

但那似乎是 OK .

Michael Anderson 15 年前

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

使用哈希图。只有当“相同”的意思完全相同时,这才有效。
使用二进制空间分区来划分点
用一个规则的网格来划分你的分数。

在情况2和3中,如果要指定某些公差,则需要搜索树或网格的多个部分。在BSP情况下,这意味着检查您是否在划分平面的公差范围内,如果在公差范围内,则递归到两个半部分。在网格情况下,这意味着检查公差范围内的所有相邻单元。这两者都不是太难,但意味着使用“现成”的解决方案将更加困难。

Kirill V. Lyadvinsky 15 年前

获取散列的常见思想是将浮点的每个位模式乘以 prime 把它们加在一起。就像这样:

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)。这里的示例只是为了说明主要的想法,您应该根据需要对其进行调整。