Tutorial: Similar Paired Dissection Coloring

Introduction

I’ve always been drawn to drawing squares and triangles on graph paper, and seeing the myriad ways that those two simple shapes could be broken down and recombined in fascinating ways. This coloring algorithm allows you to play with those ideas, to a level and precision not available with pencil and paper.

Background

Mathematically speaking, a dissection is when a shape is broken into smaller pieces, in such a way that there are no overlaps and no gaps. There are many ways in which squares can be dissected into smaller squares. A checkerboard is one example, where a larger square (the board) is dissected into 64 small squares (eight rows and eight columns). A few other examples of dissecting a square are shown in Figure 1.

Figure 1: Examples of Square Dissections

Triangles can easily be dissected into other triangles. Here, I’m interested only in isosceles right triangles, that is, triangles with a right angle and two sides the same length. A few ways to that are shown in Figure 2.

Figure 2: Examples of Triangle Dissections

Each shape can also be dissected into both shapes. For example, draw a square and one (or both) of its diagonals, and the square has been dissected into triangles. There are many different ways to dissect squares and triangles into squares and triangles, a few of which are shown in Figure 3.

Figure 3: Examples of Paired Dissections

In each case, each shape is broken into small copies of both shapes. Then, each of those shapes can be further dissected, and so on, leading to a fractal tessellation. That’s what this formula does.

There are four types of dissections that can be created, depending on with which shape you start and how you want to dissect it: triangle to triangle, triangle to both, square to square, and square to both. In any case, you need a starting point, which is the axiom. That can be either a triangle or a square. Then, you need one or two generators (two for either “to both” dissection type). A generator defines how the shapes are dissected into smaller shapes.

Perhaps the best way to use this coloring is to first design your dissection on a piece of graph paper. For an example, let’s look at the first pair in the Figure 3. We begin with a square (the square axiom) that is divided by its two diagonals into four triangles (the square generator). Each triangle (the triangle axiom) is then divided into a square and two more triangles (the triangle generator). Sketch each axiom and the points of its generator, and find the coordinates of all the corner points. For this example, the sketches might look like this:

Figure 4: Generators Laid out on a Coordinate Plane

It’s not necessary that the coordinates be integers, or that the shape have a corner at (0, 0), but I find that doing so makes it easier to keep track of the points. The reason you need to find the corner coordinates is so that the routine knows how to draw the smaller shapes, and so that the shapes retain their, well, shape.

Another important consideration is the ordering of the generator points. The generator represents the axiom being dissected into a number of smaller shapes, called “sub-shapes.” The corner points of each of these sub-shapes need to be entered in a particular order (although the order of the sub-shapes for each generator is irrelevant). For example, the square is being dissected into four triangles. The triangle on the left of the square, with its hypotenuse along the square’s left side, could be sub-shape 1, 2, 3, or 4, it doesn’t matter. The ordering of its three corner points, though, is important. The scheme for triangles is to always have the right angle be at corner point 1, and then move counter-clockwise around the shape. This ordering holds for the axioms as well. This ensures that the angles are created properly, and that the sub-shapes don’t get turned inside out. So, for the triangle on the left, the correct ordering of its corner points is: first (1, 1), then (0, 2), and finally, (0, 0). Likewise, the top triangle’s corner points would be entered as: (1, 1), (2, 2), and (0, 2).

For square sub-shapes, there is some flexibility. The counter-clockwise ordering still holds, but, because of the symmetry of the square, there is not a particular point that must be entered first. Indeed, which point is chosen to be the first point may matter greatly to the final image. Consider this example:

Figure 5: Various Layouts of the same Dissection

In each case, the original square is broken down into one medium-sized square (2/3 of the size of the original), and five small squares (1/3 of the size of the original). The individual squares are symmetric, but the collection is not. The red squares indicate the location of the first corner of the axiom, and the black squares mark the first corner of the square sub-shapes. In the first case, each of the sub-squares is in the same orientation as the axiom, with the first corner in the lower left. In the second case, the sub-squares have been rotated, bring pairs of first corners together. The third and fourth cases have the same patterns of sub-squares, but now the axiom has been rotated so that the first corner is in the upper right. The effects of the layout changes are shown in Figure 6. Each panel is the fourth iteration of the corresponding generator shown in Figure 5. In each, you can see the characteristic cluster of a larger square surrounded on two sides by five smaller squares, but that’s where the similarity ends.

Figure 6: Fourth Iteration of Various Square Dissections

It pays to map your design out before entering the parameters, and it also pays to be flexible and try rotating the corner points around to see what happens.

Parameters

To keep track of all the corner points and sub-shapes, this formula has many parameters. However, they are grouped for ease of use, and many parameters are not visible unless they are needed.

General parameters: Overall settings, independent of the specifics of the dissections.

# iterations: How many iterations to perform; at least 0.
minimum size: The smallest size of a sub-shape that will be dissected in the next iteration. Set to 0 to dissect all the shapes.
print smallest: Check this box to print the size of the smallest sub-shape in the current iteration to decide how to set the “minimum size” parameter.
how much memory: Set this to be at least the number from the “print memory” diagnostic. More shapes means more memory; fewer shapes frees up memory for other things.
print memory: Check this box to have the coloring tell you what to put in the “how much memory” parameter
color by: How to color the image. The choices are:
- outline: Draws the outline of each shape. The shapes are filled with the solid color.
- shape number: Colors by the number of each shape, which reflects the order in which they were created.
- shape size: Colors by the size of each shape.
- shape type: Colors each triangle with color 0 and each square with color 399. Clear the “Repeat Gradient” box when using this mode.
line thickness: The thickness of the line when coloring in the “outline” mode; only visible in that mode.
speedup threshold: If the pixel is further than this distance from the line, it won’t be checked against the line for coloring purposes. Generally, set it a bit larger than the longest side that will be drawn.
print speedup: Check this box to print the longest side in the current iteration, so you know how to set the “speedup threshold” parameter.

Axiom parameters: Settings for the triangle and/or square axioms, depending on the “dissection type” choice.

dissection type: How the original shape is to be dissected. The choices are:
- triangle -> triangle: An initial triangle is dissected only into triangles. No square axiom or generator parameters are displayed.
- triangle -> both: An initial triangle is dissected into triangles and squares. Both triangle and square axiom and generator parameters are displayed.
- square -> square: An initial square is dissected only into squares. No triangle axiom or generator parameters are displayed.
- square -> both: An initial square is dissected into triangles and squares. Both triangle and square axiom and generator parameters are displayed.
Triangle axiom: The coordinates of the three corner points of the triangle axiom, if used.
- corner 1 (Re, Im): Complex coordinates of the first corner.
- corner 2 (Re, Im): Complex coordinates of the second corner.
- corner 3 (Re, Im): Complex coordinates of the third corner.
Square axiom: The coordinates of the four corner points of the square axiom, if used.
- corner 1 (Re, Im): Complex coordinates of the first corner.
- corner 2 (Re, Im): Complex coordinates of the second corner.
- corner 3 (Re, Im): Complex coordinates of the third corner.
- corner 4 (Re, Im): Complex coordinates of the fourth corner.

Generator parameters: Settings for the triangle and/or square generators, depending on the “dissection type” choice.

Triangle generator: Parameters describing how each triangle is dissected, if needed.
- # sub-shapes: How many pieces each triangle will be broken into. The minimum is two and the maximum is 20. For each sub-shape, the following parameters will appear:
  - type: Triangle or square. If “triangle,” then the “corner 4” parameter is not displayed.
  - corner 1 (Re, Im): Complex coordinates of the first corner.
  - corner 2 (Re, Im): Complex coordinates of the second corner.
  - corner 3 (Re, Im): Complex coordinates of the third corner.
  - corner 4 (Re, Im): Complex coordinates of the fourth corner. Not displayed if “type” is “triangle.”
Square generator: Parameters describing how each square is dissected, if needed.
- # sub-shapes: How many pieces each square will be broken into. The minimum is two and the maximum is 20. For each sub-shape, the following parameters will appear:
  - type: Triangle or square. If “triangle,” then the “corner 4” parameter is not displayed.
  - corner 1 (Re, Im): Complex coordinates of the first corner.
  - corner 2 (Re, Im): Complex coordinates of the second corner.
  - corner 3 (Re, Im): Complex coordinates of the third corner.
  - corner 4 (Re, Im): Complex coordinates of the fourth corner. Not displayed if “type” is “triangle.”

Hints

You are, of course, free to use this coloring however you’d like. However, these hints may help your explorations be more productive.

This is one of those coloring formulas that does all the work. It was designed to be used as an outside coloring with the “Pixel” formula in lkm.ucl.
Design your dissection beforehand. This coloring doesn’t respond well to random mashing of buttons and tweaking of knobs.
The counter-clockwise ordering of points is important for the coloring to work properly. Likewise, having corner 1 of a triangular shape be the corner with the right angle.
When beginning, use the “outline” coloring mode, with a relatively small line thickness (about 0.01 should work). I typically use either a solid black gradient or a black to white ramp, with the “Repeat Gradient” box cleared. Set the solid color to white. This will help you see the shapes more easily.
Iteration 0 will show you the axiom, and iteration 1 will show you the (first) generator, to help you verify your layout.
More iterations means more memory and much more time. Iteration 8 can take days (literally) for a reasonable-sized image. Tread lightly with more than 3 or 4 iterations until you have some idea of what you’re doing. Use the diagnostics to know how much memory to allocate and how to use the speedup factor.
If you’re doing many iterations, then you may want to set the “minimum size” to something like 0.001 or so. This will stop small shapes from being dissected, which will reduce the amount of memory used and will keep the shapes from turning into solid lines on your image.
Checking or clearing the diagnostic boxes will cause that layer to start calculating again, so be careful with them if you ‘re working on a complex image. If you don’t see the messages when checking the box, reload the coloring.

Sample Image

Final Image (click for parameters)

1 Iteration

2 Iterations

Figure 7: Sample Image

This image reminds me somewhat of a stained glass window. It uses 3 layers, 2 for the glass and one for the lead came between the pieces. It begins with a square that is divided into 2 squares and 4 triangles. Each triangle is divided into a square and 3 triangles, as you can see in the upper left corner of the “Iteration 2” image.

Here’s how to make it.

Step 1: Start a new fractal, with these characteristics:

Location: center of (1, 1), magnification of 1.95, rotation 0, stretch 1, skew 0
Mapping: none (default)
Formula: “Pixel” from lkm.ufm, with the default settings.
Inside: none (default)
Outside: “Similar Paired Dissection” from lkm3.ucl, with the default settings. Check the “Repeat Gradient” box and set the Solid Color to black (0 red, 0 green, 0 blue).
Layers: change the layer name to “Layer 1.” Merge mode normal, opacity 100%.
Image: set both width and height to 480 pixels.
Gradient: remove all the control points. Insert one at position 0, color red (255 red, 0 green, 0 blue). Insert one at position 100, 255 red, 65 green, 65 blue. Insert one at position 200, 255 red, 129 green, 129 blue. Insert one more at position 300, 255 red, 65 green, 65 blue. This layer is providing the saturation and luminance for the image, so if you look at the gradient in the HSL mode, you should see that the hue is constant, and the saturation and luminance ramp up to peaks at position 200, and ramp back down. Make sure that the “Smooth Curves” gradient mode is on.

Your image might not look like much, but it should resemble the “Step 1” image in Figure 8.

Step 1

Step 2

Figure 8: Sample Image, Steps 1 and 2

Step 2: Create the basic dissections

In the “General parameters” section on the Outside tab, set (all are defaults except the first):
- # iterations: 2
- minimum size: 0
- print smallest: cleared
- how much memory: 100
- print memory: cleared
- color by: outline
- line thickness: 0.01
- speedup threshold: 1
- print speedup: cleared

In the “Axiom parameters” section, set the “dissection type” to “square -> both.” Here are the corner point data for the axioms:

Corner	Triangle Axiom	Square Axiom
1	(0, 0)	(0, 0)
2	(3, 0)	(2, 0)
3	(0, 3)	(2, 2)
4	n/a	(0, 2)

In the “Triangle generator” section, set “# sub-shapes” to 4. Here are their data:

Item	sub-shape 1	sub-shape 2	sub-shape 3	sub-shape 4
type	square	triangle	triangle	triangle
corner 1	(1, 0)	(0, 0)	(2, 1)	(1, 2)
corner 2	(2, 1)	(1, 0)	(1, 0)	(0, 3)
corner 3	(1, 2)	(0, 1)	(3, 0)	(0, 1)
corner 4	(0, 1)	n/a	n/a	n/a

In the “Square generator” section, set “# sub-shapes” to 6. Here are their data:

Item	sub-shape 1	sub-shape 2	sub-shape 3	sub-shape 4	sub-shape 5	sub-shape 6
type	square	triangle	triangle	square	triangle	triangle
corner 1	(1, 1)	(1, 0)	(2, 1)	(1, 1)	(1, 2)	(0, 1)
corner 2	(0, 1)	(2, 0)	(1, 0)	(2, 1)	(0, 2)	(1, 1)
corner 3	(0, 0)	(1, 1)	(2, 0)	(2, 2)	(1, 1)	(0, 2)
corner 4	(1, 0)	n/a	n/a	(1, 2)	n/a	n/a

Your image should look like “Step 2” in Figure 8.

Step 3: Finish.

Set “how much memory” to 584 and “speedup threshold” to 0.18.
Set “# iterations” to 4.
Set “color by” to “shape number.”
Set “Color Density” to 5
Click on the “Add...” icon to add a new layer, Layer 2.
On Layer 2, change “Color Density” to 25 and the Merge Mode to “Hue.”
Replace Layer 2’s gradient with “rainbow 1” from lkm.ugr.
Add Layer 3 and set its merge mode to “Multiply.”
Change its “Color Density” to 1 and clear the “Repeat Gradient” box.
Set the “Solid Color” to white (255 red, 255 green, 255 blue).
The Layer 3 gradient: delete all the control points. Add a black one at position 0, and a white one at position 399.

When it’s all done, it should look just like the “Final Image” in Figure 7. If not, look back through your work and check the parameter entries. Or, just click on the finished image for the parameter set.

I hope you have fun with this, and be sure to share your creations with the rest of us!

Back to Tutorials page
Up to my home page