Tree Cellular Automata
Kauri Remm, Aksel Martin Muru, Rasmus Lille
Code repository & runnable releases: https://github.com/murumart/cgiproject
To run the project, download a release from Github and extract the archive and run the executable file. The camera can be moved with WASD/right click/QE, scroll for speed.
Description
Multi state cellular automata in 3d that tries to imitate the growth of a tree.
We have the "leaf", "bark", and "flesh" cell types. Each cell in the 3D grid has values for each of the cell types (in other words, each position in the world has weights for each of the cell types) and the highest value type is displayed on screen using a "renderer". For each pair of cell types we run a matching kernel over the previous generation of cells and populate the new generation according to the values gotten from the kernel (a sum).
Simulation is run on the GPU using compute shader.
You can also chose to Simulated on CPU using GDScript as a proof of concept (using a different thread so that it doesn't stall everything).
We explored different voxel rendering methods for fun and interest. They can be switched in the program at runtime:
- Raytraced renderer - This renderer uses a shader with Amanatides and Woo's fast voxel traversal algrithm. The voxel ray traversal algrithm only checks cell boundries, if the cell is empty, it skips to the next cell boundry. It also uses a compute shader to calculate a brickmap, so it can skip larger space when there are no voxels nearby. The voxels are lit with Blinn-Phong and cast raytraced shadows.
When - Mesher renderer - This renderer creates a mesh (culled on the inside, no greedy meshing) on a different thread. There's a little fade out animation to make the mesh transitions a little less jarring.
- Naive renderer - This renderer manages a bunch of MeshInstances that each are a box. It hides or shows the boxes depending on the cell data. Needs to create boxes when switching to it, very bad on higher grid sizes.
I <3 raytracing
There are several solutions for rendering voxels
- Surface extraction (commonly called meshing) - rendering voxels as faces and merging faces together where you can.
++: fast rendering, more in engine tools. Most popular and lots of material.
--: remeshing is expensive when changing world. voxels->triangles->display
- Raytracing (volume marching) - using a ray to move through the grid using the DDA algorithm.
++: no need to build meshes each simulation frame. voxels->display
--: GPU is designed to render meshes, not rays.
- Lattice mesh method - rendering voxels on slices of planes, only changing the planes textures when changing the world.
++: only grid_size^3*2 triangles, no need to remesh when changing voxels.
--: not very well known, not much material.
Brick map
There are a number of ways of optimizing rendering complexity. One of the easiest methods to achieve better frame times is using a brick map. The concept is to divide the voxel space into bigger bricks, so that one brick holds for example 8^3 voxels. For each brick save if inside that brick are some voxels or not. When rendering, you can at first raytrace in the brick space, when reaching a brick that has voxels, raytrace using smaller steps in the voxel resolution.
Cost of rendering (white is more expensive) grid size is 512^3
| without brick map | with brick map |
 |  |
at grid size 1000 frame times went from 40ms to 6ms
Ball in grid size 1500 changing in real time.
How to cellular automata
Simulate cellular automata via running a compute shader on the GPU. Our growth function is very simple and just adds the results of the kernels together. To manage the data we use the following:
- 2 state buffers(one to read from and one to write to)
- buffer for kernels
- R8 3D image texture which stores the output and is used to render.
All of them are stored in VRAM which reduces data traffic between the GPU and CPU and makes memory operations faster on the GPU. Using a image texture reduced the data size in memory.
The cellular automata is dispatched with extra groups in Z dimension (groupCount * cellTypeCount) to parallelize the main loop more and make it only 4D(3D kernelGrid * cellTypeCount), as the type for which cell we are running the kernels for can be inferred from the invocation Z index.
After the iteration is calculated another shader aggregates the results so less data needs to be moved and writes the resulting cell types into the aforementioned texture.
Trees growing video:
Older illustrations
One of the boards from a design meeting.
One of our first working trees
GIF of the earliest functional tree (running the GDScript algorithm). Sadly with a lower frame rate as the CPU needs to go through a deep nested loop for each iteration of the cells running an interpreted language 😢.
 |  |
Some cool visual glitches