LINEBURG

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

Copyright Design by: Sunlight webdesign