 |
 |
Gontran Magnat
Samir-Anatole Asghar
Le but de ce projet est d’effectuer un rendu de la silhouette d’un objet 3D. En effet, notre travail consiste à calculer et afficher en temps réel la silhouette d’un objet 3D donné au format X3D. Ainsi, on obtient un objet toujours en 3D mais avec un rendu non photo réaliste : comme si on l’avait dessiné à la main.
De fait, le calcul réside dans une détection des contours et des crêtes de l’objet 3D. Le calcul se fait en temps réel car, bien évidemment, tout dépend de l’angle de la caméra qui observe l’objet et qui restitue la scène.
Pour effectuer ce travail, nous avons réparti le travail en plusieurs étapes :
L’algorithme de détection des contours est aussi assez simple à la base. En effet, un contour pour un objet 3D est :
Pour déterminer les contours d’un objet, on parcourt donc ses edge, et :
- soient n1 et n2 les normales de F1 et F2 .
- soit v un vecteur formé par la position de la caméra et un point de l’edge courant.
si (n1 ∙ v) ∙ (n2 ∙ v) ≤ 0, cela veut dire que n1 et n2 sont de direction opposée sur l’axe de la camera, donc que F1 et F2 sont orientées l’une de face, l’autre de dos par rapport à la camera, donc que l’edge courant est un contour.
Le problème qui se pose est ensuite de savoir quels contours sont visibles et quels sont ceux qui ne le sont pas. Les techniques là-dessus ne sont hélas pas nombreuses, et peu sont faciles à mettre en œuvre. Nous avons retenu celle qui à priori parait la plus simple : dessiner d’abord une fois les faces (avec culling des faces arrières pour aller plus vite), puis appliquer la méthode glClear(GL_COLOR_BUFFER_BIT) qui réinitialise le buffer de couleurs sans toucher au z-buffer. Ainsi, quand ensuite nous dessinons les contours, ceux derrière la figure seront automatiquement cachés grâce au z-buffer.
Exemples de contours:
|
|
L’étape suivante consiste à interpoler les contours pour les lisser et éviter les effets de polygonisation des courbes (une courbe en 3D est un polygone au maillage plus ou moins fin, ce qui se voit si l’on zoome dessus).
Si en 2D cela peut paraître facile, avec de nombreuses méthodes (Béziers notamment), en 3D l’affaire est plus compliquée. Plusieurs solutions s’offrent à nous :
Nous avons essayé de mettre en place les 2e et 3e solutions, avec plus ou moins de succès. Les algorithmes sont décris ci-dessous :
Nous interpolons les contours en utilisant la méthode de Hertzmann décrite dans "Introduction to 3D Non-Photorealistic Rendering: Silhouettes and Outlines" : à chaque vertex on associe une valeur correspondant aux orientations des faces qui l'entourent. Après avoir tenté d'associer la somme des normales des faces adjacentes à un vertex, nous avons préféré une méthode plus radicale: on associe au vertex la valeur -1 s'il est adjacent à au moins une face tournant le dos (façon de parler) à la caméra, 1 sinon.
Le défaut de cette méthode est que pour les objets peu triangulés, les contours sont trouvés de manière assez fantaisiste, voire sont ignorés. Tout comme Hertzmann, nous ne pouvons que conseiller une triangulation plus grande des Mesh, au détriment toutefois de la rapidité.
Pour créer des vertex grâce à cette méthode, nous parcourons les edge du Mesh. Pour chaque edge, on regarde si les vertex ont des valeurs différentes. Dans ce cas, un contour passe sur l'edge courante, et nous calculons alors le point interpolant le contour. Le calcul est défini en détail dans le document de Hertzmann, nous ne le répéterons donc pas.
exemple d'interpolation par vertex
Résultats obtenus :Voici un exemple de ce que nous avons obtenu grace a cette interpolation par vertex. Nous voyons qu'il y a certains problèmes notamment au niveau des ailes qui montrent que notre algo dépend de la triangulation du modèle. Ainsi, les ailes du jet ne sont pas assez triangulées alors que la porshe est un bien meilleur modèle.
 |
 |
 |
 |
L'interpolation par segments est elle nouvelle. Pour la mettre en oeuvre, on parcours encore une fois les edge, mais cette fois-ci uniquement en nous intéressant aux contours. Si un edge est un contour, alors on trace le segment [1/3; 2/3] de cet edge, puis on relie les deux extrémités du segment nouvellement créé à celles des segments des contours adjacents. Cela impose bien sûr de chaîner les contours, sans quoi il est assez difficile de s'en sortir.
Cette méthode a comme avantage que, appliquée par récurrence, on finirait par avoir une interpolation courbe parfaite de l'image. Par contre, le problème qui se pose ici est un problème désormais classique de visibilité, car les segments tracés sont souvent recouverts par les faces en raison du choix de notre méthode pour n'afficher que les contours visibles. Il est toutefois évident que, une fois le problème de visibilité réglé, cette méthode fait des merveilles.
Exemple d'interpolation par segments.
Le trait rouge indique la première étape.
Le trait vert indique l'étape à la fin de la
récurence
Voici un exemple de ce que nous avons obtenu grace a cette interpolation. Nous voyons que, ici encore, le probleme de visibilité cache bon nombre d'aretes:
 |
 |
L’algorithme de détection de crêtes et de creux est le suivant : si deux faces adjacentes (c'est-à-dire ayant une arête commune) forment un angle de moins de q (respectivement de plus de q + p), q donné, alors on a une crête (respectivement un creux) au niveau de l’arête commune aux deux faces.
Pour déterminer les crêtes et les creux, on parcours donc les edges de l’objet qui sont en fait toutes ses arêtes, et, considérant que la figure est bien faite (chaque edge est associé à au plus deux faces), on fait le produit scalaire des normales associées aux deux faces de l’edge (s’il en a deux) avec le vecteur de point de vue (normalisé). On obtient alors cos(q) et on en déduit donc q. Un test sur cet angle ensuite nous permet de déterminer si l’on doit afficher l’edge commun aux deux faces ou pas.
Dans notre programme, la fonction qui réalise cette détection est la fonction drawCrete(). Elle utilise la procédure d’affichage AffichageQuadriCrete.
Voici un exemple de ce que nous avons obtenu grace a cet algorithme de détection des crêtes. Dans cet exemple, nous affichons des polygones (quadrilatères) pour chaque edge détecté comme étant une crêtes. Dans cet exemple, l'angle q de détection des crêtes est de Pi/3.
 |
 |
Une fois les contours interpolés, la phase suivante consiste à appliquer une texture de trait pour donner un aspect "crayonné" ou "peint" aux contours. Avant de passer à l’étape de pose des textures proprement dite, il faut d’abord définir les polygones sur lesquels on appliquera les textures. C’est là que ça se complique, car il faut des polygones de taille non négligeable (pour voir la texture), et qui ne soient pas recouverts par la figure précédemment tracée. De plus, il faut que les polygones adjacents soient "bien" adjacents, c'est-à-dire que le polygone suivant soit tracé dans la continuité du précédent (figure 3). Ceci impose de chaîner les arêtes de contour, donc d’étendre la structure de donnée de X3D.
Pour ce faire, nous avons introduit une notion d’edge voisin dans la structure de donnée même des edges (voir fichier MyMeshData.h). En effet, on peut attribuer à un edge deux voisins maximum. Un voisin "from" et un voisin "to" : cette dénomination vient du fait que les voisins sont associés au point (ou vertex) "from" ou "to" de l’edge. Ainsi, on peut les récupérer par la suite et ainsi dessiner des polygones qui s’alignent correctement et de la façon la plus continue possible.
Une fois le chaînage des contours mis en place, il ne reste plus qu’à créer les polygones comme une bande autour des arêtes de contours, comme décrit dans le document de Markosian et Northrup, "Artistic Silhouettes: A Hybrid Approach".
Résultats obtenus :
Voici ce que nous obtenons finalement après application d'une texture simple sur les polygones. Nous montrons ici plusieurs exemple dont certains avec des contours aux angles marqués et d'autres avec des contours arrondis.
 |
 |
 |
 |
 |
 |
Le programme exécutable que nous avons implementé reprend toutes les méthodes que nous avons vues jusqu'ici. Aprés compilation (avec les commandes qmake et make), on a un exécutable que l'on peut lancer en tapant la commande mysimplifiedmeshviewer. On peut faire évoluer la camera autour de l'objet avec la souris et on peut modifier l'affichage avec des commandes au clavier. Toutes ces commandes sont résumées dans le fichier d'aide accessible en tapant la commande H au clavier.
Nous n'avons malheureusement pas pu implémenter les fonctionnalités dans leur intégralité comme nous l'aurions souhaité. Ainsi, nous avons délaissé l'interpolation par vertex au profit de celle par segments. De même, nous avons eu beaucoup de mal à créer des surfaces correctes pour poser des textures de traits pour les silhouettes, et à cet instant encore, nous sommes hélas insatisfaits du résultat. En effet, la lourde structure de X3DToolKit et le fait que nous sommes encore à nos premiers pas en OpenGL ont fait que nous avons fait beaucoup d'erreurs de codage, qui ont énormément ralenti notre progression et qui nous empêchent d'avoir les résultats que nous souhaiterions au moment où nous remettons ce rapport.
De nombreuses améliorations restent ainsi à faire. La plus importante, car nous n'avons pas trouvé de réel moyen d'en venir à bout, reste l'amélioration qui résoudrait définitivement le probleme de visibilité. Ensuite, on peut améliorer le posage des textures. En effet, on pourrat disposer pour une même texture de deux types de traits: une texture de trait droit et une de trait courbe. Dans l'algorithme, on peut calculer l'angle entre deux arêtes et si cet angle est trop important, on applique la texture de trait courbe.
Sources du Programme: ici
Page du projet: Projets image, ENSIMAG 2e année
Site contenant un grand nombre de documents relatifs au rendu non photorealiste (université de Calgary): Bibliography in Non-Photorealistic Rendering
Autre bon site sur le rendu non-photoréaliste "artistique": Open NPAR