CS 161 Mini Lab - Fractal Drawing

In class

Overview

A fractal image is an image in which every small subsection is the same as the larger image it is a part of--if you keep zooming in on the image, you just keep seeing the same thing. These images are defined recursively--each piece of the image contains a copy of itself, and so on.

For example, consider the simple sideways H (It's an H, not an I!) shape labeled (a). If you draw similar, but smaller, H shapes at the end of each leg, you get the second shape (b). Continuing that process until the line segments are too small to draw gives you the final shape (c).

(a) 1 Iteration
(b) 2 Iterations
(c) Many Iterations

Although this is just a simple example (less than a dozen lines of code), more complicated images can be just as easy. Indeed, simple recursive rules like this can produce all kinds of amazing artwork. I particularly like images from the infamous Mandelbrot Set: (See more images on Wikipedia, for example. These are fun to look at!).

In this mini-lab, you will be writing a recursive method to draw one (or more!) simple fractal images.

Necessary Files

You will need to download and extract the BlueJ project from the FractalLab.zip file. This project contains two classes for you to use: DrawingCanvas which is a simple JPanel canvas (like we've used in the past, particularly in the Painter lab), and FractalDrawer which is a class you will fill with methods to draw fractals.

Sierpinski Triangle

  1. Open up the FractalDrawer class and inspect the code. This class instantiates a Canvas and fetches a Graphics2D brush that you can use for drawing.
  2. The fractal you should draw is the Sierpinski Triangle--a classic simple fractal. You begin by drawing a triangle (Figure S1). Then, by connecting the midpoints of the triangle's sides, you construct three triangles (Figure S2). Note the triangles are at the corners. The 'upside down' one in the middle is not a triangle, but is formed as a result of the other three. The process continues: in the next iteration, you connect the midpoints of the three smaller triangles to create three triangles in each one (Figure S3). Continuing this process, the resulting fractal image looks like Figure S4.
    Figure S1
    Figure S2
    Figure S3
    Figure S4

    IMPORTANT NOTE: Your Triangle will draw one "corner" at a time; thus you will never see a figure that looks like S3. Instead, you'll see a single corner of the triangle get drawn, growing down before filling in the next corner.

  3. Add a method to the FractalDrawer class called drawTriangle(). This will be a recursive method that draws a single triangle, and then recurses to draw the internal triangles.

    The only things you need to get started drawing a Sierpinski Triangle are the coordinates of the three vertices of the first triangle. So, the signature for your recursive method might look like this:

    private void drawTriangle(int x1, int y1, int x2, int y2, int x3, int y3)

    where (x1, y1) (x2, y2) and (x3, y3) are the coordinates of the initial triangle vertices.

  4. Start by having this code simply draw a triangle by connecting the given 3 points. You can use the brush instance variable and the drawLine() method.
  5. Call this method from the provided draw() method and make sure it works! You'll need to pass in the locations for the 3 points--these can be at whatever coordinates you want.
    • You can test your whole program by running the main() method in FractalDrawer.
  6. Next, try drawing a single triangle into one of the corners of your "big" triangle. But don't actually call drawLine() again, instead think about sending out a helper cat! Calculate the corner points for this new triangle, and then recurse (call the method again) to say "draw me another triangle!"
  7. Think careful about how to calculate the corner points. You'll need to get the midpoint of each edge--you can do this by averaging the endpoints of the edge.
  8. Take a moment to think carefully about what you told it to draw, and whether you got what you expected!
  9. The DrawingCanvas has a pause(int millisecs) method that will temporarily "pause" the drawing, allowing you to see the order in which things are drawn. Try calling this right before you recurse! You can call this method with:
    canvas.pause(1000); //pauses for 1000ms, or 1 second

    Pause times of 200 or 300 work well too.

  10. You'll need a stopping condition so that you don't have infinite recursion. Try making it so that you only recurse if the length of a side is greater than some small number (around 10 works pretty well).
  11. But you'd like to draw more than just the corner triangle--you actually need to draw 3 smaller triangles. Don't call drawLine() again, but think about sending out 3 helper cats, one after another!
    • This is a bit like how we sent out multiple helper cats to calculate Fibonacci numbers.
    • Try adjusting the pause time to be something small (like 5 or 10ms) and pausing before each recursive call. This will actually give you a nice animation about the order that things are drawn!

Other Fractals

There are lots of other fractals to draw if you have time. For example, you might try the H-Tree described at the top of the page, or the Fractal Tree or Koch Snowflake described below. You could also look at drawing a Sierpinski Carpet or T-Square

Other fun (but more difficult fractals) include the Dragon curve, Peano curve, or the Barnsley fern.

The Fractal Tree

This is a version of The Pythagoras Tree (or "tree fractal"), using lines instead of cubes. This fractal is a bit more complicated. You begin by drawing a 'trunk' for the tree. In the next step, you draw 'branches'--each of which is another Pythagoras tree's trunk! That is, the 'branches' become the 'trunks' in the next recursion (see Figure P1).

Figure P1
Figure P2
Figure P3

Note that P1 actually draws two iterations--there are 3 trees (the original trunk, and then two new trunks sprouting off that).

In order to have your tree grow out, you will need to have each new trunk spread out at an angle. This can be measured as the angle off the the horizontal axis (angle1 in Figure P2). In addition, your trunks will be splitting by a particular angle each time (angle2 in Figure P2)--so you can figure out the new angle for a new trunk by adding the split angle to the current angle.

Your trunks should get shorter each time you recurse, multiplying the previous length by some ratio (0.8 is a good number). You should stop recursing when the length is too short.

So overall, your recursive method signature might look like: 

drawTreeTrunk(int x, int y, int length, double currentTrunkAngle)

The Koch Snowflake

The Koch Snowflake is an even more complicated fractal (but is still not too bad)--mostly because it doesn't use tail recursion (where you recurse at the end of the method). To draw the Koch Snowflake, think about drawing line segments, where a segment is the side of a triangle (thus you will want to draw 3 segments).

Each time you draw a segment, you are going to subdivide that segment up into three smaller pieces (that are themselves segments): you draw a segment over the "first" 1/3 of the edge and a segment over the "third" 1/3 of the edge. But instead of drawing the middle segment, you draw a pair of shorter segments that would form a kind of new triangle. See the below figures (from Wikipedia) for an example.

Drawing each segment is a recursive call--instead of drawing that segment, you actually break it up into the three pieces, and so forth. Keep going until you hit a maximum number of steps (an iteration count, similar to with the Pythagoras tree), in which case you can stop dividing the segment and just draw the straight line already!

Figure P1
Figure P2
Figure P3
Figure P4

Note that the greens lines are for illustration purposes; you do not need to draw them!

Again, you recurse (break up) your segments until they are too short--when they are too short, you just draw a line instead of breaking them up. Thus you don't actually "draw" anything until you're at the "bottom" of your set of recursive calls.

The only things you'll need to draw the Koch snowflake are the starting x and y coordinates of the side of each triangle. Important! You'll need to keep your points in "order" (e.g., going clockwise) so that you build your fractal out instead of in.

Thus overall your recursive method signature might look like: 

public void drawSegment(int x1, int y1, int x2, int y2)

Submitting

This is just for practice in class, no submission necessary!