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??