Monday, January 12, 2015

Now in 3D (Single Rotation)

I am proud to present my most complex Three.js application so far: 3D visualization of the Single Rotation cellular automaton.

Screen-shot of the program display. Grey lines form indestructible wall, attacked by multiple patterns smashing on it.

What you see on the above picture are world lines of the cellular automaton cells, as they move according to the Single Rotation rule. World lines are rendered in the browser window using WebGL technology.

This application develops the idea, presented in the previous post: Single Rotation rules with frame interpolation (application link)

In short, Single Rotation is a simple cellular automaton rule that tells, how "alive" cells move across the rectangular grid. Movement of the cells is discrete, so to improve visual experience, intermediate positions are interpolated using Lanczos re-sampling. Additionally, low-pass Lanczos filter is applied in order to remove oscillations with period 4 and less. It is done to suppress annoying circular movement of single cells (one can easily ensure that they are period-4 oscillators). Together, filtering and interpolation give smooth, continuous trajectories for each cell. Cells move in 2 dimensions, so their word lines are 3-dimensional curves. The visualizer shows these word lines.

In case you don't have a WebGL-enabled browser, or the simulator runs too slow, here is a video demonstration. See also "Advanced usage" section below to improve performance.

Collisions in 3D

Three-dimensional view of world lines makes spaceship collisions especially charming. Don't they resemble Feynmann diagrams? Below are some collisions, seen in the simulator.

Spaceship + cell

It can be easily proved that in every reversible cellular automaton with cell count conservation, a collision of a spaceship of the lightest weight and a single-cell always produces a (possible different) lightest spaceship and single cell again. Below is an example.

Collision of a light spaceship and a single cell (bottom) translates single cell and changes direction of a spaceship.

To see this scene yourself, paste the following code to the "Custom Scene" text area and click "Load":

at -20 -20; 2bobo$b2o
at 0 0; $o

Spaceship + spaceship, symmetric

From the similar considerations, symmetric collision of 2 lightest spaceship also necessarily produces 2 (possibly different) spaceships. Here is how it looks like.

Symmetric collision of 2 light spaceships produces same spaceships after long reaction.

Interestingly, it appears that both spaceships don't even exchange their cells in the collision. Scene code for this collision is:

at -20 -20; 2bobo$b2o
at 20 20; 3b2o$bobo

Spaceship + spaceship, asymmetric

When collision of 2 spaceships is not symmetric, products may be different, but they necessarily include at least one spaceship (possibly not the lightest one). Here is an example.

Collision of 2 different light spaceships produces a spaceship and oscillators.

Scene code for this collision:

at -20 -20; 2bobo$b2o
at 20 20; 3b2o$bobo

Heavy spaceship + cell

Finally, when heavy spaceship collides with anything, it almost certainly produces lots of debris. Reversibility only requires that at least 1 spaceship is produced in this reaction, usually it is a light one. Below is a collision of a heaviest single (i.e. not chained) spaceship, made of 12 cells; and a single cell. Multiple oscillators and one light spaceship are produced.

Collision of the heaviest known spaceship (12 cells) and a single cell (bottom-left) produces a single spaceship and oscillator.

Scene code:

at -20 0; 2b4o$4b2o$bo2bo$2bo$bo2bobo
at 0 0; o

You can try any of the 328 spaceships from the library. Just copy the RLE code of the spaceship into the "Custom scene" field. Mini-language also lets you to assign colors to patterns, and combine multiple patterns with different offset. Rotating is not supported yet, you can use Reversible CA simulator to get RLE of the rotated pattern (paste RLE into the "buffer" text area and click arrow buttons).

Advanced usage

The application also takes some additional URL arguments. Add them to the URL after a "?" character, separating options with "&".

  • antialias=true
    Enables anti-aliasing, making smoother images but increasing CPU load.
  • visibility=distance
    where distance is a number in the range 1000 ~ 50'000. It defines, how farthe world lines are seen. Big distance significantly decreases FPS. Here are some sample links:
  • Additional mesh generation parameters (with their default values):
    • chunkSize=500
      number of steps in one mesh chunk
    • skipSteps=1
      Generate tube section every n'th step (1 - every step)
    • boardSize=100
      Size of the square board, must be even
    • lanczosOrder=3
      Lanczos interpolation order, 1 ... 10. 1 - linear interpolation, 3 - smooth interpolation
    • interpSteps=1
      How many mesh steps are there between 2 generation. integer, 1 ... 4
    • smoothingPeriod=4
      Low-pass filter, removing oscillations with period bigger than this. integer, 1 ... 100. 1 - no filtering.
    • timeScale=0.1
      "speed of light". z-axis length of one generation
    • tubeRadius=0.1
      Radius of a single rube
    • tubeSides=3
      Number of sides in the tube cross-section (2...10)
Probably, some more arguments would be added later.


The application depends on the following technologies:

which means that latest versions of browsers and drivers are required. I have tested the application in Firefox (Linux, Windows) and Chrome (Linux, Windows, Android). It could run on the latest IE versions too.

Source code

Sources for this application are on Github: dmishin/singlerot-smooth, with 3D-specific code in the "3d" sub-folder. The sources are in CoffeeScript, to build them, CoffeeScript and "browserify" are required. Build system is written using GNU Make. I am not yet familiar enough with Node.js-specific tools.


Here are links to the related posts and pages.

Related Articles

Post a Comment