Posted on 2023-05-21 20:21
eryar 閱讀(679)
評論(0) 編輯 收藏 引用 所屬分類:
2.OpenCASCADE
OpenCASCADE曲面求交之網格離散法2
eryar@163.com
1 Introduction
由朱心雄等著《自由曲線曲面造型技術》書中對曲面求交之網格離散法描述如下：該法的基本思想是先將曲面離散為由小平面片組成的網格，當網格足夠密時，可以認為已經非常接近真實曲面，對分別表示不同曲面的兩張網格，利用平面片求交法求得的交線，并以此交線近似代表曲面間的交線。這種方法原理簡明，便于實現，適用范圍廣，任意參數曲面均可利用該法求交。但為獲取精確地交線，則必須生成非常細密的網格，這將導致占用內存多，計算花費大。因此，實際工作中很少單一使用離散網格法，而常將其與其他方法結合使用。
OpenCASCADE中對于曲面求交也提供離散網格法，其中曲面的離散網格由類IntPatch_Polyhedron表示，兩個網格面求交使用類IntPatch_InterferencePolyhedron。本文主要介紹曲面的網格求交類IntPatch_InterferencePolyhedron。
2 Polyhedron Interference
OpenCASCADE中計算兩個三角網格交線的類是IntPatch_InterferencePolyhedron，這個類還可以用來計算一個網格的自交情況。目前是簡單計算兩個網格中所有三角形的相交情況，時間復雜度為O(nm)或O(n^2)，對于網格三角形數量大的情況效率很低。為了稍微提高一些性能，引入Bnd_BoundSortBox來加速過濾掉包圍盒不相交的三角形，減少兩個三角形相交計算。
其中函數Intersect()就是用來計算兩個三角形的相交情況。關于兩個三角形的快速求交計算，很多網格處理庫都使用了Tomas Moller’s 1997 triangle intersection routine，如
http://geometry-central.net/surface/algorithms/intersection/ 中也提供兩個網格求交函數：
在使用較廣泛的網格處理庫CGAL中也有相關計算函數：
感興趣的同學可以對比一下這三個庫關于兩個網格求交的性能，看誰的性能最好，使用了什么技術。這里只是將OpenCASCADE中計算的求交結果輸出，首先是面的自相交情況：
其中紅色部分為交線，可以看出在計算自相交時，會生成多余的交線。其中藍色部分是有重疊三角形的情況。
當計算兩個網格交線時，總體上是正確的，不過也會有多余的交線產生。
3 Conclusion
綜上所述，兩個網格相交計算最直接的算法就是兩兩三角形進行求交計算，但是對于大網格會有性能問題。OpenCASCADE中兩個網格求交計算會得到多余的交線，目前網格離散求交只是用于B樣條曲面的求交計算的前處理IntPatch_PrmPrmIntersection，從OpenCASCADE計算兩個曲面交線結果來看，離散網格計算中多余的交線沒有影響最終的計算結果。大家可以帶著這個問題“離散網格計算得到多余的交線對最終結果有影響么？”來理解IntPatch_PrmPrmIntersection中曲面求交的實現原理。