Scène de test (60000 polygones, 4000m2)

Comment afficher rapidement un univers immense ?

Univers immense ?

• Exemples : un bâtiment, un circuit, une ville, une région...

• Un tel univers peut contenir des millions de polygones : on ne va pas tous les afficher !

• Rapidement = 60 images/s au moins !• Pour aller vite : ne dessiner que ceux qui

sont visibles (dans le champ de vision de la caméra).

Le champ de vision s’appelle le frustum

En 3D, c’est l’espace compris entre les 6 plans.

Calculer la partie visible = frustum culling

Exemple d’algorithme naïf

• Tester tous les polygones ? Beaucoup trop long.

• Si l’univers est plat et statique, plaquer une grille avec des cases de taille égales.

• Pré-calcul : on associe une case à chaque polygone.

• On ne dessine que les polygones dont les cases sont dans le champ de vision.

Illustration de l’algorithme précédent

• vue de dessus : les cases visibles sont grisées

Champs de

vision

Mais ce n’est pas aussi simple !

• Une simple grille ne suffit pas ! Ce n’est pas efficace et on a aussi envie aussi de :– Calculer des collisions,– Avoir des algos pour tous les types

d’environnement– Ne pas afficher ce qui se trouve « derrière un

mur »… etc…• Les quatre algorithmes que nous avons étudiés

répondent à certaines de ces conditions.

Algorithme à base de quadtrees

Principe

• Comme une grille, sauf que les cases ne font pas toutes la même taille.

• On associe à chaque case les polygones qu’elle contient

• Construction– On part d’une case qui fait toute la surface de l’univers– On découpe récursivement l’univers en cases de plus en

plus petites.

• Au final, on a un « arbre de cases », chaque case étant découpée en 4 cases

Exemple de quadtree

Comparaison grille/quadtree

• Intérêt : on teste d’abord si les grands carrés sont visibles. Si ils ne le sont pas, on les élimine. Sinon, on considère des carrés plus petits.

• Beaucoup moins de tests avec le quadtree !

Exemple avec notre scène de test

Conclusion sur les quadtrees

• Surtout adapté à des scènes plates (les polygones sont posés sur un plan).

• Peu adaptés pour des bâtiments à étages : on va par exemple afficher des polygones sous le sol.

• Les prochains algorithmes répondent à ces limitations…