Courbes & Surfaces de subdivision S. Lanquetin. Plan Paramétrique / Implicite Courbes...

Courbes & Surfaces de subdivision

S. Lanquetin

Plan

Paramétrique / Implicite

Courbes paramétriques

Surfaces Paramétriques

Courbes de subdivision

Surfaces de subdivision

Plan

Paramétrique / Implicite

Courbes paramétriques

Surfaces Paramétriques

Courbes de subdivision

Surfaces de subdivision

Deux façons de définir un cercle

Paramétrique

u

x(u) = r cos(u)y(u) = r sin(u)

Implicite

F(x,y) = x²+y²-r²

F<0

F>0

F=0r r

0,0 0,0

Représentation d'une courbe

Explicite: y = y(x)

– Ce doit être une fonction (x ->y): limitation importante

Paramétrique: (x,y) = (x(u),y(u))

+ facile à spécifier, modifier, contrôler– variable u supplémentaire u "cachée" : le paramètre

Implicite: f(x,y) = 0

+ y peut être une fonction multivaluée de x– difficile à spécifier, modifier, contrôler

bmxy

)sin,(cos),( uuyx

0222 ryx

2y x

Représentation d'une surface

Surface paramétrique+ déplacement sur la surface en modifiant u, v+ création de maillages– intersections : rayon/surface, intériorité…

Surface implicite+ intersection, "morphing"– déplacement sur la surface

Surface de subdivision+ construction récursive : maillage de contrôle +

règle+ conception intéractive

x(u,v), y(u,v), z(u,v)

F(x,y,z) = 0

Plan

Paramétrique / Implicite

Courbes paramétriques

Surfaces Paramétriques

Courbes de subdivision

Surfaces de subdivision

Courbes de Bézier

Courbes B-splines

2 types de courbes

Interpolation

Approximation

La courbe passe par les points de

contrôle

La courbe est attirée par les points de

contrôle

Polynômes linéaires par morceaux

Interpolation linéaire

p1

p2

u0 1

p(u)up1 (1 u)p2

2 fonctions de base

1

2

1 11

0 1

pp u u

p

Courbe de Bézier

Ecriture matricielle avec 3 points de contrôle

01P

00P

02P

00

2 0102

1 -2 1 P

P t = t t 1 -2 2 0 P

1 0 0 P

2 00

2 01

2 02

t -2t+1 P

P t = -2t +2t P

t P

2

0001

2 02

1-t P

P t = -2t 1-t P

t P

Courbe de Bézier

Ecriture matricielle avec 3 points de contrôle

01P

00P

02P

00

2 0102

1 -2 1 P

P t = t t 1 -2 2 0 P

1 0 0 P

2

2

000102

P1-t

-2t 1-tP t

t

= P

P

Courbe de Bézier

Ecriture matricielle avec 3 points de contrôle

01P

00P

02P

00

2 0102

1 -2 1 P

P t = t t 1 -2 2 0 P

1 0 0 P

Polynômes de Bernstein

20B t 2

1B t 22B t

n

n 0i i

i=0

= B t P

degré n = 2

000

2

21

2

12

0

02

P

= P

t

P

B t

B

B t

1 0 00 0 1P t = 1-t P +tP

Courbe de Bézier

Algorithme de De Casteljau (construction récursive)

01P

00P

02P

t10P t1

1P t20P

1 0 01 1 2P t = 1-t P +tP

2 1 10 0 1P t = 1-t P +tP

1 0 00 0 1P t = 1-t P +tP

Courbe de Bézier

Algorithme de De Casteljau (construction récursive)

01P

00P

02P

t10P t1

1P t20P

1 0 01 1 2P t = 1-t P +tP

020

11

1PP t = 1-t + Pt

0 01 2

20

0

11

00 1P t = 1-t

+ 1-t P +t

1-t P +tP

PtP

1 0 00 0 1P t = 1-t P +tP

Courbe de Bézier

Algorithme de De Casteljau (construction récursive)

01P

00P

02P

t10P t1

1P t20P

n

n 0i i

i=0

= B t Pdegré n = 2

1 0 01 1 2P t = 1-t P +tP

020

11

1PP t = 1-t + Pt

0 01 2

20

0

11

00 1P t = 1-t

+ 1-t P +t

1-t P +tP

PtP

22 0 0 00 0 1

2

221-tP t = P + P +1 tt P-t

0 0 00

221

220

21B t= P +B+ P t PB t

Courbe de Bézier

Algorithme de De Casteljau (construction récursive)– 2 constructions possibles0

1P

00P

02P

t10P t1

1P t20P

01P

00P

02P

t10P t1

1P t20P

Courbe de Bézier

Construction récursive d’une courbe de Bézier de degré 2

Courbe de Bézier

Construction récursive d’une courbe de Bézier de degré 2

Courbe de Bézier

Construction récursive d’une courbe de Bézier de degré 2

Courbe de Bézier

Construction récursive d’une courbe de Bézier de degré 2

Courbe de Bézier

Construction récursive d’une courbe de Bézier de degré 2

Courbe de Bézier

Construction récursive d’une courbe de Bézier de degré 2

Courbe de Bézier degré 3

Degré 3 ou ordre 4

3

2

000102

2

3

P

P t = P3t 1

3t

1-t

P1

t

-

-

t

t

000

3 2 10203

-1 3 -3 1 P3 -6 3 0 P

P t = t t t 1-3 3 0 0 P1 0 0 0 P

003

30

32 0

2

30

01

1

P

= P

P

t

B

t

B

t

t

B

B

Fonctions de mélange de Bézier

30B t

31B t

32B t

30B t

Courbe de Bézier

Construction récursive d’une courbe de Bézier de degré 3

Courbe de Bézier

Construction récursive d’une courbe de Bézier de degré 3

Courbe de Bézier

Construction récursive d’une courbe de Bézier de degré 3

Courbe de Bézier

Construction récursive d’une courbe de Bézier de degré 3

Courbe de Bézier

Construction récursive d’une courbe de Bézier de degré 3

Courbe de Bézier

Construction récursive d’une courbe de Bézier de degré 3

Courbe de Bézier

Courbe contenue dans l’enveloppe convexe

Courbe de Bézier

Déplacement d’un point

Courbe de Bézier

Modification de l’ensemble de la courbe

Courbe de Bézier par morceaux

Courbe de Bézier par morceaux

Courbes par morceaux

Différentes possibilités d’assemblage

Continuité de position

Continuité de position et du vecteur tangent

Continuité de position, de tangence et de courbure

Courbes B-splines

Rappel : Courbe de Bézier de degré n

– points de contrôle

– fonctions de bases

0

nn

i ii

C t PB t

iP 0,i n

kiN t

Courbes B-splines

Courbe B-Spline à n+1 points de contrôle d’ordre k

– points de contrôle– vecteur

nodal.– fonctions de base B-splines d’ordre

k

0 00

, ,n

ki i n k n k

i

C t PN t t t t t t

iP 0,i n 0;0 et i i n kT t i n k t t t k

iN t

1,1

, , 1 1, 11 1

1 si ,

0 sinon

pour 2,

i ii

i jii j i j i j

i j i i j i

t t tN t

t tt tN t N t N t j k

t t t t

0(convention 0)

0

,3 ,12 1

2 3 11,1

2 2 1 3 2 2 1

3 32,1

3 2 3 2

i ii i

i i i i

i i i ii

i i i i i i i i

i ii

i i i i

t t t tN t N t

t t t t

t t t t t t t tN t

t t t t t t t t

t t t tN t

t t t t

Courbes B-splines

1,1

1 si ,

0 sinoni i

i

t t tN t

,2 ,11

21,1

2 1

ii i

i i

ii

i i

t tN t N t

t t

t tN t

t t

it 1it 2it 3it 4it

,4iN t

Courbes B-splines

Ordre k = 2

Ordre k = 3 Ordre k = 4

Plan

Paramétrique / Implicite

Courbes paramétriques

Surfaces Paramétriques

Courbes de subdivision

Surfaces de subdivision

Surfaces de Bézier

Surface de Bézier de degré m par n

– points de contrôle

– et polynômes de Bernstein

,0 0

, , 0,1 , 0,1n m

m ni j i j

j i

S u v P B u B v u v

,i jP

njB v m

iB u

Surfaces de Bézier

Construction par produit tensoriel

Surfaces B-splines

Surface B-spline d'ordre k par l

– points de contrôle

– et

sont des vecteurs nodaux.– et fonctions de base B-spline de

degrés respectifs k-1 et l-1 associées aux vecteurs nodaux U et V.

, 0 00 0

, , , , ,n m

k li j i j n k m l

j i

S u v P N u N v u u u v v v

, , 0, et 0,i jP i m j n

0;0 et i i n kU u i n k u u u 0;0 et j j m lV v j m l v v v

kiN u l

jN v

Plan

Paramétrique / Implicite

Courbes paramétriques

Surfaces Paramétriques

Courbes de subdivision

Surfaces de subdivision

Algorithme de Chaïkin

Algorithme DLM

Algorithme 4 points

0P

00P

01P

02P

03P

04P

05P

L’algorithme de Chaikin

Génération de courbes lisses à partir d’un polygone en 2D (1974)

12 1

12 1 1

3 1

4 41 3

4 4

k k ki i i

k k ki i i

P P P

P P P

0P

00P

01P

02P

03P

04P

05P

1P

10P

11P

12P

13P

14P

15P

16P1

7P

L’algorithme de Chaikin

Génération de courbes lisses à partir d’un polygone en 2D (1974)

12 1

12 1 1

3 1

4 41 3

4 4

k k ki i i

k k ki i i

P P P

P P P

0P

00P

01P

02P

03P

04P

05P

1P

10P

11P

12P

13P

14P

15P

16P1

7P

L’algorithme de Chaikin

Génération de courbes lisses à partir d’un polygone en 2D (1974)

12 1

12 1 1

3 1

4 41 3

4 4

k k ki i i

k k ki i i

P P P

P P P

2P

L’algorithme de Chaikin

Génération de courbes lisses à partir d’un polygone en 2D (1974)

Courbe limite : B-spline quadratique uniforme

P

L’algorithme (Dyn, Levin et Micchelli)

génération de B-splines cubiques

12 1 1

12 1 1

16

81

2

k k k ki i i i

k k ki i i

P P P P

P P P

0P

00P 0

1P

02P

03P

04P

05P

10P

11P 1

2P

13P

14P

15P

16P1

7P

L’algorithme (Dyn, Levin et Micchelli)

génération de B-splines cubiques

12 1 1

12 1 1

16

81

2

k k k ki i i i

k k ki i i

P P P P

P P P

1P

10P

11P 1

2P

13P

14P

15P

16P1

7P

L’algorithme (Dyn, Levin et Micchelli)

génération de B-splines cubiques

12 1 1

12 1 1

16

81

2

k k k ki i i i

k k ki i i

P P P P

P P P

2P

L’algorithme (Dyn, Levin et Micchelli)

génération de B-splines cubiques

12 1 1

12 1 1

16

81

2

k k k ki i i i

k k ki i i

P P P P

P P P

P

L’algorithme quatre points

Génération de courbes lisses interpolantes

12

12 1 1 1 2

1

2

k ki i

k k k k ki i i i i

P P

P w P P w P P

1 16w0P

00P

01P

02P

03P0

4P

05P

1P

10P

11P

12P

13P

14P

15P

16P1

7P2PP3P

L’algorithme quatre points

Génération de courbes lisses interpolantes

12

12 1 1 1 2

1

2

k ki i

k k k k ki i i i i

P P

P w P P w P P

1 16w0P

00P

01P

02P

03P0

4P

05P

L’algorithme quatre points

Génération de courbes lisses interpolantes

12

12 1 1 1 2

1

2

k ki i

k k k k ki i i i i

P P

P w P P w P P

1 16w1P

10P

11P

12P

13P

14P

15P

16P1

7P

L’algorithme quatre points

Génération de courbes lisses interpolantes

12

12 1 1 1 2

1

2

k ki i

k k k k ki i i i i

P P

P w P P w P P

1 16w2P

L’algorithme quatre points

Génération de courbes lisses interpolantes

12

12 1 1 1 2

1

2

k ki i

k k k k ki i i i i

P P

P w P P w P P

1 16w3P

L’algorithme quatre points

Génération de courbes lisses interpolantes

12

12 1 1 1 2

1

2

k ki i

k k k k ki i i i i

P P

P w P P w P P

1 16wP

Plan

Paramétrique / Implicite

Courbes paramétriques

Surfaces Paramétriques

Courbes de subdivision

Surfaces de subdivision

Définition Vocabulaire

Applications

Algorithme de Doo-Sabin

Algorithme de Catmull-Clark

Algorithme de Loop

Algorithme de butterfly

Subdivision adaptative

Surface de subdivision

Maillage initial

Règles de subdivision

0M

Surface de subdivision

Maillage initial

Règles de subdivision

1M

1 0M S M= ´

Surface de subdivision

Maillage initial

Règles de subdivision

2M

2 1

20

M S M

S M

= ´

= ´

1

0

k k

k

M S M

S M

-= ´

= ´

Surface de subdivision

Maillage initial

Règles de subdivision

Surface lisse

3M

Maillage de contrôle / Surface limite

0M

Interpolation / Approximation

Interpolation / Approximation

Interpolation / Approximation

Primal / Dual

Principe primal : partage les faces (Loop)

Principe dual : partage les sommets (Doo-Sabin).

Uniforme / Adaptatif

Mêmes règles appliquées sur toutes les faces

Règles différentes en fonction d'un critère de distance de courbure…

Sommets extraordinaires

Valence d’un sommet

Sommets réguliers intérieurs / extraordinaires

Géométrie Complexe

Main de Woody

dans

Toy Story ©

Main de Geri

dans

Geri’s Game ©

3

CHAMPS D’APPLICATION

Film d’animation

4

2.496 polygones

CHAMPS D’APPLICATIONI NTRODUCT I ON

4

CHAMPS D’APPLICATION

Film d’animation

I NTRODUCT I ON

4

CHAMPS D’APPLICATION

Film d’animation

Modeleurs CAO

I NTRODUCT I ON

4

Principe de Doo-Sabin

0a

1a

1ka -

2ka -

( )( )0

1 54 4

23 2cos, 1, , 14i

ki

k i kk

a

pa

= +

+= = -K

34

14

Doo-Sabin

FRONTIERE

FRONTIERE

FRONTIERE

FRONTIERE

FRONTIERE

Principe de Doo-Sabin

11kf

10kf

Catmull-Clark Scheme

2ke

1kne

0ke

1ke

2ke

11knf

Calcul des nouveaux sommets:

• point "face"

1 1

ki j

k kj i

f Fj

f fF

11ke

11kf

10kf

Catmull-Clark Scheme

2ke

1kne

0ke

1ke

2ke

10ke

12ke

11knf

Calcul des nouveaux sommets:

• point "face"

• point "coté"

1 111

4

k k k kj j jk

j

v e f fe

10ke

Calcul des nouveaux sommets:

• point "face"

• point "coté"

• point "sommet"

10kf

11kf

Catmull-Clark Scheme

2ke

1kne

0ke

1ke

2ke

1kv

11ke

12ke

11knf

1 11 1

2 20 0

2 1 1n nk k k k

j jj j

nv v e f

n n n

Catmull-Clark Scheme

2ke

1kne

0ke

1ke

2ke

1kv

10ke 1

1ke

12ke

11knf

10kf

11kf

Calcul des nouveaux sommets:

• point "face"

• point "coté"

• point "sommet"

Nouveau maillage

• faces quadrilatérales

Principe de Catmull-Clark

Principe de Catmull-Clark

Principe de Catmull-Clark

Principe de Catmull-Clark

Principe de Loop

Étape 1 :

[C. Loop : Master 1987]

6

pair

impair

Principe de Loop

Étape 2 : Masques

1-k

( )( )( )223 1 5 3 13 cos 316 8 8 4 ksi k et si kkpb = = - + >

Principe de Loop

Étape 2 : Masques

1/8

3/4

1/8

Principe de Loop

Étape 1 : Étape 2 : Masques

3/8 3/8

1/8

1/8

Principe de Loop

Étape 2 : Masques

1/21/2

Principe de Loop

Méthode de type Butterfly

Splines de degré 4 sous tension Interpolation du polyèdre de contrôle dans le processus de raffinement Surfaces C1 continues

P7

P8

P6P5

P4P3

P2

P1

Méthode de type Butterfly

A chaque arête, on associe un nouveau point On évalue le nouveau point à l’aide de son voisinage Utilisation d’un paramètre de tension qui sert a fixer l’influence du

voisinage Pour C1 continuité w = 1/16

P7

P8

P6P5

P4P3

P2

P1

kkkkkkkkk PPPPPPPPP 876543211 221

Principe de butterfly

Subdivision adaptative

Principe de subdivision adaptive ou non-uniforme :

Où subdiviser ?Critère de subdivision

Comment subdiviser ?Règles de subdivision

Problem

Éviter les trous Générer un "petit" nombre de faces Obtenir un maillage progressif

Subdivision Adaptive

Avec le plus petit nombre de faces

sommet mobilesommet statique

Subdivision Adaptive

Results

468 faces 1692 faces (1872)

5022 faces (7488)

5133 faces (29952)

Subdivision Adaptive

Le maillage n'est pas conforme

Subdivision Adaptive

Algorithme en T

[Zorin et al 1998] [Amresh et al 2003]

Subdivision Adaptive

Valences peuvent être élevées

Subdivision Adaptive

Algorithme Incrémental

[Pakdel et al 2004]

Sommet progressif

Subdivision Adaptive

Grand nombre de faces

Subdivision Adaptive

Un compromis

Subdivision Adaptive

Algorithme diagonal

Textures

Lancer de rayon