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

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

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

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

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

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

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

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

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

(1) 確定分割層數，對2張曲面進行分割；

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

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

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

(5)利用三角形對求交算法求出交線段，并利用拓撲關系將求得的交線段首尾連接，形成曲面交線。

1 曲面求交的分割法

1.1 傳統曲面分割求交的原理

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

1.2 分割求交方法的關鍵點

對比其他求交方法，分割法的思想簡明，效果也比較好，因而獲得了廣泛的應用。但應注意如下關鍵點：

(1) 曲面的選取。由于Bézier曲面具有良好分割性質，在處理NURBS曲面求交時，應該將NURBS曲面轉化為有理Bézier曲面片，然后再進行求交。

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

在分割求交方法中，即便曲面片已足夠平坦，但其邊界曲線的彎曲程度可能很高，由曲面片4個角點構造的平面片采用直線段來近似曲面邊界必會帶來很大的逼近誤差，導致求交的不精確。

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

圖1 曲線交點丟失現象

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

圖2 曲線進一步分割及曲線交點

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

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

基于空間多邊形三角剖分的曲面分割求交的基本原理是：以等深度分割方法為基礎，當達到一定分割層次時，即用空間多邊形近似表示曲面片，通過對空間多邊形進行三角剖分，并以三角形面片的交線近似表示空間多邊形間的交線，進一步以空間多邊形間的交線近似表示曲面片間的交線。最后將分段求得的交線段按照拓撲關系首尾相連，以獲得整條交線。

2.1 算法步驟

輸入：2張曲面片。

輸出：2條曲面片交線。

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

步驟2.求解2張曲面片的凸包，然后判斷2個凸包是否相交，無交則轉步驟8，否則轉步驟3。

步驟3.若分割層次小于，繼續對曲面片進行四叉分割，使每張曲面片都被分為4塊。對一張曲面片的每一子曲面片，均將其與另一張曲面片的4個子曲面片求交，即調用步驟2。

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

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

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

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

步驟8.返回。

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

簡單多邊形三角剖分的定義是：將簡單多邊形分解為一系列三角形，其不相交，且沒有不屬于原簡單多邊形的頂點。簡單多邊形的Delaunay三角剖分以簡單多邊形的三角剖分為基礎，同時其內邊都是局部優化的，且分割得到的三角形具有最小內角最大、平均形態比最大的性質[11]。

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

輸入：空間多邊形。

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

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

步驟2.按逆時針方向順序讀入平面多邊形的頂點，建立鏈表，并計算出每個結點的凹凸性。

步驟3.取每個凸結點，將點與其相鄰2個結點構成的三角形，記為Δ。假如Δ不包含多邊形上其他頂點，則計算該三角形的權值(三角形的權值定義為三角形3個內角的最小值)。從所有凸結點構成的三角形中取出權值最大的三角形，記為Δ，把Δ的頂點序號保存到數據結構表中，并從鏈表中刪除中間結點。

步驟4.若鏈表中的結點個數大于3，則轉步驟3；否則轉步驟5。

步驟5.由鏈表中最后3個結點所對應的多邊形頂點構成一個三角形，刪除鏈表中最后3個結點。

步驟6.根據Delaunay 準則，通過局部變換，得到平面多邊形的Delaunay三角剖分。

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

2.3 算法分析

本文算法的創新點在于利用空間多邊形取代了傳統分割方法中的平面片，并對空間多邊形進行了三角剖分，提高了逼近精度，故求交精度也相應提高。具體表現為：

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

當用平面片近似曲面片時，未考慮到曲面片邊界曲線的彎曲帶來的近似誤差，而本文算法中的空間多邊形正是以曲面片的輪廓為基礎構造出的，故有效地避免了曲面片邊界曲線帶來的誤差。

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

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

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

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

3 數值試驗

3.1 實例

圖3為2個3×3的Bézier曲面，紅色的點表示Bézier曲面的控制頂點，分別利用曲面分割求交算法與基于空間多邊形三角剖分的曲面分割算法對3個曲面進行求交運算。

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

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

圖3 2張Bézier曲面

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

圖4 2個Bézier子曲面片

分別利用曲面分割求交算法與基于空間多邊形三角剖分的曲面分割算法對2個子曲面片進行求交計算，結果如圖5和圖6所示。其中藍色的線框表示用于近似曲面片的三角形組，可以看出本文算法得到的線框要比傳統的分割算法得到的線框更接近曲面的真實形狀，與預期相符。黃色和綠色的線條分別表示2種算法最終求得的交線。在該實例中，2種算法求得的交點見表1和表2中的交點坐標列。

圖5 分割求交算法

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

表1 傳統的分割算法 交點坐標交點投影之間的距離 (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 基于空間多邊形三角剖分的分割算法 交點坐標交點投影之間的距離 (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 結果分析

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

通過觀察可知，傳統的曲面分割求交算法丟失了交線，且求得的交點比本文算法求得的交點距離與真實交點的距離更遠，故基于空間多邊形三角剖分的曲面分割求交算法要優于傳統的曲面分割求交算法。

(a) 2種算法的求交結果對比(一)

(b) 2種算法的求交結果對比(二)

圖7 2種算法的求交結果對比

下面通過數值比較2種算法的求交結果。將交點依次投影到2張相交曲面上，計算2個投影點之間的距離?？芍嚯x越小，則交點的準確度越高。

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

依次將所求交點投影到2張曲面，并計算投影點之間的距離。由表1和表2可以看出，本文算法求得的交點投影點之間的最大距離均小于傳統分割求交算法求得的交點投影點之間的最小距離，并且在本例中傳統的曲面分割求交算法出現了丟失交線的現象，故得出：本文算法要優于傳統的曲面分割求交算法。

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

注意：

(1) 傳統的分割算法用于曲面1，3相交時，出現了交線丟失，故不存在傳統的分割算法用于曲面1，3相交時的交點表。

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

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

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

通過表1和表2數值比較，可得出理論與觀察相同的結論：基于空間多邊形三角剖分的曲面分割求交算法比傳統的曲面分割求交算法得出的交點更加精確。

4 結語與討論

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

參考文獻

[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] 朱永強, 魯聰達. 自由曲線曲面造型技術的綜述[J]. 中國制造業信息化, 2003, 32(5): 110-113.

[3] 李新友. 曲面分割求交方法的實現[J]. 計算機輔助設計與圖形學學報, 1989(1): 46-50.

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

[5] 張華, 葉顯高, 李德群. 基于網格劃分的曲面求交算法[J]. 計算機應用, 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] 許曉革, 冀陽峰, 楊蕾. 曲面離散跟蹤求交算法的研究[J]. 工程圖學學報, 2005, 26(1): 61-64.

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

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

[10] 李寧, 田震, 張立華, 等. 優化的三角網格曲面求交算法[J]. 遼寧工程技術大學學報(自然科學版), 2013, 32(9): 1269-1273.

[11] 馬小虎, 潘志庚, 石教英. 基于凹凸頂點判定的簡單多邊形Delaunay三角剖分[J]. 計算機輔助設計與圖形學學報, 1999, 11(1): 1-3.

[12] 田中朝. 三角網格曲面重建及求交理論、方法研究[D]. 淄博: 山東理工大學, 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

中圖分類號：TP 391.41

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

文獻標識碼：A

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

收稿日期：2018-08-30；

定稿日期：2018-09-11

第一作者：史永豐(1980-)，男，湖南郴州人，高級工程師，碩士。主要研究方向為CAD、計算機圖形學。E-mail：shiyf@avic-digital.com

通信作者：程 婷(1988-)，女，山西晉中人，工程師，博士。主要研究方向為CAGD、CAD、計算機圖形學。E-mail：chengt@avic-digital.com