On reliable visualization algorithms for real algebraic curves and surfaces

Abstract

In dieser Arbeit werden Visualisierungsverfahren für reelle algebraische Kurven in der Ebene und im Raum, sowie für Einbettungen von Aufblasungen der Ebene entwickelt. Ebene Kurven werden durch einen Kurvenverfolgungsalgorithmus exakt gerastert. Die Effizienz des auf symbolischen und selbstvalidierenden numerischen Methoden basierenden Verfahrens wird durch eine Komplexitätsanalyse sowie durch Experimente belegt. Die Segmente von Raumkurven werden mit Hilfe eines auf Projektion und Lifting beruhenden Ansatzes durch Streckenzüge approximiert. Es wird eine neuartige Methode zum Liften mehrfacher Komponenten der Projektion entwickelt und auf Ihre Effizienz überprüft. Spezielle Einbettungen von Aufblasungen der Ebene werden durch Raycasting ihrer impliziten Form visualisiert. Die Berechnungen von Resultanten bivariater Polynome, die in den obigen Verfahren vorkommen, werden durch die Implementierung eines parallelen Algorithmus auf Grafikkarten beschleunigt.

This work presents algorithms for visualizing real algebraic plane and space curves as well as a certain type of algebraic surface given by embedding blowups of the plane into affine space. An exact curve tracing based rasterization method for real algebraic plane curves is proposed. The efficiency of the new method, which combines symbolic and certified numerical methods, is illustrated by means of complexity analysis and practical experiments. The segments of real algebraic space curves are approximated by line strips using a projection and lifting approach. A novel efficient method for lifting multiple components of the projection is developed and tested. Certain embeddings of blowups of the plane are visualized using real time ray casting of their implicit form. The computation of bivariate polynomial resultants incorporated in the above algorithms is sped up by implementing a parallel resultant algorithm on graphics processing units.