In der numerischen Strömungsmechanik (CFD) spielt die räumliche Diskretisierung, insbesondere die Netzgenerierung und -partitionierung, eine entscheidende Rolle für die Genauigkeit und Effizienz numerischer Simulationen. Das Netz legt fest, wie die kontinuierliche physikalische Domäne in diskrete Kontrollvolumina unterteilt wird, über die die Grundgleichungen gelöst werden. Im Allgemeinen werden in technischen Anwendungen zwei grundlegende Netztypen eingesetzt: strukturierte und unstrukturierte Netze.
Ein strukturiertes Netz zeichnet sich durch eine reguläre Gittertopologie aus, bei der jeder innere Knoten eine gleichbleibende Anzahl und Anordnung benachbarter Zellen aufweist, die typischerweise hexaedrische Elemente bilden. Diese einheitliche Struktur ermöglicht eine implizite Definition der Knotenkonnektivität anhand von Netzindizes, sodass keine explizite Nachbarspeicherung erforderlich ist. Strukturierte Netze liefern im Allgemeinen eine höhere numerische Genauigkeit und ein besseres Konvergenzverhalten, da sie eine überlegene Elementqualität und eine gleichmäßige Variation des Gitterabstands aufweisen. Die Erzeugung strukturierter Netze für komplexe Geometrien ist jedoch häufig arbeitsaufwendig, erfordert erheblichen manuellen Aufwand und in vielen Fällen eine Vereinfachung der Ausgangsgeometrie, um ein topologisch reguläres Gitter zu erhalten.
Im Gegensatz dazu fehlt einem unstrukturierten Netz dieses reguläre Verbindungsmuster. Innere Knoten können eine unterschiedliche Anzahl benachbarter Elemente aufweisen, die verschiedene Formen annehmen können, wie Tetraeder, Prismen, Pyramiden oder allgemeine Polyeder. Die Flexibilität unstrukturierter Netze ermöglicht eine automatisierte Netzgenerierung für geometrisch komplexe Domänen und macht sie geeignet für Simulationen mit komplizierten Randbereichen oder mehreren interagierenden Komponenten. Diese Flexibilität geht jedoch auf Kosten eines erhöhten Speicherbedarfs und eines höheren Rechenaufwands, da Nachbarschaftsbeziehungen während numerischer Berechnungen explizit gespeichert und abgerufen werden müssen.
Octree-Netze
Der Octree als Methode zur Organisation räumlicher Objekte unterteilt den Raum in Zellen auf Basis der Einheitsdichte und vermeidet damit die Notwendigkeit, während der Netzgenerierung alle Objekte zu iterieren. Das Prinzip ist verhältnismäßig einfach: Wenn die Partitionierungsbedingungen erfüllt sind, wird der dreidimensionale Raum in acht gleiche Abschnitte unterteilt und die räumlichen Objekte entsprechend zugeordnet. Ein Octree-Netz, eine verbreitete Form des unstrukturierten Netzes, wird erzeugt, indem die Berechnungsdomäne zunächst in ein oder mehrere große kubische Netze unterteilt wird. Diese großen kubischen Netze werden dann rekursiv in acht Teilnetze unterteilt, bis jedes Teilnetz vordefinierte Größenanforderungen erfüllt oder durch geometrische Grenzen beschnitten wird.
Obwohl Octree-Netze unstrukturierte Netze sind, weisen ihre inneren Hexaeder unterschiedlicher Größe feste Verfeinerungsbeziehungen auf. Dies ermöglicht eine indirekte Speicherung der Netzzellengeometrie und der Nachbarschaftsbeziehungen. Im Folgenden wird eine Methode vorgestellt, die die raumfüllende Kurve (Space-Filling Curve, SFC) zur Speicherung von Netzzellen nutzt.
Raumfüllende Kurven (SFC)
Eine raumfüllende Kurve ist ein eindimensionales Intervall, das eine Abbildung vom n-dimensionalen Raum in den eindimensionalen Raum enthält. Konzeptionell lässt sie sich als ein kontinuierlicher Pfad betrachten, der jeden diskreten Punkt innerhalb einer räumlichen Domäne in einer bestimmten Reihenfolge besucht. Diese Reihenfolge kann inhärent bestimmte räumliche Positionseigenschaften besitzen und damit die Optimierung des Cache-Layouts begünstigen.
Die Morton-Kurve, eine verbreitete raumfüllende Kurve, bildet den n-dimensionalen Raum auf eine sortierte lineare Sequenz ab. Auf Koordinaten angewendet definiert der Morton-Code eine Z-förmige raumfüllende Kurve, die daher auch als Z-Kurve bekannt ist. Diese Kodierung stellt sicher, dass Punkte, die im physikalischen Raum nahe beieinander liegen, tendenziell ähnliche Morton-Codes aufweisen, eine Eigenschaft, die das Speicherlayout und den parallelen Datenzugriff erheblich begünstigt.
2.1 Erzeugung von Morton-Codes
Die Erzeugung von Morton-Codes beinhaltet im Wesentlichen eine Bit-Verschachtelung der gegebenen Koordinaten über jede Dimension.
Zur Veranschaulichung betrachten wir ein Quadtree-Gitter in einer zweidimensionalen Ebene mit einem maximalen Verfeinerungsgrad von maxLevel = 2. Der Wurzelknoten des Baums stellt den Bounding-Box des Gitters dar, während Blattknoten einzelnen Gitterzellen entsprechen. Jeder Zelle wird ein sechsstelliger Binärcode zugewiesen, der typischerweise auf der Schwerpunktposition der Zelle basiert. Die Gesamtanzahl der Bits im Morton-Code beträgt:
wobei numDim die räumliche Dimension des Gitters bezeichnet und maxLevel den maximalen Verfeinerungsgrad darstellt.
Der Bit-Code für jede Quadtree-Zelle kann durch ihren relativen Index im kartesischen Koordinatensystem angegeben werden. Der Morton-Code der roten Zelle in Abbildung 3 kann beispielsweise als (10,01,01) bezeichnet werden. Die Gittergrenze 00, die das anfängliche gröbste Gitter darstellt, wird vom Morton-Code ausgeschlossen. Der binäre Morton-Code kann bei Bedarf in Dezimal umgerechnet werden; die dezimale Sequenznummer der roten Zelle beträgt beispielsweise 37. Alle Zellen dieses Quadtree-Gitters können zu einem Baum angeordnet werden, wie in Abbildung 4 dargestellt, wobei die farbigen Zellen den zweidimensionalen Quadtree-Zellen in Abbildung 3 entsprechen.
Sobald alle Morton-Codes der Zellen erzeugt sind, ergibt das Durchlaufen von der unteren linken Zelle zur oberen rechten Zelle die räumliche Durchlaufsequenz, die durch die schwarze Kurve in Abbildung 5 dargestellt wird. Diese Kurve weist eine ausgeprägte Zickzack-Struktur auf, weshalb die Morton-Kurve auch als Z-Kurve bekannt ist. Es ist zu beobachten, dass Geschwisterzellen innerhalb des Quadtrees ebenfalls benachbarte Positionen entlang der Morton-Kurve einnehmen. Darüber hinaus gruppieren sich bei der dynamischen Verfeinerung des Quadtrees neu erzeugte Geschwisterzellen in der Nähe der Position ihrer Elternzelle auf der Morton-Kurve. Bei der Verfeinerung von Octrees im dreidimensionalen Raum weisen die Morton-Codes der Octree-Zellen analoge räumliche Eigenschaften auf.
2.2 Anzahl der Verfeinerungsstufen
Sobald der Morton-Code erzeugt wurde, kann die Verfeinerungsstufe jeder Zelle direkt aus dem Morton-Code abgeleitet werden.
Für einen Morton-Code der Dimension dim lautet der Algorithmus wie folgt: Gegeben sei ein Morton-Code als Array der Länge N, mortonKey, sowie ein Octree-/Quadtree-Netz als Sammlung von Morton-Codes.
Die rosa Zelle in Abbildung 3 hat beispielsweise den Morton-Code (11,00,00). Anfänglich wird level = N/dim = 3 gesetzt. Beginnend mit der ersten Schicht des Morton-Codes überspringt Code 11 (ungleich null) zur nächsten Schicht. Der Morton-Code der zweiten Schicht ist 00; das Invertieren des x-Bits von 00 ergibt 10. Die Überprüfung von (11,10,00) zeigt, dass dieser bereits im Quadtree vorhanden ist, was auf das Vorhandensein von Geschwisternachbarn auf Stufe 2 hindeutet. Beim Übergang zur dritten Schicht lautet der Morton-Code 00. Das Invertieren des x-Bits von 00 ergibt 10. Die Überprüfung ergibt, dass (11,00,10) nicht im Quadtree vorhanden ist. Somit gilt level = level - 1 = 2. Diese Zelle hat folglich zwei Verfeinerungsstufen.
2.3 Geometrische Informationen der Zellen
Aus dem Morton-Code sowie dem geometrischen Mittelpunkt und der Kantenlänge der Wurzelknotenzelle lassen sich die Kantenlänge, der geometrische Mittelpunkt und die Eckpunktpositionen der verfeinerten Zellen ermitteln.
2.4 Nachbarschaftsinformationen der Zellen
Die Bedeutung von Zell-Nachbarschaftsinformationen für die numerische Berechnung von PDEs ist offensichtlich. Die Speicherung und der Abruf von Nachbarschaftsinformationen beeinflussen die Gesamteffizienz von PDE-Solvern erheblich. Für Quadtree-/Octree-Zellen, die Morton-Codes verwenden, sind Nachbarschaftsinformationen inhärent im Morton-Code eingebettet und über einfache Bitoperationen zugänglich.
Nachbarn von Quadtree-/Octree-Zellen werden als Geschwisternachbarn und Nicht-Geschwisternachbarn kategorisiert. Geschwisternachbarn bezeichnen benachbarte Zellen, die mit der aktuellen Zelle eine gemeinsame Elternzelle teilen. Nicht-Geschwisternachbarn bezeichnen Zellen ohne Geschwisterbeziehung zur aktuellen Zelle.
2.4.1 Gleichrangige Nachbarn
Die Geschwisternachbarn der roten Zelle (10,01,01) sind beispielsweise die gelbe Zelle (10,01,00) und die orange Zelle (10,01,11). Die ersten vier Binärstellen (10,01) der Morton-Codes dieser drei Zellen sind identisch, was darauf hinweist, dass es sich um Geschwisterzellen handelt. Die fünfte Binärstelle der roten Zelle, 0, repräsentiert die x-Richtung, während die 1 der sechsten Stelle die y-Richtung bezeichnet. Um Nachbarn in x-Richtung zu finden, müssen lediglich die fünfte und sechste Binärstelle beibehalten und die 0 in eine 1 invertiert werden, wodurch der x-ausgerichtete Geschwisternachbar (10,01,11), die orange Zelle, gefunden wird.
Um den Nicht-Geschwisternachbar der roten Zelle, die grüne Zelle (00,11,11), zu finden, können Bitoperationen in beide Richtungen durchgeführt werden. Die Bestimmung des Nicht-Geschwisternachbars entlang der x-Achse für die rote Zelle (10,01,01) verläuft beispielsweise wie folgt:
Bestimmung der Bit-Flip-Schichtposition entlang einer bestimmten Achse. Der Morton-Code dieser Zelle auf der höchsten Verfeinerungsschicht ist 01, das heißt, das Binärbit in x-Richtung ist 0. Beim Verfolgen zur Elternschicht lautet der Binärcode 01, wobei das Binärbit in x-Richtung weiterhin 0 ist. Beim weiteren Verfolgen zur Großelternschicht ist die Binärzahl 01, wobei das Binärbit in x-Richtung zu 1 wechselt. Diese Schicht ist somit die Bit-Flip-Schicht. Das heißt, von links nach rechts ist das Binärbit in x-Richtung (1,0,0), und die erste Schicht ist die Bit-Flip-Schicht.
Invertieren des Binärbits auf der entsprechenden Bit-Flip-Schicht. Für die rote Zelle (10,01,01) wurde die Bit-Flip-Schicht in x-Richtung als erste Schicht bestimmt. Um den Nicht-Geschwisternachbar der roten Zelle zu bestimmen, invertieren wir den Morton-Code der roten Zelle in x-Richtung (1,0,0) bis zur ersten Schicht und erhalten (0,1,1). Der Morton-Code in y-Richtung (0,1,1) bleibt unverändert und ergibt (00,11,11), was genau der grünen Zelle entspricht.
2.4.2 Schichtübergreifende Nachbarn
Um Nachbarn mit unterschiedlichen Verfeinerungsstufen in einer gegebenen Richtung zu bestimmen, wird die folgende Methode angewendet, wobei der Nicht-Geschwisternachbar der rosa Zelle (11,00,00) in y-Richtung als Beispiel dient:
Analog zu Abschnitt 2.4.1 lautet der Morton-Code der rosa Zelle (11,00,00), wobei die Bit-Umkehrschicht als zweite Schicht bestätigt wird. Das Umkehren des y-Achsen-Morton-Codes (1,0) ergibt somit (0,1), während die x-Achse unverändert bleibt, was zum Morton-Code (10,01) führt.
Die Verfeinerungsstufe der Zelle bei (10,01) ist höher als die der aktuellen rosa Zelle. Daher müssen die letzten zwei Stellen auf der dritten Schicht wiederholt werden, um (10,01,01) zu erhalten, was der roten Zelle entspricht. Die rote Zelle ist einer der schichtübergreifenden Nachbarn der rosa Zelle. Um den anderen Nachbar zu finden, muss lediglich der x-Achsen-Geschwisternachbar der roten Zelle gefunden werden. Dieser wird durch Invertieren des x-Achsen-Bits in 01 erhalten und ergibt die orange Zelle (10,01,11).
Damit sind beide schichtübergreifenden y-Achsen-Nachbarn (10,01,11) und (10,01,01) der rosa Zelle vollständig bestimmt.
Vorteile der Morton-Kodierung
Datenkompression: Die Konstruktionsmethode des Morton-Codes ist verhältnismäßig einfach und konvertiert Koordinatenwerte, die mehrdimensionale Daten repräsentieren, in eine einzige Ganzzahl. Verschiedene geometrische und topologische Informationen über Gitterzellen lassen sich durch Bitoperationen auf dem Morton-Code leicht gewinnen, was die Größe der gespeicherten und übertragenen Daten erheblich reduziert.
Datenlokalität: Nach der Morton-Code-Sortierung entsprechen benachbarte Gitterzellen häufig physisch zusammenhängenden Positionen. Dies verbessert die Cache-Trefferrate und die Speicherbandbreite und ermöglicht damit eine bessere Nutzung der Parallelrechenkapazitäten moderner Prozessoren für komplexere Rechenaufgaben.
Recheneffizienz: Die Morton-Code-Sortierung reduziert redundante Berechnungen erheblich und verbessert dadurch die Rechengeschwindigkeit und die Gesamteffizienz.