Posted on 2023-12-02 12:20
eryar 閱讀(1721)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
2.OpenCASCADE
OpenCASCADE 曲線求交
eryar@163.com
1 Introduction
OpenCASCADE中提供了二維幾何曲線的求交類Geom2dAPI_InterCurveCurve，對(duì)應(yīng)到三維幾何只提供了GeomAPI_IntCS, GeomAPI_IntSS，沒(méi)有提供幾何的GeomAPI_IntCC求交類。這些幾何求交一般使用的是數(shù)值算法，即解方程。對(duì)于兩條幾何曲線P(u1), Q(u2)，求交就是解P(u1) - Q(u2) = 0這個(gè)方程。為什么對(duì)于三維幾何曲線沒(méi)有提供數(shù)值算法？
對(duì)于拓樸邊提供了求交算法IntTools_EdgeEdge，這個(gè)類是使用類似于曲面求交的離散網(wǎng)格法，使用了離散包圍盒法。
基于包圍合盒的算法是個(gè)遞歸算法，算法思路：
- 1) 檢查兩條邊在參數(shù)范圍內(nèi)的包圍盒，若空間干涉，則進(jìn)行下一步；否則退出本次判斷；
- 2) 找出兩條邊包圍盒的公共部分對(duì)應(yīng)的參數(shù)，若沒(méi)找到，則退出本次判斷；
- 3) 并將第一條邊在參數(shù)范圍內(nèi)分割成2或3部分，執(zhí)行第一步；
- 4) 退出條件：沒(méi)有相交或找到相交的參數(shù)值；
第一次是分別分成2部分：
在遞歸函數(shù)FindSolutions()中，只去對(duì)第一條邊進(jìn)行參數(shù)分割成3部分：
2 輔助函數(shù)
第一個(gè)輔助函數(shù)是FindParameters()，用來(lái)更新第二條邊在第一條邊的的包圍盒中的參數(shù)范圍，使用這個(gè)參數(shù)范圍更新包圍盒。
第二個(gè)輔助函數(shù)是CheckCoincidence()，用來(lái)檢測(cè)兩段邊是否重合。第一步是快速計(jì)算，對(duì)邊采樣10個(gè)點(diǎn)，若通過(guò)初步粗檢測(cè)，后面再深入計(jì)算。這些算法都不太高效。
第三個(gè)輔助函數(shù)是IsIntersection()用來(lái)判斷兩邊條在參數(shù)范圍內(nèi)是否相交。
3 測(cè)試
將兩條邊求交過(guò)程中的包圍盒顯示出來(lái)，方便查看理解算法。先測(cè)試兩個(gè)圓之間的相交：
其中第一條邊是綠色的圓，求交過(guò)程中的包圍盒也用綠色表示；第二條邊是紅色的圓，求交過(guò)程中的包圍盒也用紅色表示。因?yàn)閳A是閉合的，第一次都分割成2部分。將上面交點(diǎn)處理放大：
后面都是將第一條邊分割成3部分，然后分別用這3部分的包圍盒去找與第二條邊相交的參數(shù)范圍，再更新第二條邊的包圍盒。繼續(xù)放大上面交點(diǎn)處：
發(fā)現(xiàn)對(duì)于兩個(gè)圓的求交，執(zhí)行了100次，效率不高。又用兩個(gè)B樣條曲線求交來(lái)測(cè)試：
發(fā)現(xiàn)對(duì)于B樣條曲線求交速度較快。
4 Conclusion
曲線求交需要考慮重合部分，opencascae中沒(méi)有使用數(shù)值算法來(lái)計(jì)算，而是采用基于包圍盒的算法來(lái)處理。這種算法一般情況下可以快速找到求交解，有時(shí)遞歸較深，對(duì)于基本曲線可以像曲面求交一樣分類處理以提高性能。opencascade中對(duì)于三維曲線求交算法性能還有優(yōu)化空間。