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

in the face list for each face of the polytope. From this half-edge, the face
can be traversed by referring to the previous and next pointers in the edge
list [9, 169].
The start vertex v s (i s ,j s ,k s ) of P G (A) is obtained from p 0 (i 0 ,j 0 ,k 0 ), the
top-left-front point of A. The point p 0 is the top-left-front point of A if and
only if for each other point (i,j,k) ∈ A, k 6 k 0 and j 6 j 0 and i > i 0 . Then
it can be shown that

i s = (⌈i 0 /g⌉−1)×g, j s = (⌊j 0 /g⌋+ 1)×g, k s = (⌊k 0 /g⌋+ 1)×g. (7.1)

A UGC-face f k is a part of the outer cover if and only if exactly one of
its two adjacent UGCs has object containment. Hence, it can be shown that
if p is a point lying on P G (A), then 0 6 d ⊤ (p,A) < g. Using this property,
we can construct the set of UGC-faces comprising the surface of P G (A). In
order to organize these UGC-faces as a set of isothetic polygons, the DCEL
is constructed. For each face in face list F, we maintain its id, the id of its
incident edge, and the corresponding coordinate plane to which it is parallel.
The edge information in edge list E includes the edge id, the face on which
it is incident, its source vertex, ids of its next and previous edges, and its
paired half-edge. Vertex information in vertex list V consists of the vertex id
corresponding to each vertex.
The start vertex v s is shared by three UGC-faces, parallel to the yz-, zx-,
and xy-planes. Out of these, the one parallel to the xy-plane, i.e., the front
face is enqueued in a queue Q assigning it a unique id. The UGC-faces are
traversed by BFS [49] whereby a face f i is dequeued from Q and each face
f k incident on the edges e ij ∈ f i is checked for eligibility. The vertices of
f i are enlisted in V , avoiding repetition. Consequently, the source vertex of
e ij

∈ f i , and its next and previous edges are recorded in E, and f i is inserted
in F along with e ij as its starting edge and the plane to which f i is parallel.
If f k is an eligible face, it is assigned a unique id and enqueued in Q if it
has not already been enqueued. Otherwise, if f k is coplanar with f i and has
been previously enqueued and dequeued, then f k can be merged with f i by
deleting their common edge e ij . Hence, pair[e ij ] in E is set to the id of the
edge e ij ∈ f k whose start and end vertices are the respective end and start

vertices of e ij . Once dequeued, f i is not suitable to be enqueued again, and
another face is dequeued from Q. The procedure continues until Q is empty.
While merging the UGC-faces, their co-planarity and adjacency are tested
through half-edge information in the edge list E. The basic steps include dele-
tion (from E) of (half-)edges shared by two coplanar-adjacent faces, updating
face information in F, and readjusting the pointers of the edges associated
with the merged faces. A brief outline of the algorithm to find the 3-D iso-
thetic cover of an object A embedded in grid G is given in ISO-COVER-3D
(Algorithm 15).