Font size

DOE'ERy03077-265

o

ITi

VÂ£>

CM

I

C -

C -

o

CO

o

\

w

w

o

Q

CO

(D

e

â€¢-3

o

6

C

o

â– H

+^

CO

a

S

o

o

Courant Mathematics and

Computing Laboratory

U.S. Department of Energy

A Computational Model for Interfaces

J. Glimm and O. A. McBryan

Research and Development Report

Supported by the Applied Mathematical Sciences

subprogram of the Office of Energy Research,

U.S. Department of Energy under

Contract DE-AC02-76ER03077

3 < Mathematics and Computers

lune 1985

NEW YORK UNIVERSITY

UNCLASSIFIED

Mathematics and Computers

c\1^ UC-3.

^ v&V^'^^^ ,> DOE/ER/03077-26:

^6tâ€¢ 3. â€¢â™¦. 5

Departmeat of Mathematics

Courant Institute

New York University

New York, NY 10012.

ABSTRACT

Decompositions of the plane into disjoint components

separated by airves occur frequently. We describe a package of

subroutines which provides facilities for defining, building and

modifying such decompositions and for efficiently solving vari-

ous point and area location'"|:flrbblei!fs."'"' " '""^

Beyond the point that the specification of this package may

be useful to others, we reach the broader conclusion that well

::c: 03 ,s:;~s-:;i.-.^;:' ... ^;:.

designed data structures and support routines allow the use of

more conceptual or non-numencal portions BONDS for a given block, then the

COMPONENT is uniquely defined, ^d; isvalso stored with the precomputed

data. This same data is used by the routine intersections for efficiency rea-

sons.

While this particular pre-processing mechanism appears adequate for

many problems, it is not optimal, either in computation time or storage

space. It is not difficult to replace the current code for component with other

pre-processing schemes. A crude point location algorithm is easily devised

based on comparison of location relative to all n BONDS of an INTERFACE,

and requires 0{n) computation time, but no pre-processing or extra storage.

The algorithm described here consumes 0{n) + 0{g~) storage and pre-

processing time when the superimposed grid has dimensions g by g. How-

ever the point location computation cost is then effectively 0(1) in n for typi-

cal interfaces we have encountered, although the worst case computation time

is still 0{n) - corresponding to the case where the complete interface is con-

tained in a single grid rectangle. For a review of the point location problem

and related areas in computational geometry we refer to several recent papers

- 10 r

in the computer science literature.^-''^'*'^^'^^ Future versions of this software

may well incorporate other approaches to point location. It is important to

stress that what is required is algorithms with good behavior on normal inter-

faces, even if their worst-case behavior is poor (eg close to linear).

6. INTERFACES IN HIGHER SPACE DIMENSIONS

Based on our experience with planar interfaces, we make here several

comments on the problem of defining data structures and support routines

for interfaces in higher space dimensions. We adopt the point of view of

computational continuum mechanics, where the interfaces designate material

boundaries, phase boundaries or discontinuous waves, but there are a number

of other and unrelated applications such as graphics for these ideas. An inter-

face in R" will consist of a number of smooth surfaces and their boundaries,

boundaries of boundaries etc. The smooth surfaces will in general have an

arbitrary topology, so that they cannot be parameterized by an open subset of

R^ or in other terminology, by a sfe^fii^ cobrdiiiate chart. The surfaces of

dimension j will in general share s6me ""common boundaries of dimension

;' - 1. Thus the data structure for a numerical description of an interface

will consist of a list of smooth surfaces of various diincnsions together with a

list of boundary relations among these surfaces. Each surface of dimension j

should include a pointer to the surfaces of dimension j + I which it bounds

and to the surfaces of dimension y â€” 1 in its boundary together with the rela-

tive orientation of these surfaces. We note that the boundary of an interface

of highest dimension j is an interface of highest dimension j - 1, so that for

the case n = 3, ; = 2, the boundaries are given by the data structures defined

in this paper, with the simple addition of an extra real variable z to the POEnT

data structure.

There are three requirements which determine the data structure for the

description of a single smooth surface in an interface. A small perturbation of

the points (such as would occur in a single time step of a time dependent evo-

lution) should not require a rrparameterization of the surface. Reparameteri-

zation, when required, should be a local operation and the local reparameteri-

o

ITi

VÂ£>

CM

I

C -

C -

o

CO

o

\

w

w

o

Q

CO

(D

e

â€¢-3

o

6

C

o

â– H

+^

CO

a

S

o

o

Courant Mathematics and

Computing Laboratory

U.S. Department of Energy

A Computational Model for Interfaces

J. Glimm and O. A. McBryan

Research and Development Report

Supported by the Applied Mathematical Sciences

subprogram of the Office of Energy Research,

U.S. Department of Energy under

Contract DE-AC02-76ER03077

3 < Mathematics and Computers

lune 1985

NEW YORK UNIVERSITY

UNCLASSIFIED

Mathematics and Computers

c\1^ UC-3.

^ v&V^'^^^ ,> DOE/ER/03077-26:

^6tâ€¢ 3. â€¢â™¦. 5

Departmeat of Mathematics

Courant Institute

New York University

New York, NY 10012.

ABSTRACT

Decompositions of the plane into disjoint components

separated by airves occur frequently. We describe a package of

subroutines which provides facilities for defining, building and

modifying such decompositions and for efficiently solving vari-

ous point and area location'"|:flrbblei!fs."'"' " '""^

Beyond the point that the specification of this package may

be useful to others, we reach the broader conclusion that well

::c: 03 ,s:;~s-:;i.-.^;:' ... ^;:.

designed data structures and support routines allow the use of

more conceptual or non-numencal portions BONDS for a given block, then the

COMPONENT is uniquely defined, ^d; isvalso stored with the precomputed

data. This same data is used by the routine intersections for efficiency rea-

sons.

While this particular pre-processing mechanism appears adequate for

many problems, it is not optimal, either in computation time or storage

space. It is not difficult to replace the current code for component with other

pre-processing schemes. A crude point location algorithm is easily devised

based on comparison of location relative to all n BONDS of an INTERFACE,

and requires 0{n) computation time, but no pre-processing or extra storage.

The algorithm described here consumes 0{n) + 0{g~) storage and pre-

processing time when the superimposed grid has dimensions g by g. How-

ever the point location computation cost is then effectively 0(1) in n for typi-

cal interfaces we have encountered, although the worst case computation time

is still 0{n) - corresponding to the case where the complete interface is con-

tained in a single grid rectangle. For a review of the point location problem

and related areas in computational geometry we refer to several recent papers

- 10 r

in the computer science literature.^-''^'*'^^'^^ Future versions of this software

may well incorporate other approaches to point location. It is important to

stress that what is required is algorithms with good behavior on normal inter-

faces, even if their worst-case behavior is poor (eg close to linear).

6. INTERFACES IN HIGHER SPACE DIMENSIONS

Based on our experience with planar interfaces, we make here several

comments on the problem of defining data structures and support routines

for interfaces in higher space dimensions. We adopt the point of view of

computational continuum mechanics, where the interfaces designate material

boundaries, phase boundaries or discontinuous waves, but there are a number

of other and unrelated applications such as graphics for these ideas. An inter-

face in R" will consist of a number of smooth surfaces and their boundaries,

boundaries of boundaries etc. The smooth surfaces will in general have an

arbitrary topology, so that they cannot be parameterized by an open subset of

R^ or in other terminology, by a sfe^fii^ cobrdiiiate chart. The surfaces of

dimension j will in general share s6me ""common boundaries of dimension

;' - 1. Thus the data structure for a numerical description of an interface

will consist of a list of smooth surfaces of various diincnsions together with a

list of boundary relations among these surfaces. Each surface of dimension j

should include a pointer to the surfaces of dimension j + I which it bounds

and to the surfaces of dimension y â€” 1 in its boundary together with the rela-

tive orientation of these surfaces. We note that the boundary of an interface

of highest dimension j is an interface of highest dimension j - 1, so that for

the case n = 3, ; = 2, the boundaries are given by the data structures defined

in this paper, with the simple addition of an extra real variable z to the POEnT

data structure.

There are three requirements which determine the data structure for the

description of a single smooth surface in an interface. A small perturbation of

the points (such as would occur in a single time step of a time dependent evo-

lution) should not require a rrparameterization of the surface. Reparameteri-

zation, when required, should be a local operation and the local reparameteri-

1 2