史永豐，張育浩，程 婷，徐保文，林崗山

基于空間多邊形三角剖分的曲面分割求交算法

史永豐，張育浩，程 婷，徐保文，林崗山

(金航數(shù)碼科技有限責(zé)任公司，北京 100028)

針對(duì)傳統(tǒng)曲面分割求交方法存在的平面片的選取、遺漏部分交線段以及交線間斷的問(wèn)題，提出一種基于空間多邊形三角剖分的曲面分割求交算法。以等深度分割方法為基礎(chǔ)，避免了交線不連續(xù)的問(wèn)題，當(dāng)分割達(dá)到一定層次時(shí)以空間多邊形近似曲面片，并對(duì)空間多邊形進(jìn)行三角剖分，以三角形對(duì)的交線近似空間多邊形之間的交線，進(jìn)而以空間多邊形的交線近似曲面片的交線，最終得到相交曲面之間的交線。利用曲面片輪廓構(gòu)造出的空間多邊形更加接近曲面片的真實(shí)形狀，提高了逼近精度，同時(shí)對(duì)空間多邊形進(jìn)行三角剖分，提高了求交精度，進(jìn)而降低了丟失交線的可能性。實(shí)驗(yàn)驗(yàn)證了該算法比傳統(tǒng)的分割法更加精確。

分割法；空間多邊形；三角剖分

曲面求交是CAD/CAM和計(jì)算機(jī)圖形學(xué)中關(guān)鍵技術(shù)點(diǎn)之一，是曲面裁剪、曲面過(guò)渡、曲面拼接等技術(shù)基礎(chǔ)。曲面求交算法常用的有5種：代數(shù)法[1-2]、分割法[2-3]、離散法[4-5]、迭代法[2,6]和跟蹤法[7-8]。作為其中的一種，曲面分割求交算法是先通過(guò)2張曲面片的凸包判斷其是否相交，若相交將2張曲面片分別分割成4張小曲面片，再繼續(xù)利用凸包來(lái)做相交判斷，直到小曲面片在指定規(guī)范下逼近平面的小曲面片。經(jīng)過(guò)如此分割，形成了一列有交近似于平面的小曲面片對(duì)。求交過(guò)程中，先用平面片逼近小曲面片，然后計(jì)算相交平面片之間的交線，并通過(guò)平面片之間的交線近似曲面片對(duì)的交線。最后把交線段順序連起來(lái)，形成整個(gè)曲面片的交線。整個(gè)過(guò)程的核心思想是曲面細(xì)分，用平面代替曲面，將曲面求交轉(zhuǎn)化為平面求交問(wèn)題。該方法適用性廣，計(jì)算速度快，算法簡(jiǎn)單且容易實(shí)現(xiàn)。但存在平面片的選取、遺漏部分交線段以及交線間斷等不足[3]。

本文以等深度分割算法為基礎(chǔ)，借助空間多邊形來(lái)近似曲面片，提出一種基于空間多邊形三角剖分的曲面分割求交算法，其基本思想組成如下：

(1) 確定分割層數(shù)，對(duì)2張曲面進(jìn)行分割；

(2)利用曲面凸包，快速檢測(cè)小曲面片是否相交，舍棄凸包不相交的曲面片；

(3)當(dāng)分割到一定層次時(shí)，利用空間多邊形近似曲面片；

(4) 對(duì)空間多邊形進(jìn)行三角剖分；

(5)利用三角形對(duì)求交算法求出交線段，并利用拓?fù)潢P(guān)系將求得的交線段首尾連接，形成曲面交線。

1 曲面求交的分割法

1.1 傳統(tǒng)曲面分割求交的原理

曲面分割求交的基本原理是：通過(guò)曲面凸包快速檢測(cè)曲面是否相交。如果兩者不相交，則根據(jù)曲面凸包性質(zhì)可知，2張曲面不會(huì)相交。如果兩者相交(2張曲面可能相交)，則運(yùn)用分割技術(shù)分別將 2張曲面一分為四，然后對(duì)分割得到的子曲面片重復(fù)上述相交檢測(cè)過(guò)程，并拋棄凸包不相交的子曲面片。當(dāng)分割達(dá)到一定層次(等深度分割)或者曲面片在給定精度下已近似平坦(自適應(yīng)分割)時(shí)，就利用平面片(四邊形或2個(gè)三角形)近似表示曲面片，然后用平面片的交線近似代替曲面片間的交線。最后將分段求得的交線段按照拓?fù)潢P(guān)系首尾相連，得到整條交線。

1.2 分割求交方法的關(guān)鍵點(diǎn)

對(duì)比其他求交方法，分割法的思想簡(jiǎn)明，效果也比較好，因而獲得了廣泛的應(yīng)用。但應(yīng)注意如下關(guān)鍵點(diǎn)：

(1) 曲面的選取。由于Bézier曲面具有良好分割性質(zhì)，在處理NURBS曲面求交時(shí)，應(yīng)該將NURBS曲面轉(zhuǎn)化為有理Bézier曲面片，然后再進(jìn)行求交。

(2) 平面片的選取[3]。等深度分割方法中，當(dāng)分割達(dá)到一定層次時(shí)，由于未對(duì)子曲面片的平坦度進(jìn)行判斷，故曲面片可能并未達(dá)到近似平面片的界值，直接用平面片去代替曲面片會(huì)帶來(lái)逼近誤差。通常用曲面片凸包的厚度(取為長(zhǎng)度最小的棱長(zhǎng))除以凸包底面(與厚度相對(duì)應(yīng)的面)的面積得到平坦度。

在分割求交方法中，即便曲面片已足夠平坦，但其邊界曲線的彎曲程度可能很高，由曲面片4個(gè)角點(diǎn)構(gòu)造的平面片采用直線段來(lái)近似曲面邊界必會(huì)帶來(lái)很大的逼近誤差，導(dǎo)致求交的不精確。

(3) 遺漏部分交線段[3]。如圖1所示，，點(diǎn)分別為曲線段()與()的交點(diǎn)，直線段1P和1Q為曲線段在給定精度下的近似。由于直線段1P和1Q不相交，曲線()與()之間的交點(diǎn)丟失了。以此類推，得知曲面之間的交線也會(huì)出現(xiàn)遺漏。

圖1 曲線交點(diǎn)丟失現(xiàn)象

精度設(shè)置的不合理是造成交點(diǎn)丟失現(xiàn)象的主要原因。如圖2所示，假如再將2條曲線段分割一次，可得到近似交點(diǎn)?，?。由此可知，適當(dāng)提高逼近精度可以改善交點(diǎn)丟失的現(xiàn)象。推廣可得精度的提高也可以改善曲面求交中交線段遺漏的現(xiàn)象。

圖2 曲線進(jìn)一步分割及曲線交點(diǎn)

(4) 交線間斷[3]。由于同一曲面上相接2張曲面片被分割的次數(shù)不同，常常會(huì)導(dǎo)致交線間斷。

2 基于空間多邊形三角剖分的曲面分割求交算法

基于空間多邊形三角剖分的曲面分割求交的基本原理是：以等深度分割方法為基礎(chǔ)，當(dāng)達(dá)到一定分割層次時(shí)，即用空間多邊形近似表示曲面片，通過(guò)對(duì)空間多邊形進(jìn)行三角剖分，并以三角形面片的交線近似表示空間多邊形間的交線，進(jìn)一步以空間多邊形間的交線近似表示曲面片間的交線。最后將分段求得的交線段按照拓?fù)潢P(guān)系首尾相連，以獲得整條交線。

2.1 算法步驟

輸入：2張曲面片。

輸出：2條曲面片交線。

步驟1.確定曲面分割的最大層次(通常取為3~4)，初始化交線表。

步驟2.求解2張曲面片的凸包，然后判斷2個(gè)凸包是否相交，無(wú)交則轉(zhuǎn)步驟8，否則轉(zhuǎn)步驟3。

步驟3.若分割層次小于，繼續(xù)對(duì)曲面片進(jìn)行四叉分割，使每張曲面片都被分為4塊。對(duì)一張曲面片的每一子曲面片，均將其與另一張曲面片的4個(gè)子曲面片求交，即調(diào)用步驟2。

步驟4.若分割層次等于，則順序連接曲面片4條邊界的控制頂點(diǎn)，形成空間多邊形，以該空間多邊形代替原曲面片邊界。

步驟5.執(zhí)行空間多邊形的Delaunay三角剖分算法。

步驟6.對(duì)一張曲面片的每一個(gè)三角形，都分別與另一張曲面片的三角形求交[9-10]。

步驟7.將步驟6中求得的交線順序連接，檢查所得交線與交線表中原有交線是否相連，即檢查所得交線的首尾與原交線的首尾是否相連。若相連，則將所得交線連入原有交線; 若不相連，則生成新交線。

步驟8.返回。

2.2 空間多邊形的Delaunay三角剖分

簡(jiǎn)單多邊形三角剖分的定義是：將簡(jiǎn)單多邊形分解為一系列三角形，其不相交，且沒(méi)有不屬于原簡(jiǎn)單多邊形的頂點(diǎn)。簡(jiǎn)單多邊形的Delaunay三角剖分以簡(jiǎn)單多邊形的三角剖分為基礎(chǔ)，同時(shí)其內(nèi)邊都是局部?jī)?yōu)化的，且分割得到的三角形具有最小內(nèi)角最大、平均形態(tài)比最大的性質(zhì)[11]。

空間多邊形的Delaunay三角剖分算法步驟如下：

輸入：空間多邊形。

輸出：三角剖分后的空間多邊形。

步驟1.計(jì)算空間多邊形點(diǎn)集的最小二乘平面，即距離這些點(diǎn)最近的平面。并將點(diǎn)集投影至最小二乘平面，連接點(diǎn)集，形成平面多邊形。

步驟2.按逆時(shí)針?lè)较蝽樞蜃x入平面多邊形的頂點(diǎn)，建立鏈表，并計(jì)算出每個(gè)結(jié)點(diǎn)的凹凸性。

步驟3.取每個(gè)凸結(jié)點(diǎn)，將點(diǎn)與其相鄰2個(gè)結(jié)點(diǎn)構(gòu)成的三角形，記為Δ。假如Δ不包含多邊形上其他頂點(diǎn)，則計(jì)算該三角形的權(quán)值(三角形的權(quán)值定義為三角形3個(gè)內(nèi)角的最小值)。從所有凸結(jié)點(diǎn)構(gòu)成的三角形中取出權(quán)值最大的三角形，記為Δ，把Δ的頂點(diǎn)序號(hào)保存到數(shù)據(jù)結(jié)構(gòu)表中，并從鏈表中刪除中間結(jié)點(diǎn)。

步驟4.若鏈表中的結(jié)點(diǎn)個(gè)數(shù)大于3，則轉(zhuǎn)步驟3；否則轉(zhuǎn)步驟5。

步驟5.由鏈表中最后3個(gè)結(jié)點(diǎn)所對(duì)應(yīng)的多邊形頂點(diǎn)構(gòu)成一個(gè)三角形，刪除鏈表中最后3個(gè)結(jié)點(diǎn)。

步驟6.根據(jù)Delaunay 準(zhǔn)則，通過(guò)局部變換，得到平面多邊形的Delaunay三角剖分。

步驟7.將剖分結(jié)果映射回三維空間，即可完成空間多邊形的三角剖分[12]，也即曲面片的三角分割。

2.3 算法分析

本文算法的創(chuàng)新點(diǎn)在于利用空間多邊形取代了傳統(tǒng)分割方法中的平面片，并對(duì)空間多邊形進(jìn)行了三角剖分，提高了逼近精度，故求交精度也相應(yīng)提高。具體表現(xiàn)為：

(1) 空間多邊形的選取。當(dāng)用平面片近似曲面片時(shí)，難以改善曲面片平坦度未達(dá)到界值帶來(lái)的逼近誤差，而由曲面片輪廓構(gòu)造出的空間多邊形相對(duì)平面片來(lái)說(shuō)更接近曲面片的形狀，一定程度上可以降低曲面片的逼近誤差，提高了求交精度。

當(dāng)用平面片近似曲面片時(shí)，未考慮到曲面片邊界曲線的彎曲帶來(lái)的近似誤差，而本文算法中的空間多邊形正是以曲面片的輪廓為基礎(chǔ)構(gòu)造出的，故有效地避免了曲面片邊界曲線帶來(lái)的誤差。

相比平面片，空間多邊形更能精確表示曲面片的形狀，故求交精度更高。

(2) 改善了遺漏交線段的情況。由2.1節(jié)分析可知，利用空間多邊形近似曲面片提高了算法的逼近精度。本文算法用空間多邊形近似曲面片之后，又對(duì)空間多邊形進(jìn)行了三角剖分，即對(duì)空間多邊形進(jìn)行了細(xì)化，故逼近精度得到了提高。

無(wú)論是利用空間多邊形近似曲面片還是對(duì)空間多邊形進(jìn)行三角剖分均提高了算法的精度，精度的提高也改善了丟失交線的現(xiàn)象。

基于空間多邊形三角剖分的曲面分割求交算法，不僅考慮了等深度分割方法在交線連接上的優(yōu)勢(shì)，同時(shí)兼顧了自適應(yīng)分割方法在曲面平坦度分析上的優(yōu)勢(shì)，并且考慮到了曲面片邊界的彎曲程度，通過(guò)三角剖分提高了逼近精度，有效避免了交線丟失的現(xiàn)象。理論上，基于空間多邊形三角剖分的曲面分割求交算法比傳統(tǒng)的曲面分割求交算法得出的交點(diǎn)更加精確。本文將進(jìn)一步通過(guò)數(shù)值實(shí)驗(yàn)驗(yàn)證這一結(jié)論。

3 數(shù)值試驗(yàn)

3.1 實(shí)例

圖3為2個(gè)3×3的Bézier曲面，紅色的點(diǎn)表示Bézier曲面的控制頂點(diǎn)，分別利用曲面分割求交算法與基于空間多邊形三角剖分的曲面分割算法對(duì)3個(gè)曲面進(jìn)行求交運(yùn)算。

(a) 傳統(tǒng)曲面分割求交算法

(b) 基于空間多邊形三角剖分的曲面分割求交算法

圖3 2張Bézier曲面

由于曲面分割求交算法與基于空間多邊形三角剖分的曲面分割算法在對(duì)曲面進(jìn)行分割以及判斷是否相交的方法上是相同的，故只需通過(guò)比較分割后的子曲面片的交線是否準(zhǔn)確就可判斷2種算法的優(yōu)良。為了便于觀察，假設(shè)分割2次后得到的其中3個(gè)子曲面片已較為平緩(圖4)。

圖4 2個(gè)Bézier子曲面片

分別利用曲面分割求交算法與基于空間多邊形三角剖分的曲面分割算法對(duì)2個(gè)子曲面片進(jìn)行求交計(jì)算，結(jié)果如圖5和圖6所示。其中藍(lán)色的線框表示用于近似曲面片的三角形組，可以看出本文算法得到的線框要比傳統(tǒng)的分割算法得到的線框更接近曲面的真實(shí)形狀，與預(yù)期相符。黃色和綠色的線條分別表示2種算法最終求得的交線。在該實(shí)例中，2種算法求得的交點(diǎn)見表1和表2中的交點(diǎn)坐標(biāo)列。

圖5 分割求交算法

圖6 基于空間多邊形三角剖分的分割求交算法

表1 傳統(tǒng)的分割算法 交點(diǎn)坐標(biāo)交點(diǎn)投影之間的距離 (1.1039, 0.0567, 0.3)0.058 8 (1.0472, 0.2821, 0.3)0.232 6 (0.6752, 1.5708, 0.3)0.109 1

表2 基于空間多邊形三角剖分的分割算法 交點(diǎn)坐標(biāo)交點(diǎn)投影之間的距離 (1.3032, 0, 0.3)0.037 3 (1.0113, 1.0113, 0.3)0.039 9 (0.8497, 1.5708, 0.3)0.037 7

3.2 結(jié)果分析

將2種算法的求交結(jié)果置于一圖之中進(jìn)行比較。圖7中黃色線條表示曲面分割求交算法的結(jié)果，綠色線條表示基于空間多邊形三角剖分的曲面分割求交算法的結(jié)果。

通過(guò)觀察可知，傳統(tǒng)的曲面分割求交算法丟失了交線，且求得的交點(diǎn)比本文算法求得的交點(diǎn)距離與真實(shí)交點(diǎn)的距離更遠(yuǎn)，故基于空間多邊形三角剖分的曲面分割求交算法要優(yōu)于傳統(tǒng)的曲面分割求交算法。

(a) 2種算法的求交結(jié)果對(duì)比(一)

(b) 2種算法的求交結(jié)果對(duì)比(二)

圖7 2種算法的求交結(jié)果對(duì)比

下面通過(guò)數(shù)值比較2種算法的求交結(jié)果。將交點(diǎn)依次投影到2張相交曲面上，計(jì)算2個(gè)投影點(diǎn)之間的距離。可知，距離越小，則交點(diǎn)的準(zhǔn)確度越高。

情況 3.2.1 C1中的集合都是Y中頂點(diǎn)色集合,4,5,6中至少有2種色同時(shí)包含在每個(gè)C(ui)中,不妨設(shè)4,C(ui), i=1,2,…,10,則C2中的集合都不是X中頂點(diǎn)色集合,且至多有3個(gè)不是Y中頂點(diǎn)色集合。

依次將所求交點(diǎn)投影到2張曲面，并計(jì)算投影點(diǎn)之間的距離。由表1和表2可以看出，本文算法求得的交點(diǎn)投影點(diǎn)之間的最大距離均小于傳統(tǒng)分割求交算法求得的交點(diǎn)投影點(diǎn)之間的最小距離，并且在本例中傳統(tǒng)的曲面分割求交算法出現(xiàn)了丟失交線的現(xiàn)象，故得出：本文算法要優(yōu)于傳統(tǒng)的曲面分割求交算法。

還有一次，另一位輕功很厲害的劉歆師兄，直接就趁老師睡著，將墨涂到他臉上去了，老夫子醒來(lái)，摸了一手的墨，看著手上反印的紋路，也很贊，說(shuō)：“這些橫還是有一些生氣的，并不是死蚯蚓?！?/p>

注意：

(1) 傳統(tǒng)的分割算法用于曲面1，3相交時(shí)，出現(xiàn)了交線丟失，故不存在傳統(tǒng)的分割算法用于曲面1，3相交時(shí)的交點(diǎn)表。

(2) 本例中曲面2，3不相交，故不存在算法用于曲面2，3相交時(shí)的交點(diǎn)表。

(2)全年電力、熱力延時(shí)曲線。根據(jù)該醫(yī)院提供的熱力系統(tǒng)、變配電系統(tǒng)的運(yùn)行記錄的數(shù)據(jù)，得到醫(yī)院的熱力延時(shí)曲線和電力延時(shí)曲線如圖6所示。

(3) 由于在圖7中加入曲面1，2，3的標(biāo)記很容易影響圖片的直觀，且曲面1，2，3可以很清楚地從圖中分辨出，故這里不在圖7中進(jìn)行標(biāo)注。

通過(guò)表1和表2數(shù)值比較，可得出理論與觀察相同的結(jié)論：基于空間多邊形三角剖分的曲面分割求交算法比傳統(tǒng)的曲面分割求交算法得出的交點(diǎn)更加精確。

4 結(jié)語(yǔ)與討論

針對(duì)傳統(tǒng)曲面分割求交算法中存在的平面片的選取、遺漏部分交線段以及交線間斷問(wèn)題，本文提出了基于空間多邊形三角剖分的曲面分割求交算法.該算法不僅能夠找到曲面的交線，同時(shí)得到的交點(diǎn)要比傳統(tǒng)的分割求交算法更加精確，可以預(yù)見將本文算法所求交點(diǎn)作為初始點(diǎn)用于迭代法求交，將會(huì)提高求交速度、求交精度，并且能有效避免迭代不收斂現(xiàn)象。本文算法適用于帶有控制點(diǎn)的曲面求交，特別是Bézier、NURBS曲面。本文算法不適用于數(shù)據(jù)量龐大、且一般沒(méi)有用數(shù)學(xué)形式表示的曲面求交。如何對(duì)未有控制點(diǎn)的曲面進(jìn)行求交，是下一步研究重點(diǎn)。

參考文獻(xiàn)

[1] RATT M J, GEISOE A D. Surface/Surface intersection problems [EB/OL]. [2018-06-20]. https://www. researchgate.net/publication/247684327_SurfaceSurface_Intersection_Problems.

[2] 朱永強(qiáng), 魯聰達(dá). 自由曲線曲面造型技術(shù)的綜述[J]. 中國(guó)制造業(yè)信息化, 2003, 32(5): 110-113.

[3] 李新友. 曲面分割求交方法的實(shí)現(xiàn)[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 1989(1): 46-50.

[4] 陳振, 湯軍, 廖環(huán)宇, 等. 基于曲面方程的三角形網(wǎng)格模型求交方法[J]. 測(cè)繪與空間地理信息, 2016, 39(3): 62-64.

[5] 張華, 葉顯高, 李德群. 基于網(wǎng)格劃分的曲面求交算法[J]. 計(jì)算機(jī)應(yīng)用, 1994(6): 54-55.

[6] BARTH, W, LIEGER R, SCHINDLER M. Ray tracing general parametric surfaces using interval arithmetic [J]. The Visual. Computer, 1994, 10(7): 363-371.

[7] 許曉革, 冀陽(yáng)峰, 楊蕾. 曲面離散跟蹤求交算法的研究[J]. 工程圖學(xué)學(xué)報(bào), 2005, 26(1): 61-64.

[8] 黃金貴, 康寶生. 任意曲面間跟蹤求交的有效算法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 1998, 10(6): 499-505.

[9] 羅文龍, 熊高君, 李世吉. 基于二次劃分的大規(guī)模三角網(wǎng)曲面求交分割法[J]. 物探化探計(jì)算技術(shù), 2013, 35(3): 355-359.

[10] 李寧, 田震, 張立華, 等. 優(yōu)化的三角網(wǎng)格曲面求交算法[J]. 遼寧工程技術(shù)大學(xué)學(xué)報(bào)(自然科學(xué)版), 2013, 32(9): 1269-1273.

[11] 馬小虎, 潘志庚, 石教英. 基于凹凸頂點(diǎn)判定的簡(jiǎn)單多邊形Delaunay三角剖分[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 1999, 11(1): 1-3.

[12] 田中朝. 三角網(wǎng)格曲面重建及求交理論、方法研究[D]. 淄博: 山東理工大學(xué), 2008.

Surface Segmentation Algorithm Based on Spatial Polygon Triangulation

SHI Yong-feng, ZHANG Yu-hao, CHENG Ting, XU Bao-wen, LIN Gang-shan

(Jinhang Digital Technology Co. Ltd., Beijing 100028, China)

Abstract: The problems with the traditional surface segmentation intersection lie in the choice of plane, loss of intersection line and discontinuous intersection line. In view of these problems, this paper proposes a surface segmentation intersection algorithm based on spatial polygon triangulation. The algorithm based on equal depth segmentation avoids the problem of discontinuous intersection line. When the segmentation reaches a certain level, the spatial polygon is used to approximate the surface patch, and the spatial polygon is triangulated. The intersection of the triangular pair is similar to the intersection between the spatial polygons, then the intersection of the spatial polygons is approximated to the intersection of the patches. Finally we get intersection lines between the intersection surfaces. The spatial polygons constructed by the contours of the surface patch are closer to the true shape of the patch, and the approximation accuracy is improved. The triangulation of the spatial polygons improves the accuracy of the intersection, thus reducing the possibility of losing the intersection line. In theory, this algorithm is more accurate than the traditional segmentation method, and the experiment also verifies this conclusion.

Keywords: segmentation method; spatial polygon; triangulation

中圖分類號(hào)：TP 391.41

DOI：10.11996/JG.j.2095-302X.2019030447

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：2095-302X(2019)03-0447-05

收稿日期：2018-08-30；

定稿日期：2018-09-11

第一作者：史永豐(1980-)，男，湖南郴州人，高級(jí)工程師，碩士。主要研究方向?yàn)镃AD、計(jì)算機(jī)圖形學(xué)。E-mail：shiyf@avic-digital.com

通信作者：程 婷(1988-)，女，山西晉中人，工程師，博士。主要研究方向?yàn)镃AGD、CAD、計(jì)算機(jī)圖形學(xué)。E-mail：chengt@avic-digital.com