Graphics Reference
In-Depth Information
zero-level set for the function whose values we know at the grid points, as shown
in Figure 25.23.
In doing so, however, we are ignoring additional data: At each estimated zero
point, we can also make an estimate of the
gradient
of the function (see Fig-
ure 25.24) (or perhaps get the gradient directly as part of gathering the original
data) and use these in estimating the shape of the level set.
2
6
4
2
4
3
This can be called an “Hermite” version (see Chapter 22) of marching squares.
The
extended marching cubes
algorithm [KBSS01] uses this Hermite data to
determine how the interior of a square appears: If the normals for the data in a
square are similar, the algorithm defaults to standard marching squares. But if
the point-normal pairs for a square (say
(
X
1
,
n
1
)
and
(
X
2
,
n
2
))
are inconsistent (if
n
1
and
n
2
are not nearly parallel enough), then the square is treated differently:
A new vertex,
X
, is placed in the square in such a way that it minimizes a
quadratic error function,
X
=
arg min
i
Figure 25.23: Knowing function
values at grid points, we can esti-
mate zero-crossings (black dots)
by linear interpolation, and then
connect the dots, in each cell, to
estimate the level curve at level
zero.
n
i
)
2
,
((
X
−
X
i
)
·
(25.9)
as shown in Figure 25.25; in other words,
X
seeks to lie on the lines determined
both by
(
X
1
,
n
1
)
and
(
X
2
,
n
2
)
. (In 2D, this is trivial; in 3D, where there may be
more contributing point-normal pairs, the minimization can be more complicated.)
The newly inserted point is connected (with a pair of edges in 2D, or with a trian-
gle fan based at
X
in 3D) to the zero-set on the boundary of the grid cell.
2
6
4
4
2
3
There are two small problems.
1.
If the normal vectors are sufficiently antiparallel, it's possible that the min-
imizer
X
lies outside the square, and
X
must be adjusted to lie within it.
Figure 25.24: We can estimate
gradients at the zero-crossings
as well. Fitting a surface to the
point-and-direction data gives a
different estimate of the level-set.
2.
In the 3D case, if there are “extra points”
X
1
and
X
2
in two adjacent cells,
we perform an edge flip on the contour edge that lies in the grid face
between the two cells so that this edge now goes from
X
1
to
X
2
.
Inline Exercise 25.8:
Argue that the “bad minimizer” problem above is
the result of
aliasing
. What sampling is going on? Where are the too-high
frequencies?
6
2
4
X
In estimating (at least in special cases) a surface point in the interior of a cell,
the extended marching cubes algorithm suggests a different approach: If we had a
surface point in adjacent cells, we could join these with edges (and faces, in 3D),
using the points on grid edges as guides. Such an approach is called
dual con-
touring.
Ju et al. [JLSW02] developed a scheme for dual contouring of Hermite
data, which involves two steps.
2
3
4
Figure 25.25: The normals at the
two zero-crossings determine two
lines, which intersect at a new
point X.
1. For each cell with differently signed vertices (i.e., not all positive or all
negative), generate a mesh vertex within the cell by minimizing a quadratic
error function.
2. For each edge with differently signed vertices, generate an edge (for 2D)
or a quad (for 3D) connecting the minimizing vertices in the adjacent cells.
This algorithm has the pleasant characteristic that all cells are treated
identically—there's no threshold on when “normal vectors are close enough”—
but there are subtleties: Again, the minimizing point for a quadratic error function
