Octree

Octree
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[1].

Les octrees sont l'analogie tridimensionnelle des quadtrees. Le nom est formé à partir d'oct et de tree (arbre, en anglais) et s'écrit octree, et non octtree. Chaque nœud d'un octree subdivise l'espace qu'il représente en huit sous-espaces (les octants).

Dans le cas d'un octree de type "point region" (PR), le nœud mémorise explicitement un point tridimensionnel qui est le "centre" de la subdivision pour ce nœud ; le point définit alors l'un des coins de chacun des huit enfants. Le nœud racine d'un octree de type PR peut représenter un espace infini.

Dans un octree de type "MX", le point de subdivision est implicitement le centre de l'espace que le nœud représente. Le nœud racine d'un octree de type MX doit représenter un espace fini de manière à ce que les centres implicites des nœud soient bien définis.

Sommaire

Application pour la quantification de couleur

L'algorithme d'octree de quantification de couleur (en), inventé par Gervautz et Pergathofer en 1988, encode les données de couleur d'une image en tant qu'octree pouvant aller jusqu'à neuf niveaux de profondeur. Les octrees sont utilisés parce que 23 = 8 et qu'il y a trois composantes de couleurs dans le système RVB.

L'indice de nœud pourqu'il s'étende à partir du niveau plafond est determiné par une formule qui utilise les bits les plus significatifs des composantes rouge, vert et bleue, 4r + 2g + b, par exemple. Le niveau inférieur suivant utilise la suite de la signification des bits et ainsi de suite. Les bits les moins significatifs sont parfois ignorés afin de réduire la taille de l'arbre.

L'algorithme est grandement efficace en termes de consommation de mémoire puisqu'il limite la taille de l'arbre. Le niveau plancher de l'octree est constitué de nœuds terminaux qui accumulent les données de couleur qui ne sont pas représentées dans l'arbre. Ces nœuds contiennent initialement des bits uniques. Si bien plus de couleurs de palette que le quantité désirée sont entrées dans l'octree, sa taille peut être continuellement réduite en cherchant après un nœud plancher et en moyennant ses bits dans un nœud terminal, éliminant ainsi diverses parties de l'arbre.

Une fois que la phase d'échantillonnage est terminée on obtiendra approximativement le nombre requis de couleurs en parcourant toutes les routes possible de l'arbre en partant de son nœud racine jusqu'à ses nœuds terminaux tout en tenant compte, au passage, des différent bits.

Note et références

  1. (en) Henning Eberhardt, Vesa Klumpp et Uwe D. Hanebeck, Density Trees for Efficient Nonlinear State Estimation, dans Proceedings of the 13th International Conference on Information Fusion, Édimbourg, juillet 2010

Voir aussi

Articles connexes

Liens externes


Wikimedia Foundation. 2010.

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

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Octree — Izquierda: Subdivisión recursiva de un cubo en octantes. Derecha: La grilla octree correspondiente. Una grilla octree es una estructura árbol (informática) de datos en la cual cada nodo interno tiene exactamente 8 hijos . Las grillas octree se… …   Wikipedia Español

  • Octree — Left: Recursive subdivision of a cube into octants. Right: The corresponding octree. An octree is a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three dimensional space by… …   Wikipedia

  • Octree — Ein Octree (von lat. octo „acht“, und engl. tree „Baum“) ist eine Datenstruktur der Informatik. Ein Octree ist ein gewurzelter Baum, dessen Knoten jeweils entweder acht direkte Nachfolger oder gar keine Nachfolger haben. Octrees werden… …   Deutsch Wikipedia

  • octree — noun A treelike data structure each of whose nodes has up to eight children, most often used to partition a three dimensional space by recursively subdividing it …   Wiktionary

  • Sparse Voxel Octree — Построение воксельного октодерева Sparse Voxel Octree (SVO, рус. Разреженное воксельное октоде …   Википедия

  • OLI — octree level index …   Medical dictionary

  • OLI — • octree level index …   Dictionary of medical acronyms & abbreviations

  • Oktalbaum — Ein Octree (von lat. oct „acht“, und engl. tree „Baum“) ist eine Datenstruktur der Informatik. Ein Octree ist ein gewurzelter Baum, dessen Knoten jeweils entweder acht direkte Nachfolger oder gar keine Nachfolger haben. Octrees werden… …   Deutsch Wikipedia

  • Октодерево — Слева: Рекурсивное разделение куба на октанты. Справа: Соответствующее октодерево …   Википедия

  • Level set (data structures) — In computer science a level set data structure is designed to represent discretely sampled dynamic level sets functions.A common use of this form of data structure is in efficient image rendering.Chronological developmentsThe powerful level set… …   Wikipedia

Share the article and excerpts

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