Geometric Modeling is central to many CAD systems, even though the models traditionally employed do not satisfy all applications. Scientific applications need to deal with objects made of different materials, with distinct properties. Contact relationships are crucial in kinematics, assembly planning, robotic, and geology. In this context, it is necessary to model aggregates of objects (including solids with lower dimensional parts), keeping track of the adjacency relationships among these objects. This suggests the creation of a development environment where the applications can share not only data but also algorithms that process and transform these data. The way to handle such problems is by supporting arbitrary space subdivisions, instead of the classical subdivision in three regions (interior, boundary, and exterior of a solid object).
Planar subdivisions are simpler, but also important, mainly in geology and cartography. The creation of a planar subdivision differs from the creation of a spatial subdivision, specially by the interaction with the user (by the modeling process). The aim of this work is to deal with the problem of creating, combining, and maintaining, in real time, subdivisions of the two- and three-dimensional Euclidean space. The main goal is devising a methodology that permits the construction of subdivisions which are topologically and geometrically consistent. This methodology is determined by a modeling process, a mathematical model, and a representation scheme. To achieve this, some extensions were added to the concept of selective geometric complex, creating the basis for a flexible scheme that eliminates several restrictions imposed by traditional modeling.
The proposed representation scheme maintains an explicit boundary representation and allows one to add boolean operations without any additional restriction (furthermore, it enables the implementation of efficient geometrical algorithms). This provides a powerful set of modeling tools that can be used as the base for the creation of an interactive construction language for space subdivisions. The construction of basic operations which allow the insertion of a surface patch or a curve segment in a given subdivision in linear time, is also described in detail. This means that a complete subdivision can be built in quadratic time with the number of subdivision's elements.