论文部分内容阅读
曲面求交(SSI)是CAGD中的一个重要课题。到目前为止,提出的求交算法大致有六种,即:几何分割法、代数迭代法、跟踪法、网格法、解析法和三角法;但任何一种方法都没有解决好求交问题中速度与精度的有效统一,因为有的算法侧重于通用性,有的却只注重精度问题。由于相交曲面及交线本身的复杂性,同时实用中对交线的精度要求愈加严格,进一步加大了求交的难度。 尽管如此,对求交问题加以折衷处理还是可行的。目前,跟踪求交法就是一种人们普遍认为最有效的求交方法。这种算法包括搜索、跟踪、排序三个主要步骤,具有算法稳定、精度高等优点。只是求交速度一般,有待于进一步解决。 本文首先较为详细地分析和比较了几种常用的曲面求交算法及其存在的问题,并提出了一些解决措施,然后在此基础上扬长避短,提出并实现了一种稳定性好、精度高、速度快的曲面求交算法。主要做了以下几方面的工作: 1.在理论上,系统地分析了交线的几何特征(如切平面和法平面等)和微分特征(如曲面的一阶基本齐式等),建立了交线的微分系统跟踪模型,从而为今后进一步研究求交问题提供了一个可行的途径。同时给出了相应的较为合理的处理方法,如辅助平面法和自适应调整步长法等。 2.在算法上,提出了一种较为通用的单极值曲面求交方法——二分跟踪法,该法综合了以往各种算法的优点,并且结合工程实践,对各项关键性技术(如包围盒技术、精度控制技术)加以改进,使得数据精度与时间复杂度(即速度)的冲突得到了妥善处理,从而使算法稳定性更强、精度更高、速度更快。 3.在算法的具体求解过程中,采用了一种高效的方法:5阶卡什-卡普法估计内嵌4阶龙格——库塔法的局部误差。 4.在算法的实现和程序的编制上,全面采用了面向对象的技术,以WindowsNT Workstation为工作平台,以Visual C++和OpenGL为开发工具,设计出了一系列配套处理程序,形成了一个实用的曲面求交软件模块,在我们自行开发的曲面造型系统中取得了良好的效果。 5.为了进一步验证二分跟踪法的有效性,研究并实现了曲面裁剪、曲面剪切、曲面过渡等曲面造型功能,获得了良好的效果。 6.对曲面求交的难点——多极值曲面求交,进行了尝试性分析和展望,对曲面求交问题的进一步研究也作了一些探讨。