2A01:C22:9126:1700:2D6D:2627:CF81:3C5: /* Weitere Anwendungsgebiete */

2021-07-28T20:08:15Z

Weitere Anwendungsgebiete

Neue Seite

Ein '''Octree''' (von {{laS|octo|de=acht}} und {{enS|tree|de=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 hauptsächlich in der [[Computergrafik]] verwendet, um dreidimensionale Datensätze hierarchisch zu untergliedern. Die Wurzel repräsentiert dabei alle Daten, jeder andere Knoten repräsentiert einen Oktanten der Daten seines direkten Vorgängers. Sie eignen sich dadurch zur Umsetzung der Strategie [[Teile und herrsche (Informatik)|Teile und herrsche]].

Octrees können als Erweiterung von [[Binärbaum|Binärbäumen]] und [[Quadtree]]s angesehen werden: Binärbäume untergliedern eindimensionale Daten, Quadtrees zweidimensionale und Octrees dreidimensionale; gelegentlich wird eine Verallgemeinerung auf beliebig-dimensionale Daten [[N-Tree]] genannt. Eine weiter verallgemeinerte Version, bei der die Dimensionen nicht festgelegt sind, ist der [[B-Baum]].

== Anwendung ==
[[Datei:Octree2.png|mini|Schema eines Octrees. Links die Unterteilung des würfelförmigen Volumens, rechts der resultierende Octree.]]

Das folgende Beispiel veranschaulicht die häufigste Anwendung eines Octrees, nämlich zur gleichmäßigen Gliederung eines würfelförmigen Datenraumes: Die Wurzel steht für den gesamten Würfel. Der Würfel wird in acht kleinere Würfel – die Oktanten – zerteilt und jeder Nachfolger der Wurzel steht für einen davon. Jeder dieser kleineren Würfel wird wiederum in acht noch kleinere Würfel zerteilt und so weiter. Die Untergliederung eines Teilwürfels endet, wenn keine weitere Teilung mehr möglich oder aber nicht notwendig ist.

Das Ursprungsvolumen muss nicht würfelförmig sein, sondern kann auch allgemein quaderförmig sein. Auch eine Unterteilung der Volumen in ungleich große Teile ist möglich. In der Regel werden in den Knoten zusätzliche Informationen über die untergeordneten Knoten abgelegt. So enthält z. B. jeder Knoten der speziellen Ausprägung Min-Max-Octree das Minimum und das Maximum des folgenden Teilbaumes, was effizientes Suchen ermöglicht.

=== Weitere Anwendungsgebiete ===
Allgemeine Anwendungsgebiete für Octrees sind:
* Bildrepräsentation
* Raumindizierung (z. B. in [[Geoinformationssystem|Geografischen Informationssystemen]])
* Gruppierung von Partikeln in [[Molekulardynamik]]/[[Discrete element method|DEM]]-Simulationen
* [[Hidden Surface Removal]] von Terraindaten
* Kollisionserkennung in 3D-Computerspielen
* Hierarchical [[Splatting]]
* Adaptives Lösen von Differentialgleichungen, z. B. von deformierbaren Körpern<ref>[http://www.vision.ee.ethz.ch/publications/get_abstract.cgi?articles=804&mode=&lang=de Martin Seiler et al., ''A Threefold Representation for the Adaptive Simulation of Embedded Deformable Objects in Contact'', Journal of WSCG, Pilsen, Tschechien, Februar, 2010.]</ref>
* [[Satz von Bayes|Zustandsschätzung]]<ref>[https://publikationen.bibliothek.kit.edu/1000035090/2608481 Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, ''Density Trees for Efficient Nonlinear State Estimation'', Proceedings of the 13th International Conference on Information Fusion, Edinburgh, United Kingdom, July, 2010.] (PDF; 3,2 MB)</ref>

== Spezielle Formen ==

=== Empty-Non-Empty-Octree ===
In einem Empty-Non-Empty-Octree wird in jedem Knoten entweder der Wert ''leer'' oder ''nicht-leer'' abgelegt. ''Leer'' gibt an, dass die vom Knoten repräsentierte Datenmenge keine verarbeitenswerten Daten enthält, ''nicht-leer'' gibt entsprechend an, dass die zugehörige Datenmenge verarbeitet werden muss. ''Leer'' ist normalerweise gleichzeitig das Abbruchkriterium für die Unterteilung; da die zugehörige Datenmenge keine interessanten Informationen mehr enthält, lohnt es sich auch nicht, sie weiter zu untergliedern.

=== Min-Max-Octree ===
[[Datei:Min-Max-Octree.png|mini|400px|Schema eines Min-Max-Octrees. Jeder Knoten enthält Minimum (oben) und Maximum (unten) seines Unterbaums. Bei der Suche nach dem Wert 3 müssen nur die Datenmengen der gelb markierten Knoten durchsucht werden.]]

In einem Min-Max-Octree werden in jedem Knoten das Minimum und das Maximum des Unterbaums des Knotens abgelegt. Min-Max-Octrees eignen sich dadurch für effizientes Suchen nach dem Vorbild der Binärbäume. Der Unterbaum eines Knotens wird nur durchsucht, wenn der gesuchte Wert zwischen Minimum und Maximum des Knotens liegt. So können eventuell Teile des Baums ausgespart und die Suche dadurch beschleunigt werden.

Für den Spezialfall, dass Minimum und Maximum in einem Knoten gleich sind, kann die Suche im Unterbaum ebenfalls ausgespart werden, denn der gesamte Unterbaum des Knotens enthält den gesuchten Wert. Normalerweise ist der Fall Minimum gleich Maximum auch das Abbruchkriterium für die Unterteilung, das heißt die zugehörige Datenmenge wird nicht weiter untergliedert.

Min-Max-Octrees werden beispielsweise in der Volumengrafik zur Beschleunigung des [[Marching Cubes|Marching-Cubes]]-Algorithmus verwendet. Hier werden alle Unterwürfel des Octrees gesucht, in denen ein vorgegebener Schwellwert enthalten ist. Dieser Schwellwert ist eine Materialdichte, für die aus den Voxeldaten eine Isooberfläche extrahiert werden soll.

== Tensorfelder ==
Mathematisch betrachtet eignen sich Octrees besonders zur Gliederung von [[Tensorfeld]]ern. Ein [[Voxel]]gitter mit [[Grauwert]]en beispielsweise ist als [[Skalarfeld]] ein Tensorfeld nullter Ordnung, Voxelgitter mit drei Farbwerten nach dem [[RGB-Farbraum|RGB-Schema]] und einer [[Alpha Blending|Alpha-Komponente]] sind als [[Vektorfeld]] ein Tensorfeld erster Ordnung.

== Weblinks ==
{{Commonscat|Octrees|Octree}}

== Einzelnachweise ==
<references />

[[Kategorie:Suchbaum]]

Octree - Versionsgeschichte

2A01:C22:9126:1700:2D6D:2627:CF81:3C5: /* Weitere Anwendungsgebiete */