Frustum & octree indisociable?

**wystan** · 05/12/2008, 18h05

Bonjour,

Voila mon soucis, j'affiche un objet comme un petit immeuble ou encore une maison, je voudrais faire un frustum culling pour eviter biensur d'afficher tout les polygones de ma scene, mon probleme est de savoir si je suis obligé de faire un octree pr utiliser le frustum ou encore une autre structure de partionnement.

Merci

**LeGreg** · 05/12/2008, 22h21

Ce n'est pas indissociable.

Octree est une structure d'accélération. C'est à dire que si il n'y a pas d'octree ou de structure similaire (hachage, grille régulière, kd tree, etc) il est plus difficile de trouver rapidement les objets qui pourraient être dans ton frustum.
Le but c'est de réduire le temps passé à tracer.

La plupart des jeux modernes affichent tellement d'objet qu'il est difficile d'obtenir une vitesse d'affichage interactive (>10 fps voire 30 fps) sans une certaine forme de structure d'accélération.

Comme je l'ai dit plus haut il y a d'autres formes. Quake 3 par exemple utilisait des PVS (potential visibility set, ensemble des objets visibles depuis une certaine position précalculée), axis aligned bounding box (boite englobante alignée sur les axes ce qui permettait de faire du pruning/élagage rapide) et bsp (arbre avec plans de subdivisions arbitraires ce qui permettait de retrouver rapidement la position courante dans la liste des noeuds). Et ils pouvaient se permettre de précalculer le tout parce que la géométrie du jeu était statique.

Mais en gros, il y a des tonnes et des tonnes de techniques qui tournent plus ou moins selon les mêmes principes ("moins de calcul c'est mieux"), quelle stratégie appliquer dépendra beaucoup du type de contenu (statique, dynamique, ouvert, fermé, types d'occluders) et des contraintes de la plateforme (calcul rapide, calcul lent, mémoire constrainte, mémoire illimitée, accès mémoire rapide, accès mémoire lent). Etc.

LeGreg

**wystan** · 05/12/2008, 23h58

Merci pour ta réponse!
En gros voici un schéma de la maison que j'affiche le carré rouge, c'est juste des escaliers, les trous représente des portes.

Pensez vous que le frustum est essentiel? et si oui, je ne vois pas comment implémenter l'octree etant donné que cette structure est proportionnelle au niveau du découpage et donc la piece du milieu sera coupé en 2 et ne pourra etre affiché qu'a moitié.

Merci de m'eclaircir un peu sur le sujet!

**shenron666** · 07/12/2008, 01h31

pour les intérieurs, les PVS ou un système de portal sont bien plus simple à gérer et bien plus efficace qu'un octree

**wystan** · 07/12/2008, 21h50

Merci a toi, j'ai regardé le principe sur wikipedia et d'autres sites sans trouver de code sur les PVS donc si tu en as un, ca m'interesserait fortement!

Si j'ai bien compris le principe, on fait une sorte d'AABB par salle avec la liste des objets contenus dans la salle, à afficher, et apres on fait un test de collision avec le frustum view pour savoir quelle(s) salle(s) affichée(s)?

**bafman** · 08/12/2008, 16h03

si tes salles sont toujours de type rectangulaire, ne te prend pas la tête, fait un système de portal, ce sera super simple à faire et très efficace

**wystan** · 08/12/2008, 19h14

merci a toi, j'ai cherché systeme portal (et meme portal system) en anglais mais je n'ai rien trouvé sur le sujet. As-tu des sites qui expliquerai ca?
Pour les collisions avec un mur( pour ne pas passer a travers), a-t-on un autre choix que de faire des tests d'un vecteur entrant en collision avec un triangle? (on considere que le mur pour avoir des 'trous' comme une entrée)