Gittergenerierungsmethoden

zur Finite Elemente

Simulation aus Bilddaten

Bachelorarbeit

zur Erlangung des akademischen Grades

Bachelor of Science

Westfälische Wilhelms-Universität MünsterFachbereich Mathematik und Informatik

Institut für Numerische und Angewandte Mathematik

Betreuung:

Prof. Dr. Martin Burger

Dr. Frank Wübbeling

Eingereicht von:

Matthias Redecker

Münster, Oktober 2010

Zusammenfassung

In dieser Arbeit werden wir uns einige Grundlagen zur Generierung von Gitternaneignen. Mit Gitter meinen wir Datenpunkte die wir auf eine bestimmte Weisemiteinander verknüpfen. Zuerst gehen wir dabei kurz auf die Gewinnung vonBilddaten ein und betrachten danach auf welche Weise wir auf auf den Bild-daten Gitterstrukturen erstellen können, die die Eigenschaften des vernetztenObjektes möglichst gut, das heiÿt möglichst schnell, genau und einem möglichstwenig fehleranfälligen Algorithmus, darstellen. Dazu werden wir uns verschiede-ne Problemstellungen zuerst im zwei- und dann im drei-dimensionalen ansehen.

2

Eidesstattliche Erklärung

Hiermit versichere ich,Matthias Redecker, dass ich die vorliegende Arbeit selbst-ständig verfasst und keine anderen als die angegebenen Quellen und Hilfsmittelverwendet habe. Gedanklich, inhaltlich oder wörtlich übernommenes habe ichdurch Angabe von Herkunft und Text oder Anmerkung belegt bzw. kenntlichgemacht. Dies gilt in gleicher Weise für Bilder, Tabellen, Zeichnungen und Skiz-zen, die nicht von mir selbst erstellt wurden.

Münster, 22. Oktober 2010

3

Inhaltsverzeichnis

1 Einleitung 5

2 Segmentierung 7

2.1 Level-Set Methode . . . . . . . . . . . . . . . . . . . . . . . . . . 82.2 Marching Cubes . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3 Grundlagen zur Netzgenerierung 11

3.1 Verschiedene Netzgenerierungsmethoden . . . . . . . . . . . . . . 113.2 Basisfunktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123.3 Mesh Size Function . . . . . . . . . . . . . . . . . . . . . . . . . . 133.4 Delaunay-Triangulierung . . . . . . . . . . . . . . . . . . . . . . . 15

4 Nachträgliche Netztqualitätsverbesserungen 17

4.1 Laplacian smoothing . . . . . . . . . . . . . . . . . . . . . . . . . 184.2 Verschiedene Gitterglättungen in 3 Dimensionen . . . . . . . . . 19

5 Spezielle 3D Gitterverfahren 25

5.1 BCC Gitter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255.2 CFE Gitter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275.3 Diskussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

6 Beispiele 35

6.1 Verschiedene Triangulationen . . . . . . . . . . . . . . . . . . . . 356.2 Finite Elemente Simulation . . . . . . . . . . . . . . . . . . . . . 37

7 Fazit 40

4

1 Einleitung

Wir möchten uns in dieser Arbeit mit der Generierung von Gittern aus Bild-daten beschäftigen, da diese der Grundbaustein für jede Finite Elemente An-wengung ist. Wofür brauchen wir wiederum Finite Elemente? Wir betrachtenzunächst verschiedene Bilddaten. Mit Bilddaten können die gespeicherten Da-ten eines CT-Bildes, oder auch die Daten einer 3D Ansicht eines Stahlträgersgemeint sein. Um diese Bilder als Daten speichern zu können zerlegt man siein eine endliche(nite) Anzahl von Elementen. Indem man auf den ElementenPartielle Dierentialgleichungen deniert versucht man nun reale Geschehnissedarzustellen. Die Anwendung der Finite Elemente Methode entstand zunächstaus dem Ingenieurwesen, wo man zum Beispiel Stahlträgerkonstruktionen aufihre Stabilität testet, indem man das Gerüst in viele Elemente aufteilt und dannDruck aus verschiedenen Richtungen simuliert. Auf diese Weise möchte man dieSchwachstellen solcher Konstruktionen herausnden, ohne sie bauen zu müssen.

In den letzten Jahren hat die FE Simulation auch in der Medizin immer mehran Bedeutung gewonnen. Stahlträgerkonstruktionen kann man beispielsweiseauf ähnliche Weise wie das Knochengerüst testen. Dies kann zur zum besserenVerständnis von Osteoporose dienen, sowie zur besseren Behandlung. Durch dieSimulationen kann man besser auf die Knochenchwächen reagieren, denn durchdie Nachbildung der Knochenstrukturen mit FE-Simulationen kann man genauerkennen in welchem Maÿe und bei welchen Bewegungen sich die Krankheitbesonders bemerkbar macht. Die enorme Verbesserung künstlicher Gelenke inden letzten Jahrzenten ist ebenfalls zum Teil auf die Simulation mittels FE-Methoden zurück zu führen.

FE helfen uns also Dinge zu verstehen oder Dinge mittels Programmierungzu testen, bei denen ein realer Versuchsaufbau nur schwierig zu realisieren wäre.

Um einen Gegenstand von Interesse (den wir später häug einfach mit Mbezeichnen) in Elemente zu zerlegen, konstruieren wir eine Gitterstruktur aufdiesem. Diese Struktur soll die topologischen Eigenschaften des Gegenstandesmöglichst gut beschreiben. Da es aufgrund der endlichen Speicherkapazität einesRechners unmöglich ist das ganze Objekt, wie es in der Realität existiert, zuspeichern, legen wir Punkte durch ein das Objekt umfassende Gebiet, in denenwir jeweils ihre Position und ihre Verknüpfung zu den umliegenden Punktenund andere Dinge, wie zum Beispiel ihren Abstand zum Rand, speichern. Wirerhalten mittels der verknüpften Punkte eine Annäherung an das Objekt. Daraufwerden wir später noch im Speziellen eingehen. Diese Punkte werden wir auchhäuger Knoten oder Knotenpunkte nennen.Ein Element besteht dann aus einer bestimmten Zahl von Knoten, die von derzugrundeliegenden Gitterstruktur abhängt, die miteinander verbunden sind undzwischen denen und ihren Verbindungen kein weiterer Knoten mehr liegt.

Eine Zerlegung die bestens bekannt ist, ist die eines Bildes in Pixel. Hierwird das Gesamte Gebiet, in gleichgroÿe Quadrate aufgeteilt und die Farbe jedes

5

Pixels abgespeichert. Eine solche Zerlegung ist für FE-Simulationen jedoch meistungeeignet, denn der Speicherbedarf ist sehr groÿ, da wir keine strukturellenEigenschaften des Objektes ausnutzen und die Pixel überall gleich groÿ sindegal ob das Objekt an einer gegebenen Stelle grobe oder feine Konturen besitzt.Wir werden darauf in den kommenden Kapiteln noch genauer eingehen.

Abbildung: 1.1; Ein Beispiel für eine Vernetzung. Die Triangulierung eines Krei-ses.Quelle [13].

In Kapitel zwei werden wir uns zunächst damit beschäftigen wie wir eineFunktion auf einem bestimmten Gebiet Ω erhalten, die den Rand unseres Ob-jektes M beschreibt. Danach werden wir in Kapitel drei sehen, wie wir M mitdem Wissen um eine solche Funktion in ein Gitter einbetten, und was für ver-schiedene Möglichkeiten uns dabei zu Verfügung stehen. Am Ende von Kapiteldrei beschäftigen wir uns mit der Delaunay Triangulierung. Diese Triangulie-rung wird sehr häug verwendet und weist gute Eigenschaften auf.Da Triangulierungen teilweise schlecht geformte Elemente bilden, gehen wir inKapitel vier darauf ein wie man solche Elemente nachträglich verbessern oderaus dem Gitter entfernen kann.

In Kapitel fünf wenden wir uns zwei speziellen Gitterkonstruktionen zurAnwendung auf 3D Objekte zu. Nach dem wir uns mit diesen Gittern genauerbefasst haben, betrachten wir in Kapitel sechs noch einmal ein paar Beispiele.

6

2 Segmentierung

Das Ziel dieses Kapitels ist es nicht Segmentierung als solche zu erklären, son-dern wir möchten hier darauf eingehen, wie wir für unsere Zwecke die Ränderder von uns betrachteten Gebiete berechnen.

Wenn wir ein Gitter in einem bestimmten Gebiet Ω konstruieren, ist eswichtig zu wissen wo in dem Gebiet die Ränder des von uns betrachtetem Objektliegen. Denn genau diese Ränder möchten wir schlieÿlich mit unserem Gitterapproximieren.Wir möchten mit Hilfe einer signierten Distanzfunktion Φ den Rand unseresObjektes bestimmen.

Da wir in euklidischen Räumen Rn(meist n = 2 oder n = 3) arbeiten, könnenwir Φ über die euklidische Abstandsmetrik unseres Raumes denieren.

Sei x ∈ Rn und A ⊂ Rn.Sei d die euklidische Metrik im Rn, dann denieren wir den Abstand von x zuA als:

D(x,A) = miny∈A

d(x, y).

Auf dieser Basis denieren wir für M ⊂ Ω ⊂ Rn,∀x ∈ Ω :

Φ(x) =

D(x, ∂M ) x /∈M

−D(x, ∂M ) x ∈M .

Aufgrund der Denition von D gibt uns −∇D(x, y) den Vektor an der direktvon x nach y zeigt. Für einen Vektor der genau in der Mitte zwischen x undy liegt, gibt D einen halb so groÿen Wert an. Somit gilt für D in euklidischenRäumen die Eikonalgleichung.

‖∇Φ(x)‖ = 1 (1)

Dies gilt leider nicht für Punkte die zu zwei Randpunkten die gleiche Ent-fernung haben, also den Punkten auf der Mittelachse. Die Menge dieser Punkteist jedoch eine Nullmenge, sodass wir sie vernachlässigen können.Weitere Eigenschaften sind, dass D einen Knick auf dem Rand des Objekteshat. Hier hat D ein lokales Minimum. Unsere signierte Distanzfunktion hinge-gen weist einen solchen Knick nicht auf und ist deshalb dierenzierbar.

Signierte Distanzfunktionen sind eine Teilmenge der impliziten Funktionen.Bei einer impliziten Funktion ist die Oberäche eines Objektes implizit durchdie Nullstellen der Funktion gegeben, z.b. die Nullstellen von Φ(x) = x2 − 1,die Punkte -1,1 geben den Rand an [10]. Weitere Ausführungen über impliziteFunktionen kann man in Kapitel eins von [10] nachlesen.Bei numerischen Berechnungen haben wir nun dass Problem, dass wir nicht

7

unendlich viele Punkte speichern können, um das Objekt sehr realitätsnah ab-zubilden. Das Gitter, dass wir in unserem Gebiet des Rn erzeugen, erfasst nureine endliche Anzahl von Punkten des reellen Gebietes. Deswegen erhalten wirnur Annäherungen an unsere Randpunkte.

2.1 Level-Set Methode

Wir möchten nun eine Funktion Φ bestimmen, mit der wir in jedem Kno-ten unseres Gitter eintragen können, ob dieser Punkt innerhalb(Φ <0) oderauÿerhalb(Φ >0) unseres Objektes liegt, oder genau auf dem Rand(Φ = 0). Mitder level-set Methode versucht man Objekte und falls gegeben, deren Bewe-gung zu verfolgen. Wir machen die Level-set Funktion Φ zu einer von der Zeitabhängigen Funktion und ermitteln den Rand des Objektes, indem wir unsereFunktion sich entlang ihrer Normalenrichtung ausbreiten lassen.Die Level-set Funktion ist dann eine Funktion Φ(t, ·) von Ω nach R und Lösungder Hamilton-Jacobi Gleichung:

∂tΦ− f(t,x)|∇Φ| = 0 (2)

Die Funktion f beschreibt die Bewegung der Objektoberäche.

In der Regel ist unsere Funktion nicht analytisch deniert [2]. Deswegen lösenwir die Hamilton-Jacobi Gleichung (Gleichung (2)) numerisch, mittels verschie-dener (iterativer) Lösungsverfahren, die man z.B. in [10] Kapitel 2.5 nachlesenkann.

Wenn wir fordern, das unsere level-set Funktion auch eine signierte Distanz-funktion ist, so gilt wieder die Eikonalgleichung für Φ. Erfüllt Φ die gefordertenGleichungen, so gelten folgende Eigenschaften:Der Abstand eines Knoten x zum Rand ist:

|Φ(x)|, für alle x ∈ Ω,

und der Einheitsvektor:

N =∇Φ

||∇Φ||= ∇Φ

Es ist durchaus möglich, dass unsere so erhaltene signierte Distanzfunktion,eine wesentlich höhere Auösung aufweist, als wir zum Generieren eines Gittersbenötigen. Ist das der Fall, modellieren wir die Geschwindigkeit mit Hilfe derKrümmung des Randes, um hochfrequente Gitter zu glätten.Die Krümmung ist deniert durch:

κ = ∇N = ∇∇Φ/||∇Φ|| = ∇∇Φ = ∆Φ

Dann können wir die Kräfte wie folgt beschreiben:

f = −bκN, für b > 0.

8

Somit lautet die zu lösende level-set Gleichung nach der Umformung:

Ψt = bκ‖∇Ψ‖ (3)

Wir nennen die neue Distanzfunktion hier Ψ, da sie, durch den Ansatz, f mittelsder Hauptkrümmung zu bestimmen, im Gegensatz zu Φ keine signierte Distanz-funktion mehr ist.Wir berechnen Ψ nun durch die iterative Lösung der Gleichung:

Ψτ + S(Ψ0)(‖‖∇Ψ‖‖ − 1) = 0 (4)

Weiterführende Erläuterungen zu den Gleichungen (3) und (4) ndet man auchin [2].

Mithilfe dieses Krümmungsansatzes können wir auch erkennen, wo der Randeine besonders hohe Auösung zwecks einer guten Approximation benötigt. Des-weiteren sehen wir, wenn wir die Werte von Ψ in die Knotenpunkte eines Gitterseintragen, welche Zellen vom Rand geschnitten werden. Nämlich die Zellen, diesowohl Knoten im Objektinneren(Ω−) als auch im Äuÿeren(Ω+) besitzen. Beidiesen Zellen sind Verfeinerungen des Gitters besonders wichtig, falls der Randdes Objektes sehr nah an einer Wand der Zelle liegt, um Rundungsfehler mög-lichst zu vermeiden.

Ein paar Abschnitte weiter, werden wir zum Generieren einer mesh size func-tion diese Ansätze wieder aufgreifen. Doch bevor wir dazu kommen, möchten wirerst einmal, noch eine besondere Segmentierungsmethode betrachten, und unsim nächsten Kapitel überlegen, in was für ein Gitter wir die durch die level-setFunktion gewonnenen Erkenntnisse, einbetten.

2.2 Marching Cubes

Eine weitere Möglichkeit ∂M zu bestimmen ist die Modellierung als Voxelda-tenmengen. Voxel ist die Abkürzung für volumetric pixel [9]. Diese volumetricpixel werden als Datenpunkte in regelmäÿigen Abständen angeordnet.In jedem Punkt wird, je nach Verarbeitungszweck, zum Beispiel ein Farbwertoder eine Dichte gespeichert. Der Marching Cubes Algorithmus [5] verarbeitetdiese Bildpunkte zu einem strukturiertem Würfelgitter. Sei D(i,j,k) der Dichte-wert des Voxelgitters an der Stelle (i,j,k). Vor der Verarbeitung der Daten mussnoch ein Schwellenwert t eingeben werden. Ist D(i,j,k)≥ t so liegt der Punktim Objekt, bei D(i,j,k) 6= t auÿerhalb. Der MC Algorithmus durchschreitet dasVoxelgitter und bildet aus jeweils acht, einen möglichst kleinen Würfel bilden-den, Punkten eine Zelle des Gitters. Dabei kann nun jedem Voxel der Wert0(D(i,j,k)6= t) oder 1(D(i,j,k)≥ t) zugeordnet werden. Legt man die 8 Werte derVoxelpunkte hintereinander so erhält man eine binäre Zahl. Als Dezimalzahl

9

Abbildung 2.1: Eine Nachschlagtabelle der 15 toplogisch unterschiedlichen Fi-guren für den MC Algorithmus.Quelle: [5].

erhalten wir eine Zahl m ∈ 0, . . . , 255. Aufgrund dieser Zahl wählt der Algo-rithmus eine Konguration aus einer vorgefertigten Nachschlag Tabelle aus. Imwesentlichen gibt es 15 verschiedene Fälle.

Für jeden Würfel führt der MC Algorithmus folgende Schritte aus: (1) Berechne Index des Würfels anhand Dichtewerte(2) Erfrage mittels Index Liste der geschnittenen Würfelkanten(3) Berechne Meshknoten mittels linearer Interpolation(4) Approximiere die Normalen an Würfelknoten(5) Interpoliere die Normalen der Meshknoten(6) Ausgabe der gefundenen Knoten und der Normalen [5].

Ein Problem, das bei dieser Art der Objektrandberechnung auftritt ist, dasses sein kann, dass zwei nebeneinanderliegende Würfel keine angrenzenden Kan-ten aufweisen. Es gibt verschiedene Ansätze dem entgegen zu wirken. Eine istdie die Kanten mit Dreiecken zu glätten, oder das ganze System durch Tetraederstatt Würfeln zu konstruieren, oder andere Glättungsverfahren in den Algorith-mus einzusetzen.

Weitere Nachteile des MC Algorithmus sind, dass er erstens kein bereitsvorhandenes Wissen über die Struktur des betrachteten Objektes nutzt, beisehr hoher Polygonzahl verliert er an Ezienz, desweiteren geht er von glattenOberächen aus, wodurch leicht Artefakte an spitzen Kanten entstehen. DerAlgorithmus ist in seiner Rohform ungeeignet für irreguläre Gitter. IrreguläreGitter sind Gitter in denen nicht alle Zellen gleich groÿ sind. Wir möchten es andieser Stelle aber erstmal dabei belassen, es gibt noch viele andere als die hierbeschriebenen Segmentierungsmethoden, und viele die auf den hier vorgestelltenaufbauen.

Wir beschäftigen uns als nächstes etwas intensiver mit den verschiedenenGitterformen.

10

3 Grundlagen zur Netzgenerierung

3.1 Verschiedene Netzgenerierungsmethoden

Es gibt verschiedene Möglichkeiten ein Gitter zu konstruieren. Schlieÿlich kannman prinzipiell jede willkürliche Verknüpfung von Punkten als Gitter bezeichen,man kann sich aber vorstellen das nicht jedes Gitter für numerische Berechnun-gen hilfreich ist. Um Gitter zu konstruieren, die implementierbar sind, müssenwir nach einem bestimmten Konzept vorgehen.Eine mögliche Vorgehensweise ist ein kartesisches Gitter zu konstruieren. Es hateine äuÿerst simple Struktur. Es besteht im ganzen Gebiet aus gleichgroÿen Zel-len(z.B. Quadraten im 2-dimensionalem Raum). Durch die einfache Struktur n-den wir für jeden Knoten x, nach wenigen Berechnungsschritten, die zugehörigenZellen. Ebenfalls können wir in ein Kartesisches Gitter leicht level-set-Methodenund fast-marching-Methoden implementieren. Bei dieser Methode nähern wirden Rand in den entsprechenden Gitterzellen durch bilineare Interpolation an.Daraus, dass wir die Zellen einheitlich gewählt haben, ergibt sich jedoch auch einProblem. Benötigen wir in einer Zelle des Gitters eine Verfeinerung, so müssenwir diese auf das gesamte Gitter übertragen. Die Anzahl der Knoten wächst alsomit jedem Verfeinerungsschritt quadratisch in 2D, bzw. kubisch in 3D an. DieseEigenschaft sorgt dafür, dass das Kartesische Gitter eine Menge Speicherplatzbeansprucht, sobald wir unser Gitter verfeinern.

Um den Speicherplatzbedarf zu reduzieren ist eine Alternative, ein einheit-liches Gitter mit einer octree Struktur zu konstruieren. Octree heiÿt, dass jedeZelle die wir verfeinern in acht gleich groÿe Zellen, der Stuktur des Gitters ent-sprechend, geteilt wird(im 3-dimensionalen Raum, in 2D wäre es quadtree). DerStruktur des Gitters entsprechend bedeutet, dass die acht verfeinerten Zellenwieder die gleiche Form haben, wie die gröbere Zelle.Dieses Gitter kann, wie das kartesische Gitter, aus Quadraten, bzw. Würfelnbestehen, innerhalb denen wir wie zuvor bilineare bzw. trilineare Interpolationdurchgeführt haben. Wir passen nun das Gitter entsprechend der benötigtenGenauigkeit an, das heiÿt am Rand teilen wir die Zellen so häug wie nötig undinnerhalb und auÿerhalb des Objektes nehmen wir gröÿtmögliche Zellen um denRechenaufwand zu reduzieren. Siehe Abbildung 3.1.Dadurch wird der Rechenaufwand asymptotisch proportional zur Länge desRandes [12]. Welchen Verfeinerungsgrad wir an welcher Stelle unseres Gitterbenötigen können wir mit Hilfe einer mesh-size function bestimmen. Wie maneine solche Funktion bestimmt besprechen wir zwei Abschnitte weiter.

Eine weitere Möglichkeit, unsere Punktmenge zu vernetzen, ist ein unstruk-turiertes Gitter zu verwenden. Auf diese Weise können wir direkt da, wo wir siebenötigen kleine Zellen erstellen, und sonst möglichst groÿe Zellen verwenden.Der Rechenaufwand ist ähnlich wie oben, siehe [12]. Ein zusätzlicher Vorteil ist,dass wir die Gitterzellen, so einbetten können, das der Rand des Objektes genauauf den Rändern der Zellen liegt.

11

Benutzen wir, wie in Abbildung 3.1, unstrukturierte Dreiecke, so reduziertsich der Berechnungsaufwand weiter, da wir in der Situation linear interpolie-ren, andererseits verlieren wir dadurch im Gegensatz zur bilinearen Interpola-tion auch an Genauigkeit. Dies erkennt man schnell, wenn man den eckigenRand der unstrukturierten Triangulierung mit den Rändern der oberen beidenVernetzungen vergleicht.

Abbildung: 3.1: Die drei verschiedenen Gitterstrukturen, angewandt auf dasselbe Objekt.Quelle: [12].

3.2 Basisfunktionen

Wie kommt diese Interpolation zustande? Wir haben bereits mehrfach die Da-tenspeicherung in Knotenpunkten erwähnt. Hier speichern wir die Basisfunktio-

12

nen unseres Netzes. Die Topologie des Netzes wird mithilfe dieser Funkionen imNetz gespeichert. Dies reduziert den Speicheraufwand für unstrukturierte Netze,denn hier verwenden wir wie schon erwähnt stückweise lineare Interpolation. Dasheiÿt wir speichern in den Knoten des Gitters, einfache lineare Basisfunktionen,um die jeweiligen direkten Nachbarknoten zu identizieren.

In strukurierten Gittern liegt der Rand des betrachteten Objekts in derRegel nicht auf den Rändern der Zellen oder schneidet Knotenpunkte, wie manin Abbildung 3.1 gut sieht. Da die Gitter strukturiert sind wissen wir wo diedirekten Nachbarn liegen, wir müssen jedoch kompliziertere Basisfunktionenwählen, um den Rand des Objektes zu interpolieren.

3.3 Mesh Size Function

Unabhängig davon, ob wir eine octree Struktur oder unstrukturierte Vernetzun-gen zur Gitterkonstruktion verwenden, ist es für uns von Interesse, an welchenStellen wir unser Gitter sehr fein wählen sollten, um unser Objekt möglichstgut zu approximieren, beziehungsweise wo sehr grob um möglichst viel Spei-cherplatz zu sparen.Dazu wollen wir im folgenden eine Funktion für unseren Raum denieren, dieuns genau dies angibt. Die einzelnen Formulierungen der Nebenbedingungenndet man in Referenz [12]. Um eine solche Funktion sinngemäÿ zu denieren,überlegen wir uns in welchem Umgebungen unser Gitter eine feine Zellstrukturbenötigt, und welchen Nebenbedingungen unsere Funktion genügen soll. Diemesh size function gibt uns dann, für jeden Punkt in M , den optimalen Ab-stand zum nächsten Knoten an.

Oensichtlich braucht man überall dort ein feines Gitter, wo die Krümmungdes Randes besonders stark ist. Wir möchten dies als Nebenbedingung für dienoch zu erzeugende mesh-size function h formulieren. Dazu sei κ(x) die Krüm-mung des Randes an der Stelle x∈ Ω gegeben durch:

κ = ∇(∇Φ

‖∇Φ‖)

Der Abstand von einem Knoten x zu einem anderen Knoten y soll durch hangegeben werden. Deswegen überlegen wir uns, dass h antiproportional zu derKrümmung κ sein muss, damit sich die Abstände der Knoten bei zunehmenderKrümmung verringern. Wir erhalten als Nebenbedinung:

Curvature Adaption: h(x) ≤

hcurv(x) = 1

|κ(x)| für Φ(x) = 0

∞ sonst(5)

13

Wir haben nun eine Nebenbedingung bezüglich der Randkrümmung für hformuliert.

Eine weitere Bedingung die wir stellen ist, dass h an die lokalen Gegebenhei-ten des Objektes angepasst ist. Denn auch wenn zum Beispiel die Krümmungdes Objektrandes in x gering ist, so kann das Objekt selbst an der Stelle schmalsein. Da man sich leicht vorstellen kann, dass man für ein kleineres Objekt, klei-nere Zellen konstruiert, ist es naheliegend an schmaleren Stellen kleinere Zellenzu fordern, also den Abstand von einem zum anderen Knoten zu verkleinern.Bleibt noch zu klären was schmal heiÿt. Eine Möglichkeit die lokale Gröÿe desObjektes zu bestimmen, ist die Mittelachse des Objektes zu bestimmen.Die Mittelachse ist die Menge der Punkte innerhalb des Objekts, die zu min-destens zwei Stellen des Randes den gleichen Abstand aufweisen.Wir bestimmen für jeden Punkt der Mittelachse den Abstand zum Rand. Da-durch erhalten wir eine Funktion, die uns für Punkte innerhalb des Objektes(woanders wäre es auch nicht sinnvoll), eine lokale Gröÿe oder auch local featuresize des Objekts angibt. Diese Funktion teilen wir nun noch durch die Hälf-te der Anzahl an Elementen in schmalen Regionen des Objekts und erhaltenNebenbedingung:

Local Feature Size: h(x) ≤

hlfs(x) für Φ(x) ≤ 0

∞ sonst(6)

Zusätzlich möchte man später eventuell gewisse Regionen des Objekts beson-ders genau dargestellt haben. Für den Fall denieren wir folgende Bedingung:

Non-geometric Adaption: h(x) ≤

hext für Φ(x) > 0

∞ sonst(7)

Um die Qualität des Netzes zu verbessern, begrenzen wir den Gröÿenun-terschied von zwei benachbarten Zellen. Dass dadurch die Qualität des Gittersverbessert wird, ist wird deutlich, wenn man einmal ein groÿes gleichseitigesDreieck zeichnet und an einer Kante ein wesentlich kleineres dazu fügt. In demFall ist es nämlich unmöglich, dass das kleine Dreieck keine äuÿerst stumpfenund spitze Winkel hat. Wir erreichen die gewünschte Beschränkung der Unter-schiede zweier Zellen, indem wir dem Gradienten von h durch eine Funktion gnach oben beschränken. Dabei kann g entweder konstant sein, oder, falls derBenutzer in unterschiedlichen Regionen unterschiedliche Anforderungen an dieQualität des Netzes hat, abhängig von x ∈ Ω.

Gradient Limiting: |∇h(x)| ≤ g(x) (8)

14

Die optimalen Zellgröÿen (das heiÿt so groÿ wie möglich, um Speicherplatz zusparen, und so klein wie nötig, um die gewünschte Genauigkeit zu erzielen) erhältman nun, indem man h über alle Nebenbedingungen, also den Gleichungen(5)-(8), maximiert.Wir sind somit in der Lage, in einen Gitter erzeugenden Algorithmus, eine Funk-tion zu implementieren, die dem Algorithmus optimale Gröÿen für die Zellenangibt. Wie so ein Algorithmus aussehen kann, zeigt der nächste Abschnitt.

3.4 Delaunay-Triangulierung

Ein häug angewendetes Verfahren zur Netzgenerierung ist das Delaunay Ver-fahren. Dieses erzeugt für eine gegebene Punktmenge ein unstrukturiertes Gitteraus Dreiecken. Es gibt verschiedene Methoden, um Punkte so zu Dreiecken zuverbinden, dass sich ein Gitter ergibt, in dem alle Punkte integriert sind.

Abbildung: 3.2: Zwei unterschiedliche Triangulierungen einer Punktmenge.Quelle: [6].

In beiden Bildern ist die gleiche Punktmenge vernetzt. Welche Triangulierungist besser geeignet? Die Anzahl der Dreiecke, der Punkte, der Kanten, und derPunkte die sich auf dem Rand benden ist gleich. Jedoch sind die Dreiecke inder linken Vernetzung oensichtlich wesentlich schmaler als die rechts. Bei derspäteren numerischen Berechnung können solche degenerierten Dreiecke leichtzu Interpolationsfehlern führen. Man möchte die Punkte dementsprechend ineiner Art vernetzen, sodass die gebildeten Dreiecke möglichst ähnlich einemgleichseitigem Dreieck sind.

Mit der Delaunay Triangulierung werden die Punkte so vernetzt, dass sie derUmkreisbedingung genügen. Das heiÿt im Umkreis eines Dreiecks auf dem diedrei Knoten des Dreiecks liegen darf kein weiterer Punkt der gesamten Punkt-menge liegen. Dadurch wird der minimalste aller Dreieckswinkel maximiert. Eswerden also Dreiecke mit spitzen Winkeln so gut wie möglich vermieden. Somitwerden, wie man leicht sieht, auch stumpfe Winkel reduziert, also insgesamtentartete Dreiecke vermieden.

15

Es gibt keine andere Dreiecksvernetzung, die einen gröÿeren minimalen Drei-eckswinkel aufweist [6].

Ein Gitter ist eine Delaunay Triangulierung, wenn es folgende Eigenschaftbesitzt:

Lokal-Delaunay: Eine Triangulierung T ist Lokal-Delaunay genau dann, wennfür je zwei benachbarte Dreiecke D1 = (A,B,C) ∈T und D2 = (C,B,D)∈T gilt,D liegt nicht im Umkreis von D1 und A liegt nicht im Umkreis von D2. [6]

Ein Delaunay Gitter weist gute Eigenschaften auf. Zu einer guten Triangulie-rung gehört jedoch auch eine kurze Laufzeit, damit auch komplexere Problem-stellungen noch behandelbar sind. Zum Sortieren n reeller Zahlen ist die minima-le Laufzeit O(n(log(n))). Eine Triangulierung mit dieser Laufzeit ist die schnellstmögliche Triangulierung im 2-dimensionalen Raum. Es gibt, siehe [6], Algorith-men zur Delaunay Triangulierung, die nachgewiesen eine minimale Laufzeitkom-plexität O(n(log(n)) aufweisen. Tomas Lehner beschreibt in Kapitel 4.7 seinerDiplomarbeit [6] einen solchen Algorithmus.

16

4 Nachträgliche Netztqualitätsverbesserungen

Wir haben nun einige verschiedene Möglichkeiten gesehen, ein allgemeines Git-ter für ein Gebiet zu konstruieren, und dieses Gitter zur Lösung der Ränder desin dem Gebiet betrachteten Objektes zu nutzen.Wie wir gesehen haben, bieten diese Gitter meist eine recht gute Approxima-tion an das Originalobjekt. Ein Grund die Qualität des Gitters nachträglichzu verbessern könnte sein, dass wir in der Anwendung normalerweise sehr ver-schiedene Objekte mit sehr unterschiedlichen Rändern betrachten. Um unserGitter nochmal speziell an die Krümmungseigenschaften des betrachteten Ob-jektes anzupassen, möchten wir unser randlösendes Gitter nochmal nachträglichanpassen.Grundsätzlich gibt es drei verschiedene Ansätze zur Verbesserung der Netzqua-lität:

• Eine Option ist die lokale Anpassung des Gitters durch Verfeinerung bzw.Vergröberung indem man Knoten hinzufügt oder löscht und in der Umge-bung das Gitter neu auöst.

• Der zweite Ansatz ist face/edge swapping. Wir tauschen Flächen(3D),bzw. Kanten(2D) aus und verbinden die Knoten neu.

• Eine weitere Möglichkeit ist eine Gitterglättung. Wie der Name schonsagt, versuchen wir möglichst glatte Kanten und Übergange von grobenzu feinen Auösungen zu schaen. Dazu ordnet man die Gitterknoten neuan, indem man zum Beispiel den optimalen Ort, für einen Knoten, für einebereits festgelegte Umgebung, neu berechnet.

Ein weiterer Grund die Gitterqualität zu verbessern ist, dass schlecht ge-formte Zellen die Robustheit und die Konvergenzgeschwindigkeit der numeri-schen Berechnungen negativ beeinussen. Dazu müssen wir zunächst denierenwas eine schlecht geformte Zelle ist, um unser Gitter auf solche unerwünschtenElemente hin zu untersuchen. Zur Findung geeigneter Kriterien, nden sich inder Literatur verschiedene Ansätze. In [18] werden für 3D-Objekte beispielsweisefolgende Qualitätsmaÿe kombiniert:

• Edge-ratio: Die edge-ratio ist die längste Kante der Zelle geteilt durch dieKürzeste

• Joe-Liu Parameter: Sei ‖s‖ das Volumen eines gegebenen d-Simplex s,seien vi (i =0,...,d) die Ecken von s, und seien eij die Ecken von s die viund vj verbinden. Wir berechnen den Joe-Liu Parameter eines d-Simplexwie folgt:

F (s, d) =f(s, d)

g(s, d)=

22(1− 1d ) × 3

d−12 × ‖s‖ 2

d∑0≤i≤j≤3

‖eij‖2(9)

17

Dieser Term drückt ein, durch die Dimension, skaliertes Verhältnis zwi-schen dem Volumen eines Elementes und seinen Kanten aus. Umso gröÿerder Wert F(s,d) ist, umso besser ist die Qualität des Elementes s. Ist derWert klein, so ist das Volumen des Elementes im Verhältnis zu der Sum-me der quadrierten Kantenlängen klein. In dem Fall ist eine Kante desElementes im Verhältnis zu seinem Volumen sehr kurz, somit das Elementdegeneriert, denn die anderen Kanten sind entsprechend länger um dasgroÿe Volumen zu erzeugen.

• Minimum volume bound: Berechne das Volumen jedes Tetraeders undnde das Tetraeder mit minimalem Volumen. Dieser Volumen Parametersollte verbessert werden, falls er unter einem festgelegtem Schwellenwertliegt.

Mit Hilfe dieser Qualitätsmaÿe ist uns nun möglich schlecht geformte Zel-len zu lokalisieren.Wir gehen dabei die Gitterzellen durch und entfernen Kanten, deren edge-ratioüber einem zuvor gewählten Schwellenwert liegt. Danach verbinden wir die Kno-ten in der Umgebung neu. Dies wiederholen wir solange bis alle Zellen über demSchwellwert liegen. Auf diese Weise wenden wir auch die anderen beiden Qua-litätsmaÿe an.Als Ergebnis erhalten wir ein Gitter, das unseren, zuvor festgelegten, Qualitäts-ansprüchen genügt.

4.1 Laplacian smoothing

Laplacian smoothing ist eine Methode zur Glättung von Gittern. Es zeichnetsich vorallendingen durch die Einfachheit des Algorithmus aus. Der Algorith-mus verschiebt die einzelnen Knotenpunkte, um das Gitter zu verbessern. Umdie Punkte verschieben zu können, brauchen wir eine bereits bestehende Tri-angulierung unser Punktmenge. Wir betrachten hier 2D Laplacian-smoothingauf Dreieckgittern. Es gibt auch Algorithmen für Viereckgitter und für den 3-dimensionalen Raum.Wir betrachten, die Gleichung der gewichteten Diererenzen, siehe [3].∑

i

wi(xi − x) = 0,∑i

wi(yi − y) = 0 (10)

mit den Gewichten wi und den nächsten Nachbarn (xi, yi) von dem betrach-tetem Knotenpunkt (x,y). Nächste Nachbarn meint hier die Punkte die durcheine Gitterkante direkt mit dem Knoten verbunden sind. Diese Gleichungen las-sen sich mit Einheitsgewichten nun iterativ lösen.Die gewöhnliche Laplacian smoothing Denition ist folgende:Seien E1,E2,...,Ek Dreiecke die den Knoten z∗ teilen, und seien die übrigen

18

Ecken von E1,E2,...,Ek z1, z2,..., zk. Laplacian Smoothing deniert eine neueKoordinate durch

z∗ = (z1 + . . .+ zk)/k (11)

siehe [3].Nachdem wir den Schritt einmal für alle Knoten durchgeführt haben, könnenwir auch weitere Iterationen durchführen, indem wir im geglättetem Netz auchwieder eine Glättung, wie in (10), durchführen.

In Kapitel 3 haben wir uns unter anderem mit der Delaunay-Triangulierungbeschäftigt. Dort haben wir gesehen, dass diese Triangulierung schöne Eigen-schaften aufweist, und deswegen häug Anwendung ndet. Deswegen gehen wirnun davon aus, dass das Startgitter, das wir beim Laplacian smoothing vor-ausgesetzt haben, ein Delaunay Gitter ist. Bei der Vorgehensweise wie obenkönnte es nun sein, dass unser Gitter von einem zum nächsten Iterationsschrittdie Delaunay-Eigenschaft verliert. Deswegen erweitern wir unseren Algorith-mus dadurch, dass wir bei der Neuberechnung jedes Knotenpunktes überprüfen,ob das Gitter dadurch die Dalaunay-Eigenschaft behält oder nicht. Bleibt dieDalaunay-Eigenschaft erhalten, so verschieben wir z nach z∗. Im anderen Fallverändern wir die Position des Knotens nicht.

Für jeden Punkt zu prüfen, ob die Delaunay nach Verschiebung erhaltenbleibt ist aufwendig. Beim einfachen Laplacian smoothing haben wir hingegeneinen Rechenaufwand der Ordnung k. Die Variable k entspricht der Anzahl derKanten die mit z verbunden sind.Laplace-Delaunay- smoothing kann schon in einem einzelnen Punkt einen Re-chenaufwand der Ordnung n2 auslösen, mit n als Anzahl der Knoten. Insgesamtbedarf ein Iterationsschritt der einfachen Glättung einen Aufwand der Ordnungn, und unter Nutzung der gegebenen Datenstrukturen ndet man Algorithmender Ordnung K*n für eine Laplacian-Delaunay smoothing Iteration. Wobei Kdie maximale Anzahl der Dreiecke ist, die einen Punkt teilen.

Laplacian smoothing ist konvergent, dies ist bei der Laplace-Delaunay smoo-thing Iteration nicht der Fall, hier müssen wir andere Abbruchkriterien für denAlgorithmus angeben. Auch wenn man eventuell nicht den optimalen Schrittzum Abbrechen der Iteration gefunden hat, so ist im Laplace-Delaunay smoo-thing der maximale Dreieckswinkel wesentlich kleiner, und entsprechend derminimale Winkel wesentlich gröÿer wie folgende Tabelle eines Rechenbeispielszeigt.

4.2 Verschiedene Gitterglättungen in 3 Dimensionen

Das Laplacian-smoothing kommt auch häug in 3D Anwendungen zum Einsatz.Dies liegt daran, dass es ein einfaches Verfahren mit wenig Speicheraufwand ist.Man hat mittlerweile aber andere Verfahren entwickelt die ähnliche Laufzeiten

19

Abbildung: 4.1. Quelle: [3].

aufweisen, und wesentlich schönere Ergebnisse produzieren. Einfaches Laplaciansmoothing haben wir in dem letzten Abschnit bereits kennen gelernt. Das gleichePrinzip können wir auch in 3 Dimensionen anwenden.Einfaches Laplacian smoothing sieht in 3 Dimensionen ähnlich aus wie oben.Wir denieren den Operator zur Berechnung der neuen Koordinaten (UmbrellaOperator, oder kurz U ), wie in [9]:

U (P ) =1∑i

wi

∑i

wiQi − P (12)

Das iterative Laplace Verfahren geht dann in einem Schritt wie folgt vor:

Pnew ←− Pold + λU (Pold) (13)

Wir betrachten ebenfalls noch kurz die Iterationsregeln zum Taubin, Bila-placian smoothing und mean curvature ow und schauen uns ein paar Resultateder verschiedenen Methoden an.Taubin smoothing versucht durch alternierende Gewichtungsfaktoren hohe Fre-quenzen von U zu beseitigen und niedere Frequenzen zu unterstützen. Hierlautet die Iterationsvorschrift:

Pnew ←− (1−µU )(1 +λU )Pold = Pold− (µ−λ)U (Pold−µλU 2(Pold)) (14)

mit µ > λ > 0, und U 2(P ) = 1∑iwi

∑i

wiU (Qi)−U (P ).

Es hat sich herrausgestellt, dass diese Iteration sehr gut funktioniert, wennman U wieder wie beim einfachen Laplacian smoothing wählt.Bilaplacian Flow erhält man indem man λ = µ wählt. Ein Iterationsschritt siehtdann wie folgt aus:

Pnew ←− Pold + λU 2(Pold) (15)

Kommen wir nun noch zum mean curvature ow. Hier nehmen wir die Glät-tung mithilfe der Gesamtkrümmung des Objekts vor. Wir iterieren

20

Pnew ←− Poldλκ(Pold)n(Pold) (16)

mit κ als Krümmung wie schon in Abschnitt 3.2 und n als Einheitsnorma-lenvektor.

Für mehr Details, zu (12)-(16), verweisen wir auf [9].

Abbildung 4.2 zeigt nun, dass alle diese Verfahren Schwächen aufweisen,wenn man sie zur Glättung von Rauschen auf Gittern anwendet die in unter-schiedlichen Regionen eine unterschiedliche Zelldichte haben. In der Abbildungist an Nord- und Südpol ein dichteres Gitter konstruiert worden als auf demRest des Objekts. Das nächste Bild zeigt dasselbe Problem nocheinmal an ei-nem anderem Objekt.

Abbildung 4.2: (a) zeigt das Objekt im Originalzustand und in (b) wurde Rau-schen hinzugefügt; (c) Laplacian smoothing hat das Rauschen entfernt aber dasObjekt ist verformt; (d) Taubin smoothing hat das Rauschen entfernt und dieForm wieder hergestellt, es sind jedoch unregelmäÿige Wellen auf der Oberächeentstanden; (e)mean curvature ow stellt die Form des Objektes wieder gut her,erzeugt aber starke unregelmäÿigkeiten auf der Gitteroberäche;(f) zeigt das Er-gebnis der Methode der unten erläuterten Methode. In der unteren Reihe habenwir bei (A) ein anderes Objekt und diesem in (B) wieder Rauschen hinzuge-fügt; (C) Taubin smoothing hat wieder das hochfrequente Rauschen enfernt,man sieht aber wie in (d) niederfrequentes Rauschen; (D) mean curvature owhat die ursprünglich scharfen Kanten des Objekts vollständig entfernt (Laplacesmoothing hat hier ein ähnliches Ergebnis erzeugt); (E) zeigt das Ergebnis mitder gleich erläuterten Methode.Quelle: [9].

In [9] konstruiert man zur Vermeidung der Glättungsfehler, die wir in denAbbildungen sehen, ein modiziertes mean curvature ow Verfahren. Die Idee

21

ist, das mean curvature ow Verfahren als Grundlage zu benutzen, da diesesoft gute Glättungsresultate aufweist, und nebenbei das zugrundeliegende Gitterzu regularisieren. Die Regularisierung des Gitters wird hier mit Laplace- smoo-thing durchgeführt. Dabei sollten dann die sonst mit dem mean curvature owauftretenden Störungen beseitigt werden.Man betrachtet nun eine Familie von glatten Oberächen S(u,v,t). Wobei (u,v)die Oberäche, und t die Familie parametrisiert.

∂S(u, v, t)

∂t= Fn+Gt, S(u, v, 0) = S(0)(u, v) (17)

mit einer gegebenen Funktion G und einer Geschwindigkeit F in Normalen-richtung. Wählt man Fn = Hn und Gt= C[U0 − (U0n)n] (U0 der UmbrellaOperator mit Einheitsgewichten), C eine positive Konstante, so erhält man alsIterationsvorschrift:

Pnew ← Pold + λ[H(PoldnPold + C(U0(Pold − (U0(PoldnPold))nPold))) (18)

Man kann C auch als Funktion, abhängig von der Oberächenkrümmungwählen. Auÿerdem möchten wir uns noch überlegen wie man den Algorithmusanpasst um oversmoothing zu vermeiden.

Abbildung 4.3: (a) Original; (b) Nahansicht der unterschiedlichen Gitterdich-te in den verschiedenen Regionen des Objekts; (c) Rauschen hinzugefügt; (d)Laplace smoothing; (e) Taubin smoothing; (f) Bilaplacian smoothing; (g) meancurvature ow; (h) Glättung mit Hilfe des hier vorgestellten Ansatzes.Quelle: [9].

Beim oversmoothing durchläuft unser Glättungsverfahren zu viele Iteratio-nen, was dazu führt, dass scharfe Kanten des Objekts abgerundet werden. Einanderer Ansatz als Funktionen in einen Algorithmus einzubauen, die währendder Glättung oversmoothing vermeiden, ist die optimale Anzahl an Iterationen

22

für den Algorithmus zu bestimmen, und ihn nur solange laufen zu lassen, bisdiese Anzahl erreicht ist.Zum Vergleich verschiedener Glättungsmethoden wurde in [?] für jedes einzelnedie optimale Laufzeit bestimmt. Um die Laufzeit zu bestimmen nimmt man anes gibt ein Netz G und das Netz G mit hinzugefügtem Rauschen, auf das dasjeweilige Verfahren angewendet wird.

Die optimale Stopzeit τ lässt sich wie folgt berechnen:

τ =1

2(argmintEν(G,Gt) + argmintEn(G,Gt)) (19)

mit Gt als das Netz mit Rauschen nach t Iterationen.

Abbildung 4.4: Das Stanford bunny vernetzt; links das Original und rechts mithinzugefügtem Rauschen.Quelle: [9].

Abbildung 4.5, zeigt die Glättung mithilfe...() Laplacian smoothing; (×) meancurvature ow; () Taubin Schema; (∆) bilaplacian ow; (+) Verfahren basie-rend auf Normalenanpassung. In der oberen Zeile τ , in der unteren 5τ Iteratio-nen.Quelle: [9].

23

Das Verfahren das für (+) gewählt wurde, ermittelt die Normalen auf derNetzoberäche und mittelt diese im ersten Schritt.

m(T ) =∑

S∈N (T )

A(S)n(S)m(T )← m(T )

‖m(T )‖(20)

T ist eine einzelne Netzzelle, A(T) die Umgebung von T, n(T) der Norma-lenvektor zu T, und N (T ) die Menge aller Elemete des Netzes.

Im nächsten Schritt ordnen wir die Knoten des Netzes wieder neu an, indemwir eine Fehlerfunktion, die die Güte des modizierten Netzes misst minimieren.

Efit(P ) =∑

A(T )‖n(T )−m(T )‖2 (21)

Die schnellsten Verfahren in 5.5 sind Laplacian smoothing und mean curva-ture ow. Bilaplacian smooting und die Taubin Methode sind langsamer, erhal-ten aber auch besser die ürsprünglichen Formen des Objekts. Für die TaubinMethode ist keine Vorberechnug der optimalen Laufzeit erforderlich. Am lang-samsten ist das Verfahren basierend auf der Normalenanpassung. Sie erhält ambesten die Strukturen des Originalobjekts während sie das Rauschen entfernt.

24

5 Spezielle 3D Gitterverfahren

In diesem Kapitel möchten wir uns zwei Gitterverfahren einmal genauer anse-hen. Um zu sehen wie ein 3D Gitter konstruiert werden kann und später dieverschiedenen Methoden zu vergleichen.

5.1 BCC Gitter

Ein spezielles Gitter stellt das body-centered cubic Gitter dar. Im ersten Schritt,der Gitterkonstruktion,legen wir in unser Gebiet Ω ein uniformes Würfelgitter.Als nächstes fügen wir im center jedes Würfels einen weiteren Knoten hinzuund verbinden ihn mit den acht anderen Knoten des Würfels. So erhalten wirfür unser Gitter eine Kristallstruktur die in der Natur ebenfalls häug auftritt.Auÿerdem haben wir nun zwei ineinander verstrickte Gitter. Denn acht der ebenhinzugefügten Punkte bilden einen Würfel mit einem Knotenpunkt in der Mitte,also genauso wie im zuerst konstruierten Gitter.

Abbildung: 5.1: Die Struktur des BCC Gitters.Quelle [2].

Um bestimmte Stellen des Gitters genauer darzustellen, verfeinern wir dasGitter an diesen Stellen mit Hilfe einer rot-grün Hierarchie.Die rot-grün Verfeinerung nehmen wir in den Tetraedern in den Würfeln vor.Benötigt ein Tetraeder eine Verfeinerung so verfeinern wir es je nachdem, wieviele Seiten des Tetraeders zweigeteilt werden müssen um die nötige Verfeine-rung zu erreichen in eins der Tetraeder die in Bild 5.2 angegeben sind. Wir sehendas keines der kleineren, durch die Teilung entstandenen Tetraeder, der child-ren, entartet ist. Deswegen nutzen wir auch nur diese Tetraeder zum verfeinern.Falls ein child der grünen Tetraeder weiter verfeinert werden soll, entfernen wirzuerst das grüne Tetraeder ersetzen es durch ein rotes und berechnen darauferneut, ob eine weitere Verfeinerung nötig ist.Diese Verfeinerung kann während der Netzgenerierung oder schon im vorhinein

25

z.B. durch eine mesh-size function festgelegt werden. Auÿerdem können wir dasWürfelgitter mit einer octree-Struktur vergröbern oder verfeinern. Wobei zweibenachbarte Würfel sich höchsten um eine octree Verfeinerung/Vergröberungunterscheiden sollen.

Abbildung 5.2: Die zulässigen verschiedenen children der regulären BCC Tetra-eder.Quelle [2].

Wie man in Bild 5.2 sieht haben nur children des roten Tetraeders wieder diereguläre tetraedrische Form. Deswegen werden, wenn überhaupt, nur childrender roten Verfeinerung eventuell erneut verfeinert. Soviel erstmal zum generellenAufbau des Gitters.

Wir möchten als nächstes betrachten, wie wir unser Initialgitter für ein be-liebiges Objekt unter Kenntnis der zugehörigen level-set Funktion Φ erstellen.Um nicht das ganze Gebiet Ω zu vernetzen, konzentrieren wir uns mit unsererKonstruktion auf das Objekt M . Φ gibt für Knoten auÿerhalb von mathscrMpositive Werte an, das heiÿt Tetraeder mit nur positiven Knoten liegen komplettauÿerhalb von M und sind somit für uns nicht von Interesse. Wir entfernen die-se Zellen aus dem Gitter.Um die Tetraeder entlang der Nullschnittstelle von Φ noch weiter zu verfeinern,kann man verschiedene Ansätze, wie schon in dem Abschnitt zu mesh-size func-tions besprochen, wählen. In [2] wird der Ansatz gewählt, die Tetraeder, die vomRand geschnitten werden, genau dann zu verfeinern, wenn die längste Kante desTetraeders im Verhältnis zum Radius eines Krümmungsmaÿes zu groÿ ist. DieseVerfeinerung nehmen wir mit dem oben beschriebenen rot-grün Verfahren vorund erhalten so unser BCC Gitter.

26

5.2 CFE Gitter

Zum Vergleich stellen wir hier noch ein weiteres Verfahren vor, welches, ähn-lich wie das obige Verfahren, strukturierte Hexaedrische Gitter zu Konstruktionverwendet.Wir möchten hier den Composite Finite Elements Space vorstellen. Was über-setzt zusammengesetzter Finite Elemente Raum heiÿt. Der Raum den wir zurFinite Elemente-Simulation konstruieren, besteht aus zwei zusammengesetztenGittern.Wir kombinieren hier unstrukturierte tetraedrische Gitter und uniforme hexa-drische Gitter und zwar wegen folgender Überlegung:Unstrukturierte Gitter weisen den Vorteil auf das sie eine höhere geometrischeFlexibilität haben. Wir können die Zellen eines solchen Gitters wie schon obenbesprochen, leichter an die Form unseres Objektes anpassen, und den Rand desObjektes linear interpolieren. Dadurch benötigt so ein Gitter jedoch auch eineVernetzung der einzelnen Knotenpunkte, wie es z.B. das Delaunay-Verfahrenvornimmt. Zum anderen kommt es in der Bildverarbeitung auch häug vor,dass man merkt das eine weniger genaue Darstellung eines Gebildes vollkom-men ausreichend ist. Eine Vergröberung eines unstrukturierten Netzes ist jedochim allgemeinen ein nur schwierig zu lösendes Problem.

Ein uniformes Gitter hingegen ist leicht zu vergröbern: Wir fügen acht gleich-groÿe Würfel zusammen und erhalten einen Gröÿeren Würfel. Zudem ist eineVernetzung hier nicht mehr notwendig, da die gesamte Gitterstruktur bereitsdurch den Abstand zweier Knoten festgelegt ist. Wie bereits in Kapitel 3 be-sprochen, weist ein solches Gitter auch eine ezientere Datenstruktur auf.

In dem CFE Gitter versuchen wir nun, die beiden Strukturen möglichstoptimal zu kombinieren. Wir benutzen dazu ein uniformes hexaedrisches Hin-tergrundgitter und versuchen, durch möglichst einfache stückweise lineare Basis-funktionen, die wir durch ein nur zur Bestimmung der Basisfunktionen konstru-iertes virtuelles Gitter bestimmen, eine gute Interpolationen des Objektrandeszu erreichen. Wie dies genau geschieht, wird im Folgenden erläutert.

Um uns die Grundideen vor Augen zu führen erstellen wir zunächst einsolches Gitter im ein- und zwei-dimensionalen Raum. In einer Dimension be-trachten wir eine kompakte Teilmenge von R. Wir diskretisieren dieses Intervall,indem wir in gleichen Abständen Knotenpunkte einfügen. Auf diesen Punktenplatzieren wir unsere Unbekannten und erstellen die Basisfunktionen. Die Ideedes CFE Gitters im eindimensinalen Fall ist: Die Knotenpunkte im gleichenAbstand voneinander, ungeachtet des Objektrandes zu platzieren und die Ba-sisfunktionen durch Indikatorfunktionen am Rande des Objektes abzuschneiden.

Obige Betrachtungen führt man jedoch eher selten durch, meist betrachtet manein Objekt in mindestens zwei Raumdimensionen. Wir diskretiesieren das Gebietdurch ein karthesisches Gitter und teilen jedes Viereck in zwei gleiche Dreiecke.

27

An den Kanten dieser Dreiecke speichern wir die Bildvoxelwerte und die Rand-punkte, die wir zuvor aus der Segmentierung erhalten haben. Wir verbindendie Randpunkte, um eine lineare Annäherung des echten Randes zu erhalten.Als letztes teilen wir noch die durch den Rand entstandenen unstrukturiertenVierecke in jeweils zwei Dreiecke, um die lineare Interpolation zu lösen.

Abbildung: 5.4: Ein CFE Gitter für eine 2-dimensionale Anwendung.Quelle: [14].

Man erkennt hier schon sehr genau die Umsetzung der obigen Vorüberle-gungen: Das uniforme Viereckgitter erlaubt eziente Datenstrukturen und ein-fach vorzunehmende Vergröberungen des Gitters, und im Inneren der Zellenerhalten wir durch die Teilung, eine gute Approximation des Randes. Im Drei-dimensionalen wird das ganze nun ein wenig technischer, aber die Grundideenbleiben die selben.

Wir nennen das von uns betrachtete Gebiet, enthalten im R3, Ω, und diskre-tisieren dieses Gebiet durch ein hexaedrisches Gitter G mit den Knotenpunkten0,...,Nx×0,...Ny×0,...,Nz. Auf diesen Knoten können wir, die Werte derlevel set Funktion Φ sowie die Bildvoxel speichern. Wir erhalten für die Bild-funktion u0 : Ω→ R und die level-set Funktion Φ eine trilineare Interpolation injedemWürfel. Dabei soll keine der Zellen mehr als einmal vom Rand geschnittenwerden. Um eine bessere Approximation zu erreichen, teilen wir jeden Würfelin sechs Tetraeder der im Bild dargestellten Form.

Abbildung: 5.5: Die Einbettung der regulären Tetraeder in das hexaedrischeHintergrundgitter.Quelle: [7].

28

Nach dieser Einteilung erhalten wir ein Gitter G x welches sich durch dieKanten der Tetraeder von G unterscheidet, aber die Menge der Knotenpunkteunverändert lässt. Innerhalb der Tetraeder T∈ G x können wir nun u0 line-ar interpolieren. Wir erhalten zusätzlich eine lineare Annäherung des Inneren(Ωx−) und Äuÿeren (Ωx+), sowie des Randes (γ

∇). Einige der Tetraeder werdenvon γ∇ geschnitten, dabei entstehen durch die Teilung der Tetraeder, entwederzwei Prismen, oder ein Prisma und ein Tetraeder. Keines der Tetraeder wirdmehrmals geschnitten, denn wir haben G oben so gewählt, dass jedes Hexa-eder höchstens einmal vom Rand geschnitten wird. Um die Approximation desRandes γ∇ zu lösen, teilen wir entstandene Prismen an den viereckigen Ober-ächen durch eine Diagonale von einer Ecke zur anderen. Wir erhalten so unservirtuelles Gitter G∇ das γ∇ löst. Wir haben nun folgende Gitter konstruiert:

• Ein uniformes Hintergrundgitter G mit Knoten N

• Ein Gitter aus regulären Tetraedern G x mit Knoten N x = N

• Ein unstrukturiertes tetraedrisches Gitter G∇ mit Knoten N ∇, dass denangenäherten Rand γ∇ linear interpoliert.

In nächsten Schritt, wollen wir uns überlegen, wie wir auf unserem Gitterdie Basisfunktionen berechnen wollen. Wir betrachten dazu die Gleichung:

L(u) = f (22)

L ist ein elliptischer Dierentialoperator zweiter Ordnung, der auf die zu be-stimmende Basisfunktion u wirkt. Auf der rechten Seite der Gleichung stellt fdie Randbedingungen des Objektes dar. Die Funktionen u und f hängen von xab, wobei x ∈ N ∩ Ω− gilt.

Wir betrachten zunächst die beiden folgenden Vektorräume:

V ∇h :=spanψ∇i ∈ C0(Ω)|ψ∇i bzgl T ist an f.a. T∈ G∇ und ψ∇i (xj) = δijf.a. xj ∈ N ∇

V xh :=spanψxi ∈ C0(Ω)|ψxi bzgl T ist an f.a. T∈ G x und ψxi (xj) = δij f.a.xj ∈ N x

In beiden Fällen steht h für die Schrittweite von einem zum anderen Knoten.V ∇h löst den Rand γ∇, da der Vektorraum ja gerade durch die Funktionenerzeugt wird, die diesen interpolierten Rand darstellen. Der andere VektorraumV xh löst den Rand nicht, hat aber seine Knoten auf dem regulären Gitter. Umden Composite Finite Elemts Space zu konstruieren kombinieren wir die beidenVektorräume.

V hCFE := spanψCFEi

mit ψCFE

i := ψxi ∗ χΩx−

29

Dies mag eventuell den Eindruck erwecken, als würden wir V ∇h nicht ver-wenden, aber Aufgund der Konstruktion der Gitter G x und G∇ erhalten wirfolgende Eigenschaft:

∀xi ∈ N x∃Ci := xi1 , . . . ,xici ⊂ N ∇ und mit Gewichten µi,l ∈ R gilt:

ψxi =

ci∑l=1

µi,l ∗ ψ∇i,l (23)

Das machen wir uns zu nutze, um die Basisfunktionen zu berechnen, die vonγ∇ abgeschnitten werden. Für alle Basisfunktionen die komplett in Ωx− liegen,ist die Annäherung durch Funktionen aus V xh ausreichend.Um einen Standard Galerkin Ansatz zu erhalten, multiplizieren wir u mit einerTestfunktion v ∈ V hCFE und integrieren über Ωx−.Die Galerkin Methode versucht im Wesentlichen, eine approximative Lösungfür eine Bilinearform zu nden. Dabei soll die Lösung auf dem Vektorraum mitHilfe endlichdimensionaler Untervektorräume gefunden werden [4].Wir betrachten nun die schwache Form des Randwertproblems L(u) = f .∫

Ωx−

3∑α,β=1

aαβ∂αu∂βv =

∫Ωx−

fvdx (24)

Wir nutzen nun die Eigenschaft (23) und erhalten als schwache Lösung:∫Ωx−

∂αψi∂βψjdx =

ci∑l=1

µi,l

cj∑k=1

µj,k∑

T∈G∇∩Ωx−

∫T

∂αψ∇il∂βψ

∇jkdx (25)

Nach dem numerischen Lösen der Gleichungen erhalten wir die Basisfunk-tionen die den Rand γ∇ lösen. Doch zuvor müssen noch die Randbedingungenf, die wir bisher noch nicht genauer betrachtet haben, festgelegt werden.Zur Finite Elemente Anwendung legt man fest, das auf dem inneren Randγ = Ω−, Neumann Randbedingungen gelten sollen. Auf dem äuÿerem Rand∂Ω ∩ ∂Ω− =: ΓD∪ΓN verlangen wir Dirichlet Randbedingungen auf ΓD undNeumann Randbedingungen auf ΓN . Das heiÿt, wir schreiben dort wo der Randdes Objektes komplett in Ω liegt, die Ableitungen der Basisfunktionen vor, unddort wo das Objekt durch Ω begrenzt ist, schreiben wir die Funktionswerte vor.Man legt also fest, wie stark sich das Objekt in Ω verändern (Verformungen,Temperaturschwankungen) kann, und welche Bedingungen am Rand gelten. AlsAnwendungsbeispiel, stelle man sich einen Körper vor, der auf einer Platte liegt,oder dort befestigt ist. Dann ist die Platte eine Begrenzung von Ω und dort wosich der Körper und die Platte berühren, gelten die Dirichlet Bedingungen. Ummodellieren zu können, dass sich die Umgebungstemperatur ändert, oder wirmit einer bestimmten Kraft auf den Körper wirken, schreiben wir auf dem Restdes Randes die Bedingungen vor wie stark sich der Körper den äuÿeren Verän-derungen anpasst.

30

Abbildung: 5.6; Quelle: [7].

Wir geben, mit den Abbildungen 5.6, 5.7, 5.8, noch einen kurzen Einblickwie man obigen Ansatz implemententieren kann:Im ersten Schritt wird eine Nachschlag Tabelle konstruiert. In der die mögli-chen acht topologischen Fälle, die bei der Zerschneidung eines der regulärenTetraeder durch den Rand auftreten können, konstruiert werden. Dabei mussunterschieden werden, ob das zerteilte Tetraeder in zwei Prismen, oder in einPrisma und ein Tetraeder geteilt wurde. Danach werden die virtuellen Knotenlokalisiert. Mit Hilfe der aus der Nachschlagtabelle konstruierten topologischenFormen werden dann über Gewichte die genauen linearen Interpolationen ska-liert. Und zum Schluss eine Matrix für die entsprechenden Tetraeder aufgestellt.

31

Abbildung: 5.7; Quelle: [7].

32

Abbildung: 5.8; Quelle: [7].

5.3 Diskussion

Welches ist das bessere Verfahren? Das CFE Gitter benötigt keine Anpassungdes berechneten Gitters, denn die Annpassung erfolgt über die stückweise linea-ren Basisfunktionen die in dem Gitter mit Hilfe des virtuellen Gitters berechnetwerden. Ähnlich wird auch das BCC Gitter während der Erstellung an die Geo-metrie mit Hilfe der Rot-Grün Hierarchie angepasst. Durch diese octree Strukturdie das BCC Gitter besitzt könnte man meinen, dass es weniger Speicherplatzbenötigt. Das lässt sich aber generell nicht sagen, da wir unser CFE Gitter auch,durch eine zuvor bestimmte mesh size function, mit einer octree Struktur aus-rüsten können.Beide Gitter können auf Probleme mit nicht kontinuierlichen Koezienten an-gewendet werden und komplizierte Oberächen auösen.

Für das CFE Gitter hatten wir gefordert, dass jedes Hexaeder nicht mehr alseinmal vom Rand geschnitten wird. Das könnte zu unglaublich hohem Speicher-bedarf führen da wir das Gitter mit einheitlichen Hexaedern konstruiert haben.Diese Forderung kann nun aber leicht relativiert werden, denn lassen wir dieAufsplittung der Hexaeder einheitlich in ihrer Aufteilung in Tetraeder, aber va-riieren mit oben bereits erwähnter octree Struktur die Gröÿe der Hexaeder sosinkt der Speicherplatzbedarf wieder auf das Maÿ, welches wir als Anpassungs-bedarf mit der mesh size function deniert haben.

In [7] nden wir noch eine weitere oben nicht erläuterte Verbesserung zurImplementierung des CFE Algorithmus. Und zwar werden die Basis Funktio-nen der Tetraeder die vom Rand durchschnitten werden, ähnlich wie bei demin Abschnitt 2.2 erläutertem Marching Cubes Algorithmus, nicht mehr direktberechnet, sondern durch Betrachtung der Knotenpunkte der Zelle ermittelt.Somit braucht unsere Konstruktion einen zusätzlichen festen Speicherplatzbe-trag, jedoch müssen wir in den einzelnen Zellen nicht mehr interpolieren, son-

33

dern nur noch die die entsprechenden Daten aus der Nachschlagtabelle laden.In [7] benötigt man mit einem Standard PC 0.05 Sekunden zum erstellen einerNachschlag-Tabelle für die Tetraeder. Diese hat ein Gröÿe von 2261 KB.

Es ist mit Sicherheit möglich, noch weitere Verbesserungen der beiden Ver-fahren vorzunehmen. Letztendlich hängt jedoch die Güte eines Gitters stark vondem zu lösendem Problem und den verwendeten Qualitätsmaÿen ab.Nach [15], weisen Beispielsweise 30 Prozent aller Elemente eine Struktur wie dasBCC Gitter auf. Wenn man genau solche Elemente modellieren möchte, bietetes sich an, das BCC Gitter zu verwenden.Laut [2] ist, unter bestimmtem dort angewandten Qualitätsmaÿen, ein Face-centered Cubic Gitter dem BCC Gitter überlegen, wenn es sich um ein Problemmit keiner oder nur geringfügiger Deformation handelt. Anwendungen in de-nen das zu modellierende Material anisotrop ist, benötigen normalerweise inder einen Richtung wesentlich dichtere Knotenpunkte als in der orthogonalenRichtung. Es ist also ohne ein festgelegtes Problem und Qualitätsmaÿe mühsameine Entscheidung zu treen, welches das bessere Verfahren ist.

Bisher sind wir auch noch nicht auf unstrukturierte 3D-Gitterverfahren ein-gegangen, obwohl das Delaunay Verfahren im 2 dimensionalen doch ein häugverwendetes ist, und als überlegenes Triangulierungsverfahren gilt. Erstellt manein unstrukturiertes Gitter aus Tetraedern mithilfe des Delaunay- Verfahrens,in drei Dimensionen, so produziert dieses sliver, hauchdünne Scheiben derenVolumen in der numerischen Berechnung null ist. Shewchuk hat sich bereits mitdiesem Problem beschäftigt und beschreibt, warum dieses Problem auftritt undwie man die meisten dieser Zellen aus dem Gitter entfernen kann. Dies ist je-doch recht aufwendig und manchmal auch nicht ausreichend, da nicht immeralle dieser schlechtgeformten Zellen entfernt werden können. Es tritt noch eineweitere Eigenart der Delaunay Triangulierung auf: Die verknüpfte Punktmengebildet bei diesem Verfahren immer ein konvexes Gebiet, jedoch benötigen vieleFinite Elemente Anwendungen kein konvexes Gebiet.

Diese Erkenntnis führt uns dazu, dass die Verwendung uniformer Hinter-grundgitter, mit darin eingebetten Tetraedern, eine Alternative zu unstruktu-rierten Gittern sein könnte.

34

6 Beispiele

6.1 Verschiedene Triangulationen

Abbildung 7.1; Quelle: [13].

Links im Bild sehen wir noch einmal den Triangulierten Kreis aus Kapiteleins. Rechts wird der Objektrand mit der Hilfe einer wesentlich höheren Anzahlan Elementen genauer angenähert. Beim genauen hinsehen ist jedoch immernoch zu erkennen, dass der Rand nur stückweise linear angenähert wird.Ein Kreis hat überall auf dem Rand eine gleichbleibende Krümmung. Somit istes möglich mit nur wenigen Elementen eine sehr genaue bilineare Annäherungzu erreichen. In einer solchen Anwendung ist also ein strukturiertes Gitter ausQuadraten den unstrukturierten Dreiecken überlegen.

Abbildung 7.2; Quelle: [4].

Hingegen sehen wir in 7.2 ein Objekt, bei dem sich lineare Interpolationanbietet. Da die vielen Ecken durch geraden verbunden sind.

35

An folgendem Beispiel möchten wir uns die Anpassung des Gitters an dasObjekt vor Augen führen.

Abbildung 7.3; Quelle: [13].

Man sieht wie sich das Gitter an die lokale Gröÿe des Objektes anpasst. Linkssind die Zellen sehr klein und nach rechts hin gröÿer werdend. Eine Anpassungan die Krümmung erfolgt oensichtlich auch, denn am inneren Halbkreis sinddie Elemente kleiner als am äuÿeren Halbkreisrand. Man könnte sich im inne-ren des Elements, zur Reduzierung der Knotenanzahl, auch gröÿere Elementevorstellen. Hier erkennen wir jedoch, dass der Gröÿenunterschied benachbarterZellen relativ gering ist, sodass glatte Übergänge von den kleineren inneren Zel-len zu den gröÿeren Äuÿeren entstehen.Dies sind genau die Ansätze die wir uns auch zur Berechnung einer mesh sizefunction, in Abschnitt 3.3, überlegt haben.

36

6.2 Finite Elemente Simulation

Zu guter letzt sehen wir uns noch eine Finite Elemente Simulation an. DasObjekt nennen wir im folgenden Brücke.

Abbildung 7.4; Quelle: [8].

Hier sieht man die Triangulation der mit dem Matlab PDE Tool skizziertenBrücke.In den nächsten Bildern sehen wir die FE-Simulation von mechanischem Flächen-Druck aus verschiedenen Richtungen.

Abbildung 7.5: Druck von oben auf die BrückeQuelle: [8].

37

Abbildung 7.6; Druck von unten auf die BrückeQuelle: [8].

Abbildung 7.7; Druck von links auf die BrückeQuelle: [8].

38

Abbildung 7.8; Druck von rechts auf die BrückeQuelle: [8].

39

7 Fazit

Wir haben nun einen Einblick in die Generierung verschiedener Gitter bekom-men. Besonders in Kapitel sechs ist klar geworden, dass uns dabei sehr vieleMöglichkeiten zur Verfügung stehen. Häug wird in FE Anwendungen auf eineangepasste Netzgenerierung verzichtet. Man übernimmt Algorithmen die be-reits implementiert sind und verwendet sie lediglich als Black Box, um daraufim nächsten Schritt die FE zu modellieren. Auch wenn wir uns im vorigen Ka-pitel auf die Erläuterung zweier Gitter mit strukturiertem Hintergrundgitterbeschränkt haben, so werden, wie Kapitel 4 deutlich gemacht hat, auch häugin 3-dimensionalen Anwendungen rein unstrukturierte Gitter verwendet.Zu verstehen was im Schritt der Gittergenerierung geschieht kann also hilfreichsein. Denn wie wir oben bereits besprochen haben, hängt die Güte eines Gitterszum Groÿteil von dem betrachtetem Problem ab. Eine einfache Anpassung derGitterstruktur, vor der Generierung, auf das Anwendungsproblem, könnte inZukunft helfen eine bessere Basis zur FE Simulation zu schaen.

40

Literatur

[1] A. Belyaev and Y. Ohtake. A comparison of mesh smoothing methods. InIsrael-Korea Bi-national conference on geometric modeling and computer

graphics, volume 2. Citeseer, 2003.

[2] R. Bridson, J. Teran, N. Molino, and R. Fedkiw. Adaptive physics basedtetrahedral mesh generation using level sets. Engineering with Computers,21(1):218, 2005.

[3] D.A. Field. Laplacian smoothing and Delaunay triangulations. Communi-cations in Applied Numerical Methods, 4(6):709712, 1988.

[4] Prof. Dr. Ansgar Jüngel. Das kleine nite-elemente-skript. Technical report,Universität Mainz, 2001.

[5] Matthias Kirschner. Marching Cubes - Erstellung von Polygonmodellenaus Voxelgittern. Technical report, Universität Paderborn, WS06/07.

[6] Tomas Lehner. Digitale Geländemodellierung mittels Delaunay-Triangulierung und Abbauplanung in AutoCAD. Master's thesis, JohannesKepler Universität Linz, 2002.

[7] F. Liehr, T. Preusser, M. Rumpf, S. Sauter, and L.O. Schwen. Compositenite elements for 3D image based computing. Computing and visualizationin science, 12:171188, 2009.

[8] Matlab R2010a. PDE Toolbox. Mathworks.

[9] Y. Ohtake, A. Belyaev, and I. Bogaevski. Mesh regularization and adaptivesmoothing. Computer-Aided Design, 33(11):789800, 2001.

[10] S. Osher and R.P. Fedkiw. Level set methods and dynamic implicit surfaces.Springer Verlag, 2003.

[11] P.O. Persson. Mesh generation for implicit geometries. PhD thesis, Cite-seer, 2004.

[12] P.O. Persson. Mesh size functions for implicit geometries and PDE-basedgradient limiting. Engineering with Computers, 22(2):95109, 2006.

[13] P.O. Persson and G. Strang. A simple mesh generator in MATLAB. SIAMreview, 46(2):329345, 2004.

[14] T. Preusser, M. Rumpf, and L.O. Schwen. Finite element simulation ofbone microstructures. In Proceedings of the 14th Finite Element Workshop.

University of Ulm. Citeseer, 2007.

[15] Universität Kiel. Kristallstrukturen. http://www.tf.uni-kiel.de/matwis/amat/mw1_ge/kap_3/backbone/r3_3_1.html.

41

[16] Wikipedia. Voxel. http://de.wikipedia.org/wiki/Voxel.

[17] Y. Zhang and C. Bajaj. Adaptive and quality quadrilateral/hexahedralmeshing from volumetric data. Computer methods in applied mechanics

and engineering, 195(9-12):942960, 2006.

[18] Y. Zhang, C. Bajaj, and B.S. Sohn. 3D nite element meshing from imagingdata. Computer methods in applied mechanics and engineering, 194(48-49):50835106, 2005.

42