Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Theory of Combinatorial Algorithms
Prof. Emo Welzl and Prof. Bernd Gärtner
Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
Computational Geometry and Computer Graphics
Nina Amenta, University of Texas at Austin
Computational geometry has addressed many of the difficult algorithmic problems raised by computer graphics. Unfortunately, difficult problems often have difficult solutions. While some of our algorithms might not have proved practical, they have contributed important new ideas which have led to interesting and surprising developments in graphics.
We quickly survey two areas currently of great interest in both fields. Voronoi diagrams have always been important in surface reconstruction, and recent algorithms from computational geometry have become an important part of the discourse in graphics. In collision detection, kinetic data structures are providing a new event-driven framework for re-using information which could drastically reduce the amount of work.
Three-dimensional visibility problems inspired a lot of interesting computational geometry in the early 1990's. Pl"uker coordinates gave us a way to consider problems about lines in R3 as problems about points on a curved surface in P5. Using new algorithmic techniques, and new theorems about arrangements, we could give a data structure for ray tracing in sub-linear time and linear space. Unfortunately its performance in practice is not good. But the idea of working in ``linespace'' inspired a radical new approach in graphics. Lightfields are regular samples from the set of lines passing through a volume in R3. An image can be extracted from a lightfield very quickly, since an image is just a set of lines. Lightfields have the potential to provide very high quality images in real-time. New and interesting questions about sampling in linespace are raised by this experimental work.
Back
