Graphics Reference
In-Depth Information
h
i
k
max
i
w
i
d
FIGURE 12.8
Deformation function in the propagation region.
12.1.5
Level set methods
“Level set methods add dynamics to implicit surfaces” [
13
]. These methods operate on signed distance
functions using a grid representation for an object. Each grid cell contains the value of the signed dis-
tance function at that location in space. An isosurface,
j
, is computed on the grid as the interface
between positive and negative values. The isosurface is updated according to a velocity field defined
over the interface. For example, in two-dimensional space,
dj
/
dt¼V
(
x
,
y
,
t
). The function
V
can be given
as an externally generated velocity field. The isosurface advects (i.e., moves) in the direction of the
velocity function. A commonly used function uses the direction of the (positive or negative) gradient
of
j
and a constant magnitude. Thus, the isosurface advects in the direction of its normal at a constant
speed. Alternatively, the speed may be based on the magnitude of the curvature,
d
2
2
. A Euler
j
/
dt
update of
j
(
t þ Dt
)
¼ j
(t)
þ dt
*
V
can be used to actually update the grid values. This is called
solving
the level set equations.
Every step taken in time corrupts the signed distance function of the grid as values are modified.
Thus, the grid values need to be updated, called
renormalized
, in order to construct a signed distance
field again.
The level set equations for advection of a surface by a vector field are represented by
Equations 12.4
and
12.5
.
H ¼ V rf
(12.4)
df
dx
;
df
dy
rf ¼
(12.5)
where
V
is a vector field.
Solving the level set equations moves the interface in the direction of the vector field. For each
coordinate, calculate
V
rj
and see where it takes the interface.
rj
is calculated from the grid
representation.
To approximate
rj
, use the upwind scheme such that, in the horizontal case,
df
dx
¼ fðx þ
if
; v
x
<
0
;
1
; yÞfðx; yÞ
df
dx
¼ fðx; yÞfðx
; v
x
>
;
; yÞ
if
0
1
Search WWH ::
Custom Search