一種改進的基于微分方程的曲面求交跟蹤算法

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

?

一種改進的基于微分方程的曲面求交跟蹤算法

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

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

參數(shù)曲面求交是計算機輔助幾何設(shè)計領(lǐng)域中的關(guān)鍵技術(shù)之一。針對傳統(tǒng)跟蹤算法中曲面求交的漏交和法向共線點處難于處理的問題，提出一種改進的基于微分方程的跟蹤算法。首先選擇邊界點和拐點作為跟蹤的起點，解決了漏交問題。并采用基于交線微分形式的跟蹤公式計算后繼交點，解決了法向共線點處難于處理的問題。最后利用牛頓迭代得到精確交點。該算法不僅正確地跟蹤到交線的每個分支，而且易于處理法向共線點處的跟蹤，不遺漏關(guān)鍵點，解決了傳統(tǒng)跟蹤法在法向共線點處交線不連續(xù)的問題。與傳統(tǒng)跟蹤法對比，其魯棒性和穩(wěn)定性更強，精度更高且收斂略快，適用于求解任意參數(shù)曲面求交問題。

曲面求交；跟蹤法；微分方程；法向共線點

參數(shù)曲面求交是CAGD/CAM中關(guān)鍵技術(shù)之一，被廣泛應(yīng)用于曲面造型(如剪裁[1]、過渡[2])、實體造型(如布爾運算)[3]、制造仿真[4]、人工智能[5]等多個領(lǐng)域中。

常見的求交方法主要有5種：代數(shù)法[6]、網(wǎng)格離散法[7-9]、分割法[10-11]、迭代法[12]以及跟蹤法[13-14]。跟蹤法[15-16]需從事先求出的初始交點出發(fā)，根據(jù)交線的局部幾何關(guān)系相繼跟蹤下一個交點，最后把追蹤得到的所有點按序連接起來，從而求出交線。該方法適用范圍廣、精度高，較為穩(wěn)定，適用于任意參數(shù)曲面求交。

然而傳統(tǒng)跟蹤法也有一定的缺點，主要表現(xiàn)為：

(1) 尚無有效的方法求得所有交線環(huán)的初始點，容易漏交。

(2) 難以確定法向共線點處的跟蹤方向，產(chǎn)生的交線帶有間斷點，不能得到連續(xù)完整的交線[17]。

(3) 邊界處難于處理，收斂速度慢，不穩(wěn)定。

鑒于此，本文對上述問題作進一步研究，首先選擇邊界點和拐點作為跟蹤的起點，然后利用交線的微分形式將跟蹤點投影到參數(shù)域中計算后繼交點，最后利用牛頓迭代得到精確交點。

1 基于微分方程的跟蹤算法原理

傳統(tǒng)的參數(shù)曲面跟蹤求交，需要先用分割法或網(wǎng)格法求得交線的拓撲結(jié)構(gòu)和交點的估計值作為跟蹤起點。因此，分析交線的拓撲結(jié)構(gòu)并選擇恰當?shù)某跏键c成為跟蹤算法首要解決的問題。

1.1 確定跟蹤起點

曲面交線有兩種常見的拓撲結(jié)構(gòu)：交線段和閉環(huán)。而交線段和閉環(huán)上還可能存在法向共線點，兩曲面在該點處的法向量是共向的，無法確定在該點處的跟蹤方向。另外，當跟蹤到這些法向共線點附近時，還可能存在不同分支距離很近的情況，此時若跟蹤步長過大容易出現(xiàn)跟蹤偏離或者循環(huán)。為了避免上述情況，本文通過拓撲分析找到其法向共線點，當跟蹤到這些點附近時，減小步長，避免偏離和循環(huán)的發(fā)生，并通過本文的跟蹤過程(2.2節(jié))計算在法向共線點處的跟蹤方向，繼續(xù)跟蹤。

1.1.1 法向共線點和拐點

對于兩參數(shù)曲面(,)與(,)的求交。由上文可知，法向共線點在跟蹤過程中扮演很重要的角色，需要求出該2曲面所有的法向共線點。由文獻[17]，求解法向共線點等價于求解如下非線性方程組

為了正確地跟蹤交線上的所有閉環(huán)，需找到每一閉環(huán)上的一個點作為跟蹤起點。文獻[15]中已證明只要找到拐點或拐點，即可開始跟蹤閉環(huán)。先給出拐點的定義。

1.1.2 交線的拓撲分析

為了確保跟蹤正確，有2個關(guān)鍵點：

(1) 跟蹤起點為中的元素。

(2) 每一步跟蹤時，都要檢查當前點是否在法向共線點附近。若在，則減小跟蹤步長，防止跟蹤的偏離或循環(huán)的發(fā)生。若當前點就是法向共線點，則計算法向共線點處的跟蹤方向，繼續(xù)跟蹤。

1.2 跟蹤交線

1.2.1 交線的微分形式

設(shè)兩參數(shù)曲面分別為(,)與(,)，并假設(shè),至少是1的，則求該2曲面的交線，即

也就是說，當交點集合非空，2曲面相交，且集合包含1條或幾條交線段，對于任意的參數(shù)每一條交線段均滿足條件

其為交線的空間曲線方程。在2個參數(shù)域上的投影分別為兩平面曲線。

曲面和在交線上的一點(,,,)處的單位法矢分別為

由微分幾何中交線上一點的法矢與切矢垂直可得

而由式(3)與式(4)可直接得到的微分

將式(7)代入式(6)可得方程組

求解上述方程組可得

其中，D1，D2為常數(shù)。若令

式(9)與式(11)都為交線式(3)的微分形式。

1.2.2 確定后繼交點

傳統(tǒng)的跟蹤法確定下一個交點的過程，通常是在給定起點后，沿著交線的切矢方向前進一定的步長，跟蹤需在點的三維空間中進行，想要獲得點的參數(shù)坐標還需要通過牛頓迭代，并且無法確定在法向共線點處的跟蹤方向。

另外，文獻[15]說明了由于式(9)與(11)有兩個常數(shù)D1，D2，因此在確定跟蹤公式(12)中的步長時，有一定的自由度。其既能保證Euler方法是收斂的，又使交線的參數(shù)分布均勻。

1.2.3 算法關(guān)鍵點

上文已經(jīng)比較詳細地說明了跟蹤算法的全過程，但在實際應(yīng)用中，仍需要有幾點值得注意：

令()=(,,,)=(,,,)·n(,)，將(+d)在處二階泰勒展開得到關(guān)于的一元二次方程

其中，=p·n，=p·n，=p·n，=–2，求解上述方程得

對分0；=0；0 3種情況討論，可確定法向共線點的類型及跟蹤方向[10]，解決了傳統(tǒng)跟蹤算法在法向共線點處難于處理的問題。

(2) 利用式(12)迭代地計算后繼交點的終止條件為：①(,)和(,)中任意一個的參數(shù)值超出其定義域；②跟蹤到起點(包括邊界點和拐點)。

(3) 本文選擇4參數(shù)迭代法[14]作為得到精確交點的方法，并規(guī)定迭代的最大次數(shù)及算法終止的精度閾值。事實上，在2.1節(jié)的數(shù)值實驗中，一般只需要2~4次迭代即可達到精度要求。

(4) 針對跟蹤過程可能會出現(xiàn)跟蹤起點的冗余問題，即跟蹤得到的某條交線可能通過跟蹤起點集合里的某幾個點，需對跟蹤起點集合進行檢查，刪去該交線已經(jīng)通過的跟蹤起點，避免對同一條交線重復(fù)計算。本文規(guī)定一個最小距離標準，即刪除與交線間距離小于給定的最小距離的點。

2 數(shù)值實驗

本文數(shù)值實驗根據(jù)微分方程的跟蹤算法進行測試，來說明算法的處理能力。算法的控制參數(shù)如下：4參數(shù)迭代法的精度閾值=10–6，控制迭代的最大次數(shù)為10 000。對于傳統(tǒng)的跟蹤法，其跟蹤起點為利用網(wǎng)格法求交得到的交點。本算法適用于任何光滑曲面(片)，這里選取Bézier曲面進行測試。若要選取NURBS曲面，可以根據(jù)文獻[19]轉(zhuǎn)化為Bézier曲面。

2.1 實驗用例

充分考慮2曲面間交線的情況。交線分為2種：交線段和閉環(huán)。交線段包括只有邊界點，無拐點交線段、有邊界點及拐點的交線段。閉環(huán)選取有法向共線點和拐點的環(huán)，共3個實驗來測試本文算法。

2.1.1 有邊界點、無拐點的交線段

2個3×2次Bézier曲面相交形成如圖1所示的只有邊界點，無拐點的交線段。

兩曲面的控制頂點如下

該交線2邊界點的參數(shù)分別為(,,,)= (0.0286, 0.0968, 0.0325, 0.0973)和(,,,)= (0.9958, 0.9549, 0.7377, 0.9550)。

2.1.2 有邊界點和拐點的交線段

2曲面的表達式分別為

圖2為上述兩曲面的交線及對應(yīng)的參數(shù)域。該交線為含有2個邊界點和1個u拐點的交線段，交線兩邊界點的參數(shù)分別為(u, v, s, t)=(0.0008, 9.5125, 0.0183, 9.5116)和(u, v, s, t)=(9.5116, 0.0183, 9.5125, 0.0008), 在(u, v)=(9.5081, 0.0814)處交線存在u拐點。

2.1.3 有法向共線點和拐點的閉環(huán)

為了驗證本文算法能否正確完整地跟蹤含有閉環(huán)結(jié)構(gòu)的交線，還需考慮了2曲面間的交線為含有法向共線點和拐點的閉環(huán)。

2曲面的表達式分別為

圖3為利用本文算法與傳統(tǒng)的跟蹤算法計算得到的上述2曲面交線及其對應(yīng)的參數(shù)域。利用本文算法計算得到，在?參數(shù)域上，交線在點(,)=(0.2084, 0.2566)和(,)=(1.5250, 1.3645)處存在法向共線點，在點(,)=(1.5608, 1.2223)，(,)=(0.1956, 0.2902)存在拐點，并且可以獲得完整的不存在間斷點的閉環(huán)。

最后，驗證了對于任意含有法向共線點的閉環(huán)，通過微分形式的曲面求交跟蹤算法，均可以得到完整的閉環(huán)，2求交曲面的表達式為

求交得出的完整閉環(huán)如圖4所示。

圖4 含有法向共線點的閉環(huán)驗證

2.2 性能分析

對于曲面求交算法的魯棒性，表現(xiàn)在2個方面：①不遺漏關(guān)鍵點；②保證求得的結(jié)果與實際交線拓撲一致。由上文可知，利用本文算法在以上3個實驗中進行測試均能計算出與實際交線拓撲一致的交線，并且沒有遺漏法向共線點和拐點這樣的關(guān)鍵點，交線完整且連續(xù)。然而在利用傳統(tǒng)跟蹤法計算含有法向共線點和拐點的閉環(huán)交線時，由圖3看出，閉環(huán)交線在2個法向共線點處存在間斷點。同時，由于傳統(tǒng)跟蹤法無法處理法向共線點處的精確求解問題，因此在法向共線點(,)=(?0.0010, 0.0729)處，傳統(tǒng)跟蹤法在其附近的跟蹤過程表現(xiàn)出明顯的數(shù)值不穩(wěn)定性，該點與利用式(1)精確計算得到的法向共線點有些偏離，從而計算出的交線與實際交線有所偏差。上述事實也驗證了本文算法在經(jīng)過精確的拓撲分析以及有效的跟蹤過程后具有一定的穩(wěn)定性和魯棒性。

最后，驗證算法的跟蹤效率，將算法跟蹤過程的時間和得到的交點數(shù)作為驗證算法跟蹤效率的比較指標。時間取50次跟蹤交線過程所需時間的平均值。表1和表2為上述3個實例下2種算法跟蹤效率的比較結(jié)果。

表1 傳統(tǒng)跟蹤法的實驗數(shù)據(jù)

表2 本文算法的實驗數(shù)據(jù)

由表1和表2可知，對于上述3個實例，利用本文算法計算得到的交點數(shù)略多于傳統(tǒng)跟蹤法，而計算時間卻比傳統(tǒng)跟蹤法要少，說明不論是交線段還是閉環(huán)，本文算法每計算1個交點所用時間更少，也就是說其跟蹤過程能夠更快的收斂，克服了傳統(tǒng)跟蹤法在邊界和法向共線點附近收斂慢，不穩(wěn)定的缺點。綜上，本文算法有效地兼顧了魯棒性和效率2個方面。

3 結(jié)論與討論

鑒于曲面求交難于處理的漏交和法向共線點處的跟蹤問題，本文提出一種改進的基于微分方程的跟蹤算法。該算法選擇邊界點和拐點作為跟蹤的起點，解決了傳統(tǒng)跟蹤算法的漏交問題，并采用基于交線微分形式的跟蹤公式計算后繼交點，解決了傳統(tǒng)跟蹤算法在法向共線點處難于處理的問題，最后利用牛頓迭代得到精確交點。該算法不僅正確地跟蹤到交線的每個分支，而且易于處理法向共線點處的跟蹤，不遺漏關(guān)鍵點，能產(chǎn)生完整連續(xù)的交線。與傳統(tǒng)跟蹤法相比，魯棒和穩(wěn)定性更強，精度更高且收斂略快，適用于求解任意參數(shù)曲面求交問題。若初始點不在邊界、拐點處，有可能導(dǎo)致求交失敗。有效選取初始點仍是跟蹤問題難點之一，有待進一步研究。

[1] 伯彭波, 袁野, 張彩明. 可展曲面的自動識別與重建[J].計算機輔助設(shè)計與圖形學學報, 2016, 28(9): 1428-1435.

[2] 馬翔, 康寶生, 周儒榮. 一種用NURBS表示的過渡曲面的生成方法[J]. 航空學報, 1992, 13(12): 678-681.

[3] 周建華, 琚建軍, 范玉青. 高效可靠的實體造型隱藏線刪除算法[J]. 工程圖學學報, 1993, 14(2): 54-62.

[4] 李丹, 良辰. 高制造與仿真[J].航空制造技術(shù), 2017, 2017(4): 32-33.

[5] 葛文武, 韓江洪, 魏臻, 等. 最小最大車輛路徑問題的動態(tài)自適應(yīng)蟻群優(yōu)化算法[J]. 模式識別與人工智能, 2015, 28(10):930-938.

[6] PRATT M J, GEISOW A D. Surface/surface Intersection Problems. The Mathematics of Surface [M]. Oxford: Oxford University Press, 1986: 117-142.

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

[8] 蔣錢平, 唐杰, 袁春風. 基于平均單元格的三角網(wǎng)格曲面快速求交算法[J]. 計算機工程, 2008, 34(21): 172-174.

[9] 花衛(wèi)華, 鄧偉萍, 劉修國, 等. 一種改進的不規(guī)則三角網(wǎng)格曲面切割算法[J]. 中國地質(zhì)大學報, 2006, 31(5): 619-623.

[10] HONGHTON E G, EMENTT R F, FACTOR J D. Implementation of a divide-and-conquer method for intersection of parametric surfaces [J]. Computer Aided Geometric Design, 1985, 2(1-3): 173-183.

[11] 席平. 任意參數(shù)曲面的分割求交算法[J]. 北京航空航天大學學報, 1984, 3: 71-80.

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

[13] BARNHILL R E, KERSEY S N. A marching method for parametric surface/surface intersection [J]. Computer Aided Geometric Design, 1990, 7(1-4): 257-280.

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

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

[16] 楊寶光. 一種高效可靠的多項式參數(shù)曲面求交算法[D]. 杭州: 浙江大學, 2006.

[17] SHERBROOKE E C, PATRIKALAKIS N M. Computation of the solutions of nonlinear polynomial systems [J]. Computer Aided Geometric Design, 1993, 10(5): 379-405.

[18] 朱心雄. 自由曲線曲面造型技術(shù)[M]. 北京: 科學出版社, 2000: 1-391.

[19] SHEN J J, BUSé L, ALLIEZ P, et al. A line/trimmed NURBS surface intersection algorithm using matrix representations [J]. Computer Aided Geometric Design, 2016, 48: 1-16.

An Improved Algorithm for Tracing Surface Intersection Based on Differential Equation

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

(Jinhang Digital Technology co. LTD, Beijing 100028, China)

Intersection of parametric surfaces is one of the key technologies in the field of computer aided geometric design (CAGD). In this paper, an improved tracing algorithm based on differential equation is proposed to solve the problem in traditional tracing algorithm of missing intersection line and difficulty to trace at normal collinear points. Firstly, the algorithm chooses the boundary points and the inflection points as the starting points of the tracing, so it solves the problem of missing intersection line. Then the tracing formula based on the differential form is used to calculate the successor intersection, which solves the problem of processing tracing at normal collinear points. Finally, the Newton iteration is used to get the exact intersection. The algorithm not only correctly traces each branch of the intersection line, but also is easy to deal with the tracing at normal collinear points. Without missing the key points, the algorithm solves the problem that the traditional tracing method is not continuous at the normal collinear points. Compared with the traditional tracing method, its robustness and stability are stronger characterized with higher precision and slightly faster convergence, and it is suitable for solving any parametric surface intersection problem.

surface intersection; tracing method; differential equation; normal collinear points

TP 391.41

10.11996/JG.j.2095-302X.2019020290

A

2095-302X(2019)02-0290-06

2018-08-30；

2018-09-11

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

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