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

Abstract: To solve the problem of inefficiency and poor stability in computing intersection between subdivision surfaces,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 utilizing 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 topological structure of subdivision surface patch,the first point of intersection curve was solved,and the rules of intersection grid edge and intersection grid plane selection were established.An intersection curve was obtained by sequentially 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.

Key words: subdivision surface intersection, divide and conquer strategy, multi-segmentation, data structure