Jump to content
  • Advertisement
Sign in to follow this  
brandonman

Diamond-Square trouble

This topic is 4105 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

Hey everyone. I've been reading up on he diamond-square algorithm for terrain and understand, sort of. I dont get how, after you do the first diamond and first square iterations, how you get to the next. How does the algorithm know how many squares there are and also, this is confusing, but what point is the center of what points. Like, say you have a 2d array of points that is 5 by 5. it goes: a b c d e f g h i j k l m n o p q r s t u v w x y How does it know that g is the center of a,b,c,h,m,l,k, and f? How does it find what points' heights to average together to equal another points height?

Share this post


Link to post
Share on other sites
Advertisement
The area is still a grid in "mind"... it's only the presentation that renders objects like diamonds. Using simple x,y divisions should provide you with the info you need from each tile.

Alternativly;

Each tile is independent of the rest, can be placed anywhere etc.
But it keeps a list of it's neighbours instead.

Quote:

How does it know that g is the center of a,b,c,h,m,l,k, and f? How does it find what points' heights to average together to equal another points height?

Someone once said - you created it, you should know. :)

Cheers!

Share this post


Link to post
Share on other sites
Diamond Square
After each iteration you devide the size of each square by 2. Then (size_of_grid - 1) / square_size = number_of_squares_per_side. The center point basically is one of the corners offset by square_size/2.

Example:

I'll also a 2D array for easier reading and rename your points to indices. Changing the example to a 1D array representation is an exercise for you.

OK, let's start:

The array is:

00 01 02 03 04
10 11 12 13 14
20 21 22 23 24
30 31 32 33 34
40 41 42 43 44

LEVEL 0:
Your fist square is 00, 04, 40, 44. It's center is 22 ((square_size(4) / 2 for both indices). Square size is 4, number of squares per side is (5 - 1) / 4 = 1.

Now you do square_size/2 => 4/2 = square_size = 2.

LEVEL 1:
For the next iteration we get:
square_size = 2
num_squares_per_side = (5 - 1) / 2 = 2

With this the squares in that iteration are:
SQ1: 00, 02, 20, 22 C1: 11
SQ2: 02, 04, 22, 24 C2: 13
SQ3: 20, 22, 40, 42 C3: 31
SQ4: 22, 24, 42, 44 C4: 33

That's it. Keep doing this until square_size = 2, since in the next step you won't get any integer center points.


Caution
Using diamond square for averaging points (e.g. midpoint displacement) you have to make sure all the points needed for averaging have their values assigned yet. This is tricky with a recursive approach so for every level you should first do all the square steps and then all the diamond steps. Otherwise you'd get wrong results since the diamond steps depend on the square steps to fill in the correct values first.

Share this post


Link to post
Share on other sites
Its been a while since I implemented this algorithm, but I sort of remember how it goes. As I remember it took a many sheets of paper and much confusion.

As you iterate and recurse through levels, quads, vertices, you only know a few things:

1) current recursion level in your diamond-square descent
2) your starting corner index
3) current quad you're processing as you iterate (through x and z)

Everything else you calculate.

So as you recurse through the levels of division (diamond-square), you calculate the indices of your corners, the width of the quad, the vertices of your corners, the center indices for splitting, the indices of your parent's corners and midpoint, etc.

You could preseed the array with y values from a height map, or look them up as your're subdividing. You have to watch out for corner and edge cases when averaging your neighbors or parents, depending how you implement the height calculations.

I wanted to do it totally algorithmicly so I wrote some noise randomizer classes using boost::random that passes the parents seeds down to each sublevel so I could regenerate the displacements based on just a few early seed values.

Try starting by creating an array that will hold all the verts. So if you wanted to end up with a X square quads terrain patch, you'd create an array of ((X+1) * (X+1) floats, and pre-seed the array with the corner verts and your random heights.

Well, I hope that helps you get started. Its not totally trivial, lots of staring at numbers in the debugger and drawing grids of dots on the page. Keep staring at it, and it will eventually make sense. Start with a small grid and just a few levels of recursion, so its easy to debug. Of course use powers of 2 for the width and you'll get really used to relating the vertex values to the quads they're part of.

Share this post


Link to post
Share on other sites
Just a little question:

Did you use a breadth first (complete level first then next level) or a depth first (fully subdivide a square first then advance to its neighbors) approach ?
If you used depth first, how did you handle cases where needed values aren't properly initialized?

Share this post


Link to post
Share on other sites
Found some code, but I'm not sure what state its in. I worked on this quite a while ago. Looks like I'm actually not doing this recursively, but rather iterating through the levels. This is in the context of a Terrain object which holds a MultilevelTerrainObject (that can handle lod-ing and edge matchup), which holds multiple TerrainChunk objects, each of which holds multiple VertexGrid objects. Not sure if this is the exact diamond-square algorithm as originally envisioned, but I think its sort of close at the VertexGrid level.



#define VERTEX_INDEX(x, z) (((z) * m_WidthVertices) + (x))

void VertexGrid::generateDiamondSquare(int levels, float3* corners)
{
ostringstream logmsg;
logmsg << "generateDiamondSquare(" << levels << ", (" <<
float3ToString(corners[0]) << ", " <<
float3ToString(corners[1]) << ", " <<
float3ToString(corners[2]) << ", " <<
float3ToString(corners[3]) << ")" << endl;
log(1, logmsg);

m_RandomFloatizer->seed(m_GridSeed);

int totalWidthQuads = 1 << levels;
int totalWidthVertices = totalWidthQuads + 1;
int totalNumVertices = totalWidthVertices * totalWidthVertices;
m_WidthVertices = totalWidthVertices;

// allocate vertex array
m_Vertices = new float3[totalNumVertices];

// set outside corners
// corners[x] -- LeftNear = 0, LeftFar = 1, RightFar = 2, RightNear = 3
int lastVertexIndex = totalWidthVertices - 1;
m_Vertices[VERTEX_INDEX(0, 0)] = corners[LeftNear];
m_Vertices[VERTEX_INDEX(0, lastVertexIndex)] = corners[LeftFar];
m_Vertices[VERTEX_INDEX(lastVertexIndex, lastVertexIndex)] = corners[RightFar];
m_Vertices[VERTEX_INDEX(lastVertexIndex, 0)] = corners[RightNear];

for (int level = 0; level < levels; level++)
{
int numQuadsWide = 1 << level;
int numVerticesWide = numQuadsWide + 1;
int quadWidth = totalWidthQuads / numQuadsWide;
int halfWidth = quadWidth / 2;

// Diamond pass
for (int quadZ = 0; quadZ < numQuadsWide; quadZ++)
{
for (int quadX = 0; quadX < numQuadsWide; quadX++)
{
int leftX = quadX * quadWidth;
int rightX = (quadX + 1) * quadWidth;
int nearZ = quadZ * quadWidth;
int farZ = (quadZ + 1) * quadWidth;

// diamond step - find center of square
// find indices of quad corners - based on level, quadx, quadz
int cornerLeftNear = VERTEX_INDEX(leftX, nearZ);
int cornerLeftFar = VERTEX_INDEX(leftX, farZ);
int cornerRightFar = VERTEX_INDEX(rightX, farZ);
int cornerRightNear = VERTEX_INDEX(rightX, nearZ);
int centerIndex = VERTEX_INDEX(leftX + halfWidth, nearZ + halfWidth);

float centerX = (m_Vertices[cornerLeftNear].x + m_Vertices[cornerRightNear].x) / 2.0f;
float centerZ = (m_Vertices[cornerLeftNear].z + m_Vertices[cornerLeftFar].z) / 2.0f;
float centerY = (( m_Vertices[cornerLeftNear].y +
m_Vertices[cornerLeftNear].y +
m_Vertices[cornerLeftNear].y +
m_Vertices[cornerLeftNear].y) / 4.0f)
+ randomHeightDisplacement(level);
m_Vertices[centerIndex] = float3(centerX, centerY, centerZ);
}
}

// Square pass
for (int quadZ = 0; quadZ < numQuadsWide; quadZ++)
{
for (int quadX = 0; quadX < numQuadsWide; quadX++)
{
int leftX = quadX * quadWidth;
int rightX = (quadX + 1) * quadWidth;
int nearZ = quadZ * quadWidth;
int farZ = (quadZ + 1) * quadWidth;

int cornerLeftNear = VERTEX_INDEX(leftX, nearZ);
int cornerLeftFar = VERTEX_INDEX(leftX, farZ);
int cornerRightFar = VERTEX_INDEX(rightX, farZ);
int cornerRightNear = VERTEX_INDEX(rightX, nearZ);
int centerIndex = VERTEX_INDEX(leftX + halfWidth, nearZ + halfWidth);
float edgeLeftX = m_Vertices[cornerLeftNear].x;
float edgeFarZ = m_Vertices[cornerRightFar].z;
float edgeRightX = m_Vertices[cornerRightFar].x;
float edgeNearZ = m_Vertices[cornerLeftNear].z;

// leftX edge center point
int edgeLeftCenterIndex = VERTEX_INDEX(leftX, nearZ + halfWidth);
int edgeLeftDiamondLeftIndex = ((leftX == 0) ? -1 : VERTEX_INDEX(leftX - halfWidth, nearZ + halfWidth));
int edgeLeftDiamondFarIndex = VERTEX_INDEX(leftX, farZ);
int edgeLeftDiamondRightIndex = centerIndex;
int edgeLeftDiamondNearIndex = VERTEX_INDEX(leftX, nearZ);
float edgeLeftCenterX = edgeLeftX;
float edgeLeftCenterZ = (m_Vertices[cornerLeftNear].z + m_Vertices[cornerLeftFar].z) / 2.0f;
float edgeLeftCenterY;
if (leftX == 0)
{
edgeLeftCenterY = ((m_Vertices[edgeLeftDiamondFarIndex].y +
m_Vertices[edgeLeftDiamondRightIndex].y +
m_Vertices[edgeLeftDiamondNearIndex].y)
/ 3.0f)
+ randomHeightDisplacement(level);
}
else
{
edgeLeftCenterY = ((m_Vertices[edgeLeftDiamondLeftIndex].y +
m_Vertices[edgeLeftDiamondFarIndex].y +
m_Vertices[edgeLeftDiamondRightIndex].y +
m_Vertices[edgeLeftDiamondNearIndex].y)
/ 4.0f)
+ randomHeightDisplacement(level);
}
m_Vertices[edgeLeftCenterIndex] = float3(edgeLeftCenterX, edgeLeftCenterY, edgeLeftCenterZ);

// Far edge center point
int edgeFarCenterIndex = VERTEX_INDEX(leftX + halfWidth, farZ);
int edgeFarDiamondLeftIndex = VERTEX_INDEX(leftX, farZ);
int edgeFarDiamondFarIndex = ((farZ == lastVertexIndex) ? -1 : VERTEX_INDEX(leftX + halfWidth, farZ + halfWidth));
int edgeFarDiamondRightIndex = VERTEX_INDEX(rightX, farZ);
int edgeFarDiamondNearIndex = centerIndex;

float edgeFarCenterX = (m_Vertices[cornerLeftFar].x + m_Vertices[cornerRightFar].z) / 2.0f;;
float edgeFarCenterZ = edgeFarZ;
float edgeFarCenterY;
if (farZ == lastVertexIndex)
{
edgeFarCenterY = (( m_Vertices[edgeFarDiamondLeftIndex].y +
m_Vertices[edgeFarDiamondRightIndex].y +
m_Vertices[edgeFarDiamondNearIndex].y)
/ 3.0f)
+ randomHeightDisplacement(level);
}
else
{
edgeFarCenterY = (( m_Vertices[edgeFarDiamondLeftIndex].y +
m_Vertices[edgeFarDiamondFarIndex].y +
m_Vertices[edgeFarDiamondRightIndex].y +
m_Vertices[edgeFarDiamondNearIndex].y)
/ 4.0f)
+ randomHeightDisplacement(level);
}
m_Vertices[edgeFarCenterIndex] = float3(edgeFarCenterX, edgeFarCenterY, edgeFarCenterZ);

// Right edge center point
int edgeRightCenterIndex = VERTEX_INDEX(rightX, nearZ + halfWidth);
int edgeRightDiamondLeftIndex = centerIndex;
int edgeRightDiamondFarIndex = VERTEX_INDEX(rightX, farZ);
int edgeRightDiamondRightIndex = ((rightX == lastVertexIndex) ? -1 : VERTEX_INDEX(rightX + halfWidth, nearZ + halfWidth));
int edgeRightDiamondNearIndex = VERTEX_INDEX(rightX, nearZ);
float edgeRightCenterX = edgeRightX;
float edgeRightCenterZ = (m_Vertices[cornerRightNear].z + m_Vertices[cornerRightFar].z) / 2.0f;
float edgeRightCenterY;
if (rightX == lastVertexIndex)
{
edgeRightCenterY = ((m_Vertices[edgeRightDiamondLeftIndex].y +
m_Vertices[edgeRightDiamondFarIndex].y +
m_Vertices[edgeRightDiamondNearIndex].y)
/ 3.0f)
+ randomHeightDisplacement(level);
}
else
{
edgeRightCenterY = ((m_Vertices[edgeRightDiamondLeftIndex].y +
m_Vertices[edgeRightDiamondFarIndex].y +
m_Vertices[edgeRightDiamondRightIndex].y +
m_Vertices[edgeRightDiamondNearIndex].y)
/ 4.0f)
+ randomHeightDisplacement(level);
}
m_Vertices[edgeRightCenterIndex] = float3(edgeRightCenterX, edgeRightCenterY, edgeRightCenterZ);

// Near edge center point
int edgeNearCenterIndex = VERTEX_INDEX(leftX + halfWidth, nearZ);
int edgeNearDiamondLeftIndex = VERTEX_INDEX(leftX, nearZ);
int edgeNearDiamondFarIndex = centerIndex;
int edgeNearDiamondRightIndex = VERTEX_INDEX(rightX, nearZ);
int edgeNearDiamondNearIndex = ((nearZ == 0) ? -1 : VERTEX_INDEX(leftX + halfWidth, nearZ - halfWidth));
float edgeNearCenterX = (m_Vertices[cornerLeftNear].x + m_Vertices[cornerRightNear].x) / 2.0f;
float edgeNearCenterZ = edgeNearZ;
float edgeNearCenterY;
if (nearZ == 0)
{
edgeNearCenterY = ((m_Vertices[edgeNearDiamondLeftIndex].y +
m_Vertices[edgeNearDiamondFarIndex].y +
m_Vertices[edgeNearDiamondRightIndex].y)
/ 3.0f)
+ randomHeightDisplacement(level);
}
else
{
edgeNearCenterY = ((m_Vertices[edgeNearDiamondLeftIndex].y +
m_Vertices[edgeNearDiamondFarIndex].y +
m_Vertices[edgeNearDiamondRightIndex].y +
m_Vertices[edgeNearDiamondNearIndex].y)
/ 4.0f)
+ randomHeightDisplacement(level);
}
m_Vertices[edgeNearCenterIndex] = float3(edgeNearCenterX, edgeNearCenterY, edgeNearCenterZ);
}
}
}
}


Share this post


Link to post
Share on other sites
Quote:

Did you use a breadth first (complete level first then next level) or a depth first (fully subdivide a square first then advance to its neighbors) approach ?
If you used depth first, how did you handle cases where needed values aren't properly initialized?


Oh, to answer your question it looks pretty much breadth first. Each level is totally filled in before you get to the next.

Share this post


Link to post
Share on other sites
I tried again, and just made a 5x5 heightmap as an array and tried to render it... didn't go well. The window comes up but it is blank, nothing is drawn.
code:
heightmap:

float heightmap[5][5] =
{{ '0', '0', '0', '0', '0' },
{ '0', '0', '0', '0', '0' },
{ '0', '0', '0', '0', '0' },
{ '0', '0', '0', '0', '0' },
{ '0', '0', '0', '0', '0' }};



drawglscene:

int DrawGLScene(GLvoid) // Here's Where We Do All The Drawing
{
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT); // Clear Screen And Depth Buffer
glLoadIdentity(); // Reset The Current Modelview Matrix
glTranslatef(0.0f,0.0f,-5.0f);
glColor3f(0.0f,1.0f,0.1f);
float scale = 1.0f;


for(int z = 0; z &lt; 5 - 1; z++)
{
for(int x = 0; x &lt; 5 - 1; x++)
{
glBegin(GL_QUADS);
glVertex3f(x * scale, heightmap[z][x], z * scale);
glVertex3f((x + 1) * scale, heightmap[z][x + 1], z * scale);
glVertex3f((x + 1) * scale, heightmap[z + 1][x + 1], (z + 1) * scale);
glVertex3f(x * scale, heightmap[z + 1][x], (z + 1) * scale);
glEnd();
}
}



thanks in advance.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!