OpenCASCADE曲面求交之追蹤法

eryar@163.com

1 Introduction

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

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

2 追蹤法的原理

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

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

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

追蹤法中需要解決兩個問題：

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

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

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

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

4 Conclusion

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

IntWalk_PWalking追蹤法的步長與精度密切相關(guān)，選擇合適的精度，可以使交線的交點數(shù)量少，提高計算速度。因為精度越高追蹤過程中得到的追蹤點越多，對于每個追蹤點都需要使用迭代法計算精確交點。