Modélisation géométrique 2

Sylvain Brandel

M1if27 – 5 mars 2021

• Qu’est ce qu’on a envie d’afficher
– Courbes et surfaces paramétriques et courbes et
surfaces de subdivision
– Surfaces implicites / CSG

2
 Pourquoi ?

3
 Pourquoi ?

4
 Un tout petit peu d’histoire
• Modélisation surfacique (années 1960 – 70)
– De Casteljau (Citroën)
– Bézier (Renault)
– Coons (General Motors)
– Ferguson (Boeing)
• Modélisation volumique (années 1980)
– Réquicha
– Mäntylä
– Hoffmann

5
 Chaine de visualisation

Scène 3D § Modélisation géométrique

§ Transformations
Transformation géométrique § Projections
§ Algorithme du peintre

§ Lancer de rayon
§ Lignes de balayage
§ Z-buffer
Elimination des parties cachées § Lignes de balayage
§ Subdivisions de l’espace image
§ Lancer de rayon

§ Eclairement
Rendu réaliste § Ombrage
§ Modèles de couleurs
§ Radiosité

Affichage § Ecran !

6
 Première partie
Courbes et surfaces
paramétriques
 Représentation des courbes et
surfaces
x2+y2+z2-1=0
• Représentation implicite x-y=0
• Courbes : f(x,y,z) = 0 et g(x,y,z) =0
• Surfaces : f(x,y,z) =0
• Représentation paramétrique
• Courbes : x = f(t), y = g(t), z = h(t)
• Surfaces : x = f(u,v), y = g(u,v), z = h(u,v)
x=acost
• Courbe cubique : y=asint
• x = axt3 + bxt2 + cxt + dx z=bt
• y = ayt3 + byt2 + cyt + dy
• z = azt3 + bzt2 + czt + dz

8
 Représentation des courbes
• Représentation cartésienne
– Courbes planes : y = f(x)
– Courbes gauches : y = f(x), z = g(x)
– Avantages :
• simple
(b)
• accès direct à y et z connaissant x
(a)
– Inconvénients :
• tangente verticale non représentable
• rotation altère la courbe (b) (c)
• (c) non représentable

9
 Représentation des courbes
• Représentation paramétrique
– Courbes planes : x = f(t), y = g(t)
– Courbes gauches : x = f(t), y = g(t), z = h(t)
– Avantages :
• liberté sur les tangentes
• forme quelconque
• plein de propriétés
– Inconvénients :
• calculs parfois lourds ou délicats

10
 Historique
• Grands noms (années 60 – 70) :
– Bézier (Renault)
– De Casteljau (Citroën)
– Coons (General Motors)
– Ferguson (Boeing)
– De Boor ß B-Splines
• Grands systèmes de CFAO (années 80) :
– Euclid
– Catia
• Fin du duel Bézier – B-Splines : 1990
• Problème de reconstruction : 1990
• Surfaces de subdivisions : 1995

11
 Interpolation vs approximation
• Interpolation

• Approximation

12
 Continuité
Vn W0
• Continuité de position
– G0 : Vn = W0 Vn-1
– C0 : pareil
• Continuité de tangence W1
– G1 : Vn-1Vn et W0W1 colinéaires
– C1: même norme Vn-1
Vn W
0
• Continuité de courbure W1
– G2
– C2
Vn-1
• Continuité de torsion Vn W
0
– G3 W1
– C3

13
Interpolation de points
 Interpolation polynomiale
• L’interpolation polynomiale est à la base de tous
les concepts d’interpolation
• Soient P0, …, Pn et t0, …, tn les valeurs du
paramètre correspondant.
– Interpoler consiste à trouver une courbe P(t) passant
par tous les points
– On cherche un polynôme satisfaisant les contraintes
d’interpolation : P(ti) = Pi (i=0..n)
• Théorème :
– Il existe un unique polynôme P de degré £ n tel que
P(ti) = Pi (i=0..n) avec Pi et ti fixés

15
 Polynômes de Lagrange
• Forme explicite du polynôme d’interpolation P :
n
P(t ) = å Pi L (t )
n
n
i
Li
: polynômes de Lagrange
i =O n
avec å i (t ) = 1
Ln

i =O
n

Õ (t - t ) j
ì1 pour i = j
L (t j ) = d i , j
j =0, j ¹i
L (t ) =
n
i n
n
i =í
Õ (t i -tj) î0 sinon
j =0, j ¹i

16
 Approche de Vandermonde
• On utilise la base monômiale n
P(t ) = å ai t i
ìP(t0 ) = P0 = a0 + a1t0 + ! + ant0n i =O
ï
í" n+1 équations
ïP(t ) = P = a + a t + ! + a t n
î n n 0 1 n n n

é P0 ù é1 t0 t02 " t0n ù éa0 ù

ê ! ú = ê! ! !
úê ú
! úê ! ú ou encore
ê ú ê
êë Pn úû êë1 tn nú
tn " tn û êëan úû
2 P = TA ® A = T -1 P

17
 Algorithme d’Aitkem
• Interpolation de deux points A et B
t Î [0,1] : P(t ) = (1 - t ) A + tB

b-u u-a
u Î [a, b] : P(u ) = A+ B
b-a b-a

18
 Algorithme d’Aitkem
• Evaluation récursive
ti +1 - t t - ti
Pi (t ) =
1
Pi + Pi +1 i = 0 .. n - 1
ti +1 - ti ti +1 - ti
n -1 n -1 n -1
P0 (t ) interpole P0 , P1 , !, Pn -1 P
0 (ti ) = P
1 (ti ) = Pi
n -1
P1 (t ) interpole P1 , P2 , !, Pn
t n - t n -1 t - t0 n -1
alors P (t ) =
0
n
P0 (t ) + P1 (t ) P0n (ti ) = Pi
t n - t0 t n - t0i

19
 Algorithme d’Aitkem
P0 t - t0 P1 t - t1 P2 t - t2
P3
t1 - t0 t 2 - t1 t3 - t 2
t1 - t t2 - t t3 - t
t1 - t0 t 2 - t1 t3 - t 2
P01 (t ) t - t0 1
1
P (t ) t - t1
1
P (t )
2
t 2 - t0 t3 - t1
t2 - t t3 - t
t 2 - t0 t3 - t1
P02 (t ) P12 (t )
t - t0
t3 - t 0
t3 - t
t3 - t 0
P03 (t )
20
 Algorithme d’Aitkem
• Algorithme :
ti + r - t r -1 t - ti r -1 r = 1 .. n
Pi (t ) =
r
Pi (t ) + Pi +1 (t )
ti + r - ti ti + r - ti i = 0 .. n - r

21
 Interpolation polynomiale
• Propriétés
– Précision linéaire
– Invariance par transformation affine
– La courbe P(t) n’est pas contenue dans l’enveloppe
convexe des points interpolés
– La propriété de diminution des variations de la courbe
par rapport au polygone des points Pi n’est pas
satisfaite
• Limitations
– Interprétation géométrique non satisfaisante

22
 Interpolation de points
• Interpolation de points et d’autres informations :
– On ajoute les dérivées (tangentes)…
– Soient les points P0, P1 et les vecteurs tangents D0 et
D1. Trouver une courbe polynomiale cubique P(t)
interpolant ces données
à Interpolants cubique et quintique d’Hermite
• Interpolation polynomiale par morceaux
• Splines
– signifie « latte » (coques de bateaux)
– la latte prend une position qui minimise la torsion

23
Courbes de Bézier
 Polynômes de Bernstein
• Le ième polynôme de Bernstein de degré n est :
ì i n!
B (t ) =
i
n
( )t (1 - t )
n
i
i n -i
avec () n
i
ïC n =
=í i!(n - i )!
si 0 £ i £ n
ïî0 sinon

• Exemple le plus courant : n=3

ì B03 (t ) = (1 - t )3
ï 3
ï B1 (t ) = 3t (1 - t )
2

í 3
ï 2B (t ) = 3 t 2
(1 - t )
ïî B33 (t ) = t 3
25
 Polynômes de Bernstein
• Propriétés
– Stabilité :
• base optimale pour effectuer les principaux calculs
• passage Bernstein – Base canonique (Pn(t) = tn) connu
– Valeurs des polynômes
ìB0n (0) = 1 ì"i ¹ 0 Bin (0) = 0
í n de plus : í
îBn (1) = 1 " ¹ i (1) = 0
n
î i n B
– Positivité
"t Î [0,1] Bin (t ) ³ 0
"t Î]0,1[ Bin (t ) > 0

26
 Polynômes de Bernstein
• Propriétés
– Symétrie
"t Î [0,1] B (t ) = B (1 - t )
i
n n
n -i

– Partition de l’unité
n
"t Î [0,1] å Bin (t ) = 1
i =0
– Relation de récurrence

ìïB00 (t ) = 1
í n
j (t ) = 0 pour j Ï {0, !, n}
n -1 n -1
ïî i
B (t ) = (1 - t ) Bi (t ) + t Bi -1 (t ) avec B n

27
 Polynômes de Bernstein
• Exemples
Bi2 Bi3 B03 B33
B02 B22
B13 B23
B12

ìB02 (t ) = t 2 - 2t + 1 ì B03 (t ) = -t 3 + 3t 2 - 3t + 1
ï 2
B
í 1 (t ) = - 2t 2
+ 2t ï 3
ï B1 (t ) = 3t - 6t + 3t
3 2
ïB 2 (t ) = t 2
î 2 í 3
ï 2B (t ) = - 3 t 3
+ 3 t 2

ïî B33 (t ) = t 3
28
 Polynômes de Bernstein

ì B04 (t ) = t 4 - 4t 3 + 6t 2 - 4t + 1 ì B05 (t ) = -t 5 + 5t 4 - 10t 3 + 10t 2 - 5t + 1

ï 4
ï B (t ) = - 4 t 4
+ 12 t 3
- 12 t 2
+ 4t ï 5
ï 4
1
ï 1 B (t ) = 5 t 5
- 20 t 4
+ 30 t 3
- 20 t 2
+ 5t
í B2 (t ) = 6t - 12t + 6t
4 3 2

ï B 4 (t ) = -4t 4 + 4t 3 ïï B25 (t ) = -10t 5 + 30t 4 - 30t 3 + 10t 2

ï 3 í 5
ï ï 3 B (t ) = 10 t 5
- 20 t 4
+ 10 t 3
î 4 (t ) = t 4
4
B
ï B45 (t ) = -5t 5 + 5t 4
ï 5
ïî29B5 (t ) = t 5
 Courbes de Bézier
• Définition
– Soient (n+1) points Pi de R2 ou R3
– La courbe de Bézier associée à ces points est la courbe
obtenue en prenant comme fonctions de poids les
polynômes de Bernstein de degré n
n
P(t ) = å Pi Bin (t ) "t Î [0,1]
i =0

– Les points Pi sont appelés points de contrôle

– La ligne polygonale P0P1…Pn est appelée polygone
caractéristique de la courbe, ou polygone de contrôle

30
 n
P(t ) = å Pi Bin (t ) "t Î [0,1]
i =0
Exemples de courbes
• Linéaires (degré 1), deux points de contrôle
– P(t) = (1-t)P0 + tP1, t Î [0,1]
• Quadratique (degré 2), trois points de contrôle
– P(t) = (1-t)2P0 + 2t(1-t)P1 + t2P2, t Î [0,1]
• Cubique (degré 3), quatre points de contrôle
– P(t) = (1-t)3P0 + 3t(1-t)2P1 + 3t2(1-t)P2 + t3P3, t Î [0,1]
• Courbes de Bézier de degré supérieur à 3 :
– rarement utilisées
– raccordement de courbes cubiques
• chevauchement de points de contrôle pour assurer la
continuité

31
 n
P(t ) = å Pi Bin (t ) "t Î [0,1]
i =0
Forme matricielle
é P0 ù
P(t ) = [ B0n (t ) B1n (t) " Bnn (t )]êê ! úú
êë Pn úû

ém0,0 " m0,n ù é P0 ù

ê úê ú
P(t ) = [t n t n-1 " 1]ê ! ! úê ! ú
êëmn,0 " mn,n úû êë Pn úû
ì B03 (t ) = -t 3 + 3t 2 - 3t + 1
é -1 3 - 3 1ù ï 3
ï B1 (t ) = 3t - 6t + 3t
3 2
ê 3 -6 3 0úú í 3
M =ê = - +
3 2
n=3: B
ï 2 (t ) 3 t 3 t
ê- 3 3 0 0ú ï B 3
(t ) = t 3
ê ú î 3
ë1 0 0 0û
32
 n
P(t ) = å Pi Bin (t ) "t Î [0,1]
i =0
Caractéristiques
• Les points Pi contrôlent la forme de la courbe

Point de contrôle

Polygone caractéristique

• La courbe est obtenue par pondération des

points de contrôles. Les points sont ordonnés.
• La courbe P est un polynôme de degré n
exactement
• Autres fonctions de base à autre méthode

33
 n
P(t ) = å Pi Bin (t ) "t Î [0,1]
i =0
Propriétés
• Précision linéaire :
– Si les points de contrôle Pi sont alignés, alors la
courbe de Bézier est sur un segment de droite
• La relation entre les points de contrôle est la
courbe est invariante par transformation
affine
• La relation entre les points de contrôle est la
courbe n’est pas invariante par
transformation projective

34
 n
P(t ) = å Pi Bin (t ) "t Î [0,1]
i =0
Propriétés
• Invariance par transformation affine de t :
n n
u-a
–0£t£1àa£u£b: å
i =0
Pi B (t ) = å Pi B (
i
n

i =0
i
n

b-a
)

– Problème simplifié pour les Bézier

– Importance du paramétrage :
Courbe « bien » paramétrée Courbe « mal » paramétrée

35
 n
P(t ) = å Pi Bin (t ) "t Î [0,1]
i =0
Propriétés
• La construction de la courbe de Bézier à partir du
polygone de contrôle est invariante par combinaison
barycentrique :
n n n
a å Pi B (t ) + b å Vi B (t ) = å (aPi + bVi ) Bin (t )
i
n
i
n

i =0 i =0 i =0

• La courbe de Bézier est contenue dans l’enveloppe

convexe des points de contrôle
• Symétrie :
– P0…Pn visuellement identique à Pn…P0
n n

å i
P
i =0
B (t
i
n
) = å n -i i
P
i =0
B n
(1 - t ) car Bi
n
(t ) = Bn -i (1 - t )
n

36
 n
P(t ) = å Pi Bin (t ) "t Î [0,1]
i =0
Propriétés
• La propriété de diminution des variations de la
courbe par rapport au polygone de contrôle
est satisfaite
– aucun plan n’a plus d’intersections avec la
courbe qu’avec le polygone

37
 n
P(t ) = å Pi Bin (t ) "t Î [0,1]
i =0
Propriétés
• Condition aux limites :
– La courbe de Bézier passe par P0 et Pn : P(0) = P0
– Elle est tangente à P0 P1en P0 et à Pn Pnen P
-1 n
• Continuité :
– Une courbe de Bézier de degré n est Cn-1 continue
• Contrôle global
• La dérivée n+pème d’une courbe de Bézier de degré n est nulle
– conséquence : une courbe de Bézier de degré 2 est forcément plane

38
 Calcul d’un point
• Méthode à proscrire :
– Calcul direct des polynômes de Bernstein pour tout t
• Construction d’une parabole à partir de 3 points
P01 (t ) = (1 - t ) P0 + tP1 P02 (t ) = (1 - t ) P01 (t ) + tP11 (t )
P11 (t ) = (1 - t ) P1 + tP2 = (1 - t ) 2 P0 + 2t (1 - t ) P1 + t 2 P2
P1
P11 (t ) P0 P1 P2
P01 (t )
P02 (t ) P01 (t ) P11 (t )
P0 P2
t
P02 (t )
39
 Calcul d’un point
• Algorithme de De Casteljau
ìPi 0 (t ) = Pi , i = 0..n
í r r -1 r -1
P
î i (t ) = (1 - t ) Pi + tPi +1 (t ), r = 1..n, i = 0..n - r

– Alors P0n (t ) est le point de paramètre t sur la courbe de Bézier P(t) de

degré n
P2
P11 (t )
P1
2
t P (t ) 1 (t )
3 P P21 (t )
P02 (t ) 0

P01 (t ) 1-t
P3
P0 t

40
 Algorithme de De Casteljau
P0 = P00 (t ) P1 = P (t )
1
0
P2 = P (t )2
0
P3 = P30 (t )

1- t t 1- t t 1- t t

1
P (t )
0 P11 (t ) P21 (t )

1- t t 1- t t
2
P (t )
0 P12 (t )

1- t t
3
P (t )41
0
 Algorithme de De Casteljau
début
pour i de 0 à n • Formulation récursive à proscrire
• Complexité :
Pi 0 = Pi
finpour – O(n2) (n : degré) pour chaque valeur de t
– Couteux mais stable
pour r de 1 à n
• Convergence :
pour i de 0 à n-r
r -1 r -1
– Augmentation du nombre de points de
Pi = (1 - t ) Pi
r
+ tP
i +1 contrôle
finpour – Quand le nombre de points de contrôle
finpour augmente, la courbe et le polygone de
fin contrôle tendent à se confondre (si points
« bien » répartis)
A la fin, P (t ) = P0n

42
 Algorithme de De Casteljau
• Exemples

43
 Manipulation de Béziers
• Fermeture
– Raccordement C0 : P0 = P5
– Raccordement C1 : P1 – P0 = P5 – P4
– Raccordement C2 : P2 - 2P1 + P0 = P5 – 2P4 + P3

44
 Manipulation de Béziers
• Raccordement C2 de deux courbes de degrés n
– Raccordement C0 : Pn = R0
– Raccordement C1 : Pn – Pn-1 = R1 – R0
– Raccordement C2 : Pn - 2Pn-1 + Pn-2 = R2 – 2R1 + R0

45
 Conclusion sur les Béziers
• Modèle historique
– simple,
– expression de tout polynôme à coefficients vectoriels
– contrôle global bien connu (lissage important)
– peu de paramètres
• Mais
– la complexité augmente avec le nombre de points
– limitation obligatoire du degré (9 à 10 en pratique)
– contrôle global
– pas adapté pour l’interpolation directe d’un nuage
de points

46
Courbes B-Splines
 Fonctions B-Splines
ì( -1) k
(ui+k - u )[u ( k ) : t ](u - t ) k -1
+ pour ui £ u < ui + k
Bi (u ) = í
k i i

î0 pour u < ui et u ³ ui + k
avec å Bik (u) = 1, Bik (u) > 0 pour ui £ u < ui +k
Les différence s divisées [ui (k ) : t ](u - t ) k+-1 = [ui , ui +1 ,..., ui + k : t ](u - t ) k+-1
sont définies par récurrence :
[ui : t ](u - t ) k+-1 = (u - ui ) k+-1
[ui , ui +1 ,..., ui + k : t ](u - t ) k+-1
ì[ui +1 ,!, ui + k : t ](u - t ) k+-1 - [ui +1 ,!, ui + k -1 : t ](u - t ) k+-1
ïï pour ui + k < ui
=í ui + k - ui
ï 1 D(k) (u - t ) k -1
ïî k! t + t = u i pour ui + k < ui
48
 Fonctions B-Splines
ì( -1) k
(ui+k - u )[u ( k ) : t ](u - t ) k -1
+ pour ui £ u < ui + k
Bi (u ) = í
k i i

î0 pour u < ui et u ³ ui + k
avec å Bik (u) = 1, Bik (u) > 0 pour ui £ u < ui +k

Les puissances tronquées (u - ui ) k+-1 sont définies par :

ì1 pour t £ u
(u - t ) + = í
0

î0 pour t > u
ì( u - t) r
pour t £ u
(u - t ) + = í
r

î0 pour t > u

49
 Fonctions B-Splines
• Relation de récurrence
ì1 ui £ u £ ui +1
B (u ) = í
1
i
î0 u < ui et u ³ ui +1
ì u - ui k -1 ui + k - u k -1
ï Bi (u ) + Bi +1 (u ) ui £ u £ ui + k
Bi (u ) = í ui + k -1 - ui
k
ui + k - ui +1
ïî0 u < ui et u ³ ui + k

50
 Fonctions B-Splines
• Vecteur de nœuds
– point de départ : suite non décroissante de
valeurs t0 £ t1 £ ! £ tm
– les ti sont appelés les nœuds
– la suite des ti s’appelle vecteur de nœuds
– les ti peuvent être entiers ou réels
t0 t1 ti ti +1 tm

51
 Fonctions B-Splines
• Fonctions B-Splines normalisées d’ordre k définies sur le
vecteur de nœuds
– soit k un entier fixé > 1
– (m-k+1) fonctions polynomiales par morceaux de degré k-1 notées
: ik
vérifiant B
m-k
1) å Bik = 1 partition de l’unité
i =0

2) "i, "k , Bik ³ 0 positivité

3) Bik = 0 si t Ï [ti , ti + k ] support local
4) Bik est C k - 2 continue sur [t0 , t m ]

52
 Fonctions B-Splines
• Interprétation : la fonction Bik est
– non nulle sur [ti,ti+k]
– nulle en dehors
– un polynôme de degré k-1 sur chaque [tj,tj+1]
(j=i, i+1, …, i+k-1)
• De plus
– les k polynômes se raccordent en Ck-2
– la continuité implique : Bik (ti ) = Bik (ti +k ) = 0

53
 Fonctions B-Splines
• Fonctions avec des nœuds équidistants :

une Bi5

B05 5
B
1
5
B
2
B35 B 5
4
B55 B65 B75

54
 Fonctions B-Splines
• Fonctions avec des nœuds équidistants :
– ordre 2 (k=2, degré=1)
ìt si 0 £ t £ 1
B (t ) = í
2
0
î(2 - t ) si 1 £ t £ 2
– ordre 3
ìt 2
ï si 0 £ t £ 1
ï2 2
ï (-2t + 6t - 3)
B0 (t ) = í
3
si 1 £ t £ 2
ï 2
ï (3 - t ) 2
si 2 £ t £ 3
ïî 2
55
 Fonctions B-Splines
• Influence de la répartition des nœuds (ordre 4)
– vecteur des nœuds : 4, 5, 6, 14, 15

– vecteur des nœuds : 4, 10, 11, 14, 15

56
 Fonctions B-Splines
• Superposition de nœuds (ordre 4)
vecteur des nœuds : vecteur des nœuds :
0, 0, 0, 0, 1, 1, 1, 1 0, 0, 0, 0, 1, 2, 3, 3, 3, 3

B 4 B34
0

B1
4
B24

57
 Fonctions B-Splines
• Superposition de nœuds (ordre 3)
1, 1, 3, 3 1, 1, 2, 3

1, 1, 1, 3 1, 2, 2, 3

58
 Fonctions B-Splines
• Superposition de nœuds (ordre 4)
1, 1, 2, 3, 4 1, 1, 1, 2, 3

1, 2, 2, 2, 3
1, 1, 1, 1, 3

59
 Courbes B-Splines
• Définition
– Soient (n+1) points Pi de R2 ou R3
– La courbe B-Spline associée à ces points est la courbe
obtenue en prenant comme fonctions de poids un
ensemble de fonctions de base
n
P(t ) = å Pi Bik (t )
i =0

– Les points Pi sont appelés points de contrôle

– La ligne polygonale P0P1…Pn est appelée polygone
caractéristique de la courbe, ou polygone de contrôle

60
 Courbes B-Splines
• Il faut choisir un ordre k et un vecteur de nœuds
– k choisi en premier
• degré de continuité souhaité
• pour avoir des polynômes de degré le plus bas possible
• très souvent, k = 4
– nombre de nœuds
• nombre de nœuds : n + k + 1
• vecteur de nœuds T : t0, t1, ... tn+k
– choix des nœuds
• on prend en général t0 = t1 = … = tk-1 < tk < … < tn < tn+1 = tn+2 = … =
tn+k
• l’intervalle de travail est toujours [tk-1, tn+1]
– vaste problème

61
 Courbes B-Splines
• Propriétés
– P(t) est le barycentre des points Pi affectés des masses Bik
– Enveloppe convexe
– Caractère local : P(t) ne dépend que de k points de contrôle
– Invariance par transformations affines
– Passage par les points extrêmes
– Propriété de diminution des variations
– Propriété de reproduction de la linéarité
– Si un point apparait plusieurs fois, P(t) est tirée vers ce point
– La courbe est plus proche des points de contrôle qu’une courbe
de Bézier
– Les courbes de Bézier sont un cas particulier des B-Splines

62
 Calcul d’un point
• Algorithme de De Boor – Cox (De Casteljau)
début
pour m de i-k+1 à i k-1 ≤ i ≤ n
Pm1 = Pm ti ≤ t ≤ ti+1 avec ti < ti+1
finpour ([ti ,ti+1] vrai intervalle)
pour j de 1 à k-1
pour m de i-k+j+1 à i
j +1
(t - t m ) Pm
j
+ (t m+ k - j - t ) P j
m -1
Pm =
tm+ k - j - tm
finpour
finpour
fin A la fin, P (t ) = Pi k
63
 Dessin d’une courbe
Exemple : n=6, k=4, 11 nœuds
P2 P3
Approxime P1, P2, P3, P4

Approxime P2, P3, P4, P5

Approxime P0, P1, P2, P3

P6

Approxime P3, P4, P5, P6

P0
P1 P5 P4
64
 Choix du vecteur de
nœuds
Exemple : n=6, k=4, 11 nœuds
• Nœuds répartis uniformément
P2 P3

i=4, 4 ≤ t ≤ 5

i=3, 3 ≤ t ≤ 4
P6 i=5, 5 ≤ t ≤ 6

i=6, 6 ≤ t ≤ 7
P0
P1 P5 P4
0 1 2 3 4 5 6 7 8 9 10

t0 t1 t2 t3 t4 t5 t6 t7 t8 t9 t10
65
 Choix du vecteur de
nœuds
Exemple : n=6, k=4, 11 nœuds
• Nœuds confondus P3
P2

i=4, 1 ≤ t ≤ 2

P6 i=5, 2 ≤ t ≤ 3

i=3, 0 ≤ t ≤ 1 i=6, 3 ≤ t ≤ 4

P0
P1 P5 P4
0 1 2 3 4

t0 t1 t2 t3 t4 t5 t6 t7 t8 t9 t10
66
 Lien avec les Béziers
P2 B-Spline nœuds uniformes
P3
B-Spline nœuds confondus

Bézier
P6

P0
P1 P4
P5

67
 Rappel : interpolation
Interpolation (Aitkem)
P2
P3

P6

P0

P5
P1 P4

68
 Fermeture d’une B-Spline
• Fermeture C0
– Premier point de contrôle = dernier point de contrôle

• Fermeture C1 / G1 (méthode 1)
– Alignement de P0, P1, P6

69
 Fermeture d’une B-Spline
• Fermeture C1 / G1 (méthode 2)
– Ajout de 2 nœuds è deux points de plus

– Alignement de P0, P1’, P6’

70
 Conclusion sur les B-Splines

• Béziers : cas particulier des B-Splines

• B-Splines : Modèle opérationnel actuellement
– Plus souple que Bézier
• contrôle local
• degré
• vecteur de points
• Inconvénients
– complexité algorithmique plus importante
– difficile de maîtriser le vecteur de nœuds

71
Surfaces paramétriques
 Surface réglée
• Une surface est réglée si et seulement si par tout point il
passe au moins une droite entièrement contenue dans la
surface.
• On définit une surface réglée par deux courbes P1(u) et
P2(u) sur lesquelles s'appuient les droites de la surface.
• Exemples :
– Le cône est une surface réglée dont toutes les droites (appelées
directrices) sont concourantes au sommet.
Les directrices s'appuient sur le sommet et sur un cercle non
coplanaire avec le sommet.
– Le cylindre est une surface réglée dont toutes les droites sont
parallèles à l'axe.
• Un patch réglé est un morceau de surface réglée obtenu en
limitant les valeurs de u et v à des intervalles finis.

73
Surface réglée

74
 Patch bilinéaire
• Un patch bilinéaire est un morceau de surface réglée telle que P0(u) et
P1(u) sont des segments de droites.

75
 Carreaux de Coons bilinéaires
• Interpolation de courbes frontières à l’aide
d’opérateurs booléens
• On dispose de 4 courbes frontière à interpoler
: F(u,0)
– F(u,0) F(0,v)

– F(u,1)
– F(0,v) F(u,1)

– F(1,v) F(1,v)

u v
76
 Carreaux de Coons bilinéaires
• Surfaces réglées s’appuyant sur les courbes frontières :
F(u,0)
P1F F(0,v) P2F

F(u,1)
F(1,v)

u v u v

P1F = (1-u) F(0,v) + u F(1,v) P2F = (1-v) F(u,0) + v F(u,1)

77
 Carreaux de Coons bilinéaires
• Patch bilinéaire s’appuyant sur les points extrêmes :

P1P2F F(0,0)

F(1,0)
F(0,1)

P1P2F = (1-u) (1-v) F(0,0)

F(1,1) + u (1-v) F(1,0)
+ (1-u) v F(0,1)
u v
+ u v F(1,1)

78
 Carreaux de Coons bilinéaires
• Le patch de Coons est obtenu en ajoutant les surfaces réglées
et en retranchant le patch bilinéaire

P1 Å P2 F

P1 Å P2 F = P1F + P2F – P1P2F

79
 Carreau de Coons bicubiques
• En plus des 4 courbes frontière, on utilise les
dérivées le long de ces courbes :
– Fv(u,0)
– Fv(u,1)
– Fu(0,v)
– Fu(1,v)
• On remplace les fonctions de base (1-u, u, 1-v, v) par
les polygones cubiques d’Hermite :
– h03(t) = 2t3-3t2+1
– h02(t) = -2t3+3t2
– h01(t) = t3-2t2+t
– h00(t) = t3-t2
80
 Carreau de Coons bicubiques
é F (0, v) ù
ê F (1, v) ú
[
P1 F (u, v) = h03 (u ) h13 (u ) h23 (u ) h33 (u ) ê]
ê Fu (0, v)ú
ú
ê ú
F
ë u (1, v ) û
éh03 (v)ù
ê 3 ú
h (v )
P1 F (u, v) = [F (u,0) F (u,1) Fv (u,0) Fv (u,1)] ê 13 ú
êh2 (v)ú
ê 3 ú
êëh3 (v)úû
é F( 0,0 ) F( 0,1 ) Fv( 0,0 ) Fv( 0,1 ) ù éh03 (v)ù
ê F( 1,0 ) F( 1,1 ) F ( 1,0 ) F ( 1,1 ) ú ê 3 ú
[
P1 P2 F (u, v) = h03 (u ) h13 (u ) h23 (u ) h33 (u ) ê ] v v ú êh1 (v)ú
ê Fu( 0,0 ) Fu( 0,1 ) Fuv( 0,0 ) Fuv( 0,1 )ú êh23 (v)ú
ê úê 3 ú
F
ë u ( 1,0 ) Fu ( 1,1 ) Fuv ( 1,0 ) Fuv ( 1,1 ) û êëh3 (v)úû
P1 Å P2 F = P1F + P2 F - P1P2 F
Eléments de torsion
(carré de Gregory)
81
 Carreau de Coons bicubiques
• Eléments de torsion : carré de Grégory
¶ ¶
u Fu (0,0) + v Fv (0,0)
Fuv (0,0) = ¶v ¶u
u+v
¶ ¶
u Fu (0,1) + (1 - v) Fv (0,1)
Fuv (0,1) = ¶v ¶u
u + (1 - v)
¶ ¶
(1 - u ) Fu (1,0) + v Fv (1,0)
Fuv (1,0) = ¶v ¶u
(1 - u ) + v
¶ ¶
(1 - u ) Fu (1,1) + (1 - v) Fv (1,1)
Fuv (1,1) = ¶v ¶u
(1 - u ) + (1 - v)

82
 Carreaux rectangulaires de Bézier
• Principe
– Soit une courbe C0
– Déformons C0 vers une nouvelle position C1
– Supposons que la déformation soit continue
– Chaque point C0(u) décrit une courbe Su(v) pour
arriver en C1(u)

83
 Carreaux rectangulaires de Bézier
• Surface bicubique de Bézier 16 points de contrôle Pij
4 points Mk(t) sur les courbes
cubiques de Bézier définies
par Pkj
Le point N(t,s) sur la courbe
de Bézier définie par les 4
points Mk(t) précédents

84
 Carreaux rectangulaires de Bézier
• Produit tensoriel à partir des polygones de Bernstein
m n
• Forme explicite : P(u, v) = åå Pi , j Bim (u ) B nj (v)
i =0 j =0

• Forme matricielle :
é P00 " P0 n ù é B0 (v)ù
n

[ ê
P(u, v) = B0 (u ) " Bm (u ) ê !
m m
] ú ê
! úê ! ú
ú

êë Pm0 " Pmn úû êë Bnn (v)úû

maillage des points de contrôle de Bézier

85
 Carreaux rectangulaires de Bézier
• Exemple avec 16 points de contrôle

86
 Carreaux rectangulaires de Bézier
• Propriétés : les mêmes que pour les courbes
• Perte de convexité :

87
 Calcul d’un point
• Interpolation bilinéaire de 4 points
P0,0, P0,1, P1,0 et P1,1
P0 ,1 P1,1
ìP00,0,1 = (1 - v) P0,0 + vP0,1
P00,0,1 P10,0,1 í 0,1
P01,,01 î P1,0 = (1 - v) P1,0 + vP1,1
P01,,01 = (1 - u)vP00,0,1 + uvP10,0,1
P0, 0 P1, 0
P01,,01 = (1 - u)(1 - v) P0,0 + (1 - u)vP0,1 + u(1 - v) P1,0 + uvP1,1
é P0,0 P0,1 ù é1 - vù
P(u, v) = [1 - u u ] ê
ë P1,0 P1,1 úû êë v úû
88
 Algorithme de De Casteljau
• Pour m=n

ì Pi ,0j, 0 (u , v) = Pi , j
ï
í r ,r é P r -1, r -1
Pi ,rj-+11,r -1 ù é1 - v ù
P (u , v ) = [1 - u u ] i, j
ê r -1,r -1 r -1, r -1 ú ê
ï i, j
î êë Pi +1, j Pi +1, j +1 úû ë v úû

Alors Pi ,nj,n (u, v) est le point de paramètre (u,v) sur la surface

89
 Algorithme
P P
de De Casteljau
0,3 1, 3
P2,3
P01,,21
P11, 2,1 P3,3

P21,,21
P1, 2 P03,0,3
P0, 2
v P02,1, 2 P2, 2
1,1 P1,21, 2 P3, 2
P 0,1
P1,1 P11,1,1 P21,,11
P0 ,1
P02, 0, 2 P2 ,1
P1,20, 2 P3,1

P01,,01
P11,0,1
P0, 0
P21,,01

u P1, 0
P2, 0 90 P3, 0
 Algorithme de De Casteljau
début
pour i de 0 à n
pour j de 0 à n
Pi ,0j,0 = Pi , j
finpour
finpour
pour r de 1 à n
pour i de 0 à n-r
pour j de 0 à n-r
Pi ,rj,r = (1 - u )(1 - v) Pi ,rj-1,r -1 + (1 - u )vPi ,rj-+11,r -1
+ u (1 - v) Pi +r 1-,1j,r -1 + uvPi +r 1-,1j,r+-11
finpour
finpour A la fin,
finpour
fin P(u, v) = P0n,0,n
91
 Algorithme de De Casteljau
P1, 2
P0, 2 P2, 2
• Pour m≠n P11,1,1 P3, 2
k = min(m,n) P 1,1
0,1
P21,,11
P0 ,1 P02, 0, 2
P1,20, 2 P3,1
v

P01,,01
P11,0,1
P0, 0 P21,,01

u P1, 0
P2, 0 P3, 0
Pi ,kj,k
forme un polygone de contrôle d’une courbe de Bézier
On applique l’algorithme à une variable de De Casteljau
92
Raccordement de carreaux

93
Raccordement de carreaux

94
 NURBS
• Non Uniform Rational B-Splines
• Objectif : représenter sous un même formalisme
– les courbes et surfaces de forme libre
– des primitives :
• cercles
• coniques (paraboles, hyperboles…)
• quadriques (cylindres, sphères, cônes…)
• …
• NURBS : implémentation de courbes et surfaces
paramétriques OpenGL

95
NURBS

96
 NURBS
• Les surfaces NURBS s'obtiennent par extension de la
définition des courbes NURBS :
– deux vecteurs de nœuds T et S, un pour chacune des
variables t et s,
– (m+1) x (n+1) points de contrôle Pi,k
– (m+1) x (n+1) fonctions de pondération Rm,n.i,k déduites des
fonctions de pondération des B-splines Sm,k au moyen de
(m+1) x (n+1) poids wi,k :
wi ,k S m,i (t ) S n,k ( s)
Rm,n,i ,k (t ) =
åw j ,l S m, j (t ) S n,l ( s) N (t , s) = å Rm,n,i ,k (t ) Pi ,k
j ,l i ,k

97
 NURBS
• Exemple OpenGL / GLU

Source du code : The OpenGL Red Book

[Link]
98
 NURBS
• Exemple OpenGL / GLU

Source du code : The OpenGL Red Book

[Link]

99
 PN triangles
• Principe
– Une surface construite à partir de 3 sommets et
de leurs 3 normales
– La surface « la plus simple » : pas de données
supplémentaires (triangles voisins…)
– Résultat : on « tire » la surface vers les plans
tangents
• Détails : Curved PN triangles, A. Vlachos, J.
Peters, C. Boyd, J.-L. Mitchell, 2001
100
 PN triangles
• Principe
– Construction de 9 points de contrôle à partir des 3
sommets et de leurs normales
– La surface est définie par un polynôme de degré 3
s’appuyant sur les points de contrôle
– L’évaluation d’un point de la surface (pour une
valeur des paramètres u, v et w) fournit un point
de la surface

101
 PN triangles
• Construction des points de contrôle
– À partir d’un sommet, de sa normale et d’une arête
– Projette un point de l’arête sur le plan tangent

102
 PN triangles

• Evaluation de polynôme
– p(u,v)w=1-u-v = b300w3 + b030u3 + b003v3
+ b2013w2u + b1203wu2 + b2013w2v
+ b0213u2v + b1023wv2 + b0123uv2
+ b1116wuv

103
 PN triangles
• Evaluation des points de la surface
– Domaine paramétrique (u, v, w)
– Contraintes :
• u+v+w=1
• 0 £ u £ 1 et 0 £ v £ 1 et w = 1 – u – v
• Rappel
– On peut évaluer les points d’un triangle abc de la
même manière : p(u, v)w=1-u-v = wA + uB + vC

104
 PN triangles
• Domaine paramétrique
– p(0,0,1) = A
– p(1,0,0) = B
– p(0,1,0) = C
C C
C v=1
w=0 u=1

w=1 B u=0
A A B A v=0 B
• Exercices
– Quelles sont les valeurs de u et v pour le milieu du triangle ?
– Quelle position (x, y, z) correspond au milieu du triangle ?
– Mêmes questions pour le milieu de chaque arête du triangle

105
PN triangles

106
PN triangles

107
 Seconde partie
Courbes et surfaces de
subdivision
 Surfaces paramétriques
• Carreaux de Bézier, B-splines, NURBS...
• Avantages
– Modélisation par carreau type couture
– Chaque carreau est défini par un polygone de contrôle
• Difficultés
– contrôle des connexions entre carreaux
– ajuster la surface à un polygone de contrôle quelconque

109
 Surfaces de subdivision

maillage initial après 1 pas de après 2 pas de surface limite

subdivision subdivision

110
 1ère utilisation
• Geri’s Game (1998) : Pixar Animation Studios

111
 Principe
P0,0 P0,1 P0,2

P1,0 P1,1 P1,2

P2,0 P2,1 P2,2

112
 Principe
1 6 1
P0,0 P0,1 P0,2

6 36 6

1 6 1
P1,0 P1,1 P1,2
Q 1 6 1
Q= P0,0 + P0,1 + P0, 2
64 64 64
6 36 6
P2,0 P2,1 P2,2 + P1,0 + P1,1 + P1, 2
64 64 64
1 6 1
+ P2, 0 + P2,1 + P2, 2
64 64 64
1. Chaque sommet Pi,j est déplacé
La nouvelle position Q dépend - de Pi,j
- de ses voisins
113
è notion de masque
 Principe
4 4
P0,0 P0,1 P0,2
24 24

4 4
P1,0 P1,1 P1,2
R
R = 4 P0,0 + 4 P0,1
64 64
P2,0 P2,1 P2,2 24 24
+ P1,0 + P1,1
64 64
4 4
+ P2,0 + P2,1
2. De nouveaux points sont insérés 64 64
a. sur chaque arête

114
 Principe
16 16
P0,0 P0,1 P0,2
16 16

S
P1,0 P1,1 P1,2

S = 16 P0, 0 + 16 P0,1
64 64
P2,2 16 16
+ P1, 0 + P1,1
64 64

2. De nouveaux points sont insérés

b. sur chaque face (éventuellement)

115
 Principe

Les étapes 1 et 2 sont répétées sur tout le maillage initial

116
 Principe
64
64

32
64

32
8 48 8 64
64 64 64
Masques spécifiques pour les bords

117
 Principe

Catmull-Clark
(grille rectangulaire)

Les nouveaux points sont maillés

è tout ceci correspond à un pas de subdivision
è à réitérer jusqu'à la surface limite
118
 Principe
• Relativement facile avec un maillage régulier fermé
• Autres masques pour
– maillages quelconques
– bords
• Disposer d'une structure de données permettant
"pour chaque sommet, arête, face…",
"couper une face en deux…"
...

119
Courbes de subdivision
 Principe
• Courbe limite à partir d'un carré
Chaque arête est coupée en 2
Courbe limite

Chaque arête est coupée en 3

Courbe limite

121
 B-Splines uniformes
(rappel)
• Courbes B-Splines uniformes
é P0 ù
P(t ) = [t n t n -1 " 1] M êê ! úú
êë Pn úû

• Quadratique (n=2) Quintique (n=3)

é 1 - 2 2ù é -1 3 - 3 1ù
ê 3 -6 3 0úú
M = êê- 2 2 0úú
M =ê
êë 1 0 0úû ê- 3 3 0 0ú
ê ú
ë1 0 0 0û
122
 B-Splines uniformes quadratiques
• Courbes B-Splines uniformes é 1 - 2 1ù é P0 ù
P(t ) = [t 2 t 1] êê- 2 2 0úú êê P1 úú
êë 1 0 0úû êë P2 úû

1ère moitié 2ème moitié

de la courbe de la courbe

123
 B-Splines uniformes quadratiques
• 1ère moité de la courbe
2 é 1 - 2 1ù é P0 ù
ætö ætö t
P[ 0,1/ 2 ] (t ) = Pç ÷ = [ç ÷ 1] êê- 2 2 0úú êê P1 úú
è2ø è2ø 2
êë 1 0 0úû êë P2 úû
é1 0 0 ù é P0 ù é 1 - 2 1ù
= [t 2 t 1] êê0 1 / 2 0 úú M êê P1 úú avec M = êê- 2 2 0úú
êë0 0 1 / 4úû êë P2 úû êë 1 0 0úû
é1 0 0 ù é P0 ù
= [t 2 t 1]MM -1 êê0 1 / 2 0 úú M êê P1 úú
êë0 0 1 / 4úû êë P2 úû
æ é1 0 0 ù ö é P0 ù
ç -1 ê ú ÷ê ú
= [t t 1]M ç M ê0 1 / 2 0 ú M ÷ ê P1 ú
2

ç êë0 0 1 / 4úû ÷ø êë P2 úû
è
éQ0 ù éQ0 ù æ é1 0 0 ù ö é P0 ù é3 1 0ù é P0 ù é3P0 + P1 ù
ç -1 ê ÷ê ú 1 ê 1ê
= [t 2 t 1]M êê Q1 úú avec ê Q1 ú = ç M ê0 1 / 2 0 ú M ÷ ê P1 ú = ê1 3 0ú ê P1 ú = ê P0 + 3P1 úú
ê ú ú ú ê ú
4 4
êëQ2 úû êëQ2 úû çè êë0 0 1 / 4úû ÷ø êë P2 úû êë0 3 1úû êë P2 úû êë3P1 + P2 úû

124
 B-Splines uniformes quadratiques
• 1ère moitié de la courbe 2ème moitié de la courbe
é P0L ù é P0R ù
ê ú ê ú
P L (t ) = [t 2 t 1]M ê P1L ú P R (t ) = [t 2 t 1]M ê P1R ú
ê P2L ú ê P2R ú
ë û ë û
é P0L ù é3 1 0ù é P0 ù é3P0 + P1 ù é P0R ù é1 3 0ù é P0 ù é P0 + 3P1 ù
ê Lú 1 ê ú ê P ú = 1 ê P + 3P ú ê Rú 1 ê ú ê P ú = 1 ê3P + P ú
P
ê 1 ú 4ê= 1 3 0 ú ê 1ú 4 ê 0 1ú P
ê 1 ú 4ê= 0 3 1 ú ê 1ú 4 ê 1 2ú
ê P2L ú êë0 3 1úû êë P2 úû êë3P1 + P2 úû ê P2R ú êë0 1 3úû êë P2 úû êë P1 + 3P2 úû
ë û ë û

125
 B-Splines uniformes quadratiques
é P0L ù é3 1 0ù é P0 ù é P0R ù é1 3 0ù é P0 ù
• On regroupe ê Lú 1 ê
P = 1 3 0 ú êP ú ê Rú 1 ê
P = 0 3 1 ú êP ú
ê ú 4ê
1 ú ê 1ú ê ú 4ê
1 ú ê 1ú
ê P2L ú êë0 3 1úû êë P2 úû ê P2R ú êë0 1 3úû êë P2 úû
ë û ë û

à algorithme de Chaikin

éQ0 ù é3 1 0ù é3P0 + P1 ù
êQ ú é 0ù
P
1
ê 1ú = ê
ê1 3 0úú ê ú 1 êê P0 + 3P1 úú
ê P1 ú =
êQ2 ú 4 ê0 3 1ú 4 ê3P1 + P2 ú
ê ú ê ú êë P2 úû ê ú
Q
ë 3û ë0 1 3û P
ë 1 + 3 P2û

126
 Schéma de Chaikin
• Encore appelé corner-cutting
éQ0 ù é3 1 0ù é3P0 + P1 ù é3 1 ù
êQ ú é 0ù
P
1
ê 1ú = ê
ê1 3 0úú ê ú 1 êê P0 + 3P1 úú P + P
éQ2i ù ê 4 i 4 i +1 ú
êQ2 ú 4 ê0 3 1ú ê P1 ú =
4 ê3P1 + P2 ú
à êQ ú = ê 1 3 ú
ë 2i +1 û ê Pi + Pi +1 ú
ê ú ê ú êë P2 úû ê ú ë4 4 û
Q
ë 3û ë0 1 3û P
ë 1 + 3 P2û
Pi-1 Pi+1
Q2i-2 Q2i+1

Q2i-1
Q2i

Pi

127
 Schéma de Chaikin
( Pi ) 0£i £ n -1 ® (Q j ) 0£ j £ 2 n -3
• Schéma régulier approximant
ì Q2i = aPi + (1 - a) Pi +1 3 1
Pour 0 £ i £ n-2 í avec a = et b =
îQ2i +1 = bPi + (1 - b) Pi +1 4 4

128
 Schéma de Catmull-Clark
( Pi ) 0£i £ n -1 ® (Q j ) 0£ j £ 2 n - 4
• Schéma régulier approximant
ì 1 1
ï Pour 0 £ i £ n-1 Q2i = 2 Pi + 2 Pi +1
í 1 6 1
ï Pour 0 £ i £ n-2 Q2i +1 = Pi + Pi +1 + Pi + 2
î 8 8 8
Pi-1 Pi+1

Q2i-2
Q2i+1
Q2i-1
Q2i

Pi

129
 Schéma de Catmull-Clark
( Pi ) 0£i £ n -1 ® (Q j ) 0£ j £ 2 n - 4
• Schéma régulier approximant
ì 1 1
ï Pour 0 £ i £ n-1 Q2i = 2 Pi + 2 Pi +1
í 1 6 1
ï Pour 0 £ i £ n-2 Q2i +1 = Pi + Pi +1 + Pi + 2
î 8 8 8

130
 Four points scheme
( Pi ) 0£i £ n -1 ® (Q j ) 0£ j £ 2 n - 2
• Schéma régulier interpolant
ì Pour 0 £ i £ n-1 Q2i = Pi
ï
í Pour 1 £ i £ n-3 Q = - 1 P + 9 P + 9 P - 1 P
ïî 2 i +1
16
i -1
16
i
16
i +1
16
i+2

ì 3 6 1
ïQ1 = 8 P0 + 8 P1 - 8 P2
Conditions aux bords í
1 6 3
ïQ2 n -3 = - Pn -3 + Pn - 2 + Pn -1
î 8 8 8

131
 Four points scheme
( Pi ) 0£i £ n -1 ® (Q j ) 0£ j £ 2 n - 2
• Schéma régulier interpolant
ìPour 0 £ i £ n-1 Q2i = Pi
ï
íPour 1 £ i £ n-3 Q = - 1 P + 9 P + 9 P - 1 P
ïî 2i +1
16
i -1
16
i
16
i +1
16
i+2

Pi-1 Q2i-2 Pi+1

Q2i-1

Q2i+1

Q2i
Pi

132
 Four points scheme
( Pi ) 0£i £ n -1 ® (Q j ) 0£ j £ 2 n - 2
• Schéma régulier interpolant
ìPour 0 £ i £ n-1 Q2i = Pi
ï
íPour 1 £ i £ n-3 Q = - 1 P + 9 P + 9 P - 1 P
ïî 2i +1
16
i -1
16
i
16
i +1
16
i+2

133
 Four points scheme
• Problèmes d'oscillation

La convexité du polygone de contrôle n'est pas

toujours respectée dans la courbe limite
134
 Fractale chou fleur
( Pi ) 0£i £ n -1 ® (Q j ) 0£ j £ 2 n - 2
• Schéma fractal interpolant
ì Pour 0 £ i £ n-1 Q2i = Pi
ï
í Pour 0 £ i £ n-2 Q = 1 ( P + P ) + 1 N ( P - P )
ïî 2 i +1
2
i i +1
3
i +1 i

avec pour un point P = (x,y) , N(P) = ( - y,x)

Q2i+1

1/3
Pi Pi+1 Q2i Q2i+2

1/2

135
 Fractale
flocon de Von Koch
( Pi ) 0£i £ n -1 ® (Q j ) 0£ j £ 4 n - 4
• Schéma fractal interpolant
ì Pour 0 £ i £ n-1 Q4i = Pi
ï ì 1
ï ïQ4i +1 = 3 (2 Pi + Pi +1 )
ïï ï
í Pour 0 £ i £ n-2 ïQ = 1 ( P + P ) + 5 N ( P - P )
ï í 4i + 2 i i +1 i +1 i
ï 2 6
ï 1
ï ï Q4i +3 = ( Pi + 2 Pi +1 )
ïî ïî 3
avec pour un point P = (x,y) , N(P) = ( - y,x) Q4i+2
Pi Pi+1 Q4i Q4(i+1)

Q4i+1 Q4i+3
136
Surfaces de subdivision

(loop)
 Schémas principaux
Doo-Sabin Û Surface B-Spline quadratique uniforme
approximant (équivalent aux courbes de Chaikin)
maillages de quadrilatères ou quelconques

Catmull-Clark Û Surface B-Spline cubique uniforme

approximant
maillages de quadrilatères ou quelconques

Loop Û Surface Box-Spline quadrique uniforme

approximant
maillages triangulaires

Butterfly
interpolant
maillages triangulaires 138
 Schémas principaux
Doo-Sabin Catmull-Clark Loop Butterfly

139
 Schéma de Doo-Sabin
• Malcolm A. Sabin (11/2008)

140
 Schéma de Doo-Sabin
• Principe du corner cutting (Chaikin)
• Schéma approximant (ne passe pas par les sommets
originaux)
• Fonctionne sur des maillages quelconques
• Surface B-Spline Quadratique
• C1 continue
• Après 1 subdivision :
– tous les sommets sont de valence 4

141
 Doo-Sabin pour les maillages quadrangulaires réguliers

• Surfaces B-Splines uniformes quadriques

T
é 1 - 2 1ù é P0,0 P0,1 P0, 2 ù é 1 - 2 1ù év2 ù
[ ] ê
P(u, v) = u 2 u 1 êê- 2 2 0úú ê P1,0 P1,1
ú
P1, 2 ú êê- 2 2 0úú êê v úú
êë 1 0 0úû êë P2,0 P2,1 P2, 2 úû êë 1 0 0úû êë 1 úû

• 1er quart de la surface :

T
é3 1 0ù é P0,0 P0,1 P0, 2 ù é3 1 0ù év 2 ù
æu vö
[ ]
1ê ú ê
P[ 0,1/ 2] (u, v) = Pç , ÷ = u u 1 ê1 3 0ú ê P1,0
2
P1,1
ú1ê ú ê ú
P1, 2 ú ê1 3 0ú ê v ú
è 2 2ø 4 4
3 1úû êë P2,0
êë0 142 P2,1 P2, 2 úû êë0 3 1úû êë 1 úû
 Doo-Sabin pour les maillages quadrangulaires réguliers

P0,0 P0,1 1
P0',0 = (9 P0,0 + 3P0,1 + 3P1,0 + P1,1 )
P0,2 16
1
P0',1 = (3P0, 0 + 9 P0,1 + P1,0 + 3P1,1 )
16
P1,0
P1,2 1
P1',0 = (3P0, 0 + P0,1 + 9 P1,0 + 3P1,1 )
16
P2,0 P2,2 1
P2,1 P1,1 = ( P0,0 + 3P0,1 + 3P1,0 + 9 P1,1 )
'

16

• Pour chaque face 9 3

– pour chaque sommet de cette face
• créer un sommet à partir du masque 3 1

143
 Doo-Sabin pour les maillages quadrangulaires réguliers

• Après une subdivision

• Masques spécifiques pour les bords (pour "coller" au

bord)

144
 Doo-Sabin pour les maillages quelconques

• Autre formulation
1
E0 = ( P0, 0 + P1,0 ) E1
2 P0,0
1
E1 = ( P0, 0 + P0,1 ) P0,1
2
P’
1
F = ( P0, 0 + P0,1 + P1, 0 + P1,1 ) E0 F
4

1
P' = ( P0,0 + E0 + E1 + F )
4 P1,0 P1,1
1 1 1 1
= ( P0,0 + ( P0,0 + P1,0 ) + ( P0,0 + P0,1 ) + ( P0,0 + P0,1 + P1,0 + P1,1 ))
4 2 2 4
1 4 2 2 2 2 1 1 1 1
= ( P0,0 + P0,0 + P1,0 + P0,0 + P0,1 + P0,0 + P0,1 + P1,0 + P1,1 )
4 4 4 4 4 4 4 4 4 4
1
= (9 P0,0 + 3P1,0 + 3P0,1 + P1,1 )
16
145
 Doo-Sabin pour les maillages quelconques

Un edge-point est le milieu d'une arête

Un face-point est le centre d'une face
Un nouveau point est la moyenne
- d'un ancien point
- d'un face-point d'une face incidente à l'ancien point
- des deux edge-points incidents à l'ancien point et à la face
146
Les nouveaux points sont reliés entre eux
 Schéma de Catmull-Clark
• Schéma approximant
• Fonctionne sur les maillages quadrangulaires ou quelconques
• Surface B-Spline cubique
• G1 continue (sauf points extraordinaires)
• Après une subdivision :
– toutes les faces sont des quadrilatères

147
 Schéma de Catmull-Clark

1 n
Face f = å vi
n 1

v1 + v2 + f1 + f 2
Arête
e=
4

n-2 1 1
Sommet vi +1 =
n
vi + 2
n
å e j + n2 åf j
j j
148
 Catmull-Clark
Gestion des arêtes vives

1. Marquer chaque arête comme vive ou non vive

• n = 0 à non vive
• n > 0 à vive
Pendant la subdivision :
2. Si une arête est vive, alors on utilise les nouvelles regles.
Les nouvelles arêtes créées sont associées à n-1.
3. Si une arête est non vive, alors on utilise les règles de
subdivision normales.
149
 Catmull-Clark
Gestion des arêtes vives
1 n
Face (inchangé) f = å vi
n 1

Arête v1 + v2
e=
2
Nombre d’arêtes
Sommet vives adjacentes

pointe >2 vi +1 = vi
e1 + 6vi + e2
angle =2 vi +1 =
8
n-2 1 1
coin 0,1 vi +1 =
n
vi + 2
n
åj e j + n 2 åf
j
j

150
 Doo-Sabin
vs Catmull-Clark

Doo-Sabin

Catmull-Clark

151
 Doo-Sabin
vs Catmull-Clark

Doo-Sabin

Catmull-Clark

152
 Schéma de Loop
• Schéma approximant
• Fonctionne sur maillages triangulaires quelconques
• Surface Box-Spline quadrique
• G1 continuité, sauf aux points extraordinaires
• Simple à mettre on œuvre
– 2 masques pour les sommets internes
– 2 masques pour les sommets du bord

153
 1
8 Loop
Masques de subdivision
3 3
8 8

1
8
an an
n n
an an
n n
an 1-an
an
n
n
1 æç ö
2
æ æ 2p öö ÷
an = 40 - çç 3 + 2 cosç ÷ ÷÷
64 çè è è n øø ÷
ø
154
 Loop
Masques pour les bords

Loi d’arête Loi de sommet

1 1 1 6 1
2 2 8 8 8

155
Schéma de Loop

156
 Schéma Butterfly
• Schéma interpolant
• Fonctionne sur maillages triangulaires quelconques
• Simple à mettre en œuvre
– 3 masques

157
Schéma Butterfly

158
 Schéma Mid-edge

Masque d’arête
1 1
2 2
Puis relier entre eux chaque paire de nouveaux sommets
adjacents à un même ancien sommet
159
 Schéma Racine de trois
– un sommet est ajouté au centre de chaque triangle
– chaque triangle est coupé en 3
– les anciennes arêtes internes sont "basculées"

160
 Seconde partie

Surfaces implicites et CSG

 Surfaces implicites
P

• Rappels
– Définies par une équation implicite
S = { P (x,y,z) / f(x,y,z) = iso } N

– f est la « fonction potentiel »

– Normale à la surface : N = - Ñ f (df/dx, df/dy, df/dz )

– Modélisation volumique : intérieur f (x,y,z) > iso

– Test d’appartenance d’un point
(détections de collisions, lancer de rayons)

162
 Surfaces implicites
• Visualisation par marching cubes
– intersection de la surface implicite avec un cube
à on obtient 0, 1 ou plusieurs polygones
– 256 configurations de polygones possibles
– 14 cas possibles à symétrie et réflexivité près

163
 Surfaces implicites
• Visualisation par marching cubes
– On échantillonne l’espace à voxels
– On calcule l’intersection de chaque voxel avec la
surface
– On assemble les polygones obtenus

164
 Surfaces implicites
• Visualisation par lancer de rayon : intersection
rayon/surface
– analytique
• si on sait résoudre l’équation de l’intersection rayon /
surface
– dichotomique
• nécessité d’échantillonner le rayon
– lancer de sphères
• nécessité de connaître la distance à la surface

165
 Surfaces implicites
• Visualisation par lancer de sphères
– Sphere tracing: a geometric method for the
antialiased ray tracing of implicit surfaces, John C.
Hart, The Visual Computer, 1996
– On doit connaître
• Pour une surface A, la fonction fA(P) qui donne la
distance minimale entre tout point P et A
• Pour une surface A, la valeur DA qui est la distance de
traversement maximale depuis l’origine du rayon

166
 Surfaces implicites
• Visualisation par lancer de sphères

Illustrations : Pascal Mignot, Université de Reims

[Link]

167
 Surfaces implicites
• Visualisation par lancer de sphères
– Les fonctions de distances sont connues pour les
surfaces classiques
– Avec une liste d’objets
• La distance à cette liste et la plus petite des distance à
chaque objet
• On lance donc un seul rayon par pixel, et on itère en
progressant de cette distance

168
 Surfaces implicites
• Visualisation par lancer de sphères

Lancer de rayon Lancer de sphère

~ 0,5 seconde ~ 1 seconde …

169
 Objets construits par opérations
booléennes
• Opérations booléennes :
((A È B) – C) Ç D
– union,
– intersection, (A È B) \ C
– différence
AÈB

D
C

A B
170
 Géométrie constructive CSG
• Représentation des objets par un arbre de construction
– les feuilles :
• représentation volumique d’objets simples ou paramétrés
– les noeuds :
• opérations booléennes (régularisées)
• transformations affines
• opérations d’extrusion
• Passage CSG ð B-Rep
– évaluation du bord des objets
• Passage B-Rep ð CSG
– opérations booléennes sur des objets définis par leur bord

171
 CSG
• Lancer de sphères
– Soient A et B deux surfaces implicites et fA et fB
les fonctions de distance signées
• La distance est négative si le point P est à l’intérieur de
l’objet
• Les objets sont donc forcément fermés et orientables
– On détermine les fonctions booléennes en
combinant les fonctions de distance

172
 CSG
• Lancer de sphères
– L’union de A et B est calculée par lancer de sphère
avec la fonction de distance
d(P, A È B) = min(fA(P), fB(P))

173
 CSG
• Lancer de sphères
– L’intersection de A et B est calculée par lancer de
sphère avec la fonction de distance
d(P, A Ç B) = max(fA(P), fB(P))

174
 CSG
• Lancer de sphères
– Le complémentaire de A dans R3 est calculé par
lancer de sphère avec la fonction de distance
d(P, R3 \ A) = − fA(P)

175
 CSG
• Lancer de sphères
– La différence de A et B est calculée par lancer de
sphère avec la fonction de distance
d(P, A − B) = d(A Ç R3 \ B) = max(fA(P), −fB(P))

176