OpenCASCADE曲面求交之追蹤法

eryar@163.com

1 Introduction

朱心雄等著《自由曲線曲面造型技術(shù)》書中對(duì)曲面求交的追蹤法（Marching method）有詳細(xì)介紹，首先曲面求交追蹤法的提出是1990年R.E. BARNHILL和S.N. KERSEY的一篇論文：A marching method for parametric surface/surface intersection感興趣的可以下載來(lái)看看原文：

1990年我才幾歲，那時(shí)家里有黑白電視機(jī)已經(jīng)算不錯(cuò)的。對(duì)于一般NURBS曲面的求交，先用分割離散法求得交線的拓樸結(jié)構(gòu)和交點(diǎn)的估計(jì)值，然后再應(yīng)用迭代法根據(jù)估計(jì)值求得精確交點(diǎn)。如果認(rèn)為交點(diǎn)分布不夠細(xì)密，可以對(duì)網(wǎng)格進(jìn)行加密，再應(yīng)用迭代法得到新的精確交點(diǎn)，由此可以獲得完整、致密的精確交線，而無(wú)需應(yīng)用追蹤法。

2 追蹤法的原理

追蹤法的原理：假設(shè)兩曲面間共有N個(gè)交線環(huán)，先通過(guò)某種求交方法確定各交線環(huán)上的一個(gè)交點(diǎn)，然后以該交點(diǎn)為初始交點(diǎn)，根據(jù)交線的幾何性質(zhì)，按照一定步長(zhǎng)計(jì)算該條交線上下一交點(diǎn)的近似值，再應(yīng)用迭代法求得精確交點(diǎn)。沿交線走向不斷前進(jìn)，直到遍歷整條交線。追蹤法的優(yōu)點(diǎn)是在求得首交點(diǎn)后搜索交線其余交點(diǎn)的速度非常快，且適用范圍廣。不論何種參數(shù)曲面，只要曲面不存在非正則點(diǎn)，并可以求得曲面上任意點(diǎn)的坐標(biāo)位置、法矢、切矢等幾何信息，就可以用追蹤法求交。追蹤法的問題是目前尚無(wú)非常有效的方法來(lái)求得所有交線環(huán)的起始點(diǎn)。在有些情況下尋求初始點(diǎn)所花費(fèi)的時(shí)間遠(yuǎn)大于追蹤法過(guò)程中所節(jié)省的時(shí)間，而為了節(jié)省尋求初始點(diǎn)的時(shí)間，又可能漏掉某些交線，當(dāng)在孤立交點(diǎn)和比較小的交線環(huán)時(shí)尤甚。

3 追蹤法的實(shí)現(xiàn)

OpenCASCADE實(shí)現(xiàn)曲面求交追蹤法的類是IntWalk_PWalking，注意看類注釋中的單詞marching:

追蹤法中需要解決兩個(gè)問題：

• 如何確定追蹤方向：目前常用切線法確定追蹤方向，即估計(jì)真實(shí)交線在該點(diǎn)的切線方向，并以此作為追蹤方向。當(dāng)曲面間存在切點(diǎn)時(shí)，由于在切點(diǎn)附近兩曲面的法矢非常接近，無(wú)法確定追蹤方向，這也就是所謂的“迷向”問題（Tangent tracks）。在類IntWalk_PWalking中，追蹤方向作為成員變量tgdir，將迭代法計(jì)算的交線的切向量保存起來(lái)，當(dāng)有“迷向”問題時(shí)，調(diào)用函數(shù)RepartirOuDiviser來(lái)修復(fù)。
• 如何確定追蹤步長(zhǎng)：追蹤步長(zhǎng)的選擇通常有兩種方法：1）固定步長(zhǎng)和2）變步長(zhǎng)也稱為自適應(yīng)步長(zhǎng)法Adaptive Step。因?yàn)榈ㄊ歉鶕?jù)估計(jì)點(diǎn)的參數(shù)來(lái)計(jì)算精確交點(diǎn)，為了避免根據(jù)點(diǎn)反求參數(shù)，直接根據(jù)切線方向的X,Y分量來(lái)確定參數(shù)的步長(zhǎng)。雖然有些變化，總體上看使用的是固定步長(zhǎng)法。若直接根據(jù)交線切線方向tgdir乘以步長(zhǎng)得到點(diǎn)，是需要反求點(diǎn)在曲面上的參數(shù)。步長(zhǎng)主要與精度設(shè)置有關(guān)，精度設(shè)置高，步長(zhǎng)越小，則會(huì)導(dǎo)致計(jì)算速度慢，求出的交點(diǎn)過(guò)密，還可能帶來(lái)不穩(wěn)定因素。如步長(zhǎng)過(guò)大，可能 會(huì)導(dǎo)致迭代不收斂或者跳到另外 一條交線上。

使用默認(rèn)精度設(shè)置，追蹤法得到的交點(diǎn)數(shù)量就很大。若設(shè)置精度低，交點(diǎn)數(shù)量會(huì)明顯減少，提高計(jì)算速度。

如上圖所示，若兩個(gè)曲面只有一個(gè)交線，使用有追蹤法時(shí)只需要指定交線的初始交點(diǎn)，即可以得到整個(gè)交線。當(dāng)兩曲面有多個(gè)交線或有孤立交點(diǎn)時(shí)，就需要找出多個(gè)交線的起始交點(diǎn)：

上圖所示位置交線斷開生成兩條交線，一個(gè)是綠色一個(gè)是紅色，這種情況就需要分別指出兩個(gè)交線起始點(diǎn)。

4 Conclusion

綜上所述，曲面求交追蹤法的優(yōu)點(diǎn)是在求得首交點(diǎn)后搜索交線其余交點(diǎn)的速度非常快，且適用范圍廣。追蹤法的問題是目前尚無(wú)非常有效的方法來(lái)求得所有交線環(huán)的起始點(diǎn)。曲面求交一般會(huì)采用通用性較好的網(wǎng)格法-迭代法-追蹤法三者相結(jié)合的方法。應(yīng)用網(wǎng)格法求得交點(diǎn)的初始估計(jì)值，再用迭代法求得精確交點(diǎn)，并以其為起點(diǎn)進(jìn)行追蹤，直到得到整條精確交線。

IntWalk_PWalking追蹤法的步長(zhǎng)與精度密切相關(guān)，選擇合適的精度，可以使交線的交點(diǎn)數(shù)量少，提高計(jì)算速度。因?yàn)榫仍礁咦粉欉^(guò)程中得到的追蹤點(diǎn)越多，對(duì)于每個(gè)追蹤點(diǎn)都需要使用迭代法計(jì)算精確交點(diǎn)。