In this assignment you will learn to build 3 dimensional solids in recursive fashion. Initially, this will be similar to what you did for Assignment 4. But, once you get comfortable with the constructions, you will move to more complex geometries. Once you are comfortable doing these constructions, you will apply two techniques designed to generate fractal mountains.
You can work with a partner if you wish. The only requirement is that you choose a different partner from the one you chose for Assignment 4.
Part 1 -- Basic Subdivision
The first step of the process is to experiment with recursive subdivision. This is not unlike what you did in Assignment 4 at first but the extension make it vastly different.
First you must apply recursive subdivision to a triangle to get
into the spirit of the assignment. One level of the subdivision process
makes 1 triangle into 4. This is done by placing vertices at the midpoints
of the 3 sides of the triangle. These vertices are then connected resulting
in 4 triangles. It is very important in what follows that you do this by
identifying triangles and not just constructing subdividing lines.
We show here the first 2 generations generated from the triangle ABC.
To begin your work on this assignment, write a program that allows a user to create a triangle and then subdivide it for a specified number of generations. You need to support triangle creation in a variety of ways. The user could either enter mouse clicks for the 3 vertices or could choose from a pallate of popular triangles you provide or enter ASCII coordinates by hand or from a file. Once the triangle has been created, you will allow the user to select the number of generations. You then recursively subdivide the triangle for that number of generations. To be sure that you have the picture correct, color each new triangle in a different color.
Part 2 -- Subdividing more complex Shapes
The second step in the assignment is to perform recursive subdivision on more complication shapes. Instead of starting from a triangle, start from a tetrahedron. Recall that a tetrahedron is a 3 dimensional shape defined by 4 vertices, 6 edges and 4 triangular faces. To move from generation 0 to generation 1, all 4 triangular faces are subdivided resulting in 16 triangular faces. Generation 2 has 64 triangular faces, and so forth.
Once you feel comfortable doing this for the tetrahedron, allow the
user to enter a mesh of triangles, specify a number of
generations and proceed with recursive subdivision for
that number of generations. An arbitrary mesh is a collection
of triangles with the property that
pairs of triangles either connect along an edge (in which case
the same length of edge belongs to both) or at a vertex or not at all.
For example, here are 2 examples of meshes.
Once again, you will let the user either enter the mesh thru mouse clicks or via ASCII input. You must identify adjacencies, so that you know that an edge divides 2 faces and can identify the faces. You will probably want to record your result using the winged edge data structure we discussed in class.
Part 3 -- Controlled Randomness -- Fractal Mountains
For the third part of the assignment, you are going to generate fractal mountains by 2 different methods. The first method builds off of the mesh done above. You add the additional ability to specify a z coordinate for each vertex. Thus, the mesh becomes what is known as a terrain. Now, you can apply recursive subdivision to your terrain to generate a mountain range. To do so, you might want to vary the number of generations you use at each location depending on whether the mountain range is meant to be smooth or rough there. Part of this problem involves experimentation until you achieve a mountain range that you like.
For the second part of the mountain generation, you will introduce randomness as an aid in generating a mountainous terrain. Choose a value alpha between 0 and 1. Everytime you take a midpoint of a segment, instead of merely choosing the midpoint, create a sphere about that midpoint. Let the radius of the sphere be alpha times the length of the segment. Now choose a point at random in the sphere and use it to replace the midpoint. In so doing, you are introducing randomness into the situation. Now repeat the first 2 parts of the assignment (recursive subdivision of a triangle and of a tetrahedron) with this randomness. When you have done so, apply randomness to the recursive subdivision of terrains. The goal again is to generate the perfect mountain.
An easy hack that will help you is to assign color based on elevation. You might want to have a snow line and color varying depths of snow above that elevation. You might want to locate some small flat regions and color them as mountain lakes. The very industrious will find a method of generating trees (not hard) and have trees on the mountain up to the tree line. The tree heights will want to decrease as the elevation increases.
Grading
The assignment will be graded for correctness, for code quality and for aesthetics. You will lose points if it is clear that you merely completed the assignment and did not try to generate elegant mountains.