# Fractal Terrain - Midpoint displacement problem

This topic is 4559 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Well ive been trying to make a fractal terrain generator using the midpoint displacement algorithm and ive come up with a bit of a problem in my implementation. Basiclly I have a list of Squares made up of 4 Points. On every iteration I do this:
void Terrain ::Generate(int iterations)
{
for(int i=0; i&lt;iterations; i++)
{
// Get current number of squares making up the terrain
int size = squares.size();

// Iterate over the current squares
for(int j=0; j&lt;size; j++)
{
// Get next square from the list and save it to temp
Square *temp = squares.front();

// Remove the square from the list
squares.pop_front();

// Subdivide into 4 smaller squares
Square *subSquares[4];
temp-&gt;SubDivide(subSquares, roughness, xMax, xMin, yMax, yMin);

// Add the new squares to the end of the list
for(int k=0; k&lt;4; k++)
{
squares.push_back(subSquares[k]);
}
}

}

}


where SubDivide() looks like this:
// Divides this square into 4 other squares using random midpoint displacement
void SubDivide(Square *subSquares[], float roughness, float xMax, float xMin, float yMax,float yMin)
{
// Find the midPoints of the squares edges
Point *ab = a-&gt;MidPoint(b);
Point *bc = b-&gt;MidPoint(c);
Point *cd = c-&gt;MidPoint(d);
Point *da = d-&gt;MidPoint(a);

// Find the Centre of the square
Point *m = ab-&gt;MidPoint(cd);

// Add random displacements to the mid points if not on edges
if(ab-&gt;x != xMax && ab-&gt;x != xMin && ab-&gt;y != yMax && ab-&gt;y != yMin)

if(bc-&gt;x != xMax && bc-&gt;x != xMin && bc-&gt;y != yMax && bc-&gt;y != yMin)

if(cd-&gt;x != xMax && cd-&gt;x != xMin && cd-&gt;y != yMax && cd-&gt;y != yMin)

if(da-&gt;x != xMax && da-&gt;x != xMin && da-&gt;y != yMax && da-&gt;y != yMin)

// Create and store the sub squares
subSquares[0] = new Square(a, ab, m, da);
subSquares[1] = new Square(ab, b, bc, m);
subSquares[2] = new Square(da, m, cd, d);
subSquares[3] = new Square(m, bc, c, cd);
}


Basiclly the problem is when 2 squares share a midpoint, the midpoint is calculated seperatly twice, giving two differnt heights and therefore making gaps in my terrain when i render. Any ideas on how i can fix this problem??

##### Share on other sites
I actually just wrote a midpoint displacement class. lemme know if you want me to post the code. otherwise i'll continue trying to look through yours =)

And i'm not sure I understand your problem. If you implement the algorithm correctly, each point on the heightmap is only calculated once. If you're calculating a height for the same place more than once there's a problem with your implementation.

-me

##### Share on other sites
Its cause ive structured the grid into "Squares" rather than just a 2D array of points. I didnt really do much research before i started lol was just going on the half a page of details in the openGL green book. I cant be bothered rewritting it all tho, im pretty sure there must be a way to figure out if a mid point is shared that wont slow it down too much but i cant think straight, been trying to figure it out for too long.

##### Share on other sites
I strongly recommend re-writing it to use a 2d heightmap style grid instead of the squares list (you're essentially emulating Recursion with your list there BTW)

Not only is the midpoint algorithm a lot easier to code for a flat grid, but that structure will also allow for much faster rendering of the terrain.

When I first did my Diamond Squares (midpoint displacement) Terrain, I did an approach similar to yours, where I had a function that subdivided squares into smaller ones... and repeated for them till it hit a set limit...
It was Incredibly slow, as the terrain size increases it would use up All the CPU cycles between vsynchs. (very bad)
I switched to a grid method and not the terrain is a lot larger, has better details, and only uses about 15% of the CPU cycles between vsynchs.

##### Share on other sites
yeah, i think you're going to find that your algorithm doesn't produce the expected results. anyway a mechanism by which you could "fix" it would perhaps be to store a m_visited member variable per each "square" or whatever. So whenever you go to set the height of a location you first check it's m_visited state, if it's false you set the height and set m_visited = true;. like i said though you're not using the correct algorithm so i don't know if it'll actually produce nice looking terrain.

AFAIK you're turning a O(n) into an 0(n^2) so you're seriously screwing over performance.

-me

##### Share on other sites
No you don t have to recode your grid implementation

Just keep the 2D grid and use a 2d deterministic perlin noise

This function returns the same pseudo random numbers for each pair of (X,Y) coordinates with the same seed value.
I had the same problem a few weeks ago and this one solved it.
//generates a 2d perlin noise	inline float32	perlinnoise(int32 x, int32 y, int32 iSeed)	{		int n = x + y*57 + iSeed*131;		n = (n<<13)^n;		return (1.0f - ((n * (n * n * 15731 + 789221) + 1376312589) &0x7fffffff)* 0.000000000931322574615478515625f);	};

##### Share on other sites
Thanks Basiror, I tried using that function but i just seem to get a flat terrain. Do the x y coordinates have to be integer values as im using floating points? What kind of form does the seed take on, is it just a roughness factor which is the same over all the terrain? What kind of values have you been using for the seed to get good results? Thanks Neil

##### Share on other sites
The function returns values between -1.0f and 1.0f you need to multiply the results with your roughness factor.

The seed is just to there to generate different noise distributions for equal x,y values.

You need to convert the float x,y to integers anyways since the function is doing some integer arithmetic in the first few lines (<<,^,&)

Hope that helps

##### Share on other sites
Nope still just gettig a flat square damn it.

Point *PerlinNoise(float x, float y, float roughness, int seed){     int n = int(x*100) + int(y*100)*57 + seed * 131;     n = (n<<13)^n;     n = (1.0f - ((n * (n * n * 15731 + 789221) + 1376312589) &0x7fffffff)*                0.000000000931322574615478515625f);		     Point *displacement = new Point(0.0, n*roughness, 0.0);     return displacement;}

using int(time(NULL)) as the seed, i multiplied x and y by 100 before making them ints as their floats in a fairly close range so thought i best spread them out a bit so i dont get all the same value.

It just seems to return n=0.0 for all values of x and y, any ideas?

1. 1
2. 2
3. 3
Rutin
15
4. 4
khawk
14
5. 5
frob
12

• 9
• 11
• 11
• 23
• 12
• ### Forum Statistics

• Total Topics
633660
• Total Posts
3013224
×