Graphics Reference
In-Depth Information
•
Find the closest points on the surface for the nearby grid points,
setting their signed distance values accordingly.
Set the other
grid points as unknown.
•
Loop over the unknown grid points (
i, j, k
) in a chosen order:
•
Find all neighboring grid points that have a known signed
distance and closest surface point.
•
Find the distances from
x
i,j,k
to those surface points. If
x
i,j,k
is closer than a neighbor, mark the neighbor as unknown again.
•
Take the minimum of the distances, determine if (
i, j, k
)is
inside or outside, and set its signed distance value accordingly.
Figure 6.1.
A geometry-based signed distance construction algorithm.
Finding Closest Points.
If our input is an implicit surface function already
sampled on the grid (but presumably not with signed distance) then we
can immediately identify which grid points are near the surface: they are
those with a neighbor of a different sign.
The simplest approximation if grid values are already given is to esti-
mate the surface points along the lines between a grid point and its neigh-
bors, by finding where the linear interpolant is zero, and then taking the
closest of all these candidate points. This has the advantage of being guar-
anteed to find reasonable estimates of points on the surface, though they
may well not be the closest points, and so accuracy can be less than desired.
Also, if the underlying geometry we're trying to recover is curved within a
grid cell, the linear-interpolation model can be significantly off, flattening
out the curve—and in the process changing the shape of the surface, which
is clearly less than ideal.
An alternative for marker particles, with some given radius
r
,isto
compute distance to the particles themselves at nearby grid points and
then subtract off
r
. We can do this eciently by initializing the grid to
some large upper bound on distances, then for each particle, setting the
distance of nearby grid points (say within distance max(3
r,
2Δ
x
)) to the
minimum of their current value or distance to the particle, minus
r
.
Finally, if our geometry is given in the form of a triangle mesh we
can adapt the particle approach. Here we loop over the triangles instead
of particles, setting grid values within an expanded bounding box around
the triangle to the minimum of their current value and the exact distance
