CS 293 Programs

CS 293: Mathematical Graphics

Project: Recursive Generation of a 3-Dimensional Fractal Mountain

This project was inspired by a 2D version of the same program; a simple recursive algorithm that generates a realistic-looking mountain range.
My idea was to transfer this concept into the 3D world that OpenGL makes available to programmers. Unfortunately, this proved more difficult than I imagined.

This was my first attempt at generating terrain. As you can see, it looks as if someone took a rake and scraped through my terrain. This terrain was not generated recursively, but rather in a loop. I used the sin function to attempt to randomize whether I was adding to the height or subtracting from it.

Here is the code that generated the "rake effect":

if(landGenFirst)
{
	landGenFirst = 0;
	srand(time(NULL));
	for(int i=0; i<=LANDROWS; i++)
	{
		landpt[i][0][0] = LANDW - (2.0 * LANDW / LANDROWS) * i;
		landpt[i][0][1] = LANDL;
		landpt[i][0][2] = S(rand())/5.;
		
		for(int j=1; j<=LANDCOLS; j++)
		{
			landpt[i][j][0] = LANDW - (2.0 * LANDW / LANDROWS) * i;
			landpt[i][j][1] = LANDL - (2.0 * LANDL / LANDCOLS) * j;
			landpt[i][j][2] = landpt[i][j-1][2] + S(rand())/5.;
		}
	}
}

//old version of mountain
void mountain(GLfloat height, GLfloat x, GLfloat y, int level, GLfloat dx, GLfloat dy)
{
	level--;
	if(level>0)
	{
		mountain(height/2., x+dx, y+dy, level, dx/2., dy/2.);
		mountain(height/2., x-dx, y+dy, level, dx/2., dy/2.);
		mountain(height/2., x-dx, y-dy, level, dx/2., dy/2.);
		mountain(height/2., x+dx, y-dy, level, dx/2., dy/2.);
	}

	GLfloat newheight = height + (rand()%2 ? -1. : 1.) * height/2.;
	landpt[ptptr].x = x;
	landpt[ptptr].y = y;
	landpt[ptptr].z = newheight;

	ptptr++;
	maxptr = (ptptr > maxptr ? ptptr : maxptr);

	return;
}

//old code snippet from landgen for plotting the above version of mountain
//just look at how complicated this code is, and it still doesn't work properly
for(int i=arraySize-1; i>0; i--)
{
	if(i%5==0) glBegin(GL_TRIANGLE_FAN);
	glVertex3f(landpt[i].x,landpt[i].z,landpt[i].y);
	if(i%5==1)
	{
		glVertex3f(landpt[i+3].x,landpt[i+3].z,landpt[i+3].y);
		glEnd();
		if(i>1 && (landpt[i].y > landpt[i-2].y) && (landpt[i].x > landpt[i-2].x) )
		{
			glBegin(GL_QUADS);
			glVertex3f(landpt[i+1].x,landpt[i+1].z,landpt[i+1].y);
			glVertex3f(landpt[i+2].x,landpt[i+2].z,landpt[i+2].y);
			glVertex3f(landpt[i-2].x,landpt[i-2].z,landpt[i-2].y);
			glVertex3f(landpt[i-5].x,landpt[i-5].z,landpt[i-5].y);
			glEnd();
		}
		else if(i>1 && (landpt[i].y > landpt[i-2].y) && (landpt[i].x < landpt[i-2].x) )
		{
			glBegin(GL_QUADS);
			glVertex3f(landpt[i].x,landpt[i].z,landpt[i].y);
			glVertex3f(landpt[i+3].x,landpt[i+3].z,landpt[i+3].y);
			glVertex3f(landpt[i-3].x,landpt[i-3].z,landpt[i-3].y);
			glVertex3f(landpt[i-4].x,landpt[i-4].z,landpt[i-4].y);
			glEnd();
		}
	}
}

After removing the "rake effect" from my code, I next attempted a recursive algorithm for generating the terrain. Unfortunately, I went about the algorithm in a way that made trying to plot the generated points virtually impossible, as you can see in the image below. The code to the left is my first recursive algorithm, which generates the mess below.
A chaotic mess

Please note that this terrain appears flat intentionally - I made every height 0 so that I could see what was happening easier

I have rewritten the mountain function to generate points recursively. Unfortunately, because of the nature of the algorithm, the points were generated in a bizarre order that makes drawing polygons tricky. I wrote a sorting algorithm that kept me busy debugging for a good 12 hours (10 in the morning till 10 at night), though not straight through - I do have needs other than programming. What it came down to was a very simple mistake (although one that I did not know until I looked up the cmath library functions): I was using the abs() function on floating-point values. abs(), however, only works on integers; for floating-point values, the function to use is fabs() - file that away somewhere in your head, it'll save you a lot of painful debugging later!

My final sorting algorithm:

void sortIt(int size)
{
	bool flipped = true;
	point temp;
	
	for(int k=0; k<size; k+=size/4)
	{
		for(int i=k; i<k+size/4; i++)
		{
			flipped=false;
			for(int j=k+size/4-1; j>=k+1; j--)
			{
				if( fabs(landpt[j].x) < fabs(landpt[j-1].x))
				{
					temp.x = landpt[j].x;
					temp.y = landpt[j].y;
					temp.z = landpt[j].z;
					landpt[j].x = landpt[j-1].x;
					landpt[j].y = landpt[j-1].y;
					landpt[j].z = landpt[j-1].z;
					landpt[j-1].x = temp.x;
					landpt[j-1].y = temp.y;
					landpt[j-1].z = temp.z;
					flipped=true;
				}
			}
		}
		flipped = true;
	}
}

And the final product! I have plans to add additional user interactions (such as controlling the level) and maybe make the code more efficient. I also plan to tweak the point-generating algorithm to generate more points between the current lines of points. But that is for a later date. For now, here is the code for my Recursive Generation of a 3-Dimensional Fractal Mountain.

A representation of the alignment of points generated by my program
(looking down the z-axis)

Look at or download the current code here

Watch this page for updates on my progress with this project.