Modeling of a Voxelated Surface - Digital Geometry in Image Processing - page 230

FIGURE 7.5: An object A in Z 3 (left) and its outer isothetic cover for g = 2
(right). (See color insert.)
7.1.1 3-D Isothetic Covers
Given a grid G and a 3-D digital object A, we can approximate A by its 3-
D isothetic cover, which is defined as the minimum-volume isothetic polytope
P G (A) that contains A (Fig. 7.5). Mathematically, the following conditions
are satisfied:
• A⊆ P G (A)
• for each p ∈ P G (A), 0 6 d ⊤ (p,A) < g
Here, g denotes the grid size, and P G (A) denotes the entire cover including
its surface P G (A) and interior region. The first condition implies that each
point of A lies on or inside P G (A), and the second condition addresses the
minimum volume of P G (A). Also note that an isothetic polytope is a polytope
with all its vertices as grid vertices, all its edges made of grid edges, and all
its faces lying on face planes. Each face of an isothetic polytope is an isothetic
polygon whose alternate edges are isothetic and constituted by the grid edges
of G.
The algorithm to construct the outer isothetic cover P G (A) of A is given
in detail in [105]. From a well-defined start vertex, eligible UGC-faces are
determined by BFS (breadth first search) [49], which are stored in a doubly
connected edge list (DCEL) [9]. The eligible UGC-faces, which are coplanar
and contiguous, are later merged into isothetic polygons of maximal size, par-
allel to the yz-, zx-, and xy-planes, which together constitute the isothetic
cover. The DCEL stores topological information in the form of a vertex list,
edge list, and face list. Each vertex of the polytope is stored only once in the
vertex list. The edge list is maintained as sets of four half-edges per face of
UGC. Each half-edge is represented by its source vertex, and four consecutive
half-edges are assigned the face number that denotes the face to which the
edges belong. The edge list also records the pairing of all half-edges. The id (a
unique number) of a half-edge, considered as the first half-edge corresponding
to a face, and the plane (yz, zx, or xy) to which the face is parallel, is stored