The First Pixel

Sierpiński Triangle

The creation of the Sierpiński Triangle can be done in many ways. One surprising way is the use of random (chaotic) input, and developing order with a simple rule.

Algorithm – The Chaos Game

The algorithm could not be more simple:
1. set 3 origin points (or 4 if you’re in 3D).
2. initialize a point (to anything, but to avoid artifacts, start at one of the origin points).
3. move 50% the distance to a randomly chosen origin
4. repeat step 3, drawing the points each time.

This is known as “Order from Chaos” from where I first heard it (yes, I spelled it wrong in the demo, did you notice?). It is also called the “Chaos Game” for generating the fractal from randomness.

Three Dimensional

I showcase this in 2D and 3D. The rendering in 3D is handled in software on the CPU. No GPU, 4×4 or even 3×3 matrices, involved here (well, I need the GPU to draw the dots!). It uses the core 3D formula that I figured out after many attempts in Grade 8, which is at the root of all perspective correct matrix transforms. I remember thinking with this formula, I could render literally anything… I felt I had discovered the Holy Grail of computer graphics.

Color

The coloring is interesting as well. Each origin has its own color. If the point it at the origin, that color takes 100% of the precedence of the color choice. If the point is equidistant from two origins, then they contribute the same amount.

Interestingly, neither the 2D nor 3D versions have points near the center location of the structure, so you’ll never see a color of equal mix of all 4 colors.

Iterative Function System

Iterative Function System produces fractals using the chaos game: Order from Chaos.

Inspiration

My prior video, “order from chaos” produced the Sierpinski Triangle in 2D and 3D. I recalled the IFS (iterative function system) method of producing fractals. Specifically, the Barnsley fern. It is reminiscent of a Assembly ’94 (demoparty) entry in the demoscene: “Verses” by Electromotive Force, showcasing an animation / transition between IFS fractals.

VGA Graphics

“Verses” was made using VGA, which had many graphics modes, mostly demonstrated by its 256 color mode (18-bit color palette = 6-bit per RGB = 0..63) — the standard 320×200 mode 13h (and other Mode-X variants). However, their IFS demo ran in VGA mode 12h: 640×480 x 16-colors.

(I’ve always wondered what the Sierra line of 3D adventure games would’ve looked like if the artists deployed their phenomenal use of 16-color dithered graphics in VGA 640×480 vs. the ugly 320×200 digitized versions of painted scenes).

How IFS Works

Versus amazed me with the showcase of the Sierpinski Triangle — since it was being produced by a different method unknown to me. How was this done? It’s actually quite similar to the chaos game. In fact, it likely makes more sense when you think about it from the IFS perspective. Let’s use the Sierpinski Triangle as an example, since it’s easy to view as self-similar.

IFS is a collection of transformations of existing points. If you start with the entire Sierpinski Triangle — how do you make the 3 sections of self-similarity? You transform the triangle to be half the size (in X and Y) and move it towards one of the 3 spots. That’s it! Those are the 3 transform functions used in IFS. (The Chaos Game — in which you move an existing point half-way to one of the triangle vertices — is actually just doing the same thing!).

Now take the Barnsley fern. It’s the same thing except: The entire fern becomes two things: the left leaf, and the right leaf — which involves a rotation. But it also becomes two more things: it becomes itself pushed “upward” so that both left/right leaves become the next leaves in the sequence, and its stem; a “reset” function (the starting point). Why is the stem transform required? Because if it just continued to become left/right leaves, and “upward” pushes into the array of such leaves, the points would become “trapped” in that recursion.

That begs the question: Why does the Sierpinski Triangle not require a 4th function that resets the fractal? Why don’t the points get trapped in recursion, and never find their way back “out” to become the entire fractal? Because the transforms are only 50% of the size, and if you continue halving, and sum all of these, you get the whole: 50% + 25% + 12.5% + 6.25% + … = 100%. This is not the case with the fern.

Colors

There is no standard way to color. I have my own invention: I assign a color to each transformation function. During the chaos game of transforming an X,Y point over and over, it also gets the color of that transformation. Now, if you just immediately used that color, you’d get (in the case of the ferns), the stem being color A, left leaf = color B, right = color C, and the extension (i.e. 95% of the entire fractal) = color D. Ugly. So it only interpolates (LERPs) to the desired color. This is how the stem of the fern stays colored so well.

As for the non-nature fractals… I’m not too pleased with the coloring; both in how the colors “spread” through the fractal, and the “nature” color palettes are just plain bad. In these non-nature cases, it would actually be better (sometimes) if the color changed (was reset) immediately, with no interpolation — as it would showcase the direct result of each function.

Functions Source

Fractal data is acquired from the gallery of examples of IFS Construction Kit, made by Larry Riddle.