Sign in to follow this  

Fractal Terrain - Midpoint displacement problem

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

If you intended to correct an error in the post then please contact us.

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<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<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->SubDivide(subSquares, roughness, xMax, xMin, yMax, yMin);

			// Add the new squares to the end of the list
			for(int k=0; k<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->MidPoint(b);
	Point *bc = b->MidPoint(c);
	Point *cd = c->MidPoint(d);
	Point *da = d->MidPoint(a);

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

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

	if(bc->x != xMax && bc->x != xMin && bc->y != yMax && bc->y != yMin)
		bc->add(RandomDisplacement(roughness));

	if(cd->x != xMax && cd->x != xMin && cd->y != yMax && cd->y != yMin)
		cd->add(RandomDisplacement(roughness));

	if(da->x != xMax && da->x != xMin && da->y != yMax && da->y != yMin)
		da->add(RandomDisplacement(roughness));

	m->add(RandomDisplacement(roughness));

	// 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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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?

Share this post


Link to post
Share on other sites
Whats your roughness factor?
The code looks correct.
My roughness factor decreases each midpoint interation

16.0f->8.0f->4.0f...

But 1 thing:
Don t return a instance allocated with new from that function do it outside and pass the functions result directly or return it by value.
This often is a source of memory leaks. I also hope you use the STL containers.

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this