Box-Splines

et

Surfaces de Subdivision

Loïc Barthe

Equipe SIRV - IRIT / UPS / CNRS

Toulouse

Plan de la présentation

Pourquoi la subdivision et pourquoi sur les Box-splines

La subdivision : principe général

D'une courbe Box-spline à un schéma de subdivision

Passage aux surfaces

Les sommets irréguliers

Limites

Conclusion

Livres et cours / Bibliographie

Pourquoi la subdivision

et

pourquoi sur les Box-splines

La subdivision ?

A partir d'un maillage 2D manifold à topologie quelconque :

La subdivision ?

Chaque triangle est découpé en plus petits triangles pour fournir un maillage plus dense

La subdivision ?

Cette opération est répétée autant que souhaité

La subdivision ?

Et le maillage converge vers une surface lisse

L'animation

Modélisation intuitive et interactive de surfaces 3D

Un artiste n'est pas un informaticien, ni un mathématicien!!!!

On recherche une qualité visuelle

Continuité de normales : surfaces C1 Continuité de courbure : surfaces C2

Construction

Modélisation de maquettes

Logiciels de constructions : de la conception à la fabrication (toujours l'interactivité)

Une représentation mathématique de la surface qui doit être précise et adaptée aux contraintes de fabrication

(continuité, découpage, assemblage, discrétisation, ...)

Doit aussi supporter les modèles d'études physiques (aérodynamique, résistance des matériaux, ...)

Les surfaces paramétriques

Les carreaux de Bézier (1954), B-spline (1962), ...

Standard pour l'animation et la construction

Les surfaces paramétriques

Les carreaux de Bézier (1954), B-spline (1962), ...

Standard pour l'animation et la construction

✓	Chaque carreau est défini par un polygone de contrôle

✓	Modélisation type couture

Les surfaces paramétriques

Les carreaux de Bézier (1954), B-spline (1962), ...

Standard pour l'animation et la construction

✓	Chaque carreau est défini par un polygone de contrôle

✓	Modélisation type couture

✗	Difficulté de contrôle des connections inter-carreaux

✗	Difficulté pour ajuster la surface à un polygone de contrôle quelconque

Les surfaces de subdivision

Un maillage est raffiné itérativement et converge éventuellement vers une surface

Box-spline (1978) :

Généralisation des Box-splines à un polygone de contrôle quelconque

Geri's Game (Pixar 1997)

Les surfaces de subdivision deviennent un standard dans l'industrie de l'animation

Les Box-splines

Ce sont des splines dont les fonctions de base sont polynomiales par morceaux.

Les fonctions de base d'ordre k sont obtenues à partir de sections de boîtes de dimension k

Ordre k = 2

t

Ni2(t)

0

1

Boîte 2D

[ dBH94 ]

Les Box-splines

Boîte de dimension 3 : ordre k = 3

Ordre k = 2

t

Ni2(t)

0

1

Boîte 2D

t

Ni3(t)

0

1

1/2

3/4

Les Box-splines

Sur les courbes, les Box-splines sont identiques aux B-splines uniformes

Le produit tensoriel de 2 Box-splines est identique au produit tensoriel de 2 B-splines uniformes

Les Box-splines ont des fonctions de base contrôlées par un maillage triangulaire régulier.

Les Box-splines peuvent être définies à partir de directions (voir un peu plus loin dans la présentation)

Pourquoi subdiviser à partir des Box-splines ?

Proposer des schémas de subdivision sur les courbes, les maillages de quadrilatères et les maillages triangulaires

Pourquoi subdiviser à partir des Box-splines ?

Proposer des schémas de subdivision sur les courbes, les maillages de quadrilatères et les maillages triangulaires

Dans les zones où le maillage est régulier, la surface limite est une Box-spline et ainsi :

On connaît l'équation et la continuité de la surface limite

La surface limite possède toutes les bonnes propriétés des Box-spline : enveloppe convexe, faibles oscillations, ...

Pourquoi subdiviser à partir des Box-splines ?

Proposer des schémas de subdivision sur les courbes, les maillages de quadrilatères et les maillages triangulaires

Dans les zones où le maillage est régulier, la surface limite est une Box-spline et ainsi :

On connaît l'équation et la continuité de la surface limite

La surface limite possède toutes les bonnes propriétés des Box-spline : enveloppe convexe, faibles oscillations, ...

✓	Toutes les propriétés des Box-splines applicables à un polygone de contrôle quelconque !

✗ Un bémol néanmoins sur les zones d'irrégularité (voir plus loin dans la présentation)

La subdivision : principe général

Principe général

Illustration sur une courbe

Principe général

Un sommet est déplacé par combinaison affine des anciens sommets

1

1

6

Principe général

Un nouveau point est inséré pour un segment, par combinaison affine des anciens points

4

4

Principe général

Ces combinaisons affines sont répétées pour chaque sommet et chaque segment

Principe général

Les nouveaux points sont ensuite maillés

Principe général

Puis on répète un pas de subdivision

Principe général

Et à la limite, le maillage converge vers une courbe

Règles de subdivision

Les combinaisons affines calculant les nouveaux points sont les règles de subdivision.

Dans cet exemple, il y en a deux :

Masque

Le masque donne l'influence d'un ancien point sur les nouveaux :

6

4

1

4

1

Passage du masque aux règles de subdivision

Après subdivision, on a multiplié par deux le nombre de sommet :

schéma diadic

Pour passer du masque aux règles de subdivision, on parcours le masque en prenant une valeur sur deux :

Passage du masque aux règles de subdivision

Après subdivision, on a multiplié par deux le nombre de sommet : schéma diadic

Pour passer du masque aux règles de subdivision, on parcours le masque en prenant une valeur sur deux :

6

1

1

Passage du masque aux règles de subdivision

Après subdivision, on a multiplié par deux le nombre de sommet : schéma diadic

Pour passer du masque aux règles de subdivision, on parcours le masque en prenant une valeur sur deux :

4

4

6

1

1

Schéma de subdivision

Si on connait le masque, on en déduit les règles de subdivision

et le positionnement des nouveaux sommets

D'une courbe Box-spline

à

un schéma de subdivision

Fonctions de base des Box-splines univariées

Fonctions de base d'ordre 1 :

Fonctions de base d'ordre 2 :

Fonctions de base d'ordre k :

Masque diadic de la Box-spline d'ordre 1

Fonctions de base d'ordre 1 : Masque du schéma diadic d'ordre 1 :

Fonctions de base d'ordre 2 :

Fonctions de base d'ordre k :

Masque diadic de la Box-spline d'ordre 2

Fonctions de base d'ordre 1 : Masque du schéma diadic d'ordre 1 :

Fonctions de base d'ordre 2 : Masque du schéma diadic d'ordre 2 :

Fonctions de base d'ordre k :

Masque diadic de la Box-spline d'ordre k

Fonctions de base d'ordre 1 : Masque du schéma diadic d'ordre 1 :

Fonctions de base d'ordre 2 : Masque du schéma diadic d'ordre 2 :

Fonctions de base d'ordre k : Masque du schéma diadic d'ordre k :

En termes de directions

On définit des directions à partir des transformées en z d'un signal discret [a0 a1 ... an]

Polynôme de Laurent :

En termes de directions

On définit les directions à partir des transformées en z d'un signal discret [a0 a1 ... an]

Polynôme de Laurent :

Ainsi [1 1] s'écrit p(z) = 1 + z

En termes de directions

On définit les directions à partir des transformées en z d'un signal discret [a0 a1 ... an]

Polynôme de Laurent :

Ainsi [1 1] s'écrit p(z) = 1 + z

Ce qui se représente par :

1

z

z2

z3

z-1

z-2

1

1

0

0

0

0

En termes de directions

On définit les directions à partir des transformées en z d'un signal discret [a0 a1 ... an]

Polynôme de Laurent :

Ainsi [1 1] s'écrit p(z) = 1 + z

Ce qui se représente par :

Soit une direction :

1

z

z2

z3

z-1

z-2

1

1

0

0

0

0

En termes de directions

Ainsi le masque du schéma diadic correspondant à la Box-spline univariée à 2 directions (ordre 2) est :

soit

En termes de directions

Ainsi le masque du schéma diadic correspondant à la Box-spline univariée à 2 directions (ordre 2) est :

soit

En termes de directions

Ainsi le masque du schéma diadic correspondant à la Box-spline univariée à 2 directions (ordre 2) est :

soit

ou

1

z

z2

z3

z-1

z-2

1

2

1

0

0

0

En terme de directions

Du masque, on déduit les règles de subdivision :

En terme de directions

Du masque, on déduit les règles de subdivision :

En terme de directions

Puis on normalise les règles :

En terme de directions

Et on les applique sur les sommets :

1

1

En terme de directions

Et on les applique sur les sommets :

Et c'est tout !!

1

1

2

Masque de la Box-spline univariée à 3 directions

C'est la Box-spline d'ordre 3 (degré 2)

Masque de la Box-spline univariée à 3 directions

C'est la Box-spline d'ordre 3 (degré 2)

Masque de la Box-spline univariée à 3 directions

C'est la Box-spline d'ordre 3 (degré 2)

ou

D'où les règles de subdivision

D'où les règles de subdivision

3

1

1

3

Masques des Box-splines

A ce niveau, on peut remarquer que les masques suivent le triangle de Pascal :

1 1

1 2 1	Box-spline à 2 directions (ordre 2 => degré 1 => continuité C0 )

1 3 3 1	Box-spline à 3 directions (ordre 3 => degré 2 => continuité C1 )

1 4 6 4 1	Box-spline à 4 directions (ordre 4 => degré 3 => continuité C2 )

1 5 10 10 5 1	Box-spline à 5 directions (ordre 5 => degré 4 => continuité C3 )

...

Passage aux surfaces

Grilles de quadrilatères

Les directions sur une grille de quadrilatères :

z1

z12

1

z2

z22

z23

z1-1

Les directions sur les grilles de quadrilatères

z1

z12

1

z2

z22

z23

z1-1

Les directions sur les grilles de quadrilatères

z1

z12

1

z2

z22

z23

z1-1

Les directions sur les grilles de quadrilatères

z1

z12

1

z2

z22

z23

z1-1

Les directions sur les grilles de quadrilatères

z1

z12

1

z2

z22

z23

z1-1

Les directions sur les grilles de quadrilatères

z1

z12

1

z2

z22

z23

z1-1

Pour créer un schéma

On choisit les directions :

z1

z12

1

z2

z22

z23

z1-1

Calcul du masque

Convolution discrète :

z1

z12

1

z2

z22

z23

z1-1

Calcul du masque

Convolution discrète :

z1

z12

1

z2

z22

z23

z1-1

Calcul du masque

Convolution discrète :

z1

z12

1

z2

z22

z23

z1-1

Calcul du masque

Convolution discrète :

z1

z12

1

z2

z22

z23

z1-1

Calcul du masque

Convolution discrète :

z1

z12

1

z2

z22

z23

z1-1

Calcul du masque

Convolution discrète :

z1

z12

1

z2

z22

z23

z1-1

Calcul du masque

Convolution discrète :

z1

z12

1

z2

z22

z23

z1-1

Calcul du masque

Convolution discrète :

z1

z12

1

z2

z22

z23

z1-1

Calcul du masque

Produit de polynômes de Laurent :

z1

z12

1

z2

z22

z23

z1-1

Calcul du masque

Produit de polynômes de Laurent :

z1

z12

1

z2

z22

z23

z1-1

Calcul du masque : 2ème possibilité

Produit de polynômes de Laurent :

z1

z12

1

z2

z22

z23

z1-1

z1

z12

1

z2

z22

z23

z1-1

1

1

1

2

2

2

2

1

1

1

1

1

Règles de subdivision

A partir du masque, on déduit les règles de subdivision :

Règles de subdivision

A partir du masque, on déduit les règles de subdivision :

Règles de subdivision

A partir du masque, on déduit les règles de subdivision :

1

1

2

Règles de subdivision

A partir du masque, on déduit les règles de subdivision :

Règles de subdivision

A partir du masque, on déduit les règles de subdivision :

1

2

1

Règles de subdivision

A partir du masque, on déduit les règles de subdivision :

Règles de subdivision

A partir du masque, on déduit les règles de subdivision :

1

1

2

Règles de subdivision

A partir du masque, on déduit les règles de subdivision :

Règles de subdivision

A partir du masque, on déduit les règles de subdivision :

2

1

1

Règles de subdivision

Les règles sont appliquées à chaque face du maillage :

Règles de subdivision

Et en maillant les nouveaux points, on obtient le maillage après un pas de subdivision

Continuité de la surface limite

Dans le cas bidirectionnel (maillages de quadrilatères ou triangulaires), la continuité est obtenue avec la règle suivante :

On part du nombre de directions

Ici : 4

Continuité de la surface limite

Dans le cas bidirectionnel (maillages de quadrilatères ou triangulaires), la continuité est obtenue avec la règle suivante :

On part du nombre de directions

Ici : 4

On sélectionne le plus grand ensemble de directions qui sont dans le même sens, et on retire leur quantité

Ici : 4 ensembles de 1 direction. Le plus grand a donc 1 direction : 4 – 1 = 3

Continuité de la surface limite

Dans le cas bidirectionnel (maillages de quadrilatères ou triangulaires), la continuité est obtenue avec la règle suivante :

On part du nombre de directions

Ici : 4

On sélectionne le plus grand ensemble de directions qui sont dans le même sens, et on retire leur quantité

Ici : 4 ensembles de 1 direction. Le plus grand a donc 1 direction : 4 – 1 = 3

On retire 2 au nombre restant

Ici : 3 – 2 = 1

Continuité de la surface limite

Dans le cas bidirectionnel (maillages de quadrilatères ou triangulaires), la continuité est obtenue avec la règle suivante :

On part du nombre de directions

Ici : 4

On sélectionne le plus grand ensemble de directions qui sont dans le même sens, et on retire leur quantité

Ici : 4 ensembles de 1 direction. Le plus grand a donc 1 direction : 4 – 1 = 3

On retire 2 au nombre restant

Ici : 3 – 2 = 1

Le nombre final est la continuité de la surface limite

Ici, la continuité de la surface limite est C1

Schémas classiques

Doo-Sabin	Catmull-Clark

Box spline à 6 directions, continuité C1	Box spline à 8 directions, continuité C2

[ DS78 ]

[ CC78 ]

Comparaisons

Doo-Sabin Box-spline à 4 directions

Continuité C1 Continuité C1

Précision linéaire

Doo-Sabin (1978) Box-spline à 4 directions

Précision linéaire dans 2 directions Précision linéaire dans 4 directions

Images de [ PS04 ]

Précision linéaire

Doo-Sabin Box-spline à 4 directions

Précision linéaire dans 2 directions Précision linéaire dans 4 directions

Images de [ PS04 ]

Comparaison

Catmull-Clark (1978) Box-spline à 6 directions (2004)

Box-spline à 8 directions, continuité C2 Continuité C2

[ PS04 ]

Grilles triangulaires

Les directions sur une grille triangulaire :

z1

z12

1

z2

z22

z23

z1-1

Grilles triangulaires

Les directions sur une grille triangulaire :

z1

z12

1

z2

z22

z23

z1-1

Grilles triangulaires

Les directions sur une grille triangulaire :

z1

z12

1

z2

z22

z23

z1-1

Grilles triangulaires

Les directions sur une grille triangulaire :

z1

z12

1

z2

z22

z23

z1-1

Grilles triangulaires

Les directions sur une grille triangulaire :

z1

z12

1

z2

z22

z23

z1-1

Calcul du masque

Un masque est calculé à partir des directions, comme illustré jusqu'à maintenant.

Soit avec des convolutions discrètes

Soit en faisant le produit des polynômes de Laurent

z1

z12

1

z2

z22

z23

z1-1

Exemple

Box-spline à 6 directions (3  2) :

Exemple

Box-spline à 6 directions (3  2) :

Exemple

Box-spline à 6 directions (3  2) :

Exemple

Box-spline à 6 directions (3  2) :

Continuité C2

Schéma de Loop

[ Loo87 ]

Les sommets irréguliers

Qu'est-ce qu'un sommet irrégulier ?

Un sommet de valence différente de 4 sur un maillage de quadrilatères :

Qu'est-ce qu'un sommet irrégulier ?

Un sommet de valence différente de 4 sur un maillage de quadrilatères :

Un sommet de valence différente de 6 sur un maillage triangulaire :

Il y a toujours des sommets irréguliers

On peut facilement démontrer (formule d'Euler) qu'un objet de génus zéro ne peut pas être mailler avec un maillage triangulaire (ou formé de quadrilatères) entièrement régulier

Un maillage classique a plutôt l'aspect suivant :

Que ce passe-t-il lors de la subdivision

La subdivision n'insère que des sommets réguliers

Après plusieurs pas de subdivision, les sommets irréguliers sont isolés dans une « mer » de sommets réguliers

La surface ?

Au niveau de ces sommets, les règles de subdivisions ne font pas converger le maillage vers une surface à l'équation connue.

La surface limite ?

Au niveau de ces sommets, les règles de subdivisions ne font pas converger le maillage vers une surface à l'équation connue.

Il faut donc proposer des règles qui permettent de converger une surface de la meilleur « qualité » possible :

Minimiser les oscillations

La surface limite ?

Au niveau de ces sommets, les règles de subdivisions ne font pas converger le maillage vers une surface à l'équation connue.

Il faut donc proposer des règles qui permettent de converger une surface de la meilleur « qualité » possible :

Minimiser les oscillations

La surface limite ?

Au niveau de ces sommets, les règles de subdivisions ne font pas converger le maillage vers une surface à l'équation connue.

Il faut donc proposer des règles qui permettent de converger une surface de la meilleur « qualité » possible :

Minimiser les oscillations

Continuité maximale (si possible C2)

La surface limite ?

Au niveau de ces sommets, les règles de subdivisions ne font pas converger le maillage vers une surface à l'équation connue.

Il faut donc proposer des règles qui permettent de converger une surface de la meilleur « qualité » possible :

Minimiser les oscillations

Continuité maximale (si possible C2)

La surface limite ?

Au niveau de ces sommets, les règles de subdivisions ne font pas converger le maillage vers une surface à l'équation connue.

Il faut donc proposer des règles qui permettent de converger une surface de la meilleur « qualité » possible :

Minimiser les oscillations

Continuité maximale (si possible C2)

Maillage régulier

La surface limite ?

Au niveau de ces sommets, les règles de subdivisions ne font pas converger le maillage vers une surface à l'équation connue.

Il faut donc proposer des règles qui permettent de converger une surface de la meilleur « qualité » possible :

Minimiser les oscillations

Continuité maximale (si possible C2)

Maillage régulier

Matrice de subdivision

L'étude de la surface au voisinage des sommets irréguliers s'appuie sur la matrice de subdivision

p00

Matrice de subdivision

L'étude de la surface au voisinage des sommets irréguliers s'appuie sur la matrice de subdivision

a0

a1

a1

a1

a1

a1

a1

a1

a1

p00

Matrice de subdivision

L'étude de la surface au voisinage des sommets irréguliers s'appuie sur la matrice de subdivision

a0

a1

a1

a1

a1

a1

a1

a1

a1

p00

Matrice de subdivision

L'étude de la surface au voisinage des sommets irréguliers s'appuie sur la matrice de subdivision

p00

Matrice de subdivision

L'étude de la surface au voisinage des sommets irréguliers s'appuie sur la matrice de subdivision

6

6

2

2

p00

Schéma de Loop :

Matrice de subdivision

L'étude de la surface au voisinage des sommets irréguliers s'appuie sur la matrice de subdivision

6

6

2

2

p00

Matrice de subdivision

L'étude de la surface au voisinage des sommets irréguliers s'appuie sur la matrice de subdivision

p00

Matrice de subdivision

L'étude de la surface au voisinage des sommets irréguliers s'appuie sur la matrice de subdivision

p00

6

6

2

2

Matrice de subdivision

L'étude de la surface au voisinage des sommets irréguliers s'appuie sur la matrice de subdivision

p00

Matrice de subdivision

L'étude de la surface au voisinage des sommets irréguliers s'appuie sur la matrice de subdivision

p00

Décomposition en valeurs et vecteurs propres

Pour étudier le comportement de la surface limite, on décompose la matrice de subdivision S en vecteurs et valeurs propres :

soit

Que ce passe-t-il au cours de la subdivision ?

Après r pas de subdivision :

C'est à dire :

Interprétation en série de Taylor

Quand les valeurs propres sont ordonnées de la plus grande à la plus petite :

Interprétation en série de Taylor

Quand les valeurs propres sont ordonnées de la plus grande à la plus petite :

Cette expression peut s'interpréter comme un développement en séries de Taylor au point irrégulier :

Interprétation en série de Taylor

Quand les valeurs propres sont ordonnées de la plus grande à la plus petite :

Cette expression peut s'interpréter comme un développement en séries de Taylor au point irrégulier :

Qui s'écrit aussi :

Interprétation en série de Taylor

Ainsi :

Les li sont les dérivées partielles successives :

l0 est la position du point central à la limite

l1 et l2 sont les dérivées partielles de premier ordre (tangentes à la surface en l0)

...

Interprétation en série de Taylor

Ainsi :

Les li sont les dérivées partielles successives :

l0 est la position du point central à la limite

l1 et l2 sont les dérivées partielles de premier ordre (tangentes à la surface en l0)

...

Les mi correspondent aux différentes fonctions polynomiales représentée à une échelle donnée par le facteur d'échelle i

m0 = [1 1 1 ... 1] pour la position du point central à la limite

Interprétation géométrique

Etudions un voisinage un peu plus grand (matrice de subdivision plus grande) :

Interprétation géométrique

Etudions un voisinage un peu plus grand (matrice de subdivision plus grande) :

Les vecteurs propres m1 et m2 donnent respectivement les abscisses et les ordonnées de la position des points à la limite dans le plan tangent

Interprétation géométrique

Etudions un voisinage un peu plus grand (matrice de subdivision plus grande) :

Les vecteurs propres m1 et m2 donnent respectivement les abscisses et les ordonnées de la position des points à la limite dans le plan tangent

Interprétation géométrique

Etudions un voisinage un peu plus grand (matrice de subdivision plus grande) :

Les vecteurs propres m1 et m2 donnent respectivement les abscisses et les ordonnées de la position des points à la limite dans le plan tangent

Interprétation géométrique

Etudions un voisinage un peu plus grand (matrice de subdivision plus grande) :

Les vecteurs propres m1 et m2 donnent respectivement les abscisses et les ordonnées de la position des points à la limite dans le plan tangent

Interprétation géométrique

Etudions un voisinage un peu plus grand (matrice de subdivision plus grande) :

Les vecteurs propres m1 et m2 donnent respectivement les abscisses et les ordonnées de la position des points à la limite dans le plan tangent

Interprétation géométrique

Les valeurs propres 1, 2 et les vecteurs propres m1, m2 permettent d'étudier le comportement de la surface limite dans le plan tangent

Interprétation géométrique

Polynômes de degré 2 : Contrôle de la courbure

Coupe

Selle

Selle

Interprétation géométrique

Le vecteur propre m3 donne les altitudes des sommets du plan tangent dans la configuration de coupe

Interprétation géométrique

Les vecteurs propres m4 et m5 donnent les altitudes des sommets du plan tangent dans chacune des configurations en selle

Interprétation géométrique

Les valeurs propres 3, 4, 5 et les vecteurs propres m3, m4, m5 permettent d'étudier le comportement de la courbure de la surface limite

En fonction d'une configuration elliptique (coupe, indices 3) et de deux configurations hyperboliques (selles, indices 4 et 5)

Calcul des valeurs et vecteurs propres

La taille de la matrice de subdivision dépend de la valence v du sommet irrégulier

=>

Il faut faire un calcul différent pour étudier chaque valence

Calcul des valeurs et vecteurs propres

Structure de la matrice de subdivision :

matrice à blocs circulant

Calcul des valeurs et vecteurs propres

On utilise la transformée de Fourier pour transformer la matrice S en une matrice diagonale par blocs :

[ BGD05 ]

Calcul des valeurs et vecteurs propres

On utilise la transformée de Fourier pour transformer la matrice S en une matrice diagonale par blocs :

La taille des blocs est égal au nombre d'anneaux pris en compte autour du sommet irrégulier (ici : 3)

[ BGD05 ]

Calcul des valeurs et vecteurs propres

La taille des blocs est indépendante de la valence du sommet irrégulier

=> Un unique calcul pour toutes les valences

Les valeurs propres et vecteurs propres des différents blocs de Fourier donnent les modules des valeurs et vecteurs propres de S, ce qui est suffisant pour l'analyse du schéma

Conditions sur les valeurs propres

Conditions nécessaires

Convergence (condition nécessaire et suffisante)

[ BS88 ]

[ DS78 ]

Conditions sur les valeurs propres

Conditions nécessaires

Convergence (condition nécessaire et suffisante)

Continuité C1

Les valeurs propres 1 et 2 doivent venir des blocs de fréquence  = 1 et  = -1 et

[ BS88 ]

[ DS78 ]

Conditions sur les valeurs propres

Conditions nécessaires

Convergence (condition nécessaire et suffisante)

Continuité C1

Les valeurs propres 1 et 2 doivent venir des blocs de fréquence  = 1 et  = -1 et

Continuité C2

La valeur propre 3 doit venir du bloc de fréquence  = 0 et

les valeurs propres 4 et 5 doivent venir des blocs de fréquence  = 2 et  = -2 et

[ BS88 ]

[ DS78 ]

Courbure bornée

A noter dans le cas où les conditions nécessaires de continuité C2 sont satisfaites :

la courbure est bornée si

Sinon la courbure est nulle et la surface limite fait un « plat » au niveau du sommet irrégulier

[ BS88 ]

Carte caractéristique

La carte caractéristique est un anneau de surface régulière défini à partir des vecteurs propres m1 et m2 (position des points dans le plan tangent) :

On part d'un morceau régulier de surface triangulaire (ici, Box-spline C2 à 6 directions : Loop 1987)

Domaine :

u  [0,1], v  [0,1]

Carreau de surface

et

son polygone de contrle

Vi

[ Rei95 ]

Carte caractéristique

On considère des anneaux autour du sommet irrégulier pour avoir suffisament de points de controle Vi de coordonnées (m1i, m2i) pour construire une bande de surface régulière :

Au cours des subdivisions, cet anneau converge vers le sommet irrégulier, décrivant ainsi la convergence de la surface limite dans le plan tangent

Domaine

[ Rei95 ]

Conditions suffisantes de Continuité C1

La surface limite est de continuité C1 au sommet irrégulier si :

Les conditions nécessaires sur les valeurs propres sont satisfaites

La carte caractéristique est régulière et injective :

Garanti que la surface ne se recouvre pas

[ Rei95 ]

[ Pra98 ]

[ Zor00 ]

[ PR98 ]

D'autres conditions

Il existe d'autres conditions nécessaires pour qu'un schéma soit de continuité C2

Par exemple, la précision quadratique :

[ GBD05 ]

Schémas traditionnels aux sommets irréguliers

Sous leur forme traditionnelle, les schémas Box-splines utilisés (Loop, Catmull-Clark) ont les coefficients des règles aux sommets irréguliers calculées pour satisfaire les conditions suivantes :

Schéma C1 aux sommets irréguliers

Composante « coupe » de la courbure bornée

Limites

Les irrégularités

Autour des points irréguliers :

[ BK04 ]

[ SB03 ]

Les irrégularités

Autour des points irréguliers :

Artefact Polaire

[ BK04 ]

[ SB03 ]

Les irrégularités

Autour des points irréguliers :

Artefact Polaire

Surface seulement C1

[ BK04 ]

Les irrégularités

[ SB03 ]

Les irrégularités

[ SB03 ]

Les irrégularités

Artefact Polaire

[ SB03 ]

Les irrégularités

[ SB03 ]

Les irrégularités

Artefact Radial

[ SB03 ]

Courbure aux sommets irréguliers

Catmull-Clark :

Courbure bornée uniquement sur la « coupe » ( )

Mais la valeur propre de selle est supérieure à la valeur propre de coupe ( )

[ KPR04 ]

[ PR04 ]

Courbure aux sommets irréguliers

Catmull-Clark :

Courbure bornée uniquement sur la coupe ( )

Mais la valeur propre de selle est supérieure à la valeur propre de coupe ( )

[ KPR04 ]

[ PR04 ]

Conclusion

Subdivision basée Box-spline

Les plus

Généralisation des surfaces Box-splines à des polygones de contrôle quelconques

Connaissance de la surface limite

Schémas de continuité C2 (sauf en quelques points isolés)

Simplicité de calcul des règles régulières

Les schémas standards sont tout de même C1 aux sommets irréguliers

Subdivision basée Box-spline

Les plus

Généralisation des surfaces Box-splines à des polygones de contrôle quelconques

Connaissance de la surface limite

Schémas de continuité C2 (sauf en quelques points isolés)

Simplicité de calcul des règles régulières

Les schémas standards sont tout de même C1 aux sommets irréguliers

Les moins

Difficulté d'améliorer le comportement du schéma aux sommets irréguliers

Artefact polaire

Artefact radial

Discontinuité de courbure

Convergence en selle (ou coupe)

Quelques idées de recherche

Améliorations du comportement des schémas aux sommets irréguliers

Subdivision à partir de couple Point / Normale

Subdivision sur les nuages de points

Livres et cours

A. Iske, E. Quak and M.S. Floater (Eds). Tutorial on Multiresolution in Geometric Modelling. Springer, 2002.

J. Warren and H. Weimer. Subdivision methods for geometric design : a constructive approach. San Francisco: Morgan Kaufmann, 2002.

D. Zorin and P. Schröder. Subdivision for modeling and animation. SIGGRAPH 2000 Course Notes, 2000.

Bibliographie

[BGD05]	L. Barthe , C. Gerot, M.A. Sabin and L. Kobbelt. Simple computation of the eigencomponents of a subdivision matrix in the Fourier domain. Advances in Multiresolution for Geometric Modelling, N.A. Dodgson et al (eds), Springer-Verlag, pages 245-257, 2005.

[BK04]	L. Barthe and L. Kobbelt. Subdivision scheme tuning around extraordinary vertices, Computer Aided Geometric Design, 21(6), pp. 561-583, 2004.

[BS88]	A.A. Ball and D.J.T. Storry. Conditions for tangent plane continuity over recursiveley generated B-spline surfaces. ACM Transactions on Graphics, 7(2), pp. 83-102, 1998.

[CC78]	E. Catmull and J. Clark. Recursively generated B-spline surfaces on arbitrary topological meshes. Computer Aided Design, 10 (6), pp. 350-355, 1978.

[dBH94]	C. de Boor, D. Hollig and S. Riemenschneider. Box Splines. Springer-Verlag, New York, 1994.

[DS78]	D. Doo and M.A. Sabin. Analysis of the behaviour of recursive subdivision surfaces near extraordinary points. Computer Aided Design, 10 (6), pp. 356-360, 1978.

[GBD05]	C. Gerot, L. Barthe, N.A. Dodgson and M.A. Sabin. Subdivision as a sequence of sampled Cp surfaces. Advances in Multiresolution for Geometric Modelling, N.A. Dodgson, M.S. Floater and M.A. Sabin (eds), Springer-Verlag, pp. 259-270, 2005.

[KPR04]	K. Karciauskas, J. Peters and U. Reif. Shape characterization of subdivision surfaces - case studies. Computer Aided Geometric Design, 21(6) , pp. 601-614, 2004.

[Loo87]	C. Loop. Smooth subdivision surfaces based on triangles. Master's thesis, University of Utah, 1987.

Bibliographie

[Pra98]	H. Prautzsch. Smoothness of subdivision surfaces at extraordinary points. Adv. Comp. Math., 14, pp. 377-390, 1998.

[PR98]	J. Peters and U. Reif. Analysis of algorithms generalizing B-spline subdivision. SIAM Journal of Numerical Analysis, 35(2), pp. 728-748, 1998.

[PR04]	J. Peters and U. Reif. Shape characterization of subdivision surfaces - basic principles. Computer Aided Geometric Design, 21(6), pp. 585-599, 2004.

[PS04]	J. Peters and L.J. Shiue. Combining 4- and 3-direction Subdivision. ACM Transaction on Graphics, 23 (4), pp. 980-1003, 2004.

[Rei95]	U. Reif. A unified approach to subdivision algorithms near extraordinary vertices. Computer Aided Design, 12, pp. 153-174, 1995.

[SB03]	M.A. Sabin and L. Barthe. Artifact in recursive subdivision surfaces. Curve and Surface Fitting: St Malo 2002, A. Cohen, J.L. Merrien and L.L. Schumaker (eds), Nashboro Press, Brentwood, pp. 353-362, 2003.

[Zor00]	D. Zorin. A method for analysis of C1-continuity of subdivision surfaces. SIAM Journal of Num. Anal., 35 (5), pp. 1677-1708, 2000.

Merci pour votre attention

Questions ?

2004-09-27T14:41:30