Projet image 2012 : Surfaces de subdivision interpolant des courbes de bords

De Ensiwiki
Aller à : navigation, rechercher

CDROM.png  Informatique  Mathematiques.png  Mathématiques 


Project schedule.png
Titre du projet Surfaces de subdivision interpolant des courbes de bord données
Cadre Projets de spécialité
Page principale Projet image 2012 : Surfaces de subdivision interpolant des courbes de bords

Encadrants Stephanie Hahmann


Contexte

Exemple de subdivision avec Catmull-Clark

Dans certains films d'animation, l'enjeu principal est de réaliser des objets 3D aux contours "lisses" (c'est à dire étant de classe G 2) de manière à les rendre aussi réalistes que possible. L'une des méthodes les plus utilisées pour satisfaire cette contrainte est la représentation en surfaces de subdivision.
Il existe deux types d'algorithme de subdivision de maillage : les algorithmes d'approximation et les algorithmes d'interpolation. En règle générale, les algorithmes d'interpolation assurent, au niveau des points réguliers, une continuité G1 alors que ceux d'approximation assurent une continuité G 2. Le plus connu (et utilisé) des algorithmes d'approximation est l'algorithme de Catmull-Clark car il donne un résultat de haute qualité (par exemple utilisé pour les longs métrages des Studios Pixar).

L'objectif principal est de garder cette haute qualité de résultats tout en interpolant des courbes de bords données.

Notions utiles

G 2

G 2  : définition de la continuité géométrique au niveau de la dérivée seconde

G^{0} : C(t_{k}^{+}) = C(t_{k}^{-})
G^{1} : G^{0} \and \exists \beta \in R^{+} \ | \ C'(t_{k}^{+}) = \beta C'(t_{k}^{-})
G^{2} : G^{1} \and \exists \chi \in R \ \ \ | \ C'(t_{k}^{+}) = \beta^{2}C''(t_{k}^{-}) + \chi C'(t_{k}^{-})

Algorithme de Catmull-Clark

Entrée : Maillage E.
Sortie : Maillage S.
Le maillage S est le maillage E subdivisé une fois via l'algorithme. On peut bien évidemment ré-appliquer l'algorithme avec S en entrée et ainsi de suite afin d'obtenir un maillage très lisse.
Voici le principe de cet algorithme (une étape de subdivision) :

Principe de Catmull-Clark
  1. On ajoute un sommet par face  : ce sommet est le barycentre de la face.
  2. On ajoute un sommet par arête : ce sommet est le barycentre de l'arête et des deux nouveaux points des faces qui joignent l'arête.
  3. On réajuste les anciens sommets : le nouveau sommet est calculer comme étant la moyenne des anciens points voisins, ainsi que les nouveaux points des faces qui contiennent le sommet que l'on réajuste. Pour ce calcul de moyenne, le sommet se voit attribuer un poids Wn, dépendant de la valence du point (4 si face quads, i.e. une face constituée de 4 sommets ), tandis que les autres points ont un poids égal à 1.

L'algorithme a donc pour conséquence de bouger les anciens points, c'est à dire les points du maillage initial. C'est pour cette raison que c'est un algorithme d'approximation et non d'interpolation.

Exemple Catmull-Clark

Interne/externe

Les faces sont toujours définies comme étant internes au maillage.
Une arête est sur le bord si et seulement si ses deux extrémités le sont. Ainsi, les arêtes, qui sont sur le bord, sont externes. Les autres sont internes.
Dans le cas d'un maillage quads, un sommet est sur le bord si et seulement si il a une valence de 3. Ainsi, les sommets qui sont sur le bord sont externes. Les autres sont internes

Travail réalisé

Algorithmes

De manière forcée

La première idée pour adapter l'algorithme de Catmull-Clark est d'utiliser un maillage initial grossier qui interpole déjà les courbes de bords. On effectue ensuite la subdivision, et, au niveau des bords, on colle les nouveaux points des arêtes externes sur la courbe. Ainsi l'interpolation à forcément lieu, quelque soit le nombre de subdivision que l'on effectue.

Pour ce faire, chaque points externes est associés à une(plusieurs) courbe(s) de bord ainsi qu'à un(des) paramétrage(s)  t \in [0,1] . Nous pouvons ainsi modifier l'algorithme de Catmull-Clark de la manière suivante :

  1. Pour la partie externe du maillage:
    1. arête : créer un nouveau point comme étant le point associé à la courbe commune des deux extrémités (de l'arête) au paramètre t (t étant la moyenne des paramètres associés aux extrémités pour cette courbe). (cf. Schéma).
    2. réajustement de point : ne pas les bouger car ils sont déjà sur la courbe.
  2. Pour la partie interne du maillage : appliquer Catmull-Clark normalement.
alt = Adatation 1 de Catmull-Clark

Nous obtenons ainsi les résultats suivant :

Reesultat

De manière plus naturelle

L'un des effets de Catmull-Clark, lié à son approximation, est qu'il "rétrécit", "contracte" la surface, ou au contraire "l'élargit", en fonction de la courbure.
IMAGE
Ainsi, une seconde idée est de créer un maillage initial qui permet de contrer cet effet. Nous avons pour cela implémenté l'algorithme de Adi Levin Interpolationg Nets Of Curbes By Smooth Subdivision Surfaces. L'idée principale est d'effectuer des ajustements sur les sommets au niveau du bord.
Tout comme la première adaptation, chaque point du bord est associé à une(des) courbe(s) et un(des) paramètre(s). Pour chacun de ces points, on prend en compte la courbure des courbes de bords ainsi que l'écart des paramètres associés aux sommets des arêtes voisines (en effet, plus les points sont proches, moins la subdivision est puissante). Grâce à cela, on peut obtenir un effet de rejet de la courbe (au bord) en présence de fortes courbures.

Toutefois, un tel maillage initial ne permet pas de converger complétement vers une surface interpolant les bords avec Catmull-Clark. En effet, les coins seront forcément arrondis. Ainsi, il faut aussi, comme pour la première adaptation, effectuer des modifications sur les bords en fonction des courbures et de l'écart des paramètres.

Nous obtenons ainsi les résultats suivant :

Resultat

Bien que visuellement on voit que les surfaces sont lisses, il nous faut des outils pour juger, de manière plus précise, la qualité de la surface obtenue.

Visualisation de la qualité

Lignes isophotes

Reflexion lumineuse

Les lignes isophotes se basent sur la réflexion lumineuse. A partir d'un point lumineux, on calcule l'angle de réflexion sur chacune des faces. On affecte ensuite une couleur en fonction de l'angle.
Toutefois, pour une meilleure visibilité, nous avons segmenté la fonction et alterné le noir et blanc.

Coloration isophote

La surface est de bonne qualité si les lignes sont C 2.

Courbure de Gauss

Un second critère pour évaluer la qualité des surfaces obtenues est le calcul de la courbure de Gauss. La courbure de Gauss est une mesure du caractère plus ou moins courbé de la surface en chaque point. Dans le cadre de nos surfaces de subdivision, on la calcule en chaque point de la manière suivante:

Principe des courbures de Gauss

On affiche ensuite la valeur de la courbure en utilisant une échelle de couleur: rouge, jaune, vert, turquoise, bleu. Le rouge représentant les points de courbure minimum et bleu, ceux de courbure maximum. On obtient le résultat suivant:

Surface avec courbures de Gauss

On remarque que les couleurs sont réparties de manière régulière. La surface obtenue est donc lisse.

Interface Graphique

L’interface graphique a facilité l’utilisation des algorithmes et l’analyse des résultats. Il permet de créer et modifier des courbes ainsi que leur nature (polygonale ou Bspline), de créer le maillage initial des deux façons utiles dans les adaptations de Catmull-Clark et de visualiser les lignes isophotes et la courbure de Gauss.

Interface

Les limites

Les algorithmes utilisés sont généraux pour n'importe quel type de courbe et leur nombre. Toutefois, il est nécessaire d'avoir un maillage initial de la surface, or mailler l'espace avec une configuration quelconque des courbe de bords s'avère être délicat,voir très complexe, à réaliser. C'est la raison pour laquelle nous nous sommes limités au cas simple de surfaces définies par 4 courbes de bords.

Types de courbes

Nous avons géré 2 types de courbes : les B-Splines et les courbes polygonales.
Nous avons fait le choix des B-Splines car elles permettent de créer des courbes complexes avec un nombre de points réduit, ce qui facilite la création et l’interaction.
Quant aux courbes polygonales, elles sont définies par un ensemble quelconque de points. De ce fait, n'importe quelle courbe peut être décrite par ces courbes, ce qui a pour but de généraliser notre algorithme à tout type de courbe. L'inconvénient majeur de ces courbes est que, à cause de leur nature discrétisée, elles imposent une limite dans la résolution du maillage : on ne pourra jamais obtenir un maillage plus fin que la résolution de la courbe utilisée au bord. Une solution peut être d'interpoler le "vide" entre deux points par une courbe de bezier.

Maillage initial

Comme nous l'avons mentionné, le maillage initial n'est pas une chose simple à obtenir. Nous avons donc utilisé la méthode de Coons pour obtenir un bon maillage initial interpolant déjà les courbes. Pour l'algorithme "plus naturel", on écarte juste les points du bord en fonction des courbures et de l'écart des paramètres.

Bilan

En conclusion, les surfaces obtenues sont lisses et interpolent bien les courbes de bords. Cependant, le contrôle de la surface finale est difficile à partir des courbes de bords. Cet outil est donc peu adapté au design d'objets 3D complexes. Pour un meilleur contrôle, une solution serait d'interpoler des tangentes de la surface données aux bords.

Références

[1] Adi Levin: Interpolating nets of curves by smooth subdivision surfaces, SIGGRAPH'99
[2] Adi Levin: Combined Subdivision Schemes for the design of surfaces satisfying boundary conditions, CAGD 16, (1999)