Graphics Reference
In-Depth Information
Also recall from multivariable calculus that, since
S
is an isocontour of
φ
, the normal to
S
is parallel to
∇
φ
. Knowing that
∇
φ
=1andthat
φ
is negative in the inside, it's not hard to see that
∇
φ
is in fact exactly
the unit-length outward-pointing normal
n
.Moreover,
φ
is defined nearly
everywhere else, off the surface, and clearly must be the same as the normal
n
at the closest point on
S
.Thuswecanuse
∇
∇
φ
as the natural extension
of the surface normal.
I should interject here that later, when we use numerical approximations
to the signed distance, the gradient
φ
(or finite difference estimates of it)
may not be exactly unit length. In this case, it usually makes sense to
normalize the result. If you happen to have the bad luck of evaluating
it on the medial axis, where signed distance isn't differentiable, there's
even a chance that the finite difference might evaluate to zero—in this case
typically a default unit length vector such as (1
,
0
,
0) is used.
It nearly goes without saying that signed distance of course also allows
easy inside/outside tests: just check the sign of
φ
(
x
).
∇
6.2.2 Calculating Signed Distance
Typically we will start the simulation with a known signed distance function
(either precomputed, or an analytic function such as
r
forasphere
centered on
c
with radius
r
). However, if we are only given the implicit
surface with an arbitrary function on a grid, or are constructing it from
marker particle data, or are given a triangle mesh of the surface, we need
to calculate signed distance.
There are two general approaches: PDE methods that numerically ap-
proximate
x
−
c
−
= 1 (technically known as the Eikonal equation) and
geometric methods that instead calculate distances to the surface. There
are merits to both approaches, but we will focus on the latter as they are
very robust and accurate but also can be simple and quite fast. In partic-
ular, we base our method on algorithm 4 in Tsai's article [Tsai 02]. For a
recent review of many other algorithms, see the paper by Jones et al. [Jones
et al. 06].
The algorithm is given in Figure 6.1. It eciently propagates infor-
mation about the surface out to grid points far away, without requiring
expensive
4
geometric searches for every single grid point. There are several
details to work out: finding the closest points for grid points near the sur-
face, what order to loop over grid points, and determining inside/outside.
∇
φ
4
Expensive either in terms of CPU time for brute-force methods or programmer time
for sophisticated fast methods!
