Jean-Laurent Mallet. Geomodeling
Подождите немного. Документ загружается.
68
CHAPTER
2.
CELLULAR PARTITIONS
In
practice,
it is
convenient
to
define
the
functions
^
and
//
,
respectively,
on
D
+
and D~ as the
inverses
of
TT
+
and
TT~:
Note
that
these
functions
p,
+
and
/j,
are
such
that
Figures
(2.26),
and
(2.27)
show examples
of the
magnetic
interpretation
of
Darts.
2.4.4
Orientability
Surfaces
play
an
important role
in the field of
geomodeling. From
a
practical
point
of
view,
"orientable"
surfaces
are the
only ones
that
can be
encoun-
tered when modeling
natural
objects.
The
orientability
of
surfaces
is
thus
of
particular interest, therefore
it is
worthwhile
to
recall some
definitions:
• A
surface
A is
said
to be
"orientable"
if,
walking
on one
side
of
this
surface,
one
cannot
reach
the
opposite
side
without
crossing
a
boundary
(if
any).
For
example,
the
Moebius
strip
or the
Klein
bottle (see
figures
(2.26),
and
(5.8))
are,
respectively,
open
and
closed
non-orientable
surfaces.
• An
orientable
surface
A is
said
to be
oriented
if one of its two
sides
is
entitled
to be the
"positive"
side,
while
the
other
is the
"negative"
side.
• A
closed
curve
C
drawn
on an
oriented
surface
A,
without
self-intersection
and
bounding
a
region
R C A, is
said
to be
"positively
oriented"
if,
walking
on the
curve
C on the
positive
side
of
^4,
the
region
R
remains
on the
left
(see
figure (5.9)).
• A
cellular
partition
P(A)
of a
surface
A is
said
to be
"oriented"
if
the
boundary
of
each
2-cell
is
positively
oriented
(see
figure
(5.10)).
In
this
case,
each
edge
not
belonging
to the
boundary
is
traversed
exactly
twice.
In
this section,
a
generalization
to
n-GMaps
of
this
concept
of
orientability
is
proposed.
Such
a
generalization
is
derived
from
the
magnetic interpretation
of
Darts presented above
and is
based
on the
following
"painting" algorithm,
which
can be
easily understood when considering
the
2-dimensional
example
illustrated
in figure
(2.26):
Painting
algorithm
Let
n be a
positive integer
and let
Q(D,ao,ai,..
.,a
n
)
be a
connected
n-
GMap
whose positive poles
d
+
are
assumed
to be
painted
in red
while
the
negative poles
d~ are
assumed
to be
painted
in
blue.
Then
let us
surmise
that
it
is
possible
to
split
D
into subsets
D
+
and
D~
of
equal size
in
such
a way
that
2.4.
GENERALIZED MAPS
69
In
other words,
we
would like
to
know whether each Dart
is
linked
by
o.i
involutions
only with Darts having
an
opposite polarity: this would allow
{oti}
involutions
to be
interpreted physically
as
"attracting
forces" between
Darts.
As
shown
in
figure
(2.26),
the
answer
is
•
yes,
if the
object
modeled
by the
GMap
is
orientable (see
figure
(2.26)-A),
and
• no, if the
object
modeled
by the
GMap
is
non-orientable
such
as, for
exam-
ple,
a
Moebius
strip
(see
figure
(2.26)-B).
This suggests
the following
painting
algorithm
21
where
the
input argument
D*
is an
empty
set
while
d*
is an
arbitrary
dart
of
D:
GMap_paint(
Q(D,
a
Q
,..
.,a
n
),
d*,
D*
T
) {
if(d*
G
D*)
return
D*
<—
£>*
U
{d*}
for(
i =
l\
i<n;i
+ +) {
GMap_paint(
Q(D,a
0
,..
.,a
n
),
a
0
oa
i
(d
i
'),
D* )
}
}
If
the set D* is
initially empty, then
the
above recursive
function
returns
a
set
D*
containing
all the
Darts having
the
same polarity
as the
Dart
d*.
In
consequence,
after
running
the
above algorithm with
D*
initialized
to the
empty
set
•
either
D* is
equal
to D,
• or the set D* is
identical
to the set
D
+
or
D~
corresponding
to the
Darts
having
the
same
polarity
as
d*.
Definition
Let G —
G(D,
QO,
•
•.,
Oi
n
]
be a
connected
n-GMap
and let
D*
be the
associated
set of
Darts
defined
by the
above painting algorithm.
By
definition,
we
will
say
that
• G is
orientable
if D* is
distinct
from
D, and
• G is
non-orientable
if D* is
equal
to D.
Theorem
A
surface
A is
orientable
if, and
only
if,
there
is an
orientable 2-GMap asso-
ciated with
a
cellular partition
P(A)
of A
(see [134,
136]).
2.4.5
Maps
So
far,
we
have presented
the
notion
of
"generalized"
Map
without saying
anything about "ordinary" Maps.
In
this section
we
briefly
present this notion,
which
can be
very
useful
in
practical applications.
For
example
Output argument
D*
is
noted
with
a
|
sign.
70
CHAPTER
2.
CELLULAR
PARTITIONS
Figure
2.27
An
example
of
2-Map
associated
with
a
2-GMap.
The
"magnetizer"
function
JJL
transforms
each
twin
Darts
(d~,d
+
)
into
a
magnet
m,
while
the
"pole"
functions
IT~
and
TT
+
associate each
magnet
respectively
with
its
corresponding
Darts
d~ and
d
+
.
The
ai
involutions
are
represented
by
simple links,
the
0:2
and
/?2
involutions
are
represented
by
double links,
and the
J3\
permutation
is
represented
by
oriented arcs
of
circles.
•
from
a
computer science
point
of
view,
a Map can be
used
for
storing
a
"compre-
ssed"
version
of a
GMap,
and
•
from
an
algebraic topology point
of
view,
a Map can be
used
for
describing
the
orientations
of a
manifold object.
Introduction
As
suggested
in
figure (2.27),
let us
consider
the
magnetic
interpretation
of a 2-
GMap
G =
Q(D,
a
05
«i,
^2)
introduced
in
section
(2.4.3)
and let
Ai(M,
/3i,
$2)
be the
algebraic
structure
derived
from
G as
follows:
Using
the
function
p,
+
=
(TT
+
)
l
denned
on
page
68, it is
observed
that
the
above
relationships
(2.30)
can
also
be
written
more
concisely
as follows:
2.4. GENERALIZED MAPS
It can be
noted
that
the
functions
(3\
and
/?2
so
denned
are
invertible and,
in
addition,
/3
2
is an
involution:
We
will
see
below
how the
notion
of
n-Map generalizes
the
algebraic structure
M.(M,P\,fl2)
presented
in
this introduction.
Definition
Let n
>
1 be a
given integer
and let
jVf
(M,
f3\,...,
/3
n
)
be a
(n
+
l)-tuple such
that
22
By
definition,
we
will
say
that
M(M,
0i,..
.,(3
n
)
is a
"Map"
of
dimension
n
or,
more simply,
an
n-Map
or a Map if the
following
constraint
is
honored
[22]:
• the
transformations
{/5j
+
2+fc
°
A}
are
involutions
for any i
>
1 and any
k
>
0
such
that
(i + 2 +
k)
<
n:
A
0-Map
is
defined
by
M(M)
=
M.
Converting
an
n-GMap
into
an
n-Map
The
relationships (2.31) presented
in the
introduction
to
this section
in the
particular case
of a
2-GMap
can be
generalized
as
follows
for
converting
an
n-GMap
G =
£(D,a
0
,ai,
•
•
-,
a
n
}
into
an
n-Map
G
+
=
M(M,
fa,..
.,/?„)
called "Map
of the
positive side"
of G:
It can be
checked
that
the
functions
{A}
so
defined
are
invertible
and,
in
addition,
the
functions
{/3j
:
j =
2,..
.,n}
are
involutions:
22
Recall
that
a
permutation
(3 is an
invertible operator
for
which
j3(m}
is
called "succes-
sor"
of
77i,
while
/3~
l
(m)
is
called "predecessor"
of
m.
71
72
CHAPTER
2.
CELLULAR PARTITIONS
Similarly,
it is
possible
to
define
as
follows
the
n-Map
G =
M(M,
/?i,...,
j3
n
)
called
the
"Map
of the
negative side"
of G:
It can be
checked
that
the
functions
{&}
so
denned
are
invertible and,
in
addition,
the
functions
{/3j
:
j =
2,..
.,n}
are
involutions:
It
should
be
observed
that
M
is the set of
magnets
ra =
(j,(d
+
,d~}
obtained
in
reversing
the
polarity
of the
magnets
of
M.
For
example,
if we
refer
to
figure
(2.27),
G
+
corresponds
to the map on the
right-hand side
of the
figure,
while
G~
corresponds
to the figure
obtained
by
reversing both
the
orientations
of
the
magnets
and the
direction
of the
(3i
links.
Converting
a
connected
n-GMap
into
a
connected
n-Map
Converting
a
connected n-GMap
G(D,
ao,
0:1,...,
a
n
)
into
a
connected n-Map
A4
(M,
/?i,...,(3
n
)
can be
performed
in
three
steps
23
as
follows:
1.
The first
step
consists
in
applying
the
painting algorithm presented
on
page
69 for
building
the set
D
+
containing half
of the
Darts
of
D:
Build_£>
+
(
g(D,a
0
,...,a
n
),
£>
+T
) {
•
choose
a
Dart
d E D
•
D
+
<—
0
GMap_paint(
<?(D,a
0
,...,an),
d,
D
+
)
}
2.
The
second step consists
in
building
M and
defining
the
function
/j,
+
as
a
table
of
associations
[123]:
Build_M_At+(
£>+,
M\
^
) {
•
M<—0
• let
{x,
/j,
+
(x)}
be an
empty
table
of
associations
for_all(
d
+
e
D
+
) {
•
build
a new
magnet
m
• M
<—
M U
{m}
• add
((i
+
,m)
to the
table
{x,p,
+
(x)}
}
}
3.
The
third step consists
in
building
the
functions
{/%
: i —
1,..
.,n}
as
follows:
23
For
the
sake
of
clarity, output arguments
are
noted with
a
|
sign.
2.4.
GENERALIZED MAPS
Build_/3(£(L>,a
0
,...,a
n
),
£>+,
//+,
{/3
1;
..
.,/?
n
}
T
) {
for_all(
d
+
e
D+
) {
•
m
<—
/^
+
(d
+
)
for(
i
—
I;
i<n;
i + +) {
•
(3i(m)
=
n
+
(ao
o
ai(d
+
))
•
(3-
l
(m)
=
^+(ai
o
a
0
(d
+
))
}
}
}
Converting
a
connected
n-Map
into
a
connected
n-GMap
Any
n-Map
A4(M,
fl\,..
.,/3
n
)
can
always
be
transformed into
its
associated
orientable n-GMap
G(D,
a
0
,
«i,
• •
•,
a
n
).
For
this
purpose,
we
have
to
proceed
in
two
steps:
1.
The
first
step consists
in
restoring
the set D and
denning
the
functions
TT
+
and
QQ
as
association-tables:
Build_
J
D_7r+_a
0
(Ai(M,/5i,...,/3
n
),
D
T
,
7r
+t
,
aj
) {
•
D
+
<—
0 ; D-
<—
0
• let
{X,TT
+
(X}}
and
(a^aoC^)}
be two
empty
association-tables
for_all(
m € M ) {
•
build
a new
pair
of
Darts
(d
+
,
d~)
•
D
+
<—L>+U{d+}
;
£>~
<—.D-Uld"}
• add
(m,d
+
)
to the
table
{X,TT
+
(X}}
• add
(d
+
,d~)
to the
table
{x,ao(x)}
• add
(d~,d
+
)
to the
table
(o;,ao(x)}
}
•
D<—
D
+
UD~
}
2.
The
second step consists
in
restoring
the
involutions
(o^
: i =
1,...,
n}
as
follows:
Build_a(
M(M,/3i,...,/3
n
),
TT+,
a
0
,
{ai,...,a
n
}
T
) {
for_all(
m 6 M ) {
•
d+
<—7r+(m)
•
d~
•<—
ao(d
+
)
for(
i
=
l;«<n;i
+ +) {
•
a.i(d
+
]
—
ao
o
TT
+
o
^i(m)
•
ai(d~)
=
7r
+
o/?-
1
(m)
}
}
}
73
74
CHAPTER
2.
CELLULAR PARTITIONS
Compressing
an
orientable
connected
n-GMap
It can be
observed
that
the
number
of
Darts
of an
orientable connected
n-
GMap
is
twice
the
number
of
magnets
of its
associated
n-Map.
Moreover,
an
n-GMap contains
one
more operator
than
its
associated n-Map. This clearly
shows
that,
from
a
computer science
point
of
view, n-Maps
are
more
than
twice
as
small
as
their associated orientable n-GMaps. Accordingly,
as
long
as we
have
to
deal with orientable n-GMaps, their associated n-Map
can be
considered
as a
"compressed" representation
of the
same object.
2.4.6 Operations
on
GMaps
So
far, cells
and
CellViews have been introduced
in a
descriptive
perspective
where
the
notion
of
VertexView appears
as the
elementary entity
to
which
an
object
can be
decomposed. This section introduces
the
opposite point
of
view
where
Darts
are
used
in a
constructive
perspective showing
that
they
can
be
used
as the
kernel
of a
topological
modeler.
The
basic idea consists
in
building
a
series
of
n-GMaps
{G°,
G
1
,...}
where:
•
G°
corresponds
to the
empty
n-GMap:
•
G
k
corresponds
to an
n-GMap
deduced
from
G
k
~
l
by a
"macro"
transformation
T
k
:
At
any
time, each "abstract" n-GMap
G
k
is
assumed
to be
mapped
to a
"real" n-GMap
Q(P
k
(A
k
],
0$,
a^,...,
a£)
=
4>(G
k
]
associated with
a
partition
P
k
(A
k
)
of an
n-manifold
object
A
k
.
Micro
transformations
{tj}
In
practice,
the
macro transformations
T
k
presented above
are
decomposed
as
follows
where
each
tj is a
"micro" transformation.
For
example, Bertrand [22] pro-
poses
choosing
the
following minimal
set of
micro transformations
{tj}:
•
Create
an
isolated
Dart
x and add it to the
current
GMap;
the
involutions
associated
with
this
isolated
Dart
x are
initialized
as
follows:
•
delete
a
Dart
from
the
current
GMap.
2.4. GENERALIZED MAPS
•
Create
an
on
involution between
two
Darts
x and y of the
current GMap
in
such
a way
that
the
following
relationships
become true:
•
Delete
an
cti
involution between
two
Darts
x and y of the
current GMap
in
such
a way
that
the
following
relationships become true:
It
should
be
noted that,
in
general, these micro transformations {tj}
do not
transform
a
GMap into
a new
valid GMap: they must
be
combined
carefully
to
build authorized macro transformations
T
k
able
to
transform
a
GMap
G
k
~
l
into another valid GMap
G
k
honoring
the
constraints
(2.13),
(2.14),
and
(2.15).
Orbit
traversals
In
addition
to the
micro transformations presented above,
for any
given Dart
d,
there
is a
need
for a set of
traversals
that
allow
all the
Darts belonging
to
an
orbit
<
a^,...,
oti
k
>
(d)
to be
scanned.
For
example, these traversals
are
used
in
operations related
to
• The
definition
of a
transformation
tj
described above
and
used
for
build-
ing
a
valid transformation
T
k
.
•
Geometrical queries required
by
geometrical algorithms such
as
—
computing
the
intersection
of two
surfaces,
—
scanning
the
boundary
of an
z-cell,
and
—
detecting
the
region
(n-cell)
containing
a
given
point.
•
Display
of the
embeddings
of
^-cells.
If
we
note
C^
+1
the
number
of
distinct combinations
<
o^,
a^
2
,...,
oti
p
>
of
p
>
1
involutions taken
in the set
{ao,...,a
n
},
then, according
to the
binomial
formula,
it is
well
known
that
we
have:
We
conclude
that
there
are
(2
n+1
—
1)
possible traversals corresponding
to all
the
possible orbits
<
a^,...,
a^
p
> (d) of any
Dart
d G D.
From
a
practical point
of
view,
the
following
general algorithm
can be
used
for
traversing
the
orbit
<
CKi[i],0^2],
• •
••>oti(k]
> (d) and
applying
the
operator
do_it()
to
each traversed Dart:
Orbit_traversal(
Q(D,ao,..
.,a
n
),
k,
i[-],
d,
do_it
) {
•
build
new
empty
set of
Darts:
traversed
•
build
new
empty stack
of
Darts:
to-traverse
75
76
CHAPTER
2.
CELLULAR PARTITIONS
•
traversed
<—
traversed
U {d}
•
to-traverse
•
push(cf)
while
(
to-traverse
not
empty
) {
• d*
<—
to-traverse
•
pop()
•
do_it(cT)
•
traversed
<—
traversed
U{d*}
for(
j =
I
•
j
<
k ; j + + ) {
if(
a
i
[j](d*)
0
traversed
){
•
to.traverse-push(oti[j](d*))
}
}
}
}
Abstract
i-cell
iterators
By
definition,
we
call "abstract
z-cell
iterator,"
or
more simply
"i-cell
iter-
ator,"
any
algorithm allowing exactly one,
and
only one, Dart
per
abstract
i-cell
24
honoring
a
given criterion
to be
scanned. Among
the
most
frequently
used
i-cell
iterators,
the
notions
of
global
and
local
i-cell
iterators
can be
mentioned:
• A
global
z-cell
iterator
is
used
for
scanning
one
Dart
per
abstract
i-cell
of
a
GMap.
For
example,
in the
case
of a
surface
composed
of
adjacent
polygonal
facets
(see
figure
(2.25)):
—
a
global
2-cell
iterator
can be
used
for
scanning
all the
facets
of the
surface,
—
a
global
1-cell
iterator
can be
used
for
scanning
all the
edges
of the
surface,
and
—
a
global
0-cell
iterator
can be
used
for
scanning
all the
vertices
of the
surface.
• A
local
i-cell
iterator
is
used
for
scanning
one
Dart
per
abstract
i-
cell
incident
25
to a
given
fc-cell. For
example,
in the
case
of a
surface
composed
of
adjacent polygonal facets (see
figure
(2.25)):
—
a
local
2-cell
iterator
can be
used
for
scanning
all the
facets
adjacent
to
a
given facet,
—
a
local 2-cell
iterator
can be
used
for
scanning
all the
facets
incident
to
a
given edge,
—
a
local
2-cell
iterator
can be
used
for
scanning
all the
facets
incident
to
a
given
vertex,
—
a
local
0-cell
iterator
can be
used
for
scanning
all the
vertices
incident
to a
given facet,
and
24
Recall
that, according
to the
definition
given page
61,
abstract
z-cells
are
identified
to
i-orbits.
25
See
definition
on
page
59.
2.4.
GENERALIZED
MAPS
77
Figure
2.28
Examples
of
"sewing"
transformation
performed
on a
pair
ofl-cells
of
a
2-GMap.
—
a
local
0-cell
iterator
can be
used
for
scanning
all the
vertices
linked
by
an
edge
to a
given
vertex.
2.4.7 Cell transformations
Minimal
set of
cell
transformations
{T
k
}
Using
the
micro transformations
{t/}
and the
traversals introduced
in the
preceding section,
it is
possible
to
build
the
following
set of
cell operators
{T
k
}
transforming
a
given
n-GMap
into
a
new, valid
n-GMap
honoring
the
constraints (2.13), (2.14),
and
(2.15):
•
create_cell(n,
gm,
ncell-def)
creates
and
adds
to the
n-GMap
gm
a
new
n-cell
whose type
and
associated embeddings
are
defined
by the
input argument
ncelLdef;
•
delete_cells(n,grn,
d)
removes
from
the
n-GMap
gm and
deletes
all
the
i-cells
currently
incident
26
to a
given Dart
d for i
<
n.
However,
if
the
deleted
z-cells
share vertices with adjacent
n-cells,
then
the
Darts
corresponding
to
these
vertices
are
kept
in the
n-GMap
gm and the
adjacent
cells remain unchanged.
As a
result,
a
"hole"
will
appear
in
the
associated object modeled
by the
n-GMap.
•
sew_cells(n,gra,
do,di)
sews
a
pair
of
n-cells
(Co,Ci)
incident respec-
tively
to a
pair
of
given
Darts
(do,di)
of the
n-GMap
gm
(see
figure
(2.28)).
Such
a
sewing operation
is
possible only
if the
pair
of (n
—
1)-
cells
(Fo,Fi),
called "faces"
and
incident respectively
to
(d
0
,di),
honor
the
following
preconditions:
26
See
definition
on
page
59.