Pretty? It's a screenshot of the output from fractals.ps, which is a PostScript program for drawing fractals using random iteration. |

Roughly speaking, any structure is said to be *fractal* if it is self-similar; i.e. if examining part of the structure yields something similar to the whole. Of course, this does all depend on how you define "similar". Look at the word "chaos" in the picture above; you should be able to see that every line in every letter of the word is in fact the word "chaos" again. Every line in those little "chaos" is another "chaos", and so on. The triangle (it's known as Sierpinski's Triangle) is fractal too - it's made of three smaller triangles, each of which is contains three smaller triangles.

It turns out that knowing exactly how the picture is self-similar is the *only* thing you need in order to reproduce it. We can describe the self-similarity of a fractal as a set of transformations, each of which maps the the image onto part of itself, such that combining all of the transformed copies produces the original image again.

Under this scheme, Sierpinski's Triangle is represented by:

a b c d e f ================ .5 0 0 .5 0 0 .5 0 0 .5 .5 0 .5 0 0 .5 0 .5

Fractal decomposition of a fern This image is in the public domain. |

To produce a plot of a fractal from a set of transformations, we use the random iterations algorithm [Barnsley]. In short, we repeatedly transform a single point, each time using a transformation randomly chosen from the list. If we plot the points visited, we get an approximation to the fractal; proof of this is well beyond the scope of this page.

PostScript is a stack-based language in which programs and data are described in Reverse Polish Notation. This is somewhat counterintuitive at first, but it makes it very easy to write a fast and robust parser, and for graphics programs to use it as an output language.

I am no expert on PS, having only started coding in it earlier this week - I make no representations as to the quality, reliability or conformity of my program. Specifically, bear in mind that if you send this file to a PostScript printer, the algorithm will be executed on the printer, not on your PC. What takes your machine a second to preview may take your printer several minutes to produce - you have been warned!

The first part of the program is the data for the three fractals. Each line specifies a transformation and a probability associated with it; these are used to weight the choice of transformation, so that the image produced appears to have an equal density of dots for all areas that are on the fractal.

The`makeptable`

function takes a fractal specification and produces a table of cumulative probabilities.
/makeptable { dup length array 0 0 1 3 index length 1 sub { 4 copy 4 -1 roll exch get 0 get add 3 -1 roll exch 4 -1 roll pop dup 4 1 roll put } for pop exch pop dup dup length 1 sub 1.0 put } bind defIn retrospect,

`makeptable`

was unnecessary, as you can produce a deviate from a given distribution without a cumulative probability table, just by repeatedly subtracting and comparing. Nonetheless, `randidx`

uses the table to produce a random index into the list of transformations, weighted by the probabilities.
/randidx { rand 2147483648.0 div 0 { 1 index 3 index 2 index get le { 3 1 roll pop pop exit } if 1 add } loop } bind defThe real work is done in

`randfractal`

; this is an implementation of Barnsley's random iteration algorithm, described above. The .0025 constants are the width and height of the dot drawn on the page. Using larger dots results in the fractal requiring fewer iterations but produces a coarser image.
/randfractal { dup makeptable /pmap exch def /eqns exch def /n exch def 0 0 1 1 n { 10 gt { 2 copy .0025 .0025 rectfill} if eqns pmap randidx get 1 get transform } for pop pop } bind defA quick function to conveniently scale and translate each rendered fractal...

/render { matrix currentmatrix 7 1 roll translate scale randfractal setmatrix } bind def... and finally the fractals can be plotted. Each line consists of a number of iterations, the name of the fractal, a position to translate to, a size to scale to, and a call to the

`render`

function.
40000 Sierpinski 200 200 100 300 render 200000 Fern 40 40 350 350 render 100000 Chaos 25 25 50 150 render showpage

Note the size of the file: it's around 2K. That's less than a tenth the size of the screenshot at the top of this page (which is just under 30K). Unlike that screenshot, the PS file can be rendered at any resolution, and (if the number of iterations and dot size are adjusted) will produce as much detail as the output device can handle.

As an experiment, I decided to see exactly how small I could get the code. This was also a good way to figure out exactly what was and was not legal in the language. My favourite trick was deliberately nesting the '[]' and '{}' brackets "incorrectly". In most languages, this would be invalid code; in PS, the left bracket is just a marker, and may be manipulated by other instructions. I used this to help compress the data, and to implement stack frames which could be popped more efficiently.

%! /B{bind def}def/r{roll}B/i{index}B/N{0 0 5 2 r]}B/R{0 5 1 r 0 3 1 r]}B/H{20 div .2}B/V{20 div -.2}B/f{matrix currentmatrix[9 2 r translate scale 0 0 1 1 5 -1 r{10 gt{2 copy .0025 dup rectfill}if 3 i[4 i rand 21474836.48 div 0{1 i 3 i 2 i get le{4 1 r]pop exit}if 1 add}loop get transform}for]pop setmatrix}B[[.5 .5 0 0 N[.5 .5 .5 0 N[.5 .5 0 .5 N][33 66 100]40000 200 200 100 300 f[[0 .16 0 0 N[.85 -.04 .04 .85 0 1.6][.2 .23 -.26 .22 0 1.6][-.15 .26 .28 .24 0 .44]][1 86 93 100]200000 40 40 350 350 f[[5 V 1 0 R[5 V 5 0 R[5 V 7 0 R[4 V 11 1 R[3 V 13 1 R[3 V 16 1 R[2 V 9 0 R[1 H 5 2 N[1 H 17 3 N[1 H 19 1 N[2 H 1 0 N[2 H 1 4 N[2 H 8 4 N[2 H 8 2 N[2 H 9 0 N[3 H 17 4 N[3 H 17 2 N[3 H 17 0 N[4 H 12 0 N[4 H 12 4 N][8 16 24 31 36 41 45 47 49 51 55 59 63 67 71 76 81 86 93 100]100000 25 25 50 150 f showpage |

- If you're a Windows user and can't work out how to display a PostScript file, you probably need GSView and GhostScript
- A First Guide to PostScript
- MDW Consulting have PostScript page with a complete list of Postscript operators
- Other people have written PostScript programs to generate fractals: here are some

- The fern fractal, and the original random iteration algorithm are both from Barnsley
- The transformations for the "chaos" fractal were designed by Robert Chrismas; it was his own program based on Barnsley's algorithm which inspired me to write this implementation.
- The fern decomposition image is public domain
- PostScript is a trademark of Adobe Systems Incorporated

[1] Actually, the fern is (like Sierpinski's Triangle) a pretty standard example; the first to use it was (probably) Barnsley

[Barnsley] Michael Barnsley, *Fractals Everywhere* (ISBN 0-12-079062-9)

© 2006 Will Benfold (email: will AT benfold DOT com)

This work is licensed under a Creative Commons Attribution 2.5 License.