健壯的多邊形正常計算

是否有一個好的魯棒算法來計算凸多邊形的法向量（當然是3D）？對於三角形，很容易：一個需要兩個三角形的邊緣，並計算叉積：健壯的多邊形正常計算

vec3 u = point[0] - point[1], v = point[0] - point[2]; 
vec3 n = normalize(cross(u, v));

但這種方法並沒有真正延伸至多邊形非常好。多邊形的某些邊可以近似或「精確」共線（這通常發生在發生T形結消除的網格中），因此有必要選擇一對邊，從而給出「強」法線（兩邊都是「足夠長」並且它們保持「幾乎垂直」的角度）。

雖然這種方法仍然不適用於所有多邊形。想象一下光盤形狀的多邊形。如果它被細分得很細，所有的邊緣都會很短，所有的連續邊緣幾乎是共線的，無論光盤的半徑如何。同時，正常情況非常明確。

一個解決方案可能是找到最大的內切三角形並計算其正常值。但是，找到它會有O(n^2)的複雜性，這看起來很難。

一個更好的解決方案可以是使用SVD或特徵值分解來計算法線，給定所有多邊形點，而不僅僅是三個或四個。

這是否有一個標準算法？任何人都有這樣做的好方法？

來源

2014-04-03 the swine

如果因式分解公式爲三角形，你會得到如下：

n ~ (p1 - p0) x (p2 - p0) 
    = p0 x p1 + p1 x p2 + p2 x p0

可以概括這個公式對任意多邊形：

n ~ p0 x p1 + p1 x p2 + ... + pn x p0

所以總結的連續叉積邊緣。這是一個強大的算法，適用於非平面多邊形。

如果你能肯定的是，多邊形是平面的，我會做以下（以節省計算時間）：

Repeat k times 
    Pick 3 random polygon vertices 
    Calculate the normal of the according triangle 
Choose the longest normal as the polygon's normal.

你可能會放棄具有length <= epsilon任何正常。

來源

2014-04-03 12:52:32

你有沒有考慮光盤的例子？我不認爲它非常強大，因爲連續邊的交叉積在那裏相當小。但是，否則，謝謝，我想這大多數時候會更好。 –

穩健性來自總和。 –

此外，使用epsilon保證該方法不具有數值穩健性。考慮有一個網格，其中有狹窄的多邊形。如果閾值很高，那些多邊形將不會有正常。如果它太低，算法可能會接受稍微不平坦的邊緣或其他次優邊緣對，即使在具有正常定義好的多邊形的情況下也會產生不精確的法線。 –

您可以計算多邊形所有點的協方差矩陣（這將是3D空間的3x3矩陣）。多邊形的法線將是對應於最小特徵值的特徵向量。

來源

2014-04-04 13:49:50

任何想法如何確定正常的方向？因爲在計算協方差矩陣時，頂點的順序會丟失。顯然，可以使用叉積來計算不太精確的法線，並將精確的法線翻轉以指向更相似的方向。你能想到更優雅的解決方案嗎？ –

你是對的，協方差矩陣將失去連通性，因此正常矢量可能有正負符號，這取決於你的約定。對不起，我不知道任何簡單的方法，那麼你提出的那個，以獲得標誌。與其他方法相比，該方法非常穩健但昂貴。 –

健壯的多邊形正常計算

回答

相關問題