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 :
vorocamera.avi
Date : 21/03/2003
Size : 20 MB
Type : AVI (DivX 5.03)
Video showing the reduction process :
vororeduce.mpg
Date : 21/03/2003
Size : 2.5 MB
Type : MPEG
Complete diploma thesis as PDF (in German) :
voronoicamera.pdf
Date : 21/03/2003
Size : 3.5 MB
Type : Acrobat PDF
University of Dortmund
Department for Computer Sciences
Computer Graphics Group
http://ls7-www.cs.uni-dortmund.de