Voronoi Camera

The final project in my computer science study at University of Dortmund was a diploma thesis about advanced camera management in 3D computer games. The basic idea was to combine two well known methods in the field of robot navigation: Voronoi Graphs & Potential Fields. The result is a navigation graph which has certain advantages: fast local and global navigation without the problem of local minima and very smooth camera movement. The new graph is easy to reduce, thus it's usable in real time environments demanding only in samll part of available resources of modern PC (<5%). An implementation has been made for the computer game Half-Life.

Creating these graphs for a given scene is a time consuming task. First all walls and obstacles has to be sampled. The result is a point cloud and a voronoi graph is calculated using the Qhull library. The full voronoi graph is much too big for the use in realtime environments, thus it's reduced by removing nodes. This procedure is a bit like mesh reduction, but using complete different cost functions. This process takes for an average Half-Life map up to 2 hours.

The camera management in Half-Life loads these precalculated voronoi graphs for each level and uses them to navigate the camera. The camera movement is controlled by different constraints for distance, angle, visibility, inertia & clearance. The camera management is trying to optimize these constraints for each screen frame. The medial axis property of voronoi graphs is very helpful in this case.

Here some pictures, videos and documents:

The game map datacore.bsp from outside.

The same map as point cloud after the sampling process.

The final Voronoi graph for navigation.

Video showing the Voronoi Camera in action :
Date : 21/03/2003
Size : 20 MB
Type : AVI (DivX 5.03)

Video showing the reduction process :
Date : 21/03/2003
Size : 2.5 MB
Type : MPEG

Complete diploma thesis as PDF (in German) :
Date : 21/03/2003
Size : 3.5 MB
Type : Acrobat PDF

University of Dortmund
Department for Computer Sciences
Computer Graphics Group