The loop is examined as a conceptual programming tool in the context of computer artwork and fractal curve generation. In particular, a simple geometric construction for the visualization of Alexander’s horned sphere as a self-similar fractal curve in the plane is presented, based on a recursive rep-2 rectangle progression to a specified depth. Parameterized curve generation and rendering details are briefly discussed.
1. Loops and Computers
Loops form the fundamental core of almost all computer programs. The most common type is the iterative loop, typically signified by the keywords for, while, do, repeat etc, in which a given set of instructions is repeated a specified number of times.
The recursive loop is a more powerful construct that performs a given set of instructions, typically including recursive calls with modified parameters back to the instruction set itself, until a terminating condition is met. Recursive algorithms solve problems by reducing them to smaller and smaller subproblems until a solution is found, reusing the same set of instructions as often as required.
This elegant approach to problem solving satisfies the programmer’s endless desire for efficiency and simplicity in program design. Recursive loops can always be rewritten as iterative ones, but if an algorithm can be defined with a recursive approach it is generally best implemented as such.
2. Fractal Geometry
Fractal geometry involves the description of mathematical objects that display self-similarity on all scales [6]. Recursion is a natural way to describe such objects programatically. For instance, the fractal curve shown in Fig. 1 can be somewhat confusing to the eye until the viewer realises that it’s composed of a common structure repeated at successively smaller scales.
Fig 1. A set of woven horns.
The woven horn is based on a famous mathematical construct called Alexander’s horned sphere, which is traditionally visualized as a recursive set of interlocking pairs of orthogonal rings of decreasing radius [1,5].
The horned sphere has been embedded in the plane by reducing the interlock angle between ring pairs from 90o to 0o, then an over-under weaving pattern has been defined to reestablish ring interlock without intersection to give the woven horn set. Fig. 1 was inspired by the etching Yggdrasil by Bill Meyers [4], probably the most famous realization of Alexander’s horned sphere in the plane.
It should be noted that the woven horn construction is a self-similar fractal but not technically an area-filling curve, as any open subset of the plane will contain points that are a non-zero distance from the curve.
3. Rep-tiles
Rep-tiles, polygons which can be divided into smaller copies of themselves, provide a method of tiling an area to a given depth of recursion [3,6]. The rep-2 rectangle with sides in the ratio 1:sqrt(2) is of particular interest. For instance, metric paper sizes A2, A3, A4 etc are rep-2 rectangles, making them convenient for stacking and printing purposes as each page can be folded in half to give two pages of the next smaller size [2].
Fig. 2 shows a rep-2 rectangle progression to three levels of subdivision. Note that the side length ratio 1:sqrt(2) is maintained for each generation. This fractal structure forms a rectangular lattice upon which the planar woven horn set can be generated.
Fig 2. Rep-2 rectangle progression.
So how far should we recurse, given that this process is potentially infinite? Fortunately the display or printing device used to visualise the object provides a convenient terminating condition: there is little point in recursing beyond the visible resolution of the device, typically one pixel or picture element.
One advantage of fractally defined curves is that they can be examined in infinite detail. This can be done efficiently by zooming in on an area of interest and scaling up the coordinate system accordingly, and choosing upper and lower recursion limits such that parts of the curve that lie outside the display area or are too small to see are clipped, and only the visible subset drawn.
3. Curve geometry
The construction of one generation of horn growth from a pair of left and right parent branches Pl and Pr is shown in Fig. 3. The generated curves are bounded by the rep-2 rectangle with width w and height h where:
w = |Pl – Pr|, the gap distance between the terminal points of Pl and Pr
h = w / ff2
Fig. 3. Geometric construction of horn branches.
Spacing parameter s forms an internal margin that creates an interior rep-2 rectangle progression offset from the bounding rep-2 rectangle (s’ = ff2 s). Thus each generation attracts curves towards a central vanishing point, facilitating the woven horn design.
Horn branches for each generation are described by two long curves Cl and Cl’ and two short curves Cs and Cs’. The actual geometry of these cubic spline curves is not important here; suffice it to say that they can be adjusted according to taste provided that the following constraints are met:
lines CD and DE must be collinear to guarantee long curve continuity;
the entrance angle a formed at point A must agree with the exit angles a at G and H, and hence agree with the entrance and exit angles of future generations.
The following guidelines were found to produce good results but are not essential:
point D should be coincident with the top left corner of the interior rectangle;
curves should be bounded by the outer rep-2 rectangle;
an entrance/exit angle of 45o is convenient and aesthetically pleasing.
This process is repeated from the terminal points G and I for the next generation. Curves Cl and Cs then become parent generators Pl and Pr, and curves Cl’ and Cs’ become intersecting parent generators Pr’ and Pl’, with the gap width w reduced and the frame of reference rotated accordingly. Fig. 4 shows the process of recursive growth to depths of 1, 2, 3 and 9.
Fig. 4. Increasing generation depth: (a) d = 1; (b) d = 2; (c) d = 3; (d) d = 9.
4. Results
The gap width wd of the branching pair at any particular depth d can be calculated from the spacing parameter s and the total structure width W as follows:
wd = wd-1 /ff2 - 2sd-1 (where w0 = W and sd is the actual spacing for iteration d)
The structure’s appearance is now defined by just two variables: the inter-generational spacing value s and the depth of recursion d. The effect of varying control parameter d was shown in Fig. 4. The effect of varying the other control parameter s is shown below in Fig. 5.
Fig. 5. Spacing as a percentage of width: (a) s = 10%; (b) s = 20%; (c) s = 30%.
Smaller spacing values yield boxier shapes with denser weave around the perimeter of each rep-tile, as seen in Fig. 5a. The shape converges to a single underlying rep-2 lattice as s approaches 0. Larger spacing values, such as those in Figs. 5b and 5c, provide rounder, looser weaves with tighter clusters in the center. The optimal spacing for aesthetic purposes was found to be around s = 13%.
The program developed for this paper exports woven horn designs as a series of generational branch growths in the following formats:
PostScript file of offset curves of decreasing thickness;
VRML file of polylines or extrusions of decreasing radius.
Fig. 1 shows a depth 10 structure stored in PostScript format and rendered in PhotoShop with glass and noise filters applied.
Conclusion
Fractal geometry highlights the power, beauty and elegance of the recursive loop: simple instructions are used to visualize complex shapes that vanish inwards with infinite clarity.
Acknowledgments
Thanks to Alan Tonisson for providing useful comments.
