Coding with Balls

March 29, 2015

Slow and inaccurate screenspace voronoi vectorization.

Filed under: Uncategorized — codingwithballs @ 16:56

<@Slummy_> speaking of anti-advisory.. I’ve been doing screenspace voronoi vectorization in 100% asm recently. 😀

<@Slummy_> worst thing is that it’s just for playing around, or “offline precalc” at most, so it could’ve been done in any sane language on a PC

<@Slummy_> but hey, it’s been too long since I did any amigacoding so it seemed like a decent way of playing a bit

<@Raylight-PwL> Slummy_: any tip on algo for that btw? voronoi is da shit you know!

Basically the task is: take a 2D voronoi diagram rendered as pixels and convert each cell to a polygon.

Without going into any detail of how (or why) it was implemented in 68k asm, this is the basic approach. It’ll obviously also work for other 2D graphics with “voronoi-like” characteristics (convex shaps with lots of straight edges) but it’s far from a general purpose vectorizer.

Render your voronoi with a different ID (colour) for each cell.


Identify all the corners / vertices in the image. I do this by scanning through the buffer and comparing each pixel to 3 of its neighbours: (x+1), (y+1) and (x+1, y+1), as well as some special-casing for edges. In the general case a pixel is on a vertex if it has a different colour than at least 2 of its 3 neighbours, and those neighbours are also different.

For each detected vertex store it’s screen space position (x,y) as well as the IDs of the 4 sampled pixels (e.g. the 3 or 4 cells that this vertex is part of)



Then, for each cell in the screen buffer find:

  • All vertices participating in the cell
  • The cell’s bounding box
  • The center of the bounding box


To get a polygon out of this we need to sort the vertices according to winding order. In other words: for each vertex find the angle of the vector from the centre of the bounding box and then sort the vertices according to those.

Finding the angle, either through the magic of basic trigonometry or the glorious path of brute force, is left as an exercise for the reader. 🙂


And voila!


While it’s neither clever nor elegant it worked as intended.


Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Create a free website or blog at

%d bloggers like this: