从'三角汤'中找到独特的顶点

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)

虽然我有一个执行此操作的实现,但是步骤1(唯一顶点列表的生成)按O(n!)的顺序非常慢,因为每个顶点都与列表中已有的所有顶点进行比较.我想"嘿,让我们使用std :: map构建我的顶点组件的哈希映射,这应该加快速度!",只是发现从三个浮点值生成一个唯一键不是一项简单的任务.

在这里,stackoverflow的专家发挥作用:我需要某种哈希函数,它可以在3个浮点数上运行,或者从3d顶点位置生成唯一值的任何其他函数.

Answer 1

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

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

distance(vertex1, vertex2) < threshold

但这似乎还可以。