Unterabschnitte

• Boolesches Geometriemodell (CSG)
• Oberflächendarstellung (BRep)
• Zelluläre Geometrien

5.1 Geometrie Repräsentationen

Zur Darstellung dreidimensionaler geometrischer Objekte in Computerprogrammen sind verschiedene Methoden gebräuchlich, die je nach Anwendungsbereich gewisse Vor- und Nachteile bieten [123,124,125,126]. Die drei am häufigsten verwendeten Darstellungsformen sind

• Boolesche Modelle (CSG=Constructive Solid Geometry),
• Oberflächendarstellung (BRep=Boundary Representation) und
• zelluläre Darstellungsformen (CD=Cellular Decomposition).

Boolesches Geometriemodell (CSG)

Diese Form der Geometrierepräsentation wird häufig in CAD Programmen zur Konstruktion mechanischer Teile verwendet. Die geometrischen Grundelemente sind Ebenen, die den Raum in zwei Hälften (Halbräume) teilen. Mittels logischer Verknüpfungsoperationen lassen sich damit beliebige durch ebene Flächen begrenzte Geometrien erstellen. Abgespeichert wird die Struktur in einem baumförmigen Graphen, dessen Blätter die Grundelemente darstellen und dessen innere Knoten entweder logische (UND, ODER, ...) oder geometrische (Translation, Rotation, ...) Operationen bedeuten. Beispielsweise lässt sich ein Quader als UND-Verknüpfung (Durchschnitt) von sechs Halbräumen darstellen (siehe auch Abb. 5.1).

Abbildung 5.1: Konstruktion einer CSG Geometrie: Ein Quader (B) wird als Durchschnitt (ds) von sechs Halbräumen gebildet, das (unendlich lange) dreieckige Prisma (C) aus drei Halbräumen. Mit der Operation ,,B ohne C`` wird ein Quader mit einem dreieckigen Loch (A) konstruiert.

Für Oberflächen quadratischer Ordnung kann man als Grundelemente zusätzlich zu den Halbräumen noch die Kugel, den (unendlich langen) Zylinder und den Torus verwenden. Im Prinzip können auch andere Oberflächen wie z.B. Splineflächen als Grundelement verwendet werden. Eine notwendige Bedingung ist allerdings, dass die Flächen entweder geschlossen sind oder unendliche Ausdehnung haben, sodass der Raum eindeutig in ein inneres und ein äußeres Gebiet aufgeteilt wird.

Das Erzeugen der Kanten und Eckpunkte der Geometrie ist mit großem Rechenaufwand verbunden, da hiezu alle Grundelemente untereinander verschnitten werden müssen. Hingegen ist es relativ einfach festzustellen, ob ein (beliebiger) Punkt innerhalb oder außerhalb der Geometrie liegt (Punktsuche). Dazu wird für jedes Grundelement getestet, ob der Punkt innerhalb oder außerhalb liegt. Die Ergebnisse der Einzeltests werden dann anhand des Graphen logisch verknüpft.

Oberflächendarstellung (BRep)

Bei der Oberflächendarstellung (Boundary Representation) bilden die Eckpunkte, die durch ihre Koordinaten gegeben sind, die Basis der Geometrie--im Gegensatz zu CSG, wo die topografische Information durch Ebenengleichungen festgelegt ist. Ausgehend von den Punkten ist der Aufbau streng hierarchisch (siehe auch Abb. 5.2). So ist eine Kante durch zwei Eckpunkte definiert, Flächen sind durch die Kanten, die den Rand bilden, gegeben. Zu beachten ist dabei, dass Flächen mit Löchern nicht nur einen äußeren, sondern auch einen oder mehrere innere Ränder haben. Körper (Solids) sind durch ihre Randflächen festgelegt. Sie haben genau einen äußeren Rand, können aber auch innere Ränder besitzen (Hohlräume oder Einschlüsse).

Abbildung: Streng hierarchischer Geometrieaufbau der Oberflächenrepräsentation: Körper werden durch ihre Randflächen festgelegt, die wiederum sind durch ihre Randlinien gegeben, welche durch jeweils zwei Punkte definiert sind.

Während es bei CSG-Geometrien keine Probleme mit Datenkonsistenz gibt (jede beliebige darstellbare Geometrie ist eine gültige Geometrie), muss bei der Oberflächendarstellung streng auf topologische und topografische Konsistenz geachtet werden. Um topologische Konsistenz zu erreichen, muss garantiert sein, dass

• Linien mit genau zwei Punkten verknüpft sind,
• Flächen zu nicht mehr als zwei Solids gehören,
• die Berandung(en) von Flächen und Solids geschlossen ist (sind), und
• Solids und Flächen genau einen äußeren Rand haben.

Für topografische Konsistenz wird gefordert, dass

• die Berandung von Flächen in einer Ebene liegt,
• keine Verschneidungen auftreten,
• Solids, die sich in einem Punkt, Linie oder Fläche berühren, auch im Datenformat diesen Punkt, Linie oder Fläche gemeinsam haben,
• wenn mehr als 3 (bzw.. 2) Ebenen im Datenformat einen Punkt (eine Linie) gemeinsam haben, sie sich auch tatsächlich in diesem Punkt (dieser Linie) schneiden.

Manche Operationen können daher nur unter bestimmten Voraussetzungen oder in Kombination mit anderen ,,passenden`` Operationen durchgeführt werden. So darf beispielsweise eine Fläche, die zwei Solids trennt, nicht gelöscht werden, außer man verbindet gleichzeitig die Solids miteinander. Aber auch bei an sich korrekten geometrischen Operationen muss immer darauf geachtet werden, dass nicht etwa durch numerische Ungenauigkeiten Inkonsistenzen entstehen. Umgehen kann man dieses Problem durch Verwendung einer exakten rationalen Arithmetik. Dabei handelt man sich aber wieder den Nachteil ein, dass einerseits die Ausgangsdaten selten in einem rationalen Format vorliegen und es dadurch bei der Konvertierung zu topologischen Inkonsistenzen kommen kann und andererseits, dass gewisse geometrische Operationen dadurch unmöglich gemacht werden (z.B. Rotation).

Zelluläre Geometrien

Bei den zellulären Darstellungsformen wird die Geometrie aus einfachen dreidimensionalen Grundelementen (z.B. Tetraeder oder Würfel) zusammengesetzt. Dabei kann man zwischen strukturierten und unstrukturierten Gittern unterscheiden.

Bei unstrukturierten Gittern

ist weder die Anordnung der Knotenpunkte noch der Gitterelemente einer bestimmten Regelmäßigkeit unterworfen (siehe Abb. 5.3).

Abbildung 5.3: Ein unstrukturiertes Tetraedergitter

Abgespeichert wird ein unstrukturiertes Gitter durch eine Punktliste und eine Elementliste. Die Punkte sind durch ihre Koordinaten gegeben, die Elemente referenzieren ihre Knoten durch Indizes auf die Punktliste. Bei Gittern mit verschiedenen Grundelementen muss zusätzlich noch der jeweilige Elementtyp angegeben werden.

Strukturierte Gitter

sind topologisch regelmäßige Hexaedergitter. Jeder Gitterpunkt und jede Zelle kann durch ein Indextripel $(i,j,k)$ eindeutig identifiziert werden. Als Beispiel seien die Gitter der Finiten Differenzen Methode erwähnt (siehe auch Abb. 5.4).

Abbildung 5.4: Ein strukturiertes Gitter

Bei strukturierten Gittern brauchen die Elemente nicht explizit abgespeichert werden, da ihre Eckpunkte direkt in der Punktliste mit den drei Richtungsindizes gefunden werden können.

Ortho-Produkt-Gitter

sind strukturierte Gitter bei denen nicht nur die Topologie der Zellen sondern auch die Koordinaten der Gitterknoten einer Regelmäßigkeit unterliegen. Jede Gitterzelle sowie das Gesamtgitter hat Parallelogramm- (2D) bzw. Spatform (3D). Jeder der drei Gitterindizes unterteilt eine Hauptachse des Gitters in sogenannte Ticks. Fallen die Hauptachsen mit den Achsen des Koordinatensystems zusammen, spricht man von einem rectilinearen Gitter (Abb. 5.5a).

Bei der Voxeldarstellung^5.1,

oder auch kartesisches Gitter genannt (Abb. 5.5b), gilt zusätzlich, dass alle Zellen gleiche Abmessungen haben. Ein Voxelgitter ist durch Angabe des Koordinatenursprungs, der Breite/Höhe/Tiefe einer Zelle sowie der Anzahl der Zellen in $x$, $y$, und $z$-Richtung vollständig definiert.

Abbildung 5.5: Rectilineares Gitter (a) und Voxeldarstellung (b) als
Spezialfälle strukturierter Gitter

Generell ist man mit Ortho-Produkt-Gittern sehr stark in der Darstellung allgemeiner Geometrien eingeschränkt. Für nicht hexaederförmige Strukturen muss man für jede Gitterzelle eine Boolesche Variable abspeichern, die angibt ob die jeweilige Zelle zur Geometrie gehört oder nicht. Kommen mehrere Materialien vor, so verwendet man stattdessen eine Indexvariable, die das entsprechende Material anzeigt (oder Vakuum, falls die Zelle nicht zur Geometrie gehört).

Flächen, die nicht zu den Gitterachsen parallel sind, können lediglich stufenförmig angenähert werden. Damit durch die Diskretisierung nicht kleine geometrische Details verloren gehen, muss man die Gitterdichte ausreichend hoch wählen (Abb. 5.6).

Abbildung 5.6: Geometrie in Voxeldarstellung: Flächen, die nicht zu den Koordinatenachsen parallel sind müssen stufenförmig angenähert werden.

Bei der Voxeldarstellung kann man zur Reduktion des Speicherbedarfs die Tatsache, dass benachbarte Zellen mit hoher Wahrscheinlichkeit aus dem selben Material sind, ausnutzen, um eine komprimierte Darstellung zu erzielen z.B. mittels eines Octree oder mittels Lauflängencodierung.

Ähnlich wie beim CSG-Modell ist jede darstellbare Voxel-Geometrie auch automatisch gültig, was sich natürlich positiv auf die Robustheit voxelbasierter Algorithmen auswirkt.

Fußnoten

... Voxeldarstellung^5.1

Voxel$=$Volume Element, in Analogie zu Pixel.