Octree - LinkFang.de





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

Octrees können als Erweiterung von Binärbäumen und Quadtrees 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

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:

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

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-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 Tensorfeldern. Ein Voxelgitter mit Grauwerten beispielsweise ist als Skalarfeld ein Tensorfeld nullter Ordnung, Voxelgitter mit drei Farbwerten nach dem RGB-Schema und einer Alpha-Komponente sind als Vektorfeld ein Tensorfeld erster Ordnung.

Weblinks

 Commons: Octree  – Sammlung von Bildern, Videos und Audiodateien

Einzelnachweise

  1. Martin Seiler et al., A Threefold Representation for the Adaptive Simulation of Embedded Deformable Objects in Contact, Journal of WSCG, Pilsen, Tschechien, Februar, 2010.
  2. 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)

Kategorien: Suchbaum

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Octree (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.