平面多邊形Newell公式的運(yùn)用與推廣

王睿旻， 吳 夢(mèng)， 鄧建松

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

平面多邊形Newell公式的運(yùn)用與推廣

王睿旻， 吳 夢(mèng)， 鄧建松

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

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

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

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

1 平面多邊形Newell公式

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

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

有

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

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

圖1 一個(gè)四邊形的示例

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

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

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

2 三維Newell公式

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

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

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

圖2 錐體T

從而引理得證。

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

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

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

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

圖3 將一個(gè)凸多面體分為若干錐體

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

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

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

進(jìn)而有

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

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

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

3 異面多邊形的Newell公式

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

例如圖4即為兩個(gè)異面四邊形。

圖4 兩個(gè)異面四邊形

由定義1，異面多邊形是非常普適的一個(gè)圖形，任意給一些不在同一平面上的點(diǎn)就存在一個(gè)異面多邊形?？梢远x異面多邊形P的 Newell向量。

下面分析異面多邊形的Newell向量的特征。

證 明 由定義知道 N (P′)，N (P)均垂直于平面X，所以 N (P′)平行于 N (P)。下面將進(jìn)行分解

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

并且

如果在等式(12) 兩邊點(diǎn)乘 N (P′)的話，可以將上面式子簡(jiǎn)化為而 N (P′)和 N (P)相互平行，有 N(P ′)= N (P)從而定理成立。

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

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

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

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

所以有

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

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

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

4 二維和三維Newell公式的計(jì)算

4.1 二維Newell公式的計(jì)算

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

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

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

取Q點(diǎn)為零點(diǎn)，有

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

如果直接計(jì)算的nx的話

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

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

以上是二維Newell公式的計(jì)算，三維Newell公式也可以運(yùn)用類似的方法進(jìn)行一些簡(jiǎn)化。

4.2 三維Newell公式的計(jì)算

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

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

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

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

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

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

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

5 總 結(jié)

本文主要圍繞 Newell公式展開了一系列的思考，旨在推廣 Newell公式并且將其運(yùn)用。推廣到了三維 Newell公式，并可以用其計(jì)算多面體的體積。對(duì)于異面多邊形，Newell向量是將異面多邊形投影到與該向量垂直平面的平面多邊形的 Newell向量，向量的模是所有投影多邊形面積的最大值。接著簡(jiǎn)化了二維 Newell公式和三維Newell公式的計(jì)算。

通過本文的工作，我們可以有效地用計(jì)算機(jī)計(jì)算平面多邊形的面積和多邊形所在平面的法向量以及多面體的體積。

[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-），男，重慶人，學(xué)士，主要研究方向?yàn)橛?jì)算機(jī)圖形學(xué)。