基于重新參數(shù)化的Bézier曲面求交算法

龐乾一,王振飛,陳小雕

(杭州電子科技大學計算機學院,浙江 杭州 310018)

0 引 言

參數(shù)曲面求交是計算機輔助幾何設計中基本且重要的問題,也是布爾運算的基礎。Bézier曲面和NURBS曲面作為最常用的參數(shù)曲面,其求交運算廣泛應用于計算機動畫[1]、曲面裁剪[2]、數(shù)控加工[3]、制造仿真[4]、地質建模[5]等領域。常用的Bézier參數(shù)曲面求交方法包括代數(shù)法[4]、網(wǎng)格離散法[6]、迭代法[7]、跟蹤法[8]等。代數(shù)法將2個參數(shù)曲面相交問題轉化為非線性方程組的求解問題,僅在計算低階曲面相交時有效,雖然可以通過函數(shù)合成[9]獲得相交線的精確表示,但其階數(shù)過高,無法在實際中使用。網(wǎng)格離散法將曲面離散為由三角平面片組成的網(wǎng)格,將參數(shù)曲面相交問題轉化為三角形面片之間的求交運算,通用性強,但曲面的劃分需要足夠細密,計算耗時明顯增加。迭代法根據(jù)初始交點在2個曲面上的投影點,通過四參數(shù)迭代法求解下一交點,不能單獨使用迭代法,且要求交點初值盡可能準確,否則迭代不收斂,無法得到滿足精度要求的交點。跟蹤法從提前求出的初始交點出發(fā),根據(jù)交線的幾何特性,按照一定的步長迭代計算后繼交點,將這些離散點按順序連接并再次用B樣條擬合。跟蹤法存在漏交問題,在法向共線點處的跟蹤方向產(chǎn)生的交點不連續(xù),且收斂速度慢,不穩(wěn)定。文獻[10]采用基于交線微分形式的跟蹤公式計算后繼交點,解決了法向共線點處交點間斷不連續(xù)的問題,但是,若精度要求很高,則需要很小的跟蹤步長,導致跟蹤步數(shù)和耗時均顯著增加。上述曲面求交方法在求得一系列交點之后,需要再次用B樣條插值才能表示出交線,且求得的近似曲面交線不能嚴格落在任何一個曲面上。為此,本文提出一種基于重新參數(shù)化的Bézier曲面求交算法,把曲面控制網(wǎng)格的交線近似為曲面的交線,并將其映射到參數(shù)域進行擬合,在計算交點個數(shù)較少的同時得到較高的逼近精度,且求解出的交線嚴格落在指定的一個曲面上。

1 算法原理

1.1 曲面控制網(wǎng)格的求交

曲面控制網(wǎng)格求交的基本思想是先將2個曲面都升階10次從而加密曲面的控制網(wǎng)格,再將控制網(wǎng)格轉化為三角網(wǎng)格,每個三角形對應空間中的1個平面,將曲面對求交轉化為三角面片對求交。

首先,判斷三角形T1與三角形T2所在平面是否相交。平面F2的計算公式如下:

X·N2+d2=0

(1)

將三角形T1的3個頂點分別代入式(1),得到各頂點到平面F2的距離為:

(2)

然后,根據(jù)三角形的3條邊與對方三角形的交點求得三角形對的交線段,將所有相交三角形對的交線段依次相連,得到控制網(wǎng)格的交線。

1.2 參數(shù)域上的交線擬合

張量積形式的Bézier曲面定義為:

(3)

首先,采用1.1節(jié)中求交方法求得交點的重心坐標,將交點直接映射到2個曲面各自的參數(shù)域,得到參數(shù)域中的交點坐標,并將這些交點按順序連接,得到控制網(wǎng)格交線映射到參數(shù)域中的折線段。由于交點在兩曲面的控制網(wǎng)格重心坐標并不相同,所以映射到兩曲面各自參數(shù)域中的折線段也不相同。

然后,用分段2次均勻B樣條分別擬合2個曲面參數(shù)域中的折線段。B樣條的節(jié)點矢量采用均勻節(jié)點,即

(4)

式中,r為B樣條的擬合次數(shù),k為節(jié)點矢量的個數(shù),q為B樣條控制頂點的個數(shù)。

將2個曲面參數(shù)域交線按照u向或者v向分為2段,對這2段都使用6個控制點的2次B樣條曲線進行擬合,得到2個曲面各自參數(shù)域中擬合后對應的多段B樣條曲線。

1.3 重新參數(shù)化函數(shù)的牛頓迭代求精

將2個曲面參數(shù)域中的分段2次B樣條曲線作為重新參數(shù)化函數(shù),分別代入到2個曲面中,得到曲面上的2條曲線。當這2條曲線之間的Hausdorff距離足夠小時,可將其中1條曲線當作2個曲面的交線。由此,設置每一段的牛頓迭代目標函數(shù)為:

(5)

從1.2節(jié)曲線的分段參數(shù)區(qū)間內映射到參數(shù)域的交點值中均勻取樣4個點,作為牛頓迭代的初始值。因為給出的初始值已是較為接近的結果,所以點映射到參數(shù)域經(jīng)過不超過10次的迭代即可使得目標函數(shù)小于某個閾值,從而可以認為迭代得到的結果就是最終的近似交線。設置最大迭代次數(shù)為30次,如果某段擬合結果的Hausdorff距離在達到最大迭代次數(shù)時的結果仍然不滿足精度要求,就將該段按照u向或者v向二分,然后再分別用2次B樣條擬合迭代求解。

2 實例分析

通過2個數(shù)值實例來驗證本文提出算法的有效性。算法的控制參數(shù)如下:牛頓迭代目標函數(shù)的精度為10-7,Hausdorff距離閾值設定為10-3,迭代最大次數(shù)為30。實驗在CPU為Intel(R) Core(TM) i5-6300HQ 2.3 GHz,內存為12 GB的64位win10操作系統(tǒng)的PC上運行。

例12個2×2次Bézier曲面相交,Hausdorff距離閾值為10-3。

運用本文算法得到參數(shù)域分段2次B樣條擬合曲線,并代入其中1個曲面得到的交線如圖1所示。

圖1 本文算法求得的曲面1和曲面2交線圖

曲面1和曲面2的參數(shù)域擬合圖分別如圖2和圖3所示。

圖2 曲面1的參數(shù)域擬合圖

圖3 曲面2的參數(shù)域擬合圖

從圖2和圖3可以看出,只要經(jīng)過2次二分即可得到滿足Hausdorff距離精度要求的參數(shù)域函數(shù)。

例22個2×2次Bézier曲面相交,設定Hausdorff距離閾值為10-3。

運用本文算法得到參數(shù)域分段2次B樣條擬合曲線,并代入其中1個曲面得到的交線如圖4所示。

圖4 本文算法求得的曲面3和曲面4交線圖

曲面3和曲面4的參數(shù)域擬合圖分別如圖5和圖6所示。

圖5 曲面3的參數(shù)域擬合圖

圖6 曲面4的參數(shù)域擬合圖

分別采用本文算法和傳統(tǒng)跟蹤法進行求交結果精度的比較。傳統(tǒng)跟蹤法在給出初始點之后,以不同的步長進行跟蹤,再將求得的交點用3次B樣條插值,得到最終的近似交線,此交線與精確交線的Hausdorff距離值如表1所示,本文算法求得的交線與精確交線的Hausdorff距離如表2所示。

表1 傳統(tǒng)跟蹤法的求交結果與精確交線的Hausdorff距離

表2 本文算法的求交結果與精確交線的Hausdorff距離

從表1和表2可知,與傳統(tǒng)的跟蹤算法比較,本文算法在二分2次時精度值即可達到10-3。因為本文算法先對曲面進行有限次升階,再求控制網(wǎng)格交線從而得到初始值,該初始值已較為接近結果,所以,2個實例中,經(jīng)過2～3次的區(qū)間二分,每段交線的迭代次數(shù)不超過10次即可得到滿足精度要求的交線。同時,本文算法中,每段交線在參數(shù)域上都是用6個控制點,2次B樣條擬合,每段端點處有重疊,所以二分3次的總控制頂點數(shù)只有21個,頂點數(shù)明顯少于傳統(tǒng)跟蹤法。

3 結束語

本文提出一種基于重新參數(shù)化的Bézier曲面求交算法,在計算交點個數(shù)更少的同時,獲得更高的逼近精度,且交線嚴格落在其中一個指定的曲面上。算法仍然有較大的改進空間,擬合交點的選取及優(yōu)化可進一步提升逼近精度。此外,若參數(shù)域內對應的曲線形狀較為復雜,則需將參數(shù)域的交線分為較多段擬合才能得到較為精確的結果,數(shù)值計算的耗時和計算穩(wěn)定性將面臨更大的挑戰(zhàn)。