Ein Collapsing Algorithmus für Simpliziale Meshes
| Wer die Homologiegruppen eines simplizialen Meshes berechnen will, muss ziemlich zeitaufwändige Algorithmen über die Inzidenzmatrizen fahren lassen, um diese in Dreiecksform zu bringen. Mein Artikel stellt das Collapsingverfahren dar und bietet einen Algorithmus der direkt im Komplex Vereinfachungen unternimmt.
| | Autor: jan - Date: 10.07.2004 - Size: 9693 chars - Hits / Day: 6.57 - Total Hits: 15823 | Diese Arbeit ist im Rahmen eines ETH Semesterprojekts entstanden, unter Aufsicht von Prof. R. Hiptmair, am Institut für angewandte Mathematik.
Simpliziale Komplexe und Meshes Wenn ein Mathematiker einen Raum aus gewissen natürlichen Bauteilen zusammenkleben kann, so spricht er von einem CW-Komplex. Sind diese natürlichen Bauteile Punkte, Kanten, Dreiecke, Tetraeder oder im allgemeinen Simplizes (d.h., die konvexe Hülle von d+1 Punkten), so spricht er von einem simplizialen Komplex. Ist der Rand des Raums nicht leer und die Kodimension des Randes gleich eins, die Anzahl der Bausteine endlich, so nenne ich einen simp. Kplx. ein "Mesh".
Homologie und Betti Zahlen Wir wollen zwei Räume miteinander vergleichen, oder, anders gesagt, wir wollen wissen, wie stark wir einen Raum deformieren dürfen ohne dass er seine Grundlegenden Eigenschaften verliert. Wie geht man das an?
Wenn man mit einem Buntstift oder so eine Bahn auf den Raum malt, die ein paarmal um irgendwelche Löcher in dem Raum herumfährt und dann wieder beim Startpunkt ankommt - dann den Raum verknetet und die Bahn wieder betrachtet, so kann es sein, dass sie gewisse Löcher nicht mehr umranded (weil wir die Löcher zugeknetet haben, oder die Bahn zu sehr deformiert haben). Falls das nicht passiert ist, und zwar für keine Bahn, und wir auch keine neuen Löcher dazugeknetet haben, so könnte man etwas salopp von "Homotopie-Invarianter Kneterei" sprechen.
Homotopie-Invarianz ist aber leider sehr schwer nachzuprüfen. Nun wurden zwei unabhängige Konzepte eingeführt: Die Homologie, bei welcher die Bahnen auf den Kanten der Bausteine wandern (und man auch Flächen etc. auf Dreieck-Konstellationen untersucht) und die sogenannte "einfache Homotopie".
Homologie ist einfach zu berechnen, jedoch ist ihre Invarianz bei Kneterei nicht ganz so aussagekräftig: Räume mit derselben Homologie müssen nicht zwingendermassen dieselbe Homotopie haben. Betti Zahlen sind einzelne ganze Zahlen welche prinzipiell die Anzahl der n-dimensionalen Löcher angeben. Ihre Invarianz ist die schächste aber ein guter Indikator für Homologie-Invarianz (sie beschreiben alles bis auf Torsion, auf welche ich hier nicht eingehen möchte).
einfache Homotopie
Wieder ausgehend von einem aus Simplizes gebastelten Raum untersucht einfache Homotopie nur Deformationen einzelner Bausteine: Wenn man zum Beispiel ein Tetraeder flach quetscht, bis es nur noch ein Dreieck ist, so ist dies unter gewissen Bedingungen an die Umgebung des Tetraeders ein "starker deformations Retrakt", d.h., ich habe den Raum nur etwas verbeult, aber ihn in keinster Weise beschädigt.
Einfache-Homotopie-Invarianz ist die stärkste (für die erfahreneren Leser ist sie ungefähr so mächtig wie nicht-evasive equivalenz). Damit ist man aber beim Kneten auch ziemlich eingeschränkt.
Kollapse Ein Kollaps ist zu verstehen als "eindrücken" eines Simplizes von aussen. Also ein starker deformations Retrakt. Ganz genau betrachtet, wird zuerst der Bereich eines Simplexes, der den Rest des Meshes berührt sozusagen abgeschnürt. (Wenn dieser Bereich einfach zusammenhängend ist, so ist das abschnüren eine Homotopie). Danach ist der Simplex nur noch so ein "Pickel", der an dem abgeschnürten Punkt hängt, und man kann ihn ebenfalls auf diesen Punkt stauchen. (Das Kontrahieren einer Kugel zu einem Punkt ist eine Homotopie, trivialerweise).
Das Programm Der vorgestellte Algorithmus führt zufällig Kollapse aus, bis es keinen mehr gibt, der die einfache Homotopie gleich lässt und berechnet dann die Betti-Zahlen. Das Paper beschreibt zudem lokale Kriterien an die Nachbarschaft von Simplizes, sodass deren eindrücken, abschnüren oder löschen ungefährlich ist.
Ein Objekt equivalent zu einer BretzelZwei Formate werden unterstützt: NetGen erzeugt die ".vol" Files aus .geo oder .stl (stereo lithographie) files. Viele Medizinische Dateien sind auf dem Internet im stl Format zu finden, also sollte man schnell irgendeinen Schädelknochen oder so im .vol file erhalten (NetGen gibts gratis zum runterladen). Andererseits unterstützt das tool "raw" files (welche vermutlich nicht ganz eindeutig definiert sind. Ich habe ausserdem aus kompatibilitäts und einfachheits-Gründen einige Änderungen an dieses Files unternommen. Hier "mein" .raw Standard:
<pn> steht für die Anzahl Punkte
<vn> steht für die Anzahl Tetraeder
xi,yi,zi sind die Koordinaten der Punkte im Raum
p1 etc., sind die Punkte des jeweiligen Tetraeders; 5 6 9 12 zBsp. wird aus dem 5., 6. etc. Punkt aus der Punkteliste gebastelt (beginne mit 1, nicht mit 0). Die "1 4" vor jeder Tetraederzeile erfüllen keinen besonderen Zweck. Füllt sie einfach ein, ohne zu fragen... :-)
points <pn> x1 y1 z1 x2 y2 z2 ... volumeelements <vn> 1 4 p1 p2 p3 p4 1 4 p1 p2 p3 p4 ...
using C:Dokumente und EinstellungenAll UsersDesktopSemesterArbeitsculpture.vol
Number of max. simplices: 5524
Simplicial Complex loaded.
Computing:
boundaries...
- d_3: [.........]
- d_2: [.........]
incidence relations...
- on 3
- on 2
local surroundings...
exterior simplices...
normalizing vertex coordinates...
Done.
Started with 5524 maximal simplices.
Done with 68 maximal simplices in 260 milliseconds.
20 simplices per millisecond.
Computing incidence matrices...
decomposing incidence matrix 0...
decomposing incidence matrix 1...
decomposing incidence matrix 2...
betti3=0
betti2=0
betti1=2
betti0=1
using C:Dokumente und EinstellungenJan KayatzDesktopCell DeletionsSample VOL Filesheart_tetra.raw
Number of max. simplices: 247924
Simplicial Complex loaded.
Computing:
boundaries...
- d_3: [.........]
- d_2: [.........]
incidence relations...
- on 3
- on 2
local surroundings...
exterior simplices...
normalizing vertex coordinates...
Done.
Started with 247924 maximal simplices.
Done with 14216 maximal simplices in 14271 milliseconds.
16 simplices per millisecond.  Ein vereinfachter Mesh |
Im oberen Bereich sieht man den Lade-, Vorbereitungs- und Vereinfachungsoutput von dem durch die Bilder dokumentierten Beispiel. Darunter wir das grösste raw file geladen, dass ich habe, um zu zeigen, wie die Performance mit grossen Datenmengen umgeht. Nicht ersichtlich ist, dass die Ladezeit für ein solches Objekt viel länger dauert.
Kleines Howto
- Man startet das Tool mittels
java -Xms<n1>m -Xmx<n2> -jar CellDeletions.jar [-file=...|-gui]
wobei
- n1 die Heap Groesse am Anfang
- n2 die maximale Heap Groesse
- -file=<file> startet kein GUI und berechnet direkt die Betti Zahlen
- -gui startet ein GUI
- Beispiel (fuer Grosse Meshes):
java -Xms256m -Xmx1024m -jar CellDeletions.jar -file=heart_tetra.raw
oder (mit GUI)
java -Xms256m -Xmx512m -jar CellDeletions.jar -gui - Das GUI
typisches Vorgehen:
- File ↓ load ↓ Vol oder Raw File laden
- Actions ↓ Prepare
- Actions ↓ draw the mesh
- Actions ↓ simplify
- Actions ↓ draw the mesh
- Actions ↓ compute betti
Links:
http://www.hpfem.jku.at/netgen/
| Bemerkungen, Kommentare und Feedback  | | Beiträge: 1 | 17.11.2004 20:20 |
|
Du kannst auch selber einen Thread starten, indem du hier klickst. |
| Home
| Artikel / Tipps und Tricks | | Artikel Navigation | |
|
|
