OpenCASCADE 曲線(xiàn)求交

eryar@163.com

1 Introduction

OpenCASCADE中提供了二維幾何曲線(xiàn)的求交類(lèi)Geom2dAPI_InterCurveCurve，對(duì)應(yīng)到三維幾何只提供了GeomAPI_IntCS, GeomAPI_IntSS，沒(méi)有提供幾何的GeomAPI_IntCC求交類(lèi)。這些幾何求交一般使用的是數(shù)值算法，即解方程。對(duì)于兩條幾何曲線(xiàn)P(u1), Q(u2)，求交就是解P(u1) - Q(u2) = 0這個(gè)方程。為什么對(duì)于三維幾何曲線(xiàn)沒(méi)有提供數(shù)值算法？

對(duì)于拓樸邊提供了求交算法IntTools_EdgeEdge，這個(gè)類(lèi)是使用類(lèi)似于曲面求交的離散網(wǎng)格法，使用了離散包圍盒法。

基于包圍合盒的算法是個(gè)遞歸算法，算法思路：

1. 1) 檢查兩條邊在參數(shù)范圍內(nèi)的包圍盒，若空間干涉，則進(jìn)行下一步；否則退出本次判斷；
2. 2) 找出兩條邊包圍盒的公共部分對(duì)應(yīng)的參數(shù)，若沒(méi)找到，則退出本次判斷；
3. 3) 并將第一條邊在參數(shù)范圍內(nèi)分割成2或3部分，執(zhí)行第一步；
4. 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樣條曲線(xiàn)求交來(lái)測(cè)試：

發(fā)現(xiàn)對(duì)于B樣條曲線(xiàn)求交速度較快。

4 Conclusion

曲線(xiàn)求交需要考慮重合部分，opencascae中沒(méi)有使用數(shù)值算法來(lái)計(jì)算，而是采用基于包圍盒的算法來(lái)處理。這種算法一般情況下可以快速找到求交解，有時(shí)遞歸較深，對(duì)于基本曲線(xiàn)可以像曲面求交一樣分類(lèi)處理以提高性能。opencascade中對(duì)于三維曲線(xiàn)求交算法性能還有優(yōu)化空間。