Binary space partitioning

Un article de Wikipédia, l'encyclopédie libre.

Pour les articles homonymes, voir BSP.

Le binary space partitioning, abrégé en BSP, est un système utilisé par un Moteur de jeu pour calculer des espaces "pleins" (bloquant) et "vides" (ou le joueur peut exister et se déplacer).

[modifier] Utilisation

Le BSP constituait la quasi totalité des jeux en 3D depuis DOOM, Unreal, Quake et dans une moindre mesure, Half-Life.

Le moteur de quake / half life était basé sur des polygones convexes. Il permet d'ajouter, dans un espace vide infini, des plans sur lequel seront plaquées des textures. Le joueur peut alors se déplacer à la surface des plans horizontaux.

Le système de modélisation d'arbre bsp utilisé par l'Unreal Engine appelé constructive solid geometry part d'un espace infini mais plein, où de l'espace est soustrait afin de créer les plans nécessaires à la formation d'une pièce ( excavation booléenne ). Le temps de création est ainsi réduit, et le moteur, lors de la compilation, n'a pas a recalculer l'espace pour remplir les zones situées hors du champ d'action du joueur. Ce système présente aussi l'avantage de réduire les risques de HOM, ou Trou BSP, erreurs de conceptions communes à tous les moteurs.

[modifier] Évolution

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.

[modifier] Le remplacement progressif

Dans les jeux récents (à partir des années 2000 environ), le BSP a tendance à être supplanté pour les détails d'architectures et les décorations complexes, par des systèmes mieux optimisés. L'exemple le plus parlant est sans doute celui des Static-Meshes 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.

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 vitesses de certains jeux.

[modifier] Les niveaux extérieurs

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 bogues, les générateurs de terrains ont étés 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. Notons qu'aujourd'hui, des niveaux de ce type seraient sujets à des ralentissements, dûs aux problèmes d'optimisation du BSP de plus en plus délaissée. Ainsi, sous les dernières versions de l'Unreal Engine, le BSP ne remplit pas sa fonction occlusive permettant l'amélioration des performances (ce qui devrait être corrigé dans la version 3 du moteur).

[modifier] Éclairage des surfaces

L'éclairage des surfaces BSP a subi trois grandes étapes. D'abord fut l'éclairage basique et statique utilisé sous DOOM et DOOM 2 : 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.

[modifier] Collisions

Si l'augmentation du nombre de polygones a rendu presque désuète l'utilisation des bsp tree comme structures d'affichages, le bsp est toujours une structure très utilisée pour la gestion des collisions en raison du z-ordering.