HOMEO: Netzoptimierung höherer Ordnung mit Garantien

• Antragsteller: Professor Dr. Marcel Campen
• Fachliche Zuordnung: Bild- und Sprachverarbeitung, Computergraphik und Visualisierung, Human Computer Interaction, Ubiquitous und Wearable Computing
• Förderung: Förderung seit 2021
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 451286978

Das Zerlegen komplexer 2D oder 3D Objekte in einfache Elemente (wie Dreiecke oder Tetraeder) ist ein zentraler Aspekt in Bereichen wie Simulation, Design, Animation und Computergrafik. Auf Netzen solcher Elemente können etwa Funktionsräume definiert werden, auf die Algorithmen rigoros aufsetzen können. Der Bedarf an solchen Netzen hat bereits zu zahlreichen Entwicklungen im Bereich der algorithmischen Netzerzeugung geführt. Die allgemeine Problemstellung lautet: gegeben die Beschreibung des Randes eines Objekts, erzeuge eine qualitativ angemessene Netzrepräsentation des Objektinnern. Der Hauptfokus lag dabei auf linearen Netzen, mit geraden Kanten. Im häufigen Fall, dass ein Objektrand jedoch nicht stückweise gerade oder eben ist, können diese das Objekt nur approximierend beschreiben; das Netz ist nicht randkonform. Präzise Randkonformität ist jedoch ein wichtiger Baustein in anspruchsvollen Anwendungsfällen, z.B. in der numerischen Analysis und der physikalischen Simulation. Eine fehlerfreie Repräsentation wird durch allgemeinere, nichtlineare Elemente ermöglicht. Insbesondere sind polynomielle/rationale Elemente höherer Ordnung in der Lage sich randkonform an gekrümmte Objektränder zu schmiegen. Das Potenzial von Methoden, die auf solche Netze höherer Ordnung aufsetzen, wurde vielfach demonstriert. Aktuelle Entwicklungen haben die verlässliche automatische Erzeugung solcher Netze möglich gemacht, mit Garantien hinsichtlich ihrer Validität. Ein Netz ist valide, wenn es, wie gefordert, randkonform und frei von Defekten wie lokaler Inversion oder Degeneration ist – eine wichtige Voraussetzung, z.B. in der Finite Elemente Methode und verwandten Techniken. Allerdings haben diejenigen Erzeugungsmethoden, die Netz-Validität garantieren, die Eigenheit, im Gegenzug größtenteils die Netz-Qualität zu ignorieren. In anderen Worten: die erzeugten Netze sind prinzipiell zur Nutzung geeignet, erfüllen alle zwingenden Anforderungen, doch zusätzliche Desiderata, die nicht für die bloße Korrektheit von Bedeutung sein mögen, aber relevant für, z.B. Effizienz und Genauigkeit, somit Praktikabilität, werden schlecht bedient. Dieses Projekt zielt ab auf verlässliche Algorithmen zur Erzeugung nichtlinearer Netze die beides sind, valide und von hoher Qualität. Zentral steht der Gedanke, auf die obengenannten garantierenden Methoden aufzubauen, indem ihre Ausgabenetze genutzt werden als valide Ausgangspunkte für systematische Optimierung. In diesem Prozess wird die Qualität verbessert, mittels neuer Strategien und Operatoren zur effizienten und effektiven Ausnutzung sowohl der kontinuierlichen wie auch der diskreten Freiheitsgrade des Problems – während sichergestellt wird, dass die so sorgfältig etablierte Validität beibehalten wird. Mehrere Arten von Qualitätszielen, von Kompaktheit zu Verzerrungsmaßen, werden berücksichtigt. Die Projektergebnisse ermöglichen es somit letztlich, das Potenzial von Methoden, die auf nichtlineare Netze bauen, weiter voranzubringen.

• DFG-Verfahren: Sachbeihilfen