Loading AI tools
De Wikipédia, l'encyclopédie libre
Pour les articles homonymes, voir BSP.
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.
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 :
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] :
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 :
|
 |
| 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é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.
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 :
Appliquons cet algorithme à l'exemple précédent :
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.
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).
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.
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].
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
