Majeure "Algèbre, Informatique et Applications"
Enseignement d'Approfondissement "Géométrie et Synthèse d'Images"

Moteur de rendu de terrain


Projet Réalisé par Pierre-Yves Soeiro de Brito (promo 2000)

Description du projet

Ce projet consiste à simplifier un terrain en temps réel pour pouvoir s'y déplacer de façon fluide, tout en ayant un niveau de détail satisfaisant. J'ai cherché à innover par rapport aux méthodes habituelles. En effet, pour stocker les points de la carte, la plupart des méthodes utilisées mettent en oeuvre une structure de données arborescente où chaque noeud donne naissance à quatre fils : un quad-tree. On descend récursivement dans l'arbre jusqu'à un détail satisfaisant, et on affiche les huit triangles s'appuyant sur les neuf points contenus dans le niveau du quad-tree auquel on est arrivé.

L'algorithme utilisé ici s'appuie sur la triangulation de Delaunay pour trianguler les points jugés nécessaires : à chaque frame, on supprime de la triangulation les points devenus inutiles, et on ajoute les points utiles. Cela permet une plus grande liberté dans le choix des sommets que l'on affiche. Ainsi, avec moins de triangles à afficher, on a un meilleur rendu, vu que les sommets choisis sont les plus pertinents.
Bien sûr, cette méthode implique un traitement plus important. L'intérêt du projet est donc d'évaluer l'efficacité de cet algorithme par rapport à la méthode traditionnelle.

Algorithmes utilisés

Les algorithmes utilisés sont :
-la localisation par marche d'un sommet dans une triangulation
-l'insertion d'un sommet dans une triangulation existante
-la suppression d'un sommet de la triangulation, qui nécessite l'emploi d'un algorithme de triangulation d'un polygone quelconque.

les critères de notation des sommets sont essentiels. On peut utiliser plusieurs méthodes, avec des résultats différents :
-notation par évaluation de la courbure locale
-notation par comparaison de la moyenne des altitudes des 8 voisins d'un sommet avec l’altitude du sommet lui-même

Résultats obtenus

Voici deux captures d'écran montrant la simplification effectuée. La carte est générée par une fonction analytique à base de fonctions sinusoïdales. On peut bien sûr se promener librement dans ce paysage virtuel à l'aide de la souris et du clavier. Le programme propose plusieurs modes d'affichage. On peut voir ici le mode lissé, avec en superposition, à droite, le maillage. On peut remarquer que le lissage effectué empèche de voir les frontières entre les triangles.
On peut remarquer la régularité de la triangulation de la plage : j'ai appliqué un traitement particulier pour que la mer ne remonte pas sur les terres, ce qu'elle fait spontanément si l'on colore simplement les sommets au niveau de la mer en bleu...
Je n'ai pas eu le temps de mesurer la performance de l'algorithme pour le comparer à la méthode du quad-tree. Cependant, j'ai pu constater que le traitement de la triangulation n'alourdit pas sauvagement le temps de calcul.

Problèmes rencontrés et solutions apportées

Le choix du critère de notation des sommets est absolument primordial, et que ce soit l'un ou l'autre des critères de notation cités plus haut, cela n'est pas satisfaisant. En effet, dans un cas comme dans l'autre, l'algorithme triangule totalement certaines zones, jusqu'à une frontière nette, puis ne triangule plus rien du tout. La solution que j'ai trouvée consiste à multiplier la note trouvée par un terme aléatoire. Cela permet de trianguler progressivement les différentes zones de la carte, et d'éviter les fronts de triangulation.

Améliorations possibles

Il me semble utile de poursuivre la recherche d'un meilleur critère de notation. Peut-être un critère unifié entre les deux méthodes proposées serait-il judicieux.
D'autre part, il me semble intéressant d'introduire une structure de données particulière (peut-être un quad-tree) pour pouvoir accélérer le traitement des zones éloignées du point de vue (en appliquant l'algorithme moins souvent pour les sommets éloignés).
Pour ce qui est du rendu, il faut bien sûr appliquer à terme une texture.

Retour à la liste des projets réalisés