Home

Projektgruppe 471: Beyond Graphics

1. Eis aul Restdreiecke enfemen Untetelen Cherrier trial objekt st98 Punkte und 192 Fl chen Abbildung A 15 Das neue Objekt und das dazu konstruierte Grobgitter 136 ANHANG A BENUTZERHANDBUCH Im n chsten Schritt muss die Oberfl chentriangulierung reduziert werden indem die Inde pendent Set 1x entfernen Independent Set 20x entfernen Dreiecke auf 2 reduzieren oder Bis auf Restdreiecke entfernen Schaltfl che bet tigt wird Im letzten Fall wird zun chst die Anzahl der Restdreiecke ber den dazugeh rigen Schieberegler angepasst s Abb A 16 Unterteilung Glattung Zeichenoptionen Debug GPGPU Loser Independent Set Independent Set 1x entfernen Independent Set 20x entfernen Dreiecke auf 2 reduzieren 10 Bis auf Restdreiecke entfernen Unterteilung Unterteilen Abbildung A 16 Die Schaltfl chen zur Reduzierung der Oberfl chentriangulierung Wi Freeware pg471 Abbildung A 17 Die reduzierte Oberfl chentriangulierung A 2 TUTORIAL 137 Ist die Reduzierung abgeschlossen kann der erste Unterteilungsschritt bego
2. j EN lt P L L a Oberfl che Winkel Gl tter 50 mal ange b Oberfl che Winkel Gl tter 70 mal ange wandt wandt Abbildung 6 29 Der Oberfl che Winkel Gl tter Oberfl che Jacobi Gl tter Der Oberfl che Jacobi Gl tter s Kap 5 7 4 versucht durch eine Heuristik Jacobi Fehler in den Randelementen zu beheben Die Abbildungen 6 30 a und 6 30 b belegen exemplarisch seine Korrektheit a Ein Jacobi Fehler an der Objektoberfl che b Der Fehler wurde behoben Abbildung 6 30 Der Oberfl che Jacobi Gl tter Reparatur Prozedur Zun chst werden die Testmethoden f r das Reparatur Modul erl utert dann die Testdaten pr sentiert und mit den Testdaten der Implementierung von Freitag 13 verglichen Anschlie 6 4 VALIDIERUNG DER GL TTER 101 Bend werden einige f r das Projekt spezifische Feststellungen und Resultate angef hrt F r den Test des Moduls wurden in einem regul ren Gitter mit 1000 Hexaederzellen eine bestimm te Prozentzahl P von Knoten verschoben um ung ltige Elemente zu erzeugen Ein zuf llig ausgew hlter innerer Knoten p wurde um eine Distanz h bzw 2h verschoben wobei h die durchschnittliche Kantenl nge des Testgitters bezeichnet Prozentsatz Distanz Anzahl N Zeit 5 5 h 11 0 048 10 h 34 0 124 25 h 101 0 048 10 2h 164 0 4 Tabelle 6 13 Leistungsdaten der Reparatur
3. Abbildung 5 18 Eine Gitterschicht am Kugel Modell Kapitel 6 Projektvalidierung In diesem Kapitel wird berpr ft inwiefern die von der PG erstellte Software die zur rech nergest tzten Str mungssimulationen notwendigen Arbeitsschritte hinreichend gut bew ltigt Weiterhin wird die Geschwindigkeit und der Speicherplatzverbrauch evaluiert Zun chst wird die Validierungstechnik vorgestellt es folgt eine Auflistung der Testf lle mit denen die Randanpassung und die implementierten Gl ttungsalgorithmen untersucht werden Der Einfluss der initialen Objektreduzierung auf die Parametrisierung wird anschlie end ge pr ft An einem komplexen Testfall wird die Praxistauglichkeit von InGrid3D demonstriert und die Funktionalit t von HaGrid3D wird an Hand eines Beispiels berpr ft Der darauf fol gende Abschnitt untersucht die Leistungsf higkeit des L sers Das Kapitel schlie t mit einer zusammenfassenden Diskussion 6 1 Validierungstechnik Um die erzeugten Gitter der Projektgruppe objektiv bewerten zu k nnen m ssen geeignete Kriterien definiert werden Die Messung der Qualit tsmerkmale eines Gitters wurde in Kapi tel 2 3 2 beschrieben In Abh ngigkeit des zu verwendenden L sers gelten f r die einzelnen Merkmale bestimmte Toleranzen In Tabelle 6 1 werden exemplarisch die Toleranzen der L serimplementierung der PG mit zwei Mehrgitter Implementierungen MG1 MG2 vgl 16
4. 70 5 7 Gittergl ttung und Reparatur von Selbstdurchdringungen 71 5 7 1 Reparatur von Gitter Selbstdurchdringungen 71 5 7 2 Laplace Gl ttung a 72 5 7 3 Umbrella Gl tung 72 5 7 4 Heuristiken zur Gittergl ttung auf der Objektoberflache 72 5 9 GPU B ser us ode Bean ee Mata are dns 73 5 8 1 Datenstruktur 2 73 5 8 2 Implementierung 74 3 9 Visualisierung es ee ee ne ak en RO RO 74 6 Projektvalidierung 77 6 1 Validierungstechnik 2 0 0000000 000000004 77 6 2 Testgeometrien und Testgitter 2e 78 6 3 Validierung der Randanpassung durch Parametrisierung 84 6 4 Validierung der Gl tter 96 6 5 Einfluss der initialen Objektreduzierung 103 6 6 Komplexer Testfall 105 6 7 106 6 8 LOSER Sha D 108 6 0 Leist ngstests una m duoc et ee ae be GAG ee 111 6 10 Bewertung der Testergebnisse 113 ERR tee EE EEN 115 6312 c Ausblick ioa 2 04 ana area che ie at 116 7 Entwicklungsprozess 117 ZE Zeitlicher Ablauf 0 9200 nr an IPTE 117 7 1 1 Ablauf der PG im ersten Semester 117 7 1 2 Ablauf der PG im zweiten Semester 118 4 2 Brototypens olo edes Bean ee 118 7 2 1 Gitterunterteilung Pr
5. E B Abbildung 2 18 Abspeicherung einer Bandmatrix in Texturen 48 Zur Durchf hrung der Matrix Vektor Multiplikation liegt die Bandmatrix als Menge von Dia gonalvektoren vor Diese werden in zweidimensionale Texturen berf hrt ebenso der Vek tor der mit der Matrix multipliziert werden soll Nacheinander werden die Diagonalvektoren mit dem Vektor multipliziert und das Resultat in einer Ergebnistextur gespeichert Bei jedem Durchgang der Diagonalvektor Vektor Multiplikation muss darauf geachtet werden dass die richtigen indizierten Werte miteinander multipliziert werden Daher ist es n tig einen Hilfs index auf den aktuellen Index im Vektor aufzuaddieren Dieser Hilfsindex errechnet sich aus dem Abstand des Bandes zur Hauptdiagonalen s Abb 2 19 Die Ergebnisse der einzelnen Diagonalvektor Vektor Multiplikationen werden in den entsprechenden Eintr gen der Ergeb nistextur aufsummiert 2 6 GPGPU Abbildung 2 19 Produkt von Bandmatrix und Vektor 41 42 KAPITEL 2 GRUNDLAGEN Kapitel 3 Werkzeuge berblick ber die benutzte Software 3 1 OpenGL OpenGL Open Graphics Library 43 ist eine Spezifikation f r ein plattform und program miersprachenunabh ngiges API Application Programming Interface zur Erzeugung von 3D Computergrafik Es ist ein offener ber viele Hardwareplattformen unterst tzter Standard Zu
6. Hexaederseitenfl chen auf dem Objekt Punktgr sse RE J Er Abbildung A 12 Nach dem Verschieben des Grobgitterknotens wird dieser fortan gelb darge stellt 134 ANHANG A BENUTZERHANDBUCH Auf diese Weise l sst sich gut berblicken welche Knoten sich schon auf dem Objekt befinden Sind alle Knoten einer Hexaederseitenfl che auf den Objektrand verschoben worden so wird die Fl che rot und die inzidenten Kanten der beteiligten Knoten werden gelb eingef rbt Dies hat den Vorteil dass zum Einen die Wasserdichtigkeit der Approximation kontrolliert werden kann und zum Anderen f llt es leichter m gliche Kandidaten zum Verschieben zu finden Bilden nun die Hexaederfl chen einen vollst ndigen und wasserdichten K rper so kann das Grobgitter exportiert und in InGrid3D geladen werden Abbildung A 13 zeigt ein vollst ndiges Grobgitter f r das Testobjekt nur interest Knoten je Hexaeder anzeigen I nur die Schnittkanten anzeigen Hexaederseitenfl chen auf dem Objekt all Punktgr sse 1 IV DX x 4 m C Dokumente und Einstellungen klaus Eigene Dateienjcvs grobgitter bin tutorial_objekt stl98 Punkte und 192 Fl chen Abbildung A 13 Ein fertiges Grobgitter f r das Testobjekt mit eingef rbten Randfl chen der Hexaeder A 2 3 Tutorial Gitterunterteilung mit InGrid3D Nach dem Programmstart s Abb A 14 kann zun chst ein Objekt
7. wobei Geschwindigkeitspotential genannt wird Die Inkompressibilit tsbedingung V u 0 impliziert dass Ag 0 Dies ist wieder die so genannte Laplacegleichung Wenn eine Str mung also wirbelfrei ist wird das Geschwindigkeitsvektorfeld u durch den Gradienten eines unbekannten Potentials beschrieben d h u Ma Bei konstanter Dichte sagt das Massenerhaltungsgesetz aus dass die Divergenz des Vektorfelds gleich O ist Also muss folgende Gleichung gel st werden V x Ad 0 2 2 MAPS Multiresolution Adaptive Parameterization of Surfa ces Bei der Anpassung des Gitters an das Netz des Objektes ist es nicht trivial zu entscheiden auf welchem Punkt der Oberfl che des Objektes neu entstandene Gitterknoten ihre Position erhalten Besonders Einbuchtungen in das Objekt stellen schwierige Situationen dar Eine ein fache Projektion des neuen Punktes auf die Oberfl che des Netzes kann zu schlechten Ergeb nissen 14 f hren Aus diesem Grund hat sich die PG daf r entschieden initial eine Para metrisierung der Oberfl che zu berechnen um mit deren Hilfe erst im folgenden Schritt die Randanpassung des Gitters an die Oberfl che vorzunehmen Die PG entschied sich f r das MAPS Verfahren 30 Es soll im Folgenden in seiner Funktionsweise erkl rt werden MAPS ist eine Methode um eine glatte d h hier differenzierbare Parametrisierung einer Mannigfaltigkeitstriangulierung ber einem Basisnetz zu erhalten Dieses Basisnetz k
8. DIJKSTRA E W A note on two problems in connexion with graphs Numerische Ma thematik 1 269 271 1959 DOBKIN D P und KIRKPATRICK D G A Linear Algorithm for Determining the Se paration of Convex Polyhedra J Algorithms 6 3 38 1 392 1985 FAN Z F QIU A KAUFMAN und S YOAKUM STOVER GPU Clusters for High Performance Computing In Proceedings of ACM IEEE Supercomputing Con ference 2004 ACM Press 2004 http www cs sunysb edu 7Evislab projects urbansecurity GPUcluster_SC2004 pdf FEATFLOW http www featflow de FERNANDO R GPU Gems Bd Programming Techniques Tips and Tricks for Real Time Graphics Addison Wesley 2004 179 180 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 LITERATURVERZEICHNIS FREITAG L A und P E PLASSMAN Local optimization based simplicial mesh un tangling and improvement Int J Numerical Methods in Engineering 49 1 2 109 125 2000 G DDEKE D Geometrische Projektionstechniken auf Oberfl chentriangulierungen zur numerischen Str mungssimulation mit hierarchischen Mehrgitterverfahren Diplomar beit Universit t Dortmund 2004 GODDEKE D GPGPU Basic Math Tutorial Ergebnisberichte des Instituts f r Angewandte Mathematik Nr 300 FB Mathematik Universit t Dortmund 2005 http www mathematik uni dortmund de goeddeke gpgpu tutorial html
9. 3 140 3 1 6 3 0 6 30 1 1 6 3 0 6 3 F r detaillierte Informationen sei auf http rpdrec ic polyu edu hk old files stl introduction htm verwiesen A 3 DATEIFORMATE 143 beschreiben die ersten drei Knoten in Z Richtung In der ersten Zeile ist der Knoten mit den Indizes 0 0 0 x y z In den ersten drei Spalten findet man die Koordinaten 1 6 3 1 4 des Knotens die 3 in der dritten Spalte beschreibt den Status des Knotens und sagt aus dass es sich hier um einen Randknoten handelt Der f nfte Wert speichert den interest Status und der sechste Wert gibt den Index des Objektknotens wieder falls der Knoten auf das Objekt verschoben wurden ansonsten steht dort wie hier im Beispiel der Wert 1 In den folgenden zwei Zeilen sind die beiden Nachbarn des Knotens aus der ersten Zeile in Z Richtung Wie man erkennt sind die Knoten bis auf die Werte in der dritten Spalte identisch Dort unterscheiden sie sich um die oben beschriebene Kantenl nge 0 4 Die default Werte unterscheiden sich nicht von den Koordinaten aus den ersten drei Spalten da die Knoten nicht verschoben wurden In den n chsten Zeilen sind vier Knoten beschrieben die auf das Objekt gezogen worden sind 0 793760 0 184749 0 569158 21 160 1 2 0 2 0 6 0 0 952176 0 193007 0 202686 21 684 1 2 0 2 0 2 0 0 958134 0 189769 0 187040 2 1 788 1 2 0 2 0 20 0 764738 0 193005 0 606224 2 1 2082 1 2 0 2 0 60 Man erkennt dies leicht an den Werten der Koordinat
10. Auf nahezu planaren Oberfl chen arbeitet der Algorithmus sehr zuverl ssig und liefert die er warteten Ergebnisse dennoch beinhaltet er zwei Einschr nkungen Die Snake bewegt sich nicht in gr ere Vertiefungen auf der Objektoberfl che ebensowenig ist sie in der Lage ber st rkere Ausbuchtungen zu wandern Da der k rzeste Weg auf der Oberfl che gesucht wird ist die erste Einschr nkung immanent so ist es beispielsweise g nstiger am Rand einer Ausbuchtung ent langzulaufen als in die Ausbuchtung hineinzuwandern Auch die zweite Einschr nkung liegt hierin begr ndet der Weg ber eine Ausbuchtung w rde die L nge der Snake kurzfristig stark vergr ern Au erdem w rde sich die Kr mmung der Snake an einer solchen Stelle zu stark erh hen so dass das berqueren letztendlich dadurch verhindert wird dass die Snaxel dort eine der eigentlichen Bewegung entgegengesetzte Geschwindigkeit annehmen In der Praxis bleibt die Snake dann am Rand der Ausbuchtung stehen die Abbruchkriterien greifen obwohl ein globales Optimum noch nicht erreicht wurde Diese Einschr nkungen treten insbesondere bei zu grob aufgel sten Geometrien auf u a auch dann wenn der Dijkstra Pfad zu weit vom globalen Optimum entfernt ist s Abb 5 10 Die Grenzen des Konzeptes sind f r den Einsatz in der Gitterunterteilung jedoch keine prakti sche Einschr nkung so dass die Implementierung der im Kapitel 2 5 1 vorgestellten Technik des gradient vector flow nicht n
11. berpr ft ob einer der beiden Knoten der Kante innerhalb des Objektes liegt double calcLength berechnet die L nge einer Kante void calcVector tKoord koord berechnet den Vektor vom Start zum Endpunkt der Kante static void calcNormal cEdge xel cEdge xe2 tKoord berechnet einen Vektor der senkrecht auf e1 und e2 steht Klasse cFace cFace ist die Entit tenklasse f r eine Fl che einer Gitterzelle C 1 BERSICHT BER DIE PAKETE UND KLASSEN VON INGRID3D 153 bool addHexa cHexa xhexa f gt einen von bis zu zwei Hexaedern in einen Vektor der zur Fl che inzidenten Hexaeder ein bool isBorderObj liefert true wenn alle vier Knoten der Fl che den Status Objektrand haben bool hasSolidPoint liefert true wenn mindestens einer der vier Knoten der Fl che den Status Ob jektinneres hat double calcEdgeRatio berechnet das Verh ltnis zwischen der kleinsten und der l ngsten Kante der Fl che double calcFaceSize berechnet die Gr e einer Fl che wird ben tigt zur Berechnung der Seitenver h ltnisse der Hexaeder s Kap 2 3 2 Klasse cHexa cHexa ist die Entit tenklasse f r eine Gitterzelle des Gitters mit erweiterten Abfrageroutinen bool isSolid liefert true falls der Hexaeder im Objektinneren liegt double calculateJacobi berechnet das Jacobi Verh ltnis der Gitterzelle s Kap 2 3 2 Klasse cGrid cGrid verwaltet die einzelnen Elemente der Klassen cP
12. f hrt einen Unterteilungsschritt durch int getSubdivisions liefert die Anzahl der bisher durchgef hrten Unterteilungsschritte void doQualityTests f hrt folgende Qualit tstests durch gr ter kleinster Winkel Kantenverh ltnis Seitenverh ltnis und Jacobi Test int getBadHexas liefert die Anzahl der Hexaeder die den Jacobi Test nicht bestanden haben double getWorstEdgeRatio liefert das schlechteste Kantenverh ltnis im Gitter C 1 BERSICHT BER DIE PAKETE UND KLASSEN VON INGRID3D 157 double getSmallestAngle liefert den kleinsten Winkel im Gitter double getBiggestAngle liefert den gr ten Winkel im Gitter static cMultiGrid createHexa double double double double double double int int int bool wackeln false eine statische Hilfsroutine die regelm ige Gitter vordefinierter Gr e erzeugen kann ggf auch mit vertauschten Koordinaten Parameter wackeln true void toggleDrawGPUVec void toggleDrawGPUVecNorm void toggleDrawGPUPres void toggleRefine void toggleDrawGPUGrid void set_x_Value int schicht void set_y_Value int schicht void set_z_Value int schicht t x void set y EZ void se void se Diese Methoden setzen Zeichenoptionen f r die Visualisierung Sie bestimmen welche Gitterschicht und Datenmenge gezeichnet wird sowie die Art der Darstel lung Klasse Untangler Diese Klasse behebt Durchdringungen in Gitterne
13. gegen bergestellt die sich in der Robustheit ihrer Vorkonditionierer unterscheiden F r alle drei L ser ist es also wichtig dass keine Jacobi Fehler in den verwendeten Gittern vorhanden sind Die Einhaltung der beschriebenen Qualit tskriterien wird bei jedem der fol genden Testf lle berpr ft Dazu ist die Implementierung einer speziellen Testumgebung nicht notwendig da InGrid3D alle n tigen Qualit tsinformationen in der Statuszeile zur Verf gung stellt Der Test erfolgt nach einer aufsteigenden Strategie so werden zun chst die einzelnen Methoden an Hand von einfachen Testf llen berpr ft und anschlie end an Hand eines kom plexen Testfalls das Gesamtsystem evaluiert Die Arbeitsschritte beinhalten die Grobgittergenerierung die Gitterunterteilung das L sen sowie die Visuali sierung der berechneten Daten 77 78 KAPITEL 6 PROJEKTVALIDIERUNG Merkmal MGI MG2 Eigenimplementierung Jacobi Fehler nicht erlaubt nicht erlaubt nicht erlaubt Innenwinkel 30 lt lt 150 20 lt a lt 160 20 lt lt 160 L ngenverh ltnis 4 105 100 Tabelle 6 1 Toleranzen der Qualit tskriterien 6 2 Testgeometrien und Testgitter Die den Tests zu Grunde liegenden Geometrien und Gitter sind in Tabelle 6 2 aufgelistet Die Aufl sung des Geometrieobjektes bezeichnet dabei die Anzahl der Dreieckselemente die die Oberfl che beschreiben Fein bzw grob bezeichnen dabei die relative Aufl
14. 6 10 BEWERTUNG DER TESTERGEBNISSE 113 brauch nach dem Laden von Netz und Gitter dar die Spalte zeigt den Speicherverbrauch nach der Vergr berung des Netzes f r die Parametrisierung Die brigen Spalten zeigen den Speicherverbrauch nach der entsprechenden Anzahl von Unterteilungsschritten Bei Testfall 8 stand f r die f nfte Unterteilung nicht genug Arbeitsspeicher auf dem Testsystem zur Verf gung 6 10 Bewertung der Testergebnisse Abschlie end sollen nun die Resultate der durchgef hrten Tests zun chst bewertet und an schlie end diskutiert werden Dadurch soll die Eignung der von der PG erstellten Programme die zur rechnergest tzten Str mungssimulation notwendigen Arbeitsschritte zu bew ltigen de monstriert werden Resultate bei der Randanpassung Testfall 1 zeigt dass die Randanpassung an einfache Geometrien f r bis zu f nf Unterteilungen ohne die Verwendung von Gl ttern m glich ist wobei die Einhaltung der Qualit tskriterien erf llt ist Als Tendenz kann jedoch festgestellt werden dass mit h herer Unterteilungsstufe die maximalen und minimalen Winkel und L ngenverh ltnisse schlechter werden s Tabelle 6 3 Wird wie in Testfall 2 zu erkennen bei einer einfachen Geometrie die Objektoberfl che gr ber aufgel st werden auch in der f nften Unterteilungsstufe die Qualit tskriterien erf llt Diese sind aber schlechter als bei dem gleichen h her aufgel sten Objekt Die genauen Werte lassen sic
15. Die von der PG erstellte Sammlung von Werkzeugen bietet an vielen Stellen die M glich keit Erweiterungen und Verbesserungen einzubringen So ist z B die Weiterentwicklung und Verbesserung der Gl ttungsalgorithmen denkbar Beispielsweise wurde ein von der PG erdach ter Ansatz der die Randelemente an Hand der Oberfl chennormalen des Objektes ausrichtet lediglich aus Zeitgr nden nicht mehr implementiert Des Weiteren besteht die M glichkeit zus tzliche Schnittstellen zu anderen L sern zu implementieren so K nnte zum Beispiel eine komplette Mehrgitterhierarchie exportiert werden Da InGrid3D die Gitterinformationen auf Basis eines polyedrischen Komplexes speichert ist auch die Verwendung von unstrukturierten Grobgittern m glich Die Einschr nkung auf regu l re kartesische Gitter stellt lediglich einen Tribut an den verwendeten L ser dar Kapitel 7 Entwicklungsprozess Ablauf Prototypen 7 1 Zeitlicher Ablauf 7 1 1 Ablauf der PG im ersten Semester Die Arbeit der Projektgruppe begann mit einer Seminarphase in der sich die Teilnehmer in die Thematik einarbeiteten und ber Grundlagen des Projektgruppenthemas referierten Folgende Themen wurden behandelt e Mathematische Grundlagen e Gitter e Grafikhardware e DirectX e OpenGL e GPGPU e Qt e Tools e Stable Fluids Nach der Seminarphase wurde eine Aufteilung in Einzelgruppen beschlossen die sich folgen den Themen widmeten GPGPU Gitterdeformationstechniken P
16. GODDEKE D STRZODKA R und TUREK S Performance and accuracy of mixed precision solvers in FEM simulations on anisotropic grids International Journal of Par allel Emergent and Distributed Systems IJPEDS 2006 submitted General Purpose Computations on the GPU http gpgpu org GROSSMANN CH und Roos H G Numerik partieller Differentialgleichungen Teub ner 2006 3 Auflage GUSKOV I VIDIMCE SWELDENS und SCHRODER Normal Meshes In Proceedings of the 27th annual conference on computer graphics and interactive techniques Bd 27 S 95 102 ACM Press 2000 ISBN 1 58113 208 5 HACKBUSCH W Iterative L sung gro er schwachbesetzer Gleichungssysteme Oxford Clarendon Press 2002 KASS M WITKIN A und TERZOPOULUS D Snakes Active contour models Inter national Journal of Computer Vision S 321 331 1988 KELLY S Element Shape Testing AnSyS Inc 1998 chapter 13 in Ansys Theory Reference http www ansys com KIM S J KIM C H und LEVIN D Surface simplification using a discrete curvature norm Computers amp Graphics 26 5 657 663 2002 KNUPP P M Matrix Norms and The Condition Number A General Framework to Im prove Mesh Quality Via Node Movement Proceedings 8th International Meshing Round table South Lake Tahoe CA U S A pp 13 22 1999 http www andrew cmu edu user sowen abstracts Kn676 html KOBBELT L P Iterative Erzeugung glatter Interpolanten Dissertation Un
17. dem k nnen andere Organisationen zumeist Hersteller von Grafikkarten auch propriet re Er weiterungen definieren 32 Qt Qt 60 ist eine Klassenbibliothek f r die plattform bergreifende Programmierung graphischer Benutzeroberfl chen GUIs unter C Es stellt viele Funktionen bereit um Anwendungen mit den modernsten graphischen Benutzerschnittstellen zu versehen Qt ist objektorientiert und leicht zu erweitern Es beinhaltet einen einfachen Mechanismus zur Kommunikation zwischen Objekten namens signals and slots Dabei werden bei Ereignissen Signale erzeugt die von Empf ngern aufgenommen werden Diese Signale werden an korrespondierende Funktionen weitergegeben die die Ereignisverarbeitung realisieren Die grafische Benutzeroberfl che der einzelnen Prototypen und des endg ltigen Programms wurden mit Hilfe von Ot erstellt Ein Tutorial ist beispielweise unter 58 verf gbar 3 3 Visual Studio Das Programm Visual Studio 37 ist eine von der Firma Microsoft angebotene integrierte Entwicklungsumgebung f r Hochsprachen Neben der Programmierumgebung und einem De bugger sind noch diverse Werkzeuge zur Unterst tzung des Entwicklers bzw zur Erweiterung 43 44 KAPITEL 3 WERKZEUGE von Team Arbeits Funktionen integriert Visual Studio wurde von der Informatikrechner Be triebsgruppe IRB lizenziert und f r die PG zur Verf gung gestellt und diente als Program mierumgebung f r C 3 4 CVS CVS concurrent versions s
18. lt a lt 178 7 34 655360 4G 2 12 lt lt 179 7 25 655360 Tabelle 6 17 Werte der Qualit tskriterien f r den komplexen Testfall 6 7 Grobgittergenerator HaGrid3D stellt in erster Linie eine Benutzerschnittstelle fiir die Erzeugung und Bearbeitung eines geeigneten Grobgitters fiir ein bestimmtes Objekt zur Verfiigung Der einzige Automatis mus innerhalb von HaGrid3D ist der Inklusionstest zur Klassifizierung von Grobgitterknoten innerhalb des Objektes s Kap 5 2 Im Folgenden wird die Korrektheit des Algorithmus vali diert Wichtigster Bestandteil des Inklusionstests ist die Berechnung des vorzeichenbehafteten Volu mens von Tetraedern Die korrekte Funktionalitat dieser Teilfunktion wurde an Hand verschie dener Beispiele verifiziert Grundlegend wichtig ist es beim Z hlen der Schnitte zu beachten dass in verschiedenen F llen Fehlinformationen zustande kommen k nnten Dies passiert im 6 7 GROBGITTERGENERATOR 107 mer dann wenn ein Schnitt entweder innerhalb einer Kante eines Eckpunkts oder in einer Ebene auftritt Bei dem in HaGrid3D verwendeten Algorithmus werden diese zweideutigen Schnitte umgangen indem im Falle eines solchen ein neuer Referenzpunkt f r den gerade zu berpr fenden Grobgitterknoten randomisiert erzeugt wird und s mtliche Dreiecke des Objek tes erneut auf Schnitt berpr ft werden Da die oben erw hnten zweideutigen Schnitte extrem selten auftreten stellt dieses Verfahren kein Problem
19. 3 15282P 43824E 41856F 13312H 0J Gl ttung Keine C Normale Intelligente Smooth Iter 10 Gitterkorrektur Zeichenoptionen IV Quads Kontrollpunkte I Gitterpunkte Pointsize 3 Gitter zeichnen Kein Obiektrand Rand C Ales Abbildung 7 4 Der 3 Unterteilungsschritt 7 2 PROTOTYPEN 121 72 2 MAPS Prototyp Der MAPS Prototyp bietet eine grafische Oberfl che mit deren Hilfe sich die einzelnen Schrit te zur Erzeugung einer MAPS Parametrisierung visualisieren lassen Mit dem Start des Pro gramms wird automatisch ein Objekt geladen alternativ l sst sich ber den Men punkt Mesh Laden ein beliebiges Objekt im STL Format ffnen Durch Bet tigen der Schaltfl che Get the queued IS wird eine maximal unabh ngige Menge von Knoten des geladenen Objekts markiert gi a amp Freeware maps Mesh Hilfe Get the queued Kiu d IS Hinge Map 1 Conformal Map 1 Remove red Point Remove wholeis Hinge Map 2 Conformal Map 2 Hinge Map 3 Conformal Map 3 einfache 2D Einbettung Modul Test Imini stl erfolgreich geladen 50 Punkte und 96 Fl chen Abbildung 7 5 Der MAPS Prototyp Dies wird visualisiert indem die jeweiligen Eins Ring Nachbarschaften der Knoten aus der unabh ngigen Menge aufgebaut und die zugeh rigen Dreiecke dunkelblau eingef rbt werden Es bestehen f r den Benutzer nun mehrere M glichkeiten fortzufahren Du
20. Benachbarte Grobdreiecke Die Elternknoten werden in benachbarten Grobdreiecken parametrisiert Hier werden die bei den Dreiecke in eine Ebene abgebildet wobei die Abbildungen kongruent zu den Ursprungs dreiecken bleiben Da diese so genannte Scharnier Abbildung engl hingemap zweidimen sional ist ist es jetzt wieder m glich die Verbindungsstrecke zwischen den eingebetteten Elternknoten zu berechnen Falls die Mitte dieser Strecke in der Einbettung liegt wird die ser Mittelpunkt wieder auf die Oberfl che projiziert s Abb 5 14 Falls der Mittelpunkt nicht innerhalb eines der beiden Dreiecke liegt s Abb 5 14 wird eine geeignete Eins Ring Nach barschaft gesucht Fall 3 Eins Ring Nachbarschaft Die Elternknoten liegen in zwei Grobdreiecken die nur einen gemeinsamen Eckpunkt haben oder es konnte im Fall zweier benachbarter Dreiecke kein Grobdreieck gefunden werden In diesem Fall wird die konforme Einbettung der Eins Ring Nachbarschaft dessen Mittelpunkt der gemeinsame Eckpunkt ist berechnet s Kap 5 In dieser Einbettung wird die Mitte der Verbindungsstrecke zwischen den eingebetteten Elternknoten berechnet s Abb 5 14 Liegt diese innerhalb dieser Einbettung wird der Punkt wieder auf die Oberfl che projiziert Da die Einbettung der Eins Ring Nachbarschaft nicht konvex sein muss kann auch hier der Mittel punkt ausserhalb liegen In diesem sehr seltenen Fall wird Fall 4 genutzt 70 KAPITEL 5 SYSTEMBESCHREIBUNG
21. Fall 4 Snake Die Elternknoten liegen in zwei disjunkten Grobdreiecken oder es wurde kein Grobdreieck in den jeweiligen Einbettungen gefunden In diesem Fall kann die Parametrisierung keine Ver bindungslinie zwischen zwei Knoten auf der Oberfl che berechnen und es wird eine Snake s Kap 2 5 benutzt Diese berechnet ein lokales Minimum der Verbindungswege auf dem Pa rameterraum zwischen den eingebetteten Elternknoten Der Mittelpunkt von diesem Weg und das dazugeh rige Dreieck wird als geeigneter Mittelpunkt angesehen und der parametrisierte Punkt auf der Objektoberfl che zum Grobgitter zur ckgeliefert gt Gei a Eine einfache Einbettung b Eine hingemap kann erzeugt werden CG E c Die Verbindungslinie liegt nicht innerhalb d Eine Eins Ring Umgebung vor der Ein der hingemap bettung Abbildung 5 14 M gliche F lle bei der Parametrisierung 5 6 1 Implementierungsdetails Ein gro es Problem bei der Implementierung des oben beschriebenen Algorithmus bestand dar in den richtigen Fall zu ermitteln Objektknoten die bei der Vergr berung s Kap 2 2 3 erhal ten bleiben geh ren zu keinem Grobdreieck und k nnen gleichzeitig in mehrere Grobdreiecke 5 7 GITTERGL TTUNG UND REPARATUR VON SELBSTDURCHDRINGUNGEN 71 eingebettet werden Falls ein solcher Knoten als Elternknoten auftritt m ssen alle angrenzen den Grobdreiecke gepr ft werden Zun chst wird berpr ft ob die zwei Punkte adjazent zuein ander sind
22. Gitter f r Testfall 6 nach drei Unterteilungen 6 3 VALIDIERUNG DER RANDANPASSUNG DURCH PARAMETRISIERUNG 93 Unterteilungsstufe Jacobi Fehler Innenwinkel L ngenverh ltnis Gitterzellen 0 0 50 lt a lt 144 1 63 3375 1 0 29 lt lt 171 2 81 27000 2 0 18 lt a lt 173 4 91 216000 3 45 9 lt a lt 178 12 46 1728000 Tabelle 6 8 Werte der Qualit tskriterien f r Testfall 6 Testfall 7 a Originalobjekt im Gitter b Durch das Gitter angen herte Objektoberfl che Abbildung 6 21 Gitter f r Testfall 7 nach zwei Unterteilungen KAPITEL 6 PROJEKTVALIDIERUNG a Originalobjekt im Gitter b Durch das Gitter angen herte Objektoberfl che Abbildung 6 22 Gitter f r Testfall 7 nach vier Unterteilungen Unterteilungsstufe Jacobi Fehler Innenwinkel L ngenverh ltnis Gitterzellen 0 0 50 lt a lt 130 2 49 125 1 0 50 lt a lt 144 2 81 1000 2 2 30 lt a lt 160 3 20 8000 3 17 17 a 169 3 64 64000 4 77 T lt a lt 177 8 72 512000 Tabelle 6 9 Werte der Qualit tskriterien f r Testfall 7 6 3 VALIDIERUNG DER RANDANPASSUNG DURCH PARAMETRISIERUNG 95 Testfall 8 a Originalobjekt im Gitter b Durch das Gitter angen herte Objektoberfl che Abbildung 6 23 Gitter f r Testfall 8 nach zwei Unterteilungen a Originalobjekt im Gitter b Durch das Gitter angen herte Objektoberfl che Abb
23. J D LUEBKE D GOVINDARAJU N HARRIS M KRUGER J LEFOHN A E und PURCELL T J A Survey of General Purpose Computation on Graphics Hardware In Eurographics 2005 State of the Art Reports S 21 51 2005 48 PHARR Hrsg GPU Gems 2 Programming Techniques for High Performance Graphics and General Purpose Computation Kap 44 A GPU Framework for Solving System of Linear Equation S 703 718 Addison Wesley 2005 49 Pozo R HEROUX M A und REMINGTON K A Sparse BLAS Library Lite and Toolkit Level Specifications Manual BLAS Technical Forum 1997 50 PURCELL T J I BUCK W R MARK und P HANRAHAN Ray Tracing on Program mable Graphics Hardware ACM Transactions on Graphics 21 3 703 712 2002 Pro ceedings of ACM SIGGRAPH 2002 51 RWTH AACHEN OpenMesh http www openmesh org 52 SANDIA CORPORATION http cubit sandia gov 53 SCHREIBER P und S TUREK An Efficient Finite Element Solver for the Nonstationary Incompressible Navier Stokes Equations in Two and Three Dimensions In Proc Work shop Numerical Methods for the Navier Stokes Equations Bd 47 d Reihe Notes on Numerical Fluid Mechanics S 25 28 Vieweg 1993 54 SCHWARZ H R Methode der finiten Elemente 2 Auflage Oxford Clarendon Press 1984 55 SCHWARZ Numerische Mathematik Oxford Clarendon Press 1997 56 The Stanford 3D Scanning Repository http graphics stanford e
24. berechnet den Abstand des Punkts p zum Nullpunkt double angle MyMesh Point x MyMesh Point y MyMesh Point z gibt den inneren Winkel des Dreiecks x y z am Punkt y zur ck double tetaK std vector lt MyMesh Point gt r MyMesh Point pi int k gibt die Summe der Winkel der ersten k Dreiecke gegeben durch die Eckpunktliste r um den Punkt pi zur ck Klasse Maps_Modul dient zur Berechnung des mittleren Punktes zwischen zwei bekannten Punkten auf der Oberfl che des Objektes und zur Bestimmung m glicher Ausweichpunkte zur Gl ttung auf der Ober fl che C 1 BERSICHT BER DIE PAKETE UND KLASSEN VON INGRID3D 161 void setMesh MyMesh mesh MyMesh origmesh Maps_Param maps_param setzt die Referenzen zu den Dreiecksnetzen des Objektes der Vergr berung und der Parametrisierung void setSnake Snake snake_obj setzt die Referenz zur Klasse Snake float find middle int indexl int index2 bool addToList true Gibt einen Punkt auf der Oberfl che zwischen den zwei bekannten Punkten mit index1 und index2 zur ck Diese Mitte wird durch Parametrisierung bestimmt AddToList gibt dabei an ob der berechnete Punkt den bekannten Punkten hinzu gef gt werden soll int add_point int grobdeieck float alpha float beta float gamma int vl int v2 int v3 int feindreieck f gt einen Punkt mit den angegebenen Werten der internen Liste hinzu int add_point int eckpunkt f gt einen Eckpunkt des Dreiec
25. das entweder eine Kante oder einen Knoten mit dem ersten Dreieck gemeinsam hat so kann die Scharnier Abbildung oder die konforme Abbildung zur Einbettung dieser Dreiecke angezeigt werden Die Position des roten Knotens in der 3D Ansicht entspricht der Position des Kreuzes in der 2D Ansicht der Einbettung Freeware maps2 ys Vy Bet the queued Kir IS Hinge Map 1 Conformal Map 1 Remove redPoint Remove whole IS IV V delauneyviem o 3D View IV bien P Punkte PNetz 1 Originaimesh T Parameter Test einfache 2D Einbettung 1 a fp Modul Test H N Hinge Map 2 Conformal Map 2 Hinge Map 3 Conformal Map 3 Anti sl erfolgreich geladen 50 Punkte und 96 Fl chen Abbildung 7 6 Links Dezimiertes Objekt mit der urspr nglichen Oberfl chentriangulierung und Parameterlinien Mitte 2D Einbettung einer Eins Ring Nachbarschaft und Retriangulie rung Rechts Konforme Abbildung einer Eins Ring Nachbarschaft die die beiden farblich markierten Dreiecke enth lt 7 2 3 Snakes Prototyp Der Snakes Prototyp bietet ebenfalls eine grafische Benutzeroberfl che mit der das Verhalten der Snake visualisiert werden kann Beim Start des Prototypen wird automatisch eine Geome trie geladen alternativ k nnen ber das Datei Men auch andere Objekte ausgew hlt wer den Die perspektivische Darstellung des Objektes k
26. einer Simulation unabh ngig gesetzt werden k nnen Als Beispiel kann die Behandlung der Geschwindigkeitsvariablen bei der Simulation der Str mung in einem virtuellen Windkanal mit einem zu umstr menden inneren Objekt dienen Hier liegen zwei Randkomponenten vor der u ere Kanal und das innere Objekt Eine Seite des Kanals dient als Einstr mrand der Wert der Geschwindigkeit wird hier als Dirichlet Randbedingung vorgegeben Ein typischer Fall ist die Vorgabe eines parabolischen Einstr mprofils F r die festen W nde des Kanals und f r das innere Objekt die die Str mung nicht durchdringen darf wird der Wert der Geschwin digkeit explizit auf Null gesetzt Der Kanal wird idealisiert als unendlich lang angenommen d h die Str mung kann am Ausstr mrand den Kanal verlassen und andererseits nie ber diesen Rand wieder einstr men F r den Ausstr mrand werden also keine Randbedingungen gesetzt 10 KAPITEL 2 GRUNDLAGEN Neumann R nder treten beispielsweise bei der Simulation der Verformung unter Druck von mechanischen Bauteilen auf bei denen sich die Geometrie w hrend der Simulation ver ndert F r die Integration der Randbedingungen in das durch die Diskretisierung aufgestellte Glei chungssystem stehen drei Techniken zur Verf gung F r eine ausf hrliche Beschreibung wird auf die Arbeit von Turek 61 verwiesen F r das Gleichungssystem wird vorausgesetzt dass bislang nur nat rlichen Randbedingungen gesetzt wurden Es bezeichne
27. lf Kanten werden nun die vier neuen Fl chen definiert und die alte Fl che wird verworfen Diese vier Fl chen bekommen den gleichen Randstatus wie die urspr ngliche Fl che Unterteilung der Hexaeder Zun chst muss entschieden werden ob der Knoten der in der Mitte des alten Hexaeders er zeugt wird im Objektinneren liegt oder nicht Hat eine der begrenzenden Fl chen des He xaeders den Status Objektinneres befindet sich das Innere des Hexaeders im Inneren des Objektes und damit auch der im Inneren des Hexaeders erzeugte Knoten Falls alle sechs Fl chen des Hexaeders den Status Objektrand haben ist der innere Knoten ebenfalls im Ob jektinneren da dieser Hexaeder dann einen einzelnen unabh ngigen W rfel im Raum darstellt Um nun einen Hexaeder in acht neue kleinere Hexaeder zu unterteilen m ssen zun chst wie bei den Fl chen im Inneren des aktuell betrachteten Hexaeders neue Kanten erzeugt werden Die Startknoten sind die Knoten die bereits bei der Unterteilung der Fl chen in der Mitte der sechs Randfl chen des Hexaeders erzeugt wurden Als Endpunkt wird diesen Kanten der neue Knoten in der Mitte des Hexaeders zugewiesen Abbildung 5 13 Unterteilung der Hexaeder Insgesamt erh lt man 24 Kanten auf der Oberfl che des alten Hexaeders im Inneren der Rand fl chen und sechs Kanten im Inneren des alten Hexaeders Aus diesen werden als n chstes zw lf Fl chen im Inneren des alten Hexaeders konstruiert Bei d
28. lt a lt 158 4 22 1844 0 37 lt a lt 152 3 95 558 0 37 lt a lt 152 3 89 226 0 35 lt lt 154 4 13 92 0 33 lt lt 157 4 54 36 0 24 lt lt 165 5 16 Tabelle 6 14 Einfluss der initialen Objektreduzierung f r Testfall 1 Objekten nicht auszahlt und hohe Reduzierungen hier u erst negative Auswirkungen auf die Qualit tsma e haben Anzahl Restdreiecke Jacobi Fehler Innenwinkel L ngenverh ltnis 80 0 43 lt a lt 144 2 79 62 0 42 lt a lt 144 2 77 48 0 43 lt a lt 144 2 85 38 0 42 lt lt 144 2 83 28 0 34 lt a lt 146 3 00 6 7 3 lt lt 177 9 65 Tabelle 6 15 Einfluss der initialen Objektreduzierung f r Testfall 2 Abschlie end wird Testfall 8 im Hinblick auf die Objektreduzierung betrachtet Das Objekt besteht aus 91536 Dreiecken Die vollst ndigen Ergebnisse sind in den Tabellen 6 14 6 15 und 6 16 zusammengefasst Die in Tabelle 6 16 aufgef hrten X XX bedeuten dass in diesem Testfall ein Programmfehler auftrat s Anhang A 4 6 6 KOMPLEXER TESTFALL Anzahl Restdreiecke Jacobi Fehler Innenwinkel L ngenverh ltnis 25408 XXX XXX XXX 18458 XXX XXX XXX 7184 XXX XXX XXX 1526 XXX XXX XXX 584 0 22 lt a lt 164 3 87 244 0 20 lt lt 162 5 11 86 36 2 lt lt 178 67 71 Tabelle 6 16 Einfluss der initialen Objektreduzierung f r Testfall 8 6 6 Komplexer
29. nnte nun an eine CFD Software wie z B FEATFLOW 11 weitergegeben werden Um im Kon text der PG die Praxistauglichkeit der erzeugten Gitter zu demonstrieren wurde ein L ser auf GPU Basis implementiert Da der L ser nur einen Konzeptnachweis engl proof of concept darstellen sollte beschr nkte sich die PG bei der Umsetzung auf vollst ndig regul re Gitter 46 Die implementierten Gitterunterteilungsalgorithmen sind aber auch problemlos auf un regelm ige Gitter anwendbar ebenfalls w re es m glich durch einige Modifikationen des Programms eine komplette Hierarchie f r ein geometrisches Mehrgitterverfahren 14 zu er zeugen und in entsprechende L ser zu exportieren Urspr nglich sollte die GPU in allen Bereichen zur Beschleunigung eingesetzt werden Es stellte sich jedoch heraus dass die zur Gitterdeformation umgesetzten Techniken aufgrund mangelnder Parallelisierbarkeit nicht GPU tauglich waren vgl Kap 4 1 3 Vorgehensweise der Projektgruppe Als Basis f r die Berechnung dient ein Modell des zu umstr menden Objektes und ein an dieses Objekt angepasstes Grobgitter Das Grobgitter das anf nglich aus wenigen Hexaederelemen ten besteht wird wiederholt unterteilt Die dabei neu entstehenden Randpunkte m ssen an die Oberfl che des Objektes angepasst werden um eine bessere Approximation zu erhalten Die Beschreibung des Objektes wird ber eine Oberfl chentriangulierung vorgegeben auf dieser ist die Bestimmung der neuen Ran
30. sche Einsatzf lle und die Resultate dieser Gl tter Oberfl che Winkel Gl tter Der Gl tter Oberfl che Winkel s Kap 5 7 4 versucht die Knoten des Gitters auf dem Objekt so zu verschieben dass sich die Winkel im Gitter verbessern Da bei komplexen Modellen eine Verschiebung der Knoten auf dem Objekt nur in Abh ngigkeit von Winkelmessungen zu einer Verschlechterung des Gitters f hren kann wird die Kr mung der Oberfl che zus tzlich be r cksichtigt Falls ein einstellbarer Schwellwert durch eine Verschiebung berschritten w rde wird diese nicht durchgef hrt Das in Abbildung 6 28 gezeigte qualitativ schlechte Grobgitter wird nach 70 Iterationen in einen fast optimalen Zustand berf hrt s Abb 6 29 Die genauen Resultate der durchgef hrten Gl ttung lassen sich Tabelle 6 12 entnehmen Iteration kleinster Winkel gr ter Winkel L ngenverh ltnis 20 58 136 1 71 30 66 125 1 51 40 72 116 1 35 50 78 108 1 23 60 84 100 1 16 70 87 92 1 08 Tabelle 6 12 Werte der Qualit tskriterien f r Winkelgl tter a Oberfl che Winkel Gl tter 10 mal ange b Oberfl che Winkel Gl tter 30 mal ange wandt wandt Abbildung 6 28 Der Oberfl che Winkel Gl tter 100 KAPITEL 6 PROJEKTVALIDIERUNG
31. ssten alle m glichen Kombinationen dieser Positionen untersucht werden dies w rde zu exponentiellem Aufwand f hren Winkel Gl ttung Ein wesentliches Qualit tsmerkmal eines Gitters sind die Winkel benachbarter Kanten an ei nem Knoten Idealerweise haben zwei benachbarte Kanten an einem Knoten in einer Ebene einen Winkel von 90 zueinander Je gr er die Winkelabweichung an den Knoten ist desto schlechter ist die Qualit t des Gitters Daher ist es sinnvoll in den Bereichen starker Winkel abweichungen diese durch eine Positionsver nderung der Knoten zu verbessern Wird durch das Verschieben des Knotens auf dem Feinnetz lokal das Winkelverh ltnis verbessert wird die neue Position bernommen F r jeden Knoten auf der Objektoberfl che werden zun chst al ternative Positionen berechnet und anschliessend bewertet Zur Bestimmung der alternativen Positionen ist es entscheidend wo sich der Knoten auf dem Objektrand befindet e Liegt er auf einem Punkt des Feinnetzes so kommen f r ihn als neue Positionen Punkte aus seiner Eins Ring Nachbarschaft in Frage e Liegt er innerhalb eines Feindreieckes so sind die Eckpunkte des Dreiecks die m glichen Kandidaten f r neue Positionen des betroffenen Knotens Die Bewertung basiert auf den Winkelabweichungen der Kanten an den jeweiligen Positio nen Ist eine der m glichen Positionen besser bewertet worden als die aktuelle Position so wird der Gitterknoten an diese verschoben Knoten an mar
32. tig war So wird die Snake nur auf kurzen ann hernd plana ren Teilst cken der Objektoberfl che eingesetzt die problematischen Aus und Einbuchtungen wurden zuvor durch die Parametrisierung entfernt 66 KAPITEL 5 SYSTEMBESCHREIBUNG Abbildung 5 10 Links Die grob aufgel ste Geometrie f hrt zu einer ung nstigen Initialisie rung der Snake diese erreicht dadurch die optimale Lage nicht sie h lt vor einer Ausbuchtung blaue Markierung bereits fr hzeitig an Rechts Zur Verdeutlichung die gleiche Situation aus einer anderen Perspektive die Ausbuchtung ist nun deutlich zu erkennen 5 5 Gitterunterteilung 5 5 1 Datenstuktur Die Gitterstruktur wird als polyedrischer Komplex gespeichert Dabei bilden Knoten die null dimensionalen Kanten die eindimensionalen Vierecke die zweidimensionalen und Hexaeder die dreidimensionalen Polyeder Der Knoten besteht aus den Koordinaten im Raum und der Information ob er ein Objektrandpunkt ist bzw eine solid Markierung hat Die Kanten werden ber einen Startpunkt und einen Endpunkt definiert die viereckigen Fl chen werden ber vier Kanten definiert und die Hexaeder bestehen wiederum aus sechs Fl chen Die Kanten und die Fl chen speichern wie die Knoten eine Information dar ber ob sie am Objektrand oder im Inneren des Objektes liegen den sogenannten Randstatus e Standard Der Polyeder liegt im freien Raum au erhalb des Objektes e Objektrand Der Polyeder liegt auf der Obj
33. und Ver wendung der Snakes s Kap 5 4 an Hand der vorgestellten Qualit tskriterien f r die Test f lle 1 bis 8 berpr ft Es werden keine Gl ttungsoperatoren oder Korrekturen von Gitter Selbstdurchdringungen angewendet Testfall 1 a Originalobjekt im Gitter b Durch das Gitter angen herte Objektoberfl che Abbildung 6 9 Gitter f r Testfall 1 nach zwei Unterteilungen 6 3 VALIDIERUNG DER RANDANPASSUNG DURCH PARAMETRISIERUNG 85 a Originalobjekt im Gitter Abbildung 6 10 Gitter f r Testfall 1 nach f nf Unterteilungen b Durch das Gitter angen herte Objektoberfl che Unterteilungsstufe Jacobi Fehler Innenwinkel L ngenverh ltnis Gitterzellen 0 0 87 lt a lt 92 1 08 26 1 0 52 lt a lt 126 2 90 208 2 0 40 lt a lt 150 3 00 1664 3 0 31 lt a lt 160 4 68 13312 4 0 25 lt a lt 161 5 49 106496 5 0 22 lt a lt 161 6 24 851968 Tabelle 6 3 Werte der Qualit tskriterien f r Testfall 1 86 KAPITEL 6 PROJEKTVALIDIERUNG Testfall 2 a Originalobjekt im Gitter b Durch das Gitter angen herte Objektoberfl che Abbildung 6 11 Gitter f r Testfall 2 nach zwei Unterteilungen a Originalobjekt im Gitter b Durch das Gitter angen herte Objektoberfl che Abbildung 6 12 Gitter f r Testfall 2 nach f nf Unterteilungen 6 3 VALIDIERUNG DER RANDANPASSUNG DURCH PARAMETRISIERUNG 87 Unterteilungsstufe Jaco
34. wird diese Berechnung nicht funktionie ren man w hlt dann einfach die nachfolgenden Segmente der Snake und verwendet lediglich zur Berechnung von a dann die entsprechende Kante der Oberfl che auf der der Snaxel liegt Nachdem die Geschwindigkeiten f r alle Snaxel berechnet sind wird ein Zeitschritt At be rechnet und zwar so dass kein Snaxel ber das Ende einer Kante hinauswandert At min 1 ds 05 2 19 Wenn ein Snaxel nun am Ende einer Kante auf einen Knoten der Valenz n trifft wird der Snaxel in n 1 neue Snaxel aufgeteilt die auf die ausgehenden Kanten gesetzt werden Durch diese Aufteilung kann die zweite Konsistenzbedingung verletzt werden dies kann aber wie bereits erw hnt relativ einfach behoben werden s Abb 2 15 2 6 GPGPU GPGPU bedeutet general purpose computation using graphics hardware d h es werden Gra fikkarten benutzt um allgemeine Probleme wie z B die Matrix Vektor Multiplikation zu 16 sen Durch die in der Pipeline aktueller Grafikkarten frei programmierbaren Vertex und Pi xelshader kann man die Grafikkarte als Stream Prozessor auffassen Passende Programmier techniken vorausgesetzt erlaubt die Grafikkarte eine Vielzahl von Probleml sungen welche die Geschwindigkeiten normaler CPU L sungen bei weitem bersteigen und somit ein besse res Preis Leistungs Verh ltnis bieten Zus tzlich gibt es frei zug ngliche Shadersprachen mit denen man die GPUs effizient auf Hochsprachen Niveau
35. 16 Gitter f r Testfall 4 nach drei Unterteilungen 90 KAPITEL 6 PROJEKTVALIDIERUNG Unterteilungsstufe Jacobi Fehler Innenwinkel L ngenverh ltnis Gitterzellen 0 0 42 lt a lt 126 3 30 1000 1 0 42 lt lt 132 3 29 8000 2 0 42 lt lt 141 3 29 64000 3 0 42 lt lt 142 3 79 512000 Tabelle 6 6 Werte der Qualit tskriterien f r Testfall 4 Testfall 5 a Originalobjekt im Gitter b Durch das Gitter angen herte Objektoberfl che Abbildung 6 17 Gitter f r Testfall 5 nach zwei Unterteilungen 6 3 VALIDIERUNG DER RANDANPASSUNG DURCH PARAMETRISIERUNG 91 a Originalobjekt im Gitter Abbildung 6 18 Gitter f r Testfall 5 nach f nf Unterteilungen b Durch das Gitter angen herte Objektoberfl che Unterteilungsstufe Jacobi Fehler Innenwinkel L ngenverh ltnis Gitterzellen 0 0 49 lt a lt 150 2 14 64 1 3 19 lt lt 159 4 70 512 2 23 9 lt a lt 177 5 64 4096 3 80 0 lt a lt 180 10 88 32768 4 149 0 lt a lt 180 25 07 262144 Tabelle 6 7 Werte der Qualit tskriterien f r Testfall 5 92 KAPITEL 6 PROJEKTVALIDIERUNG Testfall 6 a Originalobjekt im Gitter b Durch das Gitter angen herte Objektoberfl che Abbildung 6 19 Gitter f r Testfall 6 nach zwei Unterteilungen a Originalobjekt im Gitter b Durch das Gitter angen herte Objektoberfl che Abbildung 6 20
36. 2 um die Untertei lung zu beschleunigen Die Hexaeder speichern ihren Jacobi Wert und einen Booleschen Wert der anzeigt ob ein Jacobi Fehler vorliegt Dieser wird im Folgenden als Integerwert behandelt In Tabelle 6 19 ist zusammenfassend der Speicherbedarf aller Gitterelemente aufgelistet Die rechte Spalte zeigt wie viele Elemente durch eine Unterteilung entstehen Die Formeln dazu ergeben sich aus dem Ablauf des Unterteilungsprozesses Dabei steht H f r die Anzahl der Hexaeder F f r die Anzahl der Fl chen K f r die Anzahl der Kanten und N f r die Anzahl der Knoten im zu unterteilenden Netz Der Speicherverbrauch des Gitters h ngt somit nicht nur von der Anzahl der Hexaeder ab sondern auch davon wie diese zusammenh ngen Element Referenzen Flie komma Integer Unterteilungsfaktor Knoten 0 6 3 3 N E F H Kanten 2 4 1 0 3 2E 4F 6H Flachen 4 2 1 1 2 4F 12H Hexaeder 6 0 1 1 8H Tabelle 6 19 Auflistung der Gitterelemente und ihr Speicherverbrauch Testfall Speicherverbrauch in MB 0 P 1 2 3 4 5 Kugel 324 590 591 592 598 638 1102 Auto 102 178 180 187 264 769 Tabelle 6 20 Tabelle zum Speicherverbrauch exemplarischer Testf lle In Tabelle 6 20 ist der Speicherverbrauch f r die Testf lle der hochaufgel sten Kugel sowie des Autos f r bis zu f nf Unterteilungen aufgelistet Die Spalte 0 stellt den initalen Speicherver
37. 3 Modul MAPS CIA Modul GPU L ser C 2 bersicht ber die Klassen von HaGrid3D D Lizenz Literaturverzeichnis INHALTSVERZEICHNIS Kapitel 1 Einleitung Motivation Einordnung Grenzen 1 1 Anforderung Ziele Motivation Die Aufgabe der Projektgruppe PG bestand darin eine Softwareumgebung zur numerischen Str mungssimulation zu entwickeln Dabei sollte insbesondere die Leistungsf higkeit moder ner Grafikkarten ausgenutzt und entsprechende 3D Gittermanipulationstechniken verwendet werden Str mungsvorg nge treten in der Natur in einer Vielzahl verschiedenster Situationen auf man denke beispielsweise an meteorologische Vorg nge wie Wind und Meeresstr mungen Luft und Benzinstr mungen in Automotoren Turbinen und Triebwerken sowie Umstr mungen zur Analyse des Luft bzw Wasserwiderstandes komplexer Objekte wie Automobile oder Schiffe Um diese Vorg nge qualitativ und quantitativ zu untersuchen gibt es zwei grunds tzliche Vor gehensweisen das Experiment und die Simulation Im Experiment wird ein Modell der Wirklichkeit h ufig in ver ndertem Ma stab konstruiert und an diesem werden dann Messungen durchgef hrt In der Automobilindustrie platziert man beispielsweise w hrend der Designphase ein verkleinertes Modell eines Prototyps in einem Windkanal um seinen Luftwiderstand zu messen In der Simulation geht man im Gegensatz dazu abstrakter vor Man versucht mit Hilfe der
38. Dieses Konzept besagt dass ein kleiner Instruktionskernel unabh ngig auf verschiedene Daten angewendet wird Erst nach dem kompletten Abarbeiten des Datensatzes kann auf die neu berechneten Werte zugegriffen wer den Der Instruktionskernel wird im Grafikprozessor von mehreren parallel geschalteten Sha dern abgearbeitet Um Grafikkarten zur allgemeinen Berechnung sinnvoll nutzen zu K nnen muss dieses Konzept effizient auf die Problemstellung anwendbar sein Innerhalb einer Grafikkarte werden Daten in Texturen gespeichert Texturen sind zweidimen sionale Felder von Texeln Ein Texel kann aus bis zu vier Skalaren bestehen Diese Organisation der Daten ist durch die eigentliche Aufgabe der Grafikkarte der Darstellung einer dreidimen sionalen Szene bedingt Ein Texel welcher nach vollst ndiger Berechnung zum Pixel auf dem Bildschirm wird besteht aus drei Skalaren f r die Farbkan le Rot Gr n und Blau sowie einem weiteren Skalar f r Transparenz Es werden auch 1D und 3D Texturen nativ von aktuellen Grafikkarten unterst tzt Die Benutzung f hrt jedoch zu Geschwindigkeitseinbu en Kernel die auf einer GPU ausgef hrt werden beschreiben wie ein Bild gerendert werden soll Vertexshader manipulieren geometrische Informationen Knoten Normalen usw w h rend Fragmentshader auf den Daten von einzelnen Fragmenten z B interpolierten Farb und Tiefeninformationen arbeiten 2 6 2 Shader und Metasprachen Shadersprachen Um die einz
39. Fehler ebenfalls in der grafischen Benutzer oberfl che angezeigt s Abb 7 4 7 2 PROTOTYPEN pitter_v2 Gitter unterteilen Unterteilen 0 144E 108F 26H QJ Gl ttung Keine Normale C Inteligente Smooth Iter 10 E Gitterkorrektur Zeichenoptionen Quads Kontrollpunkte Gitterpunkte Pointsize 3 Bette Gitter zeichnen C Kein Objektrand C Rand Alles Abbildung 7 1 Der Prototyp im Ausgangszustand Wi pgitter v2 Gitter unterteilen Unterteilen 1 342P 876E 744F 208 0J Gl ttung Keine C Normale C Intelligente Smooth Iter 10 Gitterkorrektur Zeichenoptionen IV Quads Kontrollpunkte Gitterpunkte Pointsize 3 vi j Gitter zeichnen Kein Objektrand Rand Ales 119 Abbildung 7 2 Nach Dr cken der Unterteilen Schaltfl che wird das urspr ngliche Gitter unterteilt 120 pitter_v2 Gitter unterteilen Unterteilen 2 2170P 5976E 5472F 1664H 0J Gl ttung Keine Normale C Inteligente Smooth Iter 10 Iv Gitterkorrektur Zeichenoptionen Quads Kontrollpunkte Gitterpunkte Pointsize 3 Bitter zeichnen C Kein Objektrand C Rand C Ales KAPITEL 7 ENTWICKLUNGSPROZESS Abbildung 7 3 Der 2 Unterteilungsschritt Die Objektrand Sicht dient zur besseren Betrach tung des entstandenen Gitters Wi pgitter v2 Gitter unterteilen Unterteilen
40. Filte rungsoperatoren n tig 2 1 5 L sung des Gleichungssystems Es gibt zwei gro e Klassen an Verfahren zur L sung von linearen Gleichungssystemen die direkten und die iterativen Verfahren Die direkten Verfahren liefern die L sung nach einem Schritt sind daf r aber sehr rechenaufw ndig Die iterativen Verfahren sind pro Schritt weni ger rechenintensiv ben tigen aber mehrere unter Umst nden sehr viele Schritte um die L sung zu liefern Es tritt jedoch das Problem auf dass nicht alle Verfahren in allen Situationen auch konvergieren d h im Grenzwert die L sung bestimmen Bieten diese Verfahren aber eine M glichkeit zur Fehlersch tzung so kann in jedem Schritt beurteilt werden wie gut die Ap proximation bereits ist was in praktischen Szenarien vollkommen ausreicht Die Darstellung in diesem Kapitel basiert gr tenteils auf den B chern von Meister 36 und Hackbusch 20 beide stellen neben den Grundlagen und Konvergenzbeweisen auch ausf hrliche spezialisierte Verfahren f r den Fall d nn besetzter Matrizen einer festen Struktur vor Dar ber hinaus enth lt das Lehrbuch von Meister auch die Ergebnisse experimenteller Analysen des Konvergenzver haltens iterativer Verfahren f r typische Modellprobleme F r Details wird auf diese Quellen verwiesen 2 1 GUNDLAGEN DES CFD 11 Direkte Verfahren In der Praxis ist die Programmbibliothek UMFPACK f r kleine Probleme ca 10000 Unbe kannte hochperformant Sie bietet h
41. Grobgittergenerator und InGrid3D geschaffen um das erzeugte Grobgitter dort laden und weiter verwenden zu k nnen Die Daten strukturen werden bin r gespeichert um sie zu einem sp teren Zeitpunkt in InGrid3D einlesen zu k nnen Der Grobgittergenerator durchl uft die schon im Speicher vorhandenen Knoten Instanzen und schreibt die Informationen in eine Datei Die Dateiformate werden im Anhang A 3 im Detail vorgestellt 5 2 6 Visualisierung Mit zunehmender Anzahl an Hexaederzellen verliert die Darstellung des Grobgitters stark an bersichtlichkeit s Abb 5 3 Um dem entgegenzuwirken wurden verschiedene Ans tze dis kutiert Zun chst wurden die vier verschiedenen Ansichten s Abb 5 1 implementiert In den 2D Fenstern wird die Ansicht per Tastendruck um 180 Grad gedreht um damit auf die jewei lige R ckseite zu schalten Die perspektivische Ansicht wird auf Tastendruck in den Vollbild modus gebracht Ein weiterer Punkt zur Verbesserung der bersicht ist das Anzeigen nur der interessanten Kno ten Per Auswahlfeld lassen sich in der Bedienungsoberfl che die restlichen Knoten ausblen den da sie die Sicht auf das Objekt versperren k nnen Interessante Knoten sind solche die auf einer Kante liegen die den Objektrand schneidet Sie werden ber die solid Markierung identifiziert Ebenso l sst sich die bersicht verbessern indem nicht alle Hexaederzellen angezeigt werden m ssen um ein Grobgitter zu erzeugen So kann die Anzahl vo
42. Grossman und Roos 18 Die Auslenkung einer Membran ist ein zweidimensionaler Anwendungsfall f r das so genann te Poissonproblem Die Membran sei am Rand eingespannt und werde durch eine vertikale Kraft f x x Q belastet Gesucht ist die Auslenkung u x mit x Q unter der Einspann bedingung u x 0 f r x OQ Zur Herleitung betrachtet man die Gesamtenergie J u des Systems die sich zusammensetzt aus Spannungsenergie J u und potentieller Energie Jo u Die Spannungsenergie ist proportional zur Oberfl chen nderung und zus tzlich abh ngig von einem Elastizit tsfaktor a Eine ausf hrliche Herleitung ergibt A TO a 2 f VP a9 f fua Jo f dQ bedeutet hierbei dass ber das gesamte Gebiet integriert wird J u und J2 u sind also die Resultate mehrdimensionaler Integration J u 2 1 GUNDLAGEN DES CFD 7 Eine Funktion u u x ist die gesuchte Auslenkung falls sie das Prinzip der minimalen Energie erf llt lt J v f r alle zul ssigen Auslenkungen v bzw lt J u ev f r alle gt 0 und alle zul ssigen Auslenkungen v Das Auslenkungsproblem ist also auf das folgende Minimierungsproblem zur ckgef hrt wor den J u ev _ 0 f r alle zul ssigen Funktionen v 2 1 Die in Gleichung 2 1 gew hlte Notation soll verdeutlichen dass J u ev gerade 0 sein Minimum annimmt und somit das Prinzip der minimalen Energie wie gew nscht erf llt wird Man erh lt nach weiteren Umformung
43. In diesem Fall w rde die Transformation auf das Referenzelement zu Fehlern in der Simulation f hren die letztendlich das gesamte Simulationsergebnis unbrauchbar machen w rden Die Erkennung solcher Invertierungen oder Durchdringungen erfolgt durch die Berechnung der zuvor erw hnten Jacobi Determinanten M glichkeiten zur Behandlung dieses Problems werden in Abschnitt 2 4 vorgestellt 2 3 GITTER 27 Abbildung 2 12 Eine invertierte Hexaederzelle 2 3 3 Glattungsmethoden Gittergl ttung bezeichnet den Vorgang ein existierendes Gitter allein durch lokale Koordi natenverschiebung von Knoten so zu ver ndern dass die einzelnen Gitterzellen im Mittel eine h here Qualit t bzgl verschiedener Qualit tskriterien s Kap 2 3 2 erreichen In diesem Ab schnitt werden verschiedene Gl ttungsverfahren vorgestellt Laplace Gl ttung Der Laplace Gl tter durchl uft alle Knoten des Gitters und berechnet f r einen Knoten p seine neuen Koordinaten Pneu aus den umliegenden Knoten wie folgt a 1 SEET j 2 1 PT 2s c ne q Adj p Dabei ist a 0 1 ein Gewichtungsfaktor der die lineare Interpolation zwischen alter und neuer Position steuert a 0 5 ist ein guter Ausgangswert Die Menge Adj p enth lt f r jeden Knoten p die Knoten die mit p durch eine Kante verbunden sind Da die Koordinaten des neuen Knotens Pneu das Mittel der umliegenden Knoten q Adj p sind kann es an nicht konvexen R ndern
44. Ma thematik ein Modell zu bilden und dieses mit Computern auswerten zu lassen Ein so genannter Simulationszyklus besteht aus vier wesentlichen Schritten 1 Modellbildung Ein physikalisches Ph nomen wird durch eine Reihe von mathemati schen Gleichungen beschrieben F r die Str mungssimulation sind dies die sogenann ten Navier Stokes Gleichungen 53 ein System partieller Differentialgleichungen Ei ne L sungsformel f r diese Gleichungen existiert nicht daher ist man auf numerische Verfahren angewiesen die eine N herungsl sung iterativ berechnen 2 Diskretisierung Das Modell wird diskretisiert d h in eine f r den Computer verarbeit bare Form gebracht Dies geschieht beispielsweise mit der Methode der Finiten Elemente 2 KAPITEL 1 EINLEITUNG FEM oder mittels so genannter Finiter Differenzen FD 54 Man erh lt nach einiger mathematischer Arbeit gro e lineare Gleichungssysteme 3 Berechnung Die L sung dieser Gleichungssysteme liefert gro e Mengen an diskreten Rohdaten 4 Aufbereitung Mit Hilfe geeigneter Visualisierungstechniken werden die Rohdaten in eine f r den Anwender interpretierbare Form gebracht Die wissenschaftliche Disziplin des CFD computational fluid dynamics 28 63 besch ftigt sich mit der Vorhersage von Str mungsvorg ngen durch eben diese Simulationen CFD ist ein interdisziplin res Forschungsgebiet es beinhaltet Aspekte aus so verschiedenen Bereichen wie den klassischen Naturwis
45. Objekt angeschmiegt wird Beide Konzepte erwiesen sich letztendlich f r die Ziele der PG als ungeeignet da lediglich auf die Approximation einer Oberfl chen eingegangen die n tigen Qualit tsmerkmale eines adjazenten Gitters zu dieser Oberfl che jedoch nicht betrach tet wurden Die Methode des Gradient Vector Flow wurde ebenfalls auf die dritte Dimension erweitert 67 der Nachteil der fehlenden Ber cksichtigung eines adjazenten Gitters liegt aber auch hier vor 2 5 3 Snakes auf Oberfl chentriangulierungen Die von der PG benutzte Snakes Technologie basiert vollst ndig auf dem Ansatz von Kob belt et al 3 die Autoren waren so freundlich w hrend der Implementierung bei Fragen zur Verf gung zu stehen 2 5 AKTIVE KONTUREN 35 Konsistenzbedingung Die Snake wird durch einen Polygonzug im dreidimensionalen Raum repr sentiert f r den zwei Bedingungen gelten m ssen 1 Die Knoten des Polygonzuges m ssen auf den Kanten der Oberfl chentriangulierung liegen 2 Die einzelnen Streckenabschnitte des Polygonzuges m ssen innerhalb eines Dreieckes der Oberfl chentriangulierung liegen Weiterhin hat jeder Knoten s IR des Polygonzuges der von den Autoren auch Snaxel ge nannt wird eine Richtung und wird wie folgt beschrieben s 1 d vt amp onm d 0 1 wobei Vgom und Vto die Endpunkte der Kante auf der Oberfl chentriangulierung sind Die Richtung definiert sich von nach vio Es ist w
46. Qualit tstests des Gitters aufgelistet Q Kein Eintrag in der Tabelle bedeutet dass diese Untertei lungsstufe nicht mehr erreicht werden konnte da nicht gen gend Arbeitsspeicher zur Verf gung stand Speicherverbrauch In Kapitel 5 5 wurde die Datenstruktur des Gitters beschrieben Neben den dort beschriebenen Referenzen der Elemente untereinander den Koordinaten und dem Randstatus werden noch einige weitere Daten gespeichert Die vier verschiedenen Elemente Knoten Kante Fl che 112 KAPITEL 6 PROJEKTVALIDIERUNG Testfall Laufzeit in Sekunden P 1 Ql 2 Q2 3 Q3 4 Q4 5 Q5 Kugel 28 3 4 7 0 0 55 0 1 86 0 5 24 6 4 1 1124 34 9 Auto 6 5 5 9 0 0 12 6 0 4 59 1 2 9 247 5 22 9 Tabelle 6 18 Tabelle zum Laufzeitverhalten und Hexaeder werden in vier Vektoren gespeichert Jedes Element speichert seinen Index in nerhalb des jeweiligen Vektors als Integerzahl Die Knoten besitzen einen weiteren Index der jedoch nur f r Randknoten relevant ist er dient der Kommunikation mit dem Modul MAPS Die Kanten speichern weiterhin eine Richtungsinformation X Y oder Z Richtung um das Gitter gerichtet durchlaufen zu k nnen In jeder Fl che wird f r die Reparatur Prozedur das Kantenverh ltnis festgehalten Sowohl Kanten als auch Fl chen speichern bei der Unterteilung eine Referenz auf den auf ihrem Mittelpunkt erzeugten Punkt s Kap 5 5
47. Schlu folgerungen Die Qualit t der durch Unterteilung erzeugten Hexaedergitter steigt und f llt mit der Qualit t der initial verwendeten Grobgitter Leider konnten im Verlauf der PG keine konkreten Kriterien definiert werden die ein gutes Grobgitter beschreiben Der Erfolg bei der Erstellung eines geeigneten Gitters h ngt also von der Erfahrung des Anwenders ab Bis zu einem gewissen Grad lassen sich bei der Unterteilung auftretende Probleme durch die Verwendung der Gl tter beheben aber auch hier ist die Erfahrung des Anwenders wichtig um entscheiden zu K nnen welcher Gl tter im konkreten Problemfall eine Verbesserung bringen k nnte Die Komplexit t des Geometrieobjektes ist ebenfalls ein wichtiger Faktor Bei einfachen Objekten lassen sich auch relativ einfach die dazugeh rigen Grobgitter entwerfen deren Qualit t oft schon so gut ist dass der Einsatz von Gl ttern kaum noch Verbesserungen bringt Bei komplexen Objekten ist sowohl der Entwurf eines geeigneten Grobgitters eine anspruchsvolle Aufgabe als auch die Entscheidung zu welchem Zeitpunkt welcher Gl tter eingesetzt wird Ebenfalls spielt es eine Rolle in welcher Unterteilungsstufe des Gitters ein Gl tter angewandt wird So kann beispiels weise pr ventiv in jeder Unterteilungsstufe gegl ttet werden ein Einsatz der Gl tter erst bei 116 KAPITEL 6 PROJEKTVALIDIERUNG auftretenden Problemen stellt ebenso eine geeignete Vorgehensweise dar Die Parametrisier
48. Schritt kann das Objekt im Grobgitter an eine geeignete Position verschoben werden s Abb A 9 Unter Verwendung der T Taste wird das Grobgitter bei gedr ckter linker Maustaste in den 2D Ansichten in die gew nschte Richtung gezogen A 2 TUTORIAL Datei Help ei A Ee Dokumente und Einstellungen klaus Elgene Dateien cvs grobaitter binjtutorial_objekt sti96 Punkte und 192 Fl chen Grobgilter Parameter Kantenl nge BTH ry E mo CH Grobaitter erzeugen Knotenmarkierungen setzen T Objekt An 1 C Transparent Aus Alle Knoten innerhalb einer Box um Objekt interest und innere Knoten nur interest Knoten V Hexaeder anzeigen I nur die Schnittkanten anzeigen Hexaederseitenflachen auf dem Objekt Punktgr sse 131 Abbildung A 8 Anpassen der Kantenl nge der Hexaederzellen an das Objekt und Festlegen der Anzahl an Hexaederzellen in den drei Dimensionen x y z Wi Freeware grobeitter Datei Help C Dokumente und Einstellungen klaus Eigene Dateien cvs arabaitter bin tutorial_objekt stl98 Punkte und 192 Fl chen Grobgitter Parameter Kantenl nge 27 BIH kyz Grobgitter erzeugen Knotenmarkierungen setzen Objekt An C Transparent C Aus Ansicht Alle Knoten C innerhalb einer Box um Objekt interest und innere Knoten nurinterestKnoten V Hexaeder anzeigen JV nur die Schnittkanten anzeigen Hexaederssitenfl chen auf
49. aufgef llt werden Anschlie end kann es jedoch nur in ein unstrukturiertes Hexa edergitter berf hrt werden indem jedes Tetraeder in vier Heaxeder unterteilt wird s Abb 4 1 b Zwar bietet Cubit einige Operationen an mit deren Hilfe das Differenzvolumen in regul re He xaederzellen unterteilt werden k nnen soll jedoch befinden sich diese noch im Beta Stadium und liefern nur f r sehr einfache Objekte regul re Gitter Die Methode Plastering versucht die Volumendifferenz mit Quadern aufzuf llen Dieses setzt ein Objekt voraus welches einer Blockstruktur hnelt s Abb 4 2 Mapping funktioniert nur bei Volumen die sechs logische Seiten haben und acht logische Ecken Die Unterteilung erfolgt jeweils bei gegen berliegenden Seitenfl chen Die Oberfl chentriangulierungen die in der Projektgruppe Verwendung finden werden zudem nur indirekt unterst tzt Das Objekt muss erst in ein Volumen konvertiert werden damit es in Cubit verwendet werden kann Weitere Informationen ber die Operationen von Cubit k nnen im Handbuch 52 nachgelesen werden a Volumendifferenz mit Subtract b Unstrukturiertes Hexaedergitter mit THex Abbildung 4 1 Testmodell in Cubit 4 4 GPGPU 49 N SL EN M SSS SS SS gt SS Same ST Abbildung 4 2 Mit der Methode Plastering erzeugte reguldre Grobgitter 4 4 GPGPU Da es zur Zeit viele u
50. berf hren Implementierung Die Hauptkomponenten des Reparatur Moduls sind Funktionen zum Auffinden von invertier ten Elementen ein L ser f r lineare Programme Ipsolve s Kap 3 9 und eine Klasse zum Aufstellen des linearen Programms Dem Auffinden von invertierten Elementen liegen die Kri terien aus Kapitel 2 4 2 zugrunde Daher werden zuerst die Jacobi Determinanten an den acht Eckknoten des Hexaeders berechnet Falls die Anzahl negativer Jacobi Determinanten gr er oder gleich f nf ist ist das Element invertiert Ist die Anzahl negativer Jacobi Determinanten null oder eins so wird das Element als g ltig angesehen Liegt die Anzahl negativer Jacobi Determinanten zwischen diesen Werten so muss getestet werden ob es benachbarte Eckknoten gibt an denen negative Jacobi Determinanten vorkommen Es wird nun das Optimierungspro blem min cly unter der Bedingung Ay b y gt 0 aufgestellt und gel st Die Komponente zum Aufstellen des linearen Programms erh lt suk zessive einen der zuvor berechneten ung ltigen Hexaeder als Eingabe Es werden die Determi nanten aus Kapitel s Kap 2 4 berechnet daraus ergibt sich die Matrix A und der Vektor cl Hinzu kommt ein Vektor b IR dessen erste drei Komponenten Null sind und die letzte Eins Damit l sst sich das primale LP aufstellen welches an an den L ser weitergegeben wird der 72 KAPITEL 5 SYSTEMBESCHREIBUNG L sungen f r das primale und duale Problem errechnet Die neuen
51. betrachtet werden und anschlie end an Hand eines komplexen Testfalles das Gesamtsystem evaluiert wird Kapitel 7 befasst sich mit dem zeitlichen Ablauf des Projektes und bietet einen kurzen ber blick der erstellten Prototypen Der Anhang gliedert sich in drei Bereiche Im Benutzerhandbuch Anhang A wird die Bedie nung des Systems in Form von Anleitungen erkl rt Das Pflichtenheft Anhang B beinhaltet eine detaillierte Beschreibung der in der PG erstellten Software Die Programmierschnittstelle Anhang C des Systems wird in diesem Bericht in Kurzform auf Klassenebene und auf Metho denebene dokumentiert Der Bericht schlie t mit dem Abdruck der verwendeten Lizenz und einem umfassenden Literaturverzeichnis Eine kurze Projektvorstellung und der Quellcode finden sich auf der PG Homepage Ihttp 1s7 www cs uni dortmund de students projectgroups pg471 shtml Kapitel 2 Grundlagen Grundbegriffe und ben tigtes Hintergrundwissen 2 1 Gundlagen des CFD Hier sollen zun chst mathematische Grundlagen im Bereich der numerischen Str mungssimu lation aufgezeigt werden Die Darstellungen gehen zum berwiegenden Teil auf G ddeke 14 zur ck 2 1 1 Notationen Es werden offene Gebiete IR betrachtet f r d 1 2 3 mit dem Rand 02 Ortspunk te x Q werden mit x xz1 ta Zeitpunkte mit I C R bezeichnet F r d dimensionale Vektoren a b wird das bliche euklidische Skalarprodukt mit a b und die euklidisc
52. chengl tters behoben werden konnten Trotz verschiedener heuristischer Ans tze das Grobgitter zu verbessern oder die verbleibenden Zell durchdringungen durch Gl ttereinsatz zu beheben konnte dieses Ziel in diesem Testfall nicht erreicht werden Resultate des GPU L sers F r den von der PG realisierten GPU L ser l sst sich Folgendes festhalten Der L ser liefert bei einem visuellen Vergleich identische Resultate zu einer CPU basierten Referenzimplemen tierung vgl Abbildungen 6 36 6 37 und 6 38 Dies gilt f r alle exemplarisch evaluierten Testf lle und deckt sich mit den Untersuchungen von G ddeke Strzodka und Turek 16 Eine numerisch h here Genauigkeit ist ohne zus tzlichen mathematischen Aufwand nicht zu errei chen In Kombination mit der schlechten Konditionierung der aufgestellten Finite Differenzen Matrix kann dies zu unverh ltnism ig hohen Iterationszahlen f hren Aufgrund eines best tigten Fehlers im NVIDIA Treiber konnten wichtige Optimierungen der Implementierung nicht umgesetzt werden Deshalb wurde auf einen direkten Leistungsver gleich zwischen CPU und GPU verzichtet Abschlie end kann gesagt werden dass der L ser die von der PG gestellten Anforderungen erf llt Er demonstriert dass die mit InGrid3D erstellten Gitter prinzipiell zur Str mungssimu lation unter Verwendung des Finite Differenzen Verfahrens geeignet sind 6 11 Fazit Aus den erzielten Ergebnissen der Projektgruppe ergeben sich mehrere
53. der Hierarchiestufen Z von der Gr enordnung O log N ist Zusammenfassend kann man sagen dass eine Netzvereinfachung durch eine Kno tenentfernung gefolgt von einer Retriangulierung erfolgt Diese ist notwendig da durch die Knotenentfernung sonst L cher entstehen w rden Die Strategie zur Knotenentfernung wird im Folgenden genauer beschrieben 2 2 5 Knotenentfernung Das Vorgehen im MAPS Algorithmus sieht wie folgt aus Im Schritt von wird ei ne maximal unabh ngige Menge von Knoten mit einer niedrigen Anzahl ausgehender Kanten entfernt Zu Beginn des Algorithmus ist keiner der Knoten als nicht entfernbar markiert und die Menge der Knoten die entfernt werden sollen ist demzufolge leer Dann werden zuf llig nicht markierte Knoten k mit N k lt 12 ausgew hlt und der Stern stern k aus P ent fernt Die Nachbarn von k werden als nicht entfernbar gekennzeichnet Dieses Verfahren wird fortgesetzt bis keine Knoten mehr entfernt werden k nnen In Netzen mit einem durchschnitt lichen Knotengrad von 6 sind weniger als die H lfte der Knoten vom Grad 12 oder h her 9 Dobkin und Kirkpatrick zeigten dass in diesen Netzen zumindest 1 24 der Knoten auf jeder Stufe entfernt wird Somit ergeben sich die zu Beginn dieses Abschnitts erw hnten O log Hierarchiestufen 18 KAPITEL 2 GRUNDLAGEN Das zuvor beschriebene Vorgehen wird nun noch leicht abge ndert indem die zuf llige Aus wahl durch eine Klassifizierung der Knoten in e
54. des Dreiecks so geordnet dass das Volumen Q ABC positiv ist Die Strecke QQ schneidet das Dreieck genau dann wenn gilt Q B A 2 O Q B C Q gt O Q C A Q 2 0 Anders ausgedr ckt Die Strecke QQ schneidet das Dreieck ABC genau dann wenn die Drei ecke ABQ CBQ und ACQ von Q aus betrachtet entgegen des Uhrzeigersinns orientiert sind s Abb 5 6 Ist eines der drei Volumina 0 so bedeutet dies dass Punkt Q koplanar zum Dreieck ABC ist Bei zwei Nullwerten schneidet die Strecke QQ das Dreieck in einer Drei eckskante bei drei Nullwerten in einem der Eckpunkte des Dreiecks Q E 7 Q Abbildung 5 6 Im Schnitttest verwendete Bezeichner Implementierung Der Inklusionstest ist ber drei Funktionen implementiert Die erste berechnet die Volumi na von Tetraedern nach der zuvor beschriebenen Methode Die zweite berpr ft auf bereits beschriebene Art und Weise auf Schnitt zwischen einer Strecke und einem Dreieck Ebenso berpr ft sie im Falle eines Schnittes ob koplanar in einer Kante oder einem Punkt geschnitten wird F r diese drei F lle wird der Schnitttest mit einem anderen Referenzpunkt wiederholt da er keinem Dreieck eindeutig zuordbar ist Die letzte Methode erzeugt zun chst einen randomi sierten Referenzpunkt Q In einer usseren Schleife werden dann alle Punkte des Grobgitters durchlaufen In der zugeh rigen inneren Schleife wird ber alle Dreiecke der Triangulierung 62 KA
55. die Menge der Komponenten des Vektors x die mit dem Rand assoziiert sind Bei der voll expliziten Randbehandlung werden aus der Matrix A die Zeilen und Spalten ge strichen die zu geh ren Die Eintr ge des Vektors b werden entsprechend modifiziert Aus dem Vektor der Unbekannten x werden die Komponenten aus XQ ebenfalls gestrichen weil f r sie ja gerade die Dirichlet Werte schon bekannt sind und sie somit keine Unbekannten mehr sind Dieses Verfahren findet sich oft bei direkten L sern da die Dimension der Matrix redu ziert wird Bei der halb impliziten Randbehandlung wird folgenderma en vorgegangen In der Matrix A werden lediglich die Zeilen durch die entsprechenden Zeilen der Einheitsmatrix ersetzt die mit assoziiert sind Beim Aufbau des Vektors der Unbekannten und der rechten Seite werden die Dirichlet Werte mit einbezogen Diese Technik passt hervorragend zur Verwendung von iterativen L sern vgl folgendes Kapitel weil die L sungsvektoren immer die Randbeding ungen erf llen Bei der voll impliziten Randbehandlung wird die Matrix A nicht modifiziert sondern nur die Komponenten von x und b entsprechend der Zugeh rigkeit zu aktualisiert Randbeding ungen werden vor und nach jedem Iterationsschritt gesetzt Dies kann durch herausfiltern der von den Randbedingungen beeinflussten Werte geschehen Selbst wenn verschiedene Randbe dingungen gesetzt werden ver ndert sich die Matrix nie es sind lediglich verschiedene
56. eigenst ndige L ser in der Praxis nicht verwendet werden Ferner ist ein so genannter Relaxationsparameter w lt 1 gebr uchlich um den Defektkorrek turwert zu d mpfen und somit bessere Konvergenzraten zu erzielen Die vollst ndige Iterati onsvorschrift schreibt sich schlie lich als x 4 WON Ax Die Matrix C wird hierbei auch als Vorkonditionierungsmatrix bezeichnet Ferner ist es m g lich den Parameter w nicht nur konstant sondern auch in Abh ngigkeit von der Iterationszahl k zu w hlen 2 1 GUNDLAGEN DES CFD 13 2 1 6 Anwendung auf das Poissonproblem Beispielhaft soll am Poissonproblem s Gleichung 2 2 die oben beschriebene Vorgehensweise veranschaulicht werden Das entstehende Diskretisierungsschema wird in Kapitel 5 8 wieder aufgegriffen und als Grundlage zur Simulation eines Flusses verwendet Sei Q das betrachtete Gebiet hier C 3 Folgende Gleichung gilt es zu erf llen Au f auf Q mit f 0 auf Dies ist die in Kapitel 2 1 2 dargestellte Poissonproblem Die numerische L sung dieser parti ellen Differentialgleichung durch die oben dargestellte Finite Differenzen Diskretisierung des Laplace Operators wird nun durch den Aufbau eines linearen Gleichungssystems vorbereitet Die Finite Differenzen Matrix Im weiteren Verlauf wird davon ausgegangen dass die Punkte eines kartesischen Gitters im zweidimensionalen Fall von unten links nach oben rechts bzw im dreidimensionalen Fa
57. f r die Laufzeit dar Nachdem f r eine durch einen Grobgitterknoten und einen randomisiert gew hlten Referenz punkt definierten Strecke die Anzahl der Schnitte mit allen Dreiecken des Objektes berpr ft wurde kann an Hand dieser festgestellt werden ob sich der Grobgitterknoten innerhalb oder ausserhalb des Objektes befindet Bei ungerader Anzahl befindet sich der Grobgitterknoten in nerhalb des Objektes bei gerader au erhalb Liegt der Grobgitterknoten au erhalb des Objek tes so schneidet er das Objekt entweder gar nicht oder in mindestens zwei Punkten Da sowohl Grobgitterpunkt und Referenzpunkt au erhalb des Objektes liegen muss die Strecke wenn sie in das Objekt eintritt auch wieder aus diesem austreten Ansonsten liegt der Grobgitterknoten entweder innerhalb des Objektes oder die Anzahl der Schnitte ist durch zweideutige Schnitte verf lscht Da der letzte Fall aber durch die Funktionalit t des Inklusionstests ausgeschlossen werden kann ist die Korrektheit des Verfahrens gegeben 108 KAPITEL 6 PROJEKTVALIDIERUNG 6 8 L ser Zur Validierung des GPU L sers wird eine geeignete Testfunktion definiert uo z X x y Y y 2 Z z gt R ug 0 X x 0 Y x 0 2 Die Funktion wird analytisch differenziert und der Vektor Aug als Eingabe f r den L ser verwendet Au Aup s Abb 6 35 Die zu berechnende L sung u ist somit analytisch bekannt Zus tzlich wird eine Referenzl sung auf der CPU berechnet Zur Vali
58. geeignet aufgeteilt und in die RGBA Kan le einer Textur gespeichert wurden Kr ger und Westermann beschreiben verschiedene Verfahren die in der PG zum Einsatz kommen s Kap 5 8 Eine dieser grundlegenden Operationen die f r verschiedene L ser benutzt wird ist SAXPY ax Eine Multiplikation mit Bandmatrizen kann beispielsweise durch wiederholte Anwendung von SAXPY realisiert werden G ddeke beschreibt in seinem Tutorial 15 die Realisierung dieser elementaren Operation auf der GPU Diese Operation wurde von der PG 2 6 GPGPU 37 benutzt um die verschiedenen M glichkeiten der GPU Programmierung zu evaluieren s Kap 4 4 2 6 1 Hardware Um die potentielle Rechenkraft der Grafikkarten aussch pfen zu k nnen muss der interner Aufbau der Grafikprozessoren ausgenutzt werden Grafikkarten sind auf die Darstellung von 3D Szenen optimiert und nicht direkt zur allgemeinen Berechnung gedacht Die Anbindung der Grafikkarten in das restlichen System erfolgt ber einen AGP oder PCIe Bus Da diese Bussysteme nicht die ben tigten Geschwindigkeiten zum Hauptspeicher bieten werden Gra fikkarten mit eigenem Speicher ausgestattet Aktuelle Versionen binden diesen mit einem 256 Bit breiten Bus an und haben zur Zeit eine Speicherbandbreite von bis zu 32 GB s z B ATI Radeon X800 41 Die hohe Rechenkraft und die interne Parallelschaltung wird durch die Ausrichtung der Hard ware auf Single Instruction Multiple Data SIMD erreicht
59. hlt 127 Nach der Auswahl der Punkte k nnen nun alle Fl chen durch Dr cken der Schaltfl che subdi vide unterteilt werden in diesem Beispiel wurde dieser Schritt zweimal durchgef hrt s Abb en SCR 2 Model x lt 5 5 Abbildung A 3 Der W rfel wurde zweimal unterteilt Durch wiederholtes Benutzen der Schaltfl che smooth kann das Objekt nun gegl ttet werden dieser Vorgang entspricht der in Kapitel 2 3 3 beschriebenen Laplace Gl ttung Die scharfen Kanten des W rfels werden somit abgerundet s Abb A 4 128 ANHANG A BENUTZERHANDBUCH Blend E v File Add Timeline Game Render Help SCR2 Modei x Iscescene x view Select Mesh A EditMode 0 9 ER EISES Abbildung A 4 Das Objekt nach mehrmaliger Gl ttung Nun wird durch die Tastenkombination STRG T eine Triangulierung des Objektes berech net s Abb A 5 gt File Add Timeline Game Render Help L Iscr2 Modei X L Iscesscene x _ 8 98 Ed 288 288 Fa View Select Mesh Edit Mode J ra Abbildung A 3 Der W rfel als Oberfl chentriangulierung Der Edit Modus kann nun durch erneutes Benutzen der Tab Taste verlassen werden Blen der wechselt in den Objekt Modus A 2 TUTORIAL 129 Exportieren des Obje
60. index Liefert eine Kr mmung an dem Punkt mit dem Index maps point index aus der internen Liste zur ck Falls dieser innerhalb eines Feindreiecks liegt wird die Kr mmung an den drei umliegenden Eckpunkten gemittelt float getCurvature int point index liefert eine Kr mmung an dem Punkt mit dem Index point index aus der Fein triangulierung zur ck void setObj Object object setzt die interne Referenz der Klasse Objekt auf object Klasse Tri Diese Klasse liefert eine g ltige Triangulierung einer Punktmenge in 2D Intern werden da bei sukzessiv konvexe Ecken abgetrennt Mit Ausnahme der Anpassung der R ckgabetypen ist diese Klasse aus Computational Geometry in C Chapter 1 bernommen worden 45 Tri vector lt st_point gt points Wird die Punktmenge bergeben und eine Instanz des Triangulierungsobjekts wird erzeugt die Methoden bereitstellt um die Punktmenge zu triangulieren void ReadVertices vector lt st_point gt Um mit derselben Klasseninstanz unterschiedliche Punktmengen zu triangulieren kann die Punktemenge mit ReadVerticies berschrieben werden vector lt st_point gt Triangulate Liefert die Triangulierung der Punktmenge Je drei aufeinanderfolgene Punkte im R ckgabewert bilden dabei ein Dreieck C 1 4 Modul GPU L ser stellt einen L ser f r das Poissonproblem auf der GPU bereit Klasse GPUSolver load_datax load char filename l dt eine Datei die alle f r die L sung d
61. of the free software distribution system which is implemented by public license practices Many people have made generous contributions to the wide range of software distributed through that system in reliance on consistent application of that system it is up to the author donor to decide if he or she is willing to distribute software through any other system and a licensee cannot impose that choice This section is intended to make thoroughly clear what is believed to be a consequence of the rest of this License 10 11 12 175 If the distribution and or use of the Program is restricted in certain countries either by pa tents or by copyrighted interfaces the original copyright holder who places the Program under this License may add an explicit geographical distribution limitation excluding those countries so that distribution is permitted only in or among countries not thus ex cluded In such case this License incorporates the limitation as if written in the body of this License The Free Software Foundation may publish revised and or new versions of the General Public License from time to time Such new versions will be similar in spirit to the present version but may differ in detail to address new problems or concerns Each version is given a distinguishing version number If the Program specifies a version number of this License which applies to it and any later version you have the opti on of following the ter
62. pieces of it in new free programs and that you know you can do these things To protect your rights we need to make restrictions that forbid anyone to deny you these rights or to ask you to surrender the rights These restrictions translate to certain responsibilities for you if you distribute copies of the software or if you modify it For example if you distribute copies of such a program whether gratis or for a fee you must give the recipients all the rights that you have You must make sure that they too receive or can get the source code And you must show them these terms so they know their rights We protect your rights with two steps 1 copyright the software and 2 offer you this license which gives you legal permission to copy distribute and or modify the software 171 172 ANHANGD LIZENZ Also for each author s protection and ours we want to make certain that everyone understands that there is no warranty for this free software If the software is modified by someone else and passed on we want its recipients to know that what they have is not the original so that any problems introduced by others will not reflect on the original authors reputations Finally any free program is threatened constantly by software patents We wish to avoid the danger that redistributors of a free program will individually obtain patent licenses in effect making the program proprietary To prevent this we have made it clear that any p
63. r unterschiedliche Texturformate bei einer festen Problem bzw Texturgr e von N 1024 1024 Die FBO Ergebnisse wurden unter Linux alle anderen unter Windows XP erstellt 2D Texturen sind das Standardformat f r Texturen Aktuelle Grafikkarten k nnen in 2D Texturen bis zu 4096 4096 16 777 216 Elemente speichern 3RECT Texturen sind ein weiteres Texturformat f r Details wird auf G ddeke 15 verwiesen 4 4 GPGPU 51 5090 7000 saxpy R32 saxpy c RGBA32 c RGBA16 saxpy v R32 saxpy v RGBAZ 6608 4000 5000 4000 3000 MFLOP s 3888 MFLOP s 2608 2000 1000 DESS 1808 OT OO O OO o o o Oo Oo mm m m m gga mama ra amp amp rcrraadsddd 285655588 terang ras555888 A EEE uw O M o WW WM aa eee aa 52 AA o oO o o o o a w GZ d Hd i88g99228222 80 1884 65536 419430 SGre gg a MFLOP s f r verschiedene Problemgr en b MFLOP s f r verschiedene Texturformate Abbildung 4 3 Testergebnisse NVIDIA GeForce 6800 ATI Radeon 9800 PRO Abbildung 4 4 a stellt die Rechenleistung f r unterschiedliche Problemgr en basierend auf 2D Texturen und Cg dar Im Gegensatz zur vorigen NVIDIA Karte erzielt die ATI 9800 Pro ihr Optimum bei der Benutzung eines gepackten Pixelfomates Abbildung 4 4 b zeigt die Rechenleistung f r unterschiedliche Implementationen bei einer fe ste
64. rpern mit Hilfe von Dreiecksnetzen Jedes Dreieck wird durch seine drei Eckpunkte und die zugeh rige Fl chennormale charakterisiert InGrid3D stellt an das Objekt zus tzliche Anforderungen so muss die Oberfl che zun chst geschlossen sein anschaulich k nnte man auch von wasserdicht sprechen Konkret bedeu tet dies dass keine L cken zwischen Dreiecksfl chen existieren d rfen Ebensowenig d rfen doppelte Dreiecksfl chen vorliegen dies w rde sp ter bei der Parametrisierung zu Problemen f hren Die Einhaltung dieser Kriterien wird beim Import der Objekte berpr ft In der PG wurden die verwendeten Objekte mit Hilfe der Software Blender s Kap 3 7 erstellt Ein Beispiel zum Erstellen einer einfachen Geometrie kann Anhang A 2 1 entnommen werden Der Mittelpunkt entspricht hierbei dem Punkt auf halber L nge der Snake Ein weiteres Kriterium welches zur Entwicklung der Glitter f hrte war die Tatsache dass einige L ser mit extrem spitzen oder extrem flachen Winkeln innerhalb der Hexaeder nicht funktionieren 5 2 GROBGITTERGENERATOR 55 5 2 Grobgittergenerator Der Grobgittergenerator HaGrid3D dient der m glichst einfachen manuellen Erzeugung eines guten Grobgitters Die Evaluierung von Cubit s Kap 4 3 ergab dass es f r die Aufgaben der PG nicht ausreichend ist Somit wurde es notwendig ein eigenes Werkzeug f r diese Aufgabe zu implementieren 5 2 1 Anforderungen Die wesentlichen Aufgaben dieses Programms so
65. sung des Geo metrieobjektes Die Qualit t des Grobgitters beruht heuristisch auf Erfahrungswerten bei der Benutzung von InGrid3D daher die Bezeichnungen gut bzw schlecht Hierbei muss dar auf geachtet werden dass das Grobgitter m glichst markante Punkte der Geometrie erfasst Die Anzahl der initialen Hexaederzellen wird in der letzten Spalte angegeben Testfall Geometrieobjekt Grobgitter Name Aufl sung Qualit t Aufl sung 1 Kugel fein gut 26 Zellen 2 Kugel grob gut 26 Zellen 3 Kugel fein schlecht 26 Zellen 4 Einbuchtung fein gut 1000 Zellen 5 Einbuchtung fein schlecht 64 Zellen 6 Klotz fein gut 3375 Zellen 7 Klotz fein schlecht 125 Zellen 8 Golf fein gut 160 Zellen Tabelle 6 2 Auflistung der Testf lle und deren Eigenschaften Die Testf lle werden in den folgenden Abschnitten zun chst jeweils kurz beschrieben In den Abbildungspaaren wird auf der linken Seite das Originalobjekt und auf der rechten Seite die Approximation der Objektoberfl che durch die Hexaederseitenfl chen angezeigt aus Gr nden der bersichtlichkeit werden nur die Hexaederzellen auf den Objektr ndern angezeigt Testfall 1 Als Objekt wird eine hochaufgel ste Kugel 327680 Dreiecke verwendet Die Qualit t des initialen aus 26 Hexaederzellen bestehenden Grobgitters ist unter den Einschr nkungen die kartesische Gitter f r dieses Objekt implizieren optimal In diesem Testfall s Abb 6 1 sollte die Anzah
66. und 128 erreicht s Abb 6 27 a Umbrella 2 kann Jacobi Fehler in der N he des Objektes s Abb 6 26 b beheben indem Knoten die sich in direkter Nachbarschaft zum Objektrand be finden weiter in die vom Objektrand abweisende Richtung gezogen werden s Abb 6 27 b a Qualitativ schlechtes Grobgitter b Die Gitterqualit t wurde erh ht Abbildung 6 25 Resultate des Laplace Gl tters 98 KAPITEL 6 PROJEKTVALIDIERUNG a Eine zul ssige Gitterkonstellation b Der Laplace Gl tter erzeugt Jacobi Fehler Abbildung 6 26 Schwachpunkt des Laplace Gl tters On ul a Der Umbrella Gl tter erzielt qualitativ bessere Er b Der Umbrella 2 Gl tter zieht die Umgebungskno gebnisse als der Laplace Gl tter ten vom Objekt weg Abbildung 6 27 Eigenschaften der Umbrella Gl tter Oberfl chengl tter Oberfl che Winkel und Oberfl che Jacobi Die vorangegangenen Gl tter zur Verbesserung der Gitterqualit t k nnen auf der Objektober fl che liegende Knoten nicht verschieben Dadurch sind sie in ihren M glichkeiten einge schr nkt insbesondere weil Jacobi Fehler h ufig an der Objektoberfl che auftreten Daher 6 4 VALIDIERUNG DER GL TTER 99 wurden zwei Gl tter entwickelt die Knoten auf der Oberfl che verschieben Es folgen typi
67. verschoben Im 3D Fenster wird die Ansicht in Richtung der Maus bewegung gedreht e Bei gedr ckt gehaltener rechter Maustaste wird die perspektivische Ansicht verschoben e Bei gedr ckt gehaltener mittlerer Maustaste bzw mit dem Mausrad wird die Darstellung vergr ert Klasse mywindow erzeugt die grafische Benutzeroberfl che und stellt verschiedene Dialoge zur Verf gung void load Object ffnet einen Datei Laden Dialog um ein Objekt zu laden void save Grid ffnet einen Speichern Dialog um ein Grobgitter mit der Endung cm zu spei chern welches von HaGrid3D eingelesen werden kann void export Grid ffnet einen Speichern Dialog um ein Grobgitter mit der Endung grid zu ex portieren welches von nGrid3D importiert werden kann void load Grid ffnet einen Datei Laden Dialog um eine Grobgitterdatei zu laden void output Objectattr statusbar const char name int vert int faces schreibt Objektinformationen in die Statuszeile 167 168 ANHANG C API DOKUMENTATION void status of snapping to statusbar bool snapping schreibt den Status beim Verschieben von Knoten in die Statuszeile void createGrid erzeugt ein Gitter mit den in der Steuerungsleiste angegebenen Dimensionen void updateHexLengthSlider const QString amp text korrigiert die Position des Schiebereglers wenn der Wert f r die Kantenl nge per Hand ver ndert wurde void updateHexLength int value korrigiert den Wert im Eing
68. werden nur die neuen k rzeren Kanten bernommen Diese beiden Kanten erhalten den Randstatus der alten Kante Unterteilung der Fl chen In der Mitte jeder Fl che aus dem alten Gitter wird ein neuer Knoten erzeugt und im neuen Gitter gespeichert Falls die Fl che eine Objektrandfl che ist so wird die Knotenposition ber die Oberfl chenparametrisierung bestimmt Ansonsten wird der Knoten als arithmetisches Mit tel der vier Eckknoten der Fl che erzeugt Alternativ kann auch das arithmetische Mittel der vier neu erzeugten Knoten auf den Kanten berechnet werden was in diesem Fall zum exakt gleichen Ergebnis f hrt Diesen Knoten wird als Randstatus der Status der zu unterteilenden Fl che zugewiesen Als n chstes werden vier Kanten im Inneren der alten Fl che erzeugt Die Startknoten dieser Kanten sind die Knoten die bei der Unterteilung der Kanten neu erzeugt wurden Diese liegen auf die Mitte der Seitenkanten der aktuell betrachteten Fl che und wur den bereits bei der Unterteilung der Kanten erzeugt Der Endpunkt der vier neuen Kanten ist jeweils der neu erzeugte Knoten in der Mitte der aktuell betrachteten Fl che Der Randstatus der alten Fl che wird auf diese vier Kanten bertragen 68 KAPITEL 5 SYSTEMBESCHREIBUNG Abbildung 5 12 Unterteilung der Fl chen Insgesamt werden die vier Kanten die die alte Fl che definieren in acht Kanten unterteilt und zus tzlich vier Kanten im Inneren der alten Fl che erzeugt Aus diesen zw
69. zur Entstehung von invertierten Elementen kommen Ein L sungsansatz f r dieses Problem ist die smart Laplace Technik Ein Knoten p wird nur dann verschoben wenn dies zu einer Verbesserung der Qualit tskriterien f hrt Umbrella Gl ttung In seiner Diplomarbeit hat G ddeke 14 die Eignung des Umbrella Operators 25 zur Gl t tung von Finite Elemente Gittern experimentell nachgewiesen F r die Herleitung des Opera tors sei auf 14 verwiesen Es wird hier nur die diskrete Variante skizziert Der Umbrella Gl tter durchl uft alle Knoten des Gitters und berechnet f r einen Knoten p seine neuen Koordinaten Pneu aus den umliegenden Gitterknoten und deren Nachbarn wie folgt a a DN ge gt 2 11 1 lt j lt fAdj p wu eAdi P 28 KAPITEL 2 GRUNDLAGEN wobei a 0 1 ein Gewichtungsfaktor ist die Menge Adj p f r jeden Knoten p dessen Nachbarn enth lt und d die L nge der Kante p q bezeichnet Optimierungsbasiertes Gl tten Ein weiteres Verfahren zur lokalen Gittergl ttung wird von Freitag 13 vorgestellt Das so genannte optimierungsbasierte Gl tten versucht die Gitterpositionen zu finden die ein Qua lit tsma optimiert s Kap 2 4 Die zu minimierende Zielfunktion ist in diesem Fall f x in d x 2 12 Hierbei ist ein Qualit tsma des Elementes i wie z B der minimale Winkel Es wird ber alle n Elemente minimiert Typischerweise ist q eine nichtlineare glatte und stetig di
70. 4 Die Geometrie besteht aus einer hochaufgel sten Kugel in die eine w rfelf rmige Einbuch tung eingelassen wurde vgl Abb 6 4 Das Grobgitter versucht diesem Problemfall optimal zu begegnen indem insbesondere die Einbuchtung mit insgesamt vier Hexaederzellen aufge f llt wird 6 2 TESTGEOMETRIEN UND TESTGITTER 81 a Originalobjekt im Gitter b Durch das Gitter angen herte Objektoberfl che Abbildung 6 4 Initiales Grobgitter f r Testfall 4 Testfall 5 Als Objekt wird wieder die Einbuchtung aus Testfall 4 verwendet Um den Einfluss des Grob gitters auf die resultierende Gitterqualit t zu demonstrieren wurde bei dem hier verwendeten Gitter absichtlich nicht auf die Erfassung der Einbuchtung geachtet vgl Abb 6 5 a ze y IW PANI X 1 Ly 0 mvs j m Y 4 VA 4 PES E y 17 L y y b Durch das Gitter angen herte Objektoberfl che JI 8 7 a Originalobjekt im Gitter Abbildung 6 5 Initiales Grobgitter fiir Testfall 5 82 KAPITEL 6 PROJEKTVALIDIERUNG Testfall 6 Testfall 6 ist ein abstraktes Objekt das speziell f r die Entwicklung von InGrid3D entworfen wurde mit einem von Hand erstellten m glichst gut an dieses Objekt angepassten Grobgitter vgl Abb 6 6 Mit diesem Grobgitter waren auf dem Testsystem mit 1 5 GB
71. 61 8 38 Tabelle 6 11 Werte der Qualit tskriterien nach der jeweiligen Gl ttung Gl tter zur Verbesserung der Gitterqualit t Laplace Laplace Jacobi Umbrella und Umbrella 2 Der Laplace Gl tter ist einer der einfachsten Gl tter Das in Abbildung 6 25 a dargestellte Gitter ist qualitativ schlecht der minimale Innenwinkel betr gt 27 der maximale Innenwin kel 151 Nach 14 Iterationen haben sich die Werte auf 42 und 136 verbessert weitere Ite rationen bleiben ohne Effekt s Abb 6 25 b Bei nichtkonvexen Objekten kann der Laplace Gl tter aber auch zu Fehlern f hren s Abb 6 26 Aus diesem Grunde wurde eine zus tzli che Kontrolle auf Jacobi Fehler implementiert die den Gl ttungsvorgang abbricht sobald ein Jacobi Fehler entstehen w rde Im Beispiel aus Abbildung 6 26 a wird durch den Laplace 6 4 VALIDIERUNG DER GL TTER 97 Jacobi Gl tter kein neuer Jacobi Fehler erzeugt allerdings wird auch keine Verbesserung des Gitters erziehlt Um die Unzul nglichkeiten der beiden vorgestellten Gl tter zu kompensieren wurden mit den Umbrella Glattern zwei weitere Methoden zur Gitterverbesserung implementiert Der Umbrella Gl tter ist dabei in der Lage selbst in Situationen in denen der Laplace Gl tter keine Auswir kungen auf das Gitter mehr hat noch Qualit tsverbesserungen zu erzielen So wird bei dem Gitter des Kegelobjektes aus Abbildung 6 25 b eine weitere Verbesserung der Winkel auf 46
72. AY MODIFY AND OR REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE BE LIABLE TO YOU FOR DAMAGES INCLUDING ANY GENERAL SPECIAL INCIDENTAL OR CONSEQUEN TIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE PROGRAM INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED INAC CURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES END OF TERMS AND CONDITIONS 176 ANHANGD LIZENZ Appendix How to Apply These Terms to Your New Programs If you develop a new program and you want it to be of the greatest possible use to the public the best way to achieve this is to make it free software which everyone can redistribute and change under these terms To do so attach the following notices to the program It is safest to attach them to the start of each source file to most effectively convey the exclusion of warranty and each file should have at least the copyright line and a pointer to where the full notice is found one line to give the program s name and a brief idea of what it does Copyright C yyyy name of author This program is free software you can redistribute it and or modify it under the terms of the GNU General Public License as published by the Free Software Foun dation either version 2 of the License or at your option any later version This program is distribu
73. Endbericht der Projektgruppe 471 Beyond Graphics Str mungssimulation in der GPU Lehrstuhl fiir Graphische Systeme Fachbereich Informatik Lehrstuhl fiir Angewandte Mathematik und Numerik Fachbereich Mathematik Universitat Dortmund SoSe 2005 WiSe 2005 06 Teilnehmer Daniel Bachmann Przemyslaw Beben Till Becker Adam Andr Braun Andreas Ehrenberg Christian Gro Michael Hein Matthias Miemczyk Raphael M nster Mark Senne Mirko Sykorra Klaus Wohlgemuth Betreuer Claus Peter Alberts Dominik G ddeke il Inhaltsverzeichnis Inhaltsverzeichnis 1 Einleitung 1 1 Anforderung Ziele 1 2 Einordnung des Projektes 1 3 Vorgehensweise der Projektgruppe 1 4 Struktur des Berichtes 2 22 Co Come 2 Grundlagen 2l GundlasendesCED Sch gin ek ee a an an 2 1 1 Notationen ie e re v UE EIS 2 1 2 Modellier ng x 22 2 2er au PERSE RES SE 2 3 Diskretisierung 2 1 4 Behandlung von Randbedingungen 2 1 5 L sung des Gleichungssystems 2 1 6 Anwendung auf das Poissonproblem 2 1 7 Potential Flow EEN 2 2 Multiresolution Adaptive Parameterization of Surfaces 2 2 1 Definitionen und 2 2 2 Aufbau der Hierarchiestufen 2 2 3 Knotenentfernung 2 2 4 Projektion und Retriangulierung 2 2 5 Parametri
74. Hauptspeicher drei Unterteilungen m glich bevor die Speichergrenze erreicht wird in diesem Augenblick verbraucht InGrid3D ca 900MB Hauptspeicher a Originalobjekt im Gitter b Durch das Gitter angen herte Objektoberfl che Abbildung 6 6 Initiales Grobgitter f r Testfall 6 Testfall 7 Testfall 7 verwendet das bereits aus Testfall 6 bekannte Testobjekt welches nun mit einem sehr einfachen schlecht angepassten Grobgitter approximiert werden soll vgl Abb 6 7 Im Test verbrauchte das Programm nach der vierten Unterteilung bereits ann hernd 400MB Hauptspei cher eine weitere Unterteilung war mit den im Testsystem verf gbaren 1 5 GB Hauptspeicher nicht m glich 6 2 TESTGEOMETRIEN UND TESTGITTER 83 a Originalobjekt im Gitter b Durch das Gitter angen herte Objektoberfl che Abbildung 6 7 Initiales Grobgitter f r Testfall 7 Testfall 8 F r Testfall 8 wird das Modell eines Golf III verwendet Es wird mit einem gut angepassten Grobgitter s Abb 6 8 approximiert Auch bei diesem Testfall war es aufgrund des beschr nk ten Arbeitsspeichers nicht m glich mehr als vier Unterteilungen vorzunehmen a Originalobjekt im Gitter b Durch das Gitter angen herte Objektoberfl che Abbildung 6 8 Initiales Grobgitter f r Testfall 8 84 KAPITEL 6 PROJEKTVALIDIERUNG 6 3 Validierung der Randanpassung durch Parametrisierung In diesem Abschnitt wird die Randanpassung durch Parametrisierung s Kap 5 3
75. Hexas int mapsModul Maps_Modul void loadSolverData tisSubdividing bool void saveSolverData untangler error bool invElement cHexa tempHex cHexa currPoints set cPoint comparePoints gt grid cGrid maps param Maps Param maps bari Maps Bari Bier Ad vereinigung set int origmesh MyMesh maps bari Maps Bari snake obj Snake mesh MyMesh obj Object Ge points vector lt para_point gt er beta float gamma Float alphaw float betaw Float gammaw float vl int v2 int v3 int wi int w2 int w3 int gefundenesFeindreieck int faces ref vector lt int gt Faces vector lt set int gt create Maps Bart areaf calc_baris untouchablepoints vector lt int gt showPoints vector lt Float gt maps_queue Maps_Queue queue vector MyMesh VertexHandle gt maps delaunay Maps Delaunay maps map Maps Map maps bari Maps Bari maps param Maps Param maps hinge Maps Hinge paramMesh bool Maps Queue 1 Abbildung C 1 UML Klassendiagramm fiir InGrid3D Die Abbildung C 1 zeigt eine Gesamt bersicht der wichtigsten Klassen in InGrid3D Im Fol genden werden die vier gro en Module Gitter Snake MAPS GPU L ser im Detail vorgestellt C 1 BERSICHT BER DIE PAKETE UND KLASSEN VON INGRID3D 151 C 1 1 Modul Gitter Abbi
76. ILGARD M J Cg A System for Programming Graphics Hardware in a C like Language In Proceedings of ACM SIGGRAPH 2003 S 896 907 ACM Press 2003 McCoor M DU Torr S POPA T CHAN B und MOULE K Shader alge bra ACM Trans Graph 23 3 787 795 2004 http doi acm org 10 1145 1015706 1015801 MEISTER A Numerik linearer Gleichungssysteme Vieweg 1999 MICROSOFT Visual Studio http msdn microsoft com vstudio Microsoft High Level Shading Language HLSL http msdn microsoft com library default asp url library en us directx9_c HLSL_ shaders asp M LLER H und ABRAMOWSKI S Geometrisches Modellieren BI Wissenschaftsverlag 1992 MORELAND K und E ANGEL The FFT on a GPU In HWWS 03 Proceedings of the ACM SIGGRAPH EUROGRAPHICS conference on Graphics hardware S 112 119 Aire la Ville Switzerland Switzerland 2003 Eurographics Association MORGAN R REVIEW ATI Radeon X800 XT http www barefeats com radx800 html NVIDIA Cg http developer nvidia com page cg main html OPENGL ARCHITECTURE REVIEW BOARD OpenGL http www opengl org OpenGL Shading Language GLSL http www opengl org 182 LITERATURVERZEICHNIS 45 O ROURKE J Computational Geometry in 2nd edition Cambridge University Press 1998 46 OWEN S A Survey of Unstructured Mesh Generation Technology In Proceedings of the 7th International Meshing Roundtable S 239 267 1998 47 OWENS
77. Ist dies nicht der Fall wird f r jedes m gliche Dreieck des ersten Eckpunktes eine Suche ber die anliegenden Dreiecke durchgef hrt um eine m gliche Scharnier Abbildung zu finden Ist die Suche erfolglos wird der Snake Algorithmus benutzt 5 7 Gittergl ttung und Reparatur von Selbstdurchdringungen Dieses Kapitel beschreibt Verfahren mit deren Hilfe sich Durchdringungen in Gitterzellen re parieren oder die Gitterzellen im Allgemeinen nach bestimmten Kriterien manipulieren lassen Die implementierten Gl tter lassen sich grob in zwei Bereiche einteilen Als erstes werden Gl tter beschrieben die alle Gitterknoten manipulieren k nnen mit Ausnahme von Knoten die auf der Objektoberfl che liegen Dies ist eine Einschr nkung die zur Entwicklung des zweiten Bereiches gef hrt hat Bei diesen Gl ttern k nnen nur Knoten manipuliert werden die auf der Objektoberfl che liegen Zum ersten Bereich geh ren die Reparatur von Gitter Selbstdurchdringungen die Laplace und die Umbrella Gl ttung Zum zweiten Bereich ge h ren die Jacobi und die Winkel Gl ttung Diese Verfahren werden im Folgenden genauer beschrieben 5 7 1 Reparatur von Gitter Selbstdurchdringungen Das in Kapitel 2 4 vorgestellte Verfahren zur Behebung von Selbstdurchdringungen engl mesh untangling wurde implementiert um invertierte Elemente die beim Unterteilen des Gitters oder bei der Randanpassung an das Objekt entstehen k nnen wieder in g ltige Elemente zu
78. Koordinaten werden f r die Einbettung im Zweidimensionalen berechnet und dann auf die Punkte des Netzes der feinsten Aufl sungsstufe im Dreidimensionalen angewendet 3 k K AK Der Knoten wurde schon beim bergang von II zu entfernt Es gilt also py Y pe f r ein Dreieck a U c K F r T muss keine weitere Unter scheidung getroffen werden andernfalls gilt Da die zu entfernenden Knoten in einer Vergr berungsstufe eine maximal unabh ngige Menge s o bilden ist sichergestellt dass beim bergang von auf l 1 genau ein Knoten dieses Dreiecks entfernt wurde Dies sei o B d A k Sei jj die zugeh rige Einbettung im Zweidimensionalen s Abb 2 6 Nach der Retriangulierung liegt jjj in einem Dreieck h i j K mit baryzentrischen Koordinaten 3 7 s Abb 2 6 Setze in diesem Fall II p apn Zuordnen der Vit baryzentrischen Koordinaten zu dem alten Punkt in dem neuen Dreiec Abbildung 2 6 Nach Retriangulierung in der Ebene s Abb 2 5 werden dem soeben entfernten Knoten baryzentrische Koordinaten bzgl des ihn enthaltenen Dreiecks in der gr beren Aufl sungsstufe zugeordnet Analog m ssen nun auch allen Knoten der feinsten Aufl sungsstufe die auf ein Dreieck des entstandenen Loches abgebildet wurden einem der neu entstandenen Drei ecke der gr beren Aufl sungsstufe zugeordnet werden 30 Die Beschriftun
79. ONTUREN 33 Knoten auf dem geometrischen Randobjekt zu liegen kommen sollen Wie bei einer realen Pla stikmembran ist es hier wichtig dass keine Risse berlagerungen oder Falten in der Kontur entstehen Eine aktive Kontur im Zweidimensionalen ist eine Funktion v 0 1 R die auf einem Bild f R R positioniert wird und sich durch Minimierung ihrer Energie in eine optimale Po sition bewegen soll F r den Dreidimensionalen Fall kann dies als ein Gummiband aufgefasst werden das zwischen zwei beliebigen Punkten auf der Oberfl che eines Objektes gespannt wird Die Energie dieser Kontur setzt sich aus zwei Bestandteilen zusammen der Bildenergie und der internen Energie E v Eimage V f Bali 2 16 Die interne Energie ist dabei definiert als 1 Ein v f o s v s B s v s ds 2 17 Als Bildenergie kann beispielsweise ein Filter zur Extraktion von Kanten oder hnliches ver wendet werden Der erste Summand der Gleichung 2 17 genannt Membran Energie nimmt gro e Werte an wenn gro e Abst nde zwischen benachbarten Punkten auf der Kontur vorliegen Der zweite Summand beschreibt die Biegeenergie der Kontur Die Gewichtsfunktionen o und 8 beschrei ben somit die Elastizit t engl elasticity und Steifheit engl rigidity 2 5 1 Gradient Vector Flow Die Funktionsweise der aktiven Konturen hat insbesondere zwei Schwachpunkte Zum Einen muss sich die Kontur in n chster N he zu dem zu umschlie en
80. PITEL 5 SYSTEMBESCHREIBUNG iteriert ihre Koordinatenwerte werden abgefragt und der Funktion die auf Schnitt pr ft zu sammen mit den beiden Punkten die die Strecke festlegen bergeben Je nach Ausgabe wird entweder die Anzahl der Schnitte f r diesen Grobgitterpunkt um eins erh ht und beim n ch sten Dreieck weitergearbeitet oder ein anderer Referenzpunkt f r dasselbe Dreieck erzeugt Abschliessend wird berpr ft ob die Anzahl der Schnitte gerade Punkt liegt au erhalb des Feinnetzes oder ungerade ist was zu einer Markierung als solid f hrt 5 3 Parametrisierung Um eine Reihenfolge der Elemente innerhalb der maximal unabh ngigen Menge von Knoten zu bestimmen werden alle Knoten des Objektes durchlaufen Falls die Anzahl der ausgehen den Knoten zw lf nicht berschreitet wird die diskrete Kr mmung bestimmt und mit einer Referenz zu der Knoten ID aus OpenMesh s Kap 3 6 in einer Liste gespeichert Die nach Kr mmung und Fl cheninhalt sortierte Liste liefert die Reihenfolge in der die Knoten abgear beitet werden Wird ein Knoten des Objektes entfernt entsteht ein Loch durch die fehlenden anliegenden Dreiecke Durch eine Retriangulierung des Loches ver ndert sich dabei die diskrete Kr m mung der an diesem Loch anliegenden Knoten Die Knoten m ssen eine unabh ngige Menge engl independent set bilden um die Reihenfolge sinnvoll nutzen zu k nnen Daher wird ab schlie end die Liste durchlaufen und jeweils alle Knoten d
81. Prozedur In Tabelle 6 13 stellt P den Anteil der verschobenen Knoten in Prozent dar D steht fiir die Distanz der Verschiebung und N f r die Anzahl von ung ltigen Elementen Die letzte Spalte gibt die Zeit in Sekunden an Es stellt sich heraus dass die Distanz um die ein Knoten verschoben wird die Rechenzeit am st rksten beeinflusst Ein weiteres Resultat ist dass die Anwendung der Reparatur Prozedur auf nicht invertierte Elemente zu einem Gitter mit schlechter Qualit t f hrt Dies zeigt sich be sonders durch das Auftreten von zum Teil sehr spitzen Winkeln Des Weiteren treten Probleme auf wenn Knoten der Hexaederzelle die an die Reparatur Prozedur bergeben werden zum Objektrand geh ren Diese Knoten d rfen im Kontext des Projektes nicht von der Oberfl che gezogen sondern h chstens auf der Oberfl che verschoben werden Da bei optimierungsba sierter Durchdringungsbehebung aber die neuen Koordinaten nach Maximierung des minima len Fl cheninhalts berechnet werden kann diese Forderung nicht erf llt werden Daher werden diese Knoten von der Betrachtung ausgeschlossen und nur die brigen Knoten des Hexaeders behandelt Auf diese Weise l sst sich aber nicht gew hrleisten dass eine Invertierung behoben wird Abbildung 6 32 zeigt den Fall eines invertierten Elementes das Randknoten enth lt Die Rand knoten wurden im Unterteilungsschritt erzeugt und an den Objektrand angepasst Durch die Randanpassung haben diese Knoten die Nich
82. Punktkoordinaten sind die ersten drei Komponenten des L sungsvektors des dualen Problems und ersetzen die alten Koor dinaten so dass nachfolgende Berechnungen direkt die neuen Koordinaten verwenden k nnen Vor dem Durchf hren der Reparatur Prozedur wird das Gitter mit der intelligenten Laplace Technik engl smart Laplace vorgegl ttet und nach der Durchdringungsbehebung noch einmal nachgegl ttet In der Praxis hat sich ein Wert von 30 Iterationen intelligenter Laplace Gl ttung bew hrt 13 5 7 2 Laplace Gl ttung Zur Verbesserung der Gitterqualit t wurde ein Laplace Gl tter in das Projekt integriert Die Implementierung entspricht der Beschreibung des Verfahrens in Kapitel 2 3 3 5 7 3 Umbrella Glattung Version 1 Der Umbrella Gl tter hat den Vorteil dass er L ngenverh ltnisse der Nachbarkanten des be trachteten Knotens beibeh lt und somit keine Durchdringungen erzeugt Weiterhin wird eine gr ere Umgebung betrachtet da die Kantenl ngen der Nachbarn des zu verschiebenden Kno tens mit in die Berechnung der neuen Koordinaten eingehen s Kap 2 3 3 Version 2 Es hat sich als vorteilhaft erwiesen den Gl tter so zu modifizieren dass Knoten auf der Ober fl che des Objekts nicht in die Berechnung der neuen Koordinaten eingehen so dass Knoten die sich in direkter Nachbarschaft zum Objektrand befinden weiter in die vom Objektrand abweisende Richtung gezogen werden 5 7 4 Heuristiken zur Gittergl ttung auf der Objekt
83. Schalt fl che werden Gitterqualit tsmerkmale berechnet und in der Statusleiste angezeigt s Abb A 19 138 ANHANG A BENUTZERHANDBUCH J Snake zeichnen Gitter Punkte zeichnen Punktgr e 5 SEET Gitter zeichnen C Gar nicht Nur am Objektrand C Komplett C Objektoberll che C Innere Fl chen Qualit tsmerkmale Jacobi Fehler IV Schlechteste Winkel Schlechteste Aspect Ratio v Schlechteste Edge Ratio Qualit tspr fung Abbildung A 19 Die Qualit tsmerkmale des Gitters werden nach Bet tigen der Qualit tspr fung Schaltfl che in der Statuszeile angezeigt Unterteilung Gl ttung Zeichenoptionen Debug GPGPU L ser Untangler Laplace Laplace Jacobi Umbrella Umbrella 2 Oberfl che Jacobi berfl che Winkel Oberflache Kr mmung X ME NE Gl ttung druchf hren Iterationen 10 Gl tten Abbildung A 20 Die Gl ttung Leiste A 2 TUTORIAL 139 Vor oder nach jedem Unterteilungsschritt kann das Gitter gegl ttet und repariert werden indem man zuerst die gew nschte Option auf der Gl ttung Leiste ausw hlt die Iterationenanzahl mittels des Schiebereglers anpasst und anschlie end die Gl tten Schaltfl che bet tigt s Abb A 20 Diese Funktion ist auch ber die Tastenkombination Strg G w hlbar Zu jedem Zeitpunkt kann das erstellte Gitter gespeich
84. Shadern vorhanden sein Zu erwarten ist ein relativ gro er Bedarf an Arbeitsspeicher bedingt durch das Wachstum der Datenmenge bei jedem Unterteilungsschritt Software Als Zielplattform kommt prim r Windows 2000 XP zum Einsatz es soll aber auch die Ver wendung anderer Betriebssysteme unterst tzt werden Interoperabilit t Das Grobgitter zu einem gegebenen 3D Objekt soll durch eine geeignete externe Software zur Verf gung gestellt werden Nach durchgef hrter Unterteilung und Deformation des Gitters sollen die Ergebnisse d h die erstellte Gitterhierarchie an einen externen Mehrgitterl ser wie z B FEATFLOW 11 bergeben werden k nnen 145 146 ANHANG B PFLICHTENHEFT UND ENDPRODUKT B 1 3 Produktfunktionen Das Endprodukt soll eine Simulationsumgebung mit einer grafischen Benutzerschnittstelle bie ten Es sollen 3D Objekte und entsprechende Grobgitter geladen werden k nnen Auch ein Sichern und Wiederherstellen der Unterteilungsschritte soll implementiert werden Um eine Beurteilung der dreidimensionalen Gitter und Objekte zu gew hrleisten muss die Software ber eine frei dreh und skalierbare Objektansicht verf gen Eine Auswahl an Gl ttungs und Optimierungsalgorithmen soll zur Verf gung gestellt werden Die visuelle Darstellung der Si mulationsergebnisse kann durch ein externes z B Gnuplot 64 oder selbst implementiertes Programm erfolgen B 2 Endprodukt B 2 1 Erreichte Ziele Die geplante Ausnutzung der Leis
85. Testfall 105 F r den komplexen Testfall findet sowohl das Modell des Golf III als auch das initiale Grob gitter aus Testfall 8 Verwendung Die Benutzung der Gl tter wird durch den Anwender initiiert und beruht auf Erfahrungswerten Sind in einer Hierarchiestufe Gl tter aufgerufen worden so werden die Qualit tskriterien vor und nach deren Verwendung in Tabelle 6 17 aufgef hrt Im Gegensatz zu Unterteilungsschritt 1 und 2 in denen keine Gl tter verwendet werden wer den in Iteration 3 und 4 der Oberfl chen Jacobi Gl tter jeweils zehn mal aufgerufen In Tabelle 6 17 sind die Resultate der Gl ttung mit G markiert Wie in Testfall 8 konnte das Grobgitter aufgrund des zu geringen Arbeitsspeichers nicht mehr als vier mal unterteilt werden a Originalobjekt im Gitter b Durch das Gitter angen herte Objektoberfl che Abbildung 6 33 Gitter f r den komplexen Testfall 106 a Vor der Benutzung der Gl tter Abbildung 6 34 Gitter f r den komplexen Testfall nach vier Unterteilungen Die Jacobi Fehler sind markiert KAPITEL 6 PROJEKTVALIDIERUNG b Nach der Benutzung der Gl tter Unterteilungsstufe Jacobi Fehler Innenwinkel L ngenverh ltnis Gitterzellen 0 0 45 lt lt 157 2 88 160 1 0 38 lt lt 157 2 83 1280 2 0 30 lt a lt 159 3 82 10240 3 1 25 lt lt 167 4 99 81920 3G 0 25 lt a lt 187 4 99 81920 4 14 10
86. abefeld f r die Hexaederkantenl nge wenn dieser ber den Schieberegler ver ndert wurde void updatePointSizeSlider const OString amp text korrigiert die Position des Schiebereglers wenn der Wert f r die Punktgr e der Grobgitterknoten per Hand ver ndert wurde void updatePointSize int korrigiert den Wert im Eingabefeld f r die Punktgr e der Grobgitterknoten wenn dieser ber den Schieberegler ver ndert wurde void updateObjectPointSizeSlider const OString amp text korrigiert die Position des Schiebereglers wenn der Wert f r die Punktgr e der Objektknoten per Hand ver ndert wurde void updateObjectPointSize int korrigiert den Wert im Eingabefeld f r die Punktgr e der Objektknoten wenn dieser ber den Schieberegler ver ndert wurde void view all ver ndert die Ansicht so dass alle Grobgitterknoten angezeigt werden void view box ver ndert die Ansicht so dass alle Grobgitterknoten innerhalb eines minimalen Quaders der das Objekt einschliesst angezeigt werden void view near ver ndert die Ansicht so dass alle Grobgitterknoten angezeigt werden die entwe der interessante oder innere Knoten sind C 2 BERSICHT BER DIE KLASSEN VON HAGRID3D 169 void view_interest ver ndert die Ansicht so dass alle Grobgitterknoten angezeigt werden die inter essant sind void hide_Object schaltet die Sichtbarkeit des Objektes aus void unhide_Object schaltet die Sichtbarkeit des Obj
87. aeder unterteilt Es werden zuerst auf allen Kanten des Hexaeders die Mittelpunkte als neue Knoten hinzugef gt dann wird in jede der sechs Fl chen ihr Mit telpunkt als Knoten gesetzt Als letzter Knoten wird der Mittelpunkt des Hexaeders eingef gt Dieses Unterteilungsschema kann auf alle Hexaeder die mit keinem Knoten auf dem Dreiecks netz liegen angewandt werden Bei den Hexaedern am Objektrand ist diese Unterteilung nicht m glich Es muss bei diesen Hexaedern darauf geachtet werden dass neu hinzukommende Knoten eventuell ebenfalls auf dem Dreiecksnetz liegen m ssen F r diese Aufgabe wird ein Suchalgorithmus auf dem reduzierten Objekt gestartet der aus zwei Teilen besteht Abh ngig Dies ist eine wichtige Eigenschaft vor allem f r die sp ter beschriebenen Snakes 53 54 KAPITEL 5 SYSTEMBESCHREIBUNG von der Entfernung der Dreiecke innerhalb derer sich zwei Knoten befinden werden verschie dene Verfahren angewendet e Liegen beide Knoten innerhalb eines Dreiecks so wird der Mittelpunkt ihrer Verbin dungslinie zur ckgegeben e Liegen beide Knoten in zwei ber eine Kante benachbarten Dreiecken so werden die beiden Dreiecke an ihrer gemeinsamen Kante auf eine Ebene abgebildet wobei die Ab bildungen kongruent zu den Ursprungsdreiecken sind Danach wird wiederum der Mit telpunkt der Verbindungslinie der beiden Knoten zur ckgegeben e Haben die zwei Dreiecke einen gemeinsamen Eckpunkt so wird die Eins Ring Nachbar sc
88. ann als Parameterraum angesehen werden In den Vereinfachungsschritten wird das Dreiecksnetz als Graph angesehen und bestimmte Knoten dieses Graphen werden entfernt bis die Vereinfa chungsprozedur terminiert und das Basisnetz bereitstellt s Abb 2 3 Das gesamte Verfahren 16 KAPITEL 2 GRUNDLAGEN hat eine Zeit und Speicherkomplexit t von O N log N wobei N die Anzahl der Knoten des Netzes der feinsten Aufl sungsstufe also des Netzes ist mit dem begonnen wurde 30 W h rend die Vereinfachungsschritte durchgef hrt werden erh lt man eine Hierarchie von O log N Stufen des Netzes Die Basis f r die Auswahl der zu entfernenden Knoten bildet der Dobkin Kirkpatrick Algorithmus 9 der eine Hierarchie von O log N Vergr berungsstufen garan tiert a Mannigfaltigkeitstriangulierung b Basisnetz Abbildung 2 3 Mannigfaltigkeitstriangulierung und berechnetes Basisnetz f r das so genannte Stanford Bunny 56 2 2 1 Definitionen und Notationen Es werden zun chst die grundlegenden Begriffe die zum Aufbau einer Parametrisierung nach dem MAPS Verfahren ben tigt werden eingef hrt Die Oberfl che des gegebenen Objektes die parametrisiert werden soll liegt in Form einer Mannigfaltigkeitstriangulierung vor Eine Triangulierung einer Punktmenge sei definiert als Menge planarer Dreiecke deren Eckpunkte gleich der Punktmenge sind Die Seiten der Dreiecke werden als Kanten bezeichnet Ferner bil den die Kanten graphentheoreti
89. ann in alle Richtungen frei gedreht wer den eine Zoom Funktion ist ebenfalls verf gbar Ein Klick auf die Dijkstra Schaltfl che l st die Berechnung des Dijkstra Algorithmus aus s Abb 7 7 nun wird die Snake initialisiert Durch klicken auf die Algorithmus starten Schaltfl che wird der eigentliche Algorithmus solange ausgef hrt bis eines der Abbruchkriterien s Kap 5 4 3 greift Um eine akzeptable Geschwindigkeit bei der Darstellung der Snake Bewegung zu erreichen wird die Snake ledig lich nach jeweils 1000 Iterationen neu gezeichnet Zur besseren Evaluierung der Ergebnisse und des Verhaltens der Snake wurde eine Transparenzfunktion implementiert s Abb 7 8 7 2 PROTOTYPEN 123 Abbildung 7 7 Links Der Prototyp im Ausgangszustand Rechts Nach Dr cken der Dijkstra Schaltfl che wird die Snake initialisiert SSH RSET Abbildung 7 8 Links Nach dem Start des Algorithmus erreicht die Snake ihre endg ltige Po sition Rechts Durch Einschalten der Transparenz wird das Objekt durchsichtig 124 KAPITEL 7 ENTWICKLUNGSPROZESS Anhang A Benutzerhandbuch A 1 Installation Systemvoraussetzungen Betriebssystem MS Windows ME NT 2000 oder Windows XP Hardware Prozessor mit min 1 GHz empfohlen min 512 MB Arbeitsspeicher Nvidia Grafikkarte ab der GeForce 6 Reihe Empfohlene Hardware Prozessor mit 3 GHz 1 2 GB Arbeitsspeicher GeForce 6800 Gra fikkarte o
90. ann mittels Maus in den 2D Fenstern in alle Richtungen verschoben wer den Befindet sich das Objekt an der gew nschten Position k nnen im folgenden Schritt mit Hilfe des Inklusionstest die Knoten als solid markiert werden die sich im Inneren des Ob jektes befinden Die so markierten Knoten beschr nken den Objektrand von innen und sind gleichzeitig geeignete Knoten f r die Oberfl chenapproximation Ebenso sind nat rlich genau die Knoten m gliche Kandidaten die selber nicht als solid markiert sind aber einen direkten Nachbarn mit solid Markierung haben Diese werden in HaGrid3D auch interessante Knoten genannt und k nnen hervorgehoben dargestellt werden Zum Abbilden werden einzelne Knotenpaare jeweils ein Knoten des Grobgitters und einer des Geometrieobjekts markiert und auf dem Objektrand zusammengef hrt so dass nach und nach immer mehr Hexaederseitenfl chen des Grobgitters das Objekt approximieren Die je weils vier auf das Objekt verschobenen Knoten einer Hexaederseitenfl che liegen auf dem Objektrand und die Fl che selbst spiegelt eine Vergr berung der Oberfl che des Objektes wi der Werden jetzt mehr und mehr dieser Fl chen erzeugt muss sichergestellt werden dass die hierbei erzeugte Approximation des Objektes durch Hexaederseitenfl chen eine geschlosse ne Form annimmt Eine komplett geschlossene Form wird auch wasserdicht genannt und zur manuellen und visuellen Kontrolle werden alle bereits aufliegenden Hexaederseitenfl che
91. arametrisierung sowie Aktive Konturen Im Verlauf der PG kam es immer wieder zu Umstrukturierungen so beschaftig ten sich weitere Kleingruppen mit den Themen Entfernen von Selbstdurchdringungen durch lineare Optimierung Gitterunterteilung und Qt au erdem wurde existierende thematisch ver wandte Software evaluiert 117 118 KAPITEL 7 ENTWICKLUNGSPROZESS Die PG traf sich regelm ig Donnerstags um 16 00 Uhr um die Ergebnisse der Teilgruppen zu pr sentieren und das weitere Vorgehen abzusprechen Zu jedem Treffen wurde ein Proto koll angefertigt das den jeweiligen Stand der Entwicklung sowie die Aufgaben die von den PG Teilnehmern bis zum n chsten Treffen zu erledigen waren enthielt Zum besseren Aus tausch von Informationen wurden ein Online Forum und ein Webserver eingerichtet auf dem s mtliche Protokolle Seminarunterlagen sowie weitere ben tigte Dokumente hinterlegt wur den Zum Ende des ersten Semesters wurden erste Prototypen im Bereich Gitterunterteilung MAPS und Snakes erstellt Zus tzlich wurden kurze Texte verfasst die die bereits geleistete Arbeit zusammenfassen und der PG zu Beginn des zweiten Semesters als Grundlage dienen sollten 7 1 2 Ablauf der PG im zweiten Semester Nachdem sich herausgestellt hatte dass der Gittergenerator Cubit den Anforderungen nicht gen gen w rde wurde beschlossen einen eigenen Grobgittergenerator zu implementieren Die Hauptaufgaben des zweiten Semesters bestanden in der Weiterentwi
92. aten die einfache Adaption in bestehende Systeme die Erweiterbarkeit f r zuk nftige Hardware und die Unter st tzung f r nicht auf Shading ausgerichtete Anwendungen einer GPU Eine Shadersprache ersetzt weder die Grafik APIs wie DirectX oder OpenGL noch die Applikation Sie fungiert als Zwischenschicht und wird explizit nur ber definierte Programm parameter angesprochen s Abb 2 16 Die bergabe kann ber Assemblersprache oder die Runtime API erfolgen Application Direct3D API U Abbildung 2 16 Die Cg Architektur 34 Metasprachen Mit Hilfe von Metasprachen wie Sh 35 und BrookGPU 6 ist es m glich eine GPU soweit sie ber programmierbare Shader verf gt auf abstrakter Ebene zu programmieren Das hei t dass man die OpenGL DirectX oder herstellerspezifischen Erweiterungen nicht beachten muss Man kann sich ganz auf den Algorithmus und nicht auf die grafikspezifische Implementierung www microsoft com windows directx default aspx http www opengl org 2 6 GPGPU 39 konzentrieren Der Nachteil ist dass im Vergleich zu handgeschriebene Programmen zum Beispiel in Cg und OpenGL Leistungseinbu en in Kauf genommen werden m ssen Das liegt daran dass BrookGPU ein bersetzer Frontend darstellt und C bzw Shader Programme generiert und Sh mehr als ein Toolkit aufgefasst werden soll das zwar einen Compiler Optimierer usw beinhaltet aber auch nur einen Zwischencode liefert Auf d
93. atent must be licensed for everyone s free use or not licensed at all The precise terms and conditions for copying distribution and modification follow TERMS AND CONDITIONS FOR COPYING DISTRIBUTION AND MODIFICATION 0 This License applies to any program or other work which contains a notice placed by the copyright holder saying it may be distributed under the terms of this General Public Li cense The Program below refers to any such program or work and a work based on the Program means either the Program or any derivative work under copyright law that is to say a work containing the Program or a portion of it either verbatim or with mo difications and or translated into another language Hereinafter translation is included without limitation in the term modification Each licensee is addressed as you Activities other than copying distribution and modification are not covered by this Li cense they are outside its scope The act of running the Program is not restricted and the output from the Program is covered only if its contents constitute a work based on the Program independent of having been made by running the Program Whether that is true depends on what the Program does 1 You may copy and distribute verbatim copies of the Program s source code as you re ceive it in any medium provided that you conspicuously and appropriately publish on each copy an appropriate copyright notice and discla
94. aus einer Farbkom ponente wohingegen die Pixel in den gepackten Formaten aus den blichen vier Kan len RGBA bestehen Es standen verschiedene Grafikkarten der Hersteller ATI und NVIDIA zur Verf gung Die OpenGL Tests basierten vollst ndig auf der Verwendung von so genannten pBuffers Die neue re und einfacher zu handhabende Methode der so genannten Framebuffer Objects FBOs stand zum Zeitpunkt der Tests in den ATI Treibern noch nicht zur Verf gung Beide Methoden zie len darauf ab eine Textur alternierend als Ergebnisspeicher und Datenquelle zu verwenden Als exemplarische Testbeispiele sollen hier die Ergebnisse einer NVIDIA GeForce 6800 NV40 sowie einer ATI Radeon 9800 PRO dienen Die BrookGPU Ergebnisse waren um 5 10 langsamer als die LA Framework und OpenGL Implementierungen Zwischen OpenGL und DirectX wurden keine signifikanten Unterschiede festgestellt NVIDIA GeForce 6800 NV40 Abbildung 4 3 a stellt die Rechenleistung f r unterschiedliche Problemgr en basierend auf Texture Rectangles und Cg dar Es ist deutlich zu erkennen dass die Geschwindigkeit erst bei gr eren Problemen attraktiv wird bedingt durch Datentransferzeit und Overhead Erwar tungsgem sind die 16 Bit Texturformate am schnellsten allerdings auf Kosten der Genauig keit die ohne Nachkorrektur inakzeptabel ist Ungepackte Pixelformate laufen auf dieser Karte schneller als gepackte Abbildung 4 3 b zeigt die Rechenleistung f
95. bi Fehler Innenwinkel L ngenverh ltnis Gitterzellen 0 0 69 lt a lt 105 2 30 26 1 0 62 lt a lt 122 2 37 208 2 0 48 lt a lt 140 2 37 1664 3 0 38 lt a lt 152 2 44 13312 4 0 29 lt lt 165 3 08 106496 5 0 20 lt lt 171 8 32 851968 Tabelle 6 4 Werte der Qualit tskriterien f r Testfall 2 Testfall 3 a Originalobjekt im Gitter b Durch das Gitter angen herte Objektoberfl che Abbildung 6 13 Gitter f r Testfall 3 nach zwei Unterteilungen KAPITEL 6 PROJEKTVALIDIERUNG a Originalobjekt im Gitter b Durch das Gitter angen herte Objektoberfl che Abbildung 6 14 Gitter f r Testfall 3 nach f nf Unterteilungen Unterteilungsstufe Jacobi Fehler Innenwinkel L ngenverh ltnis Gitterzellen 0 0 49 lt a lt 150 2 14 26 1 1 27 lt lt 174 3 85 208 2 11 T lt a lt 179 5 99 1664 3 80 2 lt a lt 178 10 15 13312 4 377 1 lt a lt 179 25 44 106496 5 1692 0 lt a lt 180 51 40 851968 Tabelle 6 5 Werte der Qualit tskriterien f r Testfall 3 89 6 3 VALIDIERUNG DER RANDANPASSUNG DURCH PARAMETRISIERUNG Testfall 4 b Durch das Gitter angen herte Objektoberfl che a Originalobjekt im Gitter Abbildung 6 15 Gitter f r Testfall 4 nach zwei Unterteilungen b Durch das Gitter angen herte Objektoberfl che a Originalobjekt im Gitter Abbildung 6
96. cPoint getNextPoint cPoint point cEdge xlastEdge int direction Gibt den n chsten Knoten ausgehend von lastEdge ber point in Richtung direction zur ck int load const char filename Maps Modul zx maps modul bool faceKorrektur L dt die Datei ilename als Gitter Dabei werden gleichzeitig in maps_modul die entsprechenden Werte gesetzt damit zu jeden Zeitpunkt die n tige Datenkon sistenz zwischen den beiden Klassen herscht faceKorrektur steuert die Art und Weise wie der Status der geladenen Punkte auf die dar ber konstruierten Kanten und Fl chen bertragen wird int save const char filename Maps Modul maps modul Speichert das Gitter unter ilename ab Dabei werden die n tigen Daten beim Laden f r maps modul von maps modul geschrieben int saveSolverData const char filename Speichert in der Datei ilename die n tigen Daten des Gitters f r einen entspre chenden L ser int loadSolverData const char filename L dt vorher auf der GPU berechnete Daten f r die Visualisierung Klasse cMultiGrid Die Klasse cMultiGrid verwaltet ein cGrid und bietet zahlreiche zus tzliche Funktionen die auch die Oberfl chenparametrisierung mit einbeziehen Urspr nglich sollte die Klasse ein mehrfach aufgel stes Gitter speichern k nnen daher der Name der GPU L ser ben tigt aber nur eine Aufl sungsstufe void buildAllDisplayLists baut alle OpenGL Display Listen auf die zur Darstellung des Gitt
97. ch nach dem Delauney Kriterium optimiert 160 ANHANG API DOKUMENTATION vector lt st_point gt delaunay vector lt st_point gt punkte MyMesh mesh Liefert eine f r das 3D Netz g ltige Triangulierung der Punktmenge punkte die nach dem Delauney Kriterium optimiert ist Mesh ist eine Referenz auf das 3D Netz um die g ltige Einbettung zu berpr fen Der R ckgabewert ist eine Liste der Eingabepunkte in der immer drei aufeinander folgende Punkte ein Dreieck bilden Klasse Maps_Hinge dient zur Berechnung einer 2D Einbettung von zwei Dreiecken mit einer gemeinsamen Kante st point hinge MyMesh HalfedgeHandle heh bool links rechts MyMesh x myMesh Liefert eine 2D Einbettung von allen Dreiecken mit der Halbkante heh Der Para meter links rechts gibt an ob das von der Halbkante aus gesehen linke oder rechte Dreieck eingebettet wird Bei der Einbettung bleiben alle Innenwinkel und L ngenverh ltnisse erhalten Der R ckgabewert ist eine Liste von drei zweidimen sionalen Knoten die das Dreieck bilden Klasse Maps_Map dient zur Berechnung der konformen Abbildung eines Dreieckringes um einen Punkt vector lt st_point gt map MyMesh Point v point vector lt MyMesh Point gt ring bool verbose Gibt die Einbettung um den Punkt v_point zur ck ring ist eine Liste der ad jazenten Punkte von v_point Die R ckgabe ist die Liste der Nachbarpunkte in der zweidimensionalen Einbettung double length MyMesh Point p
98. chbarten Dreieck 3 Die Knoten liegen innerhalb eines Dreiecksf chers des Grobnetzes und keiner der ersten beiden F lle trifft zu 4 Keiner der obigen Fille trifft zu Im ersten Fall werden die baryzentrischen Koordinaten des Punktes pr mit Hilfe von T be rechnet Im zweiten Fall werden die benachbarten Dreiecke berpr ft und das Dreieck gefunden das den letzten Dreieckseckpunkt enth lt Dieses angrenzende Grobdreieck wird mit dem Dreieck in dem sich die anderen beiden Punkte befinden in die Ebene projiziert Im dritten Fall wird die Eins Ring Nachbarschaft gesucht zu der die Grobdreiecke geh ren in denen sich die Punkte des projizierten Feinnetzes befinden Diese Eins Ring Nachbarschaft wird mit der oben eingef hrten konformen Abbildung in die Ebene projiziert Im vierten Fall muss das Netz lokal vergr bert werden Danach folgt ein weiteres Pr fen der obigen Fille Auf jeder der O log N Hierarchiestufen werden alle Knoten des Netzes durchlaufen Die Laufzeit bel uft sich somit auf O N log N 2 3 GITTER 23 2 3 Gitter Nach der Darstellung der unterschiedlichen Gittertypen in Kapitel 2 1 3 folgt eine bersicht ber die verschiedenen Qualit tskriterien denen Gitter in der computergest tzten Simulation gen gen m ssen Anschlie end werden verschiedene Methoden vorgestellt um die Qualit t eines Gitters zu erh hen Zun chst soll jedoch die Gitterunterteilung motiviert werden Das Entfernen von sog Selbstdurchdring
99. cklung der Prototypen und der anschlie enden Integration zu InGrid3D Das offizielle Ende der Projektgruppenarbeit stellt dieser Endbericht sowie die Abschluspr sentation dar 7 2 Prototypen Im Laufe der PG wurden verschiedene Prototypen erstellt um die eingesetzten Techniken auf ihre Tauglichkeit zu untersuchen und optimieren zu k nnen Es werden im Folgenden drei Pro totypen vorgestellt deren Techniken auch im Endprodukt zum Einsatz kommen 7 2 1 Gitterunterteilung Prototyp Der Gitterunterteilung Prototyp bietet eine grafische Benutzeroberfl che mit der Probleme und Ergebnisse der Gitterunterteilung Gittergl ttung und Gitterkorrektur visualisiert werden k n nen Beim Start des Prototypen wird ein 3 x 3 x 3 Gitter erzeugt wobei der innere Hexaeder das zu umstr mende Objekt repr sentiert s Abb 7 1 Damit verschiedene Varianten der m g lichen Fl chenformen ausprobiert werden k nnen wird an jeder Seite des inneren Hexaeders eine B zier Fl che implementiert deren Verhalten mit Hilfe von Steuervariablen beeinflusst werden kann F r verschiedene Betrachtungsperspektiven kann das Objekt in alle Richtungen frei gedreht sowie vergr ert werden Nach der Gitterunterteilung s Abb 7 2 wird das Gitter neu gezeichnet die entstandene Approximation der Oberfl che kann in der Objektrand Ansicht betrachtet werden s Abb 7 3 Zur besseren Evaluierung der Ergebnisse wird die Anzahl der Punkte Kanten Fl chen Hexaeder und Jacobi
100. d in Kombination mit zus tzlichen Tastaturbefehlen werden die jeweiligen Funktionen umgesetzt Der Import der Geometrie erfolgt mittels einer STL Schnittstelle F r das Grobgitter ist das Laden Speichern und Exportieren nach InGrid3D vorgesehen Die Hauptfunktionalit t besteht darin die Koordinaten eines Grobgitterknotens auf die Koor dinaten eines Geometrie Eckpunkts zu setzen und gesondert zu markieren damit sie sp ter bei der Parametrisierung in nGrid3D entsprechend behandelt werden k nnen Alle Grobgitterkno ten werden zun chst einem nklusionstest unterzogen um die Knoten innerhalb des Objektes als solid zu markieren Mit dieser Information kann auch die Menge der Grobgitterknoten die auf den Objektrand zu bewegen sind wesentlich eingeschr nkt werden W hrend des ma nuellen Verschiebens von Grobgitterknoten erm glicht eine zuschaltbare Visualisierung der am Objekt anliegenden Hexaederseitenfl chen eine Sichtpr fung auf die Wasserdichtigkeit des Grobgitters Nach dem Starten des Grobgittergenerators muss zun chst ein Objekt in Form einer Oberfl chentriangulierung geladen werden Anschlie end kann das standardm ig erzeugte Grobgit ter angepasst werden indem die Anzahl der Hexaederzellen in X Y und Z Richtung und die Kantenl nge der Hexaederzellen ver ndert werden Mit diesen Informationen wird ein Grob gitter erzeugt das aus gleichf rmigen Hexaederw rfeln besteht Das Objekt liegt im Zentrum des Grobgitters und k
101. dem Objekt Punklgr sse Abbildung A 9 Positionieren des Objektes im Grobgitter 132 ANHANG A BENUTZERHANDBUCH Der n chste Schritt besteht in der automatischen Markierung der Grobgitterknoten die ber die Knotenmarkierung setzen Schaltfl che eingeleitet wird Ist die Berechnung abgeschlos sen stehen von nun an neue Ansichtsoptionen zur Verf gung die durch die neuen Knoten markierungen erm glicht werden Die Schaltfl che wird deaktiviert In Abbildung A 10 ist die Objektoberfl che transparent und somit sieht man die rot eingef rbten inneren Knoten Freeware erobgitter Datei Help Grobgitter Parameter Kantenl nge n BTH xz Grobgitter erzeugen Objekt Transparent Aus d Ansicht Alle Knoten innerhalb einer Box um Objekt C interest und innere Knoten nurinteresHKnoten Hexaeder anzeigen IV nur die Schnittkanten anzeigen Hexaederseitenfl chen auf dem Objekt Punktgr sse Cifbokumente und EinstellingenjklausjEigene Datelenjcvs grobgiter binftutoril_abjekt st98 Punkte und 192 Fl chen Abbildung A 10 Nach dem Inklusionstest sind alle inneren Knoten markiert rot eingef rbt und es stehen neue Ansichtsoptionen f r die interessanten Knoten zur Verf gung Nun kann mit der Manipulation einzelner Grobgitterknoten begonnen werden Zun chst soll te man in der Optionenleiste die Opti
102. den Objekt befinden zum An deren konvergieren die aktiven Konturen h ufig nicht in Randeinbuchtungen da z B dann die Biegeenergie st rker als die Bildenergie wirkt Mit der Methode des Gradient Vector Flow GVF 66 werden diese Probleme zumindest teilweise gel st dabei werden mit Hilfe von Diffusionsgleichungen die f r die Snake relevanten Bildinformationen so manipuliert dass be reits aus relativ gro er Entfernung die Snake in Richtung der zu erfassenden Details gezogen wird In Abbildung 2 14 werden die Vorteile von Gradient Vector Flow gegen ber herk mmli chen Snakes deutlich 34 KAPITEL 2 GRUNDLAGEN O O v e Abbildung 2 14 Erste Zeile Eine herk mmliche Snake muss in der N he des Objektes in itialisiert werden die Randeinbuchtung wird nicht erfasst Zweite Zeile Die GVF Snake kann in gr erem Abstand zum Objekt initialisiert werden und erfasst auch die Randausbuchtung Dritte Zeile Die GVF Snake kann auch quer ber das Objekt initialisiert werden bei her k mmlichen Snakes funktioniert dies h ufig nicht 2 5 2 Active Net Eine Erweiterung des Snake Konzepts auf die dritte Dimension wurde von Takanashi et al 57 vorgestellt einen vergleichbaren Ansatz hat Ahlberg 1 entwickelt Beide verfolgen ein hnli ches Prinzip Aus einem Volumendatensatz wird eine bestimmte Information extrahiert indem ein vorgegebenes Objekt wie z B die Oberfl chentriangulierung einer Kugel an das zu extra hierende
103. der besser Installation der Programme InGrid3D und HaGrid3D Die Programme InGrid3D und HaGrid3D finden sich auf der PG Homepage Der Name der Datei ist pg471 zip Diese gepackte Datei enth lt die Programme InGrid3D und HaGrid3D und alle notwendigen Bibliotheken Die ZIP Datei muss in ein beliebiges Verzeichnis entpackt werden Zum Starten der Programm muss die Datei ingrid3d exe bzw hagrid3d exe ausgef hrt werden Die Installation ist damit abgeschlossen A 2 Tutorial Die Bedienung von nGrid3D und HaGrid3D wird im Folgenden an Hand von Anleitungen engl tutorials erl utert Dabei wird exemplarisch ein Anwendungsfall von der Erstellung eines Objektes ber die Gittergenerierung und Unterteilung bis hin zur Simulation und Visua lisierung der Ergebnisse beschrieben Ihttp 1s7 www cs uni dortmund de students projectgroups pg471 shtml 125 126 ANHANG A BENUTZERHANDBUCH A 2 1 Tutorial Erzeugung eines 3D Objektes mit Blender Die bei der Str mungssimulation verwendeten Objekte k nnen auf unterschiedliche Weise bezogen werden Entweder durch Herunterladen aus einer Modelldatenbank aus dem Inter net 59 durch die Exportfunktion einer CAD Software oder aber durch die Erzeugung mittels eines 3D Modellierungsprogrammes Letzteres soll hier an Hand der Software Blender 4 de monstriert werden Zun chst m ssen noch einmal die wichtigsten Eigenschaften und Voraus setzungen der Objekte f r die Verwendung in den von der PG er
104. die aber in Breite und H he und Tiefe variieren k nnen 3 Strukturierte Gitter bestehen aus Zellen gleichen Typs und gleicher Konnektivit t die aber in Gr e und Ausrichtung variabel sind Konnektivit t bezeichnet hierbei dass alle Gitterzellen au er denen am Rand gleich viele Nachbarzellen haben 4 Allgemein strukturierte Gitter sind Gitter die auf irgendeine Art und Weise strukturiert sind beispielsweise durch Polygone und Kreise 5 Unstrukturierte Gitter verwenden verschiedene Zelltypen in einem Gitter oder haben va riable Konnektivit t 2 1 GUNDLAGEN DES CFD 9 Abbildung 2 1 Beispiele f r die verschiedenen Gittertypen von links oben nach rechts unten Rechteckig strukturiertes Gitter strukturiertes Gitter allgemein strukturiertes und unstruktu riertes Gitter 2 1 4 Behandlung von Randbedingungen Randbedingungen dienen der Kontrolle des Verhaltens der zu simulierenden Funktionen am Rand des Simulationsgebiets Werden die Werte einer Variablen v auf ON explizit durch die Angabe eines Wertes gesetzt u x f x f r x Q so spricht man von Dirichlet Randbedingungen Wird hingegen lediglich der Wert der Ableitung der Variablen vorge schrieben Vv x f x f r x 0 C Q so spricht man von Neumann Randbedingungen Bei nat rlichen Randbedingungen engl do nothing condition werden gar keine Werte ge setzt Man beachte dass die Randbedingungen durchaus f r verschiedene Variablen innerhalb
105. dierung werden Visualisierungen der berechneten Skalarfelder u verglichen Abbildung 6 36 zeigt keine sichtbaren Unterschiede zwischen der GPU und der CPU L sung Weiterhin wurde die L sung f r das Gitter des Testfalls 6 Klotz berechnet s Abb 6 37 Als abschlie ender Test wurde das Gitter des Testfalls 8 nach drei Unterteilungen an den GPU L ser bergeben s Abb 6 38 Abbildung 6 35 Das initiale Skalarfeld wird auf einem regul ren Gitter dargestellt 6 8 L SER 109 Abbildung 6 36 Vergleich zwischen der GPU und der CPU L sung Das obere Bild zeigt das Skalarfeld der L sung auf der GPU und das untere die L sung auf der CPU 110 KAPITEL 6 PROJEKTVALIDIERUNG Abbildung 6 37 Vergleich zwischen der GPU und der CPU L sung Das obere Bild zeigt das Skalarfeld der L sung auf der GPU und das untere die L sung auf der CPU 6 9 LEISTUNGSTESTS 111 Abbildung 6 38 Vergleich zwischen der GPU und der CPU L sung Das obere Bild zeigt das Skalarfeld der L sung auf der GPU und das untere die L sung auf der CPU 6 9 Leistungstests In diesem Kapitel soll das Laufzeitverhalten sowie der Speicherverbrauch der Anwendung ana lysiert werden Als Testsystem diente ein Athlon 64 3000 mit 1 5 Gigabyte Hauptspeicher Laufzeitverhalten In Tabelle 6 18 ist die Laufzeit f r die Erzeugung des Grobnetzes der Parametrisierung P sowie f r die ersten f nf Unterteilungsschritte und die jeweils darauffolgenden
106. diglich ein geeigneter Kernel implementiert werden Die Testroutine bestand aus einer bestimmten Anzahl von SAXPY Durchl ufen mit unter schiedlichen Problem und Iterationsgr en Die Anzahl der Iterationen war bei kleinen Pro blemgr en h her um den Einfluss der Datentransferzeit und des sonstigen Overheads m g lichst zu minimieren Bei gr eren Problemen f hren solche hohen Iterationszahlen aber zu sehr langen Rechenzeiten daher wurden in diesen F llen weniger Iterationen durchgef hrt Die Experimente wurden f r verschiedene Einstellungen bzw Texturformate durchgef hrt Die Tests in OpenGL wurden f r alle Kombinationen aus Shadersprache Texturformat und inter SSE Streaming SIMD Extensions ist eine x86 Befehlssatzerweiterung 50 KAPITEL 4 VORARBEITEN ner Flie kommarepr sentation durchgef hrt In DirectX und BrookGPU wurden exemplarisch verschiedene Texturformate getestet Dabei werden folgende Abk rzungen verwendet R32 Eine Textur mit einem Farbkanal unpacked und 32 Bit Farbtiefe RGBA32 Eine Textur mit vier Farbkan len packed und 32 Bit Farbtiefe RGBA16 Eine Textur mit vier Farbkan len und 16 Bit Farbtiefe 2D 2D Texturen OpenGL RECT RECT Texturen OpenGL CG Shader in der Sprache Cg implementiert GLSL Shader in der Sprache GLSL implementiert BROOK Bei Brook kann man das Backend OpenGL DirectX frei w hlen Bei den so genannten ungepackten Pixelformaten besteht jeder Pixel nur
107. dpunkte nicht trivial Nachdem dieses Problem bereits von G d deke mit Hilfe geometrischer Projektionstechniken untersucht wurde 14 entschied sich die PG dazu einen alternativen Ansatz auf Basis einer Parametrisierung zu entwickeln Dabei wird die Oberfl chentriangulierung sukzessive vergr bert ohne dass seine Struktur verloren geht W hrend der Unterteilung dient dieses grobe Netz als Parameterraum f r die Randanpassung Das so berechnete Gitter muss h ufig noch nachbearbeitet werden da die einzelnen Hexader zellen unter Umst nden von ung nstiger Qualit t sein k nnten Das Resultat ist ein optimal an das Objekt angepasstes Hexaedergitter Auf diesem Gitter wird mittels eines GPU basierten L sungsverfahrens eine Str mungssimulation durchgef hrt um prototypisch die Nutzbarkeit dieser Gitter zu demonstrieren 4 KAPITEL 1 EINLEITUNG 1 4 Struktur des Berichtes Nach der allgemeinen Einleitung der genauen Aufgabenstellung und der Einordnung des Be richtes stellt Kapitel 2 zun chst die ben tigten theoretischen Grundlagen bereit e Kapitel 2 1 bietet eine Einf hrung in die ben tigten mathematischen Grundlagen der numerischen Str mungssimulation Dabei wird insbesondere das zugrundeliegende ma thematische Modell potential flow auf der Basis der Poisson Gleichung erkl rt In Kapitel 2 2 wird gezielt die Methode Multiresolution Adaptive Parametrization of Surfaces MAPS beleuchtet welche in der Implementierung von I
108. du data 3Dscanrep 57 TAKANASHI I MURAKI S DOI A und KAUFMANN A 3D Active Net for Volume Extraction Proc SPIE Electronic Imaging 98 184 193 1998 58 THELIN J The Independent Qt Tutorial http www digitalfanatics org projectsf qt tutorial 59 TIMASHEV A 3D car gallery http www 3dcar gallery com 60 TROLLTECH Qt http www trolltech com products qt index hem 61 TUREK S Efficient Solvers for Incompressible Flow Problems An Algorithmic and Computational Approach Springer Berlin 1999 LITERATURVERZEICHNIS 183 62 WALTER R Differentialgeometrie Wissenschaftsverlag Bibliographisches Institut 1978 ISBN 3 411 01543 8 63 WESSELING P Principles of computational fluid dynamics Springer Berlin 2001 64 WILLIAMS T und KELLEY C Gnuplot http www gnuplot info 65 WOBKER H Beschreibung und Implementierung einer Segmentierungs Methode zur Parametrisierung von Dreiecksnetzen Diplomarbeit Universit t Duisburg Essen 2003 66 Xu C und PRINCE J L Active Contours Deformable Models and Gradient Vector Flow http iacl ece jhu edu projects gvf 67 Xu C und PRINCE J L Snakes Shapes and Gradient Vector Flow IEEE Transactions on Image Processing 7 3 359 369 1998
109. e Program subject to these terms and conditions You may not impose any further re strictions on the recipients exercise of the rights granted herein You are not responsible for enforcing compliance by third parties to this License If as a consequence of a court judgment or allegation of patent infringement or for any other reason not limited to patent issues conditions are imposed on you whether by court order agreement or otherwise that contradict the conditions of this License they do not excuse you from the conditions of this License If you cannot distribute so as to satisfy simultaneously your obligations under this License and any other pertinent obli gations then as a consequence you may not distribute the Program at all For example if a patent license would not permit royalty free redistribution of the Program by all those who receive copies directly or indirectly through you then the only way you could satisfy both it and this License would be to refrain entirely from distribution of the Program If any portion of this section is held invalid or unenforceable under any particular cir cumstance the balance of the section is intended to apply and the section as a whole is intended to apply in other circumstances It is not the purpose of this section to induce you to infringe any patents or other property right claims or to contest validity of any such claims this section has the sole purpose of protecting the integrity
110. e j gilt 4 falls j i oul 2 4 1 fallsj i N 1 i 1 i 1i N 1 0 sonst Es handelt sich also um eine Matrix die nur auf f nf B ndern Eintr ge besitzt die ungleich 0 sind Eine solche Matrix wird auch pentadiagonal genannt Der Fall Q C R Wie schon im zweidimensionalen Fall werden hier quidistante Abst nde angenommen Durch Hinzunahme der z Achse entsteht eine symmetrische N 1 x N 1 Matrix Sie hat sieben B nder 6 falls 7 i oul h 4 1 falls j i N 1 2 iA N41 i 1 i4 1 i N 1 i N 1 0 sonst Das L sen des entstandenen linearen Gleichungssystems mit einer der in Kapitel 2 1 5 darge stellten Verfahren f hrt zu einer numerischen L sung der Poisson Gleichung 2 2 MULTIRESOLUTION ADAPTIVE PARAMETERIZATION OF SURFACES 15 2 1 7 Potential Flow Da ein ideales inkompressibles Fluid mit konstanter Dichte ohne anf ngliche Verwirbelungen auch im weiteren Verlauf keine Verwirbelungen generieren wird ist es mathematisch sinnvoll ein Fluid unter der folgenden Bedingung zu betrachten Zu jedem Zeitpunkt sei Vxu 0 2 9 hiebei ist V x u die so genannte Rotation des Vektorfeldes u Sei u u1 u2 u3 7 dann ist V x u definiert durch Ozug Vxu O3U4 O4u3 Ein Vektorfeld f r das Gleichung 2 9 gilt wird als wirbelfrei bezeichnet Solche Str mungen werden irrotational flow genannt und k nnen als Gradient eines skalaren Potentials aufgefasst werden
111. e zur Darstellung ben tigt werden Zudem enth lt sie Methoden die auf die Oberfl chentriangulierung und auf das Grobgitter gleichzeitig zugreifen m ssen da sich hier die Schnittstelle aller aktuellen Objekte befindet reset die vier Ansichten auf das Objekt werden auf Ihre Startansichten zur ckgesetzt change View 180 in den drei 2D Fenstern wird die Ansicht auf die jeweilige R ckansicht gesetzt initializeGL Die Beschreibung der Koordinaten Richtung St rke und Farbe der Lichtquellen die sich innerhalb der Szene befinden und das Objekt anstrahlen Die Materialei genschaften von zu zeichnenden Fl chen und Kanten werden ebenfalls definiert resizeGL int w int h die Gr sse der aktuellen Ansicht wird gesetzt C 2 BERSICHT BER DIE KLASSEN VON HAGRID3D paintGL die OpenGL Befehle zum Zeichnen des Grobgitters und des Objektes werden hier aufgerufen paintSelectedGL Neuzeichnen von Objekten die durch den Benutzer ver ndert wurden Dies bein haltet das Verschieben von Knoten und das Ver ndern der Ansicht mousePressEvent QMouseEvent evt Interaktion mit der Maus Bei einer Bet tigung der Maustaste werden die aktuellen Bildschirmkoordinaten berschrieben mouseMoveEvent QMouseEvent evt Bei einer Bewegung der Maus werden in Kombination mit verschiedenen Tasten folgende Aktionen ausgef hrt e Bei gedr ckter linker Maustaste wird in den 2D Fenstern die Ansicht auf das Objekt
112. ect TE VideoScape with Vertex Colors obj wavefront obj Wavefront2 obj Wings3D wings X3D Extensible 3D 30 Abbildung A 6 Ble nder bietet vielf ltige Exportm glichkeiten f r 3D Objekte 130 ANHANG A BENUTZERHANDBUCH A 2 2 Tutorial Erzeugung eines Grobgitters in HaGrid3D Nach dem Starten von HaGrid3D s Abb A 7 kann zun chst ein Objekt im STL Format ge laden werden In diesem Tutorial wird das in Kapitel A 2 1 erzeugte Objekt geladen Um die Perspektive zu ver ndern kann die Ansicht bei gedr ckter linker Maustaste gedreht und bei gedr ckter rechter verschoben werden Mit Hilfe des Mausrades wird der Bildausschnitt in Stufen bei gedr cktem Mausrad und vertikaler Bewegungsrichtung der Maus stufenlos ver gr ert Datei Help Grobgitter Parameter m Brobgiller erzeugen igen Hexaederseitenfl chen auf dem Objekt Punktgr sse 5 ke G RED wt d 5 kugel_lowres stl2562 Punkte und 5120 Fl chen Abbildung A 7 Die Benutzeroberfl che von HaGrid3D unmittelbar nach dem Start Ist das neue Objekt eingelesen worden so ist es zun chst sinnvoll die Parameter des Grob gitters an das Objekt anzupassen Hierzu wird zun chst die Kantenl nge der Hexaederzellen ber den gleichnamigen Schieberegler angepasst und dann die Anzahl der Grobgitterknoten in alle Dimensionen bestimmt s Abb A 8 Im n chsten
113. ecutable 174 ANHANGD LIZENZ If distribution of executable or object code is made by offering access to copy from a designated place then offering equivalent access to copy the source code from the same place counts as distribution of the source code even though third parties are not compelled to copy the source along with the object code You may not copy modify sublicense or distribute the Program except as expressly pro vided under this License Any attempt otherwise to copy modify sublicense or distribute the Program is void and will automatically terminate your rights under this License Ho wever parties who have received copies or rights from you under this License will not have their licenses terminated so long as such parties remain in full compliance You are not required to accept this License since you have not signed it However nothing else grants you permission to modify or distribute the Program or its derivative works These actions are prohibited by law if you do not accept this License Therefo re by modifying or distributing the Program or any work based on the Program you indicate your acceptance of this License to do so and all its terms and conditions for copying distributing or modifying the Program or works based on it Each time you redistribute the Program or any work based on the Program the recipient automatically receives a license from the original licensor to copy distribute or modify th
114. eise in Gleichungen zu berf hren Aufstellen des linearen Optimierungsproblems Es wird das Optimierungsproblem f r einen freien Knoten p dessen Position opimiert werden soll aufgestellt Sei nun n die Anzahl der zu p inzidenten Elemente dann ist A die 3 x n Matrix deren i te Spalte der Vektor axi ayi N ist Diese Vektoren werden wie in Gleichung 2 13 f r jedes Element des lokalen Teilnetzes gebildet Sei weiterhin m der d 1 wertige Vektor der die Koordinaten von p und in der letzten Komponente die momentane Sch tzung der minimierten Fl chen enth lt Nun gilt also A m c s hierbei ist c der Vektor der die in Gleichung 2 15 definierten c enth lt und s der Vektor der Schlupfvariablen wobei die i te Komponente s die Differenz zwischen der momentanen Sch tzung des minimalen Fl cheninhalts und der Fl che des Dreiecks angibt Das ergibt das duale Problem bim unter der Bedingung Afm s c gt 0 Hierbei ist b ein 3 wertiger Vektor dessen erste zwei Komponenten Null sind und die letzte Komponente eins Nach Definition ist dann das prim re Problem minc y unter der Bedingung Ay b y gt 0 Das lineare Optimierungsproblem ist gel st wenn s gt 0 also alle Fl cheninhalte mindestens so gro sind wie der minimierte Fl cheninhalt und gleichzeitig die Bedingung 0 erf llt ist 2 4 2 Anwendung auf Hexaedernetze Die Entfernung von Selbstdurchdringungen durch lineare Optimierung kann nicht garanti
115. ektes ein void blend object on schaltet die Transparenz des Objektes ein void blend object off schaltet die Transparenz des Objektes aus void refresh all aktualisiert die Objektansichten void drawHexas ver ndert den Status der Sichbarkeit der Hexaederzellen des Grobgitters void mark_solid f hrt f r s mtliche Grobgitterknoten einen Inklusionstest durch und markiert diese entsprechend void drawPseudoEdges ver ndert den Status der Sichtbarkeit so dass nur Grobgitterkanten angezeigt wer den die den Objektrand schneiden void drawPseudoFaces ver ndert den Status der Sichbarkeit der Hexaederseitenfl chen deren s mtliche Knoten auf den Objektrand verschoben wurden void resizeEvent QResizeEvent x wird automatisch aufgerufen wenn die Gr e des Fenster ver ndert wurde und passt die Gr e der Ansichtsfenster an void keyPressEvent OKeyEvent wird automatisch aufgerufen wenn die Tastatur bet tigt wird und sorgt f r die Ausf hrung aller Tastaturbefehle 170 ANHANG API DOKUMENTATION void keyReleaseEvent QKeyEvent wird automatisch aufgerufen wenn ein Tastendruck ausgel st wird Klasse object verwaltet die Informationen des Geometrieobjekts und stellt einfache Funktionen zur Unter st tzung der Visualisierung zur Verf gung void paint zeichnet das Objekt void paintPoint const floatx int zeichnet die Eckpunkte des Geometrieobjekts void load File co
116. ektoberfl che e Objektinneres Der Polyeder liegt im Inneren des Objektes e Rand Der Polyeder liegt auf dem u eren Rand bzw auf dem Windkanalrand Im Ge gensatz zur Objektoberfl che ist die Unterteilung hier trivial man braucht keine Parame trisierung Die Datenstrukturen verwalten Referenzen auf die inzidenten Polyeder der jeweils n chsth heren Dimension Ein Knoten hat bis zu sechs Referenzen auf inzidente Kanten Kanten bis zu vier Referenzen auf inzidente Fl chen und Fl chen bis zu zwei Referenzen auf inziden te Hexaeder Diese Referenzen vereinfachen und beschleunigen viele Algorithmen auf dieser Datenstruktur 5 5 GITTERUNTERTEILUNG 67 5 5 2 Ablauf der Gitterunterteilung Kopieren der alten Knoten Zun chst werden im ersten Schritt alle Knoten des alten Gitters in das neue Gitter kopiert Unterteilung der Kanten Im Mittelpunkt jeder einzelnen Kante aus dem alten Gitter wird ein Knoten erzeugt und der Knotenmenge des neuen Gitters hinzugef gt Der Randstatus dieses Knotens wird auf den Randstatus der unterteilten Kante gesetzt Liegt die zu unterteilende Kante auf dem Objektrand so wird die Mitte der Kante ber die Oberfl chenparametrisierung bestimmt ansonsten wird die arithmetisch Mitte bestimmt Abbildung 5 11 Unterteilung der Kanten Dann werden zwei Kanten erzeugt von den Endknoten der alten Kante zum neu erzeugten Knoten in der Mitte der alten Kante Die alte Kante wird verworfen in das neue Gitter
117. ellt wurde Das GPUGRID Format wird ebenfalls bin rkodiert gespeichert Als erstes wird die Variable nPoints die die Anzahl der Gitterknoten angibt gespeichert Im Anschluss daran werden alle Distanzinformationen f r jeden Knoten als st ruct vom Typ dist_inf gespeichert Darin befinden sich die Abst nde zu den jeweiligen rechten linken oberen unteren vorderen und hinteren Nachbarknoten und der Randstatus des Knotens Es 144 ANHANG A BENUTZERHANDBUCH folgen die Informationen f r die Breite die H he und die Tiefe des Gitters Als n chstes wird f r jeden Punkt die X Y und Z Koordinate gespeichert Am Ende der Datei werden erst die maximalen dann die minimalen X Y und Z Koordinaten der Knoten gespeichert A 3 5 GPU Format Dieses Format wird vom GPU L ser nach der Berechnung erzeugt und kann in InGrid3D im portiert und dargestellt werden Es wird ebenfalls im Bin rformat gesichert Am Anfang der Datei stehen die Informationen f r die Breite die H he und die Tiefe des Gitters Danach folgen die Koordinaten der Punkte Als n chstes wird das Geschwindigkeits vektorfeld gesichert in dem zuerst die X Werte dann die Y Werte und danach die Z Werte geschrieben werden Im Anschluss daran wird der berechnete Druck wert abgespeichert A 3 6 GMV Format Das GMV Format wurde vom GPU L ser verwendet um bereits in der Implementierungspha se ber eine Visualisierungsm glichkeit zu verf gen Die Spezifikation des Dateiformats kan
118. elnen Grafikkarten nicht mit Assemblercode programmieren zu m ssen wurden in nerhalb der letzten Jahre Shader Hochsprachen zur Programmierung dieser Karten entwickelt Im Gegensatz zu so genannten Offline Shadersprachen deren verwendete Algorithmen nicht effizient auf Hardware implementierbar sind wurden Cg 34 HLSL 38 und GLSL 44 in Hinblick auf ihre Implementierbarkeit bez glich einer Rendering Pipeline entworfen Ziel bei der Entwicklung war es also eine Sprache zu entwickeln die der GPU Hardware leicht zu g nglich ist und dort direkt ausgef hrt werden kann Da sich die Sprachen im Aufbau und Leistung sehr hnlich sind bezieht sich das folgende Beispiel auf Cg 38 KAPITEL 2 GRUNDLAGEN Vorteile einer Shadersprache am Beispiel von Cg Bei der Entwicklung der Sprache Cg wurde haupts chlich auf die Kriterien Programmierbar keit und Portabilit t besonderes Augenmerk gelegt Einfache Programmierbarkeit bedeutet in diesem Fall ein h heres Abstraktionslevel als Assemblersprachen und Wiederverwendbarkeit von Quelltext und die M glichkeit zur Quelltext Strukturierung durch Schnittstellen Structs und Methodenaufrufe Unter Portabilit t versteht man die Unabh ngigkeit von Hardwareher stellern Hardwaregenerationen Betriebssystemen und den unterschiedlichen 3D APIs Wei tere wichtige Kriterien waren die vollst ndige Unterst tzung der Hardwarefunktionalit t die Perfomanz die minimale Beeinflussung der Organisation von Anwendungsd
119. em Kapitel soll der Einfluf der initialen Objektreduzierung auf die Projektion bei der Unterteilung des Gitters praktisch untersucht werden Dazu werden drei ausgew hlte Objek te mit verschiedenen initialen Objektreduzierungen drei Mal unterteilt und anschlie end die Qualit t des Gitters gemessen Es werden keinerlei Gl ttungsoperatoren angewendet Zun chst wird Testfall 1 betrachtet der aus der hoch aufgel sten Kugel mit 327680 Dreiecken besteht Hier ist neben den Qualit tswerten auch die Laufzeit des Programms zu beachten Ist die Reduzierung nicht ausreichend kommen fast ausschlie lich die aktiven Konturen zum Einsatz die dann auf einem sehr feinen Netz k rzeste Wege finden m ssen was zu einer in akzeptabel hohen Laufzeit f hrt Darum wurde bei diesem Objekt auf Tests die Evaluierung sehr geringer Reduzierungen verzichtet W hrend die dritte Unterteilung auf dem Testsystem ohne Reduzierung 323 Sekunden dauerte dauerte sie mit 226 Restdreiecken nur 19 5 Sekun den Reduziert man die Anzahl der Restdreiecke noch weiter so wird die Laufzeit aber wieder deutlich schlechter Als n chstes wird Testfall 2 betrachtet die grob aufgel ste Kugel Sie besteht aus 80 Dreiecken An den Qualit tswerten l sst sich erkennen da sich eine Objektreduzierung bei solch groben 104 KAPITEL 6 PROJEKTVALIDIERUNG Anzahl Restdreiecke Jacobi Fehler Innenwinkel L ngenverh ltnis 39086 0 31 lt a lt 162 4 31 8282 0 32
120. en Finite Differenzen Approximation des Laplace Operators Aus der Definition der Differenzierbarkeit von u folgt ula h y z u z y z 2 h 0 h en 8 KAPITEL 2 GRUNDLAGEN aber auch h SI c lim GEZ y z u x X 2 4 h 0 h Aus 2 3 und 2 4 folgt nun 1 u z h y 2 u z 2 Ov lim 2h 2 5 Dies f hrt zu einer besseren Diskretisierung als 2 3 oder 2 4 vgl 55 Indem der Differen tialquotient 2 5 durch den Differenzenquotienten ersetzt wird erh lt man eine Approximation der partiellen Ableitung von u nach x ulz h y z ula z 2h Ur f r kleines h F r die zweite partielle Ableitung nach x gilt somit 2 2 2u z y z 2u x z n2 Ura Dies motiviert Ure Uyy uz als Diskretisierung des Laplace Operators Zerlegung des Gebiets Das kontinuierliche Gebiet Q wird in eine endliche Anzahl von geometrisch einfachen Teil gebieten zerlegt Dies sind z B Dreiecke und Rechtecke in der Ebene bzw Tetraeder und He xaeder im Raum Diese Teilgebiete werden Zellen genannt Die Gesamtheit wird als Gitter bezeichnet Hierbei werden die folgenden Typen von Gittern unterschieden vgl Abb 2 1 1 Uniform strukturierte kartesische Gitter bestehen aus achsenparallelen Zellen gleichen Typs und gleicher Gr e 2 Rechteckige strukturierte Gitter bestehen aus Rechteckzellen Hexaederzellen
121. en da sie mehr als eine Nachkommastelle haben Sie haben den solid Status 2 und die jeweiligen Objektknoten haben die Indizes 160 684 788 und 2082 A 3 3 GRID Format Das GRID Format dient zum Speichern und Einlesen von Gittern in InGrid3D Ein Grobgitter in Form einer GRID Datei kann aus HaGrid3D exportiert werden Im Unterschied zum CM Format wird das Format bin rkodiert gespeichert Die folgenden Werte werden in dieser Reihenfolge in die Datei geschrieben Die Variable nPoints gibt die Anzahl der Gitterknoten an Es folgen alle Grobgitterknoten in Form von structs des Typs tPointSave Es beinhaltet die X Y und Z Koordinaten den solid Status des jeweiligen Knotens und das Attribut mapsindex Dieses dient der Kommunikation zwischen der Parametrisierung und dem Gitter Als n chstes wird die Breite H he und Tiefe des Gitters gespeichert Anschlie end wird der Wert maps IndexCounter gesichert Er ent spricht der Anzahl der Gitterknoten die auf dem Objektrand liegen Es folgen structs vom Typ tParaPoint die diese Knoten beschreiben Sie beinhalten den Index des Punktes auf dessen Position sie sich befinden das Grob und Feindreieck in dem sie liegen und die bary zentrischen Koordinaten sowie die Indizes der entsprechenden Eckpunkte des Feindreiecks in dem sie liegen A 3 4 GPUGRID Format Die Gitterdaten f r den GPU L ser werden im GPUGRID Format gespeichert Sie k nnen aus InGrid3D exportiert werden nachdem ein Gitter erst
122. en auf der GPU realisiert werden hei t Reduktion engl reduce 12 Die Idee ist in jedem Durchlauf engl rendering pass durch die Fragmentpipeline eine partielle Reduktion durchzuf hren bis sich die Anzahl der Pixel auf eins reduziert hat Das Verfahren dass in Abbildung 2 17 dargestellt wird sieht wie folgt aus Eine zweidimensionale Textur mit Werten dient als Eingabe In jedem Durchlauf wird ein Rechteck gezeichnet dessen Gr e einem Viertel der Eingangsgr e entspricht Jedes Frag ment des verkleinerten Rechtecks entspricht dem Maximum eines 2 x 2 Rechtecks in der Tex tur Wenn die Texturgr e n x n ist werden O log n Durchl ufe ben tigt 40 KAPITEL 2 GRUNDLAGEN 84 64 83 97 REESEN 93 99 Abbildung 2 17 Reduktionsverfahren auf der GPU 12 Produkt von Bandmatrix und Vektor Bandmatrizen werden als eine Menge von diagonalen Vektoren aufgefasst und dementspre chend werden diese Diagonalvektoren in einer zweidimensionalen Textur gespeichert Um Platz einzusparen kann man an den Diagonalvektor der in der i ten Spalte der ersten Zeile beginnt den Diagonalvektor der in der IV i ten Zeile der ersten Spalte beginnt anh ngen s Abb 2 18 Alternativ k nnen die Diagonalvektoren sofern sie nicht zu weit von der Haupt diagonalen entfernt liegen durch ein Auff llen mit Nulleintr gen auf die L nge N angepasst werden in der PG wird dieses Verfahren angewendet
123. en die folgende quivalente Integralschreibweise al VuVvdQ f v 0 f r alle zul ssigen v Q Q Mit Hilfe der Greenschen Formel kann man nun das Integral aufteilen in ein Gebietsintegral und ein Randintegral Da die Einspannbedingung Nullrandwerte vorschreibt f llt das Randin tegral weg Es bleibt d aAu f v dQ 0 f r alle zul ssigen v Q Da dies fiir alle Funktionen v gilt muss der Ausdruck in der Klammer nach dem DuBois Raymond Lemma bereits die Nullfunktion sein Man erh lt die Gleichung aAu f 9 mit Nullrandbedingungen 2 2 Dies ist das prototypische Poissonproblem allgemein werden Gleichungen diesen Typs auch als elliptische PDEs bezeichnet 2 1 3 Diskretisierung Nachdem ein mathematisches Modell in Form von Differentialgleichungen vorliegt muss aus ihm eine L sung gewonnen werden die eine Vorhersage f r den zugrundeliegenden Natur vorgang erlaubt Bei einfachen Gleichungen ist es vielleicht mit viel Erfahrung Geduld und Intuition m glich direkt durch scharfes Daraufschauen eine analytische L sung zu bestim men Bei komplexeren Systemen ist dies nicht mehr m glich daher ist man auf ein numerisches L sungsverfahren angewiesen Ein Beispiel ist das Differenzenverfahren bei dem die Differentialoperatoren durch Differen zenquotienten ersetzt werden Das Verfahren soll hier am Beispiel der Herleitung einer Diskre tisierung des dreidimensionalen Laplace Operators verdeutlicht werd
124. en mit den Indizes i o und p noch den vordefinierten Abstand delta zu seinen direkten sechs Nachbarn im Grobgitter hat und ansonsten false Der Test ist notwendig damit sich beim Verschieben von Knoten keine Hexaederzellen durchdringen k n nen 165 166 ANHANG API DOKUMENTATION bool check_snap_dependency int i int o int p float snapx float snapy float snapz Dieser Test wird aufgerufen bevor der Grobgitterknoten auf den Objektrand an der Stelle snapx snapy snapz gezogen wird Es wird getestet ob sich durch das Verziehen Hexaederzellen gegenseitig durchdringen w rden void save File const char file Das aktuelle Grobgitter wird in einer Datei mit dem bergebenen Namen abge speichert Die Knoten werden der Reihe nach zeilenweise zusammen mit ihren Positionen und Attributen im ASCII Format abgespeichert s Anhang A 3 void load File const char file ein zuvor mit save File gespeichertes Grobgitter wird mit dieser Methode wie der in den Speicher geladen void export File const charx file mit dieser Methode wird ein Objekt vom Typ Grobgitter in eine Datenstruktur berf hrt und unter file gespeichert das von InGrid3D wieder eingelesen wer den kann void set Actual Vertex To Defaultvalues der aktuelle Grobgitterknoten bekommt durch den Aufruf dieser Methode wieder seine urspr nglichen Koordinaten und seinen solid Status Klasse OpenGLView Diese Klasse erstellt und verwaltet alle OpenGL Objekte di
125. epr ft ob die Strecke zwischen dem Referenzpunkt und dem auf Einschluss zu pr fenden Punkt das jeweilige Dreieck schneidet Hierbei wird die Anzahl der Schnitte pro Grobgitter punkt gez hlt ber sie kann bestimmt werden ob der Punkt eingeschlossen ist oder nicht Bei ungerader Anzahl von Schnitten liegt der Punkt innerhalb des Feinnetzes bei gerader au er halb Schnitttest Seien A a Ya Za b Yb 25 e Ye zc und D Yd Za Punkte im IR Das vorzeichenbehaftete Volumen des Tetraeders DABC im Folgenden mit DABC bezeichnet ist wie folgt definiert 1 Xa Ud 4a Zd DABC g Td Yo Ya 2 2a Ud 2 7d Falls das Volumen D ABC ein positives Vorzeichen hat bedeutet dies dass die Punkte A und C vom Punkt D aus betrachtet entgegen des Uhrzeigersinns orientiert sind F r zwei Punkte Q und Q kann zun chst leicht berpr ft werden ob sie auf verschiedenen Seiten des zu pr fenden Dreiecks ABC liegen Dies ist n mlich genau dann der Fall wenn genau ein Vorzeichen der Volumina QABC und JO ABC positiv und das andere negativ 5 2 GROBGITTERGENERATOR 61 ist Ebenso kann mit Hilfe des Volumens berpr ft werden ob ein Schnittpunkt zwischen der Strecke QQ und dem Dreieck ABC existiert Seien ABC ein Dreieck und QQ eine Strecke R wobei und Q sich auf verschiedenen Seiten des Dreiecks befinden Au erdem seien die Punkte
126. er Erfahrungen im Umgang mit den verschiedenen Gl ttern haben ergeben dass es sinnvoll ist diese erst zu verwenden wenn den Quali tskriterien nicht mehr entsprochen wird Das bedeutet bei der Validierung anhand der fein aufgel sten Kugel und einem guten Grobgitter dass die Gl tter erst in Unterteilung 5 verwendet werden Des Weiteren kann gesagt werden dass sie bei der Verbesserung der maximalen und minima len Winkel sowie bei dem L ngenverh ltnis eher kontraproduktiv sind Dabei muss erw hnt werden dass die Grobgitterunterteilung bei einem kartesischen regul ren Gitter ein prinzipi elles Problem darstellt Andere Arbeiten haben gezeigt dass die Verwendung weniger stark eingeschr nkter Hexaedergitter bessere Ergebniss liefern 14 Im komplexen Testfall soll dar gelegt werden dass die Anwendung von Gl ttern zur Verhinderung von Zelldurchdringungen von Vorteil ist 6 11 FAZIT 115 Resultate des komplexen Testfalles Als Modell kam hier wieder das praxisnahe Beispiel des Golf III zum Einsatz Bis zur Un terteilungsstufe zwei war der Einsatz von Gl ttern nicht n tig da alle Qualit tskriterien erf llt wurden Der erste auftretende Jacobi Fehler in Stufe drei konnte durch Anwendung des Jacobi Oberfl chengl tters behoben werden Die brigen Qualit tskriterien wurden jedoch nicht ver bessert In der folgenden Unterteilungsstufe traten 14 Jacobi Fehler auf von denen zw lf eben falls durch die Anwendung des Jacobi Oberfl
127. er Behandlung der Fl chen 5 6 GITTERANPASSUNG AN DAS OBJEKT 69 6 4 24 wurden in jeder Randfl che des alten Hexaeders vier neue Fl chen erzeugt und hier nun zus tzlich zw lf innere Fl chen im alten Hexaeder also insgesamt 36 neue Fl chen Aus diesen werden die acht neuen Hexaeder definiert und der alte Hexaeder wird verworfen Damit ist die Unterteilung abgeschlossen 5 6 Gitteranpassung an das Objekt Bei der Unterteilung des Gitters m ssen neue Knoten zwischen zwei Objektknoten im Folgen den Elternknoten genannt auf die Oberfl che bewegt werden Diese Aufgabe wird mit Hilfe der Parametrisierung gel st Die gesuchte Position dieses neuen Knotens ist dabei die Mitte eines optimalen Verbindungsweges zwischen den zwei Objektknoten der gr beren Untertei lungsstufe auf dem Objekt Typischerweise kann mit Hilfe einer Parametrisierung ein guter Verbindungsweg gefunden werden Dabei werden die Elternknoten in den Parameterraum pro jiziert und die Verbindungslinie zwischen den beiden eingebetteten Punkten im Parameterraum gesucht Dabei kann es zu den folgenden vier F llen kommen Fall 1 Einfache Einbettung Die Elternknoten werden im selbem Grobdreieck parametrisiert Da ein Grobdreieck immer konvex ist liegt der Mittelpunkt der Verbindungsstrecke der beiden eingebetteten Elternkno ten auch in diesem Dreieck s Abb 5 14 Dieser Mittelpunkt wird nun auf die Oberfl che projiziert und als geeignete Mitte angenommen Fall 2
128. er einen Seite werden dem Pro grammierer alle grafikkartenspezifischen Bereiche die Handhabung von Texturen Speicher usw abgenommen und die Plattformunabh ngigkeit gewahrt auf der anderen Seite muss man mit einem Leistungsverlust rechnen 2 6 3 GPU Konzepte Im folgenden Abschnitt werden GPU Analogien f r grundlegende Datenstrukturen und Pro grammierkonzepte vorgestellt In Programmen f r die CPU ist ein Feld von Daten engl ar ray eine zentrale Datenstruktur Eine GPU Entsprechung hierf r ist das Speichern von Daten in Texturen Damit die Feldindizes den Indizes der Textur entsprechen ist in den Grafikschnitt stelle eine orthographische Projektion zu setzen und die Dimension der Bildebene ist der der Textur anzupassen Die eigentliche Berechnung wird dadurch durchgef hrt dass die Vertex oder Fragmentprogramme aktiviert werden die Texturen oder Texturkoordinaten als Parameter bergeben werden und letztendlich ein Rechteck der zuvor angegebenen Bildschirmdimension gezeichnet wird Dadurch wird f r jedes Texel der Ergebnisstextur f r jeden Eintrag im Feld das Fragmentprogramm ausgef hrt Reduktion Allgemein berechnen Shaderprogramme eine Menge von Ausgabewerten aus einer Menge von Eingabewerten Bei allgemeinen Berechnungen wird jedoch h ufig ein einzelner Wert aus ei ner Menge von Werten berechnet wie z B das Maximum einer Menge von Werten oder das Skalarprodukt von Vektoren Das Verfahren mit dem oben genannte Operation
129. eren dass die Netzqualit t verbessert wird laut Freitag 31 ist es sogar nicht w nschenswert die Prozedur auf Elementen die nicht ung ltig sind durchzuf hren Der Test ob ein Element un g ltig ist muss an Hexaedernetze angepasst werden denn f r Rechtecksnetze oder Hexaeder netze ist es m glich dass Elemente f r die es negative Jacobi Determinanten gibt nicht inver tiert sind Abbildung 2 13 zeigt beispielhaft zum Einen ein nicht invertiertes Viereckselement mit einem negativen Jacobi Wert am Knoten v3 und ein nicht invertiertes Hexaederelement mit einem negativen Jacobi Wert am Knoten vg zum Anderen 32 KAPITEL 2 GRUNDLAGEN Abbildung 2 13 Nicht invertierte Elemente mit negativen Jacobi Werten bei solchen Elemen ten gen gt die Anwendung herk mmlicher Gl ttungsmethoden 31 Ein Vierecks oder Hexaederelement ist g ltig wenn die Schnittmengen der Kanten oder Fl chen Netzelemente von geringerer Dimension sind also sollte z B der Schnitt von zwei He xaederfl chen entweder leer eine Kante oder ein Knoten des Netzes sein Bedingungen f r die G ltigkeit die leichter zu berechnen ist liefern die folgenden Beobachtungen Ein Viereckselement ist g ltig genau dann wenn h chstens eine der vier Jacobi Determinanten der Knoten negativ ist Dies l sst sich folgenderweise auf Hexaederelemente bertragen Ein Vierecks oder Hexaederelement ist g ltig genau dann wenn es keine zwei benachbarten Knoten mit negati
130. eren Kr mmung sich ge ndert hat aus ihr entfernt So bleibt die Reihenfolge erhalten und eine unabh ngige Menge entsteht Der Vergr berungsprozess beinhaltet gleichzeitig die Parametrisierung und somit zwei Schritte Zun chst wird die Entfernung des Knotens und Retriangulierung der Eins Ring Nachbarschaft im Zweidimensionalen vorgenommen anschlie end wird der Mittelpunkt und alle vorher para metrisierten Knoten in die neue Triangulierung eingebettet Dabei ist zu beachten dass es sich bei dem Grad der Vergr berung um eine Heuristik handelt der vom Anwender variiert werden kann 5 3 1 Retriangulierung F r den Vergr berungsprozess wird sequentiell die oben gebildete Liste durchlaufen und jeder Knoten abgearbeitet Dabei wird zuerst die Eins Ring Nachbarschaft um den Knoten herum durch konforme Einbettung in 2D eingebettet Dabei werden nicht nur die anliegenden Drei ecke eingebettet sondern auch alle schon vorher parametrisierten Knoten des Netzes Die kon forme Einbettung minimiert dabei die auftretenden Verzerrungen Nachdem der Mittelpunkt entfernt wurde wird eine Triangulierung der Eins Ring Nachbarschaft des zuvor entfernten Punktes ben tigt Hier wird zuerst die einfache Methode des Ohrenabschneidens engl ear cutting benutzt Diese liefert immer eine g ltige Triangulierung Als Implementierung wurde auf eine freie Bibliothek von O Rourke zur ckgegriffen s Kap 2 2 4 Dieser Zugang erzeugt jedoch schlechte Triangulierunge
131. ers ben tigt wer den cGrid getGrid liefert das cGrid Objekt auf dem diese cMultiGrid Instanz arbeitet void setSmoothTypeNoSmooth void setSmoothTypeSmooth void setSmoothTypeSmoothSmart void setSmoothTypeUntangler void setSmoothTypeUmbrella void setSmoot TypeUmbrella2 void setSmoothTypeOberflaeche TypeOberflaecheWinkel BR S BR En b void setSmoot 156 ANHANG C API DOKUMENTATION void setSmoothTypeOberflaecheKruemmung diese Routinen bestimmen welche Art von Gl ttung von doSmooth durchge f hrt wird void doSmooth f hrt die Gl ttung aus die als aktueller Gl ttungsoperator eingestellt ist void untangleHexas f hrt eine Gl ttung nach dem Verfahren zur Entfernung von Selbstdurchdringung en durch s Kap 2 4 void smoothOberflaecheWinkel f hrt eine Gl ttung der Oberfl chenrandknoten durch mit dem Ziel die Winkel zu verbessern s Kap 5 7 4 void smoothOberflaecheJacobi f hrt eine Gl ttung der Oberfl chenrandknoten mit Jacobi Fehlern durch mit dem Ziel die Jacobi Fehler zu beseitigen s Kap 5 7 void setSmoothlter int newIter stellt ein wie viele Iterationen beim Gl tten durchgef hrt werden sollen void setKruemmungsToleranz int toleranz reguliert ab wann smoothOberflaecheWinkel Knoten aus einer Position mit hoher Kr mmung heraus verschiebt um den Winkel zu verbessern int subdivide
132. ert werden Hierzu wird ber das Men Gitter die Speichern unter Funktion aufgerufen und dann die Ausgabedatei ausgew hlt auch ber die Tastenkombination Strg S w hlbar A 2 4 Tutorial L ser und Visualisierung Hat man nach einigen Unterteilungsschritten die gew nschte Aufl sung des Gitters erreicht so kann man die Daten f r den GPU L ser in eine Datei exportieren Hierzu wird ber das Men Gitter die Export zum GPU L ser Funktion aufgerufen und ein entsprechender Dateiname angegeben auch ber die Tastenkombination Strg E w hlbar Nach erfolgter Berechnung k nnen die von dem GPU L ser gelieferten Daten wieder in In Grid3D ber das Men Gitter und dann die Importiere L serdaten Funktion zur Visuali sierung importiert werden auch ber die Tastenkombination Strg I w hlbar Der Import der L serdaten schaltet alle Zeichenoptionen in der GPGPU Leiste frei s Abb A 21 Unterteilung Gl ttung Zeichnen GPGPU Debug L serdaten Zeichenoptionen y z Schicht x z Schicht 0 x y Schicht 0 Geschwindigkeits Yektorfeld normiertes Vektorfeld Druck verbesserte Interpolation Gitterzellen Abbildung A 21 Das Bedienfeld f r die Zeichenoptionen der in der Grafikkarte berechneten Daten 140 ANHANG A BENUTZERHANDBUCH Durch das Bet tigen der Schicht Schaltfl chen oder das Verschieben der jeweils darunter liegenden Sch
133. es Problems ben tigten Gitterdaten enth lt C 1 BERSICHT BER DIE PAKETE UND KLASSEN VON INGRID3D 163 void createBandsGPU int width int height int depth dist_inf inf float amp dataDD float amp dataDU float x amp dataDL float amp dataUD float amp dataUU float amp dataUL float x amp dataLD float amp dataLU float amp dataLL float vec weist den B ndern der Finiten Differenzen Matrix ihre Werte zu f llt die B nder falls n tig mit Nulleintr gen auf und passt die Eintr ge im Falle von Randpunkten entsprechend an static void grid2GMV const char filename double data gmv_arr arr load data dat int schicht exportiert eine Punktschicht des Rechengitters das Skalar und Vektorfeld in das Format des Programms GMV int solverGPU startet den GPU L ser auf dem geladenen Rechengitter double calculateTestVector int width int height int depth load data data Diese Funktion berechnet einen Vektor der auf der rechten Seite der Poissonglei chung eingesetzt wird Die Funktion ruft calculateDerivative auf double calculateDerivative double x double y double z int N int var load data data berechnet die partielle Ableitung einer Referenzfunktion nach einer ausgew hlten Variablen 164 ANHANG API DOKUMENTATION C 2 bersicht ber die Klassen von HaGrid3D Abbildung C 4 UML Klassendiagramm f r das Modul HaGrid3D Klasse Grobgitter erstellt u
134. fferen zierbare Funktion Da die partiellen Ableitungen von x nicht stetig sind f hrt dies zu einem nicht glatten Optimierungsproblem das beispielsweise mit der Methode des steilsten Abstiegs engl steepest descent method gel st werden kann 13 2 4 Entfernen von Selbstdurchdringungen 2 4 1 Allgemeine Formulierung des Optimierungsproblems Das Entfernen von Selbstdurchdringungen durch lineare Optimierung engl optimization ba sed mesh untangling ist ein Verfahren das es erm glicht invertierte Elemente in verschie denen Netzen z B Dreiecks Vierecks oder Hexaedernetze wieder in g ltige Elemente zu berf hren Betrachtet man also einen Knoten eines invertierten ung ltigen Elements und seine Nachbarschaft so wird das Ziel angestrebt den Knoten an eine Stelle zu verschieben so dass nur noch g ltige Elemente in der Nachbarschaft dem lokalen Teilnetz existieren Die Menge der Knotenpositionen die g ltige Elemente ergibt wird G ltigkeitsbereich engl fea sible region genannt Zur Entfernung von Selbstdurchdringungen durch lineare Optimierung wird die Strategie ver folgt ein Qualit tsma f r Netze zu w hlen und dieses in einer lokalen Umgebung zu optimie ren F r Dreiecksnetze wird als Qualit tsma der Fl cheninhalt eines Dreiecks gew hlt Dieser Fl cheninhalt soll ber alle Dreiecke durch Optimierung maximiert und so die Netzqualit t ver bessert werden Es wird eine lineare Gleichung zur Berechnung de
135. fiziert und rot ausgef llt Die Kanten die die Fl che in derselben Ebene verlassen werden gelb gezeichnet void translate Vertex float tx float ty float tz int i int o int p Diese Methode wird aufgerufen wenn ein Knoten des Grobgitters verschoben wird Mit den Parametern i o und p wird der zu verschiebende Knoten identi fiziert und die drei loat Werte tx ty und tz geben die relativen Koordinaten nderungen in den drei Dimensionen an Sollte ein Verschieben eine Hexaederzel lendurchdringung hervorrufen so wird die Verschiebung r ckg ngig gemacht void translate_All_Vertices float tx float ty float tz durch den Aufruf wird das ganze Grobgitter um den loat Wert tx in X Richtung um ty in Y Richtung und um tz in Z Richtung relativ verschoben bool snap_Vertex floatx toSnapVertex int indexOfObjectVertex Der aktuell selektierte Grobgitterknoten erh lt die Koordinaten des aktuell aus gew hlten Objektknotens Die Koordinaten werden in Form eines Zeigers auf ein dreidimensionales float Array toSnapVertex an diese Methode berge ben und die Koordinaten des aktuellen Grobgitterknotens mit diesen berschrie ben Der Grobgitterknoten erh lt den Index des Objektknotens als zus tzliches Attribut Die Methode liefert als R ckgabewert true falls das Verschieben er folgreich war ansonsten false bool check_dependency int i int o int p Diese Testmethode liefert den R ckgabewert true falls der Grobgitterknot
136. gen wurden aus dem Englischen bersetzt 22 KAPITEL 2 GRUNDLAGEN Diese Fallunterscheidung ist vollst ndig Angenommen es g be einen Knoten d der bei obiger Fallunterscheidung nicht ber cksichtigt w rde Dann w rde gelten e dg K t da sonst Fall 1 greift e dg K K da sonst Fall 2 greift und e dg K K da sonst Fall 3 greift Es folgt d g Kt U K K U K K K dist also kein Knoten des Netzes der feinsten Aufl sungsstufe und muss somit nicht betrachtet werden Verfahren zur Berechnung der Koordinaten eines beliebigen Punktes auf der Oberfl che Im weiteren Verlauf werden Dreiecke des Basisnetzes als Grobdreiecke und Dreiecke des Feinnetzes als Feindreiecke bezeichnet Gegeben sei ein Punkt p K auf dem Netz der gr bsten Aufl sungsstufe Zun chst muss mit Hilfe eines Such Algorithmus zur Punkt Lokalisierung das Dreieck auf dem Feinnetz gefunden werden das p enth lt Dies ist quivalent dazu das Dreieck des Feinnetzes zu fin den welches k nach Projektion des Feinnetzes auf das Grobnetz enth lt Der Suchalgorithmus geht wie folgt vor Alle auf ein Grobdreieck projizierten Dreiecke werden durchlaufen und es wird getestet ob es unter ihnen eines gibt so dass der projizierte Punkt von allen Kanten dieses Dreiecks links liegt Zur Parametrisierung des Punktes unterscheiden wir vier F lle 1 T liegt in einem Grobdreieck 2 Zwei Knoten aus liegen in einem Dreieck der dritte in einem bena
137. h Tabelle 6 4 entnehmen W hrend in den ersten beiden Testf llen ein als gut erachtetes Grobgitter verwendet wird so kam in Testfall 3 ein schlechtes zur Anwendung Bei diesem Vorgehen kommt es schon in Unterteilungsstufe eins zu einem Jacobi Fehler Bis zu Unterteilung f nf erh ht sich die Zahl der Fehler drastisch auf 1692 Auch die Werte der maximalen und minimalen Winkel erf llen schon ab Unterteilungsstufe eins nicht die erforderlichen Kriterien s Tabelle 6 5 Im dem Fall dass diese einfache Geometrie eine Einbuchtung aufweist Testfall 4 wird mit einem 1000 Gitterzellen enthaltenden relativ fein aufgel stem Grobgitter begonnen Deshalb kann drei mal unterteilt werden wobei alle Qualit tskriterien erf llt werden Auch die maxi malen und minimalen Winkel und das L ngenverh ltnis befinden sich in dieser Stufe im guten Bereich wie in Tabelle 6 6 ersichtlich Wird bei dieser Geometrie ein schlechtes Grobgitter Testfall 5 verwendet so kommt es schon nach der ersten Unterteilung zu drei Jacobi Fehlern Die Anzahl erh ht sich bis zur vierten Unterteilungsstufe auf 149 Zus tzlich werden auch ab Unterteilungsstufe zwei die minimalen und maximalen Winkel sowie das L ngenverh ltnis schnell sehr schlecht F r die genauen Werte wird auf Tabelle 6 7 verwiesen Testfall 6 wird zun chst mit einem guten Grobgitter validiert Hierbei stellt sich heraus dass lediglich zwei Unterteilungsstufen die Qualit tskriterien erf llen Danach ko
138. haft des gemeinsamen Eckpunktes auf eine Ebene abgebildet Diese Abbildung erfolgt mit Erhaltung der Kantenverh ltnisse der Kanten die vom gemeinsamen Eckpunkt aus gehen Die Winkel der am gemeinsamen Eckpunkt anliegenden Kanten werden auf 360 verteilt abgebildet Anschlie end wird der Mittelpunkt der Verbindungslinie der beiden Knoten zur ckgegeben e Haben die zwei Dreiecke keinen gemeinsamen Eckpunkt so wird die Snake zwischen den beiden Knoten aufrufen und der Mittelpunkt der Snake wird zur ckgegeben Der von diesem Verfahren erzeugte Mittelpunkt wird auf das Dreiecksnetz projiziert und als Knoten der neuen Hexaeder vermerkt Bei komplexen Objekten kann diese Methode manchmal zu unerw nscht verdrehten Hexa ederzellen f hren weshalb verschiedene Gl tter implementiert wurden deren Aufgabe darin besteht die Hexaederzellen m glichst gleichm ig auszurichten Am Ende der Systembe schreibung wird ein L ser vorgestellt der eine Simulation auf GPGPU Basis auf dem vorher an die Objektoberfl che angepassten Gitter durchf hrt 5 1 Geometrieobjekte Die Software InGrid3D wurde erstellt um f r komplexe geometrische Objekte Gitter zur Str mungssimulation zu erzeugen Zum Import der Objekte ins Programm wird das STL Format benutzt Beim STL Format Standard Transformation Language handelt es sich um eine Quasi Standardschnittstelle vieler CAD Systeme s Anhang A 3 Sie beinhaltet die Be schreibung der Oberfl che von 3D K
139. he Norm mit Tall bezeichnet d a b X och i 1 a a Ilall Funktionen treten entweder skalarwertig oder vektorwertig auf u x t Ge t Partielle Ableitungen d h Ableitungen nach einer der vorkommenden Variablen werden wie folgt geschrieben 6 KAPITEL 2 GRUNDLAGEN ER Ou Ly du bezeichnet die p te Ableitung nach der Variable x u die Approximation der ersten Ableitung nach der Variable x und u die Approximation der zweiten Ableitung Mit dem Nabla Operator V werden der Gradient Vektor aller partiellen Ableitungen einer skalaren sowie die Divergenz einer Vektorfunktion geschrieben als grad Vu Oqu qu 7 div u V u Oyu Die Kombination von Divergenz und Gradientenoperator ergibt den Laplace Operator Au Vu u Hu 2 1 2 Modellierung Ziel der Modellierung ist es f r Naturvorg nge eine oft stark vereinfachte mathematische Beschreibung zu finden d h Vorg nge wie Diffusion Stofftransport oder Temperaturvertei lung mit Hilfe mathematischer Gleichungen zu beschreiben Dies ist ein h chst kreativer Akt der viel Erfahrung erfordert und f r den es kein Standardkochrezept gibt An dieser Stelle wird exemplarisch die Herleitung einer partiellen Differentialgleichung PDE f r die Auslenkung einer Membran dargestellt Es wird in Form einer partiellen Differentialgleichung PDE be schrieben und basiert auf dem Lehrbuch von
140. ichtig dass die Richtung f r alle Snaxel konsistent gehalten wird es m ssen also alle Snaxel zur selben Seite der Snake zeigen Des Weiteren d rfen keine zwei Segmente der Snake im gleichen Dreieck der Oberfl chentriangu lierung liegen diese Segmente werden als ung ltig bezeichnet Ung ltige Segmente k nnen bei der berquerung von Knoten entstehen sie lassen sich aber leicht erkennen und auch entfer nen indem ihre benachbarten Snaxel miteinander verbunden werden s Abb 2 15 Mit dieser st ckweise linearen Darstellung l sst sich also jedes Detail des Objektes erfassen unabh ngig von der Aufl sung bzw der Anzahl der verwendeten Dreiecke Abbildung 2 15 Links Eine g ltige Snake Mitte Die Konsistenzbedingung wurde verletzt Rechts Durch Entfernen des ung ltigen Snaxels wird die Konsistenz wieder hergestellt Bewegung Die Bewegung oder auch Evolution einer Snake wird ber interne und externe Kr fte bestimmt welche blicherweise aus der Biegeenergie der Snake berechnet werden In unserem Fall wird zun chst jedem Snaxel s ein Geschwindigkeitswert v zugewiesen der die Energie repr sen tiert Dann wird die Winkelhalbierende zwischen zwei Snake Segmenten ermittelt Mit der Kante auf der der Snaxel s liegt ergibt sich nun ein Winkel ag Die Geschwindigkeit 05 ent lang der Kante ergibt sich wie folgt Us Us 2 18 s COS Qs 36 KAPITEL 2 GRUNDLAGEN Falls sich mehrere Snaxel auf einem Punkt befinden
141. ieberegler ist es m glich durch einzelne Gitterschichten zu wechseln Zur Vi sualisierung der L ser Daten stehen verschiedene Zeichenoptionen bereit Es ist m glich ber die Schaltfl chen die Visualisierung des Geschwindigkeitsvektorfeldes einzuschalten Wird es eingeschaltet gibt es noch zus tzlich die Option die Vektoren zu normieren was gelegentlich f r die bersichtlichkeit von Vorteil ist s Abb A 22 Auch das von der GPU berechnete Druckfeld l sst sich einschalten und in verschiedenen Schichten anzeigen F r gr bere Gitter empfiehlt es sich die verbesserte Interpolation hinzu zu schalten Hierdurch werden Artefakte in der Darstellung des Druckfelds ausgeglichen s Abb A 23 Als letzte Option ist es m glich eine Schicht aus dem Gitter darstellen zu lassen Alle drei Datenbereiche k nnen so einzeln oder in beliebiger Kombination miteinander darge stellt werden s Abb A 24 Mesh Gitter Hilfe Unterteilung Gl ttung Zeichnen GPGPU Debug L serdaten Zeichenoptionen yz Schicht 4 13 sa Schicht 13 xy Schicht fr Geschwindigkeits Vektorfeld normiertes Vektorfeld Druck verbesserte Interpolation Gitterzellen Abbildung A 22 Das normierte Geschwindigkeitsvektorfeld A 2 TUTORIAL 141 Unterteilung Gl ttung Zeichnen GPGPU Debug L serdaten Zeichenoptionen y 2Schicht Geschwindigkeits Vektorfeld nomierte
142. iel Arbeitsspeicher verbraucht Es zeigte sich in Versuchen dass mit einer heute blichen Arbeitsspeicherausstattung von einem Giga byte etwa vier bis sechs Unterteilungsschritte m glich sind je nach Anzahl der Elemente des Grobgitters B 2 ENDPRODUKT 147 Software Die im Rahmen der PG erstellten Programme sind auf Windows 2000 XP lauff hig Eine Por tierung auf das Linux Betriebssystem wurde aus Zeitgr nden nicht vorgenommen ist aber aufgrund der Verwendung der plattformunabh ngigen Bibliotheken Ot s Kap 3 2 und Open Mesh s Kap 3 6 m glich Die Verwendung der neuesten Grafikkartentreiber wird empfohlen F r den L ser ist des Wei teren das Cg Toolkit in der Version 1 3 oder 1 5 n tig Version 1 4 ist fehlerbehaftet Interoperabilit t Da die Generierung geeigneter Grobgitter durch externe Software nicht gelang s Kap 4 3 implementierte die PG ein eigenes Werkzeug zur Unterst tzung bei der manuellen Grobgit tererstellung Nach durchgef hrter Unterteilung und Deformation des Gitters kann selbiges an den ebenfalls entwickelten L ser bergeben werden Eine analoge Exportfunktion zu anderen L sern ist einfach hinzuzuf gen Die zu umstr menden Objekte m ssen als Oberfl chentrian gulierung vorliegen konkret unterst tzt wird das STL Format B 2 3 Produktfunktionen Die im Pflichtenheft geforderten Produktfunktionen wurden vollst ndig umgesetzt Da nicht alle verwendeten Techniken auf die GPU bertragbar wa
143. iert Es kann gezeigt werden dass diese Funktion konvexe Level Sets hat im Falle dass der freie Knoten innerhalb oder au erhalb des G ltig keitsbereichs liegt 13 Allgemeiner Ansatz Es wird ein allgemeiner Aufruf f r eine Prozedur die Durchdringungen entfernt vorgestellt ein solcher Aufruf h tte die Form Pnew Untangle p Adj p Hierbei bezeichnet Adj p die Knoten u so dass eine Kante p u existiert und p ist der Kno ten dessen Position verbessert werden soll Es wird der minimale Fl cheninhalt eines Dreiecks im lokalen Teilnetz maximiert und die Position des freien Knotens dementsprechend angepasst Die Funktion f die den Fl cheninhalt des Dreiecks angibt l sst sich allgemein schreiben als f p min A p f r1 i n Hierbei ist n die Anzahl der Dreiecke im lokalen Teilnetz und A der Fl cheninhalt des 7 ten Dreiecks im lokalen Teilnetz Fl cheninhalt und Jacobi Determinante Betrachtet man im Zweidimensionalen ein Dreieck mit den Punkten p pz Py u uz Uy und v vz vy so besteht die Jacobi Matrix aus den Spaltenvektoren e u p und v p J ei e3 Im Dreidimensionalen wird die Matrix analog gebildet Die Determinante dieser Matrix gibt nun den Fl cheninhalt eines Elements an es gilt also 1 A 5 det J wobei a4 Uy Vy dy Ur Ug C UgUy Uruy 2 13 Im Dreidimensionalen gilt analog fiir ein Tetraeder mit freiem Kno
144. ierung des pro totypischen L sers von einem Betreuer zur Verf gung gestellt s Kap 5 8 46 KAPITEL 3 WERKZEUGE Kapitel 4 Vorarbeiten Ergebnisse der vorbereitenden Experimente Im Verlauf des ersten Semesters wurden verschiedene Ans tze und Programme zum Errei chen der Ziele der PG untersucht Unter anderem wurde die Gittergenerierungssoftware Cubit untersucht und es wurden Leistungstests auf Grafikkarten durchgef hrt Au erdem sind Ver ffentlichungen zur Parametrisierug von Objektoberfl chen evaluiert worden Die Ergebnisse werden in diesem Kapitel vorgestellt 4 1 Diplomarbeit von Wobker Die Idee der Diplomarbeit von Wobker 65 zur Parametrisierung von Oberfl chennetzen ist folgende Das zu parametrisierende Netz wird durch das L schen von Halbkanten und an schlie endem Verschmelzen der Knoten engl halfedge collapse vergr bert Das entstande ne Grobnetz stellt den Parameterraum f r die Parametrisierung dar In einem weiteren Schritt muss nun das Originalnetz segmentiert werden Wichtig ist hierbei dass eine eins zu eins Be ziehung zwischen der Segmentierung und den Dreiecken des dezimierten Netzes ben tigt wird Um dies zu bewerkstelligen wurden von Wobker die k rzesten geod tischen Distanzen auf der Oberfl che berechnet Nach Besprechung dieses Parametrisierungsverfahrens innerhalb der PG fand ein Treffen mit Hilmar Wobker statt in dem er seine Implementierung vorstellte und auf Probleme und Vorteile die
145. ig s Abb 2 8 Winkelabweichung Die Winkelabweichung misst wie stark die Innenwinkel zwischen jeweils zwei inzidenten Kanten in einem Hexaeder oder einem Viereckselement von einem rechten Winkel abweichen s Abb 2 9 Ihre Berechnung mittels Skalarprodukt ist trivial Als Winkelabweichung wird das Maximum aller so berechneten Werte bezeichnet In einigen Simulationspaketen ist die ser Wert wichtig wenn beispielsweise f r die Berechnung von Ableitungswerten m glichst rechteckige Zellen vorausgesetzt werden LG Abbildung 2 9 Beispiele f r Winkelabweichung von 0 5 und 30 0 Innenwinkel Die Berechnung minimaler und maximaler Innenwinkel wird f r alle Paare inzidenter Kanten eines Hexaeders oder Viereckselements durchgef hrt Mit diesem Ma k nnen nicht tolerier bar starke Elementverformungen schnell gefunden werden Beispielsweise hat ein zu einem Dreieck degradiertes Viereckselement einen maximalen Innenwinkel von 180 s Abb 2 10 gn 140 150 Abbildung 2 10 Beispiele f r den maximalen Innenwinkel von 90 140 und 180 26 KAPITEL 2 GRUNDLAGEN Jacobi Verh ltnis Dieses Ma ist f r viele numerische Simulationsprogramme und auch in der Visualisierung von fundamentaler Bedeutung und zwar immer dann wenn die verwendeten Algorithmen ei ne Koordinatentransformation zwischen einem Tensorproduktgitter computational space und einem verzerrten randangepasstem Gitter physical space be
146. ildung 6 24 Gitter f r Testfall 8 nach vier Unterteilungen 96 KAPITEL 6 PROJEKTVALIDIERUNG Unterteilungsstufe Jacobi Fehler Innenwinkel L ngenverh ltnis Gitterzellen 0 0 45 lt lt 157 2 88 160 1 0 38 lt lt 157 2 83 1280 2 0 31 lt lt 159 3 82 10240 3 1 25 lt lt 167 4 99 81920 4 15 11 lt lt 179 7 34 655360 Tabelle 6 10 Werte der Qualit tskriterien f r Testfall 8 6 4 Validierung der Gl tter In diesem Abschnitt werden die F higkeiten der Gl tter Gitter zu verbessern untersucht Es wird zwischen einfachen Gl ttern und Gl ttern die auf der Objektoberfl che arbeiten unter schieden Sie werden an Hand von fallspezifischen Beispielen demonstriert F r detaillierte Funktionsbeschreibungen der Gl tter wird auf Kapitel 5 7 verwiesen Einfache Gl ttungsstrategien Mit Hilfe dieser Testserie wird exemplarisch f r Testfall 1 hochaufgel stes Kugelobjekt mit optimalem Grobgitter die Strategie beurteilt erst bei Erreichen der feinsten Unterteilungsstu fe eine Gl ttung durchzuf hren Nach f nf Unterteilungsschritten werden die in Tabelle 6 11 angegebenen Gl tter jeweils so lange iteriert bis sie keine nderung des Gitters mehr erzielen konnten Gl tter Jacobi Fehler Innenwinkel L ngenverh ltnis ohne 0 29 lt a lt 154 5 62 Laplace 0 29 lt lt 154 5 62 Umbrella 0 25 lt lt 157 8 22 Umbrella 2 0 27 lt lt 1
147. im STL Format geladen werden In diesem Tutorial wird die Oberfl chentriangulierung aus dem Kapitel A 2 1 geladen Hierzu wird ber das Men Mesh die Mesh Laden Funktion aufgerufen und dann die entsprechende Datei ausgew hlt auch ber die Tastenkombination Strg M w hlbar A 2 TUTORIAL Wi Freeware pg471 wegen Zeichenopionen Debug GPGPUL ser Independent Set Independent Set 1x entfemen Independent Set 20s entfemen Dreiecke auf 2 reduzieren Bis auf Restdreiecke entfemen Untertelen Jeng at Punkte und 384 Fl chen 135 Abbildung A 14 Die Benutzeroberfl che von InGrid3D unmittelbar nach dem Programmstart Ist das neue Objekt eingelesen worden ist es notwendig das dazu konstruierte Grobgitter zu laden das mit Hilfe des Programms HaGrid3D erstellt wurde s Anhang A 2 2 Hierzu wird ber das Men Gitter die Laden Funktion aufgerufen und dann die entsprechende Datei ausgew hlt auch ber die Tastenkombination Strg L w hlbar Das neue Objekt und das dazu konstruierte Grobgitter sind nun geladen s Abb A 15 mt Freeware Gei Mesh Gtter Dir n Unietelurg Gl tung Zeicheroptonen Debug GPEPULser Independent Set Independent Set 1x enlerren Indegendent Set 20x entfemen Dreiecke aul 2 reduzeren
148. imer of warranty keep intact all the notices that refer to this License and to the absence of any warranty and give any other recipients of the Program a copy of this License along with the Program You may charge a fee for the physical act of transferring a copy and you may at your option offer warranty protection in exchange for a fee 2 You may modify your copy or copies of the Program or any portion of it thus forming a work based on the Program and copy and distribute such modifications or work under the terms of Section 1 above provided that you also meet all of these conditions a You must cause the modified files to carry prominent notices stating that you chan ged the files and the date of any change b You must cause any work that you distribute or publish that in whole or in part contains or is derived from the Program or any part thereof to be licensed as a whole at no charge to all third parties under the terms of this License c If the modified program normally reads commands interactively when run you must cause it when started running for such interactive use in the most ordinary way to print or display an announcement including an appropriate copyright notice 173 and a notice that there is no warranty or else saying that you provide a warranty and that users may redistribute the program under these conditions and telling the user how to view a copy of this License Exception if the Program itself is i
149. iner Priorit tswarteschlange Q ersetzt wird wobei die Priorit t von geometrischer Information des Knotens abh ngt Entscheidend f r die Priorit t einer Eins Ring Nachbarschaft in der Geometrie sind ihre Oberfl che und Kr mmung Das bedeutet Je spitzer eine Eins Ring Nachbarschaft zul uft und je gr sser ihre Oberfl che ist desto niedriger sollte die Priorit t sein diese zu entfernen Die Oberfl che einer Eins Ring Nachbarschaft ist offensichtlich die Summe der Fl chen der Dreiecke aus denen sie besteht Die diskrete Kr mmung wird nach Kim und Levin 23 berechnet aus der Gausskriimmung K und der mittleren Kr mmung H K an Rea 071 1 34 und TEET 4 27i I 34 Die Bedeutung der Bezeichner kann Abbildung 2 4 entnommen werden A bezeichnet den Fl cheninhalt der Eins Ring Nachbarschaft Abschlie end kann die diskrete Kr mmung Ka berechnet werden 2 H falls K gt 0 2 H sonst Nj 1 lij Abbildung 2 4 Zur Berechnung von K i verwendete Notation e bezeichnet die Kante vi vj fi bezeichnet das Dreieck v vi vit1 ai ist der Winkel zwischen zwei aufeinan der folgenden Kanten e und e und Dj ist der Winkel an einer Kante ej d h der Winkel zwischen den Normalen der zu ei adjazenten Dreiecke die Abbildung rechts ist ein Blick von der Seite Die Zeichnung wurde adaptiert von 23 Zusammenfassend berechnet man die Priorit t eines Knotens v wie folgt a v K v InaXpe stern
150. inhalten Man spricht von einer Transformation auf Referenzelemente Als Jacobi Verh ltnis wird das Verh ltnis von gr ter zu kleinster Determinante der Jacobi Matrizen in allen Eckknoten des Hexaederelements be zeichnet Die Determinante der Jacobi Matrix eines Eckknotens beschreibt das durch die inzi denten Kanten aufgespannte Volumen eines Tetraeders vgl Kap 2 4 1 Ein Jacobi Verh ltnis nahe 1 impliziert somit die Singularit t der Matrix sehr hohe Werte bedeuten dass die Trans formation unzuverl ssig wird s Abb 2 11 In einem idealen Element gibt es keinen Vorzei chenwechsel in den getesteten Knoten und die Werte sind alle hnlich gro Deshalb wird h ufig nicht nur von Jacobi Verh ltnis sondern auch von Jacobi Abweichung gesprochen 1 30 100 Abbildung 2 11 Beispiele f r die Jacobi Verh ltnisse I 30 und 100 F r Hexaeder wird das Jacobi Verh ltnis aus allen Eckknoten berechnet In jedem Knoten wird die Jacobi Matrix aufgestellt dabei ist sicherzustellen dass die drei Vektoren immer gleich gerichtet sind sie zeigen alle vom Testknoten weg und immer in der gleichen Reihenfolge als Spaltenvektoren in die Matrix eingetragen werden Elementinvertierungen und Zelldurchdringungen Bei der Verfeinerung und Unterteilung des Grobgitters k nnen unter Umst nden gerade bei der Randanpassung Zellen entstehen die sich gegenseitig durchdringen oder die invertiert also quasi nach au en gest lpt sind s Abb 2 12
151. iversit t Karlsruhe Verlag Shaker Aachen 1995 1994 KR GER J und WESTERMANN R Numerical Simulation on GPUs http wwwcg in tum de Research Projects GPUSim KR GER J und WESTERMANN R Linear algebra operators for GPU implementation of numerical algorithms In ACM Transactions on Graphics TOG Bd 22 S 908 916 2003 LITERATURVERZEICHNIS 181 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 KUZMIN D Skript zur Vorlesung CFD 2003 LAMPORT L AEX http www latex project org LEE A W F SWELDENS W SCHRODER P COWSAR L und DOBKIN D MAPS Multiresolution Adaptive Parameterization of Surfaces Computer Graphics Proceedings SIGGRAPH 98 S 95 104 1998 LI X Y und FREITAG L A Optimization Based Quadrilateral and Hexahedral Mesh Untangling and Smoothing Techniques Techn Ber Argonne National Lab 1999 LIU Y LIU X und WU E Real Time 3D Fluid Simulation on GPU with Complex Obstacles In Computer Graphics and Applications S 247 256 12th Pacific Conference on PG 04 2004 LUEBKE D M HARRIS J KRUGER T PURCELL N GOVINDARAJU I BUCK C WOOLLEY und A LEFOHN GPGPU general purpose computation on graphics hardware In GRAPH 04 Proceedings of the conference on SIGGRAPH 2004 cour se notes S 33 New York NY USA 2004 ACM Press MARK W R GLANVILLE R S AKELEY K und K
152. kanten Stellen der Objektoberfl che wie zum Beispiel an Orten mit starker Oberflachenkriimmung wurden h ufig absichtlich bei der Grobgittererstellung dort positioniert um Details der Geometrie besser aufzul sen Da die Winkelgl ttung diese Knoten f r weitere Gitterunterteilungsschritte ung nstig verschob wurde als weiteres Kriterium die Oberfl chenkr mmung in die Heuristik aufgenommen 5 8 GPU L ser In diesem Kapitel wird beschrieben wie auf einem Gitter das Poissonproblem s Kap 2 1 mit Hilfe einer Finite Differenzen Approximation realisiert und danach mit dem CG Verfahren auf der GPU gel st wird Aus dieser diskreten L sung wird der so genannte potential flow berechnet 5 8 1 Datenstruktur Da eine Finite Differenzen Matrix im vorliegenden Fall eine Bandstruktur besitzt s Kap 2 1 6 ist es sinnvoll anstelle der vollst ndigen Matrix nur die Inhalte der sieben B nder zu speichern Das Analogon zu Feldern auf der CPU sind Texturen auf der GPU Daher werden die B nder der Matrix zun chst mit Hilfe der Daten des zugrundeliegenden Gitters auf der CPU erzeugt und anschlie end mit den Methoden der FEASTGPU Bibliothek s Kap 3 13 in Texturen gespeichert 74 KAPITEL 5 SYSTEMBESCHREIBUNG 5 8 2 Implementierung Die FEASTGPU Bibliothek enth lt bereits Methoden zum L sen von Gleichungssystemen auf der GPU Diese Methoden konnten unver ndert bernommen werden Die Komponente zur Matrix Vektor Multiplikation ist jedoch a
153. knetzes der internen Liste hinzu int add_point para_point neuerPunkt f gt einen Punkt neuerPunkt mit den angegebenen Werten der internen Liste hinzu vector lt para_point gt getPointVector gibt die interne Liste der bekannten Punkt zur ck void setPointVector vector lt para_point gt p berschreibt die interne Liste der bekannten Punkte void setPoint int maps_id para_point pp berschreibt den Punkt an der Stelle maps_id in der internen Liste mit pp void is_nachbearbeiten pflegt die Liste der bekannten Punkte nach einem Vergr berungsschritt set lt maps_point compare_maps_points gt getPointsAroundPoint int maps_point_index Liefert Eckpunkte der Feintriangulierung zur ck die den Punktmaps_point_index umgeben Das sind entweder die Eckpunkte des Feindreiecks in dem der Punkt liegt oder alle adjazenten Punkte falls der Punkt schon Eckpunkt ist 162 ANHANG API DOKUMENTATION set maps point compare_maps_points gt Maps Modul getNextRing set lt maps_point compare maps points oldPoints Berechnet zu jeden Punkt aus o1dPoints mit Hilfe von getPointsAroundPoint die umgebenden Eckpunkte und gibt die Vereinigung zur ck So wird eine gr e re Umgebung als mit getPointsAroundPoint auf der Oberfl che bereit gestellt void updatePoint int punkt int vektorpunktindex pflegt die Liste der bekannten Punkte nach einer Ver nderung durch eine Gl ttung float getCurvatureMapsIdx int maps point
154. ktes Durch die Tastenkombination STRG W kann die komplette Szene im Blenderformat blend abgespeichert werden Um das Objekt sp ter als STL Datei zu exportieren ist das Abbspei chern der Szene unerl sslich der Export ist grunds tzlich nur aus bereits gespeicherten Szenen m glich Dazu wird das Objekt mit der rechten Maustaste ausgew hlt eine rosafarbene Um randung erscheint Nun kann ber das in Abbildung A 6 ersichtliche Men ein Export in das gew nschte Format in diesem Falle also STL vorgenommen werden i v GE Add Timeline Game Render Help SCR 2 Model x Isce scene New Open Reopen Last Recover Last Session VRML 1 0 Save Save As Compress File Save Image Dump Subwindow Dump Screen Save Runtime Save Dynamic Runtime Ctrl Save Default Settings Append Import Export Pack Data Unpack Data Quit Blender DXF Videoscape 3D Studio 3d ctn F3 ACID ac shit amp COLLADA dae CalaD v0 9 DEC Object File Format off DirectX x ls DirectX x Shift F1 LightWave Iwo gt Motion Capture bvh Nendo ndo OpenFlight 1 PLY Radiosity radio Raw Triangle raw Save Current Theme Softimage XSI xsi TrueSpace cob Object Mo VRML 97 old version a var wr E gt view select Obj
155. l der Unterteilungsschritte lediglich durch den zur Verf gung stehenden Arbeitsspei cher limitiert sein 6 2 TESTGEOMETRIEN UND TESTGITTER 79 a Originalobjekt im Gitter b Durch das Gitter angen herte Objektoberfl che Abbildung 6 1 nitiales Grobgitter f r Testfall 1 Testfall 2 Im Gegensatz zu Testfall 1 wird nun eine sehr grob aufgel ste Kugel 80 Dreiecke verwendet Das Grobgitter besteht ebenfalls aus 26 Hexaederzellen die Qualit t ist auf Grund von nur 42 Punkten auf der Oberfl che mit denen die Gitterknoten verbunden werden k nnen etwas schlechter Auch in diesem Testfall s Abb 6 2 wird die Anzahl der Unterteilungsschritte lediglich durch den zur Verf gung stehenden Arbeitsspeicher limitiert a Originalobjekt im Gitter b Durch das Gitter angen herte Objektoberfl che Abbildung 6 2 Initiales Grobgitter f r Testfall 2 80 KAPITEL 6 PROJEKTVALIDIERUNG Testfall 3 Als Objekt wird wieder die hochaufgel ste Kugel aus Testfall 1 verwendet Die Qualit t des initialen aus 26 Hexaederzellen bestehenden Grobgitters ist in diesem Fall jedoch bewusst schlecht unterhalb der Toleranzen gew hlt worden Da die Anzahl der Hexaederzellen unver ndert geblieben ist ist auch die Anzahl der m glichen Unterteilungsschritte unver ndert vgl Abb 6 3 a Originalobjekt im Gitter b Durch das Gitter angen herte Objektoberfl che Abbildung 6 3 Initiales Grobgitter f r Testfall 3 Testfall
156. ldung C 2 UML Klassendiagramm f r das Modul Gitter Die Abbildung C 2 zeigt eine bersicht der Klassen im Modul Gitter welche f r die Ver waltung der Gitterstruktur zust ndig sind Klasse cPoint cPoint ist die Entit tenklasse f r eine Kante im Gitter bool addEdge cEdge xedge f gt eine von bis zu sechs Kanten in einen Vektor der zum Knoten inzidenten Kanten ein void getIncidentHexas set lt cHexax compareHexas gt xhexaSet liefert alle Hexaeder zur ck die den Knoten als Eckpunkt haben int getAdjacentPoints cPoint liefert alle Knoten die mit dem betrachteten Knoten durch Kanten verbunden sind 152 ANHANG C API DOKUMENTATION bool equals cPoint comp testet den Knoten auf Gleichheit mit comp bezogen auf die Koordinaten im Raum static void resetMapsCount setzt den Z hler f r den MAPS Index zur ck static void setMapsCount int count setzt den MAPS Index Z hler auf count static int getNextMapsIndex liefert den Z hlerstand des MAPS Index Z hlers und inkrementiert ihn danach Klasse cEdge cEdge ist die Entit tenklasse f r eine Kante im Gitter bool addFace cFace face f gt eine von bis zu vier Fl chen in einen Vektor der zur Kante inzidenten Fl chen ein cPoint getOtherPoint cPoint point gibt den jeweils anderen Knoten der Kante zur ck bool checkPoints int status testet ob beide Knoten der Kante den im Parameter bergebenen Status haben bool hasSolidPoint
157. ll schichtenweise so verfahrend durchnummeriert sind Es soll schrittweise beginnend mit dem Fall C R die so genannte Finite Differenzen Matrix aufgebaut werden Seien f und u als Spaltenvektoren definiert also u 1 uni f fi o fN Der Fall Q C R Es gilt 1 2 uj i h2 f z 2 7 f r j L N 1 f r j 0 N befindet man sich auf dem Rand und ist fertig Eine kompaktere Schreibweise fiir 2 7 ist f 2 8 hierbei ist Au eine symmetrische N 1 x N 1 Matrix die Finite Differenzen Matrix genannt wird Gleichung 2 8 ist das lineare Gleichungssystem dessen L sung der numerischen L sung des Poisson Problems entspricht Hier gilt tridiagy_ 1 2 zx also ist Ag eine tridiagonale Matrix auf deren Hauptdiagonalen jeder Eintrag 2h ist Auf den beiden Nebendiagonalen steht stets h alle restlichen Eintr ge der Matrix f r den zweidi mensionalen Fall sind 0 h ist hierbei der Abstand der einzelnen Gitterzellen in z Richtung vgl Abb 2 2 14 KAPITEL 2 GRUNDLAGEN N 1 NA Abbildung 2 2 Beispiel eines zweidimensionalen strukturierten Gitters Der Fall C R Aus Gr nden der Ubersichtlichkeit wird im weiteren Verlauf angenom men dass die Abst nde innerhalb des Gitters in x sowie in y Richtung identisch bi sind ist eine symmetrische UN 1 x N 1 2 Matrix F r die Zeil
158. llten hierbei folgende Punkte sein e Platzierung des Objektes im Grobgitter Markierung von Knoten die sich am Rand des Kanals befinden Markierung von Knoten die sich innerhalb des Objektes befinden Markierung von Knoten die sich auf dem Objektrand befinden Setzen der Koordinaten einzelner Knoten auf die Koordianten eines Geometrie Eck punktes und die manuelle Verbesserung von Knotenpositionen Wi Freeware grobgitter Datei Help Grobgiter Parameter Kantenl nge a xy 2 Grobgitter erzeugen Knotenmarkierungen setzen Objekt An Transparent Aus Ansicht Alle Knoten C innerhalb einer Box um Objekt interest und innere Knoten C nur interest Knoten anzeigen IV nur die Schnittkanten anzeigen Hexaederseitenfl chen auf dem Objekt Punktgr sse CiDokumente und Einstellungen klausjEigene Datelenjcys grobgitter bin tutorial_objekt stl98 Punkte und 192 Fl chen Abbildung 5 1 Die Benutzeroberfl che des Grobgitter Werkzeugs HaGrid3D 56 KAPITEL 5 SYSTEMBESCHREIBUNG 5 2 2 Aufbau des Programms Die grafische Oberfl che bietet vier verschiedene Ansichten auf das Objekt und das Grobgitter wobei drei davon 2D Ansichten sind die Vorder Seiten und Draufsicht realisieren s Abb 5 1 Die vierte Ansicht erm glicht eine perspektivische Darstellung Alle Ansichten k nnen frei konfiguriert werden Die Knoten werden mit der Maus ausgew hlt un
159. lt als Iterationsvorschrift 2 6 a p pth pe plktl p k 1 BE Be D pit 1 4 g 0g 9 Dabei ist x eine geeignete Startl sung und die Iteration wird beendet sobald p unter eine vorgegebene Schranke f llt F r Details wird auf Hackbusch 20 und Meister 36 verweisen Defektkorrekturverfahren Diese Klasse von Verfahren arbeitet so dass zum Iterationsvek tor ein Korrekturwert hinzuaddiert wird um so n her an die L sung zu gelangen Das zu l sende lineare Gleichungssystem wird folgenderma en umgeschrieben x Ab x x A b x 1 1 In dieser Form ist dies noch ein direktes Verfahren die L sung steht nach einem Schritt zur Verf gung Zur Vorbereitung der weiteren Schritte wird obige Gleichung formuliert als Iterati onsverfahren xU x 4 A 1 p Ax 9 Der Ausdruck in der Klammer ist gerade der Defekt im k ten Schritt Die Idee bei Defektkor rekturverfahren besteht nun darin nicht die vollst ndige Matrix A zu invertieren sondern nur Teile davon Nimmt man z B nur die Diagonaleintr ge von A sind zur Invertierung nur deren Kehrwerte zu bilden und man spricht vom Jacobi Verfahren Nimmt man die untere Dreiecks matrix hinzu die sich durch R ckw rtseinsetzen relativ leicht invertieren l sst erh lt man das so genannte Gau Seidel Verfahren Allerdings konvergieren diese Verfahren so langsam dass sie als
160. mmt es zu 45 Jacobi Fehlern sowie zu sehr schlechten Winkeln und einem schlechten L ngenverh ltnis Die Testwerte finden sich in Tabelle 6 8 Darin sind das Betriebssystem und weitere laufende Programme mitgerechnet 114 KAPITEL 6 PROJEKTVALIDIERUNG Wird ein schlechtes Grobgitter f r die gleiche Geometrie Testfall 7 verwendet so stellt sich ein anderes Ergebnis dar W hrend es schon in Unterteilungsschritt 2 zu zwei Jacobi Fehlern kommt deren Anzahl auf 77 in Stufe 4 steigt so sind die minimalen und maximalen Winkel bis Unterteilungsstufe 3 deutlich besser Das gleiche gilt f r das L ngenverh ltnis Die exakten Werte lassen sich Tabelle 6 9 entnehmen Bei Testfall 8 wird ein noch komplexeres und praxisn heres Objekt gew hlt f r den ein gu tes Grobgitter entworfen wurde Ohne die Verwendung von Gl ttern kann das Grobgitter zwei Mal unterteilt werden erst in Stufe drei kommt es zu einem Jacobi Fehler Die hier auftreten den maximalen und minimalen Winkel sind jedoch noch im Toleranzbereich des von der PG entwickelten L sers Ab Stufe vier ist das resultierende Gitter nicht mehr akzeptabel da so wohl die Winkel schlecht werden als auch die Zahl der Jacobi Fehler weiter ansteigt F r die genauen Werte wird auf Tabelle 6 10 verwiesen Das Grobgitter hat starken Einfluss auf die Qualit t der durch Unterteilung entstehenden Git ter insbesondere die Entstehung ung ltiger Elemente wird durch die Verwendung ungeeigneter Grobgi
161. ms and conditions either of that version or of any later version published by the Free Software Foundation If the Program does not specify a version number of this License you may choose any version ever published by the Free Software Foundation If you wish to incorporate parts of the Program into other free programs whose distributi on conditions are different write to the author to ask for permission For software which is copyrighted by the Free Software Foundation write to the Free Software Foundation we sometimes make exceptions for this Our decision will be guided by the two goals of preserving the free status of all derivatives of our free software and of promoting the sharing and reuse of software generally NO WARRANTY BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE THERE IS NO WARRAN TY FOR THE PROGRAM TO THE EXTENT PERMITTED BY APPLICABLE LAW EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND OR OTHER PARTIES PROVIDE THE PROGRAM AS IS WITHOUT WARRANTY OF ANY KIND EIT HER EXPRESSED OR IMPLIED INCLUDING BUT NOT LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU SHOULD THE PROGRAM PROVE DEFECTIVE YOU ASSUME THE COST OF ALL NECESSARY SERVICING REPAIR OR CORRECTION IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRI TING WILL ANY COPYRIGHT HOLDER OR ANY OTHER PARTY WHO M
162. n auf der Homepage des Entwicklers eingesehen werden A 4 Bekannte Fehler e Berechnung von Punkten auf der Objektoberfl che scheitert Je nach Grad der Vergr berung kann es bei der Gitterunterteilung vorkommen dass die Berechnung eines neuen Punktes auf der Objektoberfl che scheitert Die neu entstehen den Punkte werden in diesem Fall in den Koordinatenursprung gezogen um diesen Feh ler deutlich zu kennzeichnen Dieser Fehler kann umgangen werden wenn f r die Parametrisierung des Geometrieob jekts der Vergr berungsgrad variiert wird http www xdiv lanl gov XCM gmv GMVHome html Anhang B Pflichtenheft und Endprodukt B 1 Pflichtenheft B 1 1 Zielbestimmung Ziel ist der Entwurf und die Entwicklung einer Softwareumgebung zur numerischen Str mungssimulation unter Ausnutzung der Leistungsf higkeit moderner Grafikkarten und ent sprechender 3D Gittermanipulationstechniken Das System soll objektorientiert und plattform unabh ngig entwickelt werden Beim Entwurf ist ferner auf die Erweiterbarkeit mit weiteren Deformationsans tzen bzw weiteren numerischen Verfahren zu achten Die Implementierung soll in der Programmiersprache C unter Nutzung von QT OpenGL und Cg erfolgen B 1 2 Produkteinsatz und Produktvoraussetzungen Hardware Das Produkt soll auf handels blichen Rechnern 32 und 64 Bit zum Einsatz kommen Da Be rechnungen auf der GPU ausgef hrt werden sollen muss eine Grafikkarte mit programmier baren
163. n Hexeaderzellen deutlich redu ziert werden indem nur diejenigen angezeigt werden die sich in einer definierten Umgebung des Objektes befinden Hierzu kann in der Bedienungsoberfl che ausgew hlt werden ob alle Zellen zu interessanten Knoten inzident sind s Abb 5 4 oder alle die sich innerhalb eines fest um das Objekt definierten Quaders befinden angezeigt werden sollen Es ist auch m g lich s mtliche Hexeaderzellen zu verstecken oder das Objekt selbst zu verstecken s Abb 5 5 bzw transparent darzustellen 5 2 GROBGITTERGENERATOR 59 Abbildung 5 3 Ein Grobgitter mit 15 x 15 x 15 Hexaederzellen Abbildung 5 4 Ein Grobgitter mit 25 x 25 x 25 Hexaederzellen es werden nur die interessanten Knoten angezeigt 60 KAPITEL 5 SYSTEMBESCHREIBUNG Abbildung 5 5 Ein Grobgitter mit 25 x 25 x 25 Hexaederzellen es werden nur interessante Knoten mit den Kanten die das Objekt schneiden angezeigt Das Objekt ist ausgeblendet 5 2 7 Inklusionstest Der Inklusionstest soll f r jeden Knoten des initialen Grobgitters festlegen ob er innerhalb oder au erhalb des Geometrieobjekts liegt Zu diesem Zweck wird ein beliebiger zuf lliger Referenzpunkt au erhalb des Grobgitters und damit auch au erhalb des Geometrieobjekts aus gew hlt F r jeden Punkt des Grobgitters und jedes Dreieck des Objektes wird anschlie end g
164. n Problemgr e von N 1024 1024 Die leeren Felder deuten auf fehlende Eigenschaften der Grafikkarte hin ATI unterst tzte zum Testzeitpunkt das Zeichnen in Texture Rectangles nicht 7888 5000 sage 4000 j sega 4000 MFLOP s fj 2808 r MFLOP s 2608 r 1808 1808 j D3D R32 D3D RGBA32 D3D RGBA16 R32 RECT CG RGBA32 RECT CG F RGBA16 RECT CG R32 2D FBO F RGBAS2 FBO F RGBA32 CG RGBA16 2D CG R32 RECT GLSL GBA32 RECT GLSL fF R32 RECT FBO RGBA32 RECT FBO f E 1624 65536 419430 RGBA16 2D GLSL RGBA16 RECT FBO f 16 RECT GLSL f RGBAS2 GLSL a MFLOP s f r verschiedene Problemgr en b MFLOP s f r verschiedene Texturformate Abbildung 4 4 Testergebnisse ATI Radeon 9800 PRO 52 KAPITEL 4 VORARBEITEN Fazit Die PG entschied sich f r OpenGL mit der Framebuffer Object Extension die jetzt auch von den ATI Catalyst Treibern unterst tzt wird Die Benchmarks erzielten unter OpenGL auf je der getesteten Hardware die besten Ergebnisse Hinzu kommt dass OpenGL mit der FBO Erweiterung auch portabel ist und somit auch Linux bedient werden Kann Kapitel 5 Systembeschreibung berblick und die Module im Detail Zum besseren Verst ndnis der Funktionsweise von InGrid3D werden nachfolgend die einzel nen Komponenten in ihrer Funktionsweise und Zusammenarbeit erkl rt Ein trianguliertes 3D Objekt wird als Grundlage v
165. n bez glich des minimalen Winkels so dass eine Nachbe arbeitung durch das Kantenkippverfahren engl edge flipping vorgenommen wird Um die Triangulierung im Dreidimensionalen am Objekt anwenden zu k nnen wird diese nach dem Delauney Kriterium optimiert 5 4 SNAKES 63 5 3 2 Einbettung Nachdem eine Triangulierung gefunden wurde werden alle vorher eingebetteten Knoten und der neu entfernte Mittelpunkt in den neuen Dreiecken parametrisiert Dazu werden alle vorher eingebetteten Punkte durchlaufen und das umschlie ende Dreieck aus der Triangulierung ge sucht Die Einbettung wird f r jeden Knoten durch die baryzentrischen Koordinaten bez glich des umschlie enden Dreiecks abgespeichert Um die Konnektivit t der eingebetteten Punkte zu erhalten wird eine Kopie des Feinnetzes gespeichert 5 4 Snakes 5 4 1 Initialisierung Um eine Snake zwischen zwei beliebigen Punkten auf der Oberfl chentriangulierung zu initia lisieren wird der Single Source Shortest Path Algorithmus von Dijkstra 8 benutzt Zus tzlich wurde das Snake Konzept um die M glichkeit erweitert nicht nur Punkte der Oberfl chentri angulierung als Start und Endpunkte zu benutzen sondern die Punkte auch frei auf einem Dreieck positionieren zu k nnen Der Dijkstra Algorithmus liefert eine Menge von Punkten die miteinander verbunden einen Pfad bzw k rzesten Weg bilden Diese Punkte werden gem ihrer Reihenfolge durchlaufen und auf allen ausgehenden Kanten dieser Pu
166. n gr bsten Aufl sungsstufe dem Grobnetz Es existiert ein Dreieck auf dem Grobnetz etwa T a b c in dem die ser Punkt liegt Also kann dieser Punkt in baryzentrischen Koordinaten bzgl dieses Dreiecks dargestellt werden Ph 8 7 Wobei a 8 1 8 y gt 0 a b c Bei der Berechnung der Parametrisierung wird auf Hierarchiestufe l eine st ckweise lineare Bijektion DAIN konstruiert Beginnend mit 1 L erh lt man II id und endet schlie lich mit der gesuchten Abbildung II II Hierbei wird nur an den Knoten in K berechnet Die Werte f r alle weiteren Knoten ergeben sich aus der st ckweisen Linearit t Um aus II zu berechnen werden folgende F lle unterschieden 1 k K Der Knoten wird beim bergang von Hierarchiestufe l zu l 1 nicht entfernt Setze also II pj M pp pr 2 2 MULTIRESOLUTION ADAPTIVE PARAMETERIZATION OF SURFACES 21 2 k K AK 1 Der Knoten wird beim bergang 1 1 entfernt Die Eins Ring Nachbarschaft von wird in die Ebene projiziert s o Nach der Retriangulie rung k nnen die Koordinaten des zuvor entfernten Punktes p einem Dreieck welches T a b c entspr che zugeordnet werden Der Punkt kann folglich in bary zentrischen Koordinaten bez glich dieses Dreiecks geschrieben werden Y rr Pe In diesem Fall setze II pj apa Ype Die baryzentrischen
167. n mit Hilfe des Dijkstra Algorithmus snake evolution berechnet einen Schritt bei der Bewegung der Snake auf der Oberfl che s Kap 2 5 3 snake glaetter berechnet eine l ngenoptimierte Snake durch sehr kleine Bewegungsschritte para point get middle point a para point b liefert durch Aufrufe von dijkstra snake evolution snake glaetter und bestimme mitte die Mitte der Snake zur ck C 1 BERSICHT BER DIE PAKETE UND KLASSEN VON INGRID3D 159 C 1 3 Modul MAPS Abbildung C 3 UML Klassendiagramm f r das Modul MAPS Die Abbildung C 3 zeigt eine bersicht der Klassen im Modul MAPS Dieses Modul bein haltet die zur Parametrisierung notwendige Funktionen Klasse Maps_Bari stellt Funktionen zur Berechnung von baryzentrische Koordinaten zur Verf gung float area st_point a st_point b st_point c berechnet die Fl che des Dreiecks das durch die drei zweidimensionalen Knoten a b und c aufgespannt wird float calc baris st point a st point b st point c st point x Berechnet mit Hilfe von area die baryzentrischen Koordinaten des Punk tes x bez glich des Dreiecks a b c Der R ckgabewert ist eine Liste aus drei Flie kommazahlen Der erste Wert bezieht sich auf Eckpunkt a danach b und der letzte auf c Klasse Maps Delaunay Diese Klasse realisiert basierend auf der Klasse Tri eine auf das 3D Gitter anwendbare Trian gulierung Die Triangulierung wird so weit m gli
168. n rot eingef rbt s Abb 5 2 Der aktuelle Arbeitsfortschritt der Grobgittererzeugung per Hand kann jederzeit abgespeichert und wieder eingelesen werden Das fertige Grobgitter kann ber die Ex portfunktion in einer Bin rdatei gespeichert werden die dann von InGrid3D eingelesen werden kann 5 2 GROBGITTERGENERATOR 57 Abbildung 5 2 Eine bereits auf das Objekt gezogene Hexaederseitenfl che wird rot und alle inzidenten Kanten der beteiligten Knoten werden gelb eingef rbt 5 2 3 Verschieben von Grobgitterknoten auf Geometrie Eckpunkte Durch das von OpenGL unterst tzte Picking k nnen Knotenpaare mit der Maus ausgew hlt werden Durch einen Mausklick wird von der Bildschirmoberfl che aus gesehen ein Strahl in den dahinter liegenden dreidimensionalen abgebildeten Raum definiert OpenGL erfasst nun alle Elemente innerhalb einer festgelegten Umgebung dieses Strahles und gibt sie in Form einer Liste aus Je nach gedr ckter Tastenkombination kann ein Grobgitterknoten oder ein Ob jektknoten ausgew hlt werden Wurde zuerst ein Grobgitterknoten selektiert dann wird beim Selektieren eines Objektpunktes derjenige innerhalb der Liste mit der geringsten euklidischen Distanz zum zuvor gew hlten Grobgitterknoten selektiert Dies ist notwendig da beim Picking teilweise sehr viele Objektknoten getroffen werden 5 2 4 Interne Darstellung des Grobgitters Die Grobgitterknoten werden in einem dreidimensionalen Feld gespeichert ber das mit drei
169. nGrid3D zum Ein satz kommt Kapitel 2 3 beschreibt anschlie end die Anforderungen an ein Gitter zur numerischen Str mungssimulation hierbei wird vor allem auf die verschiedenen Netztypen die Qua lit tskriterien und die verschiedenen Gl ttungsmethoden eingegangen Kapitel 2 4 f hrt in Gitterkorrekturmethoden zur Behebung von Selbstdurchdringungen und Elementinvertierungen engl mesh untangling ein Anschlie end erl utert Kapitel 2 5 die theoretischen Grundlagen von aktiven Konturen die allgemein auch als snakes bezeichnet werden Diese dienen als Hilfe bei der Be rechnung eines k rzesten geod tischen Weges zwischen zwei Punkten Kapitel 2 6 bietet eine kompakte bersicht zum Themenkomplex general purpose com putation using graphics hardware GPGPU Das darauf folgende Kapitel 3 erg nzt das Grundlagenkapitel um eine kurze bersicht der verwendeten Werkzeuge und Bibliotheken Im Anschluss folgt ein kurzer Bericht ber die ge leisteten Vorarbeiten der PG in Kapitel 4 Insbesondere Konzepte die untersucht im Laufe des Projektes aber als untauglich bzw ungeeignet befunden wurden werden hier erw hnt Nachfolgend stellt Kapitel 5 das von der Projektgruppe entwickelte System vor und zwar zu n chst das allgemeine Konzept und danach die konkrete Arbeitsweise der verschiedenen Mo dule und Teilsysteme Eine objektive Einsch tzung der Resultate bietet Kapitel 6 wobei zu n chst die einzelnen Teilsysteme und Module
170. nd verwaltet das aktuelle Grobgitter im Editor void create int x int y int z Erstellt beim Aufruf ein neues Grobgitter Als Parameter werden die Anzahl der Knoten in jede der drei Achsen bergeben Zun chst wird ein eventuell vorhan denes Grobgitter vollst ndig gel scht und anschlie end neu erstellt Die Knoten werden in drei verschachtelten Schleifen gleichm ig hintereinander geschrieben Der Abstand der Knoten zueinander ist die vordefinierte Kantenl nge der Hexa ederzellen Das Grobgitter wird genauso wie das Objekt im Koordinatenursprung zentriert void detect Interesting Vertices Diese Methode dient zur Klassifizierung von Knoten die sich in der direkten N he zum Objekt befinden Die Knoten erhalten beim Aufruf dieser Methode eine ent C 2 BERSICHT BER DIE KLASSEN VON HAGRID3D sprechende Markierung wenn sie zu einer Kante inzident sind die den Objektrand schneidet void paint_Hexas Sind Hexaederzellen als sichtbar markiert so werden sie mit dieser Methode ge malt Au erdem wird hier entschieden ob die Kanten gezeichnet werden die den Objektrand schneiden wenn die Hexaederzellen ausgeblendet wurden void paint_Vertices int i int o int p in Abh ngigkeit von den Knoteneigenschaften z B interessant oder solid Status wird hier den Knoten die Zeichengr e zugeordnet void paint ParaFaces Beim Aufruf werden die Hexaederseitenfl chen die sich auf dem Objektrand be finden identi
171. ne von Nvidia und Microsoft begr ndete Programmiersprache f r Grafikprozessoren Cg kann als eine Art C Dialekt mit sehr hnlicher Struktur und Syntax aufgefasst werden Sie ist mit dem Ziel der Plattformunabh ngigkeit und Unabh ngigkeit von bestimmten Herstellern entwickelt worden und bietet zudem eine C Schnittstelle zu OpenGL und Direct3D runtime environment an Mit Hilfe von Cg wurden GPGPU Performancetests durchgef hrt s Kap 4 4 und der prototypische GPU L ser implementiert s Kap 5 8 3 11 BrookGPU BrookGPU 6 ist eine Metasprache die entwickelt wurde um GPUs direkt zu programmieren Das hei t dass man sich nicht mit OpenGL DirectX oder ATI Nvidia Erweiterungen also mit der grafikspezifische Implementierung besch ftigen muss sondern sich ganz auf den Al gorithmus konzentrieren kann BrookGPU wurde bei den GPGPU Leistungstests benutzt s Kap 4 4 3 12 LA Framework Das Lineare Algebra Framework LA Framework 26 basiert auf der DirectX Schnittstelle und wurde entwickelt um die Programmierung numerischer Berechnungen auf der GPU zu ver einfachen Es bietet eine Vielzahl von fertigen Bausteinen die man f r diese Berechnungen benutzen kann Das LA Framework wurde ebenfalls bei den GPGPU Performancetests benutzt s Kap 4 4 3 13 FEASTGPU FEASTGPU ist eine Implementierung zu aktuellen Forschungsarbeiten am Lehrstuhl f r An gewandte Mathematik Sie wurde der PG als Ausgangspunkt f r die Implement
172. nkte auf einer Seite des Pfades werden die Snaxel gesetzt Somit ist sichergestellt dass alle Snaxel gleichgerichtet sind s Abb 5 7 Abbildung 5 7 Der durch den Dijkstra Algorithmus ermittelte k rzeste Weg fett auf der Ober fl chentriangulierung dient der Snake blau zur Initialisierung Alle Snaxel werden auf der gleichen Seite des Pfades erzeugt 5 4 2 Bewegung Die Bewegung der Snake ist ein iterativer Prozess Zun chst wird jedem Snaxel ber die im Grundlagenkapitel 2 5 3 skizzierte Vorgehensweise eine Geschwindigkeit zugewiesen Dann werden alle Snaxel auf ihren Halbkanten gem ihrer errechneten Geschwindigkeit verscho ben wobei darauf geachtet wird dass maximal ein Snaxel das vordere oder hintere Ende einer Kante erreicht Sollte dies geschehen so berquert der Snaxel das Ende der Kante und auf den 64 KAPITEL 5 SYSTEMBESCHREIBUNG n 1 inzidenten Halbkanten werden neue Snaxel erzeugt Hierbei auftretende Verletzungen der Konsistenzbedingungen werden gem den Erl uterungen in Kapitel 2 5 3 behandelt Diese Schritte werden solange wiederholt bis eines der Abbruchkriterien greift s Abb 5 8 welche im folgenden Kapitel dargestellt werden Abbildung 5 8 Die Snake hat ihre Zielposition erreicht beide Abbruchkriterien treffen zu 5 4 3 Abbruchkriterien Um zu erkennen wann die Snake ihr Ziel erreicht hat wurden zwei Abbruchkriterien imple mentiert Das erste Kriterium ist dabei die Geschwindigkeit de
173. nnen werden In Abbildung A 17 kann man das Ergebniss der Reduzierung sehen die Independent Set 1x entfernen Schaltfl che wurde vier Mal bet tigt Die Objektoberfl che des Originals ist trans parent dargestellt sodass der Unterschied zwischen der Originalobjektoberfl che und der re duzierten Objektoberfl che gesehen werden kann Bevor man mit der Gitterunterteilung beginnt sollte man zuerst die Zeichenoptionen in der entsprechenden Leiste so ausw hlen dass nur die Gitterzellen am Objektrand angezeigt werden s Abb A 18 Unterteilung Gl ttung Zeichenoptionen Debug GPGPU L ser Objekt Driginalmesh zeichnen C Solide Transparent Gar nicht Objektlinien zeichnen Grobes Objekt zeichnen Snake zeichnen Gitter Punkte zeichnen Punktgr e 5 Crd d Modem d 2 o X dc d X db dr Gitter zeichnen C Garnicht Nur am Objektrand C Komplett C Objektoberflache Innere Fl chen Qualit tsmerkmale Jacobi Fehler Schlechteste Winkel Schlechteste Aspect Ratio Schlechteste Edge Ratio Qualit tspr fung Abbildung A 18 Die Zeichenoptionen Leiste Hat man sich einen berblick verschafft wird mit der Gitterunterteilung begonnen indem man die Unterteilen Schaltfl che bet tigt Die Unterteilung kann auch ber die Tastenkombinati on Strg D gestartet werden Nach jedem Gitterunterteilungsschritt oder nach dem Bet tigen der Qualit tspr fung
174. nst char file liest die Informationen aus einer STL Datei und erzeugt daraus eine OpenMesh Datenstruktur vector st point get min max berechnet die kleinsten und gr ten Koordinaten des Objektes in X Y und Z Richtung und gibt diese in einem Vektor aus Anhang D GNU General Public License Version 2 June 1991 Copyright 1989 1991 Free Software Foundation Inc 59 Temple Place Suite 330 Boston MA 02111 1307 USA Everyone is permitted to copy and distribute verbatim copies of this license document but changing it is not allowed Preamble The licenses for most software are designed to take away your freedom to share and change it By contrast the GNU General Public License is intended to guarantee your freedom to share and change free software to make sure the software is free for all its users This General Public License applies to most of the Free Software Foundation s software and to any other program whose authors commit to using it Some other Free Software Foundation software is covered by the GNU Library General Public License instead You can apply it to your programs too When we speak of free software we are referring to freedom not price Our General Public Licenses are designed to make sure that you have the freedom to distribute copies of free software and charge for this service if you wish that you receive source code or can get it if you want it that you can change the software or use
175. nten Ohrenabschneiden arbeitet angewendet 45 Laut Meisters Theo rem gibt es eine Diagonale die ein Ohr vom brigen Polygon separiert Das Ohr ist bereits korrekt trianguliert Somit kann es von der weiteren Betrachtung ausgeschlossen werden Es wird abgeschnitten und mit dem verbleibenden Polygon rekursiv fortgefahren 2 2 5 Parametrisierung Die angestrebte Parametrisierung ist eine Abbildung von einem Dreieck der gr bsten Aufl sungsstufe auf die zu parametrisierende Oberfl che Die Vorgehensweise ist adaptiv d h w h rend die oben angef hrten Schritte zur Vergr berung des Netzes f r eine Vergr berungsstufe durchgef hrt werden s Abb 2 5 werden die entfernten Punkte parametrisiert 20 KAPITEL 2 GRUNDLAGEN Abbildung in den Parameterraum i i Lo MENT d NxN Abbildung 2 5 Um einen Knoten k zu entfernen wird der zugeh rige Stern stern k vom drei dimensionalen Raum durch die konforme Abbildung in die Ebene abgebildet In der Ebene wird der innere Knoten des Sterns entfernt und das entstandene Polygon neu trianguliert 30 Die Beschriftungen wurden aus dem Englischen bersetzt Hierzu wird eine Abbildung II K K w hrend der Vereinfachung aufgebaut Die ge suchte Parametrisierung ist die Umkehrabbildung II Der zu einem Knoten k assoziierte Punkt K wird durch II auf einen Punkt c abgebildet Dieser Punkt befindet sich auf dem Netz der momenta
176. nteractive but does not normally print such an announcement your work based on the Program is not required to print an announcement These requirements apply to the modified work as a whole If identifiable sections of that work are not derived from the Program and can be reasonably considered independent and separate works in themselves then this License and its terms do not apply to those sections when you distribute them as separate works But when you distribute the same sections as part of a whole which is a work based on the Program the distribution of the whole must be on the terms of this License whose permissions for other licensees extend to the entire whole and thus to each and every part regardless of who wrote it Thus it is not the intent of this section to claim rights or contest your rights to work written entirely by you rather the intent is to exercise the right to control the distribution of derivative or collective works based on the Program In addition mere aggregation of another work not based on the Program with the Pro gram or with a work based on the Program on a volume of a storage or distribution medium does not bring the other work under the scope of this License You may copy and distribute the Program or a work based on it under Section 2 in object code or executable form under the terms of Sections 1 and 2 above provided that you also do one of the following a Accompany it with the complete co
177. nterschiedliche Standards f r Grafikkarten ATI NVIDIA Grafikkarten APIs OpenGL DirectX und Shadersprachen Cg GLSL HLSL gibt einigte sich die PG darauf einen Vergleichstest durchzuf hren Ziel dieses Tests sollte sein eine Testumgebung zu konstruieren die es erlaubt die bestm gliche Technik einfach zu bestimmen um diese dann anzuwenden Zus tzlich gibt es noch die M glichkeit eine Metasprache wie BrookGPU zu benutzen die es erlaubt Grafikkarten unabh ngig von den oben genannten Unterschieden zu programmieren Als Grundlage f r den Vergleichstest wurden die SAXPY C und SAXPY V Operationen ge w hlt da diese sehr h ufig in numerischen Berechnungen benutzt werden SAXPY C ist Teil der BLAS Bibliothek 49 und damit auf CPUs typischerweise hochoptimiert SSE SSE2 usw Die f r den Test benutzten Operationen sind wie folgt definiert saxpy c yli a x i saxpy v y i al Als Rahmen f r die DirectX Tests stand das LA Framework s Kap 3 12 und f r die OpenGL Tests eine Implementierung aus einem Tutorial zum Thema 15 zur Verf gung Zus tzlich wurde BrookGPU als frei verf gbare Metasprache eingesetzt s Kap 3 11 F r die Durchf hrung der geplanten Tests wurde das LA Framework um eine eigene SAXPY Klasse erg nzt welche auch neue Shader beinhaltet Die OpenGL Implementierung konnte ohne nderung benutzt werden da dort bereits ein SAXPY Test implementiert war F r Brook GPU musste le
178. oberfl che Die zuvor beschriebenen Gl tter sind nicht in der Lage Knoten der Hexaederzellen auf der Oberfl che des Objektes zu manipulieren Tritt dort ein Jacobi Fehler auf kann durch diese Gl tter keine erfolgreiche Gitterkorrektur durchgef hrt werden Aus diesem Grund entwickel te die PG zwei heurisitische Ans tze um Elementinvertierungen lokal zu beheben und die Innenwinkel der Randelemente zu optimieren Jacobi Gl ttung Verursacht eine Hexaederzelle einen Jacobi Fehler so wird versucht f r die Knoten dieser Zelle bessere Positionen auf dem Feinnetz zu finden und somit den Fehler zu beheben Hier zu wird zu jedem dieser Knoten die Eins Ring Umgebung der Punkte auf dem Feinnetz auf bessere Positionen untersucht Schl gt die Suche fehl so wird in der Zwei Ring Umgebung gesucht dieses Verfahren wird fortgesetzt bis hin zur Zehn Ring Umgebung Wird f r einen Knoten keine bessere Position gefunden so wird die Routine auf den n chsten Knoten der Hexaederzelle angewandt Sind alle Knoten der betroffenen Hexaederzelle auf Verbesserungs m glichkeiten berpr ft worden so bricht der Gl tter bei dieser Zelle ohne Erfolg ab es sei denn der Jacobi Fehler wurde bereits durch eine Verschiebungen behoben 5 8 GPU L SER 73 Der Gl tter kann lediglich solche Fehler korrigieren die sich durch das Verschieben eines Kno tens beheben lassen Sollte es n tig sein zwei oder mehr Knotenpositionen einer Hexaederzelle zu ndern so m
179. ochoptimierte Implementierungen von verschiedenen L sungsverfahren Hauptgrund fiir die Effizienzsteigerung ist die Verwendung intelligenter Um ordnungsstrategien so dass die Rechnung mit m glichst wenig Transfers zwischen Cache und Speicher auskommt Experimente zeigen dass UMFPACK f r kleine Problemgr en auf han dels blichen PCs fast unschlagbar schnell ist Iterative Verfahren Die zweite Klasse bilden die iterativen Verfahren die das endg ltige Resultat nicht schon nach einem Schritt ausgeben sondern erst nach mehreren Daf r sind die Einzelschritte deutlich weniger aufw ndig CG Verfahren Das CG Verfahren setzt symmetrische und positiv definite Koeffizientenma trizen A voraus d h A AT x Ax gt 0 VxeR 0 a An 0 0 Der zur Aufl sung des Gleichungssystems erforderliche Aufwand l sst sich durch die Verwen dung einer der Aufgabe angepassten Basis des IR gezielt reduzieren Basisvektoren mit der Eigenschaft Api pj mit dem Kronecker Symbol 0 1 f r j und 0 sonst hei en konjugiert oder A orthogonal Stellt man die gesuchte L sung x des Gleichungssystem ber der Basis dar d h N j l dann lassen sich die zugeh rigen Koeffizienten 17 f r j 1 N wegen der A Orthogona lit t von p explizit darstellen durch b p u pj N Zu finden unter http www cise ufl edu research sparse umfpack 12 KAPITEL 2 GRUNDLAGEN Man erh
180. of Ty Coon 1 April 1989 Ty Coon President of Vice 177 This General Public License does not permit incorporating your program into proprietary pro grams If your program is a subroutine library you may consider it more useful to permit linking proprietary applications with the library If this is what you want to do use the GNU Library General Public License instead of this License 178 ANHANGD LIZENZ Literaturverzeichnis 1 2 3 4 5 6 7 8 9 10 11 12 AHLBERG J Active Contours in Three Dimensions Diplomarbeit Link ping Universi ty SE 581 83 Link ping Sweden 1996 BERKELAAR M DIRKS J EIKLAND K und NOTEBAERT P LPSOLVE http groups yahoo com group lp solve BISCHOFF S WEYAND T und KOBBELT L Snakes on triangle meshes Bild verarbeitung f r die Medizin S 208 212 2005 http www i8 informatik rwth aachen de publications downloads sotm pdf Blender http www blender3d org BOLZ J FARMER I GRINSPUN E und SCHRODER P Sparse Matrix Solvers on the GPU Conjugate Gradients and Multigrid In Proceedings of ACM SIGGRAPH 2003 Bd 22 S 917 924 2003 Buck I FOLEY T HORN D SUGERMAN J FATAHALIAN K HOUSTON M und HANRAHAN P Brook for GPUs stream computing on graphics hardwa re ACM Trans Graph 23 3 777 786 2004 http doi acm org 10 1145 1015706 1015800 CVS http www cvshome org docs manual cvs html
181. oint cEgde cFace und cHexa und f gt sie so zum Gitter zusammen cGrid int maxPoints int maxEdges int maxFaces int maxHexas Konstruktor der ein cGrid anlegt welches die in den Parametern angegebene Anzahl an Elementen aufnehmen kann cPoint addPoint double x double y double z int status int mapsIndex 0 F gt einen Knoten mit den 3D Koordinaten x y und z zum Gitter hinzu status repr sentiert ob der Knoten Randknoten ist zur Oberfl che geh rt oder innerhalb des Objektes liegt MapsIndex wird f r jeden Knoten auf der Objektoberfl che ben tigt und dient zur Kommunikation mit dem Modul Maps 154 ANHANG C API DOKUMENTATION cEdgex addEdge cPoint start cPoint send int direction DIR_UNDEFINED int status NO_BORDER F gt zwischen den zwei Knoten start und end eine Kante mit der Richtung direction und dem Status status in das Gitter ein Die Richtung wird f r ein gerichtetes Durchlaufen des Gitters ben tigt cFacex addFace cEdge 0 cEdge xedgel cEdge edge2 cEdge edge3 int status NO BORDER f gt eine Fl che mit den Randkanten edge0 bis edge3 mit dem Status status in das Gitter ein cHexax addHexa cFace 0 cFace facel cFace xface2 cFace face3 cFace face4 cFace xface5 f gt eine Gitterzelle mit den sechs Randfl chen face0 bis face5 in das Gitter void buildGridFromPoints int a int b int c Erzeugt ein kartesische
182. onen so ausw hlen dass nur die Grobgitterknoten in der N he des Objektes angezeigt werden Sinnvollerweise sollten hier die Hexaederzellen zun chst ganz ausgeblendet werden Unter den Knoten sollte man sich hier zun chst nur die interessan ten Knoten anzeigen lassen Hat man sich einen berblick verschafft so beginnt man nun mit dem Verschieben der Grobgitterknoten auf das Objekt Die Knoten werden mit dem Mauszei ger selektiert und dann auf Objektknoten verschoben Um einen Grobgitterknoten zu selektie ren muss zus tzlich zur linken Maustaste noch die Steuerungstaste gedr ckt gehalten werden M chte man einen Objektknoten selektieren so muss die Steuerungstaste zusammen mit der Y Taste gedr ckt gehalten werden Abbildung A 11 zeigt ein solches Knotenpaar vor dem Verschieben Mit der Leertaste kann nun der selektierte Grobgitterknoten auf den Objektkno ten verschoben werden Selektierte Knoten werden etwas dicker als die brigen dargestellt Ist ein Grobgitterknoten auf einen Geometrie Eckpunkt gezogen worden so wird er fortan gelb dargestellt wie in Abbildung A 12 zu sehen ist A 2 TUTORIAL uni C AA AA 2 MAS E WZ gt Eh C Dokumente und Einstellungenjklaus Eiger a m bin tutorial_objekt stl98 Punkte und 19 Y 7 AR p KR van 03 133 Abbildung A 11 Ein selektiertes Knotenpaar kann nun mit der Leertaste auf dem Objektrand vereint werden BZ
183. orausgesetzt Eine weitere Voraussetzung f r eine Gitterunterteilung ist ein geeignetes Gitter welches die gegebene Geometrie grob approxi miert Dazu m ssen einige Gitterknoten auf dem Dreiecksnetz des Objektes liegen Der eigens f r diesen Zweck erstellte Grobgittergenerator HaGrid3D liefert die dazu n tigen Manipulati onsm glichkeiten und unterst tzt bei der manuellen Erstellung eines solchen Grobgitters Nachdem in nGrid3D zuerst ein Objekt und das dazu passende in HaGrid3D erstellte Gitter geladen wurden folgt als n chster Schritt die Parametrisierung des 3D Objektes Sie dient zur schnellen Approximation eines auf dem Dreiecksnetz liegenden Mittelpunktes zwischen zwei ebenfalls auf dem Dreiecksnetz liegenden Punkten Die Parametrisierung entfernt in einer be stimmten Reihenfolge Punkte der Oberfl che retrianguliert die dadurch entstandenen L cher und bestimmt neue Positionen f r die bereits entfernten Punkte innerhalb der neuen Triangulie rung Die Positionen werden hierbei mit Hilfe von baryzentrischen Koordinaten innerhalb der neuen Dreiecke gespeichert Dies funktioniert nach dem in Kapitel 2 2 vorgestellten Verfahren Das Objekt wird durch diese Methode stark reduziert ohne dass seine grobe Struktur verloren geht Das reduzierte Objekt sieht dem urspr nglichen Objekt damit immer noch in gewisser Weise hnlich Nach der Parametrisierung folgt die Unterteilung der Hexaeder Jeder Hexaeder wird hierbei regul r in acht neue Hex
184. ork 45 3 13 FEAST GPU EE Sh ak eG qe beu RUN 45 4 Vorarbeiten 47 4 1 Diplomarbeit von 47 4 9 Normal Meshes 4 a E es 47 4 37 Cubit ih oui e eR arr Ve adieu a ree ep uch 48 GPGPU uu sau PIS Pd Minus dani reu ud gos dale dations 49 5 Systembeschreibung 53 5 1 Geometrieobjekte eh 54 5 2 Grobgittergenerator 55 3 2 1 Anforderungen 3 wu a EX a OA ak 55 5 2 2 Aufbau des Programms 2 2 ee ee 56 5 2 3 Verschieben von Grobgitterknoten auf Geometrie Eckpunkte 57 5 2 4 Interne Darstellung des Grobgitters 57 5 2 5 Im undExport onen 58 3 2 0 Visualisierung 52 de oe ee ra e Die 58 5 2 7 Inklusionstest 60 9 37 P ramelfisierung zu Qu par na ee Laie pa 62 5 3 1 Retriangulierung 62 3 332 Einbettung 4 5 a nn a nn E 63 9 4 EE ee Dani ie Be Sas 63 SA Initialisierung zoom Bean en 63 53 4 2 Bewegung 4 er 63 543 Abbr chktriterien i uo E Ae xo Reo ener Aog 64 5 4 4 Grenzen des Konzeptes eee 65 5 5 Gitterunterteilung nh 66 54 Datenst kt t 2 2 25 AGE REGIS RR mens 66 5 5 2 67 INHALTSVERZEICHNIS 5 6 Gitteranpassung an das Objekt 69 5 6 1 Implementierungsdetails
185. ototyp ees 118 7 2 2 MAPS Prototyp 121 12 3 Snakes Prototyp 22 RA ow Rede X ex RE 122 A Benutzerhandbuch 125 AT Installation 2 urs gros fee a Shier deh esd ata Wane Yos 125 ACD Tutorial e be doe Ro Ris er Bean he ex AE 125 A 2 1 Tutorial Erzeugung eines 3D Objektes mit Blender 126 A 2 2 Tutorial Erzeugung eines Grobgitters in HaGrid3D 130 A 2 3 Tutorial Gitterunterteilung mit InGrid3D 134 A 2 4 Tutorial L ser und 139 Dateiform te aoia en Dia hh AE S RU ge 142 A 3 1 STEE Eormat a Ls Ron a Roos m d idm Rn 142 3 2 Monaten E DE exe y ee he 142 A 3 3 SGRID Form t e gue Bra Er dus ue c di IU s ra 143 vi A 3 4 GPUGRID Format 3 5 GPU Format A 3 6 GMWV Format AA BekannteFehler B Pflichtenheft und Endprodukt B 1 Pflichtenkheft u rds 1 1 Zielbestimmung B 1 2 Produkteinsatz und Produktvoraussetzungen B 1 3 Produktfunktionen B2 Endprodukt e 2 1 Erreichte Ziele B 2 2 Produkteinsatz und Produktvoraussetzungen B 2 3 Produktfunktionen C API Dokumentation 1 bersicht ber die Pakete und Klassen von InGrid3D C 1 1 Modul Omer C 1 22 Modul C 1
186. programmieren kann GPGPU wurde schon in vielf ltigen Projekten realisiert Beispielhaft sind hier Ray Tracing 50 Sortieralgorithmen 33 Kollisions oder FFT Berechnung 40 zu nennen Die aktuelle Entwicklung in diesem Bereich l sst sich dem State of the Art Report entnehmen 47 Da ein Ziel des Projektes in der Realisierung einer Str mungssimulation gesetzt war wird hier mehr auf den Einsatz von GPGPU zur Berechnung von Str mungen hingewiesen 5 32 Insbesonde re soll hier auf die Arbeit von Kr ger und Westermann eingegangen werden 27 Sie behandelt generelle Techniken zur Berechnung von algebraischen Gleichungen wie sie in numerischen Simulationen vorkommen Zur L sung von sp rlich besetzten linearen Gleichungssystemen werden dort das CG und das Gauss Seidel Verfahren benutzt Eine interessante Idee ist die Repr sentation von 2D Matrizen als Menge von diagonal verlaufenden Vektoren die sp ter ausf hrlicher behandelt wird Im von der PG implementierten L ser kommt ein hnliches Ver fahren zum Einsatz das jedoch f r den dreidimensionalen Fall angepasst wurde s Kap 5 8 F r d nn besetzte Matrix Vektor Produkte wurde ein Verfahren erarbeitet welches es erlaubt den Vertexprozessor in die Berechnungen einzubinden Dies ist insofern vorteilhaft als in den meisten Ver ffentlichungen f r Berechnungen auf der GPU ausschlie lich der Fragmentpro zessor verwendet wird Eine interessante Optimierung wurde erzielt indem Vektoren
187. r Snaxel Sobald dieser Wert f r alle Snaxel so weit gesunken ist dass kaum noch eine Bewegung stattfindet werden die Iterationen abgebrochen Da die Geschwindigkeiten in jeder Iteration neu berechnet werden m ssen wird auch diese Kontrolle in jeder Iteration durchgef hrt Das zweite Kriterium bezieht sich auf die Lange der Snake wenn keine weitere Minimierung mehr erfolgt k nnen die Iterationen ebenfalls beendet werden Da die Berechnung der L n ge rechenintensiver als die Geschwindigkeitsvergleiche ist wird diese nur nach jeweils 1000 Iterationen berpr ft Das L ngenkriterium ist unerl sslich da es in Einzelf llen vorkommen kann dass die Snake kontinuierlich zwischen zwei Positionen hin und herspringt dies ist zum Beispiel dann der Fall wenn sich die Snake in einer Zick Zack hnlichen Form s Abb 5 9 befindet Das Kriterium der Snaxelgeschwindigkeiten w rde in einem solchen Fall nicht greifen Die L nge der Snake berechnet sich aus der Summe der L ngen der einzelnen Segmente Die L nge der Seg mente wird ber die euklidische Distanz zweier benachbarter Snaxel bestimmt 5 4 SNAKES 65 Abbildung 5 9 Links Die Snake befindet sich in einer Zick Zack Konfiguration Rechts Im n chsten Iterationsschritt invertieren die Snaxelpositionen da die hohen lokalen Kr m mungswerte f r hohe Snaxelgeschindigkeiten sorgen Die Snake schwingt also in der N he der L sung 5 4 4 Grenzen des Konzeptes
188. rch Bet tigen der Schaltfl che Remove red Point kann ein einzelner Knoten dessen Nachbarschaft rot einge f rbt ist entfernt werden Durch Setzen von H kchen in den Auswahlfeldern flatview und delaunayview werden die 2D Einbettungen der rot markierten Eins Ring Nachbarschaft ein mal vor der Entfernung des Knotens und einmal nach Entfernen des Knotens und Retriangu lierung dargestellt Eine andere M glichkeit ist die gesamte unabh ngige Menge zu entfernen Remove whole IS Ist hierbei das Auswahlfeld 3D View aktiv so wird die 3D Ansicht des Objektes nach jeder Knotenentfernung aktualisiert Zur Visualisierung des Fortschritts der Parametrisierung k nnen Parameterlinien zu den para metrisierten Punkten eingeblendet werden wenn die H kchen bei P Linien und P Punkte gesetzt sind Durch Aktivieren des Auswahlfeldes P Netz wird die Projektion der Feindrei ecke auf die momentanen Grobdreiecke dargestellt Ein H kchen bei Originalmesh zeichnet das Originalnetz in der 3D Ansicht ber das Grobnetz Mit den drei vertikal angeordneten Schiebereglern kann der rot dargestellte Punkt innerhalb 122 KAPITEL 7 ENTWICKLUNGSPROZESS eines Grobdreiecks durch nderung seiner baryzentrischen Koordinaten verschoben werden Mit dem oberen Texteingabefeld s Abb 7 6 rechts unten l sst sich ein Dreieck des Grob netzes ausw hlen W hlt man nun mit dem unteren Texteingabefeld ein zweites Grobdreieck aus
189. rch Projektion in die Ebene erhal ten werden k nnen Dies ist im brigen auch der Grund warum die sechs Seitenfl chen nicht ausreichen um die Qualit t eines Hexaederelements zu beurteilen Abbildung 2 7 Querschnittsfl chen und Seitenfl chen eines Hexaeders L ngenverh ltnis L ngenverh ltnisse z hlen zu den bekanntesten Qualit tskriterien Sie sind ein Indikator f r die zu erwartende numerische Stabilit t w hrend der Simulationsberechnung Hohe L ngenver h ltnisse k nnen zu starken Fehlern f hren sofern keine geeigneten Stabilisierungsverfahren eingesetzt werden 20 Abbildung 2 8 Beispiele f r L ngenverh ltnisse von 1 1 1 und 20 1 20 Im Zweidimensionalen bezeichnet das L ngenverh ltnis das Verh ltnis von k rzester zu l ng ster Kante eines Viereckselements Ein Analogon im Dreidimensionalen n mlich das Verh lt nis gr ter zu kleinster Seitenfl che ist vorstellbar erfordert jedoch bei nichtplanaren Seiten fl chen einen zu hohen Berechnungsaufwand zur Approximation dieser so genannten Regel 2 3 GITTER 25 fl chen oder Minimalfl chen Stattdessen wird eine Approximation der neun oben genannten Testfl chen vorgenommen und jeweils das Seitenverh ltnis eines solchen 3D Viereckselements berechnet Als L ngenverh ltnis des Hexaeders wird dann der schlechteste Wert genommen Ein ideales Element hat ein L ngenverh ltnis von 1 alle Kanten sind gleich lang das Element ist w rfelf rm
190. ren wurde ein GPU L ser implemen tiert um die Korrektheit der generierten Hexaedergitter zu demonstrieren 148 ANHANG B PFLICHTENHEFT UND ENDPRODUKT Anhang C API Dokumentation 149 150 ANHANG API DOKUMENTATION C 1 bersicht ber die Pakete und Klassen von InGrid3D GUI MyWindow cGrid OpenGL View points cPoint gApp OApplication gMainwWin QMainWindow menu MyMenu openGL OpenGLyiew ob Object maps_modul Maps Modul multiGrid cMultiGrid snake obj Snake 1 datei QPopupMenu gitter QPopupMenu hilfe QPopupMenu subdivideID int Snake mesh MyMesh start para point ziel para point startknoten MyMesh VertexHandle zielknoten MyMesh VertexHandle GPU L ser Hoad data load void createBandsGPU static void grid2GMVv int solverGPLI double calculateTestVector double calculateDerivative object Object nPoints int multiGrid cMultiGrid grid cGrid ne ink snake Snake smoothType edges cE oe button ButtonState smoothiter int nEdges int rotX float winkelToleranz int maxEdges int rotY Float subdivisions int 1 Faces cFace trans float badHexas int races Int float worstEdgeRatio double maxFaces int transz float worstAspectRatio double hexas cHexa viewWidth int smallest ngle double Rb viewHeight int biggest ngle double max
191. rin eine Software zur Erzeugung und Deformation geeigneter Volumengitter zu entwickeln Insbesondere die Qualit t der Gitterelemente He xaeder stellte eine enorme Herausforderung dar So war es z B wichtig dass sich einzelne Gitterzellen nicht gegenseitig durchdringen 1 2 EINORDNUNG DES PROJEKTES 3 Die Projektgruppe verfolgte weiterhin einen aktuellen Trend der in der Evaluierung der Re chenkraft der Grafikkarte f r allgemeine Anwendungen au erhalb des Renderings general purpose computation using graphics hardware 17 besteht Diese k nnen als streaming pro cessor aufgefasst werden und in Hochsprachen komfortabel programmiert werden Erste Ver ffentlichungen wie 5 10 27 bertragen einfache numerische L sungsverfahren in eine GPU Implementierung und versprechen im Vergleich zu einer reinen CPU Implementierung eine Beschleunigung um einen Faktor 5 bis 15 1 2 Einordnung des Projektes Eine erste Sichtung der zur Verf gung stehenden Software zur Gittergenerierung zeigte folgen de Schwachpunkte Die Programme beschr nkten sich auf zweidimensionale Problemstellun gen waren nicht frei verf gbar oder waren f r die Anforderungen der PG nicht geeignet 52 Die in der PG erstellte Gittersoftware InGrid3D erlaubt es ein f r die Str mungssimulation taugliches Gitter zu erzeugen welches eine vorgegebene Geometrie m glichst gut approxi miert und ein allgemeintaugliches Ergebnisgitter zur Verf gung stellt Dieses Gitter k
192. rresponding machine readable source code which must be distributed under the terms of Sections 1 and 2 above on a medium customarily used for software interchange or b Accompany it with a written offer valid for at least three years to give any third party for a charge no more than your cost of physically performing source distri bution a complete machine readable copy of the corresponding source code to be distributed under the terms of Sections 1 and 2 above on a medium customarily used for software interchange or c Accompany it with the information you received as to the offer to distribute corre sponding source code This alternative is allowed only for noncommercial distri bution and only if you received the program in object code or executable form with such an offer in accord with Subsection b above The source code for a work means the preferred form of the work for making modifica tions to it For an executable work complete source code means all the source code for all modules it contains plus any associated interface definition files plus the scripts used to control compilation and installation of the executable However as a special excep tion the source code distributed need not include anything that is normally distributed in either source or binary form with the major components compiler kernel and so on of the operating system on which the executable runs unless that component itself accompanies the ex
193. s Fl cheninhalts aufgestellt s Kap 2 4 1 und als Zielfunktion an ein lineares Programm LP bergeben Die Zielfunktion wird optimiert und das Ergebnis der Optimierung ist eine neue Knotenposition Ein Qualit ts ma muss gewisse Anforderungen erf llen damit es sich zum Entfernen von Durchdringun gen eignet Es sollte zwischen g ltigen und ung ltigen Elementen unterscheiden k nnen und weiterhin sollte bei der Optimierung stets das globale Extremum gefunden werden F r das Qualit tsma minimaler Fl cheninhalt ist dies m glich Hierzu wird zun chst der Begriff der Level Sets definiert F r eine Funktion f D R D C R und ein festes u ist das Level Set von f auf dem so genannten Level definiert als Lu x F x uj Die Konvexit t des Level Sets spielt eine gro e Rolle Falls die Level Sets der ausgew hlten Funktion konvex sind und man ein Minimum findet so ist dieses Minimum global F r Qua lit tsma e wie z B den minimalen Winkel im lokalen Teilnetz oder den Sinus dieses Winkels 2 4 ENTFERNEN VON SELBSTDURCHDRINGUNGEN 29 sind die Level Sets nicht konvex wenn der freie d h der zu verschiebende Knoten p nicht im G ltigkeitsbereich liegt Also sind diese Ma e nicht geeignet f r das Entfernung von Selbst durchdringungen durch lineare Optimierung Das Qualit tsma das in der PG verwendet wird ist die minimale Fl che ber alle Elemente im lokalen Teilnetz Diese Fl che wird maxim
194. s Gitter aus a x b x c Knoten Die Knoten m ssen bereits zuvor in einer fest definierten Reihenfolge ins Gitter eingef gt worden sein da mit die Routine korrekt arbeitet Sie legt dann Kanten Fl chen und Gitterzellen entsprechend an int getFreeDirection cPointx objPoint Pr ft die zu objPoint inzidenten Kanten und z hlt wie viele von Ihnen in X Y und Z Richtung verlaufen Sobald eine Richtung gefunden wird in der bisher kei ne oder nur eine Kante verl uft so wird diese Richtung als noch freie Richtung zur ckgegeben bool smooth bool smoothSmart false Gl ttet das gesammte Gitter nach Laplace s Kap 2 3 3 Der Parameter smoothSmart steuert ob die Gl ttung nach einer Verschlechterung im Gitter abbrechen soll void umbrellaSmooth bool pre false gl ttet das Gitter mit Hilfe des Umbrellaoperators s Kap 2 3 3 void calcSmallestBiggestAnglesFaces set lt cFacex compareFaces gt xusedFaces double minAngle double maxAngle double minFace double xmaxFace berechnet den kleinsten und gr ten Winkel sowie die kleinste und gr te Fl che innerhalb der Menge usedFaces und gibt diese ber minAngle und maxAngle minFace und maxFace zur ck cEdgex getNextEdge cPoint point cEdge xlastEdge int direction Gibt die n chste Kante ausgehend von Last Edge ber point in Richtung direction zur ck C 1 BERSICHT BER DIE PAKETE UND KLASSEN VON INGRID3D 155 static
195. s Vektorfeld M Druck IV verbesserte Interpolation v Gitterzellen Abbildung A 23 Das verbessert interpolierte Druckfeld inklusive Gitterschicht Unterteilung Gl ttung Zeichnen GPGPU Debug L serdaten Zeichenoptionen yz Schicht i IV Geschwindigkeits Vektorfeld IV normiertes Vektorfeld Druck IV verbesserte Interpolation Gitterzellen Abbildung A 24 Alle Zeichenoptionen gleichzeitig eingeschaltet 142 ANHANG A BENUTZERHANDBUCH A 3 Dateiformate A 3 1 STL Format Innerhalb von InGrid3D und HaGrid3D werden die verwendeten Oberfl chentriangulierungen in Form von STL Dateien eingelesen Das STL Dateiformat dient der Abspeicherung von dreidimensionalen Objekten Die Objekte werden in Form von Punkten und Fl chen in einer Datei gespeichert Es ist ein weit verbreitetes Dateiformat welches von den meisten 3D Anwendungen unterst tzt wird Die Punkte werden durch ihre Koordinaten und Fl chen durch ihre Punkte beschrieben Es ist m glich die Dateien entweder im ASCII Format oder in bin rer Form zu speichern Wird ein Objekt im ASCII Format gespeichert so hat dies den Vorteil dass die Datei mit einem Texteditor durch den Anwender lesbar ist Somit hat er die M glichkeit Debug Informationen direkt auszulesen oder manuell einzelne Parameter des Objektes zu ver ndern 3 2 CM Format Das CM Format coarse mesh ist ein eigens entworfenes Dateiformat zur Speicherung von Grobgit
196. sch betrachtet eine Zusammenhangskomponente Ein Dreieck mit den Eckpunkten b c wird durch a b c beschrieben Eine Kante zwischen a und b wird durch e a b beschrieben Die Eckpunkte a b c eines Dreiecks bzw die Endpunkte a b einer Kante werden Knoten genannt Wenn vom geometrischen Ort gesprochen wird so ist das Analogon zu einem Knoten ein Punkt x IR und zu einer Kante ein Vektor e c d 2 3 Eine geschlossene Triangulierung ist eine Mannigfaltigkeitstriangulierung wenn gilt Jede Kante ist zu genau zwei Dreiecken inzident 62 Eine Parametrisierung ist in Bezug auf das MAPS Verfahren als eine bijektive Abbildung definiert die Punkte des Basisnetzes auf die Punkte der urspr nglichen Oberfl che abbildet Die zu parametrisierende Oberfl che liegt in Form eines so genannten Dreiecksnetzes vor Ein 2 2 MULTIRESOLUTION ADAPTIVE PARAMETERIZATION OF SURFACES 17 Dreiecksnetz wird als Paar K repr sentiert hierbei ist P eine Menge von N Punkten des R mit zi Yi zi 1 lt i lt N K ist die Menge aller Knoten Kanten und Dreiecke Zwei Knoten a und b sind benachbart wenn a b K gilt Eine Menge von Knoten ist unabh ngig wenn die Menge aller Knoten kein benachbartes Knotenpaar enth lt Eine solche Menge ist maximal unabh ngig wenn sie in keiner gr eren unabh ngigen Menge enthalten ist Die Eins Ring Nachbarschaft eines Knotens a ist die Menge N a b a b K also die Menge der Kno
197. senschaften der angewandten Mathematik der Informatik und den Ingenieurwissenschaften Als Fallbeispiel soll das Szenario des virtuellen Windkanals dienen bei dem ein dreidimensio nales komplexes Objekt gegeben durch eine Beschreibung seiner Oberfl che in einem Kanal fixiert und von einer Seite des Kanals eine Str mung eingeleitet wird Als Beschreibungsform des Objektes wurde von der PG die in der Computergrafik g ngige Form der Oberfl chentrian gulierung verwendet 39 Mit Hilfe von FD wird das Differenzvolumen zwischen Objekt und Kanal also der Bereich in dem beim Experiment tats chlich Str mungsvorg nge auftreten w rden in viele kleine hexa ederf rmige Elemente zerlegt All diese Elemente berdecken zusammen das Simulationsge biet ihre Gesamtheit wird Rechengitter genannt Dieses Rechengitter bildet zun chst eine rein geometrische Diskretisierung des Str mungsgebiets Ein gutes Rechengitter muss optimal an die konkrete Situation angepasst sein es m ssen beispielsweise alle relevanten Details der Geo metrie aufgel st werden So sieht man in Abbildung 1 1 die hochaufgel ste Geometrie einer Kugel und die Approximation der Kugel durch die Seitenfl chen der anliegenden Hexaeder Abbildung 1 1 Links Hochaufgel ste Oberfl chentriangulierung einer Kugel Rechts Durch 24 Hexaederseitenfl chen approximierte Oberfl che der Kugel Die Hauptanforderung der PG bestand da
198. ser Parametrisierung hingewiesen hat Aufgrund des hohen Implementierungsaufwandes bei der Berechnung der k rzesten geod tischen Wege auf dem Feinnetz riet er eher zu anderen Verfahren weswegen sich die PG gegen dieses entschieden hat 4 2 Normal Meshes Das Normal Meshes Verfahren dezimiert das vorhandende Dreiecksnetz ebenfalls mit Hilfe von Punktverschmelzungen 19 Es wird eine Segmentierung berechnet mit deren Hilfe die einzelnen Punkte des Feinnetzes ber den einzelnen Dreiecken des Grobnetzes parametrisiert 47 48 KAPITEL 4 VORARBEITEN werden Diese Parametrisierung wird mit Hilfe der L nge des Normalenvektors zum Grobdrei eck von dem zu parametrisierenden Punkt aus bewerkstelligt In der Ver ffentlichung wird an dem f r die PG relevanten Punkt n mlich der initialen Parame trisierung auf MAPS 30 verwiesen Aus diesem Grund verfolgte die PG auch diese Methode nicht weiter 4 3 Cubit Im Rahmen der Projektgruppe wurde Cubit 52 evaluiert um ein Grobgitter f r die Str mungssimulation zu erzeugen Dazu wurde das zu umstr mende Objekt in einem quaderf r migen Kanal positioniert und mittels der Methode substract das Differenzvolumen erzeugt s Abb 4 1 a welches mit gleichf rmigen Hexaederzellen aufgef llt werden sollte Das automatisierte Erstellen eines sinnvollen Grobgitters stellte sich jedoch als unm glich her aus Mittels des Schemas TetMesh und der Methode Mesh kann ein Differenzvolumen mit Tetraedern
199. sierung eh 2 3 GIET ee a ee RR OW vetas detis DL ee Nu 2 3 1 Gitterunterteilung 2 2 2 ee ee 2 3 2 Qualit tskriterien 2 3 3 2 4 Entfernen von Selbstdurchdringungen 2 4 1 Allgemeine Formulierung des Optimierungsproblems 2 4 2 Anwendung auf Hexaedernetze 2 5 Aktive Konturen e ment ee 2 5 L Gradient Vector Flow sono rasen 2 5 20 iActive Net 1 02 25 Frans ey ee 2 5 3 Snakes auf Oberfl chentriangulierungen 2 6 GPGPU gt ati uper er ee ra ba en lil iii iv INHALTS VERZEICHNIS 2 6 1 Hardware en ee A Cale open 37 2 6 2 Shader undMetasprachen 37 2 6 3 GPU Konzepte i supe Bee uo rm pe eei 39 Werkzeuge 43 OpenGL uie venere dbi expose V deg Seo ML rebos 43 D QM x c T UELLE 43 313 Visual Studios ee aedes xo er ee a o eA 43 CVS Soumettre REPE ur Re REUS 44 355 TATE eat Sale eke en er BOs PA NE Sak BALE MALES OG 44 3 6 Open Meshes vs uerbi deu ep doe Gea abe PC s ead prd elus 44 Se Blender Rex URGE Eu VE DNE RURSUS 44 3 9 Triangulate vu uec eR SE ee eon ters 44 3 9 Epsolve us cou ie Re sme M oS ORA a tod meae M e ases 45 EINES de epo er ter ER de bea NE dU ee tino DG 45 Sel Ts serve dex ded yen Rm EN Red NOR HOS vel ug 45 3 12 LA Framew
200. stellten Programmen erw hnt werden Es muss als Oberfl chentriangulierung vorliegen und es muss eine 2 Mannigfaltigkeit also ein geschlossenes Volumen bilden Diese Eigenschaften werden bereits teilweise durch das Objekt erf llt das Blender beim Start l dt ein w rfelf rmiges Element s Abb A 1 Dieser W rfel besteht aus Vierecksfl chen er kann jedoch leicht in eine Oberfl chentriangu lierung also in eine Repr sentation durch Dreiecke umgewandelt werden Dies wird jedoch erst im letzten Schritt des Tutorials beschrieben B d Ki E gt File Add Timeline Game Render Help L Iscr2 Moei X L Iscesscene ve Fa Ob9 1 i View Select Object Object Mode E amp d HH e a B gt Panes ejoa 1 Abbildung A 1 Blender direkt nach dem Start Standardm ig wird eine Szene bestehend aus einer Lichtquelle einer Kamera und einem W rfelobjekt geladen Verfeinerung des Objektes Als erstes soll die gegebene Geometrie verfeinert werden Dazu muss mit der Tabulator Taste zun chst in den sog Edit Modus von Blender gewechselt werden Mit der Taste A k nnen nun alle Punkte des Objektes ausgew hlt werden s Abb A 2 A 2 TUTORIAL 8CR2 Modet 5 5 Abbildung A 2 Alle Punkte des W rfels wurden ausgew
201. t Rand Knoten im Hexaeder berholt und ein invertiertes Element erzeugt Eine Durchdringung dieser Art ist mit dem gew hlten Ansatz nicht garantiert aufl sbar denn es wird als Nebenbedingung in der Formulierung des linearen Programms gefordert dass der minimale Fl cheninhalt der acht Tetraeder die um einen Knoten gebildet werden k nnen vergr ert wird Diese Forderung kann in einem solchen Fall h ufig nicht erf llt werden Anschlie end folgt ein weiterer Test der Reparatur Prozedur Das in Abbildung 6 31 a dar gestellte Grobgitter enth lt 27 Jacobi Fehler Die Reparatur Prozedur erreicht nach drei Itera tionen bereits eine g ltige Konstellation der Gitterzellen Wie in Abbildung 6 31 b ersichtlich werden von diesem Gl tter lediglich die Jacobi Fehler repariert sonstige Qualit tskriterien bleiben unber cksichtigt 102 KAPITEL 6 PROJEKTVALIDIERUNG a 27 Jacobi Fehler im Grobgitter b Alle Fehler wurden entfernt Abbildung 6 31 Die Reparatur Prozedur im Einsatz 6 5 EINFLUSS DER INITIALEN OBJEKTREDUZIERUNG 103 VW app n D EE Ma ae R all Mi Re SUR SE 81 Abbildung 6 32 Randknoten berholen innere Knoten 6 5 Einfluss der initialen Objektreduzierung In dies
202. t aus den eingehenden Koordinaten die Texturkoordinaten der Nachbarn des jeweiligen Punktes und kann mit diesen die partiellen Ableitungen berechnen 5 9 Visualisierung In diesem Kapitel wird die Visualisierung der Ergebnisse des GPU L sers beschrieben Der L ser berechnet ein Skalarfeld von Druckwerten f r ein Gitter Daraus l t sich ein Ge schwindigkeitsvektorfeld berechnen Diese Gr en sind einzeln oder gemeinsam in InGrid3D darstellbar die Daten werden f r einzelne Schichten des Gitters gezeichnet Es ist m glich die Gitterschichten parallel zur X Y Ebene parallel zur X Z Ebene oder parallel zur Y Z Ebene auszuw hlen um aus jeder Richtung die Ergebnisse des L sers betrachten zu k nnen Dar ber hinaus kann man das Druckfeld das Geschwindigkeitsvektorfeld oder nur die Gitterzellen der ausgew hlten Schicht angezeigt werden Zur Darstellung des Druckfeldes wird ein vom Druck abh ngiger Farbverlauf verwendet Hier bei stellen bl uliche Farben geringe gr nliche Farben mittlere und r tliche Farben die hohen Druckwerte dar In der Standarddarstellung wird eine Gitterzelle in Dreiecke unterteilt s Abb 5 15 und die Farben ber diese Dreiecke interpoliert Bei der verbesserten Interpolation wird eine Gitterzelle in acht Dreiecke unterteilt um mehr Punkte zur Interpolation verwenden zu k nnen und somit einen genauen und gleichm igen Farbverlauf darzustellen s Abb 5 16 5 9 VISUALISIERUNG 75 Abbildung 5 15 Dr
203. ted in the hope that it will be useful but WITHOUT ANY WARRANTY without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE See the GNU General Public Li cense for more details You should have received a copy of the GNU General Public License along with this program if not write to the Free Software Foundation Inc 59 Temple Place Suite 330 Boston MA 02111 1307 USA Also add information on how to contact you by electronic and paper mail Ifthe program is interactive make it output a short notice like this when it starts in an interactive mode Gnomovision version 69 Copyright C yyyy name of author Gnomovision comes with ABSOLUTELY NO WARRANTY for details type show w This is free software and you are welcome to redistribute it under certain conditi ons type show c for details The hypothetical commands show w and show c should show the appropriate parts of the General Public License Of course the commands you use may be called something other than show wand show c they could even be mouse clicks or menu items whatever suits your program You should also get your employer if you work as a programmer or your school if any to sign a copyright disclaimer for the program if necessary Here is a sample alter the names Yoyodyne Inc hereby disclaims all copyright interest in the program Gnomovision which makes passes at compilers written by James Hacker signature
204. ten b so dass es eine Kante zwischen a und 6 gibt Der Stern eines Knotens a stern a ist die Menge der Kanten und Dreiecke die a enthalten W hrend des Aufbaus der Parametrisierung wird es im weiteren Verlauf notwendig sein ein Polygon zu triangulieren Seien vo v1 Un 1 n Knoten 11 vi 001 vn 1 vo n Kanten die diese Knoten miteinander verbinden Diese bilden ein Polygon genau dann wenn die Schnittmenge zweier Kanten nur aus dem Knoten den sie beide teilen besteht und nichtinzidente Kanten sich nicht schneiden Ein weiterer wichtiger Begriff in diesem Zusammenhang ist der des Ohres Drei im Polygon aufeinander folgende Knoten a b c eines Polygons P bilden ein Ohr wenn die Kante a c eine Diagonale in P bildet Hierbei bildet eine Kante a c eine Diagonale wenn f r alle Kanten e von die keinen der Knoten a c enthalten gilt a c Ne und a innerhalb von P liegt 2 2 2 Aufbau der Hierarchiestufen Im MAPS Algorithmus wird eine Hierarchie von Netzen aufgebaut Das urspr ngliche Netz P K P9 K PF KP wird sukzessiv durch einen Knotenentfernungsschritt ver einfacht und es ergibt sich eine Folge von Netzen mit 0 l lt L hierbei wird P K als das Basisnetz bezeichnet es ist das gr bste Netz in der Hierarchie Die in MAPS verwendete Vereinfachungsprozedur ist angelehnt an das Verfahren von Dobkin und Kirk patrick 9 und garantiert dass die Anzahl
205. ten p pz py Dz und seine Nachbarn u tz Uy uz v Uz Vy Uz und w Wz Wy Wz 1 det u DVD 2 14 hierbei ist 1 1 1 Ur Ur We det uy vy Wy ay det 1 1 1 Uz Ug Wz Uz Uz Wz 2 15 Ur Ur We Ur Ur Wr det uy v Wy uy vy wy 30 KAPITEL 2 GRUNDLAGEN F r das Entfernen von Durchdringungen ist folgender Zusammenhang von Bedeutung Ein Netzelement ist g ltig wenn die Jacobi Determinante gr er Null ist 24 Durch Berechnen der Jacobi Determinante kann folglich entschieden werden ob ein Element g ltig oder ung ltig ist F r die Optimierung ist wichtig dass sich der Fl cheninhalt f r Dreiecke s Gleichung 2 13 und f r Tetraeder s Gleichung 2 14 als lineare Funktion darstellen l sst und daher als Zielfunktion eines linearen Programms verwendet werden kann Grundlagen der linearen Programmierung Ein lineares Programm LP in Standardform besteht aus k reellwertigen Variablen x1 k einer Zielfunktion 2 21 und m k linearen Nebenbedingungen F r i 1 und j 1 k seien cj b und n reelle Zahlen Gesucht ist eine Belegung der Variablen so dass die Zielfunktion k j l optimiert wird unter den Nebenbedingungen k njz lt b firi 1 m j l 2 20 fir7 1 k In Matrix Vektor Schreibweise ist ein LP gegeben durch Optimiere 2 c7 x
206. tern in HaGrid3D Die Dateien werden im ASCII Format geschrieben und k nnen so ebenfalls mit einem Texteditor gelesen und bearbeitet werden Die erste Zeile der Datei besteht aus vier Zahlenwerten die die Anzahl der Hexaederzellen in X Y und Z Richtung gefolgt von der Kantenl nge beschreiben In den darauf folgenden Zeilen werden die Knoten mit ihren Koordinaten und Eigenschaften beschrieben Pro Zeile wird ein Knoten gespeichert Hier wer den die Koordinaten des Knotens in X Y und Z Richtung der solid und der interest Status und der Referenzknoten des Objektes hintereinander geschrieben Ein Knoten bekommt den in terest Status 1 wenn er einen Nachbarn innerhalb des Objektes hat selber aber nicht innerhalb des Objektes oder auf dem Rand des Grobgitters liegt Sonst ist der interest Status 0 Es folgen noch die Koordinatenwerte in X Y und Z Richtung und der solid Status des Knotens zum Zeitpunkt seiner Erstellung Dieser beschreibt ob ein Knoten am Rand des Grobgitters liegt solid 3 sich auf der Objektoberfl che befindet solid 2 oder sich innerhalb des Objektes befindet solid 1 Sonst ist der solid Status 0 Beispiel Die erste Zeile der Datei 8 15 T 0 4 beschreibt die Gr e des gesamten Gitters mit acht Hexaederzellen in der X 15 in Y und sieben in der Z Richtung Die einheitliche Kantenl nge der Hexaederzellen betr gt 0 4 Die folgenden drei Zeilen 1 6 3 1 4 370 1 1 6 1 4 3 140 3 0 2L 1 0
207. tion e Innenwinkel engl corner angle e Jacobi Verh ltnis engl jacobian ratio deviation und e Elementinvertierungen und Zelldurchdringungen Alle diese Kriterien sind Funktionen der Elementgeometrie d h sie verkn pfen Punktkoor dinaten Kanten und Fl chen eines Hexaeders zu einem Ma f r die Elementqualit t Die Schwellwerte ab denen Elemente nicht mehr benutzt werden sollten sind stark von der ver wendeten Simulationssoftware abh ngig In einer Implementierung sollte ihre Festlegung also einem erfahrenen Anwender berlassen werden bzw eine variable Einstellm glichkeit f r die Schwellwerte vorhanden sein Im Gegensatz zum zweidimensionalen Fall lassen sich L ngenverh ltnis Parallelabweichung Aus der Unterteilung einer Hexaederzelle entstehen beispielsweise acht neue Hexaeder 24 KAPITEL 2 GRUNDLAGEN und Verzerrung nicht direkt berechnen bzw die direkte Berechnung liefert unzul ssige Verein fachungen F r diese Qualit tsma e wird daher indirekt vorgegangen Alle sechs Seitenfl chen sowie die drei Querschnittsfl chen s Abb 2 7 werden wie Vierecke im Dreidimensionalen behandelt Das Qualit tsma f r das Element ist dann der schlechteste Wert der einzelnen Test fl chen Auch wenn die hier abgebildeten Fl chen planar sind kann von dieser Eigenschaft im Allgemeinen nicht ausgegangen werden Die weiter unten vorgestellten Algorithmen basieren dabei teilweise auf planaren Approximationen welche du
208. tion von besonders effizienten Dreiecks als auch allgemei nen polygonalen Netzen zur Verf gung In der PG wird die Parametrisierung der geladenen 3D Objekte auf der OpenMesh Datenstruktur durchgef hrt 3 7 Blender Blender 4 ist ein freies 3D Modellierungsprogramm mit dem man dreidimensionale K rper modellieren rendern animieren und nachbearbeiten kann Ebenso ist das Erstellen und Ab spielen von interaktiven 3D Inhalten m glich Das Programm ist daf r ausgelegt auf verschie denen Plattformen lauff hig zu sein Blender wurde f r die Erstellung von 3D Testobjekten benutzt s Kap 5 1 3 8 Triangulate Dieses Werkzeug ist die Implementierung einer Triangulierungsmethode von Joseph O Rourke 45 Das Verfahren eignet sich um Polygone zu triangulieren innerhalb des Projekts wird es 3 9 LPSOLVE 45 w hrend der Netzdezimierung angewendet Die Robustheit der Methode ist der Hauptgrund aus dem das Verfahren im Projekt verwendet wird 3 9 Lpsolve Lpsolve 2 ist ein freies Programm zum L sen von linearen Optimierungsproblemen Lpsolve wurde in ANSI C geschrieben und kann auf verschiedenen Plattformen verwendet werden Der L ser kann als Bibliothek in ein Projekt eingebunden werden und von verschiedenen Program miersprachen aufgerufen werden Im Projekt der PG wird der L ser verwendet um Optimie rungsprobleme zu l sen die bei der Verbesserung der Gitternetzqualit t auftreten 3 10 Ce Cg C for graphics 42 ist ei
209. tter beg nstigt Testfall 1 und 3 Testfall 4 und 5 st tzen ebenfalls die anf ngliche The se insbesondere beim Erfassen der Einbuchtung scheitert das schlechte Grobgitter Aus den Resultaten des ersten Testfalls l sst sich folgern dass weitere Unterteilungen zu ung ltigen Gittern f hren w rden da die Qualit tsma e sich in jedem Unterteilungsschritt verschlechtern Dies ist darauf zur ckzuf hren dass in der Implementierung nur kartesische regul re Gitter erzeugt werden was eine Unterteilung ohne Verschlechterung der Winkel und L ngenverh lt nisse f r diese Testgeometrie ausschlie t Die Ergebnisse aus Testfall 2 f hren zu der Schlussfolgerung dass hochaufgel ste Geometrien zu besseren Resultaten bei der Gitterunterteilung f hren vgl Testfall 1 und 2 Dass die Eignung eines Grobgitters letztlich auf Erfahrungswerten des Anwenders beruht wird durch die Resultate der Testf lle 6 und 7 deutlich dass das zu Testbeginn als gut bezeichnete Gitter aus Testfall 6 erzeugt zwar weniger Jacobi Fehler die Winkel und das L ngenverh ltnis nehmen aber erheblich fr her ung nstige Werte an Im Testfall 8 wird deutlich dass Gitter f r komplexe Geometrien zwar prinzipiell aus einem geeignetem Grobgitter erzeugt werden k nnen der Jacobi Fehler in Unterteilungsstufe drei aber macht deutlich dass ohne weitere Ma nahmen eine Gitterunterteilung mit Einhaltung der Qualit tstoleranzen kaum m glich ist Resultate der Gl tt
210. tungsf higkeit moderner Grafikkarten konnte nur im L ser realisiert werden Die zur Gittermanipulation eingesetzten Algorithmen und Methoden erwie sen sich entweder als nicht auf die GPU bertragbar oder die Probleme waren nicht ausreichend gro bzw ausreichend parallelisierbar als dass sich eine Berechnung auf der GPU rentieren w rde Da der L ser auf GPU Basis als Konzeptnachweis engl proof of concept dienen soll werden nur regul re kartesische Gitter unterst tzt die Gitterunterteilungssoftware InGrid3D ist jedoch nicht auf diesen Gittertyp beschr nkt Dank der objektorientierten Entwicklung des Systems ist eine Erweiterung um zus tzliche Gl tter und numerische L sungsverfahren leicht m glich Die Implementierung erfolgte in der Programmiersprache C unter Nutzung von QT OpenGL Cg und weiteren Bibliotheken und Werkzeugen s Kap 3 B 2 2 Produkteinsatz und Produktvoraussetzungen Hardware Die Anforderungen aus dem Pflichtenheft bez glich der zu verwendenden Hardware wurden erf llt So ist sowohl der Gittergenerator HaGrid3D als auch die Gitterunterteilungssoftware InGrid3D auf handels blichen Rechnern einsetzbar es werden aber aktuelle Systeme empfoh len F r den separaten L ser ist eine Grafikkarte der neueren Generation n tig Es werden alle NVIDIA Modelle ab der GeForce 6 Reihe unterst tzt Karten des Herstellers ATI werden zur Zeit noch nicht unterst tzt Wie erwartet wird bei der Gitterunterteilung sehr v
211. tzen Durchdringungen k nnen durch Rand anpassungen oder Gl tten entstehen Intern wird ein passendes lineares Program aufgestellt und mit Hilfe von psolve gel st set lt cPoint comparePoints gt getNodes liefert die Knoten des zu optimierenden Hexaeders vector double x getLocalNeighbors cPoint point cHexa hex liefert die drei Nachbarn eines Knotens in einem Hexaeder vector lt doublex gt buildLP cPointx fPoint stellt Zielfunktion und Nebenbedingungen f r ein lineares Programm auf double getCoords cPoint point liefert die Koordinaten eines Gitterknotens 158 ANHANG C API DOKUMENTATION double detMatrix doublexx matrix berechnet die Determinate einer 3 x 3 Matrix cPoint optimizeLocal vector lt doublex gt objective f Diese Funktion optimiert die Position eines Knotens eines Hexaeders Dazu wird das lineare Program mit dem Werkzeug Ipsolve gel st Der R ckgabewert ist die neue Position des Knotens void optimizeElement optimiert ein Hexaederelement durch aufeinanderfolgendes Aufrufen von optimizeLocal 1 2 Modul Snake Dieses Modul berechnet die lokal k rzeste Verbindungsstrecke s Kap 2 5 auf einer 3D Oberfl chentriangulierung Klasse Snake float getSnakeLength liefert die euklidische L nge der aktuell berechneten Snake zur ck para point bestimme mitte berechnet die Mitte der aktuell berechneten Snake dijkstra berechnet den k rzesten Weg ber Knote
212. uckfeld um das Kugel Modell Sichtbare Artefakte h ngen mit der einfachen Interpolation der Farbwerte zusammen Abbildung 5 16 Druckfeld um das Kugel Modell Bei eingeschalteter verbesserter Interpola tion sind keine Artefakte zu erkennen und das Druckfeld wird gleichm ig dargestellt 76 KAPITEL 5 SYSTEMBESCHREIBUNG Zur Darstellung des Vektorfeldes werden die Vektoren als Linien gezeichnet Sie werden durch ihre L nge sowie durch einen Farbverlauf kenntlich gemacht der wiederum von der L nge abh ngig ist Es handelt sich hierbei um den gleichen Farbverlauf den die Druck Darstellung verwendet s Abb 5 17 Alternativ ist es auch m glich die Vektoren auf gleiche L nge zu ska lieren Dadurch ist ihre L nge nur noch an ihrer Farbe erkennbar aber die bersicht verbessert sich Es kann jeweils nur eine Gitterschicht einzeln dargestellt werden s Abb 5 18 Abbildung 5 17 Druckfeld um das Kugel Modell Bei eingeschalteter verbesserter Interpola tion verschwinden die Artefakte und das Druckfeld wird gleichm ig dargestellt T H FH E E I 5 i EH 1 T l it t 1
213. uf Struktur der Matrizen ausgelegt die sich aus spezi ellen Finite Elemente Diskretisierungen ergibt Die Methoden wurden als Ausgangspunkt zur Implementierung von angepassten Matrix Vektor Operationen auf der GPU verwendet Dies erm glicht es die bereits von der Bibliothek bereitgestellte Implementierung eines L sers f r Gleichungssysteme nach dem CG Verfahren zu nutzen Die Anpassung an die gew hlte Matrix Struktur erfolgte durch Implementierung zweier Shader s Kap 2 6 Der Vertexshader berechnet die Ansichtstransformation und leitet die eingehen den Fragmentkoordinaten weiter Der Fragmentshader berechnet aus diesen Koordinaten die Texturkoordinaten der Nachbarn des jeweils betrachteten Fragments Um zum Beispiel das links vom aktuellen Fragment liegende zu bestimmen m ssen innerhalb der Textur die Koor dinaten des Fragments links vom aktuellen bestimmt werden Hierbei muss beachtet werden dass es notwendig sein kann innerhalb der Textur um eine Zeile nach unten und dort zum ersten Fragment zu springen Dieses gilt analog f r die brigen Nachbarn und wurde durch Verwendung von Modulo Arithmetik realisiert Somit ist die Ausf hrung einer Matrix Vektor Multiplikation m glich s Kap 2 6 3 Zur Berechnung des potential flows wurde ein weiterer Fragmentshader implementiert Als Vertexshader diente der gleiche der auch schon bei der Realisierung der Matrix Vektor Mul tiplikation verwendet wurde Der Fragmentshader berechnet zun chs
214. ung der Objektoberfl che erfordert ebenfalls die Erfahrung seitens des An wenders Die Wahl des Basisnetzes welches durch Vergr berungsschritte erzeugt wird hat Einflu auf die Resultate der Unterteilung Zu starke Vergr berungen haben zur Folge dass teilweise ung ltige Positionen f r die neu entstandenen Randpunkte berechnet werden da die Approximation des urspr nglichen Objektes zu schlecht ist Eine zu schwache Vergr berung wiederum f hrt zu langen Laufzeiten da dann zu h ufig der Snake Algorithmus eingesetzt werden muss Die F higkeit der von der PG erstellten Software ein zur Str mungssimulation geeignetes Re chengitter zu erzeugen basiert also in gewissem Ma e auf den Entscheidungen des Anwenders Bei geschickter Anwendung der von den Programmen nGrid3D und HaGrid3D zur Verf gung gestellten Werkzeugen ist es also m glich ein Hexaedergitter zu erzeugen dessen Gr e nur durch den zur Verf gung stehenden Arbeitsspeicher limitiert wird Mit Hilfe eines solchen Gitters ist es m glich mittels des Finite Differenzen Verfahrens Str mungen um das Objekt zu simulieren In der PG konnte dies durch den implementierten L ser auf der GPU nachgewiesen werden Damit wurde auch das urspr ngliche Ziel der PG die Grafikkarte auch abseits der blichen Verwendungszwecke zu benutzen erreicht Gleichzeitig bewiesen die erfolgreich durchgef hrten Simulationen die prinzipielle Praxistauglichkeit der erstellten Gitter 6 12 Ausblick
215. ungen wird auf Grund seiner Komplexit t in einem eigen st ndigen Kapitel betrachtet 2 3 1 Gitterunterteilung Ausgehend von einem Gitter mit m glichst wenigen Zellen dem so genannten Grobgitter soll durch wiederholtes regul res Unterteilen einer jeden Gitterzelle sukzessive eine bessere Aufl sung bzw Approximation des zu umstr menden Objektes gew hrleistet werden Dazu m ssen die neu entstehenden Gitterzellen gegebenenfalls an die Geometrie angepasst werden ansonsten w rde sich zwar die Anzahl der Gitterzellen erh hen nicht aber die Aufl sung der Geometrie Die Anpassung der Elemente erfolgt durch die Bewegung der neu entstandenen Randpunkte auf die Geometrie dies f hrt dazu dass einige Gitterelemente stark verzerrt werden oder im schlimmsten Falle sogar ung ltige Elemente entstehen Die zur Beurteilung der Qualit t der Gitterzellen notwendigen Kriterien werden im folgenden Kapitel definiert ebenso wird erl u tert an Hand welcher Merkmale eine Gitterzelle als ung ltig zu betrachten ist 2 3 2 Qualit tskriterien Die Qualit t eines Gitters h ngt im Wesentlichen von der Qualit t der einzelnen Hexaederzellen ab und kann durch verschiedene Eigenschaften bestimmt werden Die folgenden Abbildungen und Erl uterungen wurden im Wesentlichen aus den Arbeiten von Kelly 22 und G ddeke 14 bernommen Messbare Kriterien sind beispielsweise e L ngenverh ltnis engl aspect ratio e Winkelabweichung engl angle devia
216. unter Nx lt b x gt 0 wobei x xj cj b bj und N nij f r i 1 m und j 1 k ist Zum Finden der L sung von linearen Programmen wird in der PG das Programm Ipsolve s Kap 3 9 verwendet Lpsolve l st ein lineares Optimierungsproblem in mehreren Phasen So wird in einer Phase eine zul ssige L sung bestimmt und in einer darauf folgenden Phase dar aus eine optimale L sung errechnet F r die unterschiedlichen Phasen werden unterschiedliche Formulierungen des Problems verwendet es gibt ein primales Problem und ein duales Pro blem Sei ein LP in Standardform gegeben max 2 cl x unter Nx lt b x gt 0 Dann gilt f r ein y yo Ym RQ mit y N gt cl folgende Ungleichung cx lt y Nx lt y b f r x y gt 0 Also liefert jeder Vektor y mit yT N gt c eine obere Schranke f r cl x und zwar y b Die beste kleinste obere Schranke die man so konstruieren kann ist durch folgendes LP gegeben min y b unter y N gt cT y gt 0 2 4 ENTFERNEN VON SELBSTDURCHDRINGUNGEN 31 Dieses LP wird duales LP zum obigen primalen LP genannt Sei x eine optimale L sung f r das obige primale LP und sei y eine optimale L sung f r das duale LP dann dienen diese dazu eine Ungleichung wie Nx gt b durch Subtraktion auf der rechten Seite auf Gleichungsform Nx b s zu bringen F r das von Ipsolve angewandte L sungsverfahren ist es stellenweise n tig Ungleichungen auf diese W
217. v a p InaXpe stern v K p w 1 Der Wert ist eine Konstante mit deren Hilfe gewichtet werden kann welchem Ma das Verh ltnis von Fl cheninhalt und Kr mmung zueinander stehen In MAPS wurde A 1 2 2 2 MULTIRESOLUTION ADAPTIVE PARAMETERIZATION OF SURFACES 19 vorgeschlagen Durch Sortieren der Knoten nach berechneter Priorit t erh lt man eine Kom plexit t von O N log N 2 2 4 Projektion und Retriangulierung Um K aus zu erhalten muss nach der Entfernung der unabh ngigen Menge retrianguliert werden Die Eins Ring Nachbarschaft stern k eines entfernten Knotens k wird durch die so genannte konforme also winkeltreue Abbildung z in die Ebene projiziert Hierzu nummeriert man zyklisch alle n Knoten der Eins Ring Nachbarschaft N k km 1 lt lt n so dass km 1 l mit ko kn Wir verwenden eine st ckweise lineare Approximation von z im weiteren Verlauf mit ur bezeichnet Die Abbildung ur ist definiert durch die Werte am Mittelpunkt und am Rand von stern k also 0 und ur Pr Tm exp i6 a wobei m Tm Pr und Om M 4 _ _1 1 mit a 27 0 gilt ist der zum Knoten k assoziierte Punkt Analoges gilt f r die brigen Punkte Das Polygon das nach Projektion der Eins Ring Nachbarschaft von k in der Ebene entsteht wird nach Entfernen des inneren Knotens k neu trianguliert Hierzu wird ein Verfahren wel ches mit dem so genan
218. ven Jacobi Determinaten enth lt Ein Beweis hierf r wurde von Li 31 gef hrt Der grundlegende Ansatz der Entfernung von Durchdringungen bleibt aber auch bei der Anwendung auf Hexaedernetze bestehen Es wird f r jeden Knoten eines ung ltigen Elements das minimale Volumen der Tetraeder die der Knoten mit seinen Nachbarn bildet maximiert 2 5 Aktive Konturen Das urspr ngliche Konzept der aktiven Konturen engl snakes wurde von Kass et al 21 bereits 1988 vorgestellt dabei wurde eine Kontur an Hand von bestimmten Bildinformationen verformt Der Algorithmus wurde auch Snakes genannt da die Bewegung der Konturen der Bewegung von Schlangen hnelte Insbesondere in der medizinischen Bildverarbeitung werden Snakes zur Extraktion von relevanten Bestandteilen Segmentierung aus zwei oder dreidi mensionalen Bilddaten verwendet So k nnen beispielsweise bestimmte Organe in computer tomographischen Aufnahmen hervorgehoben und ihre Eigenschaften n her untersucht werden Anschaulich kann eine aktive Kontur aufgefasst werden als der Prozess um ein gegebenes Ob jekt eine Plastikmembran zu legen und diese dann zu evakuieren engl shrink wrapping Auch der umgekehrte Weg also das Aufbl hen einer Membran innerhalb eines Objektes ist m g lich engl ballons Im Kontext der Randanpassung einer Finite Differenzen Diskretisierung ist das Analogon zur Gummimembran die Menge der Hexaederseitenfl chen die mit ihren vier 2 5 AKTIVE K
219. verschachtelte for Schleifen iteriert werden kann Die Anzahl kann ber die Benutzerober fl che festgelegt werden ebenso die L nge der gleichf rmigen Hexaederkanten Zu jedem Knoten werden intern im Programm seine Koordinaten im Raum der Status der aktuellen Sichtbarkeit die Information ob er zu den interessanten Knoten geh rt und sein aktueller so lid Status gespeichert Falls der Grobgitterknoten auf dem Objektrand liegt wird der Index des entsprechenden Objektknotens ebenfalls gespeichert Zu jedem Grobgitterknoten werden ausserdem die so genannten Default Werte gespeichert Diese werden bei der Initialisierung gesetzt und repr sentieren die urspr nglichen Koordinaten und den solid Status bei der Er stellung des Grobgitters Dies erm glicht ein sp teres Zur cksetzen des Knotens auf seine urspr ngliche Position 58 KAPITEL 5 SYSTEMBESCHREIBUNG Die Hexaederzellen selbst werden ebenfalls in einem dreidimensionalen Feld gespeichert Die Anzahl ist abh ngig von den Grobgitterknoten und muss nicht durch den Benutzer festgelegt werden 5 2 5 Im und Export Alle Knoten des Grobgitters werden in einem dreidimensionalen Feld im Speicher gehalten Beim Speichern und Laden wird das Feld in drei verschachtelten Schleifen durchlaufen und alle Eigenschaften in einer ASCII Datei gespeichert Es ist also m glich die Eigenschaften eines jeden Knotens mit einem Texteditor auszulesen Durch das Exportieren wird eine Schnittstelle zwischen dem
220. ystem 7 ist ein Programm zur Versionsverwaltung von Dateien haupts chlich Softwarequelltexten CVS vereinfacht die Verwaltung von Quelltext und allen anderen textbasierten Dateiformaten dadurch dass es alle Dateien eines Software Projektes an einer zentralen Stelle speichert Dabei k nnen jederzeit einzelne Dateien ver ndert werden es bleiben jedoch alle fr heren Versionen erhalten einsehbar und wiederherstellbar Auch k n nen die Unterschiede zwischen bestimmten Versionen verglichen werden Dank CVS konnte das Projekt trotz gemeinsamer weitverteilter Bearbeitung stets konsistent gehalten werden 3 5 BIFX BIEX 29 ist ein frei verf gbares Textsatzprogramm das speziell auf die Erzeugung von wis senschaftlichen Texten ausgelegt ist Dieser Endbericht wurde mit IATEX gesetzt da man damit die M glichkeit hatte auch dieses gro e Dokument einfach und bersichtlich zu erstellen So konnten die einzelnen Abschnitte in separaten ASCII Dateien gespeichert und Querverweise Abbildungen und Abschnitte komfortabel verwaltet werden In Verbindung mit CVS konnten alle PG Mitglieder gleichzeitig am Endbericht arbeiten 3 6 OpenMesh OpenMesh 51 ist eine Datenstruktur Bibliothek zur Repr sentation polygonaler Netze mit der man Freiform Fl chen im Bereich der geometrischen Modellierung darstellen und verar beiten kann OpenMesh basiert auf einer Halbkantendatenstruktur f r Netze und stellt vordefi nierte Mesh Kernel zur Repr senta

Projektgruppe 471: Beyond Graphics

Contents

Download Pdf Manuals

Related Search

Related Contents