# How to use recursive midpoint subdivision to generate fractal terrain like mountains?

on
I am working on a flight simulator, I know the basic idea about midpoint subdivision, but I don't know how to implement it to generate fractal terrains.

I just need some simple tutorial, simple and clear sample code that I can start with, see something done then go deeper. but I cannot find a suitable starting point.
There are many sites which talk about the algorithm, and show great demo applications, but they look too complicated to me.

Would anyone like to give me any directions or direct me to some sites which suit for beginners? Thank you in advance!
Comment
Watch Question

Do more with

EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
Most Valuable Expert 2014
Top Expert 2015

Commented:

Commented:
I 've seen that too, but seems still complex to follow
anyway, thanks
Most Valuable Expert 2014
Top Expert 2015

Commented:
Is there a particular aspect of it you need explained?

Commented:
after hard work on reading, i got my code run, now i use 257x257 array to make terrain height map, the X,Z value only goes from -1.0 to 1.0, so the random offset only about -0.3 to 0.3 (i am surprise why most of random numbers are negative),  it took quite a while to compute, i am wondering usually how large array we should use, and
if I want to draw the scene where X,Z can go larger, for
example, 50x50, then should I use larger array or are there any other way to do that?

Also my terrain looks ugly, since no matter how small variations i used, it always looks like just tons of "Triangles", never looks "mountain", can this situation become better by using texture mapping?

are there any other way to get appropriate random offset?
Thanks!
Most Valuable Expert 2014
Top Expert 2015

Commented:
You might also try offseting from a second order interpolation instead of just first order

Commented:
i already did what you said, what do you mean first/second order?

Commented:
i already did what you said, what do you mean first/second order?
Most Valuable Expert 2014
Top Expert 2015

Commented:
Instead of (p1+p2)/2 + random_offset, you might try e.g.
(-p0+5*p1+5*p2-p3)/8 + random_offset

Commented:
usually how big array do we need to use? and how big square
do  we need to start to do subdivision?
thanks
Most Valuable Expert 2014
Top Expert 2015
Commented:
How big an array you use depends on how much detail you need.
Usually you would start to do subdivision at the corners of the array,
unless you want to seed it with an rough starting terrain.

Commented:
Kindy, here is a rough description of a non-recursive implementation.

Here is some pseudo-code.

GRIDSIZE=257           // Number of vertices across and
// down assuming a square grid.
CELLSIZE=16            // The size of each cell described
// by the four vertices around it.
// It's simple to turn this into
// triangles later, the important
// thing is getting the vertex data.
NUMVERTS=GRIDSIZE*GRIDSIZE // Total number of vertices.
NUMCELLS=(GRIDSIZE-1)*(GRIDSIZE-1) // Total no. of cells.

You would now populate the first four elements of your vertex array with the data of the four corners of your grid perimeter, say in QUADS[NUMQUADS][4], space for the four vertices of each quad in the grid.

The main loop takes the next quad from this array (which initially only has one, your largest square, the perimiter), calculates it's x/z midpoint, perturbs this a random amount (usually by a Gaussian calculation but you'll have to look that up) and then generates, on-the-fly, four new quads - top/bottom left and top/bottom right of your original, then stores them in the QUADS array and increments a pointer to the next quad to fetch. So you're actually generating vertex-data only and can use this later to describe quads or tris.

Also your perturbation factor should vary according to the length of the side of the quad you are dealing with :

// perimeter of your whole grid, and will count down from
// the length of this large square to a square of size 2.

for (LENGTH=CELLSIZE*(GRIDSIZE-1);LENGTH>2;LENGTH--)

{

x1,z1=either left-hand corner/vertex
x2,z2=either right-hand corner/vertex

// Now calculate the midpoint
// These formulas depend on screen origin etc
// If you generate all points to lie between 0 and 1
// then you can scale the whole thing as needed.

xmid=x1+((x2-x1)/2)
zmid=z1+((z2-z1)/2)

// Now calculate and store four new quads (or sets of four
// vertices if you prefer, why am i using slashes for comments in pseudo-code !!! Just realised ...

topleft corner of new quad 1=topleft corner of original

bottomright corner of new quad1 = xmid/zmid

You can at this point perturb all or just some of the vertex components.

I have to go now because there are two VERY noisy children demanding my attention :)

If you need more info, do a search for these keywords :

midpoint subdivision algorithm fractal terrain

as seperate words not in quotes.

Regards.

Kinnon.

Commented:
Thanks for all the help! I don't know hot to split, otherwise I will give awards to everyone who answered me.

Do more with