Graphics Reference
In-Depth Information
The setting for the algorithm is the following: It is assumed that the data has been
acquired and possibly processed with some image processing techniques and is avail-
able as a three-dimensional array of voxels. If we think of the data as corresponding
to some density values, then the object is to use this data to define a surface S spec-
ified in terms of a given density value s. Data classification then amounts to using s
as a threshold value.
The algorithm proceeds as follows: For each voxel or cube we determine how its
vertices are situated with respect to our surface S and then “march” on to the next
cube. Each vertex is assigned a value of 1 if its density is greater than or equal to s,
that is, they are inside the surface, and 0 otherwise, if they are outside. This gives rise
to a classification of the possible types of intersections of the surface with the cube,
where the classification is based on which edges of the cube the surface intersects.
We then simply use a table to look up what our intersection looks like for any par-
ticular case. The numbering of vertices allows, in principle, up to 2 8 = 256 possible
configurations of 1s and 0s for a given cube. Each case corresponds to an intersec-
tion type. Fortunately, one can use symmetry to reduce this number. One type of sym-
metry is based on the fact that the intersection type of the surface is unchanged if we
swap what is considered as the “inside” and “outside” of the surface, that is, if we
exchange 1s and 0s. This means that we only need to consider the cases where only
zero to four vertices have a value of 1. A second type of symmetry is rotational
symmetry. Making use of these symmetries, we can reduce our table of intersections
to fourteen. These are shown in Figure 10.19. Solid disks indicate the vertices with
value 1. Figure 10.19 also shows the triangulations that are used to approximate the
intersection. The triangles are defined using linear interpolation of the vertex values.
Since what is important is the intersection of the surface with the edges of the cube,
we record the edge intersection information in our table. As it happens, two of the
cases in Figure 10.19, cases 5 and 10, are ambiguous and these ambiguities have to
be resolved. See [ScML98] or [WilV90b].
For rendering, one also needs normals for each triangle. These are also obtained
via linear interpolation of the gradient of density values at the vertices of the cube.
It is assumed that this gradient is nonzero along our surface. Now, it is a well-
known fact (see Section 8.4 in [AgoM05]) that if a surface is defined by an equation
f(x,y,z) = c where f is some function and c is a constant, then the gradient of f,
f, is
normal to the surface. To approximate the gradient at the vertices, one uses central
differences:
(
) --
(
)
f
x
fi
+
1
,,
jk
fi
1
,,
jk
~
D
x
(
) --
(
)
f
y
fij
,
+
1
,
k
fij
,
1
,
k
~
D
y
(
) -
(
)
f
z
fijk
,,
+
1
fijk
z
,,
-
1
~
D
where Dx, Dy, and Dz are the lengths of the sides of the cubes.
Search WWH ::




Custom Search