Die Octree Struktur bei der Gittergenerierung wird primär dazu verwendet, eine günstige Punkteverteilung zu erzeugen. Aber auch die generierten Zellen werden für weitere Zerlegungen z.B. in Tetraederelemente benutzt [Yer84][She91][Hit93][Con93][Con91][Con88].
Ein Octree ist eine Baumstruktur, dessen Blätter Quader sind und dessen Seitenkanten parallel zu den Koordinatenachsen verlaufen. Die Größe einer Zelle (Quader) hängt von der Entfernung von der Baumwurzel ab. Die Seitenlängen halbieren sich von Ebene zu Ebene. Die Vereinigungsmenge aller Zellen approximiert das Objekt. Die Qualität der approximierten Struktur wird durch die Anzahl der zugelassenen Ebenen und von der Struktur der primären Geometrie festgelegt.
Der polygonale Rand bei allgemeinen Strukturen wird wie bei Tensor-Produkt-Gittern nicht exakt aufgelöst. Finite Octrees [Aya85] brechen nicht bei einer gewissen Ebene oder einem gewissen Auflösungsfehler ab, sondern es gilt als Abbruchkriterium:
Anhand des in Abbildung 5.11 gezeigten zweidimensionalen Beispiels, einem Quadtree, soll darauf aufmerksam gemacht werden, daß die generierten Zellen für eine qualitativ gute Triangulierung noch aufbereitet werden müssen. Es sind die in Abbildung 5.11 strichliert gezeichneten Kanten einzusetzen, um das Gesamtgitter 1 irregulär zu machen.
Aufbauend auf diesem 1 irregulären Gitter erfolgt die Triangulierung, wobei, wie in Abbildung 5.12 leicht ersichtlich ist, außer bei Randzellen nur einige Konfigurationen auftreten, wie die Zellen zu triangulieren sind. Bei dreidimensionalen Zerlegungen der Zellen in Tetraeder sind auch die Nachbarschaftsbeziehungen zu berücksichtigen, um eine gültige Zerlegung zu erhalten [Con91].
Es ist leicht ersichtlich, daß eine achsenparallele Vordiskretisierung bei schwach nichtplanaren Strukturen zu stark verzerrten Randelelementen führt. Um dies zu verhindern, kann man z.B. Punkte, die in der Nähe des Randes liegen und diese degenerierten Elemente bilden, auf den Rand verschieben und diese degenerierten Elemente entfernen. Bei Materialgrenzen und dreidimensionaler Zerlegung ist diese Aufgabe weitaus komplexer.
Abschließend soll angemerkt werden, daß diese Methode erfolgreich zur Gittergenerierung bei komplexen dreidimensionalen Strukturen angewendet wird, wo einige zehntausend Elemente benötigt werden. Solche Gitter genügen bei geeigneter Zerlegung der Zellen dem Delaunay-Kriterium.
