i
i
i
i
i
i
i
i
16.3. Space Partitioning 395
with post-processing for mesh refinement (see Chapter 12) and caching provide a
method for interactive viewing of implicit models on modern workstations.
16.3 Space Partitioning
16.3.1 Exhaustive Search
The basic cubic space partitioning algorithm for tiling implicit surfaces was first
published in (Wyvill et al., 1986) and a similar algorithm oriented towards volume
visualization, called marching cubes in (W. Lorensen & Cline, 1987). Since then
there have been many refinements and extensions.
A first approach to finding the implicit surface might be to subdivide space
uniformly into a regular lattice of cubic cells and calculate a value for every ver-
tex. Each cell is replaced with a set of polygons that best approximates the part
of the surface contained within that cell. The problem with this method is that
many of the cells will be completely outside or completely inside the volume;
thus, many cells that contain no part of the surface are processed. For large grids
of data this can be very time consuming and memory intensive.
To avoid storing the whole grid, a hash table is used to store only the cubes
that contain a piece of the surface, based on the data structures used in (Wyvill et
al., 1986). Working software was published in Graphics Gems IV (Bloomenthal,
1990). The algorithm is based on numerical continuation; it starts with a seed
cube that intersects part of the surface and builds neighboring cubes as necessary
to follow the surface.
The algorithm has two parts. In the first part, cubic cells are found that contain
the surface and in the second part, each cube is replaced by triangles. The first
part of the algorithm is driven by a queue of cubes, each of which contains part of
the surface; the second part of the algorithm is table-driven.
16.3.2 Algorithm Description
A fast overview of the algorithm is as follows:
• divide space into cubic voxels;
• search for surface, starting from a skeletal element;
• add voxel to queue, mark it visited;
• search neighbors;
• when done, replace voxel with polygons.
i
i
i
i
i
i
i
i
396 16. Implicit Modeling
First, space is subdivided into a cubic lattice, and the next task is to find a seed
cube containing part of the surface. A cube vertex v
i
inside the surface will have
a field value v
i
>=isoand a vertex outside the surface will have a field value
v
i
< iso; thus, an edge with one of each type of vertex will intersect the surface.
We call this an intersecting edge. The field value at the nearest cube vertex to the
first primitive can be evaluated by summing the contributions of the primitives
as per Equation (16.3), although other operators can also be used as will be seen
later. We will assume that f(v
0
) > iso, which indicates that v
0
lies within the
solid. The value of iso is chosen by the user; an example is iso = 0.5 when using
the soft fall-off function, which has some symmetry properties that lead to nice
blending (see Figure 16.3). The vertices along one axis are evaluated in turn until
avaluev
i
< iso is found. The cube containing the intersecting edge is the seed
cube.
The neighbors of the seed cube are examined, and those that contain at least
one intersecting edge are added to the queue ready for processing. To process a
cube we examine each face. If any of the bounding edges have oppositely signed
Surface Skeleton
Voxel
-
+
Figure 16.10. A section through the cubic lattice. The + sign indicates a vertex inside the
surface (
f
(
v
i
≥ iso) and - is outside
f
(
v
i
< iso).
i
i
i
i
i
i
i
i
16.3. Space Partitioning 397
vertices, the surface will pass through that face and the face neighbor must be
processed. When this process has been completed for all the faces, the second
phase of the algorithm is applied to the cube. If the surface is closed, eventually
a cube will be re-visited and no more unmarked neighbors found, and the search
algorithm will terminate. Processing a cube involves marking it as processed
and processing its unmarked neighbors. Those that contain intersecting edges are
processed until the entire surface has been covered (see Figure 16.10).
Each cube is indexed by an identifying vertex which we define to be the lower-
left far corner (i.e., the vertex with the lowest (x, y, z)-coordinate values (see Fig-
ure 16.11)). For each vertex that is inside the surface, the corresponding bit will
be set to form the address in an 8-bit table (see Figure 16.11 and Section 16.3.3).
The identifying vertex is addressed by integers i, j, k, computed from the
(x, y, z)-coordinate location of the cube such that x =side∗i,etc.,whereside is
the size of the cube. The identifying vertex of each cube may appear in as many
as eight other cubes, and it would be inefficient to store these vertices more than
once. Thus, the vertices are stored uniquely in a chained hash table. Since most
0
0
1
2
3
4
5
6
7
Top
Top
Front
Front
Right
Right
0 0 00000001
1 01 00000010
2 010 00000100
3 011 00001000
4 100 00010000
5 101 00100000
6 110 01000000
7 111 10000000
Vertex If (+
Vertex If (+ )
Figure 16.11. Vertex num-
bering.
of the space does not contain any part of the surface, only those cubes that are
visited will be stored. The implicit function value is found for each vertex as it is
stored in the hash table.
Nothing is known about the topology of the surface so a search must be started
from every primitive to avoid any disconnected parts of the surface being missed.
A scalar can be used to scale the influence of a primitive. If the scalar can be less
than zero, then it is possible to search along an axis without finding an intersect-
ing edge. In this case, a more sophisticated search must be done to find a seed
cube (Galin & Akkouche, 1999).
Data Structures
The hash table entry holds five values:
• the i, j, k lattice indices of the identifying vertex (see Figure 16.11);
• f, the implicit function value of the identifying vertex;
• Boolean to indicate whether this cube has been visited.
The hash function computes an address in the hash table by selecting a few bits out
of each of i, j, k and combining them arithmetically. For example, the five least
significant bits produces a 15-bit address for a table, which must have a length
of 2
15
. Such a hash function can be neatly implemented in the C-preprocessor as
follows:
i
i
i
i
i
i
i
i
398 16. Implicit Modeling
#define NBITS 5
#define BMASK 037
#define HASH(a,b,c) (((a&BMASK)<<NBITS|b&BMASK)
<<NBITS|c&BMASK)
#define HSIZE 1<<NBITS
*
3
The queue (FIFO list) is used as temporary storage to identify the neighbors
for processing. The algorithm begins with a seed cube that is marked as visited
and placed on the queue. The first cube on the queue is dequeued and all its
unvisited neighbors are added to the queue. Each cube is processed and passed to
the second phase of the algorithm if it contains part of the surface. The queue is
then processed until empty.
16.3.3 Polygonization Algorithm
The second phase of the algorithm treats each cube independently. The cell is
replaced by a set of triangles that best matches the shape of the part of the surface
that passes through the cell. The algorithm must decide how to polygonize the cell
given the implicit function values at each vertex. These values will be positive or
negative (i.e., less than or greater than the iso-value), giving 256 combinations
Table 1
00000000
V1 set
V0 & V1 set
V0 set
V2 set
all unset
00000001
00000010
00000011
00000100
V0..V7 set
V1..V7 set
all set except
V1 unset
11111101
11111110
11111111
Table 2
Table 2
0
1
2
3
V2-V0
1
3
# polys
# edges
V2-V3
V2-V6
edges to
intersect
Figure 16.12. Table 2 contains the edges intersected by the surface. Table 1 points to the
appropriate entry in Table 2.
i
i
i
i
i
i
i
i
16.3. Space Partitioning 399
of positive or negative vertices for the eight vertices of the cube. A table of 256
entries provides the right vertices to use in each triangle (Figure 16.12). For ex-
ample, entry 4(00000100) points to a second table that records the vertices that
bound the intersecting edges. In this example, vertex number 2 is inside the sur-
face (f(V 2) >=iso) and, therefore, we wish to draw a triangle that connects the
points on the surface that intersect with edges bounded by (V 2,V0), (V 2,V3),
and (V 2,V6) as shown in Figure 16.13.
Finding Cube-Surface Intersections
Figure 16.13 shows a cube where vertex V
2
is inside the surface and all other
vertices are outside. Intersections with the surface occur on three edges as shown.
The surface intersects edge V
2
−V
6
at the point A. The fastest but inaccurate way
to calculate A is to use linear interpolation:
+
-
-
-
-
-
-
V
3
V
0
V
6
V
2
A
Figure 16.13. Finding the
intersection of the surface
with a cube edge.
f(A) −f(V
2
)
f(V
6
) − f (V
2
)
=
|A − V
2
|
side
.
If the cube side is 1 and the iso-value sought for f(A) is 0.5,then
A = V
3
+
0.5 − f(V
2
)
f(V
6
) − f (V
2
)
.
This works well for a static image but in animation error differences between
frames will be very noticeable. A root-finding method such as regula falsi should
be employed. This becomesmore computationallycostly as the gradient is needed
to evaluate the point of intersection. The gradient is also needed at surface points
for rendering. For many types of primitives it is simpler to find a numerical ap-
proximation using sample points around p,asin
∇f(p)=
f(p +Δx) − f (p)
Δx
,
f(p +Δy) − f (p)
Δy
,
f(p +Δz) − f(p)
Δz
.
A reasonable value for Δ has been found empirically to be 0.01 ∗side where side
is the length of a cube edge.
For manufacturing a mesh, as opposed to a set of independent triangles, a
second hash table can maintain a list of all the intersecting ed ges. Since each cube
edge is shared by up to four neighbors, the edge hash table prevents repetition of
the surface-cube edge intersection calculation. The hash address can be derived
from the same hash function as for vertices (applied to the edge endpoints).
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.