Partition binaire de l'espace

D'un point de vue géométrique, les arbres BSP sont la version générique des arbres de plans pour partitionner l'espace. Les arbres k-d sont des cas particuliers des arbres BSP, dans lesquels les plans sont alignés avec les axes et dont les nœuds ne contiennent qu'un point. Les arbres BSP sont des structures plus générales dans lesquels les plans peuvent avoir n'importe quelle orientation — il s'agit en général de plans générés à partir des polygones — et dont les nœuds peuvent contenir tout type d'objets géométriques — en général des formes « primitives » (formes géométriques simples : polygones, cubes, sphères, cylindres, …).

Le premier nœud de l'arbre est l'espace, il contient un plan qui divise l'espace en deux. Ses deux nœuds enfants sont des demi-espaces, ils contiennent eux-mêmes des plans qui redivisent en deux ces sous-espaces. Les nœuds terminaux de l'arbre ne contiennent plus aucun plan et sont appelés des « feuilles ».

Le « niveau de détail » — où l'on s'arrête dans la construction de l'arbre, ce que contiennent les nœuds — dépend du domaine d'application. Par exemple :

• pour des images de synthèse avec rendu 3d, les nœuds contiennent un ensemble de polygones que l'on peut tracer dans un ordre arbitraire,
  • s'il y a des faces cachées (back-face culling), un nœud contient un ensemble de polygones convexes,
  • si les deux faces d'un polygones peuvent être vues (selon le point de vue), un nœud ne contient que des polygones coplanaires ;
• en calcul de collision ou en lancer de rayon, un nœud contient une portion de l'espace dans laquelle les tests d'interception sont directs.

La construction d'un arbre BSP peut s'appuyer sur des techniques très différentes.

Elle est très simple lorsque l'on souhaite simplement s'en servir comme structure de rangement de polygones. Les moteurs physiques utilisent souvent des BSP rudimentaires pour stocker la géométrie statique (généralement des arbres k-d), leur construction se fait très rapidement.

Les moteurs de jeu vidéo utilisent des systèmes de construction beaucoup plus complexes car le BSP doit coïncider avec une structure de type secteur/portail afin d'effectuer des calculs d'occlusion. Pour avoir une structure la plus propre possible, les arbres sont généralement construits non pas à partir d'un maillage polygonal, mais à l'aide d'une imbrication de solides convexes, comme le font l'id Tech et l'Unreal Engine. L'id Tech se contente d'additionner des solides convexes, l'Unreal Engine introduit l'excavation booléenne afin d'optimiser davantage la géométrie des arbres.

Une fois l'arbre BSP construit, il est converti en structure de type secteur/portail, structure sur laquelle va s'appuyer l'occlusion. Dans l'id Tech engine, les portails sont générés automatiquement par un algorithme de clipping, puis l'occlusion est précalculée dans des bitmask appelés potentially visible sets. Dans l'Unreal Engine, à partir de la version 2, c'est le processus inverse : les portails sont construits à la main par le concepteur, et ils sont ajoutés à la géométrie de l'arbre BSP. L'occlusion est calculée en temps réel grâce aux portails.

Ce processus de construction des BSP maps étant très long et coûteux à développer, les studios de création de jeux vidéo préfèrent généralement utiliser les standards id Tech ou Unreal.

Considérons un moteur de rendu 3d dans le cas où les deux faces des polygones sont susceptibles d'être vues. On peut appliquer l'algorithme de construction récursif suivant[3] :

1. Choisir un polygone P dans la liste.
2. Créer un nœud N dans l'arbre BSP, et mettre P dans la liste des polygones de ce nœud.
3. Pour chaque polygone de la liste :
   1. Si ce polygone est entièrement devant le plan contenant P, placer ce polygone dans la liste des polygones devant P.
   2. Si ce polygone est entièrement derrière le plan contenant P, placer ce polygone dans la liste des polygones derrière P.
   3. Si le plan contenant P est sécant avec le polygone, diviser le polygone en deux par le plan de P, et placer chacun des demi-polygones dans la liste adéquate (devant P, derrière P).
   4. Si le polygone est coplanaire avec P, l'ajouter à la liste des polygones du nœud N.
4. Appliquer cet algorithme à la liste des polygones devant P.
5. Appliquer cet algorithme à la liste des polygones derrière P.

On peut ainsi ordonner les polygones du plus éloigné vers le plus proche du point de vue, et donc savoir dans quel ordre dessiner les polygones pour prendre en compte les effets de masquage.

Plus concrètement, prenons l'exemple d'un plan (espace à deux dimensions) dans lequel les objets géométriques sont des segments de droite. Chaque segment possède une orientation, il a donc un « côté avant » et un « côté arrière », défini lors de la création du segment.

	L'espace contient quatre segments de droite {A, B, C, D} ; s'il s'agissait d'un problème de rendu 3D, ce seraient des polygones formant une « scène ». Dans l'arbre, les nœuds de l'arbre sont dans des cercles, et les listes d'objets devant ou derrière sont dans des rectangles arrondis. Le côté avant de chaque segment est indiqué par une flèche
i.	Nous appliquons l'algorithme présenté ci-dessus : Nous choisissons arbitrairement un segment, ici le A. Nous créons le nœud racine contenant A. Les segments sécants avec la droite portant A sont coupés ; nous avons donc de nouveaux segments, {B1, B2, C1, C2, D1, D2}. Certains sont situés devant A, {B2, C2, D2}, et d'autres situés derrière, {B1, C1, D1}. Nous traitons, de manière récursive, d'abord les segments situés devant A (étapes ii–v), puis ceux situés derrière (étapes vi–vii).
ii.	Nous considérons les segments situés devant A, {B2, C2, D2}. Nous créons un nœud enfant, nous choisissons un segment arbitraire, B2, et nous l'ajoutons à ce nœud. Nous coupons le segment sécant avec la droite portant B2, ce qui crée deux nouveaux segments, {D2, D3}. Nous séparons les segments situés devant B2, {D2}, et ceux situés derrière, {C2, D3}.
iii.	Nous considérons les segments situés devant B2. Il n'y a qu'un seul segment, D2, nous créons donc un nœud enfant de B2 le contenant, il s'agit d'une feuille de l'arbre.
iv.	Nous considérons maintenant les segments derrière B2, {C2, D3}. Nous choisissons arbitrairement un segment, C2, et l'ajoutons au nœud enfant de B2 que nous créons. La liste des segments situés devant C2 est {D3}, la liste des segment situés derrière est vide..
v.	Nous considérons la liste des segments devant C2. Le seul segment qu'elle contient, D3, est ajouté au nœud enfant de C2 que nous créons.
vi.	Nous avons traité tous les segments situés devant A ; nous traitons maintenant ceux situés derrière lui. Nous choisissons un segment arbitraire, B1, que nous mettons dans le nœud enfant de A que nous créons. Nous séparons les segments en deux listes : les segments situés devant B1, {D1}, et ceux situés derrière, {C1}.
vii.	Nous traitons les segments situés devant B1. Il n'y a qu'un seul segment, D1, nous créons donc un nœud enfant de B1 pour l'y mettre.
viii.	Nous traitons les segments situés derrière B1. Il n'y a qu'un seul segment, C1, nous créons donc un nœud enfant de B1 pour l'y mettre. L'arbre BSP est terminé.

Un trou BSP, ou BSP-hole, est un problème couramment rencontré lors de l'affichage d'un graphique stocké sous forme d'un arbre BSP. Cela se manifeste par un trou dans l'objet représenté, qui peut être noir, ou bien laisser paraître ce qu'il y a derrière ; dans ce cas, on parle de « palais des glaces », ou HOM (pour hall of mirror), mais on peut avoir un HOM sans qu'il y ait de trou BSP.

Certains trous BSP sont aléatoires : ils n'apparaissent que sous certains points de vue. D'autres sont permanents : l'objet est absent quel que soit le point de vue ; il s'agit en général d'une erreur d'édition. Il peut également y avoir un effet de collision contre un obstacle invisible (ICH, invisible collision hull) : le moteur détecte une collision et empêche le joueur d'avancer, mais aucun objet ne s'affiche.

Le trou BSP se rencontre en général lorsque la géométrie est trop détaillée. Sa découpe peut conduire à une échelle trop petite qui génère des erreurs liés à l'approximation des nombres (erreur d'arrondi). Pour éviter ces problèmes, les programmes encodeurs de BSP détruisent la géométrie là où l'échelle devient trop petite, ce qui fait des trous dans l'arbre.

Pour éviter ces trous, il faut simplifier la géométrie. C'est pourquoi les parties détaillées d'une map doivent être réalisées avec des éléments qui ne font pas partie du BSP : quadpatch, trimesh, models et entities pour l'id Tech engine, terrains et static meshes pour l'Unreal Engine.

Un HOM se rencontre lorsque le moteur graphique n'a rien à afficher (ce qui ne signifie pas qu'il y ait un trou BSP) ; pour économiser les ressources, le moteur se contente de dessiner par-dessus l'ancienne image et ne l'efface pas, on voit donc des éléments d'image affichés les uns par-dessus les autres comme lorsqu'il y a deux miroirs qui se font face, d'où le nom « palais des glace ». Le HOM est souvent rencontré dans les jeux de tir à la première personne : le point de vue du joueur est censé être dans une zone délimitée. Mais cette hypothèse peut être violée si le joueur utilise un mode « caméra virtuelle » (mode noclip) ; la portion de l'arbre BSP affichée est alors incomplète et contient des trous BSP, qui laissent paraître des éléments de l'ancienne image.

Le parcours d'un arbre BSP est linéaire en temps, O(n). L'algorithme de parcours dépend du but poursuivi.

La localisation d'un point est l'opération la plus simple et se fait dans une petite boucle, sans besoin de fonction récursive. On teste de quel côté du plan racine se trouve le point, puis on recommence sur l'enfant correspondant, et on boucle jusqu'à tomber dans la feuille qui contient le point.

Dans le cas d'un arbre représentant des polygones à afficher, le parcours de l'arbre peut servir à déterminer l'ordre dans lequel il faut afficher les polygones (algorithme du peintre). On utilise pour cela l'algorithme d'affichage récursif suivant :

1. Si le nœud courant est une feuille, afficher les polygones contenus dans le nœud courant.
2. Sinon, si le point de vue V est devant le nœud courant :
   1. Afficher la branche enfant contenant les polygones situés derrière le nœud courant.
   2. Afficher les polygones contenus dans le nœud courant.
   3. Afficher la branche enfant contenant les polygones situés devant le nœud courant.
3. Sinon, si le point de vue V est derrière le nœud courant :
   1. Afficher la branche enfant contenant les polygones situés devant le nœud courant.
   2. Afficher les polygones contenus dans le nœud courant.
   3. Afficher la branche enfant contenant les polygones situés derrière le nœud courant.
4. Sinon, le point de vue V se trouve exactement dans le plan associé au nœud courant. Donc :
   1. Afficher la branche enfant contenant les polygones situés devant le nœud courant.
   2. Afficher la branche enfant contenant les polygones situés derrière le nœud courant.

Arbre BSP à parcourir pour déterminer l'ordre d'affichage par rapport au point de vue (point vert).

Appliquons cet algorithme à l'exemple précédent :

• On commence à la racine, le nœud A. V se trouve devant le nœud (le devant étant indiqué par la flèche), donc on applique l'algorithme récursivement aux nœuds situés derrière, soit la branche B1.
  • Le nœud courant est B1. V est derrière B1, donc on applique l'algorithme récursivement aux nœuds situés devant, soit la branche D1.
    • Le nœud courant est D1. C'est une feuille, donc on affiche D1.
  • Puis on affiche B1.
  • Puis on applique l'algorithme récursivement aux nœuds situés derrière B1, soit la branche C1.
    • Le nœud courant est C1. C'est une feuille, donc on affiche C1.
• Puis on affiche A.
• Puis on applique l'algorithme récursivement aux nœuds situés devant A, soit la branche B2.
  • Le nœud courant est B2. V est derrière B2, donc on applique l'algorithme récursivement aux nœuds situés devant, soit la branche D2.
    • Le nœud courant est D2. C'est une feuille, donc on affiche D2.
  • Puis on affiche B2.
  • Puis on applique l'algorithme récursivement aux nœuds situés derrière B2, soit la branche C2.
    • Le nœud courant est C2. V se trouve devant le C2, donc on applique l'algorithme récursivement aux nœuds situés derrière.
      • Il n'y a pas de nœud.
    • Puis on affiche C2.
    • Puis on applique l'algorithme récursivement aux nœuds situés devant C2, soit la branche D3.
      • Le nœud courant est D3. C'est une feuille, donc on affiche D3.

Le nœud est parcouru de manière linéaire en temps, et les polygones sont affichés dans l'ordre du plus éloigné au plus proche (D1, B1, C1, A, D2, B2, C2, D3) comme requis par l'algorithme du peintre.

Ce sont les principales fonctions des arbres BSP : optimiser les calculs de collision, occlusion et ombres.

Le Doom engine calculait l'occlusion en temps réel, directement dans la routine d'affichage, en clippant les faces ordonnées à l'aide du BSP. Le Quake engine et ses dérivés précalcule l'occlusion dans des listes de groupes de feuilles qui peuvent se voir l'une et l'autre (potentially visible set). Dans les moteurs plus modernes l'occlusion s'appuie sur des portails et des anti-portails, le BSP perd sa fonction occlusive mais sert toujours de structure de rangement pour les indoors.

Dans les vieux moteurs, les calculs de collision se basaient directement sur les brushes (solides convexes) employés pour construire l'arbre. Dans le moteur de Doom, ces brushes étaient construits par l'arbre lui-même. Dans les moteurs plus récents les collisions s'appuient sur un moteur physique, dont la collisionmap peut être totalement indépendante de la structure de l'arbre.

Les ombres projetées ont été introduites dans Unreal Engine ou Doom 3. Doom 3 utilise un algorithme très proche de celui employé par la caméra pour rendre les faces, entièrement basé sur le BSP (voir Carmack's Reverse).

Le BSP était employé dans la quasi-totalité des jeux en 3D depuis Doom, Unreal, Quake et Half-Life.

Le moteur de Doom construisait les BSP à partir de secteurs polygonaux. Le moteur de Quake/Half-Life construit les BSP à partir de solides convexes. Le système de modélisation d'arbre BSP utilisé par l'Unreal Engine appelé constructive solid geometry introduit la notion d'excavation booléenne : on utilise des solides « inversés », qui rendent plus efficace la construction des BSP, ce système présente l'avantage de réduire les risques de HOM ou de trou BSP (voir ci-dessus), erreurs de conception communes à tous les moteurs.

Utilisé d'abord en deux dimensions pour la totalité des niveaux sous Doom, le BSP 2d ne permettait pas à l'origine de créer des pièces superposées sur l'axe Z (axe de la hauteur). Il s'agissait toutefois d'une limitation inhérente au moteur, le Doom Engine, qui, révolutionnaire pour l'époque, paraît aujourd'hui extrêmement limité.

C'est avec sa déclinaison en 3d dans le moteur de Quake et de ses successeurs Quake II ou Quake III, et ses concurrents Unreal, ou un peu plus tard Half-Life que le BSP atteint son maximum d'utilisation, les décors s'enrichissant grâce à la multiplication de la puissance des moteurs mais aussi de la vitesse de traitement et de la puissance de calcul des microprocesseurs, et l'apparition de Cartes graphiques de plus en plus puissantes. Le BSP constituait alors la plus grande partie de l'architecture globale des niveaux en 3D. C'est à cette époque que commencent à apparaître les acteurs de décorations, non constitués de BSP, mais peu nombreux et de création ardue. Les systèmes de préfabriqués permettent de créer des structures complexes, de les sauvegarder indépendamment du niveau en cours, et de les réutiliser plus tard à l'infini. Ces « Prefabs » sont alors préférés aux acteurs de décorations, mais étant constitués de BSP, ils en possèdent tous les inconvénients.

Le BSP a l'inconvénient d'être adapté pour les architecture à faible nombre de polygones (low polygon), il est donc nécessaire d'y ajouter des éléments non-BSP pour faire les détails.

Dans les jeux récents (à partir des années 2000 environ), le BSP a tendance à être couplé, pour les détails d'architectures et les décorations complexes, avec des systèmes mieux optimisés.

L'exemple le plus parlant est sans doute celui des static meshes (en) et des terrains de l'Unreal Engine, apparu avec la deuxième version du moteur en 2002, dans le jeu Unreal II. Ces objets sont l'évolution des acteurs de décoration non-BSP qui tendent à occuper la plupart des fonctions anciennement dévolues au BSP : objets mobiles, détails d'architectures, et de plus en plus, grandes formes générales des pièces.

L'id Tech 3 introduit les quadpatch (courbes) et les meshes quelconques. Des systèmes proches des terrains/staticmesh d'Unreal, cependant moins optimisés.

Les raisons de ce remplacement sont simples : les static meshes (et leur équivalents sous d'autres moteurs), sont insensibles à tous les problèmes liés au BSP : HOM, « solides fantômes » (sous Half-Life), etc. Ils permettent aussi d'améliorer la vitesse de chargement des niveaux : un static mesh peut être instancié. Cela signifie que le moteur n'a besoin de charger l'objet qu'une seule fois puis de le dupliquer autant de fois que nécessaire en lui appliquant les changements appropriés.

Cela n'améliore par contre pas la vitesse d'affichage : chaque objet ainsi « cloné » doit tout de même être affiché individuellement. Toutefois, la réduction du nombre d'accès aux disques durs permet malgré tout d'améliorer les performances sur certains jeux.

Les niveaux extérieurs utilisent très peu le BSP, et préfèrent des structures plus adaptées comme les terrains et les octrees.

Les systèmes de terrains en BSP demandant de grandes quantités de BSP fortement déformés causant de plus en plus de problèmes et d'erreurs, les générateurs de terrains ont été introduits en même temps que les static meshes, afin de créer de grandes pièces de géométries très optimisées pour ces types de rendus. L'utilisation combinée de static meshes et de générateurs de terrains de plus en plus puissants entraîne la création de niveaux comportant parfois un nombre d'objets BSP dérisoires : sous Unreal Tournament 2004, ces systèmes permettent de créer des niveaux comportant deux grands cubes vides, l'un contenant le terrain et les static meshes, et l'autre étant une Skybox. Des jeux comme Unreal et Half-Life utilisaient des terrains en BSP, très anguleux et d'optimisation difficile.

L'éclairage des surfaces BSP a subi trois grandes étapes. D'abord fut l'éclairage simple et statique utilisé sous Doom et Doom II: Hell on Earth : plusieurs niveaux d'éclairages définis permettent d'éclairer le niveau presque uniformément.

Les jeux de génération suivante permirent des ambiances très vivantes grâce à des éclairages dynamiques et contrastés comme certains niveaux de Unreal, Unreal Tournament, Half-Life. Dans Quake 3 est utilisé au choix ce système d'éclairage dynamique, ou un système de Lightmap : textures colorées appliquées par transparence sur la géométrie du niveau pour simuler les différences de lumières. Ce procédé interdit toute lumière dynamique, mais permet des ombres très précises et marquées. Sous UT2003 et son successeur direct UT2004, les Lightmap constituent la quasi-totalité des éclairages du BSP. Quelques systèmes de lumières dynamiques persistent, mais s'avèrent très coûteux en ressource, car obligeant le moteur à rafraîchir les Lightmaps à chaque instant. De plus, des lumières ne peuvent pas projeter d'ombres aussi réalistes et détaillées que les lumières statiques.

Les jeux plus récents comme Doom 3 sont fortement optimisés, et leurs systèmes d'éclairages à la fois détaillés et dynamiques permettent de projeter des ombres très bien gérées sur le BSP, mais aussi sur les acteurs de décoration.