Samuel Loury Schéma de Subdivision Box Spline

De Ensiwiki
Aller à : navigation, rechercher


Schéma de subdivision Box Spline

Labo LJK
Equipe MGMI
Encadrants Sylvain.Meignen_(at)_imag.fr

Etudiant

Samuel Loury

Introduction

Dans le domaine de la conception assistée par ordinateur, dans la modélisation 3D ou dans l'animation, on cherche a obtenir des maillages les plus esthétiques possibles. L'esthétique commence ici par des surfaces lisses qu'il faut pouvoir imaginer mais aussi calculer de façon simple et rapide. La représentation de Bézier (par l'ingénieur français Pierre Bézier), par exemple, a été employée à l'origine pour la conception par ordinateur de voitures pour l'entreprise Renault. Elle approxime un polygone par une courbe aussi lisse que l'on veut. La représentation date de 1962, les premières exploitations datent du début des années 1970.

Bezier.jpg

Le calcul de tous les points de cette courbe, pour un assemblage plus compliqué s'avérait lent. Il a alors démontré que par un procédé dit de subdivision, on pouvait approcher cette courbe de façon aussi précise que l'on voulait en multipliant le nombre de points du polygone à chaque étape. Voici ce qu'il obtenait en 1970

Wvb.jpg

Depuis lors, de nouvelles représentations sont apparues. La plus populaire est la représentation B-spline qui consiste en un recollement de courbes Béziers et plus tard les Box-splines. Les courbes sont alors devenues encore plus compliquées mais aussi bien plus intuitives à manipuler (la modification d'un point d'une courbe de Bézier se répercute sur toute la courbe alors qu'avec la représentation B-spline, la modification a un impact local). La subdivision de tels courbes est nécessaire pour pouvoir obtenir des maillages esthétiques en un minimum de temps.

Réciproquement, l'étude des schémas de subdivisions permet d'extraire des représentations de courbes vérifiant des propriétés à caractère esthétique. Parmi les plus connues figurent la subdivision de Catmull-Clark ou la subdivision Box-Spline.

Monkey.jpg devient par subdivision de Catmull-Clark Monkey subdiv.jpg

La subdivision est notamment fortement employée par les entreprises d'animation pour modéliser leurs personnages:

Geri game.jpgFf.jpg

Pour l'animation, les b-splines permettent de créer des chemins et des maillages aux formes de serpentins par des procédés dis de 'skining'.

Spirale.jpg

Mais la subdivision peut aussi être utilisée à d'autres dessins, par exemple pour les fractales comme pour le tracé de la coubre du dragon :

Dragon.jpg

Il est donc très intéressant d'étudier les schémas de subdivision et notamment dans le cas particulier des Box-Splines (pour les fractales, c'est une autre branche des subdivision qu'il faut regarder, car on ne cherche plus à converger) pour pouvoir en extraire des méthodes de calcul plus rapides, ou pour tenter (pourquoi pas?) de fournir des représentations de courbes plus adaptées pour certains domaines.

Mon TER avait justement pour but l'étude des schémas de subdivision dans le cadre des Box-splines. J'ai donc voulu tout d'abord étudier la théorie des schémas de subdivision dans un cadre général avant de me pencher sur la partie Box-Spline proprement dite.

J'ai étudié une partie de cette théorie, en fournissant des applications numériques des résultats des théorèmes que je découvrais. Cependant, j'ai utilisé beaucoup de temps à reformuler des démonstrations de théorèmes qui, bien que clairement exposées, souffraient d'ambigüités et étaient parfois basées plutôt l'intuition que sur des définitions mathématiques claires. En bref, mon travail a essentiellement consisté à comprendre les schémas de subdivision et à donner de nouvelles démonstrations de certains théorèmes existants.

Eléments de pré-requis

B-Splines

Les B-splines forment une suite de fonctions (B_i)_{i\in\mathbb{N}} qui vérifient des propriétés qui permettent de leur associer un schéma de subdivision uniformément convergent. Voici les tracés successifs des B-splines les plus simples et les plus connues (tracé de B_0 à B_5):

B-splines.gif

Elles ont entre autre la propriété que la somme de leurs translatés par les entiers vaut 1, ou plus clairement : \forall t\in\mathbb{R},\sum_{\alpha\in\mathbb{Z}}B_i(t-\alpha)=1. On dit qu'elles reproduisent les constantes.

Subdivision

Ces fonction vérifient aussi B_i(2^k t-\alpha)\in<B_i(2^{k+1}t-\beta)>. Donc si une courbe est obtenue pour tout t par combinaison linéaire de points avec B_i(2^k t -\alpha) comme coefficient pour le point d'indice \alpha, alors cette courbe peut aussi être décrite par un autre ensemble de points de taille deux fois plus grande (on parle de subdivision diadique) dont les coefficients sont les B_i(2^{k+1} t -\alpha). Ce qui est le principe même de la subdivision. En fait, un schéma de subdivision est une formule de passage d'une suite de points à une autre. Elle est donc définie par un ensemble de coefficients appelé le masque (a_\alpha)_{\alpha\in\mathbb{Z}^s}. On pose cependant les contraintes de finitude de cet ensemble et on demande à chaque coefficient de ne pas être nul. La formule s'exprime alors : f^{k+1}_\alpha = \sum_{\beta\in\mathbb{Z}^s}a_{\alpha-2\beta}f^k_\beta

Travail réalisé

Étude préliminaire

J'ai tout d'abord étudié le cas de B-splines car il s'agit d'un exemple simple de représentation, similaire à celui des Box-Splines (des Box-Splines simples peuvent s'obtenir par produit tensoriel de B-splines). J'ai découvert qu'il y avait équivalence entre une courbe spline et ses points de subdivision en passant dans le domaine de Fourier. Puis j'ai codé des programmes scilab permettant de tracer des courbes B-splines pour me rendre compte du caractère esthétique produit par la régularité de la courbe obtenue. J'ai aussi tracé les différentes étapes de subdivision, pour vérifier visuellement les théorèmes de convergence du schéma de subdivision (convergence des polygones créés vers la courbe). Cela est faisable car dans le cas de polygones simples telles que je peux les tracer à la main (moins de 50 points), la courbe peut être calculée rapidement (de l'ordre de la seconde pour 10 points sur ensibull, machine cadencée à 1.5GHz).

Courbe spline.jpgCourbe spline2.jpg

Pour information, la courbe de droite à été tracée d'abord directement avec 181 points en 3.4 secondes alors que la subdivision à 256 points pris 2.3 secondes.

Étude des schémas de subdivision

Comme expliqué dans l'introduction, j'ai étudié de façon théorique les schémas de subdivision. Je me suis donc penché sur les études de Nira Dyn, une personne de référence en terme de schéma de subdivision et sur la thèse de Sahbi Ayari présentée en mai 1997 à la faculté des études supérieures (Université de Montréal).

J'ai découvert des théorèmes fascinants, comme par exemple celui que j'appelle théorème fondamental dans mon rapport : il prouve l'existence d'une unique fonction continue à support compacte déterminée par le masque d'un schéma de subdivision uniformément convergent (qui reproduit les constantes!!). Cette fonction décrit elle même la courbe résultante des points tracés.

Pour être un peut plus explicite:

  • hypothèse de départ : les points obtenus à chaque étape du schéma de subdivision convergent de façon globale vers une courbe continue (uniforme convergence du schéma de subdivision). Comme par exemple dans le schéma suivant (appelé schéma de Chaïkin):
Cc.gif
  • Alors: on obtient une fonction qui permet de calculer les coefficients à chaque instant t des points de départ pour le calcul de la courbe vers laquelle le schéma tend.

La preuve du théorème a fourni deux méthodes pour le calcul de cette fonction (elles sont entièrement décrites dans le rapport). Pour le schéma de Chaïkin, j'obtiens l'approximation :

Cha T.jpg

Ici, la première méthode fournit le résultat sur 512 points en 0.8 secondes alors que la deuxième prend 7.6 secondes. On peut ici vérifier la cohérence de ce résultat, car le schéma de Chaikin n'est autre que celui associé à la B-spline B_2 dont le tracé est donné plus haut (dans les pré-requis).

Apport personnel

Pour la démonstration de ce théorème, j'ai du créer une proposition préliminaire donnant une relation permettant de déterminer les points à l'itération k du schéma en fonction des points à n'importe quel itération précédente et de \delta^0 (la suite de points dont tous sont nuls sauf celui d'indice 0 qui vaut 1). Voici l'énoncé de la proposition que j'ai conçue.

Proposition.jpg

Elle figure, ainsi que sa démonstration, dans le rapport. Elle exprime le fait que l'on peut séparer l'influence des points de la courbe et du schéma de subdivision associé. On pourrait alors obtenir la courbe en appliquant le schéma de subdivision non pas sur ses points, mais sur ceux liés à une autre courbe.

Mais aussi

J'ai aussi vu un théorème donnant une condition suffisante pour la convergence uniforme de schéma basé sur une condition de stabilité d'une fonction reproduisant les constantes (c'est à dire dont la somme des translatées par les entiers donne la fonction unité). Puis j'ai aussi découvert l'ambivalence entre un schéma de subdivision et sa dérivée d'ordre k. Les résultats suivant sont valables dans le cas d'indices à une dimension. À partir des points (f^k_\alpha)_{\alpha\in\mathbb{Z}}, on peut définir une nouvelle suite de points df^k_\alpha = 2^k (f^k_{\alpha+1}-f^k_\alpha). On appelle ces nouveaux points les dérivées partielles des points (f^k_\alpha). On peut appliquer à nouveau cette opération et obtenir des dérivées partielles à des ordres choisi. J'ai découvert dans une étude de Nira Dyn un théorème indiquant que si un schéma de subdivision vérifie certaines conditions simples, alors ses dérivées partielles vérifient aussi un schéma de subdivision. On peut alors décrire des schémas de subdivision des dérivées successives allant jusqu'à ce l'un d'entre eux ne vérifie plus ces conditions. Dans cette étude, deux théorèmes démontrent qu'il suffit d'avoir la convergence uniforme du schéma de subdivision de la dérivée partielle d'ordre i pour obtenir la régularité C^i(\mathbb{R}). Or la régularité d'une courbe est en rapport direct avec nos critères d'esthétisme. À l'heure où je rédige ces lignes, je suis encore en train de chercher à démontrer ces théorèmes de façon plus formelle que ce que j'ai découvert jusqu'alors. Je n'ai donc pas encore eu le temps de fournir des exemples numériques de cette partie.

Conclusion

Le sujet m'a semblé trop vaste pour être traité seulement dans le cadre d'un TER. Cependant, ce travail m'a permis une bonne compréhension des schémas de subdivision et sera une base solide pour une étude plus approfondie dans l'avenir (pour traiter entièrement le sujet en introduisant les Box-Splines par exemple). Elle aura aussi conduit à une traduction en français et une vulgarisation de plusieurs théorèmes fondamentaux concernant la subdivision.

Une fois cette étude terminée, il sera intéressant d'étudier les vitesses de convergence des méthodes de calcul de subdivision extraites. Puis de tenter d'obtenir de nouvelles représentations de surfaces dont les schémas convergeraient plus vite, avec une étude sur les compromis vitesse de convergence <-> régularité.

Références

Pour l'algorithme de calcul des B-splines, je me suis inspiré de l'article de Wikipédia [1]

Pour l'étude, j'ai principalement trouvé matière dans ces trois oeuvres :

Pour les schémas de subdivision
  • Nira Dyn, Subdivision Schemes in Computer-Aided Geometric Design, W.Light, Clarendon Press, 1992 (Lien - > [2])
  • Sahbi Ayari, Schémas de subdivision pour la construction de courbes, Université de Montréal, 1997 (Media:These.pdf)


Pour les B-splines et les Box-Splines
  • Prautzsch Hartmut et Boehm Wolfgang et Paluszny Marco, Bézier and B-Spline Techniques, Springer, 2002

Documents additionnels

(explications dans le fichier README)