Maillage
La modélisation du terrain est une partie importante de Septant. Cette modélisation est faite de façon à gérer différents niveaux de détails, mais utilise également du géomorphing pour éviter les sauts entre les différents niveaux de détails.
Utilisation de cartes d'élévation ou Heightmaps
Comme nous l'avons déjà vu précédemment la modélisation du terrain se fait à partir d'une ou plusieurs cartes d'élévation. Une carte d'élévation étant une carte en niveaux de gris du terrain, où l'intensité d'un pixel donné représente la hauteur du point correspondant à ce pixel.
Chaque pixel d'une carte correspond à un vertex du terrain. Lors de l'utilisation de plusieurs Heigtmaps les Heightmaps sont simplement disposées côte-à-côte.
Structure en patchs
Les terrains que nous gérons pouvant dépasser le million de polygônes, il devient nécessaire de gérer différents niveaux de détails lors de la modélisation du terrain. Ainsi une zone du terrain plus proche de l'observateur sera modélisée de façon plus complexe qu'une partie plus éloignée de l'observateur. Pour obtenir un résultat crédible il est de plus nécessaire d'avoir une cohérence entre les différents patchs.
Pour gérer l'ensemble de ces problèmes, nous avons choisi de nous baser sur la méthode de Greg Snook (voir bibliographie). Cette méthode propose de gérer la continuité entre les différents patchs grâce à des motifs de patchs précalculés, ce qui en fait une méthode relativement rapide lors de l'exécution. Nous considérerons que chaque patch possède (2n+1)*(2n+1) vertices. Le terrain sera réduit en conséquence pour tenir compte de cette contrainte.
Les différents motifs d'un patch
Un patch est modelisé à partir d'un motif. Un motif est une suite d'indices qui indique quels vertices du patch il faut dessiner. À un niveau de détail correspond un motif.
Chaque motif est consitué de 9 élements :
- un corps
- quatre bords normaux
- quatre bords dits adaptatifs
Il est à remarquer qu'un motif étant seulement un tableau d'index, valable pour tous les patchs, la taille mémoire d'un motif est relativement faible.
Adaptation entre les différents patchs
La continuité entre les différents patchs est possible grâce à la présence des bords adaptatifs. Lorsque qu'un patch de niveau n est à côté d'un patch de niveau n+1 alors le patch de niveau inférieur s'adapte au patch de niveau supérieur en utilisant un bord adaptatif sur le côté contigu au patch de niveau n+1.
C'est en cela que notre algorithme diffère légèrement de l'algorithme de Greg Snook, où c'est le patch supérieur qui s'adapte au patch inférieur. Notre modélisation est donc plus précise pour un temps de rendu légèrement supérieur.
Signalons également que ce système impose deux contraintes :
- il ne doit y avoir au plus qu'un niveau de détail entre deux patchs consécutifs ;
- le premier niveau de détail est le niveau 1, avec seulement un corps et pas de bords.
Géomorphing
Problème et Principe
Le géomorphing répond au problème introduit par l'affichage avec niveaux de détail présenté précédemment, à savoir que le terrain se déplace brutalement au changement de niveau de détail. Il est donc nécessaire d'affiner cette transition pour la rendre moins visible à l'œil. Le gémorphing consiste donc à déplacer les vertices du terrain pour passer progressivement d'un niveau de détail à l'autre. En particulier, lors du passage d'un niveau de détail à un niveau de détail supérieur, les points impairs
doivent être déplacés vers l'élévation où ils devront se trouver au changement de niveau de détail.
Implémentation
L'implémentation est séparée en plusieurs parties. Tout d'abord, un précalcul est effectué sur le maillage pour obtenir les données nécessaires au déplacement des vertices. Ensuite, une première implémentation simple a été effectuée avec un géomorphing trivial
. Cette implémentation faisant réapparaître les problèmes de gaps décrits précédement, une implémentation plus poussée a donc été réalisée.
Pré-calcul des données
Pour effectuer les transformations de vertices en temps réel, il est nécessaire de connaître pour chaque niveau de détail ayant un niveau de détail inférieur à quelle élévation se trouve le centre de chaque côté de chaque triangle du maillage. Ces points sont indiqués en rouge ci-dessus. Pour chacun de ces points, nous calculons l'élévation par moyenne entre les deux sommets de chaque côté, et conservons avec le niveau de détail auquel nous effectuons le calcul.
Ces données sont codées dans un tableau de normales. Nous y utilisons une coordonnée pour les élévations, une autre pour le niveau de détail de l'élévation, et une troisième pour la hauteur réelle du point au niveau de détail le plus fin, ce qui permet de ne pas faire varier les textures sur des texturages dépendants de la hauteur du terrain.
Implémentation de base
Précédement, nous calculions le niveau de détail en valeur entière pour savoir quel niveau afficher. Pour l'implémentation du géomorphing, il est nécessaire de ne pas arrondir cette valeur. Nous obtenons ainsi une partie entière indiquant le niveau de détail à afficher, une valeur décimale comprise entre 0 et 1, et indiquant de combien nous devons déplacer le vertex vers sa position d'arrivée.
Ici, le taux d'ajustement est a. Chaque vertex impair
est ajusté à partir de sa position dans le niveau de détail affiché. On y ajoute ensuite la différence entre la position de départ et la position cible au niveau de détail supérieur (la moyenne pré-calculée) multipliée par le coefficient a. De plus, il est nécessaire de passer pour chaque patch son niveau de détail en flottant pour déterminer quels points doivent être ajustés.
L'ajustement se fait en particulier lorsque le niveau de détail du patch traité est supérieur de 1 au niveau de détail pré-calculé du point courant, donc que le point courant est un point impair
.
Toutefois, cette implémentation simple introduit des problèmes de gaps entre les patches. Ceci est dû au fait que deux patches adjacents n'auront jamais le même niveau de détail et le même taux d'ajustement. Les vertex ajustés au bord des patches sont donc ajustés différement, ce qui fait réapparaître le problème de gaps vu aux jointures des patches dans les premières implémentations du terrain.
Implémentation complète
À cause du problème que nous venons de voir, il est nécessaire de compléxifier l'implémentation pour traiter identiquement les vertices sur les côtés des patches. Pour cela, nous prenons comme convention que l'ajustement des côtés droit et bas du patch se fait par rapport au taux d'ajustement de ce même patch, tandis que les deux autres côtés utilisent le taux d'ajustement des patches voisins gauche et supérieur. Cela garantit bien que tous les vertices seront ajustés identiquement. Ces différents cas peuvent n'être traités que sur les 4 bords des patches, et non sur les corps.
Le schéma montre les vertices concernés par ces cas dans le cas des jointures :
Le shader de vertex est donc modifié pour que les vertices soient ajustés lorsque le voisin gauche ou haut est ajustable, qu'il a le même niveau de détail que le patch courant, que le vertex traité est sur un bord commun avec le patch voisin, et que le vertex est ajustable. La condition d'ajustabilité d'un patch est d'avoir un niveau de détail au moins supérieur à 2. La condition d'ajustabilité d'un vertex est d'être un point impair
.
Nous pouvons malgré tout remarquer que cette version ne gère que les jointures non ajustées, car le calcul est différent pour les jointures ajustées (pour lesquelles le voisin a un niveau de détail immédiatement supérieur). Il devient donc nécessaire de traiter les vertices lorsque le patch voisin a un niveau de détail supérieur de 1 au patch courant, en plus des conditions vues dans le cas précédent.
Avec ces 5 conditions combinées, il est alors possible de gérer tous les cas sans avoir deux taux d'ajustement différents pour le même vertex. Il subsiste tout de même certaines erreurs d'arrondi qui font apparaître des gaps de la taille d'un pixel par endroits, mais cela pose beaucoup moins de problèmes que les gaps de l'implémentation de base, et n'est presque pas visible grâce à l'environnement.
Dans les versions futures, il nous semble intéressant d'étudier la possibilité de transformer les tests de conditions pour le géomorphing en une méthode calculatoire, où le niveau de détail serait calculé non plus par patch, mais par vertex.