## PostScript FractalsIn memory of Robert Chrismas
## FractalsRoughly speaking, any structure is said to be It turns out that knowing exactly how the picture is self-similar is the ## The Mathsy BitWe could represent transformations as 2x2 matrices, but we want to be able to translate too, so we express the transformations as 3x3 matrices with 6 nontrivial elements: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 could describe a fern as an infinitely many smaller ferns placed in two lines, we don't. Instead, we break down the fern's self-similarity into just four transformations. Note that we^{1} can describe the fern in terms of a finite number of copies of itself; one for the first leaf on each side, one squashed to a line for the stem, and one shrunk a little for the whole of the rest of the fern.
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. ## PostscriptPostScript 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! ## My Code...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 ## PS can be small...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.
## Further information- 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
## Credits- 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
## Footnotes[1] Actually, the fern is (like Sierpinski's Triangle) a pretty standard example; the first to use it was (probably) Barnsley ## References[Barnsley] Michael Barnsley, |

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

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