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.

Table of contents

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.

Figure 2: Illustrations of the shape of distance geometries for various site types. Sites are in blue, coordinate axes in black, and the geometry is colored based on the value of the distance function: from low (yellow) to high (red).
2.1: The distance geometry for a point-site is a cone with its tip aligned with the site's position. It has unit slope and its base located at z = negative infinity.
Top view
Side view
2.2: The distance geometry for a segment-site is two-part: the segment itself forms the top of a tent-like shape, while each endpoint is the top of a cone similar to the one at 2.1 - only cut in half.
Top view
Side view (long)
Side view (short)

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!

Figure 3: Rendering two distance geometries for two point sites from above results in a Voronoi plot.
Top view (Voronoi)
Side view

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.

See also

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.