Mental Masturbation, Musings, and Methods

The Mind of Alex Beutel

Interactive Voronoi Diagrams with WebGL

August 2nd, 2010 · 13 Comments

Within computational geometry, the Voronoi diagram is a relatively simple concept with a wide-range of applications. ¬†Everything from physics research to the “snap-to” feature in GUI-design uses Voronoi diagrams as a simple underlying data structure to decompose space. I have been working with Voronoi diagrams for the past few months, as my research has focused on interpolation, specifically scalable natural neighbor interpolation. Because the interpolation I have been doing (and the demo I have created) focuses on Voronoi diagrams in a plane, I will only discuss the Voronoi diagrams in 2D space. However, the mathematical concepts can be extended to higher dimensions.
If you already know all about Voronoi diagrams or simply don’t care about the math and just want to play, jump to here or go straight to my Voronoi diagram generator application.

The Voronoi Diagram

I would first like to briefly describe what precisely the Voronoi diagram is, along with how nearest neighbor and natural neighbor interpolation make use of this data structure. The Voronoi diagram is the division of plane into discrete Voronoi cells. Given a set of input points S, we would like to divide the plane such that for any given position in the plane, we know the nearest input point. This is the nearest neighbor problem. A Voronoi cell Vor(p,S) represents the region of the plane for which the given point p is the closest input point from the set of input points S. Mathematically the Voronoi cell Vor(p,S) is defined as

In the Voronoi diagram below, we color each Voronoi cell with a unique color. For the entire region covered by each cell, the input point within the cell is the closest point from the set of input points. You can also easily observe that the boundaries between neighboring cells is the set of points equidistant between two nearby input points.

Interpolation with the Voronoi Diagram

Given this understanding of the Voronoi diagram, we can easily answer a nearest neighbor query. Given a point q at position (x,y) we need only check which Voronoi cell it is within to see which input point is closest to it. Thus, if each input point also has some height z we could roughly interpolate the height of q by taking the height of its nearest neighbor.
A more complex interpolation scheme, known as natural neighbor interpolation, is to take a weighted average of all of the nearby input points. This is done by inserting the query point into the Voronoi diagram and observing how much area the Voronoi cell of the query point steals from the neighboring Voronoi cells in the original Voronoi diagram. Specifically, the fractional weight assigned to each natural neighbor is the area stolen from that nearest neighbor’s original Voronoi cell divided by the total area of the Voronoi cell of the query point. Mathematically this interpolation can be defined as:

While more complicated than nearest neighbor interpolation, natural neighbor interpolation offers a higher quality interpolation and produces smooth results.

Approximating the Voronoi Diagram in OpenGL

As explained briefly in the OpenGL Red Book, we can compute the Voronoi diagram easily in OpenGL by rendering cones at each input point and using the depth buffer to figure out the boundaries between Voronoi cells. Specifically, if we place a right angle cone with the apex at a point, the height of the cone at a given position is equal to the distance form the point in the x,y plane. As such, if we place all the cones in the plane and look at them from below, we will only see the lowest cone at any given point and thus only the cone for which the point it represents is closest. This is known as taking the lower envelope. (For more information, you can read Hoff et. al.’s paper on how this works.)
Therefore, by merely drawing the cones and placing the viewpoint appropriately within OpenGL, the framebuffer will store the Voronoi diagram. Naturally, when doing computations with OpenGL, the diagram will be discretized into pixels. Additionally, OpenGL can not draw cones, only triangles. Therefore, we approximate a cone with a f-sided pyramid. With a reasonably large value for f, we will not notice the effect of the discretization, but making f a small value like 4-10 can be interesting. Both of these discretizations of course create some deviation from the previously defined Voronoi diagram.
I have used this method, implemented in WebGL, the Javascript API to OpenGL, to create the following interactive Voronoi diagram generator.

Enough Math

While math is necessary to precisely describe these concepts, it is not always the best way to convey some of the nuances of the geometric behavior. As a result, one night, both to play with WebGL and to better understand Voronoi diagrams, I implemented some of these concepts in the browser. Below is a short screencast of me playing with the tool, which may be useful if either you don’t have a WebGL-enabled browser or you want to learn some of the features of tool; or just play with it for yourself.

On Code

Not much to say here. To make this small application, I used two canvases overlaid, one with WebGL and one with just the 2D-context. This allowed me to draw over the Voronoi diagram (such as the points). Following the learningwebgl.com tutorials, I used the Sylvester library for Matrix math as well as the glUtils library from the tutorials.
WebGL is still a little buggy and memory management can be an issue, among other things. But overall, it samples a good portion of OpenGL. Unfortunately, getting started can take a little effort. For example, unlike OpenGL in C++, you must write your own shader programs; I suggest using samples from learningwebgl.com at least to get started. However, once you have a functioning WebGL canvas, it is easy to pick up speed. I also went slightly overboard on the movement functions, but it was a good chance to play with Javascript closures.

Some cool Voronoi diagrams

And finally, here are some Voronoi diagrams I have generated that I find interesting, cool, or merely pretty.
Similar kinetic Voronoi diagram but with only 6-sided pyramids used.
Below, the same set of input points are plotted with two different types of cones. The first uses a 50-sided pyramid. The second only uses 6-sided pyramids, creating the jagged effect between neigboring Voronoi cells.
The following two Voronoi diagrams show the Voronoi cells and area stolen for a natural neighbor query.

Tags: Javascript · Mathematics · OpenGL · Programming

13 responses so far ↓

  • 1 Tweets that mention Interactive Voronoi Diagrams with WebGL -- Topsy.com // Aug 2, 2010 at 10:46 am

    [...] This post was mentioned on Twitter by henrikbennetsen, Alex Beutel. Alex Beutel said: new blog post on Interactive Voronoi diagrams with WebGL, blog post: http://bit.ly/9EP3Jt webapp: http://bit.ly/9wXZuJ [...]

  • 2 WebGL around the net, 6 August 2010 | Learning WebGL // Aug 5, 2010 at 6:49 pm

    [...] On the subject of mathematical uses of WebGL, this looks fascinating in a brain-stretching kind of way: Voronoi Diagrams in WebGL. [...]

  • 3 Nicolas // Sep 2, 2010 at 3:32 am

    Wow. Thanks for this awesome article and application. I was only aware of Fortune’s algorithm for creating voronoi tessellations, and I thought that was the best solution (in terms of complexity).

    Do you know what’s the complexity of the algorithm you use?

  • 4 Alex // Sep 7, 2010 at 6:42 pm

    So the simplest answer I can give is, it depends. Fortune’s algorithm is good for points in a plane, but I am not sure how well it expands to higher dimensions. There has been much work attempting to bound the time and space complexity of computing an approximate Voronoi diagram in higher dimensions (look into Arya and Mount’s paper).

    As for my algorithm, it is hard to examine its complexity in the classical sense because of its use of the GPU for much of the computation. In the same way there are I/O efficient algorithms that assume all work done in memory is trivial relative to reading and writing to disk, drawing and data transfer with the GPU has similar effects on the speed of the algorithm. I will link to a paper I just published in a few days with the explanation of the specific bottlenecks in the implementation. Ultimately, the choice of algorithm seems to be highly dependent on your data and your use of the Voronoi diagram, for my research this happened to be performing natural neighbor interpolation.

  • 5 Eric // Sep 10, 2010 at 3:42 pm

    Just to understand. Your method is what I would call an image-based approach – it is dependent on the pixel resolution. Further, it approximates the cones with planar segments. Fortune’s method is a “vector” or purely mathematical approach which is independent of rendering resolution. So you can’t really compare the two methods unless your application is limited to a particular pixel resolution. Is this a fair assessment?

  • 6 Nicolas // Sep 17, 2010 at 3:43 pm

    One useful thing of Fortune’s algorithm is that its output is a set of sites and vertices for each area. The method described here however doesn’t output a set of vertices for each area since this is internally calculated by the GPU (using the depth buffer). So in this case I guess that for example the fast voronoi computation is not suitable as a technique for calculating CVTs for example, since you can’t know a priori the vertices corresponding to the area of each site.

  • 7 Alex // Oct 25, 2010 at 8:20 pm

    Sorry for the late response. It is definitely an image-based approach. As pointed out by Nicolas, Fortune’s algorithm produces a more generic set of output, where as this algorithm could only be used in more narrow cases.

    I just posted my paper on using this method for large-scale grid DEM construction which discusses the errors introduced by the algorithm as well as the benefits of the algorithm – http://alexbeutel.com/papers/acmgis10.nni.pdf

  • 8 wiedee // Nov 2, 2010 at 3:54 am

    I want to build GIS use voronoi diagram.
    what kind of application that I can used for it?

  • 9 Alex // Nov 3, 2010 at 8:29 pm

    As described in the paper linked in my comment above, we extended these basic ideas to build large scale grid DEMs. We did our implementation in C++ with OpenGL and CUDA. We are hoping to release the code in the future.

  • 10 neha // Aug 9, 2011 at 12:18 pm

    The application you developed is awesome! I was working on a research project and wanted an application which takes coordinates as input and outputs a voronoi diagram.

    Can you share your source code? or any other appln that provides this feature…
    Mail me asap!!
    Thanks
    neha

  • 11 Announcing TerraNNI // Nov 9, 2011 at 2:14 pm

    [...] Natural Neighbor Interpolation on a 3D Grid Using a GPU (from ACM GIS 2011) or at my previous blog post about computing Voronoi diagrams on the [...]

  • 12 Alex // Jul 9, 2013 at 10:07 am

    Cool! Turn this into an app where you have to match a given diagram by placing the dots on the screen, and you get more points the less you have to adjust them afterwards, or something like that. Also, there could also be an option to display the diagram in only four colors, because it’s a mathematical thing too, I guess?

  • 13 Dustin // Jan 4, 2014 at 8:08 pm

    great job! – only thing I would add is a “save image button”

Leave a Comment