mGroves Home
mGroves Home Coding OpenGL Voronoi Diagrams
Contact Me!
The Computer Graphics class I took at Georgia Tech focused on teaching us fundamental theory and math of computer graphics. We started with ray tracing and continued on to the fixed function pipeline found in recent consumer graphics cards. We also discussed a method for fast computation of 2D voronoi diagrams using graphics hardware.

Given a set of points on a plane, known as voronoi sites, the 2D voronoi diagram consists of zones for each site such that all points within a zone are closer to its voronoi site than to any other voronoi site in the set.

We start by generating a set of voronoi sites on the xy-plane, and position them in 3D space by setting all z-coordinates to the same predefined constant. For each voronoi site we then construct a triangle mesh in the shape of a right circular cone. The apex of the cone is positioned at the voronoi site, pointing towards the viewport. The difference between the z-coordinates of a cones apex, and a given point on the plane containing the voronoi site projected onto the cone along the z-axis approximates the distance from the voronoi site to the given point. When the scene is rendered with an orthogonal projection z-culling will cause the pixels to be colored based on the closest voronoi site.

The program I built would either use an arbitrary coloring scheme or use a coloring scheme based on an imported photo. It would also rotate the points around the center of the window to exhibit the realtime nature of the algorithm.

©2009 Michael Groves