A long overdue and much requested feature in Visions of Chaos has been better support for multi core CPUs. Watching Visions of Chaos churn away calculating a long series of frames for a movie and only seeing one of your CPU cores in use can be frustrating.
Converting single threaded code into multi-threaded capable code is not exactly easy (depending on the algorithm some code is easier than others) but I have started converting some of the easier modes into multi-thread capable code.
Smoothed Particle Hydrodynamics (SPH) was one of the modes in Visions of Chaos that really needed a speed up. See here and here for my previous experiments with SPH.
This next screenshot shows all the 12 cores of an i7 being used for calculating the SPH formulas. Note that the actual displaying of the particles cannot be parallel so there is not 100% CPU utilization. As the particle count goes up (and the time it takes to calculate the million particles moving takes longer than the display time) the CPU usage jumps closer to 100% on all cores.
After conversion to multi-CPU capable code it was time to render some new 4K resolution SPH simulations. Once the particles count and resolution goes up to fill a 4K screen the times start to plummet again, but seeing these in full 4K resolution is really nice. The parts in the following movie used 1,000,000 SPH particles each which is double my previous particle counts.
Other than SPH, the other modes that take advantage of the rewritten parallel processing code are 4D Cellular Automata, Coupled Cellular Automata 2, Ying-Yang Fire Cellular Automata, Large Neighborhood Totalistic Cellular Automata and Liquid Crystal Cellular Automata. The CA modes are the easiest to convert to parallel processing as by nature they update each cell independent of the others.
There is still a lot of code and modes that would benefit from parallel processing. Yet another entry on my ever expanding to do list of features for Visions of Chaos.
When creating a zoom movie script you can change and set a color palette for every key frame. While Visions of Chaos generates the movie frames the colors of the palettes will smoothly fade from one palette to the next.
Here is a quick sample movie showing the results. A different color palette was specified for the key frames every 2 seconds.
CA rules are usually specified in the survival/birth/states format. Conway’s original Game of Life is 23/2/2, so cells with 2 or 3 neighbors survive, empty spots with 2 neighbors become alive, and there are 2 states per cell (on or off).
If the rule starts with a / then it means there are no neighbor survival rules. eg /5/10 means no living cells survive no matter how many neighbor cells they have, a cell will be born at an empty location if it has exactly 5 neighbors, and each cell has 10 possible states it can be in.
I use the same format for the rules shown in this post. Because there can be rule numbers with 2 digits they need to separated with commas. Ranges of numbers can be separated with a hyphen. eg a rule may be (just made up to show as an example) 1-3,5,15/3,7,12-25/10.
Coding a 4D CA
Extending the 3D CA world to 4D is simple enough from a programming perspective. You just add the 4th dimension (usually denoted by the letter w) to your arrays. Rather than ca[x,y,z] you now have ca[x,y,z,w].
The number of possible neighbors for each cell grows from 26 (3^3-1) neighbors in 3D to 80 (3^4-1) in 4D. This means the settings dialog now needs 162 check boxes so the user can specify the parameters for birth and survival.
Counting the current neighbors of each cell now involves looping through the extra dimension, so again rather than just and X, Y and Z loop, you now add an additional W loop to count the 4 dimensional neighbors in the ca[x,y,z,w] array. This slows the processing down by an order of magnitude so larger grids are much slower to process. For example a 10x10x10 3D array has 10x10x10x26=26,000 neighbor count checks. A 4D 10x10x10x10 array has 10x10x10x10x80=800,000 cells to check while counting neighbors of each cell. Pushing the grid size to 100 gets the check count code up to 100x100x100x100x80=8,000,000,000 checks. The loops that do the neighbor checking/counting are the main slowdown when generating 4D CA. Since first writing this post I have now added parallel multiple CPU support for the 4D CA mode so it will use all of the available CPU cores for greater speeds.
Displaying 4D in 3D space
Now comes the tricky part. How do you display a 4 dimensional array in 3D?
To be able to truly show the 4 dimensions of (for example) a 10x10x10x10 sized 4D CA you would need to show 10 3D grids of 10x10x10 cells. I wanted some way to show 4 dimensions in the available 3 dimensions.
The first method I tried was to display a cell if any of the W dimension cells were active. This is the basic algorithm
for loopx=1 to gridsize do
for loopy=1 to gridsize do
for loopz=1 to gridsize do
begin
showcell=false
for loopw=1 to gridsize do
if ca[loopx,loopy,loopz,loopw]>0 then showcell=true
if showcell=true then DisplayCellIn3DAtXYZ
end
Another method is to pick a fixed W value. This is like slicing the 4th dimension into 3 for plotting. When I tested this method I found because you are relying on just one of the W dimension cells to tell you to plot or not to plot the 3D cell many/most of the resulting frames can be blank. The above method of “if any w dimension cells are on then plot it” works better for a consistent display every frame.
One other method to try is having a threshold value for the w dimension. Keep this low or the 3D cell will not trigger as active and won’t be rendered. So the above code would change to
for loopx=1 to gridsize do
for loopy=1 to gridsize do
for loopz=1 to gridsize do
begin
showcell=false
cellcount=0
for loopw=1 to gridsize do
if ca[loopx,loopy,loopz,loopw]>0 then inc(cellcount)
if cellcount>threshold then showcell=true
if showcell=true then DisplayCellIn3DAtXYZ
end
Playing with the threshold gives other insights into the 4th dimension structures of the CA.
Coloring the cells
At this point you have a 3D array containing a bunch of cells to render in 3D space.
These are the methods I currently use to color the cells;
1. RGB cube. Convert the XYZ location into scaled RGB values.
“David 3” /1-3/2
2. White only. Keep all the cells white. Looks good with a nice ambient occlusion renderer like Mitsuba. Also multiple colored lights can work well here too.
“David 2” /1-5/2
3. Color palette. Index into a color palette based on distance of cell from origin.
“Sphere Growth” /5/10
4. Color palette based on the 4th dimension density. For this method you count how many times the current XYZ cell is turned “on” in the W dimension array. Use count/gridsize*255 as an entry into a 256 color palette. This can show other structures/patterns the other methods do not.
“David 1” 3-5/1-2/2
Initial starting patterns
Try a single centered active cell, a block of 3x3x3x3 (remember this is 4D so all 4 dimensions need to be set on) active cells, a 10x10x10x10 block or active (or randomly active) cells, or the full grid filled with random cells.
Rendering engines
Visions of Chaos supports rendering the cell grids using software OpenGL, Mitsuba Renderer and/or Pixar’s RenderMan. OpenGL is good for quick test renders, but for best quality Mitsuba and RenderMan are the better options. Mitsuba performs excellently with even millions of cubes and I tend to use it the most when rendering movies.
“Plaid Box” /1/5 – Rendered with Pixar’s RenderMan
OBJ export
The cell grids can also be exported as Wavefront OBJ files (with material MTL files for coloring) and then imported into other 3D programs like Blender, Cinema4D, Maya, etc.
OBJ export rendered with Blender
OBJ export rendered with Blender – Strange alien satellite discovered near the Orion Nebula – Can you tell I am a Blender amateur?
Results
Here is a quick 4K resolution movie showing some 4D CA rules. For determining active cells in the 3D display I used the first method I mentioned above (if any w dimension cell is active then the XYZ location is plotted).
Help me
I am really interested in hearing any other methods for converting 4D into 3D for display that anyone has come up with. If you have a method that could give a better output than my results in this post let me know.
Also, if you know of any interesting 4D CA rules, or download Visions of Chaos and find any new rules, let me know. Finding interesting rules in 4D space seems much more difficult than in 2D and 3D (and 3D has not been easy). Finding those sweet spots between all cells dying and the grid filling with constant random noise is the real challenge.
Surprisingly there is very little out there about 4D Cellular Automata that I can find so hopefully this post may inspire others to give 4D CA a go.
I put together a new 4K resolution movie of some 3D Cellular Automata rules. All the parts were created in Visions of Chaos and rendered using the excellent Mitsuba renderer. The grids are up to 500x500x500 cells in size and the larger grids were over 25 million active cubes per frame.
I am always interested in new 3D CA rules, so if you do download Visions of Chaos and find any new rules let me know.
While I was browsing the archive section of Complex Systems I found some papers by Carter Bays here and here that discuss some “3D Game of Life” rules. Unfortunately they require special setups for the gliders to appear. I am more interested in finding rules that can lead to interesting behaviors from random starts (or from a smaller block of random cells). It is much more difficult (or at least it is for me) to find 3D CA rules that do not quickly die out or expand to fill the grid in a continuous random mess (and I have tried loads of random rules over the years).
Softology's Blog 