Program Four: Mountain Terrain Generator

For this assignment, the goal was to create a program that took a base object (like a pyramid or cone) made entirely of triangle polygons and subdivide it in such a way that the subsequent object resembles a mountain. Here's the basic pseudocode:

for each triangle{
    subdivide current triangle into 4 new triangles
    break each edge of the current triangle into two edges at the midpoint of the edge
    using Standard Brownian Motion, move the midpoint to a new position
Repeat for as many subdivisions as you desire

Standard Brownian Motion is defined as an erratic zigzag movement of particles in a gas or fluid. This gives us a randomness appearance as we would normally find in nature, yet we still have some order. In my implementation, I alter all 3 dimensions of each midpoint and each vertex.

The biggest challenge I had with this project was the data structure to store edges and faces. Instead of starting from scratch, I started with an obj viewer that I wrote for another class. For that program, I already stored edges and faces, however I did not care whether there were duplicates since I was only displaying and rotating the vertices. That issue caused a lot of headache for this project. If I were to redo this from scratch, I would use the winged-edge data structure.

After getting my data structure to work for subdivisions only, I then moved to altering the edge midpoints to give the desired effect. Simply altering the midpoint was simple, since I stored the midpoint of each edge in the edge list data structure. I started with moving the points in a very small manner, which worked well. However when I increased the randomness, I started getting gaps. I'm still yet to know why, since I reference each midpoint at the same location. For the running time of this program, mine is at least O(n^3), by simply measuring the time

Currently, I am having problems with the following:

Vertex normals - Some faces are in CCW order and some are CW order.
More efficient data structure
Underlying geometry somewhat visible - This means if I started with a pyramid, the final shape still has somewhat of a pyramid look

For those interested, here are some of the .obj files I created:
6 Levels
8 Levels
8 Levels #2
Starting Geometry

For these screenshots, I used an obj viewer written by Marco Till Brenner and Robert C. Duvall at Duke University. Here is the source code for linux:
Object viewer (.obj files)

Now, here are some images:
Final image:

This mesh took about 20 minutes to run, which is mainly due to inefficiencies in my data-structures. It is 8 levels of subdivision. I have one that is 9 levels running right now; so far its running time is 210 minutes and its not even half way.


These are some of the many errors that I had.

Brian Caines © 2024 BrianCaines.com