thumb|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.
thumb|Partition binaire d'un espace à trois dimensions pour la construction d'un arbre k-d.
La partition binaire de l'espace ( 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 . 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..
1980 Fuchs . é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. 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 dUnreal.
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. 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 lid Tech et lUnreal Engine. Lid Tech se contente d'additionner des solides convexes, lUnreal 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 lid 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 lUnreal 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 : 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 Fichier:Example of BSP tree construction - step 1.svg 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}.