计算任意多边形法向量

和计算面积一样,乍一想,不就是相邻边叉乘?实际上,对于凸多边形确实是这样,但是对于非凸多边形就没那么简单啦

原理

Newell's Method 实际上这个方法不仅能确定面的法向量,还可以计算出平面方程

具体原理: Filippo Tampieri. “Newell's Method for Computing the Plane Equation of a Polygon”. In Graphics Gems III, Academic Press, 1992, pp. 231–232.

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// Get face normal 
template <typename Point>
Vec3d GetFaceNormal(const std::vector<Point>& points_3d)
{
// use Newell's Method to compute the surface normal
Vec3d n(0, 0, 0);
for (size_t i = 0; i < points_3d.size(); ++i)
{
size_t j = (i + 1) % points_3d.size();

// http://www.opengl.org/wiki/Calculating_a_Surface_Normal
const auto& a = points_3d[i] - points_3d[j];
const auto& b = points_3d[i] + points_3d[j];

n[0] += (a[1] * b[2]);
n[1] += (a[2] * b[0]);
n[2] += (a[0] * b[1]);
}

n.normalize();

return n;
}

// Get face equation
template <typename Point>
Vec4d GetPlaneEquation(const std::vector<Point>& points_3d)
{
// use Newell's Method to compute the surface normal
Vec3d n(0, 0, 0);
for (size_t i = 0; i < points_3d.size(); ++i)
{
size_t j = (i + 1) % points_3d.size();

// http://www.opengl.org/wiki/Calculating_a_Surface_Normal
const auto& a = points_3d[i] - points_3d[j];
const auto& b = points_3d[i] + points_3d[j];

n[0] += (a[1] * b[2]);
n[1] += (a[2] * b[0]);
n[2] += (a[0] * b[1]);
}
n.normalize();

const auto& f_cen = GetFaceCentroid(points_3d);
Vec3d cen(f_cen[0], f_cen[1], f_cen[2]);

double d = -cen.dot(n);

return Vec4d(n[0], n[1], n[2], d);
}