Assignment 4: Recursively Defined Polyhedra and Fractal Mountains

CS 426 Assignment 4

Recursively Defined Polyhedra and Fractal Mountains

Due 1159 PM Friday, November 22

Again: this assignment should be done in teams of two, with the added restriction that you cannot work with your partner from the previous assignment.

Introduction

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 3. But, once you get comfortable with the constructions, you will move to more complex geometries: you will apply two techniques designed to generate fractal mountains.

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 3 at first but the extension makes 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 palette of popular triangles you provide.

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, colour each new triangle in a different colour.

Part 2 -- Subdividing more complex Shapes

The second step in the assignment is to perform recursive subdivision on more complicated 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 enter the mesh through mouse clicks. You must identify adjacencies, so that you know that an edge divides 2 faces and you 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 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 (make this value changeable by the user). 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 colour based on elevation. You might want to have a snow line and colour varying depths of snow above that elevation. You might want to locate some small flat regions and colour 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.

Output file

We'll be using the output of this assignment as input for the next one. You will need to implement a "save" feature which allows the user to save the current mesh to a file. The file format is in plain ASCII, with, starting at the first line:

max_vertices n
on the first line, with n replaced by the number of vertices in your mesh
vertex x y z
on subsequent lines, one for each vertex
tri v1 v2 v3
one of these for each triangle, where v1, v2 and v3 are indices into the vertex array, starting at index 0. Make sure that the vertices of each triangle are sorted in counter-clockwise order (when viewed from above)

Keep in mind that you'll need to add a few more lines to your output function later on (for the 5th assignment).

What to submit

Part 1: a separate program, which shows both "regular" and random subdivision of one, user specified, triangle
Part 2: a separate program, which shows random subdivision of a tetrahedron
Part 3: a separate program, which generates your fractal mountains.
a makefile which makes all three parts in one go
a README which explains any obscure/cool features that your program has

Reading

Hearn & Baker, paragraph 10-18: pp. 362-387
lecture notes on winged edge data structure
OpenGL Programming Guide, chapter 3, on viewing

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.

The grade breakdown will roughly look like this:

part 1: 1 point
part 2: 1 point
part 3: 8 points

Extra credit: the prettier your mountains are, the more points you score...

Last year

Last year four graduate students wrote a "scenery designer" as their final project. The image at the top of this page is output from their program, as is this one:

Take a look at their scenery designer web page.

CS426, CS Department, Princeton University

Last modified: Thu Nov 14 19:00:36 1996