Mesh-Generierung: Fortschritte und Anwendungen bei der Computer Vision Mesh Generation

Von Fouad Sabry

Was ist Netzgenerierung?

Bei der Netzgenerierung handelt es sich um die Praxis, ein Netz zu erstellen, eine Unterteilung eines kontinuierlichen geometrischen Raums in diskrete geometrische und topologische Zellen. Oft bilden diese Zellen ein Simplizialkomplex. Normalerweise unterteilen die Zellen den geometrischen Eingabebereich. Netzzellen werden als diskrete lokale Näherungen des größeren Bereichs verwendet. Netze werden durch Computeralgorithmen erstellt, oft unter menschlicher Anleitung über eine GUI, abhängig von der Komplexität der Domäne und dem gewünschten Netztyp. Ein typisches Ziel besteht darin, ein Netz zu erstellen, das die Geometrie der Eingabedomäne genau erfasst, mit hoher Qualität ( (gut geformte) Zellen und ohne so viele Zellen, dass nachfolgende Berechnungen schwierig wären. Das Netz sollte auch in Bereichen fein sein, die für die nachfolgenden Berechnungen wichtig sind.

Ihr Nutzen

(I) Einblicke und Validierungen zu den folgenden Themen:

Kapitel 1: Netzgenerierung

Kapitel 2: Finite-Elemente-Methode

Kapitel 3: Partielle Differentialgleichung

Kapitel 4: Computergestützte Fluiddynamik

Kapitel 5: Numerische Methoden für partielle Differentialgleichungen

Kapitel 6: Elliptische partielle Differentialgleichung

Kapitel 7: Finite-Differenzen-Methode

Kapitel 8: Numerische Fortsetzung

Kapitel 9: Finite-Volumen-Methode

Kapitel 10: Isogeometrische Analyse

(II) Beantwortung der häufigsten öffentlichen Fragen zur Netzgenerierung.

(III) Beispiele aus der Praxis für den Einsatz der Netzgenerierung in vielen Bereichen.

An wen sich dieses Buch richtet

Profis, Studenten und Doktoranden, Enthusiasten, Hobbyisten und diejenigen, die über grundlegende Kenntnisse oder Informationen für jede Art von Mesh-Generierung hinausgehen möchten.

 

 

• Sprache: Deutsch
• Herausgeber: Eine Milliarde Sachkundig [German]
• Erscheinungsdatum: 4. Mai 2024

Buchvorschau

Kapitel 1: Mesh-Generierung

Bei der Netzgenerierung wird ein kontinuierlicher geometrischer Raum in verschiedene geometrische und topologische Zellen unterteilt, um ein Netz zu bilden. Oft wird von diesen Zellen ein simplizialer Komplex gebildet. In der Regel teilen die Zellen die geometrische Eingabedomäne. Als diskrete lokale Näherungen des breiteren Bereichs werden Netzzellen verwendet. Abhängig von der Komplexität der Domäne und der Art des gesuchten Netzes werden Netze von Computeralgorithmen generiert, häufig mit menschlicher Unterstützung über eine grafische Benutzeroberfläche. Ein gemeinsames Ziel besteht darin, ein Netz zu erstellen, das die Geometrie der Eingabedomäne genau darstellt, qualitativ hochwertige (wohlgeformte) Zellen aufweist und nicht zu dicht ist, so dass Berechnungen in der Zukunft unüberschaubar werden. Darüber hinaus muss das Netz in Bereichen, die für die folgenden Berechnungen entscheidend sind, fein sein (kleine Komponenten enthalten).

Netze werden für physikalische Simulationen in Programmen wie Computational Fluid Dynamics und Rendering auf einem Computerbildschirm verwendet. Netze bestehen aus Grundbausteinen wie Dreiecken, weil wir zum Beispiel Finite-Elemente-Berechnungen (für das Ingenieurwesen) oder Raytracing (für Computergrafiken) für Dreiecke durchführen können, aber nicht für komplexere Formen und Orte, wie eine Brücke über eine Straße. Indem wir Berechnungen für jedes Dreieck durchführen und herausfinden, wie die Wechselwirkungen zwischen den Dreiecken interagieren, können wir die Stärke der Brücke modellieren oder auf einem Computerbildschirm darstellen.

Der Unterschied zwischen organisierter und unstrukturierter Vernetzung ist signifikant. Ein regelmäßiges Gitter, z. B. ein Array, wird bei der strukturierten Vernetzung mit abgeleiteter Verbundenheit zwischen den Elementen verwendet. Unstrukturierte Vernetzung ermöglicht die Erfassung komplexerer Domänen und die Möglichkeit unregelmäßiger Verbindungsmuster zwischen Teilen. Das Hauptthema dieser Seite sind unstrukturierte Netze. Während ein Netz trianguliert werden kann, unterscheidet sich die Vernetzung von der Punktsatztriangulation dadurch, dass sie das Hinzufügen von Scheitelpunkten ermöglicht, die nicht in der Eingabe enthalten waren. Die gleiche Freiheit zum Hinzufügen von Scheitelpunkten besteht beim Facettieren (Triangeln) von CAD-Modellen für das Zeichnen, aber das Ziel besteht darin, die Form mit der geringstmöglichen Anzahl von Dreiecken genau darzustellen. Die Form der einzelnen Dreiecke spielt dabei keine Rolle. Meshes werden anstelle von Texturen für die Darstellung realistischer Lichtsituationen in Computergrafiken verwendet.

Viele Netzerzeugungsprogramme sind mit CAD-Systemen verbunden, die ihre Eingabe definieren, und mit Simulationsprogrammen, die ihre Ausgabe empfangen. Die Eingabe kann viele verschiedene Formen annehmen, aber typische sind Punktwolken, Volumenmodellierung, geometrische Modellierung, NURBS und B-rep.

Die Begriffe Netzerzeugung, Rastererzeugung, Vernetzung und Rasterung werden häufig synonym verwendet, aber technisch gesehen decken die beiden letzteren die Netzverbesserung ab, d. h. den Prozess der Änderung des Netzes, um die Genauigkeit der numerischen Berechnungen, die darüber ausgeführt werden, zu beschleunigen oder zu verbessern. Gelegentlich wird ein Netz sowohl in der Mathematik als auch im Computergrafik-Rendering als Mosaik bezeichnet.

Abhängig von ihrer Bemaßung und dem Kontext, in dem das Netz verwendet wird, haben Netzflächen (Zellen, Elemente) mehrere Namen. Die höchstdimensionalen Netzelemente in finiten Elementen werden als Elemente bezeichnet, während Kanten 1D und Knoten 0D sind. Die 2D-Elemente sind Flächen, wenn es sich um 3D-Elemente handelt. Scheitelpunkte sind die 0D-Punkte in der Computergeometrie. Tetraeder werden manchmal als Tets bezeichnet, während Dreiecke, Vierecke und Hexaeder (topologische Würfel) als Tris, Quads bzw. Hexen bezeichnet werden.

Viele Regeln zum Hinzufügen von Scheitelpunkten, wie z. B. die Ruppert-Methode und die Delaunay-Triangulation, bilden die Grundlage für verschiedene Vernetzungsansätze. Ein einzigartiges Merkmal ist die Hinzufügung von Scheitelpunkten und Dreiecken, nachdem ein grobes Anfangsnetz des gesamten Raums erstellt wurde. Im Vergleich dazu führen fortschrittliche Front-Algorithmen Elemente inkrementell in das Innere des Bereichs ein, beginnend mit der Grenze. Hybride Methoden kombinieren beides. Dünne Grenzschichten von Elementen für die Strömung von Flüssigkeiten werden mit einer einzigartigen Klasse von vorgeschobenen Frontverfahren erzeugt. Das vollständige Netz, das durch die Generierung strukturierter Netze erstellt wird, ist ein Gitterdiagramm, z. B. ein regelmäßiges Raster von Quadraten. Die Domäne wird in große Unterbereiche unterteilt, von denen jeder ein strukturiertes Netz ist, in blockstrukturierter Vernetzung. Einige direkte Ansätze beginnen mit einem Netz, das blockstrukturiert ist, und passen es dann an die Eingabe an. Weitere Informationen finden Sie unter Automatische Hexadezimalnetz-Generierung auf Basis von Polycube. Schneiden Sie die organisierten Zellen an der Domänengrenze als zusätzlichen direkten Weg ab. siehe Marching cube sculpture.

Einige Netztypen sind wesentlich schwieriger zu erstellen als andere. Im Vergleich zu kubischen Netzen sind simpliziale Netze in der Regel einfacher. Die Erzeugung eines Hex-Netzes, das einem festen Vierfach-Oberflächennetz entspricht, ist eine entscheidende Kategorie, und die Erforschung der Existenz und Erzeugung von Netzen mit bestimmten winzigen Konfigurationen, wie dem tetragonalen Trapezoheder, ist ein Forschungsteilgebiet. Die Existenz kombinatorischer Sechskantnetze wurde aufgrund der Schwierigkeiten dieses Themas getrennt von der Frage der Herstellung qualitativ hochwertiger geometrischer Realisierungen untersucht. Obwohl bekannte Algorithmen simpliziale Netze mit einer minimalen Qualitätsgarantie erzeugen, haben nur wenige kubische Netze die gleichen Sicherheiten, und viele weit verbreitete Implementierungen erzeugen invertierte (Inside-Out-) Hexadezimale aus einigen Eingaben.

Auch wenn die anschließenden Berechnungen über das Mesh parallel auf Supercomputern durchgeführt werden, werden Meshes häufig seriell auf Workstations erzeugt. Dies ist auf den Nachteil zurückzuführen, dass die meisten Netzgeneratoren interaktiv sind, sowie auf die Tatsache, dass die Dauer der Netzgenerierung im Vergleich zur Solver-Zeit oft vernachlässigbar ist. Die Vernetzung erfolgt jedoch parallel, wenn das Netz zu groß ist, um in den Speicher eines einzelnen seriellen Prozessors zu passen, oder wenn es während der Simulation modifiziert (angepasst) werden muss.

Die mathematische Interpolationsfunktion dient als Grundlage für den in der Algebra verwendeten Gittererzeugungsprozess.

Nutzung bekannter Funktionalitäten in einem, Verwendung von Abschnitten verschiedener Formen in zwei oder drei Dimensionen.

Es ist möglich, dass die Rechendomäne nicht quadratisch ist, aber um die Dinge einfach zu halten, wird angenommen, dass die Domäne rechteckig ist.

Der Hauptvorteil der Ansätze besteht darin, dass sie die Form und den Abstand des physischen Gitters explizit regeln.

Die Normalisierungstransformation ist die einfachste Methode, die verwendet werden kann, um ein Berechnungsnetz zu erstellen, das an eine Begrenzung angepasst wird. Um eine Düse zu verwenden, kann mit der Beschreibungsfunktion y=x^{2} das Gitter einfach durch gleichmäßige Teilung in y-Richtung mit gleichmäßig verteilten Inkrementen in x-Richtung  erzeugt werden.

\xi =x\,\eta ={\frac {y}{y_{\max }}}\,

wobei y_{\max } die y-Koordinate der Düsenwand bezeichnet.

Für gegebene Werte von ( \xi , \eta ) können die Werte von ( x , y ) leicht wiederhergestellt werden.

Gittererzeugungstechniken, die auf Differentialgleichungen basieren, ähneln denen, die in der Mathematik verwendet werden. Der Vorteil der Verwendung partieller Differentialgleichungen (PDEs) besteht darin, dass das Netz erzeugt werden kann, indem die Lösung der gittererzeugenden Gleichungen ausgenutzt wird. Alle drei Arten von partiellen Differentialgleichungen können verwendet werden, um Gitter zu erstellen.

Die Lösungen elliptischer PDEs sind in der Regel sehr glatt, was zu glatten Konturen führt.

Maximierung der Glätte als Vorteil Die Jacobi-Funktion erwies sich als positiv als Ergebnis des Maximumprinzips für harmonische Funktionen, daher ist es vorzuziehen, die Laplace-Gleichungen zu verwenden.

Nach umfangreichen Arbeiten an elliptischen PDEs zur Erzeugung von Gittern wurden von Crowley (1962) und Winslow (1966) durchgeführt.

Bei Generatoren mit einem Poisson-Gitter erfolgt die Abbildung durch Markieren der gewünschten Gitterpunkte (x,y) an der Grenze des physikalischen Bereichs, wobei die innere Punktverteilung durch Lösen der folgenden Gleichungen bestimmt wird

\xi _{{xx}}+\xi _{{yy}}=P(\xi ,\eta )\eta _{{xx}}+\eta _{{yy}}=Q(\xi ,\eta )

wobei (\xi,\eta) die Koordinaten im Rechenbereich sind, während P und Q den Punktabstand innerhalb von D steuern.

Ändert man die oben genannten Gleichungen im Rechenraum, so erhält man ein Paar elliptischer PDEs der folgenden Form:

\alpha x_{{\xi \xi }}-2\beta x_{{\xi \eta }}+\gamma x_{{\eta \eta }}=-I^{2}(Px_{\xi }+Qx_{\eta })\alpha y_{{\xi \xi }}-2\beta y_{{\xi \eta }}+\gamma y_{{\eta \eta }}=-I^{2}(Py_{\xi }+Qy_{\eta })

wo

{\displaystyle {\begin{aligned}\alpha &=x_{\eta }^{2}+y_{\eta }^{2}\\\beta &=x_{\eta }x_{\xi }+y_{\xi }y_{\eta }\\\gamma &=x_{\xi }^{2}+y_{\xi }^{2}\\I&={\frac {\delta (x,y)}{\delta (\xi ,\eta )}}=y_{\eta }x_{\xi }-y_{\xi }x_{\eta }\end{aligned}}}

Diese Gleichungssysteme werden in der Rechenebene auf einem gleichmäßig verteilten Gitter gelöst, das uns die (x,y) Koordinaten jedes Punktes im physikalischen Raum liefert.

Die Verwendung elliptischer PDEs hat den Vorteil, dass die ihnen zugeordnete