Generating Fractals with Affine Transformations

Fractal graphics lab with GP142

Author: David L. Dewey, ddewey@cs.washington.edu

NOTE: This lab is optional and ungraded, so there are no restrictions on what resources you can utilize to help you when you get stuck. Please feel free to work in groups or receive help from other students. Unlike with homework assignments, for this lab the consultants can give you direct answers to problems you are having trouble with. If you are struggling too much with a particular step, you might want to have a consultant or TA just give you the answer so you can move on to the next step.

In the first part of this lab you will learn about vectors, matrices, and affine transformations. In the second part you will generate beautiful fractal images by recursively applying a set of affine transformations to a vector and then plotting the resulting vectors using the GP142 graphics packages. If you are not familiar with GP142, you can read about it and download it at http://www.cs.washington.edu/education/courses/142/GP142/GP142.html. Completing this lab will strengthen your programming skills by giving you practice in functional decomposition, pointer parameters, arrays, nested data structures, file IO, and recursion.

Part I: Vectors and Matrices

Step 1: What are vectors?

A vector is simply a sequence of numbers. For example, (1, 2, 3) is a vector and so is (4.9, -23.5). Each number in a vector is called an entry. As you can see, vectors can have various numbers of entries. In this lab we will only deal with vectors that have two entries. Such vectors can be used to represent points on a plane, or pixels in the GP142 graphics window. We simply take the first entry in each vector to be the x-coordinate of a point, and the second entry to be the y-coordinate.

Vectors can be added much like real numbers can. Adding two vectors a and b results in a new vector c whose first entry is the sum of the first entries of a and b and whose second entry is the sum of the second entries of a and b. For example:

(1.0, 2.0) + (3.0, 4.0) = (1.0+3.0, 2.0+4.0) = (4.0, 6.0)

Create a new console-application project (don’t use GP142 yet). Create a struct named Vector that contains two doubles, x and y. Then define a function, add, that takes two pointers to Vectors and returns a new Vector that is their sum. Make another function that takes a pointer to a Vector as its parameter and prints out the Vector in a nice, readable way. Then test your add function by writing code that reads in four doubles from the user, creates two Vectors from the doubles, adds them, and prints the result.

`Step 2: What are Matrices?`

A matrix is a two-dimensional grid of numbers laid out in rows and columns. In this lab we will only deal with 2-by-2 matrices. 2-by-2 matrices have two rows and two columns and thus contain four entries. In this lab we will refer to these four entries as a, b, c, and d. These entries are laid out from left to right and top to bottom like this:

`a`	`b`
`c`	`d`

A 2-by-2 matrix and a 2-entry vector can be multiplied. The result of such a multiplication is a new vector. If A is the matrix above, and v is the vector (x, y), then A*v = (a*x+b*y, c*x+d*y). Note that unlike multiplication of real numbers, order is important in the multiplication of a matrix and a vector. Always write the matrix first. The other way around is not defined.

Declare a struct Matrix that contains doubles a, b, c, and d, representing the entries in a 2-by-2 matrix. Define a function multiply that takes a Matrix pointer as the first parameter, a Vector pointer as the second, and returns a new Vector that is the result of multiplying the Matrix by the Vector. Test this function like you did for the add function.

`Step 3: What is a linear transformation?`

You can think of the multiplication described above as taking one vector and transforming it into another. If the vector represents a point on the screen, then multiplying the vector by a matrix generates a new point on the screen. The nature of the transformation depends on the specific entries of the matrix. Such a transformation is called a linear transformation. Given a whole set of vector points, applying a linear transformation can rotate, scale, shear, and reflect the points in the set. For example, if the points represent an image on screen, a linear transformation might enlarge, stretch, skew, or mirror the image. The exact effect would depend on the entries in the matrix.

`Step 4: What is an affine transformation?`

Although a linear transformation, applied to vectors by multiplication of the vectors by a matrix, can be used to rotate, scale, shear, and reflect a set of points in an image, a linear transformation cannot be used to translate a set of points. To translate a set of points, we need to use an affine transformation. An affine transformation multiplies a vector by a matrix, just as in a linear transformation, and then adds a vector to the result. This added vector carries out the translation. By applying an affine transformation to an image on the screen we can do everything a linear transformation can do, and also have the ability to move the image up or down and left or right.

Declare a struct AffineTransformation that contains a Matrix, matrix, and a Vector, vector. Then define a function affineTransformation that takes an AffineTransformation pointer as its first parameter, and a Vector pointer as its second paramter. This function should apply the AffineTransformation to the Vector and return a new Vector that is the result of the transformation. It should do this by making calls to multiply and add.

Part II: Fractals

Introduction:

A fractal is an object that displays self-similarity at magnified scales. There are many objects in nature that have fractal properties. For example, the branching structure of the tiny capillaries of the human circulatory system is similar in structure to the branching of the large arteries that feed them. The same is true of the nervous system, tree limbs and root systems, and river systems. As another example of fractals in nature, consider the similarity in appearance of a rugged mountain from a distance and a tiny pebble on that mountain viewed from close-up.

Fractal objects are found everywhere in mathematics as well. In this lab we will use vector transformations to generate them. To draw a fractal image we will simply start with a single vector and apply a set of affine transformations to it to generate a new set of vectors. We will then recursively apply the same set of transformations to these new vectors, and so on, until we have many thousands of vectors. Then we will plot these points on the screen to generate an image. This might sound difficult, but we will use the power of recursive functions to make it simple.

`Step 1: Experimenting with affine transformations`

Set up a new GP142 application, and create a new file called main.c. Your main function should look like the following. Remember to #include "GP142.h".

int main(void)

{

int mouse_x, mouse_y;

char key_pressed;

GP142_open(); /* Open and initialize the GP142 Graphics Window */

GP142_logging(LOG_OFF); /* logging is useful to students during debugging, */

/* but annoying during the demo; turn it off. */

drawFractal(); /* draw a cool fractal on the screen */

while (GP142_await_event(&mouse_x, &mouse_y,

&key_pressed)!=GP142_QUIT)

{}

GP142_close(); /* Clean up and close graphics window */

return 0;

}

Don’t worry about anything but the call to drawFractal(). That’s the function that's going to do all the work. Make a prototype for this function. It doesn’t need to take any parameters or return a value.

Add the functions you defined in Part I to your main.c file. Then define the drawFractal function, placing some temporary code in the body. This temporary code should declare some affine transformations and vectors representing points on the graphics screen. Try defining four vectors in a square and connecting them with line segments. (Draw a line by calling GP142_lineXY. If your background is black, use the color WHITE). Then apply an affine transformation to each vector and connect the resulting four new vectors with line segments. Repeat this with various different transformations and see if you can achieve translation and scaling. Later you will learn precisely how to scale, translate, and rotate by specific amounts.

Step 2: Reading in an array of Transformations

The user will specify a set of transformations to be used to generate a fractal in a data file “data.txt” that contains the numerical entries for each matrix and vector of each affine transformation. Up to 10 transformations may be specified, one per line of the file, with the exception of the very first line, which will contain a single integer specifying how many transformations to use. Each line after that will contain six double numbers separated by spaces. The first four numbers on a line will correspond to the entries a, b, c, and d in a transformation’s matrix, and the last two will be the entries in the translation vector. Your program will read in the transformations and store them in a ten-entry array of AffineTransformations.

Delete the temporary code you wrote in drawFractal's body. In its place, declare an array of AffineTransformations with MAX_TRANSFORMS entries, where MAX_TRANSFORMS is #defined to be 10. Declare an integer that will be the number of transformations actually used. Now define a function getTransforms that takes the arrary of transformations as a parameter and fills this array with transformations read in from data.txt. This function should return an integer that is the number of transformations used, as read from the first line of the file.

Call getTransforms from drawFractal. Remember to assign the return value to the variable you declared to store the number of transformations used.

Step 3: Calculating maximum recursion depth

You want to make sure that calculating your fractal image doesn’t take too much time. That means not plotting any more points than you have to in order to generate a nice looking image. You should #define MAX_POINTS, the maximum number of points to plot. A good number to use for MAX_POINTS is 65536. You can calculate the maximum depth to which you want your recursive function to be called from this number and the number of transformations used, because each transformation will generate a recursive call for each vector. This maximum recursion depth turns out to be the logarithm, base b, of MAX_POINTS, where b is the number of transforms. To calculate log, base b, calculate log and divide by log b. Then cast the result to an int and store this value in an int variable, called max_depth, in drawFractal. This is what you should have:

/* calculate the maximun recursion depth: */

max_depth = ( int )( log( MAX_POINTS ) / log( transforms ) );

Here the variable transforms is the number of transforms being used, as returned by the getTransforms function.

Step 4: Generating the fractal

Now create a function plotVector that takes a Vector pointer as a parameter and plots the pixel on the screen corresponding to this vector. You can do this with a single call to GP142_pixelXY. You will need to cast the Vector’s entries to ints.

Now define a Vector startPoint in drawFractal whose entries are both zero. Such a vector is known as the zero vector. This will be the starting point from which all points in the image are generated via a sequences of affine transformations. (Note that this point itself is not necessarily part of the image).

Finally, define the function recursivePlot that takes as parameters a Vector pointer, an array of AffineTransforms, an integer specifying how many transforms there are, an integer specifying current recursion depth, and an integer specifying maximum recursion depth. The base case for this recursive function should be that the current recursion depth equals the maximum recursion depth. If this is the case then recursivePlot should simply plot the Vector with a call to plotVector and return.

Otherwise recursivePlot should loop through all the transformations in the array, the number of which was specified in the third parameter. For each transformation, it should calculate a new vector with a call to AffineTransform and recursively call itself, passing the value of this new vector. Remember to pass the current recursion depth plus one or the recursion will never reach the base case! Besides the new vector and recursion depth, all other arguments to the recursive call should be the same.

Call recursivePlot from drawFractal, passing as parameters the zero vector you declared, the array of transformations you read in, the number of transformations read in, zero for the current depth, and the maximum depth that you calculated. Your program should now be complete, and you can start defining some data files to generate fractals!

Step 5: Creating fractals

Here is the data.txt file that generates the fractal on the first page of this lab:

0.4 0.0 0.0 0.4 -160 0

0.4 0.0 0.0 0.4 160 0

0.4 -0.5 0.5 0.4 0 0

0.4 0.5 -0.5 0.4 0 0

Try generating this fractal. Then try changing some numbers slightly and observe the effect. I came up with this fractal by accident, but there are many very well known fractals that can be generated with your fractal program. For example, the Sierpinski Gasket:

0.5 0.0 0.0 0.5 0 100

0.5 0.0 0.0 0.5 100 -100

0.5 0.0 0.0 0.5 -100 -100

The Koch Curve:

.3333 0.0 0.0 .3333 -200 0

.3333 0.0 0.0 .3333 200 0

0.16667 -0.288675 0.288675 0.16667 -50 86.6024

0.16667 0.288675 -0.288675 0.16667 50 86.6024

A square:

0.3333 0.0 0.0 0.3333 0 150

0.3333 0.0 0.0 0.3333 0 -150

0.3333 0.0 0.0 0.3333 150 0

0.3333 0.0 0.0 0.3333 -150 0

0.3333 0.0 0.0 0.3333 150 -150

0.3333 0.0 0.0 0.3333 -150 150

0.3333 0.0 0.0 0.3333 150 150

0.3333 0.0 0.0 0.3333 -150 -150

A pentagon:

0.38 0.0 0.0 0.38 100 0

0.38 0.0 0.0 0.38 30.9017 95.1057

0.38 0.0 0.0 0.38 -80.9017 58.7785

0.38 0.0 0.0 0.38 -80.9017 -58.7785

0.38 0.0 0.0 0.38 30.9017 -95.1057

Dragon Fire:

0.5 0.0 0.0 0.8 0.0 50

0.5 0.2 -0.2 0.5 -100 -100

0.5 -0.2 0.2 0.5 100 -100

Try modifying these and see what you can come up with on your own. Besides highly geometric shapes, it’s also possible to make fractals that look like leaves, trees, grass, or ferns. Creating a really convincing image of a natural object can be quite challenging though, and usually requires rotations!

Step 6: How to control what fractals you generate

You might wish to imagine a fractal in your head, or draw a rough sketch on paper, and then calculate what affine transformations can be used to generate it. This can actually be done fairly easily. The secret is to consider the layout of the self-similar pieces of the fractal. First of all, how many such pieces are there? The number of pieces tells you how many transformations you will need. For example, the Sierpinski Gasket consists of three pieces identical to itself, each ½ scale with one on top of the other two. Thus you need three transformations, and each transformation needs to scale by 0.5, in both the x and y dimensions. The matrix part of an affine transformation is responsible for scaling. The key to creating a matrix that will scale by a certain factor is to take a matrix that scales by a factor of one and then multiply each entry by the desired factor. The matrix that scales by a factor of one is called the identity matrix, and looks like this:

`1`	`0`
`0`	`1`

Thus the matrix that scales by a factor of 0.5 is just 0.5 times this matrix:

`0.5`	`0`
`0`	`0.5`

(Note that it is also possible to scale in the x-dimension by a different factor than in the y-dimension. The top row of the matrix effects x-coordinates, and the bottom row affects y-coordinates.)

Next you need to think about how the three pieces are positioned. This is where the translation comes into the picture. The first transformation of the Gasket has the translation vector (0, 100). This tells you that the translation is 100 units straight up. The second is (100, -100), corresponding to down and to the right. The third is (-100, -100), indicating a translation down and to the left. Thus the image will have a triangular arrangement.

Generating the Gasket doesn’t involve any rotation or skew. However, generating the Koch Curve does. To do a rotation, use a matrix like this:

cos(theta)	-sin(theta)
sin(theta)	cos(theta)

where theta is the angle to be rotated. Of course you need to calculate actual numbers to put in the data.txt file. If you don't have a scientific calculator handy, you can calculate sines and cosines with the Windows calculator (from the Start menu select Programs, then Accessories, then Calculator, and make sure Scientific is selected in the View menu).

The resulting rotation matrix needs to be adjusted for scaling, by multiplying each entry by the desired scale factor. The Koch fractal uses four transformations. The first two translate left and right and scale by 1/3, but do not rotate. The second two translate up, with one also translating left and rotating by pi/3 radians, and the other translating right and rotating by –pi/3 radians. These two scale by 1/3 also. The affect of doing such transformations on a horizontal line of length 3 would be the generation of the same line but with the middle one third removed and replaced by an equilateral triangle of side length 1, and no base. When we’re drawing the Koch fractal, we recursively apply these transformations over and over, and thus see the shape that would be generated by repeating this process for each new line segment ad infinitum.

Exercise: Try to find a set of affine transformations that can generate the following fractal:

Hint: Notice that there are five self-similar pieces, so you will need to have five transformations. Also notice that no rotation is necessary, only translation and scaling.

Conclusion:

Now that you know the tricks to designing fractals with affine transformations, dream up a fractal shape in your head or on paper and try to duplicate it by defining transformations in data.txt. This is a lot more challenging than just trying random combinations of numbers and seeing what results, but also more rewarding! If you discover a really cool fractal, please email me the data.txt data!

Have fun!