CS 261 Lab G - Fractal Drawing

Due Wed Mar 12 at 9:00am

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 Step 1. If you draw similar, but smaller, H shapes at the end of each leg, you get the second shape (Step 2). Continuing that process until the line segments are too small to draw gives you the final shape (Step N).

1 Iteration
2 Iterations
N 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.

In this lab, you will be writing methods to draw two simple factal images. You will draw one of either the above H-Tree or the Sierpinski Triangle, and one of either a fractal tree or the Koch Snowflake.

This lab will be completed in pairs. Partner assignments for this lab can be found on Moodle

Objectives

Necessary Files

You will need a copy of the FractalLab.zip file. This file contains two classes you will need to import into Eclipse. DrawableFrame is a JFrame that you can draw on (by passing an image to). FractalDrawing is an abstract class that you should use as the basis for your own drawings. This class provides functionality to initialize the frame, and provides you with a Graphics2D object that you can draw on. Do not modify either of these classes, simply use their methods! If you find that you're modifying them to make your code work, then you're doing it wrong!

The FractalDrawing class also has a couple of helpful methods you may want to use. Calling showFractal() will make your drawing so far appear in the frame, so you can use it as a kind of "refresh" method while you're drawing. Calling wait() will make your program "pause" for a moment. You can use this to slow down the drawing so that you can see what's happening. On my computer, a pause time of 0 milliseconds is instantaneous, and pause time of 5-10 milliseconds looked good. Use whatever time is needed

Assignment Details

The Fractals

This section details the fractals you will need to implement. Remember, you only need to implement two of these: pick one of either the H-Tree or the Sierpinksi Trangle, and one of the fractal tree or the Koch Snowflake.


1a. The H-Tree

The H-Tree is one of the simplest fractals to understand and program. You begin by drawing a vertical line with two (shorter) horizontal 'legs' like a sideways H (Figure H1). Then, at the ends of each 'leg', draw the same shape, rescaled (Figure H2). The process continues until the line segments are too small to draw (e.g., a single pixel or less). The result is a grid-like image (Figure H3).

Figure H1
Figure H2
Figure H3

IMPORTANT NOTE: Your H-Tree will draw one "leg" at a time; thus you will never see a figure that looks like H2. Instead, you'll see a single corner of the H-Tree get drawn, growing in a kind of spiral.

To draw the H-Tree, you will need the horizontal coordinate of the central segment and the y coordinates of the two endpoints (though you can even get away with just having the center of the H and the length of the different segments!). You will also need a ratio to specify the lengths of the 'legs' relative to the length of the central segment. Thus the signature for your recursive method might look like this: 

    private void drawH(int x1, int y1, int y2, double ratio)

where (x1, y1) and (x1, y2) are the coordinates of the endpoints of the central segment and ratio is the relative length of each leg.

The above images were generated with a ratio of 0.5; you should experiment with different ratios to see the effects.


1b. The Sierpinski Triangle

The Sierpinski Triangle Fractal is 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.

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 drawSierpinski(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.

Note that the vertices can be anywhere. That is, the triangle does not have to be equilateral or isosceles. Try drawing out Sierpinski Triangle that is neither!


2a. The Fractal Tree

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

Figure P1
Figure P2
Figure P3

You will need an initial spot (the base of the trunk) to draw each recursive tree. You should also use some passed in ratio (similar to with the H-Tree) to determine how much to shrink the next trunk; 0.8 is a good number.

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

You will need to have some way of telling your tree when to stop recursing. You should pass in a value that indicates how many iterations to complete (e.g., how many times we want to send out helper cats). Thus your recursive method signature might look like: 

    public void drawTree(int x, int y, int length, double trunkAngle, double splitAngle, double ratio, int iterations)

2b. The Koch Snowflake

The Koch Snowflake is the most 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 Kock 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 alreadt!

Figure P1
Figure P2
Figure P3
Figure P4

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

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. You will also want to keep track of how many iterations you have gone through, so that you can stop (4 or 5 ended up being a good number for me--though again, you can stop when your segments are too short to subdivide).

Thus overall your recursive method signature might look like: 

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

Extensions

You are welcome to implement more than one of the fractals if you have time. This can be worth a few points of extra credit.

You can have lots of fun with using different colors for different parts of the recursive drawings, to make really neat images!

You are welcome to implement more than one of these fractals if you have time. There are lots of other amazing fractals out there, including the infamous Mandelbrot Set

You might also have fun creating a new FractalFrame that has different buttons used to draw the different fractals. Note that you would need to adjust the FractalDrawing class to not create its own frame.

Submitting

Make sure both your names are on BOTH of your Fractal classes (you will be marked down if they are not). Once you're finished, upload the src code to the LabG submission folder on vhedwig. Only one partner needs to upload the code--we will only grade one partner's copy of the program. Make sure you upload your work to the correct folder! The lab is due at the start of class the day after lab.

After you have submitted your solution, log onto Moodle and submit the Lab G Partner Evaluation. Both partners need to submit evaluations.

Grading

This assignment will be graded out of 15 points: