快速Voronoi方法在OpenSCAD中的应用

Summary

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. Fast voronoi is about 12 times faster.

Voronoi times include 0.27 sec of array initializing:

• fastvoronoi() = 1.3 sec
• 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]);

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 nuclei 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 exmample, 100 nucleus points requires 10,000 (100²) intersection operations.

By comparison, this fastvoronoi method requires 8N intersection operations (depending on how points are distributed; some nuclei may require 9 or 10 operations). Therefore, 100 nuclei require only about 800-1000 intersections, less than 10% of the original! Moreover, the execution time increases linearly with the number of points, rather than exponentially. In practice, the execution is a bit slower due to overhead from other operations taking place.

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 cell (except those on the edges and corners) have 8 other cells around it, the nucleus in a given cell is never further than two cells away diagnoally. Typically 8 intersections would be needed to calculate the voronoi cell shape for a given nucleus, and maybe an extra intersection or two for special cases where nuclei are bunched into their grid square corners causing more than 8 nuclei to be within a radius the size of two grid square diagonals.

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 nuclei 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.