LINEBURG


 1
( 23)



. . >>

Stanley Osher Ronald Fedkiw



Level Set Methods and
Dynamic Implicit Surfaces


With 99 Figures, Including 24 in Full Color
viii Preface

of moving interfaces plays a key role in the problem to be solved. A search of
“level set methods” on the Google website (which gave over 2,700 responses
as of May 2002) will give an interested reader some idea of the scope and
utility of the method. In addition, some exciting advances in the technology
have been made since we began writing this book. We hope to cover many of
these topics in a future edition. In the meantime you can ¬nd some exciting
animations and moving images as well as links to more relevant research pa-
Preface pers via our personal web sites: http://graphics.stanford.edu/˜fedkiw
and http://www.math.ucla.edu/˜sjo/.


Acknowledgments
Many people have helped us in this e¬ort. We thank the following col-
leagues in particular: Steve Marschner, Paul Romburg, Gary Hewer, and
Steve Ruuth for proofreading parts of the manuscript, Peter Smereka and
Li-Tien Cheng for providing ¬gures for the chapter on Codimension-Two
Objects, Myungjoo Kang for providing ¬gures for the chapter on Motion
Involving Mean Curvature and Motion in the Normal Direction, Antonio
Marquina and Frederic Gibou for help with the chapter on Image Restora-
tion, Hong-Kai Zhao for help with chapter 13, Reconstruction of Surfaces
Scope, Aims, and Audiences from Unorganized Data Points, and Luminita Vese for help with the chap-
ter on Snakes, Active Contours, and Segmentation. We particularly thank
Barry Merriman for his extremely valuable collaboration on much of the
This book, Level Set Methods and Dynamic Implicit Surfaces is designed
research described here. Of course we have bene¬tted immensely from col-
to serve two purposes:
laborations and discussions with far too many people to mention. We hope
Parts I and II introduce the reader to implicit surfaces and level set
these colleagues and friends forgive us for omitting their names.
methods. We have used these chapters to teach introductory courses on the
We would like to thank the following agencies for their support during
material to students with little more than a fundamental math background.
this period: ONR, AFOSR, NSF, ARO, and DARPA. We are particularly
No prior knowledge of partial di¬erential equations or numerical analysis
grateful to Dr. Wen Masters of ONR for suggesting and believing in this
is required. These ¬rst eight chapters include enough detailed information
project and for all of her encouragement during some of the more di¬cult
to allow students to create working level set codes from scratch.
times.
Parts III and IV of this book are based on a series of papers published
Finally, we thank our families and friends for putting up with us during
by us and our colleagues. For the sake of brevity, a few details have been
this exciting, but stressful period.
occasionally omitted. These chapters do include thorough explanations and
enough of the signi¬cant details along with the appropriate references to
Los Angeles, California Stanley Osher
allow the reader to get a ¬rm grasp on the material.
Stanford, California Ronald Fedkiw
This book is an introduction to the subject. We have given examples of
the utility of the method to a diverse (but by no means complete) collection
of application areas. We have also tried to give complete numerical recipes
and a self-contained course in the appropriate numerical analysis. We be-
lieve that this book will enable users to apply the techniques presented here
to real problems.
The level set method has been used in a rapidly growing number of areas,
far too many to be represented here. These include epitaxial growth, opti-
mal design, CAD, MEMS, optimal control, and others where the simulation
x Contents

3.2 Upwind Di¬erencing . . . . . . . . . . . . . . . . . . . . 29
3.3 Hamilton-Jacobi ENO . . . . . . . . . . . . . . . . . . . 31
3.4 Hamilton-Jacobi WENO . . . . . . . . . . . . . . . . . . 33
3.5 TVD Runge-Kutta . . . . . . . . . . . . . . . . . . . . . 37

4 Motion Involving Mean Curvature 41
Contents 4.1 Equation of Motion . . . . . . . . . . . . . . . . . . . . . 41
4.2 Numerical Discretization . . . . . . . . . . . . . . . . . . 44
4.3 Convection-Di¬usion Equations . . . . . . . . . . . . . . 45

5 Hamilton-Jacobi Equations 47
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.2 Connection with Conservation Laws . . . . . . . . . . . . 48
5.3 Numerical Discretization . . . . . . . . . . . . . . . . . . 49
5.3.1 Lax-Friedrichs Schemes . . . . . . . . . . . . . . . 50
5.3.2 The Roe-Fix Scheme . . . . . . . . . . . . . . . . 52
5.3.3 Godunov™s Scheme . . . . . . . . . . . . . . . . . 54

6 Motion in the Normal Direction 55
6.1 The Basic Equation . . . . . . . . . . . . . . . . . . . . . 55
6.2 Numerical Discretization . . . . . . . . . . . . . . . . . . 57
6.3 Adding a Curvature-Dependent Term . . . . . . . . . . . 59
Preface vii
6.4 Adding an External Velocity Field . . . . . . . . . . . . . 59
Color Insert (facing page 146)
7 Constructing Signed Distance Functions 63
I Implicit Surfaces 1 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 63
7.2 Reinitialization . . . . . . . . . . . . . . . . . . . . . . . 64
1 Implicit Functions 3
7.3 Crossing Times . . . . . . . . . . . . . . . . . . . . . . . 65
1.1 Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
7.4 The Reinitialization Equation . . . . . . . . . . . . . . . 65
1.2 Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 7.5 The Fast Marching Method . . . . . . . . . . . . . . . . 69
1.3 Surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Geometry Toolbox . . . . . . . . . . . . . . . . . . . . . 8 8 Extrapolation in the Normal Direction 75
1.5 Calculus Toolbox . . . . . . . . . . . . . . . . . . . . . . 13 8.1 One-Way Extrapolation . . . . . . . . . . . . . . . . . . . 75
8.2 Two-Way Extrapolation . . . . . . . . . . . . . . . . . . 76
2 Signed Distance Functions 17 8.3 Fast Marching Method . . . . . . . . . . . . . . . . . . . 76
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Distance Functions . . . . . . . . . . . . . . . . . . . . . 17 9 Particle Level Set Method 79
2.3 Signed Distance Functions . . . . . . . . . . . . . . . . . 18 9.1 Eulerian Versus Lagrangian Representations . . . . . . . 79
2.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 9.2 Using Particles to Preserve Characteristics . . . . . . . . 82
2.5 Geometry and Calculus Toolboxes . . . . . . . . . . . . . 21
10 Codimension-Two Objects 87
10.1 Intersecting Two Level Set Functions . . . . . . ..... 87
10.2 Modeling Curves in 3 . . . . . . . . . . . . . .
II Level Set Methods 23 ..... 87
10.3 Open Curves and Surfaces . . . . . . . . . . . . ..... 90
3 Motion in an Externally Generated Velocity Field 25 10.4 Geometric Optics in a Phase-Space-Based Level
3.1 Convection . . . . . . . . . . . . . . . . . . . . . . . . . . 25 Set Framework . . . . . . . . . . . . . . . . . . . ..... 90
Contents xi xii Contents

III Image Processing and Computer Vision 95 15 Two-Phase Compressible Flow 167
15.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 167
11 Image Restoration 97 15.2 Errors at Discontinuities . . . . . . . . . . . . . . . . . . 168
11.1 Introduction to PDE-Based Image Restoration . . . . . . 97 15.3 Rankine-Hugoniot Jump Conditions . . . . . . . . . . . . 169
11.2 Total Variation-Based Image Restoration . . . . . . . . . 99 15.4 Nonconservative Numerical Methods . . . . . . . . . . . 171
11.3 Numerical Implementation of TV Restoration . . . . . . 103 15.5 Capturing Conservation . . . . . . . . . . . . . . . . . . 172
15.6 A Degree of Freedom . . . . . . . . . . . . . . . . . . . . 172
12 Snakes, Active Contours, and Segmentation 119
15.7 Isobaric Fix . . . . . . . . . . . . . . . . . . . . . . . . . 173
12.1 Introduction and Classical Active Contours . . . . . . . . 119
15.8 Ghost Fluid Method . . . . . . . . . . . . . . . . . . . . 175
12.2 Active Contours Without Edges . . . . . . . . . . . . . . 121
15.9 A Robust Alternative Interpolation . . . . . . . . . . . . 183
12.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
12.4 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . 124 16 Shocks, Detonations, and De¬‚agrations 189
16.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 189
13 Reconstruction of Surfaces from Unorganized
16.2 Computing the Velocity of the Discontinuity . . . . . . . 190
Data Points 139
16.3 Limitations of the Level Set Representation . . . . . . . 191
13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 139
16.4 Shock Waves . . . . . . . . . . . . . . . . . . . . . . . . . 191
13.2 The Basic Model . . . . . . . . . . . . . . . . . . . . . . 140
16.5 Detonation Waves . . . . . . . . . . . . . . . . . . . . . . 193
13.3 The Convection Model . . . . . . . . . . . . . . . . . . . 142
16.6 De¬‚agration Waves . . . . . . . . . . . . . . . . . . . . . 195
13.4 Numerical Implementation . . . . . . . . . . . . . . . . . 142
16.7 Multiple Spatial Dimensions . . . . . . . . . . . . . . . . 196

17 Solid-Fluid Coupling 201
IV Computational Physics 147
17.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 201
17.2 Lagrange Equations . . . . . . . . . . . . . . . . . . . . . 203
14 Hyperbolic Conservation Laws and
17.3 Treating the Interface . . . . . . . . . . . . . . . . . . . . 204
Compressible Flow 149
14.1 Hyperbolic Conservation Laws . . . . . . . . . . . . . . . 149
18 Incompressible Flow 209
14.1.1 Bulk Convection and Waves . . . . . . . . . . . . 150
18.1 Equations . . . . . . . . . . . . ...... . . . . . . . . 209
14.1.2 Contact Discontinuities . . . . . . . . . . . . . . . 151
18.2 MAC Grid . . . . . . . . . . . . ...... . . . . . . . . 210
14.1.3 Shock Waves . . . . . . . . . . . . . . . . . . . . . 152
18.3 Projection Method . . . . . . . ...... . . . . . . . . 212
14.1.4 Rarefaction Waves . . . . . . . . . . . . . . . . . 153
18.4 Poisson Equation . . . . . . . . ...... . . . . . . . . 213
14.2 Discrete Conservation Form . . . . . . . . . . . . . . . . 154
18.5 Simulating Smoke for Computer Graphics . . . . . . . . 214
14.3 ENO for Conservation Laws . . . . . . . . . . . . . . . . 155
14.3.1 Motivation . . . . . . . . . . . . . . . . . . . . . . 155
19 Free Surfaces 217
14.3.2 Constructing the Numerical Flux Function . . . . 157
19.1 Description of the Model . . . . . . . . . . . . . . . . . . 217
14.3.3 ENO-Roe Discretization
19.2 Simulating Water for Computer Graphics . . . . . . . . . 218
(Third-Order Accurate) . . . . . . . . . . .... 158
14.3.4 ENO-LLF Discretization
20 Liquid-Gas Interactions 223
(and the Entropy Fix) . . . . . . . . . . . . . . . 159
20.1 Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
14.4 Multiple Spatial Dimensions . . . . . . . . . . . . . . . . 160
20.2 Treating the Interface . . . . . . . . . . . . . . . . . . . . 224
14.5 Systems of Conservation Laws . . . . . . . . . . . . . . . 160
14.5.1 The Eigensystem . . . . . . . . . . . . . . . . . . 161
21 Two-Phase Incompressible Flow 227
14.5.2 Discretization . . . . . . . . . . . . . . . . . . . . 162
21.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 227
14.6 Compressible Flow Equations . . . . . . . . . . . . . . . 163
21.2 Jump Conditions . . . . . . . . . . . . . . . . . . . . . . 230
14.6.1 Ideal Gas Equation of State . . . . . . . . . . . . 164
21.3 Viscous Terms . . . . . . . . . . . . . . . . . . . . . . . . 232
14.6.2 Eigensystem . . . . . . . . . . . . . . . . . . . . . 164
21.4 Poisson Equation . . . . . . . . . . . . . . . . . . . . . . 235
14.6.3 Numerical Approach . . . . . . . . . . . . . . . . 165
Contents xiii

22 Low-Speed Flames 239
22.1 Reacting Interfaces . . . . . . . . . . . . . . . . . . . . . 239
22.2 Governing Equations . . . . . . . . . . . . . . . . . . . . 240
Part I
22.3 Treating the Jump Conditions . . . . . . . . . . . . . . . 241

23 Heat Flow 249
Implicit Surfaces
23.1 Heat Equation . . . . . . . . . . . . . . . . . . . . . . . . 249
23.2 Irregular Domains . . . . . . . . . . . . . . . . . . . . . . 250
23.3 Poisson Equation . . . . . . . . . . . . . . . . . . . . . . 251
23.4 Stefan Problems . . . . . . . . . . . . . . . . . . . . . . . 254

References 259
In the next two chapters we introduce implicit surfaces and illustrate a
Index 271 number of useful properties, focusing on those that will be of use to us
later in the text. A good general review can be found in [16]. In the ¬rst
chapter we discuss those properties that are true for a general implicit
representation. In the second chapter we introduce the notion of a signed
distance function with a Euclidean distance metric and a “±” sign used to
indicate the inside and outside of the surface.
4 1. Implicit Functions


φ = x2 ’ 1


1
Implicit Functions „¦+ „¦’ „¦+
φ >0 φ <0 φ >0
x
outside inside outside

‚„¦ ‚„¦
φ =0 φ =0
interface
interface


Figure 1.1. Implicit function φ(x) = x2 ’ 1 de¬ning the regions „¦’ and „¦+ as
well as the boundary ‚„¦


wasteful, since the implicit function φ(x) is de¬ned on all of n , while the
1.1 Points
interface has only dimension n ’ 1. However, we will see that a number of
very powerful tools are readily available when we use this representation.
In one spatial dimension, suppose we divide the real line into three distinct
Above, we chose the φ(x) = 0 isocontour to represent the lower-
pieces using the points x = ’1 and x = 1. That is, we de¬ne (’∞, ’1),
dimensional interface, but there is nothing special about the zero
(’1, 1), and (1, ∞) as three separate subdomains of interest, although we
ˆ ˆ
isocontour. For example, the φ(x) = 1 isocontour of φ(x) = x2 , de¬nes
regard the ¬rst and third as two disjoint pieces of the same region. We refer
ˆ
to „¦’ = (’1, 1) as the inside portion of the domain and „¦+ = (’∞, ’1) ∪ the same interface, ‚„¦ = {’1, 1}. In general, for any function φ(x) and
ˆ
(1, ∞) as the outside portion of the domain. The border between the inside an arbitrary isocontour φ(x) = a for some scalar a ∈ , we can de¬ne
ˆ
and the outside consists of the two points ‚„¦ = {’1, 1} and is called φ(x) = φ(x) ’ a, so that the φ(x) = 0 isocontour of φ is identical to the
ˆ ˆ ˆ
the interface. In one spatial dimension, the inside and outside regions are φ(x) = a isocontour of φ. In addition, the functions φ and φ have identical
one-dimensional objects, while the interface is less than one-dimensional. properties up to a scalar translation a. Moreover, the partial derivatives
ˆ
In fact, the points making up the interface are zero-dimensional. More of φ are the same as the partial derivatives of φ, since the scalar vanishes
generally, in n , subdomains are n-dimensional, while the interface has upon di¬erentiation. Thus, throughout the text all of our implicit functions
dimension n ’ 1. We say that the interface has codimension one. φ(x) will be de¬ned so that the φ(x) = 0 isocontour represents the interface
In an explicit interface representation one explicitly writes down the (unless otherwise speci¬ed).
points that belong to the interface as we did above when de¬ning ‚„¦ =
{’1, 1}. Alternatively, an implicit interface representation de¬nes the inter-
face as the isocontour of some function. For example, the zero isocontour
1.2 Curves
of φ(x) = x2 ’ 1 is the set of all points where φ(x) = 0; i.e., it is ex-
actly ‚„¦ = {’1, 1}. This is shown in Figure 1.1. Note that the implicit
In two spatial dimensions, our lower-dimensional interface is a curve that
function φ(x) is de¬ned throughout the one-dimensional domain, while the
separates 2 into separate subdomains with nonzero areas. Here we are
isocontour de¬ning the interface is one dimension lower. More generally,
limiting our interface curves to those that are closed, so that they have
in n , the implicit function φ(x) is de¬ned on all x ∈ n , and its isocon-
clearly de¬ned interior and exterior regions. As an example, consider φ(x) =
tour has dimension n ’ 1. Initially, the implicit representation might seem
1.2. Curves 5 6 1. Implicit Functions

y interval [so , sf ], one needs to resolve a two-dimensional region D. More
generally, in n , a discretization of an explicit representation needs to re-
solve only an (n ’ 1)-dimensional set, while a discretization of an implicit
representation needs to resolve an n-dimensional set. This can be avoided,
in part, by placing all the points x very close to the interface, leaving the
„¦’ „¦+ rest of D unresolved. Since only the φ(x) = 0 isocontour is important, only
φ <0 φ >0 the points x near this isocontour are actually needed to accurately repre-
sent the interface. The rest of D is unimportant. Clustering points near the
inside outside interface is a local approach to discretizing implicit representations. (We
x
will give more details about local approaches later.) Once we have chosen
the set of points that make up our discretization, we store the values of the
implicit function φ(x) at each of these points.
Neither the explicit nor the implicit discretization tells us where the in-
‚„¦
terface is located. Instead, they both give information at sample locations.
φ = x + y2 ’ 1 = 0
2
In the explicit representation, we know the location of a ¬nite set of points
interface on the curve, but do not know the location of the remaining in¬nite set
of points (on the curve). Usually, interpolation is used to approximate the
location of points not represented in the discretization. For example, piece-
Figure 1.2. Implicit representation of the curve x2 + y 2 = 1.
wise polynomial interpolation can be used to determine the shape of the
interface between the data points. Splines are usually appropriate for this.
x2 + y 2 ’ 1, where the interface de¬ned by the φ(x) = 0 isocontour is the Similarly, in the implicit representation we know the values of the implicit
unit circle de¬ned by ‚„¦ = {x | |x| = 1}. The interior region is the unit function φ at only a ¬nite number of points and need to use interpolation
open disk „¦’ = {x | |x| < 1}, and the exterior region is „¦+ = {x | |x| > 1}. to ¬nd the values of φ elsewhere. Even worse, here we may not know the
These regions are depicted in Figure 1.2. The explicit representation of this location of any of the points on the interface, unless we have luckily cho-
interface is simply the unit circle de¬ned by ‚„¦ = {x | |x| = 1}. sen data points x where φ(x) is exactly equal to zero. In order to locate
In two spatial dimensions, the explicit interface de¬nition needs to spec- the interface, the φ(x) = 0 isocontour needs to be interpolated from the
ify all the points on a curve. While in this case it is easy to do, it can be known values of φ at the data points. This is a rather standard procedure
somewhat more di¬cult for general curves. In general, one needs to param- accomplished by a variety of contour plotting routines.
eterize the curve with a vector function x(s), where the parameter s is in The set of data points where the implicit function φ is de¬ned is called
[so , sf ]. The condition that the curve be closed implies that x(so ) = x(sf ). a grid. There are many ways of choosing the points in a grid, and these
While it is convenient to use analytical descriptions as we have done lead to a number of di¬erent types of grids, e.g., unstructured, adaptive,
so far, complicated two-dimensional curves do not generally have such curvilinear. By far, the most popular grids, are Cartesian grids de¬ned as
{(xi , yj ) | 1 ¤ i ¤ m, 1 ¤ j ¤ n}. The natural orderings of the xi and yj
simple representations. A convenient way of approximating an explicit
are usually used for convenience. That is, x1 < · · · < xi’1 < xi < xi+1 <
representation is to discretize the parameter s into a ¬nite set of points
so < · · · < si’1 < si < si+1 < · · · < sf , where the subintervals [si , si+1 ] · · · < xm and y1 < · · · < yj’1 < yj < yj+1 < · · · < yn . In a uniform
are not necessarily of equal size. For each point si in parameter space, Cartesian grid, all the subintervals [xi , xi+1 ] are equal in size, and we set
x = xi+1 ’ xi . Likewise, all the subintervals [yj , yj+1 ] are equal in size,
we then store the corresponding two-dimensional location of the curve de-
and we set y = yj+1 ’ yj . Furthermore, it is usually convenient to choose
noted by x(si ). As the number of points in the discretized parameter space
is increased, so is the resolution (detail) of the two-dimensional curve. x = y so that the approximation errors are the same in the x-direction
The implicit representation can be stored with a discretization as well, as they are in the y-direction. By de¬nition, Cartesian grids imply the use
except now one needs to discretize all of 2 , which is impractical, since it is of a rectangular domain D = [x1 , xm ] — [y1 , yn ]. Again, since φ is important
unbounded. Instead, we discretize a bounded subdomain D ‚ 2 . Within only near the interface, a local approach would indicate that many of the
this domain, we choose a ¬nite set of points (xi , yi ) for i = 1, . . . , N to dis- grid points are not needed, and the implicit representation can be optimized
cretely approximate the implicit function φ. This illustrates a drawback of by storing only a subset of a uniform Cartesian grid. The Cartesian grid
the implicit surface representation. Instead of resolving a one-dimensional points that are not su¬ciently near the interface can be discarded.
1.3. Surfaces 7 8 1. Implicit Functions

We pause for a moment to consider the discretization of the one- surgery” needed for merging and pinching is much more complex, leading
dimensional problem. There, since the explicit representation is merely a to a number of di¬culties including, for example, holes in the surface.
set of points, it is trivial to record the exact interface position, and no One of the nicest properties of implicit surfaces is that connectivity does
discretization or parameterization is needed. However, the implicit repre- not need to be determined for the discretization. A uniform Cartesian grid
{(xi , yj , zk ) | 1 ¤ i ¤ m, 1 ¤ j ¤ n, 1 ¤ k ¤ p} can be used along
sentation must be discretized if φ is not a known analytic function. A typical
discretization consists of a set of points x1 < · · · < xi’1 < xi < xi+1 < with straightforward generalizations of the technology from two spatial
· · · < xm on a subdomain D = [x1 , xm ] of . Again, it is usually useful to dimensions. Possibly the most powerful aspect of implicit surfaces is that
use a uniform grid, and only the grid points near the interface need to be it is straightforward to go from two spatial dimensions to three spatial
stored. dimensions (or even more).



1.3 Surfaces 1.4 Geometry Toolbox
In three spatial dimensions the lower-dimensional interface is a surface Implicit interface representations include some very powerful geometric
that separates 3 into separate subdomains with nonzero volumes. Again, tools. For example, since we have designated the φ(x) = 0 isocontour as
we consider only closed surfaces with clearly de¬ned interior and exterior the interface, we can determine which side of the interface a point is on
regions. As an example, consider φ(x) = x2 +y 2 +z 2 ’1, where the interface simply by looking at the local sign of φ. That is, xo is inside the interface
is de¬ned by the φ(x) = 0 isocontour, which is the boundary of the unit when φ(xo ) < 0, outside the interface when φ(xo ) > 0, and on the interface
sphere de¬ned as ‚„¦ = {x | |x| = 1}. The interior region is the open unit when φ(xo ) = 0. With an explicit representation of the interface it can be
sphere „¦’ = {x | |x| < 1}, and the exterior region is „¦+ = {x | |x| > 1}. di¬cult to determine whether a point is inside or outside the interface. A
The explicit representation of the interface is ‚„¦ = {x | |x| = 1}. standard procedure for doing this is to cast a ray from the point in question
For complicated surfaces with no analytic representation, we again need to some far-o¬ place that is known to be outside the interface. Then if the
to use a discretization. In three spatial dimensions the explicit represen- ray intersects the interface an even number of times, the point is outside
tation can be quite di¬cult to discretize. One needs to choose a number the interface. Otherwise, the ray intersects the interface an odd number of
of points on the two-dimensional surface and record their connectivity. In times, and the point is inside the interface. Obviously, it is more convenient
two spatial dimensions, connectivity was determined based on the ordering, simply to evaluate φ at the point xo . In the discrete case, i.e., when the
i.e., x(si ) is connected to x(si’1 ) and x(si+1 ). In three spatial dimensions implicit function is given by its values at a ¬nite number of data points,
connectivity is less straightforward. If the exact surface and its connectivity interpolation can be used to estimate φ(xo ) using the values of φ at the
are known, it is simple to tile the surface with triangles whose vertices lie known sample points. For example, on our Cartesian grid, linear, bilin-
on the interface and whose edges indicate connectivity. On the other hand, ear, and trilinear interpolation can be used in one, two, and three spatial
if connectivity is not known, it can be quite di¬cult to determine, and even dimensions, respectively.
some of the most popular algorithms can produce surprisingly inaccurate Numerical interpolation produces errors in the estimate of φ. This can
surface representations, e.g., surfaces with holes. lead to erroneously designating inside points as outside points and vice
Connectivity can change for dynamic implicit surfaces, i.e., surfaces that versa. At ¬rst glance these errors might seem disastrous, but in reality
are moving around. As an example, consider the splashing water surface they amount to perturbing (or moving) the interface away from its exact
in a swimming pool full of children. Here, connectivity is not a “one-time” position. If these interface perturbations are small, their e¬ects may be mi-
issue dealt with in constructing an explicit representation of the surface. nor, and a perturbed interface might be acceptable. In fact, most numerical
Instead, it must be resolved over and over again every time pieces of the methods depend on the fact that the results are stable in the presence of
surface merge together or pinch apart. In two spatial dimensions the task small perturbations. If this is not true, then the problem under consider-
is more manageable, since merging can be accomplished by taking two ation is probably ill-posed, and numerical methods should be used only
one-dimensional parameterizations, si and si , and combining them into a
ˆ with extreme caution (and suspicion). These interface perturbation errors
single one-dimensional parameterization. Pinching apart is accomplished by decrease as the number of sample points increases, implying that the exact
splitting a single one-dimensional parameterization into two separate one- answer could hypothetically be computed as the number of sample points
dimensional parameterizations. In three spatial dimensions the “interface is increased to in¬nity. Again, this is the basis for most numerical methods.
1.4. Geometry Toolbox 9 10 1. Implicit Functions

y
While one cannot increase the number of grid points to in¬nity, desirable
solutions can be obtained for many problems with a practical number of
grid points. Throughout the text we will make a number of numerical ap-
N
proximations with errors proportional to the size of a Cartesian mesh cell,
N
i.e., x (or ( x)r ). If the implicit function is smooth enough and well
N N
resolved by the grid, these estimates will be appropriate. Otherwise, these
N

 1
( 23)



. . >>

Copyright Design by: Sunlight webdesign