Projet image 2015 : Modeleur 3D par B-Mesh

De Ensiwiki
Aller à : navigation, rechercher
Project schedule.png
Titre du projet Modeleur 3D par B-Mesh
Cadre Projets de spécialité
Page principale Projets de spécialité image

Encadrants Thomas Delame, Antoine Begault

Étudiants

Sujet

Introduction

Les logiciels de modélisation 3D actuels sont complexes à utiliser pour des artistes et infographistes. Ces derniers ont besoin une formation pour maîtriser ces logiciels et ils prennent du temps pour construire leurs personnages.

Objectifs

L'objectif de ce projet de spécialité est donc le développement d'une interface graphique permettant de créer simplement et efficacement le maillage d'une forme 3D, à partir de sphères clés et de liens entre ces sphères.

L'objectif minimal est que l'utilisateur donne en entrée un squelette « simple » composé des sphères clés et des segments entre elles (sous format txt) et qu'on fournisse en sortie le maillage correspondant à ce squelette (sous format obj). On dit qu'un squelette est « simple » quand les segments ne se croisent pas et quand il n'y a pas de sphère clé inclus dans une autre sphère clé..

L'utilisateur pourra enregistrer le maillage obtenu avec l'application pour l'utiliser avec un autre logiciel de modélisation 3D. Il aura un maillage quadrangulaire, modèle utilisé dans l'industrie, qui est très lisse (avec un bon edge flow) qui lui permettra d'ajouter des détails et des textures par exemple. Enfin, cela donne un outil global pour la modélisation et pour l'animation des modèles 3D articulés.

Les utilisateurs visés sont les chercheurs en modélisation 3D, les infographistes et les artistes travaillant dans le modélisation 3D (films d'animation, jeux vidéos, etc).

Interface Graphique

Nous proposons pour ce sujet une interface graphique qui permet à un utilisateur lambda de créer simplement son squelette et de sauvegarder le maillage généré pour pouvoir être utilisé après dans d'autres logiciels de modélisation/sculpture.

Notre programme propose les fonctionnalités suivantes:

  • chargement d'un squelette pré-crée (au format .txt);
  • sauvegarde d'un squelette (au format .txt)
  • sauvegarde d'un maillage (au format .obj);
  • création interactive de squelette;
  • possibilité d'afficher le maillage après chaque étape de l'algorithme ou bien tout générer d'un coup.
Aperçu de notre programme

Principe de l'algorithme de modélisation B-Mesh [1]

Lecture du squelette

Tout d'abord, avant d'appliquer l'algorithme, on lit le fichier texte donné en entrée pour détecter les sphères et les segments. On sauvegarde également les voisins de chaque sphère. On a trois types de sphères :

  • joint node : sphère qui possède au moins trois voisins (en rouge);
  • connection node : sphère qui possède exactement deux voisins (en bleu);
  • end node : sphère qui possède exactement un voisin (en jaune).

Il y a aussi des sphères vertes qui sont les sphères n'ayant aucun voisin dans le squelette.

Affichage d'un squelette pré-crée


Interpolation

La première étape consiste à calculer les sphères, appelées 'inbetween-balls, qui complètent de manière régulière les segments liant les sphères clés. Ainsi, nous obtenons un premier aperçu du personnage.

Sweeping

L'étape de 'sweeping (« balayage » en anglais) permet de construire un premier maillage approximant les branches du squelette : à partir de chaque joint node, nous créons un maillage englobant les connection nodes, les end nodes et les inbetween-balls.

Pour cela, pour chaque segment de branche, nous calculons un repère local qui permet de placer les points du maillage autour des inbetween-balls, tels que le plan formé par ces quatre points soit orthogonal au segment. Pour une connection node, nous plaçons les points du maillage dans le plan bissecteur entre les deux segments reliés à la connection node. Le plan bissecteur de deux segments est le plan tel que un segment soit le symétrique de l'autre par rapport à ce plan. Pour une end node, nous plaçons les points du maillage comme pour les inbetween-balls et nous ajoutons quatre autres points qui ferment le maillage.

Pour éviter les intersections entre les faces du maillage au niveau des connection nodes et pour réduire le nombre de points, nous plaçons des points du maillage une inbetween-ball sur deux et il y a au moins une inbetween-ball sans points du maillage qui sépare deux sphères.

Sweeping

Stitching

Après le sweeping, on fait le stitching ("suture" en anglais) qui constitue, pour chaque joint node, à compléter le premier maillage formé par le sweeping en reliant les points des différents maillages autour de la joint node par une enveloppe convexe. Pour cela, on triangularise l'enveloppe convexe à l'aide de la bibliothèque CGAL. Ensuite, on oriente correctement les triangles pour que les normales des faces soient vers l'extérieur. Enfin, on passe d'un maillage triangulaire à un maillage quadrangulaire pour l'enveloppe convexe. Pour cela, on définit un score pour chaque arête, score = A*(n_1.n_2), où A est la somme des aires des deux triangles ayant cette arête en commun et  n_1 \ et \ n_2 sont les normales unitaires des deux triangles. On fusionne alors les deux triangles adjacents avec l'arête commune qui a le score le plus grand, puis on continue selon le score de manière décroissante.

Pour la triangularisation de l'enveloppe convexe, il faut faire attention au fait que l'enveloppe peut être mal orientée à cause du fait que le maillage correspondant s'intersecte avec le maillage d'une des branches de la joint node. Ce problème arrive quand le maillage créé par le sweeping est trop éloigné des sphères.

Après triangularisation de l'enveloppe convexe
Problème de mauvaise orientation dû à l'intersection entre les maillages (ici entre le bras droit et le haut du corps)


Malheureusement, nous n'avons pas eu le temps d'implémenter le passage du maillage triangulaire au maillage quadrangulaire.

Subdivision et affinement du maillage

Courbures et directions principales

Avant d'évoquer la subdivision, l'évolution et le fairing, il est important de définir les courbures principales et les directions principales en un point p, que l'on utilise après. Les courbures et directions principales sont respectivement les valeurs propres et les vecteurs propres d'un endomorphisme symétrique appelé endomorphisme de Weingarten. Le but est donc d'estimer la matrice W de cet endomorphisme pour en déduire ses valeurs et vecteurs propres.


On pose (o_u, o_v) un repère orthonormé du plan tangent au point p (W devra donc être symétrique). On peut déterminer W à l'aide des équations suivantes:

W{(e_i^p)_u \choose (e_i^p)_v} = {(n_i - n_x)_u \choose (n_i - n_x)_v}

e_i^p est la projection d'une arête incidente à p dans le plan tangent, n_i est la normale au point p_i et ((x)_u, (x)_v) représente les coordonnées d'un point dans le repère (o_u, o_v).

On a donc autant d'équations que de voisins (sachant que dans notre cas, un point a au moins trois voisins). L'ensemble de ces équations nous permet ainsi de déterminer un système linéaire dont les inconnues sont les éléments de W.

La résolution de ce système linéaire ainsi que la détermination des éléments propres ont été faites à l'aide de la bibliothèque d'algèbre linéaire Eigen, qui propose déjà des méthodes efficaces pour résoudre des systèmes linéaires et pour déterminer les éléments propres d'une matrice.

Subdivision et évolution du maillage

Dans un premier temps, on applique au maillage un algorithme de subdivision de surface: on rajoute des points et des faces pour que le nouveau maillage soit plus raffiné. L'algorithme recommandé par l'article (et que nous avons choisi) est l'algorithme de Catmull-Clark. Cet algorithme présente deux avantages:

  • il transforme un maillage quelconque en un maillage uniquement constitué de quadrangles, ce que nous voulons;
  • c'est un algorithme classique, qui est déjà implémenté par OpenMesh.
Subdivision du maillage avec l'algorithme de Catmull-Clark


Cependant, le maillage obtenu après cette étape de subdivision dévie de la forme constituée par l'ensemble des sphères (ce que l'on peut voir sur la figure ci-dessus). On applique alors un algorithme d'évolution de maillage, qui va corriger ce problème. Ce processus d'évolution est guidé par une ligne de niveau d'un champ scalaire \mathcal{I} défini sur l'ensemble des sphères.

On définit la fonction f_i suivante: f_i = \left( 1 - \left(\frac{r}{R_i}\right)^2 \right)^2, si  r \le R_i et 0 sinon,

avec :

  •  r^2 = (x - c_x^i)^2 + (y - c_y^i)^2 + (z - c_z^i)^2 ;
  • R_i = \alpha r_i, r_i étant le rayon de la sphère i et \alpha un paramètre que l'on fixe égal à 1.5;
  • (c_x^i, c_y^i, c_z^i) centre de la sphère i.

Un point p n'a donc plus besoin d'évoluer s'il vérifie la condition suivante:  \mathcal{I} = \sum_{i=1}^{n} f_i - T = 0, où T est un paramètre qui permet de contrôler la manière avec laquelle le maillage va "coller" à l'union des sphères. Une valeur de T grande aboutira à un maillage plus proche de l'ensemble de sphères.


Maintenant que l'on sait quand un point n'a plus besoin d'évoluer, comment va-t-il justement évoluer ? Pour cela, on va considérer notre maillage initial comme une surface active (c'est à dire une surface qui évolue avec le temps). Dans ce cas, l'évolution d'un point x est dictée par l'équation différentielle suivante:

\frac{d\textbf{x}}{dt} = \textbf{n}(\textbf{x}, t) \mathcal{F}(\textbf{x}, \textbf{n}, \kappa, \mathcal{I}, ...)

\frac{d\textbf{x}}{dt} est la vitesse, \textbf{n} = -\frac{\nabla\mathcal{I}}{\Vert\nabla\mathcal{I}\Vert} est le vecteur normal et \mathcal{F} est une fonction qui dépend de plusieurs paramètres tels que la position, la normale, le champ scalaire ou encore les courbures principales.

La formulation de \mathcal{F} est la suivante: \mathcal{F} = ( \mathcal{I} - \mathcal{I}_{cible} ) f(\kappa) . Cette formulation signifie qu'un point évoluera plus vite s'il est éloigné par rapport à la surface cible. La fonction f, qui fait intervenir les courbures principales \kappa_1 et \kappa_2 permet de contrôler la vitesse d'évolution en fonction de l'endroit où le point se trouve. Une expression possible est la suivante: f = 1 / (1 + |\kappa_1| + |\kappa_2|).


On peut donc déterminer la position du point x à l'instant t + dt de la manière suivante:

 \textbf{x}(t + dt) = \textbf{x}(t) + \textbf{n}(\textbf{x}, t) \mathcal{F}(\textbf{x}, ...) dt

Pour éviter d'éventuelles oscillations, la valeur de dt doit être bien choisie. dt doit vérifier l'inégalité suivante pour éviter les oscillations:

 dt \le \frac{min\{r_i\}}{2^k \mathcal{F}_{max}} , où k est le niveau de subdivision du maillage.

Cependant, même avec cette inégalité vérifiée, nous avons eu des problèmes d'oscillations sur certaines entrées contenant beaucoup de sphères. Pour régler ce problème, nous avons du ajouter une autre condition: nous avons décidé d'arrêter l'évolution du point si le champ scalaire évalué au point obtenu après évolution est supérieur au champ scalaire du point avant évolution, ce qui permet d'éviter les oscillations et donc éviter d'avoir un programme très très lent sur certaines entrées.

État du maillage après évolution


Sur les images ci-dessous, on peut voir l'influence du paramètre T sur le maillage. Le maillage a été généré avec T = 0.1 (à gauche) puis avec T = 0.3 (à droite). On remarque bien que le maillage de droite est plus collé aux sphères que le maillage de gauche.

Cependant, l'image de droite met en lumière un phénomène que nous n'avons pas pu traiter. On remarque que le maillage n'est pas vraiment lisse: il suit plutôt l'ensemble des sphères, ce qui donne cet effet "gondolé". Ce phénomène n'est pas forcément inattendu: en effet, moins il y aura de sphères entre deux sphères clés, plus cet effet sera visible (puisque les sphères seront plus espacées). Une solution pour limiter cet effet serait d'augmenter le nombre de sphères d'interpolation (inbetween-balls) entre chaque paire de sphères clés. Mais le temps de calcul sera plus long: il faut trouver un compromis entre effet visuel et temps de calcul. Dans notre cas, choisir un T plus faible limite le phénomène.

Évolution du maillage avec T = 0.1
Évolution du maillage avec T = 0.3

Edge Fairing

Si l'évolution permet de faire en sorte que le maillage épouse au mieux l'union de sphères, il a le désavantage de détériorer l'edge flow (c'est à dire que les points ne sont pas parfaitement alignés, ce qui pourrait donner des résultats assez désagréables si l'on veut texturer la forme 3D). Pour régler ce problème, on effectue sur chaque point du maillage un fairing local, afin d'aligner correctement le point par rapport à ses voisins directs. Afin d'effectuer ce traitement, on a besoin de distinguer deux types de points:

  • ceux ayant exactement quatre voisins;
  • ceux n'ayant pas quatre voisins et ceux dont les courbures principales sont identiques.
Principe de l'edge fairing


Pour un point p ayant exactement quatre voisins, on détermine sa nouvelle position en minimisant la fonction objective suivante:

f(x) = |(a-x).e_v| + |(b-x).e_u| + |(c-x).e_v| + |(d-x).e_u|

où:

  • a, b, c et d sont les projections des quatre voisins de p dans le plan tangent;
  • e_u et e_v sont les directions principales au point p.

Il faut bien faire attention à ce que les coordonnées des points soient exprimées dans le repère lié au plan tangent et non pas dans le repère d'origine (sinon les résultats ne sont pas cohérents). On obtient donc les coordonnées du point dans le repère du plan tangent, qu'il faut ensuite transformer dans le repère d'origine.

La minimisation de la fonction objective se fait à l'aide de la bibliothèque NLopt, qui permet de résoudre des problèmes d'optimisation assez facilement.


Pour l'autre type de points en revanche, cette méthode ne peut pas s'appliquer. On utilise alors l'umbrella operator [2]. On cherche à résoudre \Delta f = 0, où f représente notre surface. On approxime ce laplacien par l'opérateur suivant (umbrella operator):

U(p) = \frac{1}{n} \sum_{i=1}^{n} p_i - p

p est le point dont on cherche la nouvelle position et p_i ses voisins. Résoudre \Delta f = 0 revient donc à dire que la nouvelle position correspond à la moyenne des voisins du point. Il faut ensuite projeter le point ainsi obtenu dans le plan tangent pour connaître la nouvelle position du point.

Difficultés rencontrées

La principale difficulté a été le passage du côté théorique au côté pratique: la compréhension de l'algorithme a été relativement simple et rapide mais le passage au code a été beaucoup plus compliqué. En effet, nous avons dû beaucoup réfléchir sur l'organisation de notre code. De plus, nous avons dû apprendre à utiliser différentes librairies comme OpenMesh, Eigen et CGAL. Enfin, l'article a expliqué l'algorithme appliqué à des cas simples et il n'est pas beaucoup allé dans les détails. Donc cela nous a amené à réfléchir nous-mêmes comment implémenter certaines parties de l'algorithme comme le stitching.


Si nous avions eu plus de temps, nous aurions aimé:

  • éventuellement trouver une structure de donnée plus efficace pour le squelette: en effet, nous utilisons actuellement une matrice dont le terme général représente le lien (s'il existe) entre la sphère i et la sphère j. On stocke également un certain nombre de données utiles (comme les inbetween-balls). Mais cette structure oblige parfois à parcourir l'ensemble de la matrice pour récupérer les éléments, ce qui est lourd quand il y a beaucoup de sphères. Nous aurions pu utiliser une structure d'arbre (qui parait plus adaptée dans notre cas). Cependant, cette structure posait d'autres problèmes dans certaines parties de l'algorithme;
  • améliorer le temps de calcul pour l'évolution du maillage: le processus est très lent quand il y a beaucoup de sphères. Une idée évoquée avec nos encadrants est la suivante: utiliser un octree. Un octree permet de diviser l'espace 3D en plusieurs cellules. En choisissant bien ce que l'on stocke dans nos cellules et quand la division soit se faire, on peut faire en sorte que le champ scalaire n'utilise que les sphères liées à la cellule dans laquelle se trouve le point dont on veut calculer le champ scalaire. Cela permettrait donc de gagner beaucoup de temps de calcul et donc d'avoir un programme bien plus réactif.
  • faire en sorte que le maillage soit toujours lisse et non pas gondolé;
  • améliorer l'algorithme pour qu'il puisse s'adapter aux cas où les maillages pourraient s'intersecter.

Bilan et perspectives

Ce projet nous a été très bénéfique car le contexte était complètement différent par rapport au projet Génie Logiciel. Nous n'avions pas de cahier des charges détaillé ni de spécifications précises, nous avions l'article comme base et nous devions partir de zéro. Avec l'aide de nos encadrants, nous avons du réfléchir à toutes les structures de données et à la manière d'implémenter le plus efficacement possible les algorithmes. C'est un projet qui a été certes moins évident mais beaucoup plus enrichissant; il permet d'avoir une bonne expérience pour mener des projets à partir de "rien", ce qui arrivera sûrement dans notre future vie active.

En plus d'apporter des compétences humaines et organisationnelles, ce projet nous a apporté de nombreuses compétences techniques: nous avons appris par exemple à utiliser un certain nombre de bibliothèques (OpenMesh, CGAL, ...) qui pourront nous servir par la suite, surtout si on veut continuer dans le domaine de l'informatique graphique.

À consulter


Références

[1] Zhongping J., Ligang L., Yigang W., B-mesh: A modeling system for base meshes of 3d articulated shapes, Computer Graphics Forum 29 (7) (2010) 2169–2177

[2] Kobbelt L., Campagna S., Vorsatz J., Seidel H.-P.: Interactive multi-resolution modeling on arbitrary meshes. In Proc. of SIGGRAPH (1998), pp. 105–114