Geoscience Reference
In-Depth Information
(a)
(b)
(d)
(c)
Fig. 4
Duality in a 3D cell complex
dimensional buildings. However, there are other usages of the dual in spatial
analysis for example finding the neighboring objects or buildings from any given
object or analyzing the propagation of fire, floods, etc.
2.4 The Dual Half-Edge Data Structure
The Dual Half-Edge (DHE) structure, as proposed by Boguslawski et al.
(Boguslawski et al.
2011
; Boguslawski
2011
), is a data structure that is able to
represent a set of connected polyhedra forming a cell complex using a boundary
representation (or B-rep). It does so by simultaneously storing both the primal and
the dual graphs of the objects, in a similar manner as the Quad-Edge structure of
Guibas and Stolfi (
1985
) in 2D.
As shown in Fig.
5
a, with the DHE each polyhedron is represented indepen-
dently with an edge-based structure (a B-rep model), and adjacent polyhedra are
linked together by their shared faces, which are represented by Half-Edges joining
3-cells. These form a graph of connections in the dual of the original (primal)
graph. Both the primal and the dual graphs are identical in terms of structure (i.e.
their basic elements and connections). Figure
5
b shows an idea of the relationships
that are stored for each edge.
Since these graphs conform to Pointcaré's duality concept, the only cells that
are needed to build a 3D model are the 0-cells (nodes) and 1-cells (edges); the
nodes store the vertex coordinates, while the edges store the connections between
the nodes. Meanwhile, the 2-cells (faces) and 3-cells (volumes) are only implicitly
represented, but their attributes can be stored in their dual counterparts, the 1-cells
and 0-cells in the dual graph.
However, an edge is not an atomic element in the DHE. Each edge consists of
two Half-Edges, each of them being permanently connected with its corresponding
Half-Edge in the dual. This pair, Half-Edge in the primal graph and Half-Edge in
the dual one, is called the dual Half-Edge, and forms the atomic element in this
model. Each Half-Edge is represented with five pointers which keep references to:
an associated vertex (V in Fig.
5
), the next edge around a shared vertex (N
V
in
Fig.
5
), the next edge around a shared face (N
F
in Fig.
5
), the second Half-Edge of
the edge (S in Fig.
5
), and to the dual Half-Edge (D in Fig.
5
).
