Playing with Space Partitioning

In this post, I’ll talk about how I came up with the idea for a short project I did over the weekend called Shards:


Inspiration:

A couple of days ago I stumbled upon this great piece of work by user /u/woodrail on the subreddit /r/generative:

What really stood out to me about this piece was how it is structured. There are several main areas which are reflected about each other, and inside of each of those are smaller sub-sections which also contain reflections. It’s a fascinating piece to look at, and I wanted to understand more on how it was made.

In his post, Woodrail links to a github post which talks about the process of creating these pieces of artwork. The basic premise is a particular type of tiling known as the Kisrhombille Tessellation:

The idea behind this is that the tiling can be used, along with a (admittedly complicated) coordinate system to create small shapes that can then be built up like Legos into larger shapes.

The math behind it is still a bit fuzzy to me, so I wasn’t able to write an implementation, but it did get me thinking about this particular type of geometric space partitioning.


Space Partitioning:

I’ve worked a little bit before with other types of space partitioning before, such as voronoi diagrams (pictured below), which split space using a nearest point algorithm.

The trouble with these types of space partitioning algorithms is that they are too predictable. I want something a little bit more organic looking.

So I started thinking about other ways you could divide up space. One approach is to use the “broken glass” model of recursive subdivision, where you take a shape and split it into two shapes by drawing a line randomly through it. Then you repeat this process over and over until you have a lot of small subsections.

In the fractal world, this is one way you can generate shapes line the Sierpinski Triangle or the Pinwheel Fractal:

The trouble with this type of recursive subdivision is that you have to keep track of every new shape that you create, and that involves a lot of bookkeeping and math in figuring out how to split polygons into sub-polygons. I’m too lazy for all of that, I just want a quick solution.


Implementation:

What if, rather than splitting the shapes, I focus on the lines and sort of “grow” them outward from a central source. Each line or “branch” could have a certain chance of splitting and crating two branches. Then whenever a branch collides with another branch, it stops growing.

This isn’t a new idea per-se. Jared Tarbell has a really great implementation of this concept in one of his pieces called Substrate:

Jared uses a slightly different algorithm than mine though. In Substrate, branches can occur anywhere along the length of an existing branch, and again that means a lot of bookkeeping (keeping track of branches and such) that I don’t really want to do.

So for my algorithm I decided that the best approach would be to do everything on a pixel by pixel basis. If your branches can only travel one pixel each step, then you’ll never have any gaps in the branches. This means that each step of the algorithm all you have to do to test for collisions is check to see if the pixel you just moved into has already been turned on.

Similarly, if each split can happen only at the head of a branch, then it doesn’t matter where the rest of the branch is, so you can ignore the bookkeeping for keeping track of lines.

By doing it this way, you don’t have to think about all of the branches anymore, all you have to do is look at the head of each branch, which is more or less just a random walk particle, and the canvas holds all of the information that you need for collisions.

The end result of implementing this algorithm looks something like this:

You can get some really interesting variations by playing around with the parameters, such as how much the “walkers” can change their angle by, how often they split off, and how much they can change their angle by

In the end though, I decided that the straight lines where more aesthetically pleasing.

As a final touch I added a couple of visual effects, I made it so the lines fade over time, and after all of the walkers stop moving or run off of the screen, I fill most of the subsection using a flood-fill algorithm and color them based on a randomly selected color palette from a 60 degree section of the color wheel.

I’m quite pleased with the final effect:

As a bonus, I also wrote a variation of this algorithm which I nicknamed “Frost” which combines the fade effect with brightness threshold for when the walkers will die. The resulting animation is somewhat mesmerizing:

The visual effect of this variation reminds me a lot of a (much more complicated) animation by Felix Woitzel called Traveling Wavefronts

wavefronts.gif


Conclusion and Next Steps:

Overall, I’m pretty happy with how Shards and Frost turned out. If I come back to this project in the future, I would like to add some gradients to the fill process in Shards to give it some more color depth, maybe I could also work on stitching the edges of the particles together in Frost to make something similar to traveling wavefronts.

I didn’t really get a chance to play around with reflections, but I suppose one way I could accomplish that would be to reproduce each particle movement about some reflection line. I’d really like to dig into the the nested geometry of the Kisrhombille Tessellation as well.

Of course, to do that I’ll have to stop being so lazy about the math and start actually keeping track of my polygons and lines. Oh well.

For an easy to implement, light-weight space partitioning algorithm, I think this works quite nicely. I haven’t decided what I’ll use it for yet, but maybe I can generate some textures or landscapes with it.

As always, thanks for reading! If you have any comments or questions, feel free to leave them below.

— Ben

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s