14
The minimum of this function describes a point that is closest to the intersection of all
the surfaces that satisfy tk(x) = t-7(rr). This is a non-linear optimization problem that
can be costly to compute. We approximate the solution using an QEF-based approach
that is described by Schaefer et al [24]. This method locates the intersections, pi, of
the surfaces along the cell edges. These intersections and the normals, ni, at these
points describe a set of planes per cell. We then find a point that minimizes
E'(z) = ∑>j. (x-pj))2 (2.4)
i
This minimization gives an approximation of Eq. 2.3 that is reasonable for our pur-
pose. Note that this is an outline for computing the contour point. Please refer to
the work of Schaefer et al. for more implementation details [24].
Since we are replacing the tri-linear function in each cell with linear approxima-
tions, the contour may not retain enough details of the original function. We can
retrieve these details by subdividing the grid space into finer cells. The new mask in-
dices are determined by the classification method described previously; the new scalar
for the refined map must be computed per each material. In effect, this approach will
expand the storage size for the scalar by a factor of n, where n is the number of ma-
terials. This can be done adaptively to subdivide cells only along material border to
reduce the computation and storage size. In our experiments, we perform a uniform
subdivision over the entire volume, but we also notice that refinement is not necessary
in most cases. Figure 2.4 shows the results of meshing using Dual Contouring.
Gradient
One useful property from standard implicit modeling is that the gradient of the
implicit function is normal to the contours of that function. In the multi-material case,
a similar property holds. Given a contour formed by the iso-surface tfc(τ) = t∙7(τ), the
gradient of the function tfe(rr) — t∙7(τ) is simply the normal to this surface. The key
observation here is that the pair of material indices j and к change as the point x varies