從「三角形湯」中找到唯一的頂點

我在兩個庫（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

從「三角形湯」中找到唯一的頂點

回答

相關問題