Jean-Laurent Mallet. Geomodeling
Подождите немного. Документ загружается.
308
CHAPTER
6.
PIECE WISE
LINEAR
TRIANGULATED
SURFACES
Figur e
6.31 Part
(A)
shows
a
parameterized triangulated
surface
T(<5)
re-
sampled
and
transformed
into
the new
triangulated
surface
T*(»S)
shown
in
part
(C).
In the
parametric domain
T(D},
part
(B)
shows
the map of the
curvature
of
T(<S),
while part
(D)
shows
the new
triangulation
T*(D*)
associated with
the new
triangulation
T*(S)
in
part
(C).
let
T*(S)
be a
copy
of
7£i(S)
install
Control-Thickness constraint
on
T*(S)
install
Control-Nodes
on the
boundary
of
T*
(S)
apply
beautifier#l
to
T*(S}
run
DSI
on
7^(3)
}while(
topology
{T*
(S}}
^
topology
{7~*_
l
(S)})
This
program
implicitly
assumes
that
the
Control-Thickness
constraints
ap-
plied
to
T*(S)
stipulate
that
the
"thickness"
between
T*(S)
and
7^^
1
(»S)
must
remain
equal
to
zero.
Figure
(6.30)-C
gives
an
example
of the
result
obtained
with
this
algorithm
when
applied
to the
triangulated
surface
shown
in figure
(6.30)-A.
6.6. MODIFYING
THE
TOPOLOGY
309
6.6.2
Resampling
algorithm
Notion
of
resampling
As
suggested
in
figure
(6.31)-A,
let
T(S]
be a
globally
parameterized
open
triangulated
surface,
and let
T(D]
be the
associated
triangulation
in the
para-
metric
domain
D
defined
by
equations
(6.60),
and
(6.64).
The
possibility
always
exists
to
build
a
vectorial
function
x(u)
interpolat-
ing
the
vertices
of
T(S]
on D and to
assume
that
this
function
corresponds
to a
parametric
representation
of the
unknown
underlying
surface
S to be
modeled:
For
example,
x(u)
could
be
• the
piecewise linear
function
x, as
denned
in
section (6.1.2)
and
interpolating,
in
a
linear way,
the
vertices
of
T(S];
• the
piecewise nonlinear function
x, as
defined
in
chapter
7 and
interpolating,
in
a
curvilinear way,
the
vertices
of
T(S)
thanks
to a
Gregory patchwork (see
section
(7.3),
page
336);
or
• a
Kriging interpolator (see section
(9.7),
page 502).
The
choice
of
such
an
interpolator
x(u)
immediately
allows
a new
triangulated
surface
T*(S]
to be
built
as
follows:
1.
Choose
a
finite
point
set P
fully
contained
in D.
2.
Build
the set £ of the
edges corresponding
to the
boundary
of D.
3.
Build
the set P*
consisting
of the set P
plus
the
vertices
of the
edges
of
£:
For the
sake
of
consistency with previous notations,
the
points
of P* are
noted
as
follows
where
the
{a*}'s
are
assumed
to
belong
to a set of
indexes
f2*.
4.
Using
the
algorithm
presented
on
page 104, build
the
constrained
Delaunay's
tessellation
T>(P*\£)
of the
parametric domain
D.
5.
Remove
all the
triangles
of
T>(P*
\E]
whose barycenters
are
outside
D to
obtain
a
retriangulation
T*(D)
of the
parametric domain
D:
6.
Build
a new
triangulation
T*
(S) of S
consisting
of the
image
of
T*
(D)
defined
by
x(-):
According
to
equation
(6.90),
the
image
x(u(a*))
of any
point
of P*
belongs
to the
unknown
surface
S,
and the set of
points
{x(a*)}
defined
by
corresponds
to the
vertices
of T*
(S).
310
CHAPTER
6.
PIECE
WISE
LINEAR TRIANGULATED SURFACES
The new
triangulated surface
T*(S)
so
defined
is
called
a
"resampling"
of
T(S}.
For
example,
the
nodes
of the
triangles
in
figure
(6.31)-D
constitute
a
resampling
of the
triangulated surface shown
in
figure
(6.31)-A.
In
practice, this resampling method
can
easily
be
adapted
to
take proper-
ties
of
T(S]
into account:
• The
density
of the
points
of P in D may be
chosen
as a
function
of a
property
of the
initial surface
T(S]
such
as, for
example
—
the
intensity
of the
curvature
of
T(S],
and
—
the
gradient
of a
physical property attached
to
T(S}.
Figures
(6.30)-D
and
(6.31) give examples
of a
resampling performed
in
function
of the
maximum curvature (see page 235)
of the
surfaces.
• If the new
triangulation
T*
(S]
has to
honor
a
polygonal curve
L
assumed
to be
drawn
on
tS,
then
it
suffices
to
proceed
as
follows:
—
build
the
image
A of L in D:
—
if
need
be,
clip
A to the
interior
of the
domain
D:
—
add the
edges
of A to the
initial
set of
edges
£:
—
add the
vertices
of A to
P*:
Figure
(6.32)
shows
an
example where
a
resampling
is
performed
in
function
of the
maximum curvature
of the
surface while honoring some
given
curves drawn
in
bold.
Piecewise
linear
embedding
x*
associated
with
a
resampling
In
practice,
the
function
x(u)
is
sampled
at
locations
u(a*)
corresponding
to
the
point
set P* and
x(u)
may be
approximated
by a
piecewise linear
function
x*(u)
interpolating
x(u)
linearly
on
each
triangle
of
T*(D).
In
this case,
the
image
T*
of
each triangle
DT*
of
T*(D)
is a flat
triangular
facet
belonging
to the new
triangulated surface
T*(S]
such
that
It
should
be
noted
that,
the two
piecewise linear functions
x(u)
and
x*(u)
interpolating
the
vertices
of
T(D]
and
T*(D)
linearly are,
in
general,
two
different functions:
6.6. MODIFYING
THE
TOPOLOGY
311
Figure
6.32 Part
(A)
shows
a
parameterized triangulated
surface
T(«S)
resam-
pled
and
transformed
into
the new
triangulated
surface
T*(S]
shown
in
part (C).
In
the
parametric domain
T(D),
part
(B)
shows
the map
of
the
initial triangulation
ofT(S),
while part
(D)
shows
the new
triangulation
T*(D*)
associated with
the
new
triangulation
T*(S]
of
the
parametric domain producing
the new
triangulation
T*(<S)
in
part (C), that honors
the
four
curves
drawn
in
bold.
An
example
of a
resampling
algorithm
The new
triangulated
surface
T*
(<S)
associated
with
the
piecewise
linear
inter-
polator
x*(u) defined
above
appears
as a new
approximation
of the
underlying
unknown
surface
<S.
The
associated
new
sampling
P*
may be
optimized
to
honor
the two
following
constraints
where
E is a
given
threshold:
2)
the
number
of
vertices
of T* (S) is
minimum.
For
this
purpose,
we
propose
using
the following
algorithm
where
the
operator
T^n(P*\£}
is
assumed
to be the
constrained
Delaunay
triangulation
(see
page
104)
with
all the
triangles
outside
the
parametric
domain
D
removed:
//—
Resampling
let P* be the set of
nodes
of
d(D)
flag
+—
true
while(
flag ) {
312
CHAPTER
6.
PIECE
WISE
LINEAR TRIANGULATED SURFACES
Figure
6.33
Gluing
an
edge
E(S)
of
a
triangulated
surface
T(«S)
onto
a
trian-
gulated
surface
T(F}
may
require
a
resampling
of
T
to
obtain
a new
triangulation
of
J-
that
honors
the
polygonal
curve
L(}-}
corresponding
to the
projection
of
E(S)
on
J-.
Figure
(6.30)-D
shows
an
example
of
resampling
obtained
with
this
algorithm
when
applied
to the
triangulated
surface
shown
in figure
(6.30)-A.
The
func-
tion
x(u)
used
in
this
example
was a
G
1
Gregory patchwork (see section
(7.3)).
About
curves
As
already mentioned
in the
resampling algorithm presented above,
the
edges
of
polygonal curves
can be
taken into account. Such
a
possibility
is
partic-
ularly interesting
in the
practical situation illustrated
in figure
(6.33).
As
shown
in
this
figure, let us
consider
the
projection
I/(^")
of an
edge E(S)
of a
triangulated
surface
T(«S)
on a
triangulated
surface
T(F}.
If the
surfaces
S
and
T
have
to be
glued (see page
90)
along
the
polygonal curves
E(S]
and
L(JF),
then,
in
general,
a
resampling
of
T
honoring
L(F]
has to be
built,
and
the
above algorithm
can be
used
for
this purpose.
Trimming
algorithm
It
should
be
noted
that
the
above resampling algorithm
can
easily
be
modified
to
build
a
triangulation
T(S/B]
corresponding
to a
subset
of S.
Such
an
operation
is
called
a
"trimming"
of
S and is
defined
by a
given closed polygonal
curve
B
assumed
to be
contained
in the
parametric domain
D and
called
a
"trimming curve."
All
that
is
required
in
this case
is to
change
the set 8 of
segments
used
by the
resampling algorithm
as
follows:
6.6.
MODIFYING
THE
TOPOLOGY
With
8
defined
in
such
a
way,
the
resampling algorithm
will
generate
a new
triangulated surface
T*(<5*)
corresponding
to a
subset
<S*
of S and
having
an
external boundary corresponding
to the
image
of
B
in
M
3
.
Extension algorithm
Let
D
+
be a
given region
of
JR
2
containing
D. The
possibility always
exists
to
build
a
function
x
+
(u)
denned
on
D
+
and
identical
to the
piecewise linear
interpolation x(u)
on D:
For
example,
if
D
+
is
bounded
by a
polygonal curve
dD
+
,
then
the
following
procedure
can be
adopted
for
building
x
+
(u)
on
D
+
:
•
build
a
triangulation
T(D
+
)
identical
to
T(D)
plus
a set of
triangles
covering
the
ring
(D
+
—
D) and
honoring
the
edges
of
dD
+
;
•
build
the
discrete
model
.M
3
(f2
+
,
N
+
,
x
+
,C
x
+),
where
£7
+
corresponds
to the
nodes
of
T(£>
+
)
and
where
C
x
+
consists
of
Control-Nodes
installed
on the
vertices
of
T(D),
while
N
+
is
induced
by the
edges
of
T(D
+
);
•
interpolate
x
+
on fi
+
with
the
DSI
method;
and
•
interpolate
x
+
(u)
by
x(u)
linearly
on
each
triangle
of
T(.D
+
).
The
image
of
T(D
+
)
by the
function
x so
defined
is a
triangulated surface
extending
T
(<!>).
Note
that
the
extension
of
T(«S)
so
obtained
can be
trimmed
by
any
polygonal trimming curve
B
contained
in
D
+
.
Moreover,
it is
easy
to
implement
a
composite operation involving extensions
and
trimmings:
for
this purpose,
in the
parametric domain
it
suffices
to
define
a
closed curve
representing
the
boundary
of the new
surface
to be
built.
6.6.3
Cut
algorithm
Let
us
consider
two
triangulated
surfaces
26
T(«S)
and
T'(.7
r
),
and let
r(«S,J
r
)
be the set of
points
of
-ff?
3
,
as
defined
by
From
a
theoretical point
of
view,
F(«S,
J-)
may
consist
of
isolated points, pieces
of
polygonal curves
and
pieces
of
isolated
surfaces (patches):
26
For
example,
S
corresponds
to a
geological
surface
cut by a
fault
F.
313
314
CHAPTER
6.
PIECEWISE LINEAR TRIANGULATED SURFACES
Figure
6.34
A
triangulated
surface
T(S}
crossed
by a
second
(transparent)
triangulated
surface
T(F}.
The cut
generates
a new
boundary
on
T(S]
without
modifying
its
geometry.
Installing
a
Boundary-on-Surface
constraint
specifying
that
the new
boundary
should
remain
stuck
on
T(F}
before
running
DSI
on
T(S}
enables
the
fault
trace
to be
"opened."
In
practice,
the
subsets
Fo(«S,
J-}
and
^(5,
F]
are
discarded. "Cut operation"
denotes
any
resampling
of
<S
resulting
in a new
triangulation
T*
(<S)
honoring
Fi(«S,
J
7
)
in the
following
sense:
The
"cut algorithm" corresponding
to
this
cut
operation
can be
outlined
as
follows:
1.
Let
"yi(S,F)
be the
empty
set.
2.
For
each
pair
of
triangles
T
s
G
T(S}
and
T/
e
T(F},
determine
the
intersec-
tion
(T
s
n
T/).
If
T
s
e
T(<S)
is a
segment,
then
add it to the set
71(5,
J
7
).
3.
Transform
the set of
segments
71
(<S,
T)
into
a set of
polygonal
curves
FI
(<5,
F).
4.
Retriangulate,
locally
or
globally,
the
surface
S to
obtain
the new
triangulation
T*(S)
honoring
the
edges
of
Fi(<S,
J
7
).
5.
Unsew
the
triangles
of
T*(S)
along
the
edges
of
Fi(«5,.F).
This
operation
is
realized
by
removing
the
«2
links
(see section
(2.4.7))
between
the
darts
associated
with
the
edges
of
ri(<5,.F).
In
spite
of its
theoretical
simplicity, implementing
the cut
algorithm
so
defined
is
extremely complex. This practical complexity
is
induced
by the
fact
that
the
above operations
(2),
(3),
and (4) are
very sensitive
to
rounding numerical
errors,
and a
naive direct implementation
of
these operations
is
unacceptable.
A
correct implementation must
be
based
on
logical geometric predicates tak-
ing
care
of the
history
of the
vertices
generated
at
step
(2).
The
role
of
these
geometrical
predicates
is to
guarantee
that
the
same logical point computed
in two
different
ways results
in one
single vertex.
A
complete description
of
such
a
complex system
is
outside
the
scope
of
this
book;
for
more details,
the
reader
is
referred
to
[109]
and
[74].
Figure (6.34) shows
an
example
of a cut
operation
corresponding
to the
intersection
of a
geological surface
by a
fault:
the new
surface
so
obtained possesses
a new
boundary corresponding
to the
fault
trace.
6.7.
CONCLUSIONS
315
6.7
Conclusions
A
large
part
of
this chapter
has
been dedicated
to the
presentation
of
DSI
constraints very
specific
to
geological surfaces modeled
as
triangulated
sur-
faces.
Most
of
these
constraints
would
be
very
difficult,
or
even impossible,
to
implement
at a
reasonable cost with traditional methods based
on
Bezier,
Splines,
or
Nurbs surfaces
(e.g.,
see
[77]).
Moreover,
the
possibility
of
glob-
ally parameterizing triangulated surfaces opens
the
door
to a
wide range
of
applications
in the
realms
of
structural geology, geostatistics,
and
geophysics.
The
only
limitation
of the
linear triangulated surfaces model
presented
in
this
chapter
is the
fact
that
the
geometry
of
each triangle
was
represented
as a flat
facet.
In the
next chapter
we
will
see how to
remove such
a
restriction.
It is
also relevant
to
note
that
most
of the
methods presented
for
triangu-
lated surfaces
can
straightforwardly
be
extended
to
tetrahedralized volumes
and
polygonal curves:
in
such cases,
the
tetrahedra
(3-simplexes)
of the
vol-
umes
and the
edges
(1-simplexes)
of the
curves play
the
same role
as the
triangles
(2-simplexes)
of the
triangulated
surfaces.
These methods
can
also
be
extended
to
surfaces composed
of
polygonal facets
or
volumes made
of
polyhedral
cells,
such
as
those shown
in figures
(2.18),
and
(2.25).
This page intentionally left blank
Chapter
7
Curvilinear
Triangulated Surfaces
Applications
exist,
for
example,
ray
tracing
in
geophysics, where
the
piecewise
linear
approximation
of
triangular facets proposed
in the
previous chapter
may
not be
sufficiently
smooth.
This chapter addresses this
problem,
proposing
practical solutions
to
obtain
smooth
curvilinear models
of
surfaces
interpolat-
ing the
vertices
of
a
given triangulated
surface.
7.1
Introduction
Initially, curvilinear models
of
surfaces were introduced
in the
industry
for
modeling elements
of car
bodies such
as the
hood,
the
roof,
or the
doors.
All
these elements being topologically equivalent
to
rectangles,
in the
early
days
of
CAD,
1
it
seemed natural
to use
parametric methods based
on
rect-
angular patches. However,
as
pointed
out by
Farin [76],
for
more complex
surfaces, such
as
those
encountered
in the
interior
of a car or in
geosciences,
decomposition into rectangular patches
is not a
natural choice:
[for
complex
surfaces],
rectangular
patches
do the
job,
although with
some
difficulties,
which
arise
mainly
in the
case
of
degenerate
rectan-
gular
patches.
Triangular
patches
do not
suffer
from
such
degeneracies
and
thus
are
better
suited
to
describe
complex
geometries than
are
rectangular
patches
...
...
If a
completely
new
system
is to be
developed,
such
a
system
would
most
likely
profit
from
the
additional
flexibility
offered
by
triangular
patches
enough
to
justify
a
higher
implementation cost.
1
Computer-Aided
Design.
317