VORONOI ON THE GPU

Voronoi diagrams are a fundamental concept in computational geometry, and have their place in countless applications. Therefore, being able to compute them quickly and robustly is important. Improvements in computation performance come in two flavors: theoretical and practical.

In this project we focus on the practical aspect. Instead of implementing an algorithm (such as Fortune's) for the CPU, we exploit the massive parallel-processing power of the GPU to plot complex Voronoi diagrams blazingly fast.

The method used is an implementation of the ideas presented in this paper by Hoff et al. Which describes how to represent diagram sites as meshes, such that when rendered result in a Voronoi plot.

What are Voronoi diagrams?

General definition

A Voronoi diagram is a partition of space into regions - also called cells. The partition is with respect to a set of sites, where a site is a subset of points in space. The relation between a cell and the set of sites is this: All points in a cell are closer to one particular site more than to any other in the set. The distance between two points in space is supplied by means of a distance function.

Common case

One of the simpler cases of Voronoi diagrams (and the one we target in this project) is that where the space is the two-dimensional Euclidean plane. Sites are often defined to be points, line segments, polygons, or curves. The distance function usually used is the Euclidean distance, though alternatives are available depending on the application.

Figure 1 (interactive): A simple Voronoi diagram for point-sites in the plane. Each cell corresponds to the subset of the plane bearing the shortest distance to a distinct site. Tap to generate a new random arrangement.

Method

Distance geometries

We will now show how so-called distance meshes can be used in order to plot a Voronoi diagram, which is what enables us to bypass the drawback of sequential and/or incremental approaches and exploit the parallel-processing powers of the GPU.

First of all, let's introduce the concept of distance geometries: Imagine the Euclidean plane our sites lie in is the xy-plane in three-dimensional space. We have $$n$$ sites given:

$$S := (s_0, s_1, \ldots s_n)$$

A distance geometry $$DG(s)$$ for a site $$s_i$$ is the result of mapping each two-dimensional position $$(x, y)$$ on the xy-plane to the three-dimensional one at $$(x, y, -D((x, y), s_i))$$, where $$D(p, s)$$ is the Euclidean distance function between a point and a site. More formally:

$$DG(s) := \{(x, y, -D((x, y), s)) \vert x \in \mathbb{R}, y \in \mathbb{R}\}$$

To facilitate an understanding of this concept, please refer to the figure below for schematics of the shapes of distance geometries for point- and segment-sites.

Rendering the scene

Now, for the key part: Attach distance geometries to each site, and assign a distinct color to each site's geometry. Next, render the scene with orthogonal projection from above. Observe that the color at each point in the resulting image will correspond to that of the geometry with the highest z-value at that position in the scene. This is equivalent to the color of the nearest site!

There you have it. The resulting rendering is a Voronoi plot, where each pixel's color corresponds to the color assigned to the nearest site!

Implementation

From geometry to mesh

It's time to make the transition from geometries to meshes: We cannot instruct the GPU to render an infinite cone, but what we can do is instruct it to render triangles arranged in the shape of a cone.

Converting our distance geometry descriptions to triangle meshes is rather simple, but there are two dangers we need to be mindful of: precision and size.

Mesh precision

A cone made of four triangles is vastly different than that made of a few dozen. The amount of triangles we use when arranging distance meshes reflects how well they approximate the geometries they are modeled after. The more triangles, the closer our Voronoi diagram will approximate its true form. However, use too many triangles and performance will suffer (for diagrams with many sites). The key is to strike a fine balance between the level of detail desired and the complexity of the diagram.

Mesh size

Another concern is the size of our meshes. That is, how far should we extend them? The answer is: the minimum distance so that they are still visible in our rendering's viewport. Imagine our diagram contains a single point site at its center. The correct rendering for such a diagram is simpley the viewport filled uniformally with the site's color. However, if we extend the geometry too little, our rendering will consist of a circle in the middle, and the default background color anywhere else.

Source code

You can view the source code and documentation on GitHub.

References

1. Hoff III, Kenneth E., et al. "Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware". Proceedings of the 26th annual conference on Computer graphics and interactive techniques. ACM Press/Addison-Wesley Publishing Co., 1999.