Analyse von nicht homogenen Unterteilungsalgorithmen

Unterteilungsalgorithmen sind numerische Methoden, die einen unverzichtbaren Implementie- rungsteil von Computeranimationen und Computerspielen bilden. Es handelt sich um schnelle und eziente Algorithmen zur Erzeugung von 3-dimensionalen Animationsguren, die lebendig aussehen und sich auf naturlicher Art und Weise bewegen. Die Animationsguren werden aus glatten Oberachenteilen und aus wenigen pragnanten Merkmalen, wie z.B. die Gesichtszugen, zusammengesetzt. Das Hauptziel dieses Projekts besteht darin, die spezielle Klasse von Un- terteilungsalgorithmen, die die Oberachen mit gewunschten topologischen, geometrischen und Glattheitseigenschaften erzeugen, zu konstruieren und zu analysieren. Die Herausforderung die- ser mathematischen Aufgabe liegt in der gleichzeitigen Erfullung von topologischen und Glatt- heitsanforderungen. 1

Dieses Projekt beschäftigte sich mit der Frage, wie man mittels eines einfachen Algorithmus, genannt Subdivision schemes, komplexe und zugleich glatte Strukturen erzeugen kann, die man zum Beispiel in der Computergrafik, in der Simulation oder in der Signalverarbeitung benötigt. Subdivision schemes sind eine Art Interpolationsalgorithmus, welcher neue Punkte berechnet indem mittelwerte naher Punkte gebildet werden. Somit werden aus wenigen Anfangspunkten durch wiederholte Verfeinerung Kurven oder Flächen, die immer glatter werden. Neu und besonders herausfordernd sind jedoch anisotrope Verfahren, die in verschiedenen Richtungen unterschiedlich schnell interpolieren. Das ist wichtig da viele Anwendung in der Natur oder in der Technik richtungsabhängig sind. In diesem Projekt konnten erstmals Methoden entwickelt werden die die Glätte solcher anisotropen Verfahren exakt bestimmen. Ein zentrales Werkzeug dafür ist der Joint Spectral Radius (JSR). Hinter diesem kompliziert klingenden Begriff verbirgt sich eine Kennzahl, die beschreibt, wie sich bestimmte Rechenschritte, genauer Produkte von Matrizen, langfristig entwickeln. Anschaulich gesagt: man kann damit messen, wie "ruhig" oder "wild" ein Prozess im Laufe der Zeit wird. Genau diese Größe entscheidet darüber, wie glatt die durch Subdivision entstehenden Kurven und Flächen sind. Bisher war es oft unmöglich, den JSR exakt zu berechnen. Wir haben bestehende Algorithm (Invarianten-Polytope, Baumverfahren) kombiniert und erhielten so einen Algorithmus der in mehr Fällen funktioniert als frühere Verfahren, als auch schneller und robuster ist. Insbesondere konnten wir damit die sogenannte Finiteness Conjecture für alle Paare von 33-Binärmatrizen bewiesen werden - ein offenes Problem in der Mathematik. Die Ergebnisse sind nicht nur von theoretischem Wert. Sie haben direkte Auswirkungen auf die Praxis: In der Computergrafik können komplexe Formen schneller und präziser berechnet werden. In der Signalverarbeitung lassen sich Eigenschaften von Filtern besser vorhersagen. In der Ingenieurwissenschaft können Stabilitätsanalysen verlässlicher durchgeführt werden. Außerdem eröffnen die neuen Methoden Wege, extrem glatte Funktionen mit kleinem "Fußabdruck" zu konstruieren, die sich als Bausteine für hochqualitative Bilddarstellung oder für spezielle mathematische Werkzeuge wie Wavelets eignen. Darüber hinaus wurden praxisnahe Programmiermuster für parallele CPU/GPU-Programmierung sowie Testmethoden für schwer wartbaren Code entwickelt, um die Umsetzung solcher mathematischen Algorithmen zu erleichtern.