Graphics Reference
In-Depth Information
If two or more adjacent vertices have value 0, more complex problems arise.
For instance, if all four vertices of a grid square have value 0, then all edges
of the square should be included in the isocurve, as perhaps should the whole
square itself, which would make the isocurve no longer be a curve! We address
these cases in the same way as the previous case: We adjust all 0 values slightly,
compute the isocurve, and then adjust vertices at the end. But if a vertex lies on a
grid edge where both ends have value 0, rather than moving the vertex to one end
or the other, we place it at the middle of the edge. The result of this is an isocurve
that's topologically correct in any grid cell with no 0 values at its corners, and is
topologically consistent even in cells where there are zeroes. This is an instance
of our second assumption—that in indeterminate cases, any consistent answer is
acceptable—except that we do not always include the entire grid edge between
two zeroes.
The difficulties of handling zeroes in the data are intrinsic to the original prob-
lem: In places where the graph of a function is nearly horizontal, level curves are
unstable,
in the sense that a small change in the input (the data values) results in a
large change in the resultant level curve.
The
marching cubes
algorithm for finding an isosurface of a function specified at
grid vertices in 3-space is exactly analogous, although there are some subtleties.
Once again, it's easiest to assume that all input values are nonzero; if there's a
zero in the input, perturb it by a small random amount, compute the isosurface,
and then move the isosurface vertices back to the proper locations as we did in the
marching squares algorithm.
Again, the output associated to a particular cube in the grid is determined by
the pattern of plusses and minuses at its vertices. Since there are eight vertices,
each with a plus or minus sign, we can encode the pattern of plusses and minuses
with an 8-bit binary number; this can be used to index into a table of presolved
examples, containing the vertex and triangle table for the mesh structure of the
output; the actual locations of the vertices in the vertex table are once again deter-
mined by interpolation along edges of the grid.
Figure 24.12 shows two of these cases: The first generates a single triangle
as output, and the second generates a rectangle, which would generally be repre-
sented by two triangles.
11
1
2
2
2
1
1
1
1
1
1
1
1
Figure 24.12: Two examples of
patterns of plusses and minuses,
and the associated bits of iso-
surface.
11
2
1
2
In the marching squares algorithm, a grid edge contained either no isocurve
vertex or one isocurve vertex. In the latter case, each of the two adjacent grid
squares had an edge that ended at that vertex, so each vertex met two edges, and
the edges therefore fell into long chains (which either were closed curves, or ter-
minated at the boundary of the grid). In the marching cubes algorithm, adjacent
cubes meet along a face, as shown in Figure 24.13; these faces share isosurface
vertices, but the way that the isosurface vertices are connected by edges within
each copy of the face might not be consistent. If this happens, the resultant model
of the isosurface will have edges in the interior of the grid, which is inappropriate.
It's critical therefore that the 256 models used for the 256 possible cases in the
marching cubes algorithm be pairwise consistent so that the resultant isosurface
mesh either is closed or has boundary edges only on the boundary of the input grid.
As in the marching squares algorithm, the marching cubes algorithm is
very well suited for a one-plane-of-data-at-a-time approach, in which the output
1
1
Figure 24.13: Two adjacent
cubes in the marching cubes
algorithm share a single face.
The same four vertices appear
on the four edges of this face, but
the edges that join together pairs
of isosurface vertices in each
cube are not consistent with one
another; the surface that results
will have a boundary rather than
being a closed surface.
