Jean-Laurent Mallet. Geomodeling
Подождите немного. Документ загружается.
128
CHAPTER
3.
TESSELLATIONS
Figure
3.21
Building
a
Coons
patch with
linear
weighting
functions:
the
resulting
surface
is the sum of two
linear
interpolations
of
pairs
of
curves
minus
a
bilinear
interpolation
of the
four
vertices.
In
conclusion,
a
better
approximation
U[
i+1
]
of the
parameter
u
corresponding
to the
location
p can be
obtained
thus:
In
practice, this updating
formula
provides
the
basis
of an
iterative algorithm.
Barycentric
interpolation
inside
a
cell
In the
case
of a
corner point model,
a
frequent problem arises where
a pa-
rameter
(p
known
by its
values
(p(oi)
at the
vertices
of a
regular
n-grid
has to
be
continuously interpolated
in
each
n-cell
of
this grid.
For
this purpose,
the
following
interpolation
<£>(u),
similar
to
equation (3.14) used
for
modeling
the
geometry
of the
cell,
is
proposed:
It can
easily
be
verified
that
the
function
<^(u)
so
defined
interpolates
the
values
of
(p
at the
vertices
of the
cell
and
varies linearly
on
each edge
of
that
cell.
It
should
be
noted
that
local nonlinear interpolations
can be
defined
in
each
n-cell. However,
in
such
a
case, these interpolations involve
not
only
the
vertices
of the
cells
but
also
the
vertices
of the
adjacent cell
(e.g.,
see
[146]).
3.4.4
Geometry
of a
regular
n-grid
As
can be
imagined,
the
geometry
of
regular
n-grids
can
easily
be
adjusted
thanks
to
DSI
to fit
geological objects. However,
in
general,
before
using
DSI
we
need
to
have
a
rough approximation
of the
shape
of
these grids,
and
the
notion
of
"Coons
patch"
is
certainly
the
simplest
way of
building such
approximations.
3.4.
NOTION
OF A
REGULAR
N-GRID
129
Coons
patch
This section addresses
the
problem
of
building
a
piece
of
surface rectangu-
lar in
shape
whose boundary
consists
of two
opposite
pairs
of
open curves
{x(u|0),x(u|l)}
and
{x(0|u),x(l|u)}:
As
shown
in
figure
(3.21),
the
solution initially proposed
by
Coons
and
gen-
eralized
by
Gordon consists
of a
parametric surface
x(w,
v)
defined
by the
following
equation
for any
u
G
[0,1]
and any v 6
[0,1]:
(3.17)
It is
easy
to
check
that
x(u,
v)
does interpolate
the
four
boundary curves
provided
that
the
associated blending
functions
{/o,
fi,go,gi}
are
such
that
Among
the
many possible choices
for
these blending
functions,
those most
often
used
are the
following:
•
linear blending functions:
•
cubic Hermit blending functions:
The
Coons surfaces
so
denned,
also called "Coons patches,"
are
very simple
to
implement
and are
extremely useful
in
situations
where
the
surface
to be
modeled
is
actually known only
by its
boundary. However,
it is
important
to
note
that
there
is no
possible control
on the
shape
of the
interior
of the
patch
-
this
is the
major drawback
of
Coons surfaces.
Construction
of a
regular
n-grid
Let
us
consider
the set of
points
(ui,Vj)
belonging
to
[0,1]
x
[0,1]
and
such
that
130
Using
equation (3.17)
for
computing
the
images
x(wj,
Vj]
of
these points,
it can
be
observed
that
these
images
are
distributed
on a
regular 2-grid
GN
1
N
2
'-
this
shows
that
Coons patches provide
an
easy
way for
initializing
the
geometry
of
regular
2-grids
as
soon
as the
boundary curves
are
known.
In
practice,
for n
=
(1,2,3),
the
construction
of an
initial shape
for a
regular
n-grid
can be
viewed
as a
recursive process
that
can be
sketched
as
follows:
•
First,
regular
1-grids
can be
initialized
as
nodes regularly spaced
on a
segment.
•
Next, regular 2-grids
can be
initialized
as the
nodes
of a
discrete Coons
patch.
•
Finally,
a
regular 3-grid
can be
viewed
as
being composed
of two
entities:
—
two
regular
2-grids
corresponding
to the top and
bottom
surfaces
bound-
aries
initialized
with
Coons patches,
and
—
internal
nodes
initialized
as
regular
1-grids
joining
twin
nodes
on the top
and
bottom
boundaries.
3.4.5 Cracking a regular n-grid
Introducing cracks
in a
regular n-grid
is a
handy
way to
define
discontinuities
of
the
embedding across
(n
—
l)-cells
of a
regular n-grid.
In
geology,
the
need
to
introduce such cracks occurs
in the two
following
situations:
• If the
geometrical
embedding
x(u)
of a
regular
2-grid
corresponds
to a
geo-
logical
surface
cut by a
fault
along
a
curve
J-,
then
we may
want
to
install
cracks
approximating
the
trace
of
T
on
this
surface.
• If the
geometrical
embedding
x(u)
of a
regular
3-grid
corresponds
to a
geo-
logical
layer
cut by a
fault
along
a
surface
J-",
then
we may
want
to
install
cracks
approximating
T
(see
figure
(3.17)).
In
practice,
in the
parametric space,
the
image
x^
1
(^
7
)
is
approximated
by a
set of (n
—
l)-cells
where
the
cracks need
to be
installed.
Of
course,
this
is
not
without consequences:
• If we
want
to
preserve
the
regularity
of the
shape
of the
images
x(t/fe
1
...*:„)
in
the
embedding
space,
then,
in
general,
the
geometry
of the
image
of the
cracks
poorly
approximate
f.
• If we
want
the
images
of the
crack
to fit
F
correctly,
then,
in
general,
we
cannot
preserve
the
regularity
of the
shape
of the
images
x(C/fc
1
...fc
n
).
From
a
topological point
of
view,
each crack must
be
implemented
as an
"unsew"
operation
on the
corresponding
(n—
l)-cell
of the
n-Gmap
associated
with
the
n-grid.
CHAPTER 3. TESSELLATIONS
3.4.
NOTION
OF A
REGULAR
N-GRID
131
Simple
nodes
and
split nodes
of a
regular
n-grid
Le t
{ufc
1
...fc
n
}
be the set of
vertices
11
of the
unit parametric squares
in the
parametric d omain
The
images
{x(ufc
1
.../
Cn
)}
of the
vertices
so
defined
are the
vertices
of the n-
cells
Cki...k
n
of the
associated regular n-grid
GN
v
...N
n
-
As
suggested
in figure
(3.19),
there
are two
cases
to
consider:
• If
there
is no
crack
incident
to a
vertex
\ik
l
...k
n
,
then
its
image
x(ufc
1
...fe
n
)
is
unique
and is
called
a
"simple node"
of the
regular
n-grid
GNi...N
n
-
• If
there
is a
crack
incident
to a
vertex
Ufc
1
...fc
n
,
then
it has
several
images
{xj(uk
l
...k
n
)
'•
J'
= 1,
2,...},
and
this
set of
images
is
called
a
"split
node"
of
the
regular
n-grid
GjVi.../v
n
-
It is
easily
verifiable
that
the
maximum
number
of
images
{x
J
-(ufc
1
...fc
Tl
)
: j = 1,
2,...}
corresponding
to
such
a
split
node
is
equal
to
2
n
.
Obviously,
simple nodes have
one
unique location, while split nodes have
multiple locations corresponding
to the
images
{x
j
-(ufc
1
...fc
n
)
: j =
1,2,...}.
In
the
case
of a
"corner point" model,
we
have
to
consider
two
strategies
concerning physical properties attached
to a
split node
{x
j
(ufc
1
k } '• j —
1,2,...}:
• If the
physical
property
(po
to be
modeled
at the set fio of
node
of
GNi...N
n
must
be
continuous across
the
cracks,
then
all the
vertices
{xj(ufc
1
...fc
n
)
:
j =
1,2,...}
associated
with
one
split
node
must
share
one
unique
storage
for
this
physical
property.
Moreover,
in
this
case,
the
neighborhoods
NQ(-)
of the
associated
discrete
model
A4
p
(f2o,
NO,
</?o,
C^
0
)
must
ignore
the
discontinuities.
• If the
physical
property
<po
to be
modeled
at the set
QO
of
node
of
GN±...N
n
must
be
discontinuous
across
the
cracks,
then each vertex
{x
J
(u
/
i
ei
...fc
Tl
)
: j =
1,2,...}
associated
with
one
split
node
must
have
independent
storages
for
this
physical
property.
Moreover,
in
this
case,
the
neighborhoods
NQ(-)
of the
associated
discrete
model
A1
p
(fio,
NO,
</?o,C<p
0
)
must respect
the
discontinu-
ities.
Cutting
a
regular
n-grid
As
mentioned above,
in a
regular n-grid,
the
regularity
of the
geometry
of
n-cells
is, in
general, incompatible with
a
good geometrical approximation
of
the
discontinuities
by
cracked
(n
—
l)-cells.
Everything
has its
price. There
is a
price
to pay to
preserve
the
regularity
of
the
geometry
of the
n-cells
and
reach
a
good
geometrical
approximation
of
the
discontinuities.
In
practice,
a
reasonable price
may be to
accept
the
existence
of
polyhedral "cut cells," which
no
longer have
a
cubic topology.
As
shown
in figure
(3.22),
such polyhedral cells
offer
a
higher
flexibility for
modeling faulted geological layers.
11
These
vertices
are
represented
as
black
nodes
in
figure
(3.19).
0m
132
Figure
3.22
An
example
of an
irregular
3-grid
composed
of
polyhedral
3-cells
cut by
geological
faults:
(A) The
initial
regular
3-grid
cut by
faults
and
horizons.
(B)
The
exploded
view
of the
result
of the
cut.
3.5
Notion
of an
irregular
n-grid
The
notion
of the
regular
n-grid
introduced
in the
previous section
is a
very
practical tool
for
modeling geological stratified layers
as
long
as
there
is no
discontinuity
to be
taken into account. However,
if we
have
to
introduce
discontinuities, then
we
have already seen
that
it is
generally
not
possible
to
control both
the
shape
of the
cells
and the
shape
of the
discontinuities.
For
this reason,
a
generalization allowing more
flexibility
will
be
introduced
briefly
in
this section:
Definition
Let
A be a
closed polygonal region
of
M
n
and let
P(A)
be a
cellular partition
of
A
honoring
the
following
constraint:
Such
a
partition
is
called
a
polyhedral partition
of A and can be
viewed
as a
generalization
of the
notion
of
"regular n-grid" presented
in
section (3.4).
For
this reason,
we
propose calling "irregular n-grid"
any
partition
of A
honoring
the
constraint
(3.19).
Most
of the
time
in
geological applications
n
— 3:
figures
(3.22),
and
(3.23)
give
examples
of
such irregular
3-grids.
Comments
1.
As
with regular n-grids, irregular n-grids
can be
associated
with
a
para-
metric domain
in the
IR
n
parametric space. However,
in
this parametric
space,
the
unit square cells must
now be
replaced
by
polyhedral cells
whose vertices
{ufc}
are not
mandatorily
distributed
at the
nodes
of a
regular lattice.
2.
Any
regular n-grid
is,
implicitly,
an
irregular n-grid,
and
this
is an
easy
way
to
build
an
initial version
of
irregular n-grids.
CHAPTER 3. TESSELLATIONS
3.5.
NOTION
OF AN
IRREGULAR
N-GRID
133
Figure
3.23
An
example
of
an
irregular
3-grid
generated
by
extrusion
of
a 2D
subdivision
of
a
faulted
surface
(curvilinear
pseudo-Voronoi
subdivision).
3.
Contrary
to the
case
of
regular
n-grids,
the
topology
of the
cells
of an
irregular
n-grid
can be
edited,
and
this
offers
much more
flexibility; for
example,
• the
cells
of an
irregular
n-grid
can be
split
into
subcells,
and
• the
cells
of an
irregular
n-grid
can be
merged
into
macro
cells,
Notion
of a
hybrid
n-grid
An
excellent compromise between regularity
and flexibility
consists
in
using
hybrid
n-grids
defined
as
regular
n-grids
with
two
types
of
n-cells:
•
"simple n-cells,"
which
are
identical
to
regular n-cells
of the
grid,
and
•
"split
n-cells"
corresponding
to
"virtual"
regular
n-cells
that
have
been
re-
placed
by a
cellular
partition,
itself
modeled
as an
irregular
n-grid.
In
general,
one
needs
few
split cells,
so
that
hybrid n-grids
so
defined
can
be
considered
as
regular
"almost"
everywhere.
In
practice,
split n-cells
may
correspond
to
intersections
of a
regular n-grid with faults
or
well-paths.
Cutting
an
irregular
n-grid
Let
J-
be an (n
—
1)-dimensional
object
12
cutting
an
irregular n-grid assumed
to
introduce discontinuities
in the
topology
of
this
grid.
In
practice,
these
discontinuities
are
introduced
by
splitting
the
n-cells
of the
grid along
F.
Such
a
cutting operation
can be
realized
as
follows:
1.
Determine
the (n
—
l)-dimensional
trace
r(
J
4|^
r
)
of the
discontinuity
T
on the
object
A
corresponding
to the
n-grid.
2
In
geology,
n = 3, and
f
is
generally
a
fault
or an
unconformity.
134
CHAPTERS.
2.
Split
the
n-cells
of the
grid
intersected
by
F(A|J-)
in
such
a way
that
the new
(n
—
l)-cells
so
generated
fit the
trace
r(A|J
r
).
3.
Unsew
(see
page
78) the (n
—
l)-cells
generated
at
step
(2)
above.
Proceeding
in
this
way
preserves
both
the
geometry
and
topology
of the
n-cells
not cut by
T(A\
J"),
while honoring
the
geometry
of
?'.
3.6
Implicit
surfaces
Introduction
Up
to now in
this
book, only surfaces
that
can be
represented
by an
explicit
local parametric equation
x(u,
v)
have been considered. There
is,
however,
another very important class
of
surfaces
<S
a
called "implicit surfaces"
[28],
denned
as
follows
by a
global
implicit
equation:
In
this equation,
v?
a
(
x
)
is
assumed
to be a
real valued
function
of x
e
D
defined
in a
region
D of
7R
3
and
having
a
gradient such
that
The
above condition (3.21) implies
that
the set
S
a
denned
by
equation
(3.20)
is,
in
actual
fact,
a
surface (and
not a
volume)
fully
contained
in the
region
D.
Most
of the
time,
the
constraint (3.21)
is
replaced
by the
following
stronger
constraint
and,
in
this
case,
</
?
a(
x
)
is
called
a
"normal-form"
of the
implicit
equation
of
S
a
'-
It is
important
to
note
that,
for any
point
x
located
in the
neighborhood
of
<S
a
,
the
normal-form
of an
implicit equation
of
S
a
represents
the
distance
of
x to
this surface.
It
should
be
noted
that
any
implicit
surface
S
a
associated with
an
implicit
equation
</?
a
(x)
(in
normal-form
or
not) divides
the
domain
of
definition
D
into
two
complementary regions
a and (D
—
a)
such
that
It is
clear
that
the
surface
S
a
is no
more
than
the
boundary
of the
region
a
so
denned:
In
this context, methods
for
performing Boolean operations analogous
to the
union
and
intersection
of
regions have been proposed.
For
example,
if a and b
are
regions
defined
by
implicit equations
(p
a
and
</?&,
then
the
implicit function
corresponding
to the
union
and
intersection
of
these regions
is
denned
as
follows:
tessellations
3.6.
IMPLICIT SURFACES
135
Figure
3.24
(A)
Intersection
of a
tetrahedron
by an
isovalue
surface.
(B)
Decomposition
of an
hexahedron
into
six
tetrahedra.
The
sign
of the
associated
function
<p
a
is
coded
by
"+"
and
"—"
symbols.
For
practical applications, most
of the
time implicit surfaces have
to be
trans-
formed
into explicit
triangulated
surfaces.
The
procedure
for
such
an
opera-
tion
will
be
explained
in the
next section.
Triangulating
an
implicit surface
In
practice,
the
function
<p
a
defining
the
boundary
S
a
of a
region
a is
assumed
to be
sampled
at the
nodes
of a 3D
discrete model approximating
the
domain
of
definition
D. Let us first
consider
the
case
where
the
discrete model
consists
of
a set of
tetrahedra
filling the
region
D, and let T =
T(p
0
,
p
1
,p
2
,p
3
)
be
one
such
tetrahedron.
It is
easy
to see
that
we
have:
If
T is
intersected
by
<S
a
,
then each
of its 6
edges
can be
intersected
or
not,
and
this generates exactly
2
6
different
cases. Nevertheless,
by
permuting
the
indices
of T, it can be
verified
that
only those
two
types
of
intersections shown
in
figure
(3.24)-A
need
in
fact
to be
considered:
•
either
three
edges
of T are
intersected,
and
then
S
a
H
T can be
approximated
by
a
triangle,
• or
four
edges
of T are
intersected,
and
then
<S
a
n T can be
approximated
by
two
adjacent
triangles.
Most
of the
time,
the
discrete models used
in
practical applications
are
based
on
regular 3-grids with hexahedral cells.
In
this case,
as
suggested
in figure
(3.24)-B,
each
hexahedron
can be
implicitely decomposed into
six
adjacent
tetrahedra
so
that
the
triangulation introduced above
is
still applicable.
It
should
be
noted, however,
that
triangulation algorithms derived
from
the
above observations generally produce "ugly" triangles,
and it is
mandatory
136
Figure
3.25
Example
of
implicit
surface
interpolating
an
unstructured
set of
points
{PJ}
where
the
unit
normal
vectors
{Ni}
are
estimated
from
local
average
tangent
planes.
(Data
courtesy
of
Unocal)
to
apply
a
"beautifying" algorithm
to
improve
the
"beauty"
of the
triangles
so
generated
(e.g.,
see
page 305).
On
the
right
of
figure
(3.25)
is an
example
of
such
a
triangulation
which
corresponds
to an
isovalue
surface
sampled
at the
nodes
of a
regular 3-grid.
The
Neanderthal skull
S
a
represented
in figure
(1.2)-A
is
another
example
of
an
implicit surface where
the
initial
data
correspond
to a
regular 3-grid
representing X-ray
"transparencies"
/(x)
generated
by a 3D
X-ray medical
scanner;
in
this
case,
the
surface
of the
skull corresponds
to a
given isovalue
/o of
this
transparency
implicit function
and
(p
a
is
defined
as
follows:
Interpolating
an
implicit surface
In
practical applications,
the
domain
of
definition
D is a 3D
hexahedral box,
and the
data
consist
of a
series
of
pairs
where
•
each
p^
is a
point
located
on the
implicit
surface
S
a
to be
interpolated;
•
each
Ni is the
unit
normal
vector
to
<S
a
,
at
location
p
i;
oriented
toward
the
interior
of the
region
a.
We
propose
to
interpolate
the
unknown
function
(f>
a
at the
nodes
of a
linear
regular 3-grid
filling
the
domain
D and
associated with
a
corner point discrete
model
A
/
(
1
(0,
TV,
(/p
0
,C^
a
).
For the
sake
of
simplicity
all the
3-cells
of the
grid
are
assumed
to be
cubic with
the
length
of
each edge equal
to 1. For
each
data
(p^,Ni),
the
following
pair
of
twin constraints
are
introduced:
CHAPTER 3. TESSELLATIONS
where
w
7
is the
normalized coordinate
of the
grid
in the
jth
direction while
N;?
is the
jth
component
of Ni in
this
coordinate system.
It
will
be
seen
in
section (4.7.2)
that
the
equations (3.23),
and
(3.24)
can be
transformed
into
the
so-called "Control-Property"
and
"Control-Gradient"
DSI
constraints
that
are
added
to
C
(fa
.
The
DSI
algorithm
can
then
be
used
for
interpolating
</?
a
at the
nodes
of the
grid:
figure
(3.25) shows
an
example
of
the
resulting implicit surface interpolating
an
unstructured
set of
points
p^
where
the
unit normal vectors
Nj
are
given.
It
should
be
noted
that
methods based
on
different
interpolation tech-
niques
have been proposed
in the
literature
[220],
but,
contrary
to the DSI
approach presented above, these methods
do not
allow
the
unit normal vectors
to be
taken into account directly.
Moreover,
in
geological applications,
the
interpolation technique based
on
DSI
can be
used
to
model discontinuous horizons intersected
by
faults such
as
those represented
in
figure
(2.1).
In
this case,
the
faults have
to be
modeled
first
and
then
used
to
introduce discontinuities
in the
discrete
model
as
shown
in
figure
(1.6). Proceeding this
way
generates
a
discontinuous
function
ip
a
,
which
in
turn induces discontinuities
in
<S
a
.
In
this case,
<S
a
represents only
a
part
of da, and the
rest
of
this boundary corresponds
to a
part
of the
faults
used
to
introduce
the
discontinuities.
Comments
It can be
observed
that
the
notion
of
implicit surface presented
in the 3D
space
can be
extended without
any
difficulty
to
implicit hypersurfaces embedded
in
the
M
n
space.
Moreover,
the
notion
of
implicit surface provides
an
elegant solution
to the
difficult
problem
of
building
parallel
surfaces.
In
practice,
if
(p
a
is a
normal-
form
of an
implicit equation
of
<S
a
(see
definition
3.22) then,
in the
neighbor-
hood
of
this surface,
for any
small real value
e,
a
surface
«S
a
(er),
parallel
to
S
a
and
located
at
approximately
a
distance equal
to £
from
<S
a
,
can be
defined
as
follows:
If
e
is
positive, then
S
a
(£)
is
located inside
the
region
a, but it is
located
outside
a if
e
is
negative.
3.7
Conclusions
Tessellation problems still provide
a
very active
field of
research
and
this
chapter gives just
a few
ideas
of the
wide variety
of
methods proposed
so
far.
• At
point
PJ,
the
function
(p
a
should
be
equal
to
zero:
• At
point
PJ
, the
derivatives
of the
function
<p
a
should
be
such
that
3.7.
CONCLUSIONS
137