Due: 11:59 p.m., Tuesday, April 10
Summary: You will write procedures that create fractal images using numeric recursion with several image models.
Purposes: To gain further experience with numeric recursion. To gain further experience with deep recursion. To make neat images.
Collaboration: We encourage you to work in groups of size two. You may, however, work alone or work in a group of size three. You may discuss this assignment with anyone, provided you credit such discussions when you submit the assignment.
Email your answer to
<firstname.lastname@example.org>. The title of your email
should have the form
should contain your answers to all parts of the assignment. Scheme code
should be in the body of the message.
Warning: So that this assignment is a learning experience for everyone, we may spend class time publicly critiquing your work.
A common fractal is the Sierpinksi carpet, which is constructed by removing portions of a square. (Other Sierpinski forms can be constructed by removing portions of other figures, such as triangles.) In particular, one can think of a square has being broken up into a three-by-three grid of smaller squares. If we remove the central square, such a figure might look like the following.
There are then eight squares left. We can repeat the same process on each of those eight squares, yielding something like the following.
With a few more recursive steps, we end up with an interesting “carpet”.
How might we accomplish the construction of the Sierpinksi carpet in Scheme? We can use the GIMP tools to select the portions of the carpet, and then unselect the portions we remove.
If we treat Sierpinski drawing as selecting the carpet, rather than drawing the carpet, we can then do all sorts of interesting things with the selection. We can, for example, fill it with a blend, rather than a single color.
(selection-compute-pixels! image (lambda (col row) (rgb-new col 0 row)))
We might also find it useful to stroke the selection, perhaps with multiple sizes of brushes in different colors. For example, the following is made by stroking the selection with (in sequence) a black "Circle (11)" brush, a grey "Circle (09)" brush, a light grey "Circle (07)" brush, and a white "Circle (03)" brush.
So, how do we make the carpet? We can first select the entire image, and then unselect all the holes. A procedure to that uses this algorithm might begin something like the following.
(define image-select-sierpinski-carpet! (lambda (image recursion-depth) (letrec ((unselect-holes! (lambda (n top left width height) (let ((w (/ width 3.0)) (h (/ height 3.0))) (when (and (>= w 1) (>= h 1)) (image-select-rectangle! image SUBTRACT (+ left w) (+ top h) w h) ...))))) (image-select-all! image) (unselect-holes! recursion-depth 0 0 (image-width image) (image-height image)))))
We then need to fill in appropriate code to recurse (and to decide when it has recursed to the desired depth). Add that code.
The so-called Koch Star or snowflake is a straightforward, yet visually interesting fractal. It belongs to a family of fractals called Lindenmayer systems that are described via a series of recursive "modifications" or re-write rules. Before describing the technical aspects of what this means, it may be useful to gain a more intuitive understanding of the process.
Beginning with an equilateral triangle (the base case), one recursively modifies each side of the triangle as follows:
This process is repeated (recursively) as many times as desired on each side of the two new segments.
More generally, Lindenmayer re-write systems are described via four elements:
This system is best implemented using the turtle model of drawing. In this system, the symbol "F" means "draw forward" a specified length, "+" means "turn right 60 degrees", and "-" means "turn left 60 degrees".
Write a procedure
that implements the Koch-snowflake rewrite rules as given
above. Your procedure should be an implementation of the axiom,
which makes calls to a recursive procedure specified by the
production rule. The recursion should proceed to a depth
and the initial distance for the "F"
command should be
that with each recursive call, the side length will change.
Note: You may wish to write non-recursive helper procedures to implement the "+" and "-" commands, as well as a recursive helper procedure to implement the "F" command. In implementing the "F" rule, you only need to move the turtle forward when you've reached the base case (the specified depth). Otherwise, "F" represents a recursive call, and there is no need to explicitly move the turtle.
Of course, the basic Sierpinski carpet is quite regular and symmetrical. As you've noted, some artists worry about such symmetry and regularity in images. Can we add some visual interest? One possibility is to divide the square up into non-equal portions. In the following, we've used the basic Sierpinski technique of removing a middle portion, but have used different criteria for determining that portion. (In this case, the middle portion is 2/5 of the width and 1/2 of the height, centered vertically and 2/5th of the way across.)
Using any techniques you deem appropriate, create an interesting pattern using a variant of the Koch star approach, the Sierpinski carpet approach, or a combination thereof.
Please include instructions for generating the image you wish to have evaluated. If you write a procedure, be sure to include a call to your procedure with specific parameters for generating the image.
If your code takes more than a couple of minutes to run, then please attach one or two images. Otherwise, there is no need to attach any images; we'll follow your instructions generate them ourselves.
We will judge your code on clarity, concision and correctness. We will judge the images that you produce on how compelling and clever the image you produce is.
Janet Davis (email@example.com)