Subdivision Software System Design And Implementation

Subdivision surface is a new geometric modeling technology of discrete surface based on mesh. It can express modeling surface through control mesh and subdivision rules. This technology not only preserves the properties of localness and affine-invariance of B-spline surface, but also has some special advantages such as adaptability to arbitrary topology which parameter surfaces don't have. These good qualities makes subdivision surface used widely in recent years. In this thesis, basic subdivision schemes and its adaptive schemes in CAD, together with the algorithm which is about triangle mesh model fitting Loop subdivision surface, are studied in depth. Then a software system based on subdivision surface is developed, and these algorithms are integrated in it. The main work is as follows:(1) Subdivision theories and typical subdivision schemes are analyzed. The approach to exactly calculate geometric parameters of subdivision surface, such as limiting point, tangent vector and normal vector, are illustrated.(2) The number of geometric elements (vertex, edge, facet) within control mesh grows exponentially as the increase of subdivision levels in general subdivision schemes. This results in enormous and redundant data. Two adaptive subdivision schemes, which can satisfy engineering requirements, are proposed in this thesis. One is based on shape precision control, another on surface fairness criterion. Both of them decrease the size of control mesh evidently, and meanwhile the quality of subdivision surface is guaranteed. All these save lots of time and space for successive storage, transmission and modification.(3) Model reconstruction is a key step in reverse engineering. The acquisition of control mesh for Loop subdivision surface from general triangle mesh is researched, and an algorithm is proposed to fulfill the reconstruction of subdivision surface from arbitrary dense mesh in topology.(4) An improved winged-edge data structure suitable for subdivision is developed. Some typical schemes are implemented via this data structure (Loop subdivision, Catmull-Clark subdivision, Do-Sabin subdivision, hybrid subdivision, adaptive subdivision). The technique of OpenGL is utilized to accomplish some basic operations, such as rotation, zoom, pan, pick and so on. Finally the algorithms studied by our research group are integrated, and a prototype system based on subdivision surface is developed.