王睿旻， 吳 夢， 鄧建松

（中國科學技術大學數(shù)學科學院，安徽 合肥 230000）

平面多邊形Newell公式的運用與推廣

王睿旻， 吳 夢， 鄧建松

（中國科學技術大學數(shù)學科學院，安徽 合肥 230000）

Newell公式在計算機圖形學中常被用于計算多邊形面積和平面法向量。論文主要討論了Newell公式的運用與推廣。首先將其推廣三維空間中用于計算多面體體積的公式。其次討論了在異面多邊形的情況下，Newell公式的幾何意義。最后，從數(shù)值計算的角度分析了Newell公式的計算方法。

Newell公式；多面體體積；異面多邊形；數(shù)值計算

圖形學中，有時候會使用大量的多邊形片對模型進行擬合和繪制，如復雜場景的網(wǎng)格模型表示。因此，求解多邊形所在平面的法向量、多邊形面積以及多面體體積是其中的基本問題。在圖形學中，通常使用 Newell公式來計算多邊形的面積以及其所在平面的法向量。該公式形式簡潔而且計算量不大。在計算多面體體積的時候，除了一些特殊的多面體一般沒有什么特別好的普適方法，一般對于比較復雜的多面體可能會采取一些分割的方法。另外對于任意給定若干點后我們同樣能定義 Newell向量，而不知道這個向量的意義。基于 Newell公式的形式，通過本文的工作將其推廣為可以用來計算多面體體積的Newell公式，并且在計算不在同一平面的多邊形時，解釋了Newell向量的意義。

1 平面多邊形Newell公式

在圖形學中，Newell公式是計算一個多邊形的面積以及其所在平面的法向量的一種常用方法，作為本文的討論基礎，首先在這一節(jié)中介紹Newell公式[1-2]。

定理 1 給定一個平面多邊形P，其頂點依次為P1,P2,… , Pn+1其中 Pn+1=P1，Q為空間內(nèi)任意一點（見圖1），定義P的Newell向量 N (P)為

有

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

證 明 如果這個多邊形是凸多邊形，先選取Q 在多邊形內(nèi)部，這時可以把這個多邊形分成n三角形得到

圖1 一個四邊形的示例

由上式知對于任意Q在多邊形內(nèi)，結(jié)論是正確的。如果是空間內(nèi)任意一點R，有

所以 N (P)向量和Q點和R點的選取無關。而對于凹多邊形，可以將其分割為幾個凸多邊形，每一個凸多邊形定理成立，而加起來之后對于凹多邊形也是成立的。這樣就證明了定理的成立。

本節(jié)中主要介紹了經(jīng)典的 Newell公式。根據(jù)這個公式，平面多邊形的 Newell向量可以用來表示一個該多邊形所在平面的法向量而且Newell向量的模是這個多邊形的面積。

2 三維Newell公式

在這一節(jié)中將平面多邊形的 Newell公式推廣，使得推廣后的三維 Newell公式可以用于計算多面體體積。首先介紹一個引理。

引理 1 給定一個錐體T，如圖2所示，底面多邊形為P，頂點為R，錐體T的體積

其中，N (P)向量是底面P的Newell向量，而 RP是底面P的任意一個頂點。

圖2 錐體T

從而引理得證。

下面我們來證明本節(jié)的主定理。

定理 2 一個多面體U，P是U的多邊形表面，M是U內(nèi)所有表面組成的集合，R為空間內(nèi)任意一點， RP為表面 P內(nèi)任意一個頂點，N (P)為多邊形P的Newell的Newell向量，并且 N (P)的方向一致，即一致朝向多面體內(nèi)部或者外部。此時U的體積公式為

證 明 由于一個凹的多面體可以通過凸分解將其分解為凸多面體[3]，若對于凸多面體等式(5)成立即可。

對于一個凸多面體 U，P為U的表面多邊形，M是所有表面組成的集合， N (P)為表面P的Newell的Newell向量?？梢酝ㄟ^選取P上頂點的順序使得所有 N (P)都朝向凸多面體的外側(cè)。選取R在U的內(nèi)部，則可以將凸多面體U分成若干個錐體，而每個錐體的底面依次為U的表面P，如圖3所示。則根據(jù)引理1有

圖3 將一個凸多面體分為若干錐體

而在前面，通過選取平面P上頂點的定向使得N (P)均朝向U的外側(cè)，所以

即式(6)可以轉(zhuǎn)化為

即是等式(5)。下面證明等式(5)和R的選取無關。假設S為空間內(nèi)任意一個點

進而有

其中， np是表面P的頂點數(shù)， PWi是表面P上的頂點，L是多面體U的所有邊組成的集合，WV為U上的邊。第2個等號之所以成立是由于每條邊屬于兩個表面，所以在計算過程中一條邊正好出現(xiàn)兩次，而由于所有表面的定向都是朝向多面體的外側(cè)，所以兩次差乘的符號正好相反。從而最后則式(8)可以化為

即式（5）的值與R的選取無關，所需要做的只是保證表面的頂點定向一致。定理證畢。

根據(jù)定理2，計算一個多面體的體積時只需要所有頂點的信息和表面的信息即可。

3 異面多邊形的Newell公式

對于空間中多于3個的點構(gòu)成的封閉折線圖形很可能并不能位于同一個平面上。通常在使用邊數(shù)大于3的多邊形網(wǎng)格的時候，可能由于計算誤差或者其他原因并不能保證所有點都在同一平面，所以引入異面多邊形及其 Newell向量。首先提出異面多邊形的定義。

例如圖4即為兩個異面四邊形。

圖4 兩個異面四邊形

由定義1，異面多邊形是非常普適的一個圖形，任意給一些不在同一平面上的點就存在一個異面多邊形?？梢远x異面多邊形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)從而定理成立。

根據(jù)這個定理，一個異面多邊形P的Newell向量 N (P)是將這個異面多邊形投影到與 N(P)垂直的平面得到平面多邊形的 Newell向量。這個結(jié)論將異面的情形轉(zhuǎn)化成了平面的情形，下面將說明這個 Newell向量的模是所有投影多邊形里面積的最大值。

定理 4 異面多邊形P的頂點依次為 P1,P2,則P的Newell向量 N (P)是將P投影到與 N (P)垂直的平面X得到的平面多邊形P′的Newell向量。并且向量的模是將P投影到平面得到的多邊形的面積的最大值。

證 明 該定理的前半部分就是定理3，已經(jīng)得到了證明，這里只需要考慮后半部分的問題。假設任意一個平面X′，將異面多邊形P投影到X′上，得到的頂點依次為XPn′+1，這些點組成的平面多邊形為P′。這里將依舊用到式(12)這里同樣有垂直于平面X′。所以說同樣有

與前面不同的是，這里不再有 N (P)平行于N (P′)，所以這里沒有相等的結(jié)論，為了證明嘗試在（15）兩邊同時點乘 N (P′)，由于前面的垂直關系，可以得到

所以有

即是說投影多邊形P′的面積不會大于 N (P)的模長。而若投影平面垂直于 N (P)的話，面積等于所以 N (P)的模長是將異面多邊形投影到平面得到的多邊形的面積的最大值。從而定理得證。

可以看到，異面多邊形的 Newell向量和投影面積有關系而且得到的向量的模長為投影面積的最大值。需要注意的是，向量的值和點的排序有關。異面多邊形的n個點是空間內(nèi)的任意n個點，投影到平面后不一定是一個平面多邊形，有可能會有交叉（如圖5）。如果改變點的排序，向量的值也會改變，所以求得的投影多邊形的最大值是指在當前的頂點排序下投影異面多邊形得到的面積的最大值，而不是將異面多邊形投影到平面后那個閉包多邊形的面積的最大值。

圖5 異面多邊形的點序改變后，投影到一個平面的結(jié)果不同

4 二維和三維Newell公式的計算

4.1 二維Newell公式的計算

在計算圖形學當中，一個精確的模型往往會使用非常多的面片，例如斯坦福的數(shù)字米開朗基羅計劃中著名的大衛(wèi)雕像的三角面片達到了 20億之多。因此，需要研究 Newell向量的算法以便節(jié)省計算時間。對于二維的情形已經(jīng)有非常好的計算方法，文獻[2]中法向量的計算就是使用這種方法。

圖6 平面多邊形的 N (P)向量

證 明 3個式子的證明是相似的，這里只需要證明一個式子成立就可以了。以式(20)為例

取Q點為零點，有

式(21)，式(22)也可以通過類似的方法證明，這里就不贅述了。

如果直接計算的nx的話

根據(jù)式(24) ，計算nx的值需要進行3n次乘法?？梢詫⒁频角蠛屯饷婵梢灾苯庸?jié)省很多運算

根據(jù)等式(25) ，只需要 2n +1次乘法就可以求得所要值。同時不難觀察到，式(20)只需要 n +1次乘法就可以算出結(jié)果，大大節(jié)省了運算時間。

以上是二維Newell公式的計算，三維Newell公式也可以運用類似的方法進行一些簡化。

4.2 三維Newell公式的計算

定理6 給定多面體U，P是U的表面，M是所有表面構(gòu)成的集合。假設已經(jīng)將所有表面的頂點順序調(diào)好，使得所有平面P的 Newell的Newell向量都指向多面體的外側(cè)，同時表面P的頂點依次為它們的坐標為是表面P的頂點的個數(shù)。三維的Newell公式(5)與下式等價。

證 明 這里主要是用到了定理5的結(jié)論對公式進行簡化。由第2節(jié)已經(jīng)有

這里選取所有計算Newell向量的Q點都是零點，所有的表面P上的 RP點都是該表面的第1個頂點，從而可以將公式展開，得到如下式子

det(v1,v2,v3)是3個向量的行列式計算，對式(27)里的行列式進行展開，得到

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

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

只需要9次乘法，而利用式(26)計算需要12次乘法。其他情況，用式(26)進行計算會簡便得多。

5 總 結(jié)

本文主要圍繞 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-），男，重慶人，學士，主要研究方向為計算機圖形學。