Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Partition binaire de l'espace
Résumé
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 (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.
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).
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.