健壮的多边形正常计算

是否有一个好的鲁棒算法来计算凸多边形的法向量（当然是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

任何想法如何确定正常的方向？因为在计算协方差矩阵时，顶点的顺序会丢失。显然，可以使用叉积来计算不太精确的法线，并将精确的法线翻转以指向更相似的方向。你能想到更优雅的解决方案吗？ –

你是对的，协方差矩阵将失去连通性，因此正常矢量可能有正负符号，这取决于你的约定。对不起，我不知道任何简单的方法，那么你提出的那个，以获得标志。与其他方法相比，该方法非常稳健但昂贵。 –

健壮的多边形正常计算

回答

相关问题