Assignment 3A: Fractals

Overview

In this part of the assignment, you will write several recursive functions related to drawing graphics for two types of fractals: the Sierpinski Triangle and the Mandelbrot Set.

Quickly jump to:

Sierpinski Triangle Mandelbrot Set Recursive Tree (Optional) Extra Features FAQ

Sierpinski Triangle

If you search the web for fractal designs, you will find many intricate wonders beyond the ones illustrated in lecture. One of these is the Sierpinski Triangle, named after its inventor, the Polish mathematician Waclaw Sierpinski (1882-1969). The order-1 Sierpinski Triangle is an equilateral triangle:

The orders greater than 1, however, are more interesting:

Order-2

Order-3

... Order-6

To create an order-K Sierpinski Triangle, you draw three Sierpinski Triangles of order K-1, each of which has half the edge length of the larger order-K triangle you want to draw. Those three triangles are positioned in what would be the corners of the larger triangle; together they combine to form the larger triangle itself.

For this problem, you will write a recursive function that draws the Sierpinski triangle fractal image. Your solution should not use any loops; you must use recursion. Do not use any data structures in your solution such as a Vector, Map, arrays, etc.

void drawSierpinskiTriangle(GWindow& gw, double x, double y,
                            double size, int order)

Your function should draw a black outlined Sierpinski triangle when passed the following parameters: a reference to a graphical window, the x/y coordinates of the top/left of the triangle (note that the triangles you draw will be inverted), the length of each side of the triangle, and the order of the figure to draw (i.e., 1 for an order-1 triangle). The provided code already contains a main function that pops up a graphical user interface to allow the user to choose various x/y positions, sizes, and orders. When the user clicks the appropriate button, the GUI will call your function and pass it the relevant parameters as entered by the user. The rest is up to you.

Some students mistakenly think that some levels of Sierpinski triangles are to be drawn pointing upward and others downward; this is incorrect. The upward-pointing triangle in the middle of the Order-2 figure is not drawn explicitly, but is instead formed by the sides of the other three downward-pointing triangles that are drawn. That area, moreover, is not recursively subdivided and will remain unchanged at every order of the fractal decomposition. Thus, the Order-3 Sierpinski Triangle has the same open area in the middle.

We have not learned much about the GWindow class or drawing graphics, but you do not need to know much about it to solve this problem (for your reference, however, here is the complete GWindow documentation). The only member function you will need from GWindow for this problem is the drawLine() function:

Member	Description
gw.drawLine(x1, y1, x2, y2);	draws a line from point (x1, y1) to point (x2, y2)

You may find that you need to compute the height of a given triangle so you can pass the proper x/y coordinates to your function or to the drawing functions. Keep in mind that the height h of an equilateral triangle is not the same as its side length s. The diagram below shows the relationship between the triangle and its height. You may want to look at information about equilateral triangles on Wikipedia and/or refresh your trigonometry.

One particular type of solution we want you to avoid would be to write a pair of functions, one to draw "downward-pointing" triangles and another to draw "upward-pointing" triangles, and to have each function call the other in an alternating fashion. This is a poor solution because it does not capture the self-similarity inherent in this fractal figure.

Another thing you should avoid is re-drawing the same line multiple times. If your code is structured poorly, you end up re-drawing a line (or part of a line) that was already drawn, which is unnecessary and inefficient. If you aren't sure whether your solution is redrawing lines, try making a counter variable that is incremented each time you draw a line and checking its value against the number of lines you know your triangle ought to require.

If the order passed is 0, your function should not draw anything. If the x or y coordinates, the order, or the size passed are negative, your function should throw an exception. You can do this by calling the built-in throw function, which takes a string parameter containing a description of the error that occurred. The throw function will terminate the program. Otherwise, you may assume that the window passed is large enough to draw the figure at the given position and size.

Mandelbrot Set

Another fascinating fractal is the "Mandelbrot Set", in tribute to Benoit Mandelbrot, a mathematician who investigated this phenomenon. The Mandelbrot Set is recursively defined as the set of complex numbers, c, for which the function f_c(z) = z² + c does not diverge when iterated from z=0. In other words, a complex number, c, is in the Mandelbrot Set if it does not grow without bounds when the recursive definition is applied. The complex number is plotted as the real component along the x-axis and the imaginary component along the y-axis.

For example, the complex number 0.2 + 0.5i is in the Mandelbrot Set, and therefore, the point (0.2, 0.5) would be plotted on an x-y plane. For this problem, you will map coordinates on an image (via a Grid) to the appropriate complex number plane (note that for this problem, we have abstracted away many details to make the coding easier).

Formally, the Mandelbrot set is the set of values of c in the complex plane that is bounded by the following recursive definition:

In order to test if a number, c, is in the Mandelbrot Set, we recursively update z until either of the following conditions are met:

1. The absolute value of z becomes greater than 4 (it is diverging), at which point we determine that c is not in the Mandelbrot Set; or,
2. We exhaust a number of iterations, defined by a parameter (usually 200 is sufficient for the basic Mandelbrot Set, but this is a parameter you will be able to adjust), at which point we declare that c is in the Mandelbrot Set.

Because the Mandelbrot Set utilizes complex numbers, we have provided you with a Complex class that contains the following member functions (#include "complex.h" to use it):

Function	Description
Complex(double a, double b)	Constructor that creates a complex number in the form a + bi
cpx.abs()	returns the absolute value of the number (a double)
cpx.real()	returns the real part of the complex number
cpx.imag()	returns the coefficient of the imaginary part of the complex number
cpx1 + cpx2	returns a complex number that is the addition of two complex numbers
cpx1 * cpx2	returns a complex number that is the product of two complex numbers

Implementation Details

For this problem, you will write three functions that work together to generate the Mandelbrot Set in a graphical window, as described here. One of your functions will be recursive. Your solution may use loops to traverse a grid, but you must use recursion to determine if a particular point exists in the Mandelbrot Set.

// makes the window display the Mandelbrot Set fractal
void mandelbrotSet(GWindow& gw, double minX, double incX,
				   double minY, double incY, int maxIterations, int color)

/* non-recursive function that returns the number of iterations it
 * takes for c to diverge with z starting at 0.  If it returns
 * maxIterations, then c is assumed to be in the Mandelbrot Set.
 * If it returns less than maxIterations, then c diverged before
 * then and it is considered not in the Mandelbrot set.
 */
int mandelbrotSetIterations(Complex c, int maxIterations)

/* recursive function that returns the number of iterations it
 * takes for c to diverge with the given z.  If it returns
 * remainingIterations, then c is assumed to be in the Mandelbrot Set.
 * If it returns less than remainingIterations, then c diverged before
 * then and it is considered not in the Mandelbrot set.
 */
int mandelbrotSetIterations(Complex z, Complex c, 
                            int remainingIterations)

One of the most interesting aspects of the Mandelbrot Set is that it has an infinitely large self- similarity. In other words, as you zoom into the Mandelbrot Set, you see similar features to an unzoomed Mandelbrot Set. The GUI for this assignment has been set up to allow zooming, based on where the user clicks on the current Mandelbrot Set in the window. The user may click on an area to zoom in, or shift-click on an area to zoom back out.

mandelbrotSet()

Your mandelbrotSet() function will be passed in a number of parameters that you will use to determine which pixels in the zoomed window will be in the Mandelbrot Set, the number of iterations you will use in the recursion, and the color(s) of the resulting image. The details of the parameters are described below.

void mandelbrotSet(GWindow& gw, double minX, double incX,
				double minY, double incY, int maxIterations, int color)

The gw parameter is the same as in the other parts. In the starter code, we have already calculated the height and width of the window, created an image for the window, and created a grid based on that image. The grid is composed of individual pixel values (ints) that you can change based on whether or not a pixel is "in the Mandelbrot Set" or not. How to color the pixels is described below.

void mandelbrotSet(GWindow& gw, double minX, double incX,
				double minY, double incY, int maxIterations, int color)

The minX, incX, minY, and incY parameters define the range of values you will inspect for inclusion in the Mandelbrot Set. minX corresponds to the left-most column in your grid, and it forms the real part of the first point you should check. minY corresponds to the top-most row in your grid, and it forms the coefficient of the imaginary part of the first point you should check. In other words, the first point you check will be the complex number minX + minYi, which you could create as follows: Complex coord = Complex(minX, minY).

The incX and incY parameters have already been scaled to the size of the GWindow, and they provide the increment amount you should use as you traverse the pixel grid. For example, the pixel at row=3, col=5 would have the following coordinate: Complex(minX + 5 * incX, minY + 3 * incY);

void mandelbrotSet(GWindow& gw, double minX, double incX,
				double minY, double incY, int maxIterations, int color)
				

The maxIterations parameter is the number of iterations that you should test to see if a complex number has diverged - use this when calling the mandelbrotSetIterations function, below. If a complex number does not diverge after this many iterations, then it is considered in the Mandelbrot set, and if it does diverge (absolute value greater than 4) within this many iterations then it is not considered in the Mandelbrot set. In the GUI, the "size" value determines the maxIterations, and if you do not enter this value in the GUI, it defaults to 200 iterations. Note that the number of iterations places an O(n²) complexity on your calculation, so it can be slow. However, the more you zoom, the more iterations you will need to determine whether a point is in the Set, and the more precise your results will be.

void mandelbrotSet(GWindow& gw, double minX, double incX,
			double minY, double incY, int maxIterations, int color)

The color parameter is used to determine the color of your picture. If the color that is passed in is non-zero, you can simply use that number in your grid to show that a coordinate is in the Mandelbrot Set. In other words, if your mandelbrotSetIterations() function returns maxIterations for a coordinate, then you should set the pixel you are working on to color.

If, however, the color is zero, you should use the palette of colors, based on the result from your mandelbrotSetIterations() function. The calculation is a simple one:

pixels[r][c] = palette[numIterations % palette.size()];

mandelbrotSetIterations()

int mandelbrotSetIterations(Complex c, int maxIterations)
int mandelbrotSetIterations(Complex z, Complex c, 
                               int remainingIterations)
				

These functions will return a number of iterations needed to determine whether or not the coordinate is unbounded. If the function returns the iterations parameter it was given, we consider the coordinate to be in the Mandelbrot Set. If it returns a number less than that, then the coordinate is not in the Mandelbrot Set. The reason we do not simply return a bool is because we can use the number of iterations to provide a range of pretty colors, based on the palette (see above).

These two functions have the same name (they are "overloaded"), but they have different parameters. You should plan on having your mandelbrotSet() function call the first function, which in turn calls the second function to perform the recursion. In this case, we call the second function a "helper" function, because it performs the recursion and in this case is used to pass along the z parameter (which, by the recursive definition, starts at zero). The helper function performs the recursion and returns the number of iterations back to the first function, which in turn passes the result back to the original mandelbrotSet() function. The mandelbrotSet() function uses this information to color the grid pixel (or not), based on the result.

(Extra Credit) Recursive Tree

For this problem, write a recursive function that draws a tree fractal image as specified here. Note that your solution is allowed to use loops if they are useful to help remove redundancy, but that your overall approach to drawing nested levels of the figure must still be recursive. Do not use any data structures in your solution such as a Vector, Map, arrays, etc.

Our tree fractal contains a trunk that is drawn from the bottom center of the applicable area (x, y) through (x + size, y + size). The trunk extends straight up through a distance that is exactly half as many pixels as size.

The drawing below is a tree of order 5. Sitting on top of its trunk are seven trees of order 4, each with a base trunk length half as long as the prior order tree’s trunk. Each of the order-4 trees is topped off with seven order-3 trees, which are themselves comprised of seven order-2 trees, and so on.

The parameters passed to your function are, in order: the window in which to draw the figure; the x/y position of the top left corner of the imaginary bounding box surrounding the area in which to draw the figure (more details on this just below); the side width/height of the figure (i.e., the overall size of the square boundary box; see below); and the number of levels, i.e., the order, of the figure.

void drawTree(GWindow& gw, double x, double y, double size, int order)

Some of these parameters are somewhat unintuitive. For example, the x/y coordinates passed are not the x/y coordinates of the tree trunk itself, but rather the coordinates of the bounding box area in which to draw the tree. The following diagram attempts to clarify the parameters visually:

Lengths: As this drawing also shows, the trunks of each of the seven subtrees are exactly half as long of their parent branch's length in pixels.

Angles: The seven subtrees extend from the tip of the previous tree trunk at relative angles of ±45, ±30, ±15, and 0 degrees relative to their parent branch's angle. For example, if you look at the Order-1 figure (below), you can think of it as a vertical line drawn in an upward direction and facing upward, which is a polar angle of 90 degrees. In the Order-2 figure, the seven sub-branches extend at angles of 45, 60, 75, 90, 105, 120, and 135 degrees; etc.

Colors: Inner branches (i.e., branches drawn at order 2 and higher) should be drawn in the color #8b7765 (r=139, g=119, b=101), and the leafy fringe branches of the tree (i.e., branches drawn at level 1) should be drawn in the color #2e8b57 (r=46, g=139, b=87).

The images below show the progression of the first five orders of the fractal tree figure:

Order-1

Order-2

Order-3

Order-4

Order-5

You should use the GWindow object's drawPolarLine() function to draw lines at various angles, and its setColor() function to change drawing colors.

Member	Description
gw.drawPolarLine(x0, y0, r, theta); gw.drawPolarLine(p0, r, theta);	draws a line the given starting point, of the given length r, at the given angle in degrees theta relative to the origin
gw.setColor(color);	sets color used for future shapes to be drawn, either as a hex string such as "#aa00ff" or an RGB integer such as 0xaa00ff

If the order passed is 0, your function should not draw anything. Similarly, if the x or y coordinates, the order, or the size passed is negative, your function should throw an exception. Otherwise, you may assume that the window passed is large enough to draw the figure at the given position and size.

Possible Extra Features

Here are some ideas for extra features that you could add to your program for a very small amount of extra credit:

• Sierpinski colors: Make your Sierpinski triangle draw different levels in different colors.
• Mandelbrot Set Gradient: The Wikipedia page on the Mandelbrot Set discusses ways to make a smooth gradient for the images, as opposed to using a palette. Implement a smooth gradient in your code.
• Mandelbrot Set iterations: The number of iterations needed to get a clear picture depends on the zoom. In the GUI, you can manually set this value, but you might want to use the minX, incX, and minY, incY parameters to determine the number of iterations, rather than the maxIterations passed into the function.
• (Advanced) Mandelbrot Parallelism: Every point in the Mandelbrot set is independent of every other point, and thus this part of the assignment can be parallelized. You might do this using PThreads.
• Add another fractal: Add another fractal function representing a fractal image you like. You'll have to do some reconstructive surgery on the GUI to achieve this, and/or swap it in place of one of the existing fractal functions (make sure to turn in your non-extra-feature version first, so as not to lose your solution code).
• Other: If you have your own creative idea for an extra feature, ask your SL and/or the instructor about it.

Indicating that you have done extra features: If you complete any extra features, then in the comment heading on the top of your program, please list all extra features that you worked on and where in the code they can be found (what functions, lines, etc. so that the grader can easily identify this code).

Submitting a program with extra features: Since we use automated testing for part of our grading process, it is important that you submit a program that conforms to the preceding spec, even if you want to do extra features. If your feature(s) cause your program to change the output that it produces in such a way that it no longer matches the expected sample output test cases provided, you should submit two versions of your program file: a first one with the standard file name with no extra features added (or with all necessary features disabled or commented out), and a second one whose file name has the suffix -extra.cpp with the extra features enabled. Please distinguish them by explaining which is which in the comment header. Our submission system saves every submission you make, so if you make more than one we will be able to view them all; your previously submitted files will not be lost or overwritten.

Frequently Asked Questions (FAQ)

Q: I'd like to write a helper function and declare a prototype for it, but am I allowed to modify the .h file to do so?

A: Function prototypes don't have to go in a .h file. Declare them near the top of your .cpp file and it will work fine.

Q: The spec says that I need to throw an exception in certain cases. But it looks like the provided main program never goes into those cases; it checks for that case before ever calling my function. Doesn't that mean the exception is useless? Do I actually have to do the exception part?

A: The exception is not useless, and yes you do need to do it. Understand that your code might be used by other client code other than that which was provided. You have to ensure that your function is robust no matter what parameter values are passed to it. Please follow the spec and throw the exceptions in the cases specified.

Q: Is the Sierpinski code supposed to be slow when I put in a large, value for N like 15?

A: Yes; keep in mind that the program is drawing roughly 315 triangles if you do that. That is a lot of triangles. We aren't going to test you on such a high order fractal.

Q: Are the Sierpinski triangles supposed to exactly overlay each other? Mine seem to be off by ~1 pixel sometimes.

A: The off-by-one aspect is because the triangle sizes are rounded to the nearest integer. You don't have to worry about that, as long as it is only off by a very small amount such as 1 pixel.

Q: What does it mean if my program "unexpectedly finishes"?

A: It might mean that you have infinite recursion, which usually comes when you have not set a proper base case, or when your recursive calls don't pass the right parameters between each other. Try running your program in Debug Mode (F5) and viewing the call stack trace when it crashes to see what line it is on when it crashed. You could also try printing a message at the start of every call to make sure that you don't have infinite recursion. If you are certain that you do not have infinite recursion, it is possible that there are just too many calls on the call stack because you are filling a very large area of the screen. If you tried to fill the whole screen with the same color, it might crash with a "stack overflow" even if your algorithm is correct. This would not be your fault.

Q: Can I use one of the STL containers from the C++ standard library?

A: No.

Q: I already know a lot of C/C++ from my previous programming experience. Can I use advanced features, such as pointers, on this assignment?

A: No; you should limit yourself to using the material that was taught in class so far.

Q: Can I add any other files to the program? Can I add some classes to the program?

A: No; you should limit yourself to the files and functions in the spec.

Q: My Mandelbrot output doesn’t exactly line up with the output in the program!

A: This may be because the window size is a bit different than when we generated our example output. Don’t worry too much about it — it should look very similar and be positioned close. The exact pixels do not need to perfectly overlap.