Schedule
IV Workshop de Matemática Computacional, Estatística e Computação
Computational Manifolds:
February 14, 2011 (Mon), 9-11 AM
1. Introduction
Theory and Practice
2. Manifolds
February 15, 2011 (Tue), 9-11 AM
Marcelo Ferreira Siqueira
3. Constructing manifolds - I
4. Constructing manifolds - II
DIMAp - UFRN
February 16, 2011 (Wed), 9-11 AM
[email protected]
5. Implementation details
6. Surface fitting
ICMC-USP, São Carlos (SP), Brasil
February 17, 2011 (Thu), 9-11 AM
6. Implementation details
7. Adaptive fitting
February 14-17, 2011
2
Outline
Introduction
Lecture 1 - February 14, 2011 - 9-10 AM
•
•
•
•
•
3
Geometric modeling
The “Four Universe” paradigm
Representation forms
Surface fitting
-
Motivation
Existing solutions
The manifold-based paradigm
What’s next?
4
Geometric Modeling
•
•
•
The Four Universe Paradigm
Models
The Physical Universe
Geometric models
Contains the "physical" (or "real" objects) we wish to study.
Geometric modeling
-
Creation
Representation
Manipulation
Computational models
a donut
5
6
The Four Universe Paradigm
The Four Universe Paradigm
The Mathematical Universe
The Representation Universe
Mathematical models of the physical universe objets.
Finite description of the mathematical universe objets.
z
r2
r1
u
torus
7
x
A parametrization s : [0, 2π ) × [0, 2π ) → R3 , such that

s(u, v)
 x (u, v) = (r2 + r1 cos(v)) cos(u)
y(u, v) = (r2 + r1 cos(v)) sin(u)
s(u, v) =
v

z(u, v) = r1 sin(v)
y
The torus is given by s ([0, 2π ), [0, 2π )) .
8
The Four Universe Paradigm
The Four Universe Paradigm
The Representation Universe
The Representation Universe
Finite description of the mathematical universe objets.
Finite description of the mathematical universe objets.
z
r2
An implicit function s : R3 → R, such that
�
s( x, y, z) = ( x2 + y2 − r2 )2 + z2 − r12
r1
y
x
The torus is given by s−1 (0) .
9
10
The Four Universe Paradigm
The Four Universe Paradigm
The Representation Universe
The Implementation Universe
Finite description of the mathematical universe objets.
Data structures and machine models of computation.
//
// Function to evaluate the implicit function of a torus
//
function torus( x, y, z, r1, r2)
var val : real
val ← sqrt( x ∗ x + y ∗ y) − r2
val ← val ∗ val + z ∗ z − r1 ∗ r1
return val
endfuntion
[Isabelle Sivignon, Stages Master Recherche, 2007-2008]
11
12
Representation Forms
Surface Fitting
What is the best representation form?
Given:
The answer depends on the application...
• a simplicial surface T with empty boundary,
• a positive interger, k, and
Data often comes in a particular representation form.
• a scalar, � ∈ R, with � ≥ 0,
So, it is crucial to be able to convert from one form to another.
13
14
Surface Fitting
Surface Fitting
Find:
Can be viewed as a problem of converting representation
forms.
a C k surface, S, satisfying the following conditions:
(a) there exists a homeomorphism,
h : |T | → S ,
where | T | is the underlying surface of T.
(b) for every vertex, v ∈ T, we have
=⇒
d(v, h(v)) < � ,
where d(v, h(v)) is the Euclidean distance from v to h(v).
15
16
Motivations
Motivations
The advent of the 3D laser scanners made popular the use
of surface models represented by "very large" simplicial
surfaces.
[DAVID Laserscanner, www.david-laserscanner.com]
17
18
Motivations
Motivations
Many applications need to do "calculus"on these 3D models.
A simplicial surface is, in general, C0 only.
When the surface is "dense", we can still compute differential properties in a reliable way (using approximate methods).
But, there are issues...
• Dense simplicial surfaces demand a large amount of
memory.
• Some continuous operators have no discrete counterparts.
• Superconvergence of some numerical algorithms.
• Computer-Aided Manufacture (CAM)
19
20
Existing Solutions
Existing Solutions
The "Stitching" Paradigm
Subdivision Surfaces
[Myles, Ni, and Peters, 2008]
[Karciauskas and Peters, 2009]
21
22
Existing Solutions
Existing Solutions
The previous paradigms yield polynomial surfaces, but
Implicit Surfaces
• No "practical" algorithm for building C k surfaces, for
k > 2, using the stitching paradigm or subdivision
surfaces.
• Subdivision surfaces lack continuity at "extraordinary" points.
[Kanai, 2006]
• Most algorithms based on the stitching paradigm
produce C k surfaces with poor visual quality, for
k ≥ 2.
23
Powerful, but with complementary features with respect to parametric surfaces.
24
The Manifold-Based Paradigm
The Manifold-Based Paradigm
Key Idea:
R3
) j)
i (iΩ
θi (θΩ
) i ) ∪ θj (θΩj (j Ω
S=
S is defined as a 2-manifold.
�
θi (Ωi )
i∈ I
Key Elements:
θj
θi
PARAMETRIZATIONS
Set of gluing data plus parametrizations.
Main Advantage:
GLUING DATA
ϕij
It naturally yields parametric C ∞ surfaces, which are suitable for numerical applications involving differential and integral calculus on surfaces.
•
•
ϕ ji
Ω ji
Ωi
Ωj
26
What’s Next?
Advertisement
about manifolds and gluing data
="&-*+,"*/=*->,&?)/+)."*/@$"&*($(*+/
A)-BC,$?&)%$&+/*/7BD&?$;E*+
@"&-(),("/:"2#"$-/2%/A2-+B,$,&2%$C/
9$%&D2C=)/$%=/;++C&?$,&2%)
+*,*-.")/$/%)0*-.")/(*/1233
4567/8/9&)/(*/:$%*&")
*(+,(-.("/0/123(-.("4/5677
89:;/0/<&2/=(/>$%(&"2
$
how to build 2-manifolds from gluing data
!!
!
We will solve the surface fitting problem
•
R2
25
We will learn...
-
Ωij
!"
$
"!
! "!! #
!"
!!
!
"
!"
"
"!
8%
! "!! #
" "!" #
!"
8%
" "!" #
data structures and algorithms
6$",&?&B$;<)
We will discuss research opportunities
C*5$($%L(2(%(5",*$%H4%H*"'*2(H*
="ST5#*%L(2(%L4$6"#$(H*24$%H4%
LI$UH*"'*2(H*
6")#"$-$;<)
/@B@1C8DE%D.B.C8D%@%+D:@1C8D
%G"2$*%#,'2*H"'I2#*%$*J24%*%'4K(E%
K#,#$'2(H*%L45*$%*2M(,#9(H*24$
%1#,#3"2$*$%4%L(54$'2($%
F%
F%
F
F
4%F)"-$;E*+
V=G%-%<10=
?WXA%WYWZ%Y[XZ
\\\])#$M2(^]#KL(]J2_3K(W[XX
!"#$%&'$()"*+
EB%=&%#
!"#$%&"$'()*%+*,('*%-%./0
1(2345*%/#6"4#2(%-%.78+
!"#9%:45;*%-%<10=
>4(,%&(55#42%-%.04,,%?@.=A
7*2%0;G%$'"I4,'$%(,I%
R*$'OI*3'*2('4%24$4(23;42$%S2*N%
!('#,%=N42#3(%$3;**5$%(,I%
24$4(23;%#,$'#'"'#*,$
D.B.C8D
;=&,&2%$C/&%D2"-$,&2%
G=F%-%<10=
?TUA%TVTW%VXUW
PPPY)#$K2(SY#NR(YL2Z3N(TXUU
%/4K#,N2#*%$*J24%L4$6"#$($%
2434,'4$E%3*K%4$L43#(5#$'($%%
F
+D:@1C8D
O*2P$;*L%3*K%L(54$'2($%
L54,N2#($%4%H4%H#)"5M(QR*%
F%
27
28
;?,&3&,&()
/@0B@1C@8D%EFBEC@8%=+G%+E:@1C@8
%=,%#,'2*I"3'*2J%3*"2$4%K#)4,%LJ%
';4%*2K(,#942$
%B(5M$%(,I%N#,#O3*"2$4$%
H
H
EFBEC@8
%=%$4N#,(2%*,%2434,'%(I)(,34$%
P#';%54(I#,KO4IK4%24$4(23;42$%
H
+E:@1C@8
Q*2M$;*R%*,%(RR5#3('#*,$%'*%
K4*N4'2J%R2*34$$#,K%(,I%
4,K#,442#,K%
H%
!"#$%&'(")
!"#$%&"$'()*%+*,('*%-%./0
1(2345*%/#6"4#2(%-%.78+
!"#9%:45;*%-%<10=
>4(,%&(55#42%-%.04,,%?@.=A