稳健的多边形法线计算

Question

是否有一个很好的鲁棒算法来计算凸多边形的法向量(当然,在3D中)？对于三角形,很容易:一个取三角形的两个边并计算叉积:

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

但是这种方法并没有真正扩展到多边形.多边形的某些边缘可能几乎或"完全"共线(这通常发生在发生T形连接的网格中),因此有必要选择一对边,给出"强"法线(两条边都是"足够长"并且它们保持"几乎垂直"的角度).

但是,这种方法仍然不适用于所有多边形.想象一下圆盘形状的多边形.如果细分非常精细,则无论光盘的半径如何,所有边缘都将非常短并且所有连续边缘将几乎共线.与此同时,正常情况非常明确.

一种解决方案可能是找到最大的内切三角形并计算其正常值.然而,发现它将具有复杂性O(n^2),这似乎令人望而却步.

给定所有多边形点,而不仅仅是三个或四个,更好的解决方案是使用SVD或特征值分解来计算法线.

这有标准算法吗？任何人都有一个很好的方法吗？

Answer 1

如果将三角形的公式分解，将得到以下结果：

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。