Graphics Reference
In-Depth Information
the three-dimensional data directly. Because
S
corresponds to the voxels having some
specified density values it is also sometimes called a contour or isosurface and the
algorithms that find it, contour algorithms. One is called the
marching cube algorithm
.
It is more complicated though. We give an overview of the algorithm in Section 10.4.2.
Another algorithm that finds
S
using octrees is described in [WilV90a]. A third algo-
rithm due to Ehud Artzy is described in [Herm98]. Here we assume that the voxels
have been assigned a value of 0 or 1. In practice, the voxels with value 1 correspond
to the tissue of interest in a CT scan. The algorithm then determines all the faces of
the voxels that are in the boundary of a connected component of the set of voxels
marked with 1. Although Artzy's algorithm is not hard to describe, proving that it
works relies on a theorem in discrete topology (one proved in [Herm98]).
When using surfaces in volume rendering one problem is the fact that defining a
surface is a binary decision process (a surface divides a region into two parts). Since
that decision is made on sampled functions, one can easily end up with spurious or
missing surface parts. With regard to the aliasing problem, we run into an added com-
plication in volume rendering. Since we only have the sampled data that was origi-
nally presented to us, we cannot readily generate new samples on our own. Basically,
the responsibility lies with the original data having been sampled adequately.
Finally, there are many nice aspects to volume rendering. Some tasks that are hard
with other rendering methods become easy here. Consider again the example of how
easy it is to modify the geometry and create the effect of cutting a hole in an object
to look inside. Levoy ([Levo90]) describes a hybrid ray tracer for both volume and
polygon data.
10.4.1
Discrete Three-Dimensional Lines
Section 2.2 already introduced the basic discrete topology concepts. Specifically, we
defined what is meant by a curve in
Z
3
that is 6-, 18-, or 26-connected. Our goal now
is to describe some three-dimensional analogs of the two-dimensional Bresenham
line-drawing algorithm. These are the algorithms used in volume rendering to define
voxelized rays. Because of the higher dimension, things get somewhat more compli-
cated. Furthermore, since we are interested in the application of this to volume ren-
dering, we have to address some issues that were not considered in Chapter 2.
We start again with the two-dimensional case because examples are easier to draw
and therefore clearer. When boundaries of sets are represented in a discrete way, we
have to worry about “holes” or “tunnels” through which a ray can pass. Figure 10.17(a)
shows an example of an 8-connected ray passing through an 8-connected boundary
without intersecting it. Figure 10.17(b) shows the same thing in three dimensions,
namely, an 18-connected ray passing through a 6-connected object. We do not want
to allow this, otherwise, the rendering of our voxelized objects will be flawed. To avoid
the problems demonstrated by Figure 10.17, we must make sure that objects and rays
are suitable connected.
The algorithms for generating discrete rays in 3-space are motivated by the mid-
point line-drawing algorithm we used in the plane. See Algorithm 2.5.3.1 in Section
2.5.3. Suppose that we want to draw a discrete version of a line
L
from
p
0
= (x
0
,y
0
,z
0
)
to
p
1
= (x
1
,y
1
,z
1
). Let
