Geoscience Reference
In-Depth Information
2 Background
2.1 Boundary Representation
Boundary representation (abbreviated as ''B-rep'') is a method in solid modeling
for representing solids and shapes using their boundaries (which separate the
interior of the solid from the exterior of the solid). These solid boundaries are
obtained by ''sewing'' together connected surface elements (or patches), whose
boundaries are composed of vertices and edges. Typically, the surface elements are
B-splines (which are linear combinations of the parametric polynomial Bézier
curves) or their generalizations (NURBS). A UML description of the Boundary
representation is shown in Fig.
2
.
2.2 Cell Complex
A cell complex is a decomposition of the space into cells, where the interior of each
cell can be obtained by continuously deforming a hyper-ball without its boundary
and vice versa, the boundary of each cell is the union of lower-dimensional cells of
the cell complex, and the topology of objects in the cell complex is defined from
their intersections with all cells
4
. It can model one subdivision of the space. The
topological relationships among the cells of the cell complex may be modeled using
a second subdivision.
2.3 Quad-Edge Data Structure
The Quad-Edge data structure was introduced by Guibas and Stolfi Guibas and Stolfi
(
1985
) as a primitive topological structure for the representation of any subdivision
on a two-dimensional manifold (see p. 18 in [49]). The Quad-Edge data structure is
the implementation of an edge algebra Guibas and Stolfi (
1985
) as shown in Fig.
3
),
which is the mathematical structure that defines the topology of any pair of dual
subdivisions on a two-dimensional manifold Guibas and Stolfi (
1985
).
In three dimensions, dual subdivisions also permit us to understand the
geometry of objects (primal subdivision) and how different solids are spatially
related (dual subdivision, e.g. two rooms in a building are adjacent) as shown in
Fig.
4
. Arguably the most known use of the dual, which stores the topological
relationships among 3D objects is to model navigational paths inside three-
4
A subset of a cell complex is closed if, and only if, the complement of its intersection with the
union of each cell and its boundary is a neighborhood.
