Quadtree Grammars

Keywords: art fractal rust
Created: 2019-07-17 Wed 23:23:00

Introduction

A quadtree is a tree where each node has exactly four children. One application is storing 2D data by recursively dividing larger squares into four quadrants (top-left, top-right, bottom-left, bottom-right) and storing these in the tree. Once some condition is fulfilled, e.g. all the pixels in the square have a similar color, the process stops and the square is stored as a leaf.

While experimenting with operations on images compressed this way, a bug in my code produced this image:

quadtree_tri.png

As a reference, the original images looks like this:

quadtree_orig.jpg

Why is there a Sierpinsky Triangle hidden in there?

After a bit of debugging, I found out that the upper right corner of each node was not drawn.

The broken images nicely shows how the images is "compressed" by storing parts with the same color as larger squares.

In the upper left, a piece of sky is stored as a big square whereas on the container below the sierpinsky triangles are very visible because the cells of the quadtree are so small.

A Framework for Experimentation

What other kinds of patterns and fractals can be generated this way? For further experimentation a bit of tooling is needed.

I'm interested in programming languages, and finding efficient ways to express ideas (see Kolmogorov Complexity) so the solution is obvious: A small language for defining patterns.

Note: Here, the notion of Kolmogorov complexity — the length of the shortest program necessary to generate some images — is a fuzzy. Which parts of the software should be counted? The rust program? The png library? What about the rust compiler itself?

A pattern is a list of four "pattern elements", one for each quadrant of the quadtree. These element can either be constant colors or references to other patterns.

This forms a subset of the context-free grammars (Chomsky Type-2), the ones with exactly four terminals and non-terminals on the right-hand-side.

In addition to that, each reference to other patterns needs a fallback color to be used once the cells are to small to be divided.

TODO: The code can be found on github TODO: example usage

Systems With One Rule

Ignoring rotations and different colors, there are only a handful of systems with a single rule.

S -> white green blue S | white

quadtree_rule1.png

S -> S red green S | red

quadtree_rule2_1.png

S -> red S yellow S | yellow

quadtree_rule2_2.png

S -> S blue S S | white

quadtree_rule3.png

There is the Sierpinski Triangle again.

Systems With Two Rules

Adding more rules, the number of possible grammars quickly grows.

S -> T red green T | red
T -> blue S S yellow | blue

quadtree_2rule_1.png

Small changes to the rules lead to very different images.

S -> red T green T | red
T -> S blue S yellow | blue

quadtree_2rule_2.png

S -> red T T green | red
T -> yellow S S blue | blue

quadtree_2rule_4.png

S -> brown T T T | brown
T -> yellow S S S | yellow

quadtree_2rule_3.png

Chance and Necessity

These rule systems are already pretty powerful but I'd like to have a bit more variation.

An easy way to do this is allowing multiple rules with the same left-hand-side (the part before the -> ) and randomly choosing one on each iteration.

S -> blue S S yellow | yellow
S -> S red green S | red

quadtree_3rule_1.png

S -> S S S white | white
S -> S S S blue | blue
S -> S S S green | green
S -> S S S red | red
S -> S S S yellow | yellow

quadtree_3rule_2.png

Now the RuleSet contains a list of patters for each index and each time one is chosen at random.

impl Index<usize> for RuleSet {
    type Output = Pattern;

    fn index(&self, i: usize) -> &Pattern {
        let mut rng = self.rng.borrow_mut();
        let j = rng.gen_range(0, self.rules[i].len());
        &self.rules[i][j]
    }
}
S -> S S S yellow | yellow
S -> S blue S S | blue
S -> white S S red | red

quadtree_3rule_3.png

Letting the Computer do the Work

At this point, the hardest part is finding sets of rules that produce interesting images. Luckily, that's easy to automate by generating random rule sets and choosing the ones that look the best.

When generating a branch of rule, the probability a reference to another rule is chosen is 75%, otherwise a constant color is used.

For rules with at least one constant color, the last of them is used as fallback color, otherwise a random one is generated.

Due to the way the systems are generated, there is a chance some of the rules can't be reached from the starting symbol ( S in the previous sections, 0 for the randomly generated ones).

Here are a few of my favorites with different color pallets and parameters.

Black & White, 2 to 4 rules with 1 branch

0 -> 1 2 2 0 | black
1 -> black 1 1 black | black
2 -> white 2 2 black | black
3 -> 3 1 white 2 | white

rng1_003.png

0 -> white 1 0 0 | white
1 -> 1 black 1 white | white

rng1_011.png

0 -> 1 black 0 1 | black
1 -> 0 1 white 1 | white

rng1_028.png

0 -> 1 0 black 1 | black
1 -> 1 0 white 1 | white

rng1_063.png

0 -> black 0 2 black | black
1 -> 2 0 white 2 | white
2 -> 0 1 3 2 | black
3 -> 3 1 white 2 | white

rng1_092.png

0 -> 2 0 2 1 | white
1 -> black 2 2 1 | black
2 -> 2 0 0 1 | black

rng1_096.png

base16 colors + white, 2 to 4 rules with 1 branch

0 -> yellow 0 1 red | red
1 -> white 1 1 cyan | cyan

rng2_729.png

0 -> 1 2 3 2 | green
1 -> red 3 0 purple | purple
2 -> 3 yellow 3 0 | yellow
3 -> red white brown brown | brown

rng2_421.png

0 -> 1 blue 1 0 | blue
1 -> 0 white 0 green | green

rng2_511.png

0 -> 1 white blue 1 | blue
1 -> 0 brown 0 0 | brown
2 -> 0 2 yellow 1 | yellow

rng2_963.png

0 -> 0 0 1 0 | yellow
1 -> yellow 1 orange brown | brown

rng2_805.png

0 -> 1 0 0 0 | yellow
1 -> blue 2 1 1 | blue
2 -> 0 cyan 1 1 | cyan

rng2_921.png

0 -> 1 3 2 2 | orange
1 -> 1 2 0 brown | brown
2 -> 3 white red 3 | red
3 -> 3 3 1 1 | white

rng2_059.png

0 -> 1 1 1 1 | cyan
1 -> 0 0 0 1 | white

rng2_392.png

base16 colors + white, 2 to 4 rules with 1 or 2 branches

0 -> 0 orange 1 0 | orange
1 -> 1 white cyan 1 | cyan

rng3_761.png

0 -> 0 brown 1 0 | brown
1 -> 0 1 1 yellow | yellow

rng3_825.png

0 -> 1 2 1 2 | red
0 -> 1 0 orange 2 | orange
1 -> blue brown white 0 | white
1 -> 0 2 0 brown | brown
2 -> 2 1 1 2 | orange
2 -> 1 brown white blue | blue

rng3_014.png

0 -> 1 0 2 1 | white
1 -> 0 brown 1 1 | brown
2 -> 3 3 1 purple | purple
3 -> 2 3 3 0 | yellow
3 -> 1 0 white green | green

rng3_054.png

0 -> 0 0 1 0 | white
1 -> 0 1 0 2 | white
1 -> 1 brown 2 0 | brown
2 -> 1 1 cyan 2 | cyan

rng3_056.png

0 -> green 0 1 blue | blue
0 -> 0 yellow 0 1 | yellow
1 -> blue 0 1 purple | purple
1 -> 1 0 yellow 1 | yellow

rng3_167.png

0 -> 2 0 0 2 | red
0 -> 0 0 blue 2 | blue
1 -> 1 2 1 2 | green
2 -> 1 3 2 2 | orange
3 -> 1 white blue 2 | blue

rng3_176.png

0 -> 1 1 3 2 | blue
0 -> 0 yellow 3 2 | yellow
1 -> green 1 2 white | white
2 -> red 3 2 3 | red
2 -> blue white 0 2 | white
3 -> blue 3 3 cyan | cyan

rng3_235.png

0 -> 0 2 2 1 | white
0 -> 2 brown 0 1 | brown
1 -> 1 cyan 0 2 | cyan
2 -> blue 2 cyan yellow | yellow

rng3_294.png

0 -> 0 1 2 1 | green
1 -> 2 1 0 3 | yellow
1 -> 0 3 3 0 | yellow
2 -> 1 brown white 1 | white
3 -> 2 cyan 3 3 | cyan
3 -> 2 1 1 3 | blue

rng3_419.png

0 -> yellow 3 1 2 | yellow
1 -> white 3 white 3 | white
1 -> 0 0 3 3 | yellow
2 -> 1 1 3 brown | brown
3 -> 0 1 yellow 1 | yellow

rng3_745.png

0 -> 0 1 1 0 | blue
1 -> blue 1 white orange | orange
1 -> 0 1 1 yellow | yellow

rng3_858.png

0 -> brown 0 brown blue | blue
0 -> 1 purple 1 red | red
1 -> 0 white red orange | orange
2 -> 0 2 1 2 | orange
2 -> red blue 1 0 | blue

rng3_901.png

0 -> 0 0 0 1 | red
1 -> 2 1 2 yellow | yellow
2 -> 2 white green 2 | green

rng3_931.png

Conclusion

Looking back at my selection from the randomly generated rule sets, the sweet spot seems to be systems with two or three rules, beyond that, the images become to "chaotic".

It should be possible to define a taxonomy of patterns based patterns that show up often, e.g. Sierpinski Triangles, diagonal divisions and recursive binary partitions, but that has to wait for another time.

I'm working on a gallery page with a larger number of images for random rule sets and the source code will be uploaded to github soon.

Another direction to take this would be using simple black and white patterns, shapes and symbols so that the results can be plotted with a pen plotter or using octrees to generate random fractal isometric structures.

If you have any questions about this process, write me at quadtree@<domain>.

References

For the images, I've used colors from the tomorrow-light variant of the base16 color scheme. Thanks Chris Kempson!

Backlinks


Last export: 2020-05-29 Fri 00:09
This document is also available as plain text and pdf.

If you have an idea how this page could be improved or a comment send me a mail.