稳健的多边形法线计算 [英] Robust polygon normal calculation

问题描述

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

is there a good robust algorithm to calculate normal vector of a convex polygon (in 3D, of course)? For triangles, it is easy: one takes two of the triangle's edges and calculates the cross product:

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

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

But this approach does not really extend to polygons very well. Some edges of the polygon can be nearly or "exactly" collinear (this will happen often in meshes where T-Junction removal took place), therefore it is necessary to choose a pair of edges, giving a "strong" normal (both edges are "long enough" and they hold "almost perpendicular" angle).

不过，这种方法仍然不适用于所有多边形.想象一个圆盘形状的多边形.如果它被非常精细地细分，则所有边缘都将非常短，并且所有连续边缘几乎都在同一条线上，无论圆盘的半径如何.同时，法线的定义非常明确.

This approach will still not work for all polygons, though. Imagine a polygon in the shape of a disc. If it is very finely subdivided, all the edges will be very short and all of the consecutive edges will be almost collinear, regardless of the radius of the disc. At the same time, the normal is very well defined.

一种解决方案可能是找到最大的内接三角形并计算其法线.然而，找到它会有O(n^2)的复杂度，这似乎令人望而却步.

One solution could be to find the largest inscribed triangle and to calculate the normal of that. However, finding it will have complexity of O(n^2), which seems prohibitive.

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

A better solution could be to use SVD or Eigenvalue decomposition to calculate the normal, given all the polygon points, not just three or four.

是否有标准算法?有谁有好的方法吗?

Is there a standard algorithm for this? Anyone has a good way of doing it?

推荐答案

如果您对三角形的公式进行因式分解，您将得到以下结果:

If you factorize the formula for a triangle, you'll get the following:

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

您可以将这个公式推广到任意多边形:

You can generalize this formula for arbitrary polygons:

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

所以求和连续边的叉积.这是一种稳健的算法，适用于非平面多边形.

So sum the cross product of consecutive edges. This is a robust algorithm and works for non-planar polygons.

如果您可以确定多边形是平面的，我将执行以下操作(以节省计算时间):

If you can be sure that the polygon is planar, I would do the following (to save computation time):

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 的法线.

You might discard any normal that has a length <= epsilon.

这篇关于稳健的多边形法线计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！