OpenCASCADE曲面求交之網(wǎng)格離散法2

eryar@163.com

1 Introduction

由朱心雄等著《自由曲線曲面造型技術(shù)》書中對曲面求交之網(wǎng)格離散法描述如下：該法的基本思想是先將曲面離散為由小平面片組成的網(wǎng)格，當(dāng)網(wǎng)格足夠密時，可以認(rèn)為已經(jīng)非常接近真實曲面，對分別表示不同曲面的兩張網(wǎng)格，利用平面片求交法求得的交線，并以此交線近似代表曲面間的交線。這種方法原理簡明，便于實現(xiàn)，適用范圍廣，任意參數(shù)曲面均可利用該法求交。但為獲取精確地交線，則必須生成非常細(xì)密的網(wǎng)格，這將導(dǎo)致占用內(nèi)存多，計算花費(fèi)大。因此，實際工作中很少單一使用離散網(wǎng)格法，而常將其與其他方法結(jié)合使用。

OpenCASCADE中對于曲面求交也提供離散網(wǎng)格法，其中曲面的離散網(wǎng)格由類IntPatch_Polyhedron表示，兩個網(wǎng)格面求交使用類IntPatch_InterferencePolyhedron。本文主要介紹曲面的網(wǎng)格求交類IntPatch_InterferencePolyhedron。

2 Polyhedron Interference

OpenCASCADE中計算兩個三角網(wǎng)格交線的類是IntPatch_InterferencePolyhedron，這個類還可以用來計算一個網(wǎng)格的自交情況。目前是簡單計算兩個網(wǎng)格中所有三角形的相交情況，時間復(fù)雜度為O(nm)或O(n^2)，對于網(wǎng)格三角形數(shù)量大的情況效率很低。為了稍微提高一些性能，引入Bnd_BoundSortBox來加速過濾掉包圍盒不相交的三角形，減少兩個三角形相交計算。

其中函數(shù)Intersect()就是用來計算兩個三角形的相交情況。關(guān)于兩個三角形的快速求交計算，很多網(wǎng)格處理庫都使用了Tomas Moller’s 1997 triangle intersection routine，如

http://geometry-central.net/surface/algorithms/intersection/ 中也提供兩個網(wǎng)格求交函數(shù)：

在使用較廣泛的網(wǎng)格處理庫CGAL中也有相關(guān)計算函數(shù)：

感興趣的同學(xué)可以對比一下這三個庫關(guān)于兩個網(wǎng)格求交的性能，看誰的性能最好，使用了什么技術(shù)。這里只是將OpenCASCADE中計算的求交結(jié)果輸出，首先是面的自相交情況：

其中紅色部分為交線，可以看出在計算自相交時，會生成多余的交線。其中藍(lán)色部分是有重疊三角形的情況。

當(dāng)計算兩個網(wǎng)格交線時，總體上是正確的，不過也會有多余的交線產(chǎn)生。

3 Conclusion

綜上所述，兩個網(wǎng)格相交計算最直接的算法就是兩兩三角形進(jìn)行求交計算，但是對于大網(wǎng)格會有性能問題。OpenCASCADE中兩個網(wǎng)格求交計算會得到多余的交線，目前網(wǎng)格離散求交只是用于B樣條曲面的求交計算的前處理IntPatch_PrmPrmIntersection，從OpenCASCADE計算兩個曲面交線結(jié)果來看，離散網(wǎng)格計算中多余的交線沒有影響最終的計算結(jié)果。大家可以帶著這個問題“離散網(wǎng)格計算得到多余的交線對最終結(jié)果有影響么？”來理解IntPatch_PrmPrmIntersection中曲面求交的實現(xiàn)原理。