Partition binaire de l'espace (haut) et arbre BSP correspondant (bas). L'espace contient des segments {A, B1, B2, C1, C2, D1, D2, D3}. Le nœud racine contient le segment A ; les deux sous-arbres correspondent aux zones de part et d'autre de A.Partition binaire d'un espace à trois dimensions pour la construction d'un arbre k-d.
La partition binaire de l'espace (binary space partitioning ou BSP) est un système utilisé pour diviser l'espace en zones convexes. Ces cellules sont délimitées par des hyperplans ; dans le cas d'un espace à deux dimensions (plan), les séparations sont des droites et les cellules sont des quadrilatères (souvent des rectangles) ; dans le cas d'un espace à trois dimensions, les séparations sont des plans et les cellules sont des polyèdres (souvent des parallélépipèdes rectangles).
Les cellules sont disposées en arbre binaire appelé arbre BSP. Cette structure de données facilite certaines opérations. Elle est notamment intéressante pour le rendu 3d et est donc utilisée pour la gestion des graphismes de certains jeux vidéo.
Historique
1969 Schumacker et coll.[1] publient un rapport décrivant comment des plans judicieusement positionnés dans un environnement virtuel peuvent accélérer l'ordonnancement de polygones. La technique utilise la profondeur de cohérence, une notion selon laquelle un polygone situé dans le demi-plan le plus éloigné de l'observateur ne peut pas masquer un polygone situé dans le demi-plan le plus proche. Cette notion est utilisée par les simulateurs de vol développés par General Electric et Evans & Sutherland. Toutefois, la création de la hiérarchie des polygones est faite manuellement par le concepteur de la scène.
1975 Bentley de l'université Stanford propose la structure des arbres k-d pour la recherche multidimensionnelle[2].
1980 Fuchs et coll.[3] étendent l'idée de à la représentation d'objets 3D virtuels, en utilisant les plans des polygones, et en partitionnant l'espace de manière récursive. Ils créent ainsi un algorithme entièrement automatisé de création d'une structure de donnée hiérarchisée pour les polygones, nommée Binary Space Partitioning Tree (BSP Tree). Ce procédé intervient dans une étape précalculatoire, avant la livraison à l'utilisateur final. Lors de l'exécution en temps réel, l'ordonnancement des polygones pour déterminer la visibilité est faite en parcourant l'arbre.
1981 La thèse de doctorat de Naylor associe les arbres BSP et la théorie des graphes pour déterminer la visibilité précalculée. Il met l'accent sur l'utilisation des arbres BSP en tant que structure de recherche indépendante de la dimension de l'espace, avec des applications sur la visibilité des surfaces. En utilisant le modèle de la navette spatiale, la thèse démontre de manière empirique que la taille de l'arbre et le nombre de nouveaux polygones créés est raisonnable.
1983 Fuchs et coll. décrivent un code minimal d'arbre BSP sur un système de mémoire tampon d'image Ikonas. C'est la première mise en œuvre de détermination de visibilité de surface en temps réel utilisant les arbres BSP.
1987 Thibault et Naylor[4] décrivent comment représenter des polyèdres en utilisant des arbres BSP, en contraste avec la méthode habituelle des B-Rep(boundary representation). On a une représentation de solide par opposition à une représentation de surfaces (les frontières de solides). Les outils proposés pour les polyèdres permettent le rendu de solides décrits par Constructive Solid Geometry (CSG) en temps réel. C'est le précurseur de la méthode de la conception des niveaux BSP utilisant des brosses (brushes), introduite dans l'éditeur de Quake et réutilisé dans l'éditeur d'Unreal.
1990 Naylor, Amanatides et Thibault fournissent un algorithme permettant de fusionner deux arbres BSP en un seul. Cela permet notamment : de combiner des objets en mouvement, représentés par des arbres BSP, avec un environnement statique lui aussi représenté par un arbre BSP ; d'effectuer des opérations booléennes entre polyèdres (CSG) de manière rapide ; des calculs de collision exacte en O(log n × log n) ; et d'ordonner de manière correcte des surfaces transparentes contenues dans des objets s'interpénétrant (utilisé pour un effet de vision par rayons X).
1990 Teller et Séquin proposent de déterminer les éléments potentiellement visibles avant livraison du logiciel, pour accélérer la détermination des surfaces visibles dans des environnements orthogonaux 2D.
1991 Gordon et Chen[5] décrivent une méthode efficace pour faire un rendu avant-arrière à partir d'un arbre BSP, au lieu de l'approche habituelle arrière-avant. Ils utilisent une structure de données dédiée pour enregistrer, de manière performante, les parties de l'écran qui ont déjà été dessinées et celles à qui ne le sont pas encore. Cet algorithme a été utilisé par John Carmack pour créer le jeu vidéo Doom.
1992 la thèse de doctorat de Teller décrit une méthode performante pour déterminer les ensembles potentiellement visibles, dans une étape de prétraitement, permettant d'accélérer la détermination des surfaces visibles en temps réel dans un environnement 3D formé de polygones. Cette méthode a été utilisée dans Quake et a contribué de manière significative aux performances du jeu.
1993 Naylor détermine ce qui caractérise un « bon » arbre BPS. Il mesure de manière mathématique le coût de recherche dans un arbre et l'applique pour construire de « bons » arbres, en se basant sur les cas probables plutôt qu'une analyse des pires cas. De manière intuitive, les bons arbres représentent des objets à différents niveaux de résolution (arbre d'approximations). Cette méthode présente des similarités avec le codage de Huffman et les arbres de recherche par permutation aléatoire .
1993 la thèse de doctorat de Hayder Radha décrit une méthode de représentation (naturelle) d'image utilisant les arbres BSP. Cela inclut le développement d'une structure de construction optimum d'arbre BSP pour une image arbitraire. Cette structure est fondée sur une nouvelle transformation d'image, la transformation par une droite de partition obtenue par régression des moindres carrés (Least-Square-Error Partitioning Line transform). La thèse de Radha développe également une structure de compression d'image avec un taux de distorsion optimal et une approche de manipulation d'image utilisant les arbres BSP.
Définition
Description
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 polygone 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.
Construction
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.
Exemple de construction
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] :
Choisir un polygone P dans la liste.
Créer un nœud N dans l'arbre BSP, et mettre P dans la liste des polygones de ce nœud.
Pour chaque polygone de la liste :
Si ce polygone est entièrement devant le plan contenant P, placer ce polygone dans la liste des polygones devant P.
Si ce polygone est entièrement derrière le plan contenant P, placer ce polygone dans la liste des polygones derrière P.
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).
Si le polygone est coplanaire avec P, l'ajouter à la liste des polygones du nœud N.
Appliquer cet algorithme à la liste des polygones devant P.
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é.
Les Trous BSP et les HOM
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ées à 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.
Parcours
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 :
Si le nœud courant est une feuille, afficher les polygones contenus dans le nœud courant.
Sinon, si le point de vue V est devant le nœud courant :
Afficher la branche enfant contenant les polygones situés derrière le nœud courant.
Afficher les polygones contenus dans le nœud courant.
Afficher la branche enfant contenant les polygones situés devant le nœud courant.
Sinon, si le point de vue V est derrière le nœud courant :
Afficher la branche enfant contenant les polygones situés devant le nœud courant.
Afficher les polygones contenus dans le nœud courant.
Afficher la branche enfant contenant les polygones situés derrière le nœud courant.
Sinon, le point de vue V se trouve exactement dans le plan associé au nœud courant. Donc :
Afficher la branche enfant contenant les polygones situés devant le nœud courant.
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.
Utilisation dans les jeux vidéo
Dans les jeux vidéo, certains objets ou sujets sont mobiles.
En raison de la complexité de construction d'arbres BSP adaptés aux moteurs de jeu, beaucoup de sociétés ne développent pas leur propre format de map mais utilisent des moteurs existants, notamment les standards Unreal et id Tech(Quake). Par exemple, le moteur d'Half-Life est basé sur le moteur de Quake 1. Le standard actuel est l'Unreal Engine. L'id Tech, passé à la communauté open source, est devenu le format BSP standard utilisé par les développements amateur ou indépendant.
Les différentes observations ci-dessous sont donc essentiellement basées sur l'étude de ces deux formats standards.
Un BSP une fois construit sert à faire un z-ordering des faces ainsi qu'y stocker d'autres données (collisions, etc). Pour gérer l'occlusion culling, il faut au préalable calculer la géométrie des feuilles de l'arbre pour savoir lesquelles sont en contact, puis générer des polygones qui les connectent appelés "portails".
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).
Évolution mathématique dans les jeux vidéo classiques
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.
Évolution au niveau visuel
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.
Combinaison du BSP avec les structures d'affichages détaillées
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
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.
Éclairage des surfaces
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.
Autres applications
De manière générale, les structures arborescentes sont utilisées pour de nombreux algorithmes. On peut par exemple utiliser une partition binaire pour trouver les plus proches voisins d'un point ou la recherche par plage : la construction de l'arbre est gourmande en ressource, mais son parcours est bien plus rapide qu'un balayage systématique de tous les points[6]. L'arbre k-d est à ce titre intéressant car des algorithmes de partition permettent de construire des arbres à peu près équilibrés ayant peu de cellules vides et un rapport grande dimension/petite dimension de cellule favorable à la recherche[7].
Abandon du BSP dans les pipeline graphiques modernes
Le BSP fut longtemps utilisé dans des moteurs de jeux vidéo tels que les anciennes versions de Quake ou Unreal, car il avait deux avantages : trier les faces à l'époque où la 3d n'était pas rendue par les GPU, et générer automatiquement un graphe de cellules et portails très fin qui permettait de calculer une occlusion au polygone près.
Cependant la structure BSP avait l'inconvénient de générer de nombreux problèmes : "holes", "leaks", "distortions", "flat leaves", et des arbres peu optimisés en raison des nombreux plans quasi-confondus.
Dans les moteurs 3d modernes l'occlusion se fait objet par objet ("chunk" ou "batch"), on utilise donc des cellules plus grossières, qui peuvent être modélisées manuellement (Cry Engine), ou encore des cubes générés automatiquement (Unreal 4, bibliothèque Umbra utilisée par Unity et id Tech 6). On utilise alors des structures de rangement dérivées du BSP (octrees et kd-trees, basés sur des plans orthogonaux, donc des normales non-approximatives) qui ont l'avantage d'être stables et de ne pas résulter en des approximations lors de leur construction.
Le BSP reste en revanche utilisé comme outil de modélisation pour accélérer la "Constructive Solid Geometry", construction de solides complexes à partir de solides simples.
Notes et références
↑(en) Robert A. Schumacker, Brigitta Brand, Maurice G. Gilliland et Werner H. Sharp, Study for Applying Computer-Generated Images to Visual Simulation, U.S. Air Force Human Resources Laboratory, , 142 p..
↑(en) Jon Louis Bentley, « Multidimensional binary search trees used for associative searching », Communications of the ACM, vol. 18, no 9, , p. 509-517 (DOI10.1145/361002.361007).
↑ a et b(en) Henry Fuchs, Zvi M. Kedem et Bruce F Naylor, « On Visible Surface Generation by A Priori Tree Structures », SIGGRAPH '80 Proceedings of the 7th annual conference on Computer graphics and interactive techniques, New York, ACM, , p. 124–133 (DOI10.1145/965105.807481).
↑(en) William C. Thibault et Bruce F. Naylor, « Set operations on polyhedra using binary space partitioning trees », SIGGRAPH '87 Proceedings of the 14th annual conference on Computer graphics and interactive techniques, New York, ACM, , p. 153–162 (DOI10.1145/37402.37421).
↑(en) S. Chen et D. Gordon, « Front-to-Back Display of BSP Trees », IEEE Computer Graphics & Algorithms, , p. 79–85 (lire en ligne [PDF]).
