龐乾一,王振飛,陳小雕

(杭州電子科技大學(xué)計(jì)算機(jī)學(xué)院,浙江 杭州 310018)

0 引 言

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

1 算法原理

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

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

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

X·N2+d2=0

(1)

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

(2)

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

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

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

(3)

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

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

(4)

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

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

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

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

(5)

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

2 實(shí)例分析

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

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

運(yùn)用本文算法得到參數(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曲面相交,設(shè)定Hausdorff距離閾值為10-3。

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

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

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

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

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

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

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

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

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

3 結(jié)束語

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