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 *R*^{3} as problems about points on a curved surface in
*P*^{5}. 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 *R*^{3}. 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