Rounded cell painter

 from Red Blob Games
21 Jun 2018, then 14 July 2019, then 15 Oct 2019

I was intrigued by this question on stackoverflow[1] about creating blobby-looking regions based on points. I thought it might work well with the cellular structure I’ve been playing with[2]. (I’m actually working on a tutorial on this topic right now, so this question was right up my alley.) These cells are related to Voronoi, but look much rounder. Voronoi uses the circumcenter of the Delaunay triangles. These cells use the centroid instead.

Click and drag to change the color of a region. (Mouse tracking isn’t exact for this demo, sorry)

Chaikin’s Algorithm#

For the curves, the idea is to start with a convex polygon and change the sharp corners to curves. First find the midpoints of each edge. Then for each segment between the midpoints build a quadratic bezier curve using the original corner as the control point. This is called Chaikin’s Algorithm[3]:

In my problem, I don’t want to turn every section into a curve. I only want the curves in some situations. I draw one wedge at a time from the polygon on the left (marked with ), and consider these four cases:


Compare the owners of the neighboring two regions with the current region (owned by A):

I think this curve drawing logic is a little more convoluted than it should be, and I haven’t tested all the cases. I’m not sure what the best thing to do is when there are three different owners meeting at a point. I used a different rule for the demo at the top of the page — I leave a curved gap. On this project I made the curved borders thick enough that they covered the gap. Oskar Stalberg (Bad North) recommends focusing the logic on the triangles formed around each vertex. That triangle can be owned by one of the three neighboring polygons.

Cool: Chaikin’s son has an interactive post about Chaikin’s curve algorithm[4]. Also see Ortho-tiles[5].

Source is in rounded-cell-painter.js but it’s relying on my dual mesh library to calculate the cells, so it’s probably not directly useful.

Email me , or tweet @redblobgames, or comment: