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

我在两个库（Opencascade和DWF Toolkit）之上构建了一个CAD文件转换器。从“三角形汤”中找到唯一的顶点

然而，我的问题是plattform不可知：

鉴于：

我已经生成的网格三角形面的一个列表的形式通过我的申请构造的模型。每个三角形通过三个顶点定义，其中包含三个浮点数（x，y坐标）。由于三角形形成网格，因此大部分顶点由多于一个三角形共享。

目标：

我需要找到独特的顶点列表，并产生由在此列表中三个指数的元组的面孔组成的数组。

什么我想要做的是这样的：

//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)

虽然我确实有这这样做，第一步（独特的顶点列表的生成）的实现是在O3顺序很慢（N ！），因为每个顶点都与已经在列表中的所有顶点进行比较。我认为“嘿，让我们使用std :: map构建我的顶点组件的hashmap，这应该可以加快速度！”，但仅仅发现从三个浮点值生成一个唯一关键字并不是一项简单的任务。

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

来源

2010-03-09 sum1stolemyname

这个顶点唯一性必须有多强大？我的意思是，你只是想节省空间，还是需要非常健壮的拓扑结构？假设顶点Va和Vb得到不同的ID pn和pq，但实际上真的是'相同'，是一个交易断路器？ – Tarydon 2010-03-09 08:18:18

是的，这是因为我试图导出拓扑的网格。如果源中的单个顶点将在目标中存在多次，则从其构建的三角形不会共享边 - 拓扑可能会打开。 – sum1stolemyname 2010-03-09 10:49:20

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

我能想到的唯一要注意的是，你的unique功能应该能够采取一个指向比较函数，因为你可能要考虑你的顶点相等，如果

distance(vertex1, vertex2) < threshold

，但似乎是OK。

来源

2010-03-09 13:52:24 AVB

这种方法有效。我使用STL列表实现了这一点。 +1 – sum1stolemyname 2010-03-10 06:38:54

这种方式效率更高。（我的第一种方法是35秒，精炼方法是1.5秒） – sum1stolemyname 2010-03-10 09:03:09

如果您想要在彼此的阈值距离内捕捉点，那么存在一个令人讨厌的错误。不能保证点靠近彼此“排序”。事实上，我认为你可以证明，对于任何排序功能，都有点随机排列在列表中的远端位置......不好。 – 2010-03-14 03:48:04

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

使用哈希映射。这只适用于“相同”的意思完全相同的情况下
使用二进制空间分区来划分点
使用常规网格来划分你的点。

在情况2和3中，如果要指定一些容差，则需要搜索树或网格的多个部分。在BSP案例中，这意味着检查你是否在分割平面的容差范围内，如果是这样，则将其递归到两半。在网格情况下，这意味着检查容忍范围内的所有相邻小区。这两者都不是太难，但意味着使用“现成”解决方案会更困难。

来源

2010-03-09 08:10:10

我花了一点时间来了解空间分区如何帮助我 - 这是一个有趣的方法。 +1 – sum1stolemyname 2010-03-09 08:17:26

得到散列的常见思想是将float的每个bitpattern乘以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）。此处的示例仅用于说明主要想法，您应该根据自己的需求调整它。

来源

2010-03-09 08:10:58

当x，y和z不是整数时，将它们乘以素数不会有多大帮助。 – Tarydon 2010-03-09 08:21:49

正确。你应该乘以浮点数的位模式，而不是浮点数。 – 2010-03-09 08:33:20

请注意，某些数字具有多个比特模式表示，如0和-0是相同的，但具有不同的比特模式。这意味着他们将散列到不同的值。尽管这可能会或可能不会成为您的应用程序的问题。 – 2010-03-14 18:34:45

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

回答

相关问题