Les applications 3D, et notamment les jeux, sont toujours plus détaillées et réalistes. Cela représente des millions, voire des milliards de polygones à afficher en temps réel, et bien que le hardware soit lui aussi en constante évolution, de telles grandeurs sont bien souvent impossibles à traiter. Ainsi on utilise ce que l'on appelle un partitionnement de l'espace.

Le principe est simple : on va trier nos polygones/objets/pièces, et les ranger dans une structure qui sera bien plus rapide à utiliser. Ainsi selon l'endroit où l'on va se trouver et ce que l'on va faire, on va pouvoir limiter les calculs à une portion beaucoup plus réduite de la scène, ce qui économisera des millions de calculs inutiles et sera donc bien entendu beaucoup plus rapide.

Il existe bon nombre de structures de partitionnement de l'espace, toutes différentes et utilisables dans des situations bien identifiées. Parmi les plus courantes, on retrouve les arbres BSP, les quadtrees/octrees, ou encore les portails. Voir https://jeux.developpez.com/faq/3d/?page=partitionnement#PARTITIONNEMENT_choix.

On peut utiliser un partitionnement de l'espace dans plusieurs buts, principalement pour le frustum culling (voir https://jeux.developpez.com/faq/3d/?page=culling#TECHNIQUES_CULLING_frustum) et la détection de collisions.

Vous l'aurez compris, avoir un partitionnement efficace de l'espace est quasiment obligatoire dans une application qui se veut performante. Cependant il faut choisir avec soin la structure utilisée, voire en combiner plusieurs selon le type de scène que vous devrez gérer.

Il existe de nombreuses méthodes/structures de partitionnement de l'espace, chacune ayant ses avantages, ses inconvénients et surtout son domaine d'application.

Les arbres BSP (BSP-trees)
Le principe de cette structure est de couper le monde en deux récursivement, et ainsi d'organiser l'espace de la scène en un arbre binaire. Les « plans de coupe » étant les polygones de la scène, cette technique peut potentiellement finir avec un nombre de polygones très supérieur au nombre original. Cette contrainte en fait également un très mauvais candidat pour les scènes dont les polygones ont plus ou moins la même orientation (par exemple un terrain). Étant une structure difficile à mettre à jour, l'arbre BSP est également un piètre candidat pour tout ce qui peut être dynamique dans une scène.
Ainsi, les domaines d'applications typiques des arbres BSP sont les décors, de préférence les intérieurs. C'est une technique très utilisée pour tous les jeux de shoot (Doom, Quake).
Avantage non négligeable des arbres BSP : une fois construits, ils permettent d'afficher à très peu de frais les polygones en front-to-back (du plus proche au plus lointain), permettant ainsi d'économiser le Z-Buffer.

Liens

• BSP trees FAQ
• BSP trees : theory and implementation
• Généralités sur les arbres BSP
• Application des BSP à l'élimination de facettes

Les portails (portals)
L'idée qui se cache derrière les portails est très simple. Regardez par la porte de votre bureau : vous voyez d'autres pièces. Maintenant tournez-vous : vous ne voyez plus rien. Le principe des portails est le même : si votre caméra ne peut voir ce qui se trouve derrière une porte/fenêtre/…, alors cela peut être éliminé des calculs.
Vous l'aurez compris, les portails sont donc tout particulièrement adaptés aux scènes découpées en secteurs (les pièces donc), lesquels étant reliés par des portails (les portes et les fenêtres).
À noter qu'il est tout à fait possible de mixer portails et arbres BSP dans une même application, ce qui peut parfois apporter un gain encore non négligeable.

Liens

• Tutoriel simple sur les portails
• Hidden surface removal (portails et PVS)

Les quadtrees/octrees
Les quadtrees (arbres quaternaires) et les octrees (arbres octaires) procèdent eux aussi par un découpage récursif de la scène, mais cette fois beaucoup plus simplement que les arbres BSP. Imaginez un rectangle 3D recouvrant la totalité de votre scène : c'est la racine de votre arbre. Découpez-le en 4 (quatrees) ou en 8 (octrees) rectangles 3D de taille égale, déterminez dans lequel de ces rectangles se trouve chaque polygone de la scène, puis recommencez le processus sur chaque rectangle jusqu'à atteindre un nombre limite de polygones, ou une taille limite de rectangle.
L'efficacité des quadtrees et octrees vient du fait qu'ils permettent de stopper les calculs très tôt. En effet, si l'on peut déterminer que l'un de nos (gros) rectangles peut être écarté des calculs, alors ses fils le seront aussi, et il est inutile d'aller plus loin dans la récursion.
De par leur construction indépendante de la scène, les quadtrees et octrees sont tout à fait adaptés aux environnements dont la géométrie est disposée de manière quelconque, par exemple les scènes d'extérieur. Les quatrees n'étant subdivisés que suivant deux axes, on les utilise principalement lorsque la vue est en 2D, ou figée sur l'un des axes (ex. : les jeux de stratégie, en vue de dessus). Pour tout le reste, on utilise les octrees.
Nous citerons également une extension des octrees : les loose octrees, permettant de mieux gérer les objets à cheval entre plusieurs rectangles.

Liens

• Tutoriel simple sur les quatrees et octrees
• Loose octrees

Les hiérarchies de volumes englobants (bouding volumes hierarchies : sphere-trees/AABB-trees/OBB-trees/…)
Les hiérarchies de volumes englobants fonctionnent sur le même principe que les octrees ou les quadtrees : la scène est découpée récursivement, et ce sont les nœuds terminaux de l'arbre qui contiennent les polygones ou groupes de polygones.
Le volume englobant utilisé peut être à peu près tout et n'importe quoi : sphère, AABB (boîte alignée sur les axes), OBB (boîte orientée), polygone… Plus le volume sera complexe, plus il englobera précisément l'objet, mais plus il sera coûteux en calculs. Ainsi les sphères offrent typiquement des performances optimales et sont très simples à manipuler, mais englobent très approximativement les objets.
Hormis leur simplicité, le gros avantage des hiérarchies de volumes englobants est qu'elles peuvent être mises à jour facilement, et donc utilisées sur des objets dynamiques de la scène. On utilise notamment beaucoup les sphere-trees ou OBB-trees pour effectuer le découpage des personnages animés, en vue de gérer leurs collisions.

Liens

• Introduction to bounding volumes hierarchies
• BVH analysis
• Collision detection of deformable objects