Subdivisions of Surfaces and Generalized Maps

Abstract

The modeling of subdivisions of surfaces is of greatest interest in Geometric Modeling (in particular for Boundary Representation) , and many works deal with the definition of models, which enable the representation of closed, orientable subdivisions of surfaces, and with the definition of elementary operations, which can be applied to these models (Euler operators) . We study in this paper the notion of 2-dimensional generalized map (or 2-G-map), which make possible the definition of the topology of any subdivision of surface, orientable or not orientable, opened or closed ; reciprocally, the topology of any subdivision of any surface may be defined by a 2-G-map . Three characteristics are associated to any 2-G-map G (the most elementary being the number of boundaries, the most known being the genus ...), and can be directly computed on G . These characteristics define the subdivision of surface modelled by G (static classification of the subdivision) . We define also operations which can be applied to 2-G-maps . Any 2-G-map (and then any subdivision of surface) can be constructed by a sequence of operations . To these operations correspond variations of the characteristics associated to the 2-G-maps . These variations enable the control of the effect of an operation on the modelled subdivision (dynamic classification of the subdivision) . The notion of 2-G-map defines the different elements of a subdivision (vertex, edge, face, bound ary...) by using one unique kind of elements, in a rigorous and unambiguous manner. Data structures may be deduced from the notion of 2-G-map . These data structures make possible the representation of any subdivision of surface , in a way near to the well-known "windged-edge" data structure defined by B. Baumgart in [BA75] . The constraints of consistency about these data structures can be directly deduced from the definition of 2-G-maps . The set of the properties of 2-G-maps (rigour, consistency, possibility of static or dynamic classification) makes the greatest interest of the 2-G-maps, with respect to other models of subdivisions of surfaces used in Geometric Modeling .