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();

intlength = fractal.getNumTriangles();

glEnableClientState(GL_VERTEX_ARRAY);

glVertexPointer(3,GL_FLOAT,0,vert);GLuint list = glGenLists(1);

glNewList(list, GL_COMPILE);//Set Color

floatcolorBlue[] = { 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