一种改进的基于微分方程的曲面求交跟踪算法  

An Improved Algorithm for Tracing Surface Intersection Based on Differential Equation

作　　者：史永丰 程婷 张育浩 徐保文 林岗山 SHI Yong-feng;CHENG Ting;ZHANG Yu-hao;XU Bao-wen;LIN Gang-shan(Jinhang Digital Technology co. LTD,Beijing 100028,China)

机构地区：[1]金航数码科技有限责任公司,北京100028

出　　处：《图学学报》2019年第2期290-295,共6页Journal of Graphics

摘　　要：参数曲面求交是计算机辅助几何设计领域中的关键技术之一。针对传统跟踪算法中曲面求交的漏交和法向共线点处难于处理的问题,提出一种改进的基于微分方程的跟踪算法。首先选择边界点和拐点作为跟踪的起点,解决了漏交问题。并采用基于交线微分形式的跟踪公式计算后继交点,解决了法向共线点处难于处理的问题。最后利用牛顿迭代得到精确交点。该算法不仅正确地跟踪到交线的每个分支,而且易于处理法向共线点处的跟踪,不遗漏关键点,解决了传统跟踪法在法向共线点处交线不连续的问题。与传统跟踪法对比,其鲁棒性和稳定性更强,精度更高且收敛略快,适用于求解任意参数曲面求交问题。Intersection of parametric surfaces is one of the key technologies in the field of computer aided geometric design(CAGD).In this paper,an improved tracing algorithm based on differential equation is proposed to solve the problem in traditional tracing algorithm of missing intersection line and difficulty to trace at normal collinear points.Firstly,the algorithm chooses the boundary points and the inflection points as the starting points of the tracing,so it solves the problem of missing intersection line.Then the tracing formula based on the differential form is used to calculate the successor intersection,which solves the problem of processing tracing at normal collinear points.Finally,the Newton iteration is used to get the exact intersection.The algorithm not only correctly traces each branch of the intersection line,but also is easy to deal with the tracing at normal collinear points.Without missing the key points,the algorithm solves the problem that the traditional tracing method is not continuous at the normal collinear points.Compared with the traditional tracing method,its robustness and stability are stronger characterized with higher precision and slightly faster convergence,and it is suitable for solving any parametric surface intersection problem.

关 键 词：曲面求交 跟踪法 微分方程 法向共线点 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]