kindy
asked on
How to use recursive midpoint subdivision to generate fractal terrain like mountains?
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!
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!
ozo
http://www.gameprogrammer.com/fractal.html
ASKER
I 've seen that too, but seems still complex to follow
anyway, thanks
anyway, thanks
Is there a particular aspect of it you need explained?
ASKER
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!
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!
Your random offset should decrease as your resolution increases.
You might also try offseting from a second order interpolation instead of just first order
You might also try offseting from a second order interpolation instead of just first order
ASKER
i already did what you said, what do you mean first/second order?
ASKER
i already did what you said, what do you mean first/second order?
Instead of (p1+p2)/2 + random_offset, you might try e.g.
(-p0+5*p1+5*p2-p3)/8 + random_offset
(-p0+5*p1+5*p2-p3)/8 + random_offset
ASKER
usually how big array do we need to use? and how big square
do we need to start to do subdivision?
thanks
do we need to start to do subdivision?
thanks
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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
NUMCELLS=(GRIDSIZE-1)*(GRI
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 :
// Your loop will start with the first cell describing the
// 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
{
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
quad
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.
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
NUMCELLS=(GRIDSIZE-1)*(GRI
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 :
// Your loop will start with the first cell describing the
// 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
{
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
quad
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.
ASKER
Thanks for all the help! I don't know hot to split, otherwise I will give awards to everyone who answered me.