CS 106: Assignment 06

CS 106 Winter 2016

Assignment 06: Recursion

Due: Monday March 7th, 11:59pm (midnight, not noon!)

Starter code: A06.zip (for Question 2)

Question 1 Half-Hex

The Half-Hex tiling is a "reptile": it's a single shape that can be divided up into smaller copies of itself. Each of those copies can then be divided up, and so on. If you keep doing this, you can fill as large a region (e.g., a bathroom floor) as you want with copies of the original shape.

If we arbitrarily decree that the long side has length 100, the corners of the shape could be given coordinates as in the diagram below. Note that the long edge is exactly twice as long as the three short edges.

Create a Processing sketch that displays this tiling. When the sketch starts up, it should display a single large half-hex centred in the sketch window (scale it so that it takes up most of the width of the window). The sketch should have a single interactive feature: when the user presses the "-" (minus) key, decrease the number of recursive levels shown in the drawing, and when the user presses the "=" (equals) key, increase the number of levels. The screenshots below show Level 0 on the left and Level 4 on the right.

In terms of code, the sketch can be structured almost identically to the sample sketch Gasket1. The draw() function sets up a global geometric context to position the drawing, and then calls a recursive helper function. Depending on the current level of recursion (passed in to the function), the recursive function either just draws a single shape (in this case, a copy of the half-hex) or calls itself recursively inside a set of "child" geometric contexts. What you need to do, then, is figure out the four geometric contexts you need for the recursive calls that will place four small copies of the half-hex inside one large one.

I suggest the following approach. First, get Level 0 working: make sure that when the sketch starts, you can display a single large half-hex. Then work on Level 1 one shape at a time: figure out the geometric context you need to place the first small half-hex inside the large one, using the "-" and "=" keys to jump back and forth and verify that it's placed correctly. Do this until your four geometric contexts are all correct, and the fractal structure of the design will simply fall into place.

A few final notes:

You should use a sketch window of size 600×400.
At each recursive level, the tiles are exactly half as large as they were in the previous level.
Draw all tiles with black outlines. You can use any fill colours you want, and feel free to try to colour individual tiles differently, as long as the colours don't change every frame. But it's fine if every tile is filled with the same colour.
In any given drawing, make sure every tile is drawn with the same line thickness. But it's fine if that thickness changes when you change the amount of recursion.
Feel free to experiment with other enhancements. An interesting experiment is to sometimes skip the recursive step with some small probability. That will give you an uneven tiling with half-hexes of different sizes. Just make sure there's a way to disable enhancements so that we can see the basic sketch working.

Submit a sketch named HalfHex.

Question 2 Menger Sponge

The Sierpinski Carpet is a 2D fractal shape created by dividing a square into nine smaller squares, removing the central square, and then repeating that process on each of the remaining eight squares. It is demonstrated by the Carpet sample sketch.

The 3D analogue of the Sierpinski Carpet is the Menger Sponge. You divide a cube into 27 smaller cubes, and remove the seven cubes that make up the central 3D cross. Then you repeat the process on each of the 20 remaining cubes.

Create a sketch that draws the Menger Sponge to a specified number of recursive levels. As in the previous question, the "-" and "=" keys should be used to decrease and increase the number of levels, interactively showing a more or less fractally shape.

This sketch can be written more or less directly from the following two main pieces:

The Sponge sketch provided in the starter code. As given, the sketch just draws a cube, but it also sets up a PeasyCam to allow manipulation of the camera, and adds a couple of lights to make the cube's faces different colours.
The Carpet sample sketch in Module 07. That sketch gives you a great approach to making the 3D version. Just define an array of booleans, this time of length 3×3×3 = 27, saying which cubes are part of the fractal and which ones aren't. Then, at a given recursive level, use three nested for loops (as in the GridOfSpheres sample sketch in Module 06) to walk over all 27 sub-cubes, and do a recursive calls on the ones specified as true in the array. If that's confusing, study the code for Carpet until the approach makes sense. You definitely shouldn't have a recursive function containing 20 copies of the code that creates a geometric context and makes a recursive code—too much typing!

Save your solution in a sketch titled Sponge.

Submission

Remember to review the Code Style Guide and use Processing's built-in auto format tool. Then review the How To Submit document. At the top of all of your source files, be sure to include a comment with your name and student ID number. When you're ready, zip both of the sketches created above (HalfHex and Sponge) into a single archive called A06.zip and upload that file to LEARN.