TOPOLOGICAL SHAPE MODELS (GEOMETRIC MODELING).

摘要

Many new geometric and topological representations of shapes are being developed. Work in this area is motivated because of the need to provide computational models as a basis for computer systems that can manipulate spatial information. Topological representations are particularly important because (i) they can be used with a variety of different geometric primitives, and (ii) they correspond to the more intuitive, higher-level properties of shapes.;This thesis concentrates on the topological properties of two- and three-dimensional subdivisions of space. Subdivisions are characterized as simplicial complexes that are combinatorial manifolds. Two important pieces of information are needed to represent these subdivisions: adjacency and relative ordering. A relational model for storing this information is presented which is useful for accessing the information stored in a topological database. The mathematical properties of manifolds are used to develop various properties of a well-formed subdivision. These include valency restrictions on the number of adjacent elements, and generalizations of Euler operators for constructing subdivisions. A 2-d data structure, the half-edge, and a new 3-d data structure, the face-edge are analyzed. These data structures have two important properties: they occupy minimal space and all elemental adjacencies can be determined in time proportional to the number of neighboring elements. Finally, two applications of these principles are discussed. First, converting a line-drawing to a solid model, and second, testing for topological equivalence.