关键词: 平面与细分曲面求交, 数据结构, 分治, 多级分割, Catmull-Clark细分曲面

Abstract: To solve the problems of inefficiency and poor stability in computing intersection curve between plane and subdivision surface,an high efficient method for plane and Catmull-Clark subdivision surface intersection was presented according to mesh topological characteristics of subdivision surface.Based on piecewise representation of subdivision surface,the problem of computing intersection curve between plane and complex subdivision surface was transformed into the problem of computing intersection curve between plane and subdivision surface patch.From analysis of intersection points between plane and subdivision surface patch,the intersection points were divided into three basic types:initial intersection point,following intersection point and terminal intersection point.The multi-segmentation technology for subdivision surface patch was presented on the basis of topological characteristics of subdivision surface patch.By applying multi-segmentation in combination with the bounding box interference detecting technique,subdivision surface patches non-intersecting the plane was determined and the initial intersection point could be obtained.According to the topological relationship between subdivision surface patches,all the unordered curve segments were merged orderly together into an intersection curve.The high performance of proposed algorithm was verified through the practical cases.

Key words: plane/subdivision surface intersection, data structure, divide and conquer, multi-segmentation, Catmull-Clark subdivision surface