Freesteel Blog » Voronoi progress

Voronoi progress

Wednesday, October 7th, 2015 at 7:52 pm Written by:

A speculative challenge of machining some leather stamping tools out of brass has led me to do more work on my voronoi experiment hacked as part of my barmesh model.

To make a brass tool requires some area clearing, chamfering and then v-grooving the details.

Like most coders, I do suffer from Not-Invented-Here Syndrome, but at least I did look at OpenVoronoi last year.

I’ve also had a try out of jscut (an in-browser CAM system) which has a V-engrave feature that is not quite right for this application. Nevertheless, the C++ voronoi code underlying this (which I should study at some point) is here and it’s then compiled into Javascript that runs in the browser using Emscripten. Emscripten is a technology that changes everything about where you expect code to be applied.

The stuff I’m doing is quite buggy, but I can at least see a way for it to handle pure arcs in the contours coming in. Most 2D contour voronoi implementations give up once they can do polygons, because it just gets too complicated to be worth it. But this algorithm works by sampling on a regular grid and shouldn’t suffer from complexity that comes in.

The thin cyan lines is the 5-sided polygon with one concave vertex. The yellow lines is the voronoi diagram, and I’ve plotted the nodes of the mesh in different colours depending on its voronoi polygon.

Here is a sparser mesh to show that I am able to subdivide the cells (white line segments) to get to the details. (Something looks wrong at node (2,3).)

Let’s try a more interesting polygon.

One of the fundamental algorithms is the ability to find all the crossing points of the voronoi polygons along a straight line by subdividing. This is easy. Work out the voronoi polygons that the endpoints belong to (ie which edges or vertices are the closest in distance compared to all all the others), find where the line segment cuts the bisector between these two voronoi polygons (if it exists), and this point — when tested — is either in one or other of the polygons (because it’s on the edge) or it shows up in a new third polygon. Repeat for the two halves of the line until no more new polygons show up. This is as good as a mathematical proof.

Here’s what it looks without all the mesh cell lines getting in the way.

Zoomed in to one of the cells to show how I’ve managed to subdivide things up. It’s important to note that I’m not limited to horizontal and vertical subdivisions, as I had in the HSMWorks code (and all previous code I’ve done). I hope this innovation doesn’t catch me out.


Now for some real data of a polygon lifted from the target SVG file. What a mess, because the cells have too many voronoi polygon sides passing through them, so I’m plotting the ambiguous multi connections in cyan.

After 30 iterations it’s beginning to look promising.

More debugging is required, and I only want this to work for one particular example. Then I’ll write my chamfering and v-grooving toolpaths based on that and hopefully make some brass stamps. I’m just so keen to see this as a direct application, rather than get bogged down in the issue of making the most perfect voronoi code that doesn’t have any use to it.

Leave a comment

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <blockquote cite=""> <code> <em> <strong>