Fast voronoi method for OpenSCAD

Inspired by OpenSCAD Voronoi Generator by Felipe Sanches.

Two .scad files are provided:

• fastvoronoi.scad can be included on its own with no other libraries.
• fastvoronoi_func_bosl2.scad is for use with BOSL2. It provides a functional version of fastvoronoi that returns arrays of vertices, for use with BOSL2 operations such as offset_sweep() for rounding edges. Handling everything in vertex arrays rather than OpenSCAD's native internal objects is significantly slower but useful for fancier effects.

Benchmark results

Testing 400 nuclei. Times are approximate averages from several runs. Fastvoronoi is about 12 times faster.

Voronoi times include 0.27 sec of array initializing:

• fastvoronoi() = 1.3 sec
• original voronoi using offset() instead of minkowski() = ~16 sec
• original voronoi by Felipe Sanches (using minkowski) = ~16 sec

Usage of fastvoronoi.scad

use <fastvoronoi.scad>

// display a fast voronoi pattern with voronoi cells averaging 'cellsize' in
// size, in a rectangle bounded by [xmin,ymin], [xmax,ymax] with
// boundaries of 'thickness' size and 'rcorner' radius between boundaries
random_voronoi(cellsize, [xmin], [xmax], [ymin], [ymax], [thickness], [rcorner], [$fn]);

The random_voronoi() module above does the following, which you can do separately:

// 1. Generate an array of random points compatible with fast voronoi
points = voronoi_array(cellsize, [xmin], [xmax], [ymin], [ymax], [allowable], [seed]);

// 2. display the voronoi pattern
fastvoronoi(points, cellsize, [thickness], [rcorner]);

You can then use linear_extrude() on the output of fastvoronoi() to give the pattern some thickness.

Usage of fastvoronoi_func_bosl2.scad

// must use "include" rather than "use"!
include <fastvoronoi_func_bosl2.scad> // includes standard and rounding BOSL2 libraries 

// 1. Generate an array of random points compatible with fast voronoi
points = voronoi_array(cellsize, [xmin], [xmax], [ymin], [ymax], [allowable], [seed]);

// 2. Generate array of polygon vertices for voronoi pattern
polygon_vertices = fastvoronoi(points, cellsize, [thickness], [rcorner]);

The helper function voronoi_array() (from fastvoronoi.scad) creates an array of random nucleus locations such that each grid cell contains one nucleus, which is necessary for fastvoronoi() to work.

The fastvoronoi() function generates an array of 2D polygon vertices. Each polygon can be rendered individually using linear_extrude() and polygon(), or using the BOSL2 functions like offset_sweep() for making extrusions with rounded edges.

Speed improvements

The original voronoi algorithm requires N² intersection() operations, which is slow. For example, generating 400 voronoi cells requires 160,000 (400²) intersection operations.

By comparison, this fastvoronoi method requires 24N intersection operations per cell (on average). Therefore, 400 nuclei require only about 9,600 intersections, or 6% of the original! Moreover, the execution time increases linearly with the number of points, rather than exponentially.

How does this work?

We generate an array of randomly located nuclei on a grid, such that each grid square contains exactly one nucleus. The nucleus can be anywhere in the grid square (and can be confined further by the allowable parameter). This arrangement still looks random, but guarantees that each voronoi cell is constructed from nuclei no more than two grid squares apart. Therefore, to generate any voronoi cell around a given nucleus, we can ignore any other nuclei more than this distance away.

Because each grid square (except those on the edges and corners) has 8 other squares around it, the nucleus in a given square is never further than two squares away diagonally from any other nucleus. Because two nuclei can be two cells apart, we need no more than 24 intersections to calculate the voronoi cell shape for a given nucleus (the two concentric rings of cells around the nucleus, the inner ring being 8 cells and the next ring being 16 cells).

Changes made

Tweaks to original code by Felipe Sanches:

• Stripped out the minkowski() operation and substituted offset() instead, but that made only a tiny difference in execution speed, likely because minkowski() in 2D on a polygon with few sides is pretty fast.
• Corrected thickness error (boundaries were twice as thick as they should have been). This of course made no difference in speed, it was a bugfix.

Functional improvements:

• The fastvoronoi() module generates a 2D voronoi pattern based on an array of nucleus coordinates provided, like the original version.
• The helper function voronoi_array() creates an array of random nucleus locations such that each grid cell contains one nucleus, which is necessary for fastvoronoi() to work.
• Rewrote the original random_voronoi() wrapper to work with the fastvoronoi() module.