LINEBURG


<< . .

 8
( 23)



. . >>




run parallel in underresolved regions of the ¬‚ow. This indeterminacy leads
to vanishing viscosity solutions that can incorrectly delete characteristics
’0.5

when they appear to be merging.
’1



9.2 Using Particles to Preserve Characteristics
’1.5



In [61], Enright, Fedkiw, Ferziger, and Mitchell designed a hybrid parti-
’2
’2 ’1.5 ’1 ’0.5 0 0.5 1 1.5 2
cle level set method to alleviate the mass loss issues associated with the
x

level set method. In the case of ¬‚uid ¬‚ows, knowing a priori that there
Figure 9.3. Initial square interface location and the location of a number of
are no shocks present in the ¬‚uid velocity ¬eld, one can assert that char-
particles seeded interior to the interface.
acteristic information associated with that velocity ¬eld should never be
deleted. They randomly seed particles near the interface and passively ad-
vect them with the ¬‚ow. When marker particles cross over the interface,
this indicates that characteristic information has been incorrectly deleted,
1

and these errors are ¬xed by locally rebuilding the level set function using
the characteristic information present in these escaped marker particles.
Since there is characteristic information on both sides of the interface,
0.5
two sets of marker particles are needed. Initially, particles of both types are
seeded locally on both sides of the interface, as shown in Figure 9.5. Then
an equation of the form
0
y




xnew = x + (φnew ’ φ(x)) N (9.1)
is used to attract particles initially located at x on the φ = φ(x) isocontour
to the desired φ = φnew isocontour. φnew is chosen to place the particles on
’0.5
the correct side of the interface in a slightly randomized position. Figure 9.6
shows the initial placement of particles after an attraction step.
The particles are initially given a ¬xed radius of in¬‚uence based on their
’1
distance from the interface after the seeding and attraction algorithms
have been employed. As the particles are integrated forward in time using
’1 ’0.5 0 0.5 1
xt = V , their position is continually monitored in order to detect possible
x

interface crossings. When a particle crosses over the interface, indicating
Figure 9.4. Final square interface location and the ¬nal location of the particles
incorrectly deleted characteristic information, the particle™s sphere of in-
initially seeded interior to the interface. A number of particles have incorrectly
¬‚uence is used to restore this lost information. This is done with a locally
escaped from the interior and need to be deleted in order to obtain the correct
applied Boolean union operation that simply adds the particle™s sphere of
vanishing viscosity solution.
in¬‚uence to the damaged level set function; i.e., at each grid point of the
9.2. Using Particles to Preserve Characteristics 83 84 9. Particle Level Set Method

cell containing the particle, the local value of φ is changed to accurately
95
re¬‚ect the union of the particle sphere with the existing level set function.
Figures 9.7 and 9.8 show the rigid-body rotation of a notched sphere
90
using the level set method and the particle level set method, respectively.
Similarly, Figures 9.9 and 9.10 show the results of the “Enright test,” where
85
a sphere is entrained by vortices and stretched out very thin before the ¬‚ow
time reverses returning the sphere to its original form. The particle level
80
set solution in Figure 9.10 returns (almost exactly) to its original spherical
shape, while the level set solution in Figure 9.9 shows an 80% volume loss
75
y




on the same 1003 grid.
70



65



60



55
30 35 40 45 50 55 60 65 70
x


Figure 9.5. Initial placement of both types of particles on both sides of the
interface. (See also color ¬gure, Plate 1.)


95



90



85



80



75
y




70



65



60



55
30 35 40 45 50 55 60 65 70
x


Figure 9.6. Particle positions after the initial attraction step is used to place them
on the appropriate side of the interface. (See also color ¬gure, Plate 2.)
9.2. Using Particles to Preserve Characteristics 85 86 9. Particle Level Set Method




Figure 9.9. Level set solution for the “Enright test” with 80% volume loss by the
Figure 9.7. Smeared-out level set solution of a rigidly rotating notched sphere.
¬nal frame.




Figure 9.10. Particle level set solution for the “Enright Test.” The sphere returns
Figure 9.8. High-quality particle level set solution of a rigidly rotating notched
almost exactly to its original shape in the time reversed ¬‚ow.
sphere.
88 10. Codimension-Two Objects

1 1

0.5 0.5

10 0 0


Codimension-Two Objects ’0.5 ’0.5

’1 ’1
’1 ’1
0 0
1 ’1 1 ’1
1 1
0 0


1 1

0.5 0.5

0 0

’0.5 ’0.5

’1 ’1
’1 ’1
10.1 Intersecting Two Level Set Functions 0 0
1 ’1 1 ’1
1 1
0 0
Typically, level set methods are used to model codimension-one objects such
as points in 1 , curves in 2 , and surfaces in 3 . Burchard, Cheng, Merri- Figure 10.1. Two helices evolving under curvature motion eventually touch and
merge together.
man, and Osher [22] extended level set technology to treat codimension-two
objects using the intersection of the zero level sets of two level set func-
tions. That is, instead of implicitly representing codimension-one geometry
by the zero isocontour of a function φ, codimension-two geometry is rep- vectors are just a normalization of this:
resented as the intersection of the zero isocontour of a function φ1 with
φ1 — φ2
the zero isocontour of another function φ2 . In one spatial dimension, zero
T= . (10.1)
| φ1 — φ2 |
isocontours are points, and their intersection is usually the empty set. In
two spatial dimensions, zero isocontours are curves, and the intersections
Note that replacing φ1 with ’φ1 reverses the direction of the tangent
of curves tend to be points which are of codimension two. In three spatial
vectors. This is also true when φ2 is replaced with ’φ2 .
dimensions, the zero isocontours are surfaces, and the intersections of these
The curvature times the normal, κN , is the derivative of the tangent
surfaces tend to be codimension two curves.
vector along the curve, i.e., with respect to arc length s,

dT
κN = . (10.2)
ds
3
10.2 Modeling Curves in Using directional derivatives, this becomes
« 
In order to model curves as the intersection of the φ1 = 0 and φ2 = 0
T1 · T
isocontours of functions φ1 and φ2 in 3 , a number of relevant geometric
T ·T = T2 · T  ,
κN = (10.3)
quantities need to be de¬ned. To ¬nd the tangent vectors T , note that
T3 · T
φ1 — φ2 , taken on the curve, is tangent to the curve. So the tangent
3
10.2. Modeling Curves in 89 90 10. Codimension-Two Objects

Setting V = N or V = B gives motion in the normal or binormal direction,
respectively. Figures 10.1 and 10.2 show curves evolving under curvature
1 1
motion in three spatial dimensions. In Figure 10.1 (page 88), two helices
touch and merge. Similarly, in Figure 10.2 (page 89), two closed curves
0 0 evolve independently until they touch and merge together.

1 1
1 1
10.3 Open Curves and Surfaces
1 1
0 0
0 0
1 1
1 1
Level set methods are used to represent closed curves and surfaces that
may begin and end at the boundaries of the computational domain. How-
ever, it is not clear how to devise methods for curves and surfaces that
have ends or edges (respectively) within the computational domain. Curves
in 2 have codimension two ends given by points, while surfaces in 3 have
1 1
codimension-two edges given by curves. A ¬rst step in this direction was
carried out by Smereka [152] in the context of spiral crystal growth. In two
0 0
spatial dimensions, he used the intersection of two level set functions φ
and ψ to represent the codimension-two points at the beginning and end
of an open curve. The curve of interest was de¬ned as the φ = 0 isocontour
1 1
1 1 in the region where ψ > 0, while a ghost curve was de¬ned as the φ = 0
1 1
0 0 isocontour in the region where ψ < 0. Velocities were derived for both the
0 0
curve and the ¬ctitious ghost curve that exists only for computational pur-
1 1
1 1
poses. Figure 10.3 shows an initial con¬guration where the curve moves
Figure 10.2. Two rings evolving under curvature motion eventually touch and upward and the ghost curve moves downward, as shown at a later time in
merge together. Figure 10.4. Figure 10.5 shows this open curve rolling up and subsequently
merging with itself, pinching o¬ independently evolving closed curves.
where T1 , T2 , and T3 are the components of the tangent vector T . Then
the normal vectors can be de¬ned by normalizing this quantity,
10.4 Geometric Optics in a Phase-Space-Based
κN
N= , (10.4)
Level Set Framework
|κN |
and the binormal vectors are de¬ned as
In [124], Osher et al. introduced a level-set-based approach for ray tracing
and for the construction of wave fronts in geometric optics. The approach
T —N
B= . (10.5) automatically handles the multivalued solutions that appear and automat-
|T — N |
ically resolves the wave fronts. The key idea, ¬rst introduced by Engquist,
The torsion times the normal vector is de¬ned as „ N = ’ B · T . All these Runborg, and Tornberg [60], but used in a “segment projection” method
geometric quantities can be written in terms of φ1 and φ2 and computed rather than level set fashion, is to use the linear Liouville equation in twice
as many independent variables, (actually, 2d ’ 1, using a normalization)
at each grid point one uses similar to the way the normal and curvature
are computed when using standard level set technology for codimension- and solve in this higher-dimensional space via the idea introduced by Bur-
one objects. Interpolation can be used to de¬ne these geometric quantities chard et al. [22]. In two-dimensional ray tracing this involves solving for an
between grid points. evolving curve in x, y, θ space, where θ is the angle of the normal to the
Both φ1 and φ2 are evolved in time using the standard level set equation. curve. This, of course, uses two level set functions and gives codimension-2
A velocity of V = κN gives curvature motion in the normal direction. motion in 3-space plus time. A local level set method can be used to make
10.4. Geometric Optics in a Phase-Space-Based Level Set Framework 91 92 10. Codimension-Two Objects
10 10

φ>0 8 8

6 6

4 4
ψ<0 ψ>0 ψ<0
2 2

0 0

’2 ’2




¤¤¤




¥¥¥¥
’4 ’4
¢¢£




  ¡
¡
’6 ’6

’8 ’8

’10 ’10
’10 ’5 0 5 10 ’10 ’5 0 5 10


φ<0
10 10

8 8

6 6

4 4


Figure 10.3. The hortizontal line marks the set where φ = 0 while the two veritical 2 2

lines mark the set where ψ = 0. The arrow in the center indicates the motion of 0 0
the real curve while the arrows to the right and left indicate the motion of the
’2 ’2
ghost curves.
’4 ’4

’6 ’6

φ>0 ’8 ’8

’10 ’10
’10 ’5 0 5 10 ’10 ’5 0 5 10


Figure 10.5. Four snapshots of the evolving open curve at various times. The curve
ψ<0 ψ>0 ψ<0
rolls up subsequently merging with itself pinching o¬ independently evolving
closed curves.

the complexity tractable, O(n2 log(n)), for n the number of points on the
¦¦¨¦¦§
§§




©¨©
©¨©




curve for every time iteration. The memory requirement is O(n2 ).
§




In three-dimensional ray tracing this involves solving for an evolving two-







<< . .

 8
( 23)



. . >>

Copyright Design by: Sunlight webdesign