Voxel Automata Terrain

Voxel Automata Terrain

Brent Werness aka @R4_Unit tweeted about an algorithm he calls “Voxel Automata Terrain” that creates interesting 3D structures. He also provides some processing source code I was able to translate so I had to have a go at creating some of these myself.

Voxel Automata Terrain

These structures are created using a process similar to the diamond-square algorithm but in 3D. A 3D cube is repeatedly iterated and divided to leave these structures behind. I don’t really understand it beyond that so I cannot give a better explanation at this time.

Voxel Automata Terrain

The code for dividing the cube up is the first parts of Brent’s code. Mostly everything after the evaledges routine is display related.

Voxel Automata Terrain

For my images I use the states array to render solid cubes using the Mitsuba renderer. State 1 and state 2 cells can be shown or hidden and displayed using different colors.

Voxel Automata Terrain

I also setup a flickr gallery with more example images.

Voxel Automata Terrain

Voxel Automata Terrain

If you start the process without a random side and fill the initial base side with all state 1 or state 2 cells you get symmetric structures as a result.

Voxel Automata Terrain

Voxel Automata Terrain

Voxel Automata Terrain

I also tried extending the maximum possible cell states to 4. The rule arrays need to be changed to three dimensional. From some initial quick searches (a few hundred of the possible 4 billion rules) did not lead to any new unique structures, but it does add another color to the mix.

Voxel Automata Terrain

Voxel Automata Terrain

Voxel Automata Terrain

Here is a movie showing some samples with ncreasing levels of detail/recursion.

Voxel Automata Terrain are now available as part of the latest version of Visions of Chaos.

I have also added the option to export the Voxel Automata Terrain cube grids as OBJ files that can be imported into other 3D modelling programs.

Jason.

11 responses to “Voxel Automata Terrain

  1. I am really curious about how some of these were made – I am getting more noise than orderly shapes when I use the 3d CA terrain setup – also is there a way to remove the limit of size – I see you have several that are larger than 10×10. I am a really big fan of this software – I had heard of it before but thought for some reason that it was not free, found out recently that it was so I started using it this week.

    • To get the more orderly like results I did, you start from only one side (bottom edge) of the starting grid activated before you start the automata steps.

      For sizes larger than 10x10x10 you just expand the possible dimensions of the 3D arrays. If L is the division steps, then the grid dimension maximum size is calculated by (1 shl L)+1.

      Visions of Chaos used to be commercial, but I have since changed it back to freeware.

      • Is there a command line/scripting interface? I guess I’m just using the gui – there are some things you can change to get different results, but I guess it will take more experimentation to find out. When you say start with one side filled, you mean the options where it’s like ‘random, all state 1, all state 2’? The option I see for size is labeled universe size, is that the L you are talking about? – Really sorry for all the questions but what operation does ‘shl’ refer to when you say ‘(1 shl L)+1’?

      • There is no command line to my implementation. Not sure about the original version. It has been a while since I converted his code.

        Yes, in my options dialog “Universe size” is the L. SHL is binary shift left. Every programming language out there should support or implement it.

        I was a bit unclear with the starting pattern. The options are how the bottom edge of the 3D array is filled. Random is just random values that gives the more random looking structures (like the original). Setting all the base cells to either 1 or 2 gives the more symmetric structures.

      • Ok, that makes more sense. So basically the edge length is going to be (1*2^L)+1. So it seems to me that each horizontal layer is the previous layer with the rule applied to it again, right? Don’t want to be annoying, but I’ve been having a lot of fun messing around with this and the free version of renderman for the pathtracing renderer – thanks for all the work you put into this software, I’m really getting a lot out of it. I am really curious about the sharp geometric structures, and the ones with flat faces and thin lines – are these just particular rules that behave really orderly or are they edited after the fact?

      • The grid is not layers of steps. The grid is updated by subdividing the grid into smaller and smaller cubes and applying the cellular automata rule to smaller cube(s) within the main grid.

        No post edits. All of my example grids/images (and sample files in Visions of Chaos) are all direct output from the algorithm without changes or edits.

      • That’s interesting – so it considers the 26 neighbors for each cell. How are the rules formed? I assume it’s a bit pattern to represent the birth/survival rules but you have it entered in the as a decimal number. How many iterations take place before the final output is computed? I just this morning found the example config files, so I’m going to be messing around with those here tonight probably, I’ve got a really busy day today.

      • The way the grid is constructed does not use the 26 neighbors like a usual 3D CA. Actually the voxel automata terrain really is not like a CA at all (other than a grid of cells). The grid is subdivided into smaller cubes and the corners of each smaller cube are used to determine the state of each cell. This process only happens once and the structure is done. There are no repeated steps to evolve the grid further.

        The original author describes the process as “The basic idea is that you pretend you’ve drawn a certain level of detail of the image into a grid of voxels and you are now wondering how to make a twice as detailed image. You do so with a collection of rules. First, you have a rule for how to fill in the center of a cube when you know all the corners, second you have a rule for filling in all the faces when you know the corners and centers, and then finally you have a rule for filling in the edges when you know everything you’ve filled in so far. In this way, you can go from a voxel grid to one twice the size. Repeating this many times gives you a large detailed voxel grid.”

        If you are a coder, maybe looking at the code can help? https://bitbucket.org/BWerness/voxel-automata-terrain/ Or maybe it will only confuse you more. I don’t think I really grasped what is happening. The results are nice though.

        I try and include samples for all the modes on Visions of Chaos.

      • Damn, I just got a chance to look through the examples they provided in that repository – that is some beautiful stuff. I didn’t get much out of the code, but I may take a closer look at it at some point. The way that the orthogonal ones are rendered reminds me of a project I did one time, I actually used one of the outputs as a gravatar thing so it shows up next to my username on a lot of sites (the one that shows up here). Basically that was a 2 dimensional rendering of a diamond square scheme that computed the 2d array of heights and then drew a column of pixels up, that many pixels then moved up and to the right one pixel to start drawing the next one, till it hit the end of that row and then it would move back to just below and to the right of the first pixel that got drawn. It ended up with this isometric look to it, but it didn’t go much further than just rendering the output of the diamond square algorithm. That was a few years back, but I have to say, I’ve been fascinated with voxels since before I even knew what to call the concept. It really kind of ticked me off when minecraft and things like that got popular and people thought that was the only way to express voxels, when in reality the volumetric grid idea has a much cooler application when the voxels are close to pixel size. Looking through some of the examples that were in that repository, I got the idea that pieces of the outputs could be taken and put together, to make things like volumetric pixel art – using some of the shapes that resulted as decorative edges for roofs or things like that, since you could take out a subset of the 3d array and copy it or just keep the features within it that you wanted. I am really glad I live in a time where it is possible for this kind of thing to be realized in nearly real time, I hope to see this kind of thing applied to graphics more in the future. I know they were outdone by polygons in the 90s just due to performance/memory concerns, but what a world it would be if graphics like what they used in Hexplore and Command and Conquer Tiberian Sun had caught on and become more the norm. 3 dimensional sprites seems like a really promising idea to me, and I hope I see more things done with volumetric rendering in my lifetime.

      • Hate to bother you, but I was just wondering how the palette is applied when you choose palette 2 – the palette 1 obviously radiates out from the center but I can’t really tell for the other one – it seems at least partially based upon states, but I just wanted to see if you could tell me.

      • Palette 2 colors each cell by taking the average state value of the surrounding cells (27 cells total) and then maps that average to the current 256 color palette.

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