RENDU DE TERRAIN Problématique : Rendre une très large zone de terrains en la simplifiant au maximum pour réduire le nombre de polygones à afficher. A.Bailly

RENDU DE TERRAINRENDU DE TERRAIN

• Problématique : Rendre une très large zone de terrains en la simplifiant au maximum pour réduire le nombre de polygones à afficher.

A.Bailly & L.Zaslavsky 1

Représentation du terrainReprésentation du terrain

• Le terrain est représenté par une grille d’élévation :

1 10 20 17

15 12 16 21

32 16 8 14

X

YA.Bailly & L.Zaslavsky 2

Techniques de rendu de Techniques de rendu de terrain en temps réelterrain en temps réel

• Continuous LOD rendering of heigh fields (1996)• ROAM : Real-time Optimally Adapting Meshes (1997)• Comparaison des 2 méthodes


Real-Time, Continuous Level of Detail Real-Time, Continuous Level of Detail Rendering of Height FieldsRendering of Height Fields


Représentation du terrain

La surface

• La surface correspondante est composée d’un ensemble de blocs de triangles de taille 3x3 points :


Représentation du terrain

Les blocs

• Chaque bloc peut être décomposé en une grille de sous-blocs de même dimension :


Algorithme

Étapes

Cet algorithme se décompose en deux étapes :

Simplification d’un bloc point par point.

Simplification de la surface par bloc.


Algorithme

Simplification par point

• Les deux triangles droit et gauche d’un quadrant peuvent être fusionnés selon qu’une certaine condition soit vérifiée :



Condition de simplification

• Soit la distance verticale maximale entre les deux triangles obtenus après simplification :



Condition de simplification

projeté sur le plan de projection indique l’erreur maximum perceptible entre les deux triangles fusionnés et le triangle résultat de la fusion.

• Si est inférieur à un certain seuil alors les triangles peuvent être fusionnés.

• L’opération est répétée récursivement avec le triangle obtenu et un triangle adjacent.


Algorithme

Simplification par bloc

• Pour ne pas avoir à considérer tous les points de la surface pour la simplification, l’algorithme procède par bloc.


Simplification par bloc

Principe général

• Si toutes les valeurs des points d’un bloc sont inférieures à alors le bloc peut être directement remplacé par un bloc de moindre résolution.

• De plus, de larges zones de terrain peuvent être éliminées par test avec la pyramide de vue.


Résultats


ROAMing TerrainROAMing Terrain - - introductionintroduction

• Algorithme populaire de LOD

• Utilisé dans simulateurs de vol, jeux, réalité virtuelle…

• Principe de découpage et fusion de facettes ingénieux


Structure de données – arbre Structure de données – arbre binairebinaire

Va

Vo V1

(Vo,V1)

Vc1(Vc1,Va,Vo)

(Vc1,V1,Va)

Level 1


Calculé dans pré-processeur

Structure de données – arbre Structure de données – arbre binairebinaire

Va

Vo V1

(Vo,V1)

(Vc1,Va,Vo)

(Vc1,V1,Va)

Vc1

Vc2 Vc3

(Vo,Vc1,Vc2)

(Vc2,Vc1,Va)

(Va,Vc1,Vc3)

(Vc3,Vc1,V1)

Level 2


On rajoute des feuilles TQ LOD non atteint

Accès aux structures de Accès aux structures de données :données : Split / merge opérationsSplit / merge opérations

3 cas :• La face fait partie d’un

diamant - Split la face et « Base Neighbor ».

• La face est à coté du maillage - Trivial, split la face.

• La face n’appartient pas à un diamant – Forcer le découpage du « Base Neighbor ».

découpage

fusion


Forcer le découpage d’une Forcer le découpage d’une faceface

Current triangle Base neighbor

• « Current triangle » n’appartient pas à un diamant

• récursivement, forcer le découpage jusqu’à trouver un diamant !

• le triangle original peut maintenant être découpé.


Optimisation par files de Optimisation par files de prioritéspriorités

• Priorités sur chaque facette.• Si point de vue change : modification des

priorités selon les frames précédentes.• Split file : contient les triangles à raffiner.• Merge file : contient les triangles à

fusionner.

Cohérence frame-to-frame (+ pour les grands terrains !)

Maillage optimal : 1ère frame coûteuse, le reste peu coûteux grâce aux files.


Étude de performancesÉtude de performances

• Performance proportionnelle au nb de changements de triangles de la frame précédente ! et non la taille de la carte !

• Tests sur Indigo2 Silicon Graphics• View frustum culling : ok - flags pour

chq triangle de l’arbre binaire.• T-Stripping : bien, dû à la structure du

terrain


Évolutions…Évolutions…

Diamond Terrain algo (2001) : H.Hakl• Basé sur ROAM, avec une structure de

triangle quadtrees.• 4 files LIFO (à la place des files de priorités)• Meilleur pr triangle stripping

Moins d’opérations split/mergeex : 5 Splits pr Diamond pr réduire une face en 16 sous-facettes. ROAM fait 15 splits !


Quelques graphiques…Quelques graphiques…


Comparaison des méthodesComparaison des méthodes

ROAM LOD Height Field+ Calcul conservé d’une frame sur l’autre.

+ Simplification par bloc.

- Calcul refait à chaque frame.

+ La structure de données employée pour représenter la surface :

+ Pas de problème de disjonction de face. + Accélération par Triangle Stripping.


Documents

RENDU DE TERRAIN Problématique : Rendre une très large zone de terrains en la simplifiant au maximum pour réduire le nombre de polygones à afficher. A.Bailly