- Partition binaire de l'espace
-
Pour les articles homonymes, voir BSP.La partition binaire de l'espace (binary space partitioning ou BSP) est un système utilisé par certains moteurs 3d pour diviser l'espace en zones convexes. L'agencement de ces zones se fait à l'aide de plans, disposés en arbre binaire.
Sommaire
Définition
Description
D'un point de vue géométrique, le BSP est la version générique des arbres de plans pour partitionner l'espace. Les octrees et kd-trees sont des cas particuliers du bsp.
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".
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 kd-trees), 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 le 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 bolé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 designer, 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.
les "bsp-holes"
Il s'agit d'un bug couramment rencontré lors de la construction des arbres bsp, lorsque la géométrie est trop détaillée, sa découpe peut conduire à une échelle trop petite qui génère des bugs liés à l'approximation des nombres. Pour éviter ces bugs, 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.
Parcours
Le parcours d'un arbre bsp est très simple: on localise une forme (point, boite, sphère, capsule, nuage de points, rayon, polygone...) par rapport au plan-racine de l'arbre, puis récursion sur les nœuds enfants si la forme s'y trouve.
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.
Utilisation dans les jeux vidéo
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 quake1. 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 indie. Les différentes observations ci-dessous sont donc essentiellement basées sur l'étude de ces deux formats standards.
Occlusion / collisions / projections d'ombres
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 antiportails, 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 doom3. Doom3 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 reverse")
Evolution 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 Trou BSP, erreurs de conception communes à tous les moteurs.
Évolution au niveau visuel
Utilisé d'abord en 2 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 "low polygon", il est donc necessaire 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 et des terrains de l'Unreal Engine, apparu avec la deuxième version du moteur en 2002, dans le jeu Unreal 2. 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 Mesh (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 de bugs, 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 entraine 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-mesh, et l'autre étant une Skybox. Des jeux comme Unreal, 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 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.
Voir aussi
- Octree
- Quadtree
- Fichier de map compilée pour le Valve Hammer Editor (Half-Life, Counter-Strike...) ou Doom et Quake.
Wikimedia Foundation. 2010.
