Julia Sets

Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.
Wiki Markup
{style}
cite{font-family:Courier New; font-style:normal}
{style}

h2. Project Overview

!Screen shot 2011-12-03 at 9.58.40 PM.png|width=400, align=right, border=1!

Given a function such as f\(x) = x^2 + c, you can iterate it as many times as you like by computing f(f(...f(f\(x))...)).  In general, inserting a real number into such an equation will result in the iteration growing towards infinity.  If c=0 and x<1, though, it will shrink to zero.  In fact, when c=0 and x=1, iterating the function does not change the value at all\!

When you generalize this to allow for complex numbers, then the behavior becomes more interesting.  A given value for c may have several _attractors_, such as zero and infinity in the example above.  Sometimes iterating a certain value enters into an orbit -- perhaps it rotates between a finite number of points.  Usually nearby points have the same behavior.  The boundaries between regions with different behavior compose the Julia set of the function.

Recall that complex numbers, written x + iy, can be thought of as coordinates on a two-dimensional plane, such as an image.  Using this relationship, we can visualize the Julia set of a function by coloring pixels (which correspond to a sampled complex number) based on their behavior over iterations in the function.

It is difficult (though by no means impossible) to detect orbiting points, but it is quite simple to tell if a value is increasing without bound.  A point ...

Lisp's functionality provides convenient aspects to visualize Julia sets in this way.

\\
\\
\\

h2. Writing an Image File
In \\
order to display a Julia set, we first need a way to output an image.  The file format ppm is simple to create.  After a header which specifies a few parameters (including the dimensions of the image), you just have to write the rgb values in bytecode.  We open a stream with ??with-open-file??, which is described in [LPE:Input&Output].  Here we open it with a specified ??element-type?? of ??unsigned-byte 8?? since we need to write bytecode.
{table}{tr}{td}{code: align=right}
(defun write-ppm(filename colors cols rows)
  ; open file st
  (with-open-file (st filename
		:element-type '(unsigned-byte 8)
		:direction :output
		:if-exists :supersede
		:if-does-not-exist :create)
      ; P6 means colors are in byte-code (P3 for ASCII)
      ; \~a prints object without escape chars, such as quotes
      ; 255 indicates the max color (intensity)
      (let (( header (format nil
            "~&P6~&~a ~a~&~a~%" cols rows 255) ))
	 (loop for char across header do
	    (write-byte (char-code char) st)))

      (loop for x from 0 to (- cols 1) do
	  (loop for y from 0 to (- rows 1) do
	      (let ((pixel (nth x (nth y colors)) ))
		  (write-byte (max 0 (min 255
                       (floor (* 255 (car pixel))))) st)
		  (write-byte (max 0 (min 255
                       (floor (* 255 (cadr pixel))))) st)
		  (write-byte (max 0 (min 255
                       (floor (* 255 (caddr pixel))))) st)
	       )
	   )
       )
   )
filename)
{code}{td}{td}

In order to display a Julia set, we first need a way to output an image.  The file format ppm is simple to create.  After a header which specifies a few parameters (including the dimensions of the image), you just have to write the rgb values in bytecode.  We open a stream with ??with-open-file??, which is described in [LPE:Input&Output].  Here we open it with a specified ??element-type?? of ??unsigned-byte 8?? since we need to write bytecode.

Lisp has a ??write-byte?? function which writes the binary representation of an integer to the specified stream.  The format is ??(write-byte integer stream)??.  To write characters we use the ??char-code?? function to convert characters into integers which can be written.  Entire strings (such as the header) must be written out one character at a time.  To do so we use a for-each loop, which is an example of an imperative structure which has worked its way into the Common Lisp language.  The syntax is similar to that of any other language.  Semantically, it just executes the body for each character in the string ??header??.

To write out every pixel's rgb values we use a different loop structure.  This one is like the conventional ??for?? loop that iterates over a specified range of integers.  Lisp provides other looping options as well.  The nested loops access every pixel in a two-dimensional list, which is a large list containing lists of rows of pixels (which are themselves lists of three elements).  That is, colors = \[ row1 row2 ... rowN \] where rowi = \[pixeli1 pixeli2 ... pixeliN] and pixelij = \[r g b\].  In Lisp, an image with one row and three columns is written as ??(list (list '(.7 .3 .13) '(.45 .8 .1) '(.23 0 .73) ))??.

The colors need to ;be letintegers usbetween write0 binaryand data255 tofor athe fileppm, ;but directour stream to output
; overwrite existing file

; write PPM file header to the file
; "P6~%" 		     ; P6 means colors are in byte-code (P3 for ASCII)
; "~a \~a \~%" cols rows  ; \~A prints object without escape chars, such as quotes
; "~a~%" 255            ; max color (intensity)
functions for visualizing the Julia set produce numbers between 0 and 1 to be interpreted as colors.  Before we can write out the colors we scale them to 255 and then cap the values at 0 and 255 with ??max?? and ??min?? in case some numbers were outside the expected range.

{td}{tr}{table}

h2. Generating the Image
{table}{tr}{td}{code}
;calculates a Julia Set from -1.5(1+i) to 1.5(1+i)
;with precision corresponding to rows&cols
(defun calculateMatrix (rows cols)
    (labels ( 
       (calcMatrix-util (i rows cols)
          (if (= i rows)
            '()
            (cons (calculateRow i 0 rows cols)  
                  (calcMatrix-util (+ i 1) rows cols) )
        ))
        (calculateRow (i j rows cols)
           (if (= j cols)
              '()
               (cons (getColor (+(* (/ i rows) 3) -1.5) 
                               (+ (* (/ j cols) 3) -1.5))
                      (calculateRow i (+ j 1) rows cols) )
            ) 
        ))
 (calcMatrix-util 0 rows cols) )
)
{code}{td}{td}

In Lisp you usually create lists recursively: one element at a time, which you add to the beginning of the rest of the list.  To make a two-dimensional list in an imperative style, you could use nested for-loops (similarly to how we read the list above).  In the functional style, this requires two recursive functions.  We define these helper functions in a ??labels?? block, which is a special operator described in [LPE:Functions].

{td}{tr}{table}