Binary Space Partitioning

Binary Space Partitioning

Partition binaire de l'espace

Page d'aide sur l'homonymie Pour les articles homonymes, voir BSP.

La partition binaire de l'espace (binary space partitioning ou 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).

Sommaire

Utilisation

Le BSP constituait la quasi totalité des jeux en 3D depuis Doom, Unreal, Quake et 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.

É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.

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.

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é 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, dus 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).

É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.


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.

Voir aussi

  • Portail du jeu vidéo Portail du jeu vidéo
Ce document provient de « Partition binaire de l%27espace ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Binary Space Partitioning de Wikipédia en français (auteurs)

Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Binary space partitioning — (BSP) is a method for recursively subdividing a space into convex sets by hyperplanes. This subdivision gives rise to a representation of the scene by means of a tree data structure known as a BSP tree.In simpler words, it is a method of breaking …   Wikipedia

  • Binary Space Partitioning — Der Begriff Binary Space Partitioning (BSP, „binäre Raumpartitionierung“) bezeichnet eine Technik zur Partitionierung multidimensionaler Daten durch eine Menge von Hyperebenen. Die so erstellte Datenstruktur ist ein Binärbaum und wird BSP Baum… …   Deutsch Wikipedia

  • Binary space partitioning — 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 un moteur de jeu pour calculer des espaces pleins (bloquant) et vides (ou le… …   Wikipédia en Français

  • Binary Space Partitioning — …   Википедия

  • Binary Space Partition — Der Begriff Binary Space Partitioning (BSP, „binäre Raumpartitionierung“) bezeichnet eine Technik zur Partitionierung multidimensionaler Daten durch eine Menge von Hyperebenen. Die so erstellte Datenstruktur ist ein Binärbaum und wird BSP Baum… …   Deutsch Wikipedia

  • Binary tree — Not to be confused with B tree. A simple binary tree of size 9 and height 3, with a root node whose value is 2. The above tree is unbalanced and not sorted. In computer science, a binary tree is a tree data structure in which each node has at… …   Wikipedia

  • Partición binaria del espacio — Binary space partitioning o Partición Binaria del Espacio (BSP) es un método para subdividir recursivamente un espacio en elementos convexos empleando hiperplanos. Esta subdivisión da lugar a una representación de la escena por medio de una… …   Wikipedia Español

  • BSP (file format) — BSP is a map file extension used in games such as the Doom , Quake , and games that use Quake derived engines, such as the Half Life series. .BSP files use binary space partitioning to generate levels that can be rendered quickly while minimizing …   Wikipedia

  • Collision detection — For collision detection on networks see CSMA/CD Collision detection typically refers to the computational problem of detecting the intersection of two or more objects. While the topic is most often associated with its use in video games and other …   Wikipedia

  • Trie — A trie for keys A , to , tea , ted , ten , i , in , and inn . In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. Unlike a binary search… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”