Partition binaire de l'espace

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

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

Publications associées (1)

Concepts associés (24)

Séances de cours associées (9)

Octree

right|thumb|240px|Des nœuds d'octree dépeints en tant que division d'un espace de couleur. Un octree est une structure de données de type arbre dans laquelle chaque nœud peut compter jusqu'à huit enfants. Les octrees sont le plus souvent utilisés pour partitionner un espace tridimensionnel en le subdivisant récursivement en huit octants. Quelques utilisations courantes des octrees : l'indexation spatiale la détection efficace de collision dans le cadre de la 3D l'élimination des objets hors du cône de vue dans le cadre d'un rendu 3D l'observateur d'état.

Partition binaire de l'espace

Quake engine

The Quake engine is the game engine developed by id Software to power their 1996 video game Quake. It featured true 3D real-time rendering and is now licensed under the terms of GNU General Public License v2.0 or later. After release, the Quake engine immediately forked. Much of the engine remained in Quake II and Quake III Arena. The Quake engine, like the Doom engine, used binary space partitioning (BSP) to optimise the world rendering. The Quake engine also used Gouraud shading for moving objects, and a static lightmap for non-moving objects.

L'algorithme de Huffman : mécaniser la preuve CS-550: Formal verification

Explore la mécanisation de l'algorithme de Huffman et sa mise en œuvre fonctionnelle.

Arbres binaires et nombres catalans

Couvre la définition des arbres binaires, des formules récursives et des fonctions génératrices pour les nombres catalans.

Eclairage : ombres et récursivité CS-341: Computer graphics

Explore plusieurs sources de lumière, ombres, tracé de rayons récursif et calculs d'éclairage en tracé de rayons.

Asymptotically Optimal Contextual Bandit Algorithm Using Hierarchical Structures

Hakan Gökcesu, Kaan Gökcesu

We propose an online algorithm for sequential learning in the contextual multiarmed bandit setting. Our approach is to partition the context space and, then, optimally combine all of the possible mappings between the partition regions and the set of bandit arms in a data-driven manner. We show that in our approach, the best mapping is able to approximate the best arm selection policy to any desired degree under mild Lipschitz conditions. Therefore, we design our algorithm based on the optimal adaptive combination and asymptotically achieve the performance of the best mapping as well as the best arm selection policy. This optimality is also guaranteed to hold even in adversarial environments since we do not rely on any statistical assumptions regarding the contexts or the loss of the bandit arms. Moreover, we design an efficient implementation for our algorithm using various hierarchical partitioning structures, such as lexicographical or arbitrary position splitting and binary trees (BTs) (and several other partitioning examples). For instance, in the case of BT partitioning, the computational complexity is only log-linear in the number of regions in the finest partition. In conclusion, we provide significant performance improvements by introducing upper bounds (with respect to the best arm selection policy) that are mathematically proven to vanish in the average loss per round sense at a faster rate compared to the state of the art. Our experimental work extensively covers various scenarios ranging from bandit settings to multiclass classification with real and synthetic data. In these experiments, we show that our algorithm is highly superior to the state-of-the-art techniques while maintaining the introduced mathematical guarantees and a computationally decent scalability.

2019