Two analytical 2d line intersection in OpenCASCADE Abstract. OpenCASCADE geometric tools provide algorithms to calculate the intersectio

Size: px

Start display at page:

Download "Two analytical 2d line intersection in OpenCASCADE Abstract. OpenCASCADE geometric tools provide algorithms to calculate the intersectio"

窗钻昝
5 years ago
Views:

1 Two analytical d line intersection in OpenCASCADE eryar@63.com Abstract. OpenCASCADE geometric tools provide algorithms to calculate the intersection of two d curves, surfaces, or a 3d curve and a surface. Those are the basis of the Boolean Operation, so under the implementation can help to under the BO algorithms. The paper focus on the intersection of two d analytical line. Key Words. OpenCASCADE, Line Intersection.Introduction 在几何造型系统中, 通常利用集合的并交差运算实现复杂形体的构造, 而集合运算需要大量的求交运算如何提高求交的实用性稳定性速度和精度等, 对几何造型系统至关重要当前的几何造型系统, 大多数采用边界表示法来表示模型在这种表示法中, 形体的边界元素和某类几何元素相对应, 它们可以是直线圆弧二次曲线 Bezier 曲线和 B 样条曲线等, 也可以是平面球面二次曲面 Bezier 曲面和 B 样条曲面等, 求交情况十分复杂在一个典型的几何造型系统中, 用到的几何元素通常有 5 种, 为了建立一个通用的求交函数库, 所要完成的求交函数多达 : C 在 OpenCASCADE 中也有类似的数据结构来表示几何体本文先来学习最简单的一种求交 : 两条二维直线的相交 Figure. d line intersection.code Usage OpenCASCADE 中计算二维解析曲线的类是 IntAnad_AnaIntersection, 可用于计算如下的曲线之间的相交 : 两条二维直线 ; 两个二维圆 ; 二维直线和二维圆 ; 二维直线圆椭圆抛物线双曲线二次曲线与另外一条二维曲线 ;

2 下面使用 OpenCASCADE 来对图所示的两条二维直线进行求交计算代码如下 : /* Copyright(C) 07 Shing Liu(eryar@63.com) Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files(the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and / or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions : The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ // NOTE // ---- // Tool: Visual Studio 03 & OpenCASCADE7..0 // Date: :5 #include <gp_dird.hxx> #include <gp_lind.hxx> #include <gp_pntd.hxx> #include <GCEd_MakeLine.hxx> #include <IntAnad_AnaIntersection.hxx> #pragma comment(lib, "TKernel.lib") #pragma comment(lib, "TKMath.lib") #pragma comment(lib, "TKGd.lib") #pragma comment(lib, "TKG3d.lib") #pragma comment(lib, "TKGeomBase.lib") void test(void) GCEd_MakeLine alinemaker(gp_pntd(0.0, 0.0), gp_pntd(0.0, 0.0)); GCEd_MakeLine alinemaker(gp_pntd(.0, 0.0), gp_pntd(.0,.0)); gp_lind aline = alinemaker.value()->lind(); gp_lind aline = alinemaker.value()->lind(); IntAnad_AnaIntersection aintana;

3 aintana.perform(aline, aline); if (aintana.isdone()) const IntAnad_IntPoint& aintpoint = aintana.point(); std::cout << "Number of IntPoint between the curves: " << aintana.nbpoints() << std::endl; std::cout << "Intersect Point: " << aintpoint.value().x() << ", " << aintpoint.value().y() << std::endl; int main(int argc, char* argv[]) test(); return 0; 计算得到交点为 (6.44, 6.44): Number of IntPoint between the curves: Intersect Point: , Press any key to continue... 3.Code Analysis 计算二维直线相交的代码在文件 IntAnad_AnaIntersection_.cxx 中, 其中名字 IntAnad 的意思是 Intersection Analytical 两个单词前三个字母, 即二维解析曲线求交包源码列出如下 : void IntAnad_AnaIntersection::Perform (const gp_lind& L, const gp_lind& L) done = Standard_False; Standard_Real A,B,C; Standard_Real A,B,C; L.Coefficients(A,B,C); L.Coefficients(A,B,C); Standard_Real al,be,ga; Standard_Real al,be,ga; Standard_Real Det =Max (Abs(A),Max(Abs(A),Max(Abs(B),Abs(B)))); if (Abs(A)==Det) al=a; be=b; ga=c; al=a; be=b; ga=c; else if (Abs(B)==Det)

4 al=b; be=a; ga=c; al=b; be=a; ga=c; else if (Abs(A)==Det) al=a; be=b; ga=c; al=a; be=b; ga=c; else al=b; be=a; ga=c; al=b; be=a; ga=c; Standard_Real rap=al/al; Standard_Real denom=be-rap*be; if (Abs(denom)<=RealEpsilon()) // Directions confondues para=standard_true; nbp=0; if (Abs(ga-rap*ga)<=RealEpsilon()) // Droites confondues iden=standard_true; empt=standard_false; else // Droites paralleles iden=standard_false; empt=standard_true; else para=standard_false; iden=standard_false; empt=standard_false; nbp=; Standard_Real XS = (be*ga/al-be*ga/al)/denom; Standard_Real YS = (rap*ga-ga)/denom; if (((Abs(A)!=Det)&&(Abs(B)==Det)) ((Abs(A)!=Det)&&(Abs(B)!=Det)&&(Abs(A)!=Det))) Standard_Real temp=xs; XS=YS; YS=temp;

5 Standard_Real La,Mu; if (Abs(A)>=Abs(B)) La=(YS-L.Location().Y())/A; else La=(L.Location().X()-XS)/B; if (Abs(A)>=Abs(B)) Mu=(YS-L.Location().Y())/A; else Mu=(L.Location().X()-XS)/B; lpnt[0].setvalue(xs,ys,la,mu); done=standard_true; 从上述源码中可以看出,OpenCASCADE 对二维直线求交计算使用的是解方程组的方法步骤如下 : 计算两条直线的系数 ; 计算系数方程组这些都是高中数学知识了, 就当复习下, 并由此看出 OpenCASCADE 中的一些编码风格先看第一步, 根据点和方向计算二维直线的系数, 相关的源码如下所示 : inline void gp_lind::coefficients (Standard_Real& A, Standard_Real& B, Standard_Real& C) const A = pos.direction().y(); B = - pos.direction().x(); C = -(A * pos.location().x() + B * pos.location().y()); 由高中数学可知, 二维直线的方程有三种形式 : 点斜式两点式和一般式 y y y - y y - y k( x x ) Ax By C 0 x x x x 点斜式两点式一般式根据一般式方程, 当 B 不等于 0 时, 可得 : A C y x B B 因为 OpenCASCADE 中的 gp_dird 是单位向量, 所以可将其 X Y 值分别对应 -B 和 A 确定 A 和 B 后, 再根据一般式方程将 C 移项得到 :C=-Ax-By 得到直线的系数后, 交点的计算就变成如下方程组的求解了 : A x B y C 0 BC x A x B y C 0 A B BC A B, y AC A B A C A B

6 OpenCASCADE 的源码中有多个条件判断, 相当于高期消元法中的选主元操作, 主要是为了避免分母为 0 的情况其中有两个实数直接判断相等的语句, 如 Abs(A)==Det 这种对于实数大小的比较, 一般总是使用两者相减的值是否落在 0 的领域中来判断 OpenCASCADE 中对于实数的比较没有采用领域比较技术, 显得不够严谨其实领域比较的方法已经在 Precison.hxx 中进行了说明, 只是有些代码没有严格执行 4.Conclusion 通过对 OpenCASCADE 中二维直线相交代码的分析, 理解其实现原理 : 将点向式的直线转换成一般式, 再对一般式联立方程求解求解过程中使用了高期消元法的选主元方法对于实数的比较应该尽量采用领域比较技术, 而避免直接使用两个数相等 == 或不相等!= 的判断如果只是判断两条直线是否相交, 而不用计算交点的话, 算法导论中有使用向量来高效算法因为二维直线相交只涉及到高中数学知识, 所以本文是抛砖引玉, 通过继续学习, 理解 B 样条曲线的相交算法实现 5.References. 孙家广, 胡事民. 计算机图形学基础. 清华大学出版社人民教育出版社中学数学室. 数学第二册上. 人民教育出版社钱能. C++ 程序设计教程. 清华大学出版社易大义, 沈云宝, 李有法. 计算方法. 浙江大学出版社潘金贵等译. 算法导论. 机械工业出版社. 0