浏览量:151

2.6. “近似”平面

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。

PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry

2.6. “近似”平面

问题描述:在三维空间上,有一个多边形\({\rm P} = \left\{ {{V_0},{V_1}, \cdots ,{V_{m - 1}}} \right\}\),确定经过该多边形的平面,并不能保证多边形上的顶点精确的在同一个平面上。

计算经过多边形的平面,有一种非常简单的方法,就是从中任选三个顶点,使用叉积,计算出法向量,再计算出平面表示中的常量。这种方法存在两个问题:(1)如果所有点不能精确的在同一个平面上,任选的三个点不具代表性,无法代表点集中所有的点;(2)如果选择的三个点,“几乎”(很接近,但是又不是)是同一条直线上,计算叉积的结果会非常的小,则误差就会变得非常的大。

另外一种方法,是从顶点集中任选三个点匹配,那么就会有\(m\left( {m - 1} \right)\left( {m - 2} \right)/6\)个组合,计算出它们的法向量,排除掉长度很小的法向量,归一化所有的法向量,最终取所有向量的平均值。这是一种估计法向量的方法,但是算法的复杂度达到\(O({m^3})\),效率成了这种方法的瓶颈。

Martin Newell提出了一种计算经过多边形\({\rm P}\)的平面的估计方法[1],考虑到所有点对法向量的贡献。设求得的法向量是\(\vec n = ({n_x},{n_y},{n_z})\),它的计算公式如等式(2.26)所示:

\[\begin{array}{l}{n_x} = \sum\limits_{i = 0}^{m - 1} {({y_i} - {y_{next(i)}})({z_i} + {z_{next(i)}})} \\{n_y} = \sum\limits_{i = 0}^{m - 1} {({z_i} - {z_{next(i)}})({x_i} + {x_{next(i)}})} \\{n_z} = \sum\limits_{i = 0}^{m - 1} {({x_i} - {x_{next(i)}})({y_i} + {y_{next(i)}})} \end{array} \tag{2.26}\]

2015-3-22 13-20-17

图2.15 多边形\({\rm P}\)的法向量方向

其中,\(m\)表示顶点的个数,\(({x_i},{y_i},{z_i})\)表示第\(i\)个点,\(next(i) = (i + 1)\% m\),计算出的法向量方向遵守右手法则,如果沿着法向量向下方向观察,顶点是以逆时针方向排序的,如图2.15所示。

举个例子,给定多边形的三个点\({P_0} = (6,1,4),{P_1} = (7,0,9),{P_2} = (1,1,2)\),使用叉积的方法可以求得法向量\(((7,0,9) - (6,1,4)) \times ((1,1,2) - (6,1,4)) = (2, - 23, - 5)\)。现在使用等式(2.26),同样可以计算出最终的法向量是\((2, - 23, - 5)\)

在求得法向量\(\vec n\)后,还需要求得平面经过的一点\(V\),可以通过计算所有点的平均值,采用来求点\(V\),如下所示:

\[V = \frac{1}{n}\sum\nolimits_0^{n - 1} {{V_i}} \tag{2.27}\]

知道了平面的法向量和平面上的点\(V\),就可以很容易计算出平面的表示公式。接下来,介绍该公式的推导过程,解释为什么它能表示成经过经过多边形的“近似”平面:

把一个多边形正交投影到\(x = 0,y = 0\)以及\(z = 0\)的平面上,可以得到3个2D多边形,3个2D多边形的面积分别为\({{A_x},{A_y},{A_z}}\)。首先需要证明的一个子结论是:法向量\(\vec n\)\(\left( {{A_x},{A_y},{A_z}} \right)\)成比例,即\(\vec n = k\left( {{A_x},{A_y},{A_z}} \right)\)

1.  假设多边形\({\rm P}\)是一个三角形(多边形可以表示成多个三角形的和),如图2.16所示。三角形\(T\)所在的平面的法向量是\(\vec n\),是单位长度,三角形面积为Area(\(T\));三角形\(T'\)是三角\(T\)在另一个平面上的投影,投影平面的法向量是\(\vec m\),也是单位长度,三角形面积为Area(\(T'\))。

2015-3-22 13-20-29

图2.16 把三角形\(T\),投影到另一个平面上,得到新的三角形\(T'\) [1]

a) \({\mathop{\rm Area}\nolimits} (T) = \frac{1}{2}\left| {\vec v \times \vec w} \right|\),则有\(\vec v \times \vec w = 2{\mathop{\rm Area}\nolimits} (T)\vec n\);同理,计算投影后的三角形\(T'\),有\({\mathop{\rm Area}\nolimits} (T') = \frac{1}{2}\left| {\vec v' \times \vec w'} \right|\),则有\(\vec v' \times \vec w' = 2{\mathop{\rm Area}\nolimits} (T')\vec m\)

2015-3-22 13-20-39

图2.17 向量\(\vec v\)投影到法向量\(\vec n\)的平面上,得到新的向量\(\vec v'\)

b) 考虑单个向量的投影,如图2.17所示,向量\(\vec v\)投影到另一个平面,得到新的向量\(\vec v'\),易知\(\vec v' = \vec v - (\vec v \cdot \vec m) \cdot \vec m\),同理,可以计算出\(\vec w' = \vec w - (\vec w \cdot \vec m) \cdot \vec m\)

c) 把\(\vec v'\)\(\vec w'\)代入(a)中的等式,可以得到

\[\vec v' \times \vec w' = \vec v \times \vec w - (\vec w \cdot \vec m)(\vec v \times \vec m) + (\vec v \cdot \vec m)(\vec w \times \vec m) + (\vec w \cdot \vec m)(\vec v \cdot \vec m)(\vec m \times \vec m)\]

由于\(\vec m \times \vec m = \vec 0\),所以可以消除最后一项,则有

\[2{\mathop{\rm Area}\nolimits} (T')\vec m = \vec v \times \vec w - (\vec w \cdot \vec m)(\vec v \times \vec m) + (\vec v \cdot \vec m)(\vec w \times \vec m)\]

d) 把上述等式两边点积上\(\vec m\),可以得到

\[2{\mathop{\rm Area}\nolimits} (T') = \left( {\vec v \times \vec w} \right) \cdot \vec m = 2{\mathop{\rm Area}\nolimits} (T)(\vec n \cdot \vec m)\]

2. 现在考虑一般多边形的情况,多边形\({\rm P}\)可以表示成多个三角形的和,即有

\[{\mathop{\rm Area}\nolimits} ({\rm P}') = \left( {\vec n \cdot \vec m} \right){\mathop{\rm Area}\nolimits} ({\rm P})\]

3.  多边形在\(x = 0,y = 0\)或者\(z = 0\)的平面上的投影,相当于在法向量分别是\(\vec m = (1,0,0)\)\(\vec m = (0,1,0)\)\(\vec m = (0,0,1)\)的平面上的投影,则\(\left( {{A_x},{\rm{ }}{A_y},{\rm{ }}{A_z}} \right){\rm{ }} = K\left( {{n_x},{\rm{ }}{n_y},{\rm{ }}{n_z}} \right)\)\(K\)是一个常数。法向量可以通过求多边形在多个平面上的投影面积,再将它归一化,就是多边形的法向量。

接下来,考虑计算多边形\({\rm P}\)在3个平面上的投影面积,以xy平面为例,即\(\vec m = (0,0,1)\)。多边形\({\rm P}\)上的顶点\({V_i} = ({x_i},{y_i},{z_i})\),投影到平面上,得到\({V_i} = ({x_i},{y_i})\),由顶点\({V_0},{V_1}\)与在轴对齐直线\(x = {x_0},x = {x_1}\)构成一个梯形,计算梯形的面积,得到

\[{A_0} = \frac{1}{2}({x_0} - {x_1})({y_0} + {y_1})\]

每条边都可以求得一个面积,一般的等式是

\[{A_i} = \frac{1}{2}({x_i} - {x_{next(i)}})({y_i} + {y_{next(i)}})\]

2015-3-22 13-20-49

图2.18 计算二维平面上多边形的面积

有些梯形的面积可能是正,有些可能是负,所有面积的和,就可以得到图2.18所示的多边形的面积。即使存在两条边几乎在同一条直线上的情况,但是它们都为最后求得的法向量作出了贡献。

每条边的面积和为:

\[{A_z} = \frac{1}{2}\sum\limits_{i = 0}^{m - 1} {({x_i} - {x_{next(i)}})({y_i} + {y_{next(i)}})} \]

同理,可以计算出多边形\({\rm P}\)xz平面上的投影面积\({A_y}\)和在yz平面上的投影面积\({A_x}\)

spacer

Leave a reply