Graphics Reference
In-Depth Information
Figure 10.18.
Tripod 6-connected line-drawing algorithm cases.
determine the actual face by which it leaves by analyzing the projections
L
xy
,
L
xz
, and
L
yz
with respect to the projections of the three edges of the pixel that meet in the point
O
. See Figure 10.18(b-e). Note that, like in the midpoint line-drawing algorithm, the
sign of f
i
(0.5,0.5) tells us the relative position of the corresponding line with respect
to the point (0.5,0.5). If the sign is negative, the line is below the point. Since it is the
taxicab metric that determines the length of lines in the case of 6-connected lines, our
line will have dx + dy + dz + 1 points. Algorithm 10.4.1.2 implements the algorithm.
The reason for the name is that the vertex
O
and the three edges emanating from it
in Figure 10.18(b) have the appearance of a tripod.
Efficient C versions of Algorithms 10.4.1.1 and 10.4.1.2 can be found in [CohK97].
Rather than indexing into a voxel array the idea is to use a pointer to the beginning
of the array and then, using pointer arithmetic, to add the appropriate offsets instead
of updating indexes. [CohK97] also contains a discussion of and references for other
algorithms for drawing three-dimensional discrete lines. Another algorithm and more
references can be found in [Roge98].
[YaCK92] describes how rays generated using the algorithms of this section can
be used to ray trace voxelized objects. Note that 26-connected rays contain a lot fewer
pixels than 6-connected rays, but one has to worry about tunnels that would cause
artifacts in the image. One can mix 26-connected and 6-connected rays, using the
latter only when we are near objects.
10.4.2
The Marching Cubes Algorithm
The marching cubes algorithm was developed independently by [WyMW86] and
[LorC87]. We follow the outline of the algorithm presented in [LorC87]. For an imple-
mentation of the algorithm we refer the interested reader to [WatW92].
