Spring is not here yet, but we can draw some trees ourselves :)

A variety of natural phenomena exhibit self-similar or "fractal" structures, i.e., similar patterns that recur at progressively smaller scales:

In computer graphics, one simple way to model fractal behavior is to recursively apply the types of transformations we've been studying in class (rotation, translation, scale, etc.) to some graphical primitive (like a line segment or rectangle). For this assignment, you will design a function that draws a fractal binary tree in 2D:

Your task is to write a routine that (i) draws a single edge in the tree, and (ii) recursively draws the (smaller) left and right branches. The only argument this function needs to take is the current depth of the tree. When the depth reaches zero, recursion should terminate. Your challenge, then, is to apply the right transformations at just the right moment, so that the output looks something like the tree depicted above.

Your routine should have the following structure:

drawSubTree( depth )
{
   if( depth == 0 ) return;
   
   // draw some geometry for the current edge
   
   // apply some transformations

   drawSubTree( depth-1 );

   // apply some transformations

   drawSubTree( depth-1 );

   // apply some transformations
 }

As you can see, most of the routine has already been written for you. Your job is to fill in the part that says "draw a rectangle" and "apply some transformations." You should assume that the following pseudocode commands are available to you:

rotate( theta );    // rotate by an angle theta, in radians
translate( u, v );  // apply a horizontal translation u, and a vertical translation v
scale( s );         // uniformly scale by a factor s
rect( x, y, w, h ); // draw a rectangle with corner (x,y), width w, and height h

You also can assume that transformations are applied in the same way as in OpenGL: the last transformation gets applied first. For instance, if you write

rotate( theta );
translate( u, v );
rect( x, y, width, height );

then the rectangle will be translated then rotated. If you instead write

translate( u, v );
rotate( theta );
rect( x, y, width, height );

the rectangle will be rotated then translated. Note that you should not use the depth value to determine the width/height or position of the rectangle - everything should be done purely through the transformations.

Hint: Think very carefully about how transformations get applied as you move up and down the call stack. (Do you need to "undo" any transformations?)

Implement in HTML5 Canvas Sandbox

Now you'll write "real code", not just pseudocode. Since it's hard to write correct pseudocode without a visualization of what you're writing, you may find it very helpful - and fun! - to try out what you did above in a real environment. We've created a sandbox for you to try out here:

HTML5 Canvas Sandbox for Tree Drawing

This sandbox allows you to call drawing and transformation routines using HTML5 Canvas, which is a modern standard for drawing 2D graphics in a web browser. Most of the code has been written for you already. The basic idea is that you have a context, called ctx, which can make all sorts of draw calls. For instance, to draw a rectangle you can write

ctx.beginPath();
ctx.rect(-10,-40,20,80); // the four arguments specify x, y, width, height
ctx.fill();

Geometric transformations look nearly identical to the pseuedocode commands given above:

ctx.rotate( theta ); // rotate by an angle theta, in radians
ctx.translate( u, v ); // apply a horizontal translation u, and a vertical translation v
ctx.scale( a, b ); // scale by a in the horizontal direction and b in the vertical direction
ctx.rect( x, y, w, h ); // draw a rectangle with corner (x,y), width w, and height h

As above, transformations get applied in the order "last transformation first." And again, you should think about how transformations should get applied and then reversed as you go up and down the call stack.

Of course, you're welcome to get as fancy as you like here; here's a reference guide for more functions in Canvas.

Submission details

To encourage collaborations, we will require each group to draw 2 different trees using the HTML5 Canvas Sandbox.

Take a screenshot of your code and drawings, and turn it in via gradescope! We will create a Piazza thread for results, so that people can see them in their full-color glory. We want to see what cool stuff you make. We definitely encourage creativity here - try changing the shape, size, color, style of the tree---or even (if you're feeling ambitious) the branching factor.