快速计算高精度细分曲面之间交线的方法  

Efficient algorithm for computing intersection curve between subdivision surfaces

作　　者：曹斌[1] 王敏杰[1] 朱建宁[1] 

机构地区：[1]大连理工大学机械工程学院,辽宁大连116024

出　　处：《计算机集成制造系统》2014年第9期2079-2085,共7页Computer Integrated Manufacturing Systems

摘　　要：为解决细分曲面求交效率低、稳定性不足的问题,基于分治策略提出一种更加高效、稳定的CatmullClark细分曲面求交算法。采用新型数据结构实现细分曲面的分片表示,将细分曲面的求交问题转化为若干细分曲面面片的求交问题。对细分曲面面片进行多级分裂,并结合包围盒干涉检测技术获取相交网格集。利用细分曲面面片拓扑结构特性求解交线的首交点,同时建立相交网格边和相交网格面的选取规则,按序计算后续交点,得到细分曲面面片的交线。求出所有相交细分曲面面片间的交线后,再利用细分曲面面片间的拓扑关系合并细分曲面交线段。通过实例对算法进行了测试,结果表明,该算法在细分曲面形状复杂、细分次数较高的情况下能够实现高效、稳定的求交运算。To solve the problem of inefficiency and poor stability in computing intersection between subdivision sur- faces, an efficient and stable Catmull-Clark subdivision surface method was presented based on divide-and-conquer strategy. The subdivision surface intersection was simplified to several subdivision surface patch intersection by uti- lizing a new data structure to realize piecewise representation. Based on subdivision surface patch multi-segmentation technology and bounding box collision detection technology, intersection grid set could be obtained. By using the to- pological structure of subdivision surface patch, the first point of intersection curve was solved, and the rules of in- tersection grid edge and intersection grid plane selection were established. An intersection curve was obtained by se- quentially calculating subsequent intersection points. The intersection curves between all facets were computed, and subdivision surface intersection curves segments were combined by using topological structure of subdivision surface patch. The examples testing result showed that the algorithm could realize efficient and stable intersection operation with complex shape and high subdivision frequency of subdivision surfaces.

关 键 词：细分曲面求交 分治策略 多级分裂 数据结构 

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