The purpose of this project is to create 3d mountain terrain using a recursive Midpoint Displacement Formula. For this project I decided a GUI would be useful, that way manipulations could be seen in real time. This would require a 3d rendering package. My choices were DirectX, OpenGL and Java3d. Since I prefer to do my development in Linux, DirectX was ruled out. I have not been very impressed with the performance of Java3d so that left me with OpenGL. After deciding on my rendering package I needed to choose a language and a GUI framework. GLUI is an excellent framework for leaning OpenGL, but lacks control over the layout of the interface. So I decided on QT by Trolltech which was just recently acquired by Nokia.

Midpoint Displacement Formula

The Midpoint Displacement Formula is simply to take two points, find the midpoint and then add or subtract a random number. This formula can then be repeated for each segment creating a fractal. This same concept can be converted to 3d in what is known as the Diamond-Square algorithm. Instead of two points we take a plane defined by four points, calculate the midpoint and add a random number. We can start with one large plane and perform the algorithm. Then divide the plane into four sub-planes and repeat. A recursive function works well for this task. For the mountains to look real, it is best to shorten the range of random numbers as the algorithm progresses. Below is the midpoint Function I wrote for this program in C++.
/****************************************
*This is the recursive algorithm of the
* midpoint formula
****************************************/
int GenFractal::midpoint(int i,int start,int topx, int topy) {
//Base case
if(i<1) {
return 0;
}

//find lenght for this section
int len = (int)pow(2,i);

//Calculate midpoints

//Top middle
int x1 = topx + len/2;
int y1 = topy;

//Right middle
int x2 = topx + len;
int y2 = topy + len/2;

//Bottom middle
int x3 = x1;
int y3 = y1 + len;

//Left Middle
int x4 = x2 – len;
int y4 = y2;

//Midpoint
int xmid = x1;
int ymid = y2;

//Calculate the values of the midpoints

//Top middle
data[x1][y1] = data[topx][topy] +
(data[topx+len][topy] – data[topx][topy])/2;

//Right middle
data[x2][y2] = data[topx+len][topy] +
(data[topx+len][topy+len] – data[topx+len][topy])/2;

//Bottom middle
data[x3][y3] = data[topx][topy+len] +
(data[topx+len][topy+len] – data[topx][topy+len])/2;

//Left middle
data[x4][y4] = data[topx][topy] +
(data[topx][topy+len] – data[topx][topy])/2;

//Midpoint
data[xmid][ymid] = data[x1][y1] + (data[x3][y3] – data[x1][y1])/2;

//Decrease the varence of randomness as iterations go foward
float min = hmin * (((float)start – ((float)start – (float)i)) / (float)start);
float max = hmax * (((float)start – ((float)start – (float)i)) / (float)start);
//Add random value to midpoint from hmin to hmax

data[xmid][ymid] +=  (int)(min + ((float)rand() / (float) RAND_MAX) * (max – min));

//As mountians get larger add less varence of random data

//Decrease I
i–;

//Recursive steps

//Upper left quadrant
midpoint(i,start,topx,topy);

//Upper right quadrant
midpoint(i,start,x1,y1);

//Lower left quadrant
midpoint(i,start,x4, y4);

//Lower right quadrant
midpoint(i,start,xmid,ymid);

return 0;

Building the Framework
For this project I decided on using QT4 with OpenGL. Since I am running Ubuntu, I used apt-get to install the QT4 development packages.

sudo apt-get install libqt4-dev qt4-dev-tools qt4-designer qt4-doc

For my development environment I chose the Eclipse IDE for C/C++ Developers with the QT Eclipse Integration Plugin. This allows for rapid development of QT applications. I decided to use CVS for version control since it is easy to setup and is integrated into eclipse.

Building the Interface
I built the interface using the Qt4 designer. Below you can see a screen shot of my application’s layout.

Rendering
For OpenGL rendering I had to create a QGLWidget Class. Once the class is created you can then paint to this widget using regular OpenGL functions. My OpenGL skills are not nearly as good as I would like. I have a copy of the Red and Blue Book which is enough information to get a rendering window, setup lighting and draw some polygons. For this project I converted the elevation map to triangles with the normals facing up and packed them into a GLfloat array. The polygons can be rendered with the following commands.

//Create array for triangles
GLfloat * vert = fractal.getTriangles();
int length = fractal.getNumTriangles();
glEnableClientState(GL_VERTEX_ARRAY);
glVertexPointer(3,GL_FLOAT,0,vert);

GLuint list = glGenLists(1);
glNewList(list, GL_COMPILE);

//Set Color
float colorBlue[] = { 1.0f, 0.5f, 0.0f, 0.0f };
glMaterialfv(GL_FRONT, GL_AMBIENT_AND_DIFFUSE, colorBlue);

//Draw the triangles from array
glDrawArrays(GL_TRIANGLES,0,length);

glEndList();

This same data can then be used for my RAW triangles export by simply converting it to ASCII.


Windows XP / Vista Port
After I had a satisfactory application I decided to try porting it to windows. This is so windows users can try this program without having to compile it. I simply download QT for Windows with the MinGW GNU compiler and ran ‘qmake’ and ‘make’. Thats was about all that was needed.

Conclusion

This turned out to be a very involved programming project for me. There is a saying that no software is ever finished. This project has really solidified that for me. There are still may improvements and features I would like to add. I am still not 100% satisfied with the terrain generation. I feel that I could use some improvements of my algorithm.

Download
Source Code Tarball: Mountains.Feb-4-2008.tar.gz

Source Code Zip: Mountains.Feb-4-2008.zip

Win32 Binary: Mountains-win32.zip