平面多边形Newell公式的运用与推广

王睿旻， 吴 梦， 邓建松

（中国科学技术大学数学科学院，安徽 合肥 230000）

平面多边形Newell公式的运用与推广

王睿旻， 吴 梦， 邓建松

（中国科学技术大学数学科学院，安徽 合肥 230000）

Newell公式在计算机图形学中常被用于计算多边形面积和平面法向量。论文主要讨论了Newell公式的运用与推广。首先将其推广三维空间中用于计算多面体体积的公式。其次讨论了在异面多边形的情况下，Newell公式的几何意义。最后，从数值计算的角度分析了Newell公式的计算方法。

Newell公式；多面体体积；异面多边形；数值计算

图形学中，有时候会使用大量的多边形片对模型进行拟合和绘制，如复杂场景的网格模型表示。因此，求解多边形所在平面的法向量、多边形面积以及多面体体积是其中的基本问题。在图形学中，通常使用 Newell公式来计算多边形的面积以及其所在平面的法向量。该公式形式简洁而且计算量不大。在计算多面体体积的时候，除了一些特殊的多面体一般没有什么特别好的普适方法，一般对于比较复杂的多面体可能会采取一些分割的方法。另外对于任意给定若干点后我们同样能定义 Newell向量，而不知道这个向量的意义。基于 Newell公式的形式，通过本文的工作将其推广为可以用来计算多面体体积的Newell公式，并且在计算不在同一平面的多边形时，解释了Newell向量的意义。

1 平面多边形Newell公式

在图形学中，Newell公式是计算一个多边形的面积以及其所在平面的法向量的一种常用方法，作为本文的讨论基础，首先在这一节中介绍Newell公式[1-2]。

定理 1 给定一个平面多边形P，其顶点依次为P1,P2,… , Pn+1其中 Pn+1=P1，Q为空间内任意一点（见图1），定义P的Newell向量 N (P)为

有

area (P)是平面多边形 P的面积，而且 N(P)垂直于平面P。

证 明 如果这个多边形是凸多边形，先选取Q 在多边形内部，这时可以把这个多边形分成n三角形得到

图1 一个四边形的示例

由上式知对于任意Q在多边形内，结论是正确的。如果是空间内任意一点R，有

所以 N (P)向量和Q点和R点的选取无关。而对于凹多边形，可以将其分割为几个凸多边形，每一个凸多边形定理成立，而加起来之后对于凹多边形也是成立的。这样就证明了定理的成立。

本节中主要介绍了经典的 Newell公式。根据这个公式，平面多边形的 Newell向量可以用来表示一个该多边形所在平面的法向量而且Newell向量的模是这个多边形的面积。

2 三维Newell公式

在这一节中将平面多边形的 Newell公式推广，使得推广后的三维 Newell公式可以用于计算多面体体积。首先介绍一个引理。

引理 1 给定一个锥体T，如图2所示，底面多边形为P，顶点为R，锥体T的体积

其中，N (P)向量是底面P的Newell向量，而 RP是底面P的任意一个顶点。

图2 锥体T

从而引理得证。

下面我们来证明本节的主定理。

定理 2 一个多面体U，P是U的多边形表面，M是U内所有表面组成的集合，R为空间内任意一点， RP为表面 P内任意一个顶点，N (P)为多边形P的Newell的Newell向量，并且 N (P)的方向一致，即一致朝向多面体内部或者外部。此时U的体积公式为

证 明 由于一个凹的多面体可以通过凸分解将其分解为凸多面体[3]，若对于凸多面体等式(5)成立即可。

对于一个凸多面体 U，P为U的表面多边形，M是所有表面组成的集合， N (P)为表面P的Newell的Newell向量。可以通过选取P上顶点的顺序使得所有 N (P)都朝向凸多面体的外侧。选取R在U的内部，则可以将凸多面体U分成若干个锥体，而每个锥体的底面依次为U的表面P，如图3所示。则根据引理1有

图3 将一个凸多面体分为若干锥体

而在前面，通过选取平面P上顶点的定向使得N (P)均朝向U的外侧，所以

即式(6)可以转化为

即是等式(5)。下面证明等式(5)和R的选取无关。假设S为空间内任意一个点

进而有

其中， np是表面P的顶点数， PWi是表面P上的顶点，L是多面体U的所有边组成的集合，WV为U上的边。第2个等号之所以成立是由于每条边属于两个表面，所以在计算过程中一条边正好出现两次，而由于所有表面的定向都是朝向多面体的外侧，所以两次差乘的符号正好相反。从而最后则式(8)可以化为

即式（5）的值与R的选取无关，所需要做的只是保证表面的顶点定向一致。定理证毕。

根据定理2，计算一个多面体的体积时只需要所有顶点的信息和表面的信息即可。

3 异面多边形的Newell公式

对于空间中多于3个的点构成的封闭折线图形很可能并不能位于同一个平面上。通常在使用边数大于3的多边形网格的时候，可能由于计算误差或者其他原因并不能保证所有点都在同一平面，所以引入异面多边形及其 Newell向量。首先提出异面多边形的定义。

例如图4即为两个异面四边形。

图4 两个异面四边形

由定义1，异面多边形是非常普适的一个图形，任意给一些不在同一平面上的点就存在一个异面多边形。可以定义异面多边形P的 Newell向量。

下面分析异面多边形的Newell向量的特征。

证 明 由定义知道 N (P′)，N (P)均垂直于平面X，所以 N (P′)平行于 N (P)。下面将进行分解

由于 XPi是 Pi的投影，所以垂直于平面X，即互相之间平行并且平行于 N (P)和 N (P′)。所以，可以知道

并且

如果在等式(12) 两边点乘 N (P′)的话，可以将上面式子简化为而 N (P′)和 N (P)相互平行，有 N(P ′)= N (P)从而定理成立。

根据这个定理，一个异面多边形P的Newell向量 N (P)是将这个异面多边形投影到与 N(P)垂直的平面得到平面多边形的 Newell向量。这个结论将异面的情形转化成了平面的情形，下面将说明这个 Newell向量的模是所有投影多边形里面积的最大值。

定理 4 异面多边形P的顶点依次为 P1,P2,则P的Newell向量 N (P)是将P投影到与 N (P)垂直的平面X得到的平面多边形P′的Newell向量。并且向量的模是将P投影到平面得到的多边形的面积的最大值。

证 明 该定理的前半部分就是定理3，已经得到了证明，这里只需要考虑后半部分的问题。假设任意一个平面X′，将异面多边形P投影到X′上，得到的顶点依次为XPn′+1，这些点组成的平面多边形为P′。这里将依旧用到式(12)这里同样有垂直于平面X′。所以说同样有

与前面不同的是，这里不再有 N (P)平行于N (P′)，所以这里没有相等的结论，为了证明尝试在（15）两边同时点乘 N (P′)，由于前面的垂直关系，可以得到

所以有

即是说投影多边形P′的面积不会大于 N (P)的模长。而若投影平面垂直于 N (P)的话，面积等于所以 N (P)的模长是将异面多边形投影到平面得到的多边形的面积的最大值。从而定理得证。

可以看到，异面多边形的 Newell向量和投影面积有关系而且得到的向量的模长为投影面积的最大值。需要注意的是，向量的值和点的排序有关。异面多边形的n个点是空间内的任意n个点，投影到平面后不一定是一个平面多边形，有可能会有交叉（如图5）。如果改变点的排序，向量的值也会改变，所以求得的投影多边形的最大值是指在当前的顶点排序下投影异面多边形得到的面积的最大值，而不是将异面多边形投影到平面后那个闭包多边形的面积的最大值。

图5 异面多边形的点序改变后，投影到一个平面的结果不同

4 二维和三维Newell公式的计算

4.1 二维Newell公式的计算

在计算图形学当中，一个精确的模型往往会使用非常多的面片，例如斯坦福的数字米开朗基罗计划中著名的大卫雕像的三角面片达到了 20亿之多。因此，需要研究 Newell向量的算法以便节省计算时间。对于二维的情形已经有非常好的计算方法，文献[2]中法向量的计算就是使用这种方法。

图6 平面多边形的 N (P)向量

证 明 3个式子的证明是相似的，这里只需要证明一个式子成立就可以了。以式(20)为例

取Q点为零点，有

式(21)，式(22)也可以通过类似的方法证明，这里就不赘述了。

如果直接计算的nx的话

根据式(24) ，计算nx的值需要进行3n次乘法。可以将移到求和外面可以直接节省很多运算

根据等式(25) ，只需要 2n +1次乘法就可以求得所要值。同时不难观察到，式(20)只需要 n +1次乘法就可以算出结果，大大节省了运算时间。

以上是二维Newell公式的计算，三维Newell公式也可以运用类似的方法进行一些简化。

4.2 三维Newell公式的计算

定理6 给定多面体U，P是U的表面，M是所有表面构成的集合。假设已经将所有表面的顶点顺序调好，使得所有平面P的 Newell的Newell向量都指向多面体的外侧，同时表面P的顶点依次为它们的坐标为是表面P的顶点的个数。三维的Newell公式(5)与下式等价。

证 明 这里主要是用到了定理5的结论对公式进行简化。由第2节已经有

这里选取所有计算Newell向量的Q点都是零点，所有的表面P上的 RP点都是该表面的第1个顶点，从而可以将公式展开，得到如下式子

det(v1,v2,v3)是3个向量的行列式计算，对式(27)里的行列式进行展开，得到

进一步由式(20)，(21)和(22)知

代入式(27)即得即证明了定理。

只需要9次乘法，而利用式(26)计算需要12次乘法。其他情况，用式(26)进行计算会简便得多。

5 总 结

本文主要围绕 Newell公式展开了一系列的思考，旨在推广 Newell公式并且将其运用。推广到了三维 Newell公式，并可以用其计算多面体的体积。对于异面多边形，Newell向量是将异面多边形投影到与该向量垂直平面的平面多边形的 Newell向量，向量的模是所有投影多边形面积的最大值。接着简化了二维 Newell公式和三维Newell公式的计算。

通过本文的工作，我们可以有效地用计算机计算平面多边形的面积和多边形所在平面的法向量以及多面体的体积。

[1] Angle E. Interactive computer graphics: a top-down approach using openGL, 4th Edn [M]. Addision Wesley, Boston, MA, 2006: 290-322.

[2] Hearn D, Baker M. Computer graphics with OpenGL, 3rd end [M]. Prentice Hall, Englewood Cliffs, NJ, 2003: 24-50.

[3] Bajaj C, Dey T K. Convex decomposition of polyhedra and robustness [J]. SIAM J. Comput, 1992, 21: 339-364.

[4] Lien L, Amato N M. Approximate convex decomposition of polyhedra and its applications [J]. Computer Aided Geometric Design, 2008, 25(7): 503-522.

[5] Lien L, Amato N M. Approximate convex decomposition of polyhedra [J]. Proceedings of the ACM Symposium on Solid and Physical Modeling, Beijing, China, 2007: 121-131.

The application and promotion of the Newell formula

Wang Ruimin, Wu Meng, Deng Jiansong
( Academy of Mathematics, University of Science and Technology of China., Hefei Anhui 230000, China )

The application and promotion of the Newell formula in CAGD are discussed in this paper. This formula is used to calculate the area of a plane polygon and the normal vector of the plane the polygon lies on. Firstly, it is promoted to calculate the volume of a polyhedron. Secondly, the meaning of the Newell formula is discussed if the vertices are not on the same plane. Finally, some methods are proposed to simplify the calculation of the formula.

Newell formula; polyhedron volume; polygon with vertices not in the same plane; numerical calculation

TP 391.41

A

2095-302X (2012)02-0062-06

2011-09-30

王睿旻（1990-），男，重庆人，学士，主要研究方向为计算机图形学。