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.

voir1

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)

voir2

voir2b

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

voir3

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

voir3b

And voila!

voir4

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

Blog at WordPress.com.