Projet image 2015 : Modeleur 3D par surface médiane

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

Encadrants Thomas Delame, Antoine Begault


Étudiants


Sujet

Dans l'ère de la modélisation 3D, la créativité est souvent inhibée : les outils les plus efficaces sont également les plus difficiles à appréhender. Les artistes préfèrent commencer par dessiner et sculpter leurs créations. Ensuite, ils numérisent leurs ébauches avant de passer à des logiciels de modélisation. De plus, ces créations sont souvent figées : le modèle n'est pas articulé. Il faut alors utiliser d'autres logiciels pour définir les articulations puis modifier la pose du modèle.

Notre travail s'inscrit dans un projet de conception d'un logiciel intuitif de modélisation et d'animation 3D, accessible au grand public. L'objectif d'un tel logiciel est de laisser libre cours à la créativité de ses utilisateurs, de "rendre les outils aussi invisibles aux artistes infographistes que les effets spéciaux ont été rendu invisibles au grand public", Rob Cook 2009 .

L'approche de ce projet est d'utiliser un squelette pour représenter et animer un objet 3D. Dans ce cadre-ci, nous utilisons la surface médiane comme squelette (voir #Ajout de matière et squelettisation). Un squelette étant une structure mince, centrée à l'intérieur d'un objet, décrivant la géométrie et la topologie de cet objet, cela impose des restrictions sur les objets modélisables par le logiciel. Un objet (ou une forme) définit sans ambiguïté un intérieur et un extérieur. La surface de cet objet doit donc être orientée et ne pas avoir d'auto-intersection. Un squelette est un modèle de représentation des formes intuitif [1]. En particulier, la relation entre les modifications d'un squelette et celles de sa forme sont intuitivement comprises. De plus, le squelette est divisé en composantes qui représentent chacune une composante logique de la forme (un bras, un nez, etc.). Le choix d'un tel modèle est donc adapté pour une gestion efficace et intuitive de la forme et de sa topologie.

Plusieurs fonctionnalités peuvent alors être implémentées ; étant donné le temps accordé, nous nous sommes concentrés sur l'ajout de matière et la squelettisation du modèle, ainsi que la réalisation d'une interface répondant aux critères. D'autres fonctionnalités seraient notamment la suppression de matière (outil gomme) et les opérateurs de posture (l'articulation du squelette).

D'autres projets ont suivi une approche similaire, avec d'autres types de squelettes, par exemple avec des squelettes de convolution. Cependant, ce projet est le premier à tenter d'utiliser une surface médiane pour réaliser ces fonctionnalités. Il s'agit donc d'un sujet exploratoire. En cas de succès de l'approche, l'avantage sera la capacité de recalculer un squelette pour mieux capturer la géométrie et la topologie de la forme après des modifications par l'utilisateur.


Ajout de matière et squelettisation

La matière de l'objet est représentée par un squelette, qui est une surface médiane dans notre cas. Un tel squelette est l'ensemble des sphères maximales intérieures à la forme. Pour une utilisation pratique, il s'agit d'un ensemble discret et fini de sphères appelées atomes. Une des premières tâches à réaliser dans notre logiciel est d'ajouter de la matière à notre objet.

À la manière d'un pinceau qui dépose des pigments sur une feuille, l'utilisateur de notre logiciel peut déposer de la matière dans l'espace. Cette matière est représentée par des sphères dont les centres sont tous dans un même plan (voir #Ajout de matière). Ces sphères sont alors combinées au squelette existant avant l'ajout de matière de sorte à construire le squelette de l'ensemble de la matière (celle qui était représentée avant par des atomes ainsi que celle représentée par les nouvelles sphères).

                                 Squelette <--- Squelette (+) Spheres
                (1)    Atomes <--- Spheres

L'ensemble des nouvelles sphères est tout d'abord converti en atomes. Pour cela nous échantillonnons la surface de l'union des sphères. En plus d'une position, un échantillon porte une normale à la surface de l'union des sphères. Grâce à ces échantillons, nous construisons de nouveaux atomes par la méthode Shrinking Ball de Ma et al en 2012 [2]. L'avantage de l'ensemble des atomes sur une union de sphères quelconque est la minimalité : les atomes étant maximaux intérieurs, leur nombre est inférieur au nombre de sphères construites par l'utilisateur. Il est alors plus efficient de traiter les atomes que les sphères non maximales.

                (2)    Squelette' <--- Atomes

Un squelette est composé d'atomes pour capturer la géométrie de la forme. La topologie est, quant à elle, capturée par des liens entre les centres des atomes. Il n'existe pas de consensus sur le calcul des liens en pratique. Nous utilisons ici un algorithme de nos encadrants pour les définir et les calculer. Un lien relie deux centres d'atomes qui s'intersectent, donc suivant un disque, et dont le disque d'intersection n'est pas totalement inclus dans l'union d'atomes. Ainsi, si deux atomes sont reliés, il existe un endroit sur la surface de l'union des sphères où nous pouvons voir les deux atomes côte à côte.

                (3)    Squelette <--- Squelette (+) Squelette'

Nous avons maintenant deux squelettes qu'il nous faut combiner afin d'obtenir un seul squelette, consistant avec sa définition pour l'ensemble de la matière de l'objet. Il faut supprimer les atomes totalement inclus dans l'union des autres sphères maximales, établir des liens entre les atomes des deux squelettes et supprimer des liens entre deux atomes d'un même squelette (lorsque leur disque d'intersection devient complètement inclus dans l'union totale des atomes).

Remarquons qu'un atome totalement inclus dans l'union des autres sphères maximales est un atome sans lien (ou un atome représentant une sphère séparée du reste de l'objet, cas que nous ignorons). Donc cette étape se réalise par un simple filtrage après avoir réalisé les deux autres.

Nous pouvons associer à un lien entre les atomes a1 et a2 d'un squelette S1, les portions du disque (en pratique, le cercle défini par le contour du disque) d'intersection qui sont hors de l'union des atomes. Cherchons les atomes A du squelette S2 qui intersectent a1 et a2. Retirons des portions du disque les parties incluses dans l'union des atomes de A. S'il n'y a plus aucune portion du disque valide, le lien est supprimé. Un atome a dans A est aussi un candidat pour réaliser le lien a1--a et a2--a. Pour savoir si ces liens sont à ajouter, il suffit de récupérer l'ensemble des atomes de S1 et S2 qui intersectent a1 et a, puis a2 et a, puis tester si le disque d'intersection est totalement inclus ou non.

On obtient alors une surface composée des centres et des liens, qui nous sert de base à la construction du squelette. Les centres et rayons des atomes permettent de retracer une forme équivalente à la forme initiale. Après les calculs, les sphères dessinées initialement sont alors remplacées par les atomes médians à l'écran, ce qui ne change pas l'aspect mais autorise l'affichage du squelette, et permet de manipuler une quantité plus faible de données.

Les structures de données

Un exemple d'octree

Afin d'améliorer les performances de nos algorithmes, les sphères dessinées par l'utilisateur sont ajoutées à un octree (ou arbre octal). Un octree est une division hiérarchique de l'espace en octants (qui sont des cubes dans notre cas). Chaque noeud a huit fils, dont les octants partitionnent l'octant du père. Grâce à cette structure d'optimisation, nous pouvons réaliser plus efficacement des requêtes spatiales. Par exemple, pour connaître l'ensemble des atomes intersectant un atome A, nous cherchons l'ensemble des feuilles de l'octree dont les octants intersectent A. Nous parcourons les atomes qui intersectent également ces octants (en pratique, chaque nœud contient une liste des primitives qu'il intersecte) et nous filtrons les atomes qui n'intersectent pas A (ainsi que A).

Dans notre implémentation, une sphère peut se situer dans plusieurs octants à la fois, tant qu'il n'y a pas plus de 32 sphères par octant. Ce choix nous permet alors une plus grande précision lorsque l'on devra échantillonner cette union de sphères. Après échantillonnage puis squelettisation, cet octree est vidé et rempli par les atomes obtenus, qui feront partie de l'union de sphères lors du tracé et de la squelettisation suivantes.

L'échantillonnage

Un exemple explicatif en 2D de l'échantillonnage

Afin d'équilibrer au mieux entre temps d'exécution et performances de l'algorithme de squelettisation, l'échantillonnage de l'union de sphères est une étape clé de nos calculs. L'échantillonnage consiste à déterminer, pour chaque sphère dans chaque octant, les points normés qui représenteront au mieux la surface de l'objet. Les normales des échantillons sont orientés vers l'extérieur de la forme (soit vers le volume non borné définit par une sphère).

L'algorithme de shrinking ball insère un atome par échantillon normé. Un grand nombre d'échantillons conduit donc à un squelette très dense, lourd à manipuler. Au contraire, une faible densité spatiale d'échantillons mène à la disparition des détails de la forme. De plus, le temps de calcul de l'échantillonnage est lié à la densité spatiale d'échantillons que nous cherchons à obtenir. Un juste milieu doit être trouvé pour bien capturer la géométrie de la forme, tout en restant en temps interactif et sans ajouter trop d'atomes pour les traitement futurs.

Plusieurs approches ont été envisagées pour échantillonner nos unions de sphères. La première, l'approche aléatoire, assignait un certain nombre de points à chaque sphère, et ceux-ci étaient placés aléatoirement sur sa surface, en prenant bien garde qu'ils ne soient pas inclus dans l'union de sphères. Cependant, en fonction du rayon des sphères, cette approche sur-échantillonnait certaines sphères par rapport à d'autres.

La deuxième approche, celle que nous avons gardée, consiste à échantillonner non pas la sphère mais les faces d'un octant, et de projeter ces points normés sur les surfaces des sphères contenues dans l'octant. Cette technique donne des résultats satisfaisants, car elle réduit comme voulu le nombre de sphères après squelettisation. En revanche, cette méthode peut avoir l'effet de lisser certains détails, si ceux-ci ne sont pas touchés par les échantillons projetés. Pour gérer ce phénomène, il est possible de contrôler la taille de l'octant ou l'espacement entre les échantillons par face, pour que ces deux valeurs soient inférieures à l'ordre de grandeur des détails que nous souhaitons capturer.


Interface graphique

Une utilisation simple et claire

Les fonctionnalités recherchées s'effectuent via des boutons sur lesquels on peut cliquer à la souris. Des raccourcis clavier existent également pour les utilisateurs plus expérimentés. Chaque fonctionnalité fait l'objet d'une section qui contient des boutons d'affinage de l'action. De plus, une page d'aide est disponible à tout moment.

Gestion de la caméra

Dans cette section, l'utilisateur peut faire tourner l'objet sur lui-même, zoomer et dézommer. Il a également accès aux possibilités de cature d'écran, sauvegarde de son travail et chargement d'un fichier. C'est seulement dans ce mode qu'il est possible d'alterner le type d'affichage (atome - squelette).

Sélection

Ajout de matière

Cette section permet à l'utilisateur de définir le plan de dessin pour l'ajout de matière. Un plan de dessin sera relatif à un atome, sur lequel il sera centré. Un réglage fin est alors possible pour l'orientation par rapport aux axes, si l'utilisateur ne s'est pas mis exactement face au plan dans lequel il veut dessiner. Enfin, la taille du plan est au départ définie par le zoom et la fenêtre de dessin, et fait environ 15 fois le rayon de l'atome sélectionné, mais un autre réglage permet de faire varier cette taille. Après ces modification, la zone d'ajout de matière sera centrée et recadrée par rapport à ce plan pour plus d'intuitivité dans le dessin.

Ajout de matière

Ici, l'utilisateur peut définir le rayon de son tracé. Il peut alors faire autant de tracés qu'il le veut dans son plan, et valider l'image lorsque celle-ci lui convient. C'est alors que le processus de calcul du squelette est lancé et que l'affichage se rafraichit pour laisser apparaitre les atomes. Pour plus de visibilité vis-à-vis de l'épaisseur, un dégradé de couleurs s'applique en fonction du rayon des sphères et atomes.

Suppression de matière

Dans cette fonctionnalité, l'utilisateur peut choisir de creuser en étant face au plan à travailler, ou au contraire gommer selon un plan de coupe. Cette dernière fonctionnalité est visible mais indisponible pour le moment, de même que pour la section déplacement du squelette.

La suppression par creuse fonctionne exactement de la même manière que l'ajout de matière classique. On peut considérer cet outil comme un ajout d' "antisphères". Les sphères qui rencontrent l'antisphère sont supprimées, puis de nouvelles sphères sont calculées pour combler l'espace de l'ancienne sphère non contenu dans l'antisphère.

Déplacement de matière

Cette partie n'a pas été finalisée: un "NOT SUPPORTED YET" s'affiche à l'écran dans ce mode. Cependant l'idée est que l'utilisateur sélectionne un morceau du squelette avec un clic (avec éventuellement un affichage de la hiérarchie squelettique sur le côté) et qu'il le déplace en utilisant la souris.


Outils et méthodes utilisés

Notre application est soumise aux normes du compilateur GCC 4.9 et de C++11, qui peuvent supporter correctement nos autres outils. La visualisation en 3D passe par OpenGL 3.0, et l'application utilise Qt 5.4.2. Enfin, de nombreux outils et bibliothèques (flann, boost, etc.) ont été installés afin d'utiliser au mieux les sources fournies par nos encadrants.

Les sources nous viennent de nos encadrants, membres de l'équipe IMAGINE à l'INRIA. Pour plus d'informations sur les méthodes utilisées dans les sources et dans notre travail, voir aussi la page personnelle de T. Delame.


Validation et bilan

Notre projet étant un sujet exploratoire, nous n'avons pas l'ambition de satisfaire les utilisateurs pour le moment. Les infographistes rompus aux logiciels professionnels s'attendraient à plus de contrôle sur la forme et le squelette. Nous avons cependant pu montrer que la matière peut à tout moment être squelettisée, sans perte majeure de détails et avec un temps de calcul relativement court. Nous l'avons prouvé dans le cas de l'ajout de matière, et nous avons donné des pistes de recherche dans la suppression de matière également.

De plus, notre application reste plus intuitive que beaucoup de méthodes utilisées à ce jour. Ici, pas besoin de créer le squelette courbe à la main afin d'obtenir une forme, et nul besoin d'une panoplie d'outils divers et variés. Tout est fait par une métaphore de peinture avec des algorithmes qui calculent automatiquement un squelette. La prise en main est donc très rapide pour le grand public.

Ainsi, nous avons atteint notre objectif, à savoir de démontrer la faisabilité du projet. Par un raffinement des calculs théoriques utilisés, et la création d'une interface intuitive, nous avons donc un prototype qui répond aux besoins de la recherche actuelle, en explorant les limitations et les forces des algorithmes.


Documentation annexe


Références

[1] Harry Blum. A transformation for extracting new descriptors of shape. In W. Wahen-Dunn editors, Models for the perception of speech and visual form, MIT Press 1967. Pages 362-380. 1967.

[2] Adrien Bernhardt, Adeline Pihuit, Marie-Paule Cani and Loïc Barthe. Matisse: Painting 2D regions for Modeling Free-Form Shapes. In Alvarado C. et Cani M.-P. editors, EUROGRAPHICS Workshop on Sketch-Based Interfaces and Modeling, SBIM 2008. Annecy, France, juin 2008. Pages 57–64. 2008.