i
i
i
i
i
i
i
i
712 28. Spatial-Field Visualization
isovalue f
0
, there is a surface in the cell if the minimum and maximum of the
eight vertex values surround f
0
. What surfaces occur depend on the arrangement
of values above and below f
0
. This is shown for three cases in Figure 28.6.
Figure 28.6. Three cases
for polygonal isosurfacing.
The black vertices are on
one side of the isovalue,
and the white on the other.
There are a total of 2
8
= 256 cases for vertices above and below the isovalue.
We can just enumerate all the cases in a table, and do a look-up. We can also
take advantage of some symmetries to reduce the table size. For example, if we
reverse above/below vertices, we can halve the table size. If we are willing to do
flips and rotations, we can reduce the table to size 16, where only 15 of the cases
have polygons.
Ray Tracing
Although the above algorithm, usually called marching cubes is elegant and sim-
ple, some care must be taken to ensure accurate results (Nielson, 2003).
The algorithm for intersecting a ray with an isosurface has three phases: tra-
versing a ray through cells which do not contain an isosurface, analytically com-
puting the isosurface when intersecting a voxel containing the isosurface, shading
the resulting intersection point (Lin & Ching, 1996; Parker, Parker, et al., 1999).
This process is repeated for each pixel on the screen.
To find an intersection, the ray a + tb traverses cells in the volume checking
each cell to see if its data range bounds an isovalue. If it does, an analytic com-
putation is performed to solve for the ray parameter t at the intersection with the
isosurface:
ρ(x
a
+ tx
b
,y
a
+ ty
b
,z
a
+ tz
b
) − ρ
iso
=0.
When approximating ρ with a trilinear interpolation between discrete grid points,
this equation will expand to a cubic polynomial in t. This cubic can then be
solved in closed form to find the intersections of the ray with the isosurface in
that cell. Only the roots of the polynomial which are contained in the cell are
examined. There may be multiple roots corresponding to multiple intersection
points. In this case, the smallest t (closest to the eye) is used. There may also
be no roots of the polynomial, in which case the ray misses the isosurface in the
cell.
A rectilinear volume is composed of a three-dimensional array of point sam-
ples that are aligned to the Cartesian axes and are equally spaced in a given dimen-
sion. A single cell from such a volume is shown in Figure 28.7. Other cells can
be generated by exchanging indices (i, j, k) for the zeros and ones in the figure.