# Midpoint displacment after 8 iterations.

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

## Recommended Posts

Hello Everyone im having some problems with a mid-point displacment algorithm i've put together, the problem is, once i reach 8 or more iterations the terrain is displayed strangely with out of place vertices, have a look at the image. the algorithm works great for any terrain under 8 iterations but once the size and iteration reaches 8 and 257 it messes up. I think it all works really well until i get to the 8th iterations looks like really nice terrain :) my generation code
	int numberOfIterations = iNumberOfIterations;
while(pow(2.0f, iNumberOfIterations) > ixSize)
{
iNumberOfIterations -= 1;
}

m_iNumberOfCellsPerRow = pow(2.0, iNumberOfIterations);
m_iNumberOfCellsPerCol = pow(2.0, iNumberOfIterations);
m_iNumberOfVertsPerRow = m_iNumberOfCellsPerRow + 1;
m_iNumberOfVertsPerCol = m_iNumberOfCellsPerCol + 1;

m_iWidth = ixSize;
m_iDepth = izSize;
m_iNumberOfVertices = m_iNumberOfVertsPerRow * m_iNumberOfVertsPerCol;
m_iNumberOfTriangles = m_iNumberOfCellsPerRow * m_iNumberOfCellsPerCol * 2;

int numberOfXSquares = 1;
int numberOfZSquares = 1;
int numberOfSquares = numberOfXSquares * numberOfZSquares;
float displacement = 100.0f;

m_hdHeightData = new HeightData[m_iNumberOfVertices];

ClearHeightData();

if(numberOfIterations == 0)
{
m_hdHeightData[0].fHeight = 0.0f;
m_hdHeightData[1].fHeight = 0.0f;
m_hdHeightData[2].fHeight = 0.0f;
m_hdHeightData[3].fHeight = 0.0f;
}

int index = 0;
int indexa = 0;
int indexb = 0;
int indexc = 0;
int indexd = 0;

float average = 0.0f;

for(int n = 0; n < numberOfIterations; n++)
{
int sizeXOfSquare = m_iNumberOfCellsPerRow / numberOfXSquares;
int sizeZOfSquare = m_iNumberOfCellsPerCol / numberOfZSquares;
for(int x = 0; x < numberOfXSquares; x++)
{
for(int z = 0; z < numberOfZSquares; z++)
{
index = (m_iNumberOfVertsPerRow * (z * sizeZOfSquare + sizeZOfSquare / 2)) + (x * sizeZOfSquare + sizeZOfSquare / 2);

indexa = (m_iNumberOfVertsPerRow * (z * sizeZOfSquare)) + (x * sizeZOfSquare + sizeZOfSquare);
indexb = (m_iNumberOfVertsPerRow * (z * sizeZOfSquare + sizeZOfSquare)) + (x * sizeZOfSquare);
indexc = (m_iNumberOfVertsPerRow * (z * sizeZOfSquare)) + (x * sizeZOfSquare);
indexd = (m_iNumberOfVertsPerRow * (z * sizeZOfSquare + sizeZOfSquare)) + (x * sizeZOfSquare + sizeZOfSquare);

average = (m_hdHeightData[indexa].fHeight + m_hdHeightData[indexb].fHeight
+ m_hdHeightData[indexc].fHeight + m_hdHeightData[indexd].fHeight) / 4;

if(m_hdHeightData[index].bSized == false)
{
m_hdHeightData[index].fHeight = average + RandomNumber(-displacement, displacement);
m_hdHeightData[index].bSized = true;
}
}
}

for(int x = 0; x < numberOfXSquares; x++)
{
for(int z = 0; z < numberOfZSquares; z++)
{
index = (m_iNumberOfVertsPerRow * (z * sizeZOfSquare + sizeZOfSquare / 2)) + (x * sizeXOfSquare);

indexa = (m_iNumberOfVertsPerRow * (z * sizeZOfSquare)) + (x * sizeXOfSquare);
indexb = (m_iNumberOfVertsPerRow * (z * sizeZOfSquare + sizeZOfSquare / 2)) + (x * sizeXOfSquare + sizeXOfSquare / 2);
indexc = (m_iNumberOfVertsPerRow * (z * sizeZOfSquare + sizeZOfSquare)) + (x * sizeXOfSquare);
if(x != 0 )
{
indexd = (m_iNumberOfVertsPerRow * (z * sizeZOfSquare + sizeZOfSquare / 2)) + (x * sizeXOfSquare - sizeXOfSquare / 2);
average = (m_hdHeightData[indexa].fHeight + m_hdHeightData[indexb].fHeight +
m_hdHeightData[indexc].fHeight + m_hdHeightData[indexd].fHeight) / 4;
}
else
{
average = (m_hdHeightData[indexa].fHeight + m_hdHeightData[indexb].fHeight +
m_hdHeightData[indexc].fHeight) / 3;
}
if(m_hdHeightData[index].bSized == false)
{
m_hdHeightData[index].fHeight = average + RandomNumber(-displacement, displacement);
m_hdHeightData[index].bSized = true;
}

index = (m_iNumberOfVertsPerRow * (z * sizeZOfSquare)) + (x * sizeXOfSquare + sizeXOfSquare / 2);

indexa = (m_iNumberOfVertsPerRow * (z * sizeZOfSquare)) + (x * sizeXOfSquare);
indexb = (m_iNumberOfVertsPerRow * (z * sizeZOfSquare + sizeZOfSquare / 2)) + (x * sizeXOfSquare + sizeXOfSquare / 2);
indexc = (m_iNumberOfVertsPerRow * (z * sizeZOfSquare)) + (x * sizeXOfSquare + sizeXOfSquare);

average = (m_hdHeightData[indexa].fHeight + m_hdHeightData[indexb].fHeight +
m_hdHeightData[indexc].fHeight) / 3;

if(m_hdHeightData[index].bSized == false)
{
m_hdHeightData[index].fHeight = average + RandomNumber(-displacement, displacement);
m_hdHeightData[index].bSized = true;
}

index = (m_iNumberOfVertsPerRow * (z * sizeZOfSquare + sizeZOfSquare)) + (x * sizeXOfSquare + sizeXOfSquare / 2);

indexa = (m_iNumberOfVertsPerRow * (z * sizeZOfSquare + sizeZOfSquare / 2)) + (x * sizeXOfSquare + sizeXOfSquare / 2);
indexb = (m_iNumberOfVertsPerRow * (z * sizeZOfSquare + sizeZOfSquare)) + (x * sizeXOfSquare);
indexc = (m_iNumberOfVertsPerRow * (z * sizeZOfSquare + sizeZOfSquare)) + (x * sizeXOfSquare + sizeXOfSquare);

average = (m_hdHeightData[indexa].fHeight + m_hdHeightData[indexb].fHeight +
m_hdHeightData[indexc].fHeight) / 3;

if(m_hdHeightData[index].bSized == false)
{
m_hdHeightData[index].fHeight = average + RandomNumber(-displacement, displacement);
m_hdHeightData[index].bSized = true;
}

index = (m_iNumberOfVertsPerRow * (z * sizeZOfSquare + sizeZOfSquare / 2)) + (x * sizeZOfSquare + sizeZOfSquare);

indexa = (z * sizeZOfSquare + sizeZOfSquare) * m_iNumberOfVertsPerRow + (x * sizeXOfSquare + sizeXOfSquare);
indexb = (z * sizeZOfSquare + sizeZOfSquare / 2) * m_iNumberOfVertsPerRow + (x * sizeXOfSquare + sizeXOfSquare / 2);
indexc = (z * sizeZOfSquare) * m_iNumberOfVertsPerRow + (x * sizeXOfSquare + sizeXOfSquare);

average = (m_hdHeightData[indexa].fHeight + m_hdHeightData[indexb].fHeight +
m_hdHeightData[indexc].fHeight) / 3;

if(m_hdHeightData[index].bSized == false)
{
m_hdHeightData[index].fHeight = average + RandomNumber(-displacement, displacement);
m_hdHeightData[index].bSized = true;
}

}
}
displacement *= pow(2,-Roughness);
numberOfSquares = static_cast<int>(pow(2.0, n + 2));
numberOfXSquares = numberOfZSquares = numberOfSquares / 2;
}

// Creates the Vertex buffer we need to use
if(FAILED(d3ddev->CreateVertexBuffer(m_iNumberOfVertices * sizeof(TerrainVertex), D3DUSAGE_WRITEONLY,
D3DFVF_TERRAINVERTEX, D3DPOOL_MANAGED, &m_pVB, 0)))
{
return false;
}

// Generate start and end points so the for loop can fill the terrain buffer
int xStep = (m_iWidth / m_iNumberOfCellsPerRow);
int zStep = (m_iDepth / m_iNumberOfCellsPerCol);

int StartX = 0;
int StartZ = zStep * numberOfZSquares;
int EndX = xStep * numberOfXSquares;
int EndZ = 0;

TerrainVertex *v = NULL;

m_pVB->Lock(0, 0, (void**)&v, 0);

// Set texture Co-ords
float zTex = 0;
float xTexStep = 1.0f / m_iNumberOfCellsPerRow;
float zTexStep = 1.0f / m_iNumberOfCellsPerCol;
int i = 0;

// Loop around filling vertices with heightdata and texture data
for(int z = StartZ; z >= EndZ; z -= zStep)
{
float xTex = 0;
int j = 0;
for(int x = StartX; x <= EndX; x += xStep)
{
int verticesIndex = j * m_iNumberOfVertsPerRow + i;
fprintf(m_pLog, "\nx: %d", v[verticesIndex].x);
fprintf(m_pLog, "\nz: %d", v[verticesIndex].z);
fprintf(m_pLog, "\ny: %f", m_hdHeightData[verticesIndex].fHeight);
fprintf(m_pLog, "\n\n");
v[verticesIndex] = TerrainVertex((static_cast<float>(x) * m_ixScale), (m_hdHeightData[verticesIndex].fHeight - 127.5f) * m_iyScale,
(static_cast<float>(z) * m_izScale), xTex, zTex, xTex, zTex);
j++;
xTex += xTexStep;
}
i++;
zTex += zTexStep;
}

m_pVB->Unlock();

// Create index buffer to allow for faster triangle processing
if(FAILED(d3ddev->CreateIndexBuffer(m_iNumberOfTriangles * 3 * sizeof(WORD), D3DUSAGE_WRITEONLY,
D3DFMT_INDEX16, D3DPOOL_MANAGED, &m_pIB, 0)))
{
return false;
}

WORD *indices = 0;

m_pIB->Lock(0, 0, (void**)&indices, 0);

// Loop around filling index buffer with triangle data.
int baseIndex = 0;
for(int i = 0; i < m_iNumberOfCellsPerCol; i++)
{
for (int j = 0; j < m_iNumberOfCellsPerRow; j++)
{
indices[baseIndex] = i * m_iNumberOfVertsPerRow + j;
indices[baseIndex + 1] = i * m_iNumberOfVertsPerRow + j + 1;
indices[baseIndex + 2] = (i + 1) * m_iNumberOfVertsPerRow + j;
indices[baseIndex + 3] = (i + 1) * m_iNumberOfVertsPerRow + j;
indices[baseIndex + 4] = i * m_iNumberOfVertsPerRow + j + 1;
indices[baseIndex + 5] = (i + 1) * m_iNumberOfVertsPerRow + j + 1;

baseIndex +=6;
}
}

m_pIB->Unlock();

return true;


Any help or suggestions would be appreciated Thanks

##### Share on other sites
Obvious guess:

if(FAILED(d3ddev->CreateIndexBuffer(m_iNumberOfTriangles * 3 * sizeof(WORD), D3DUSAGE_WRITEONLY, D3DFMT_INDEX16, D3DPOOL_MANAGED, &m_pIB, 0)))

I don't think 16bit indices will be enough for your indices with that many vertices...

##### Share on other sites
Quote:
 Original post by TriencoObvious guess:if(FAILED(d3ddev->CreateIndexBuffer(m_iNumberOfTriangles * 3 * sizeof(WORD), D3DUSAGE_WRITEONLY, D3DFMT_INDEX16, D3DPOOL_MANAGED, &m_pIB, 0)))I don't think 16bit indices will be enough for your indices with that many vertices...

Yeah you where right 16bit isnt enough however using 32 is not something i would like to do since its not broadly supported apparently is there an alternative, would i just need to create two terrain objects and render them side by side?

##### Share on other sites
Well, unless your goal is to simply visualize the height map, you probably don't want to draw the whole thing as one big pile of polygons, as this effectively keeps you from culling invisible parts and/or applying any form of LoD.

512x512 might not be big enough for any fancy LoD schemes, but it never hurts to break the terrain up into chunks of anywhere between 32x32 to 128x128, depending on what you're doing with it. The trade off is how precise you can be with culling and LoDs vs. additional render calls.

Next you will wonder, if you should have one vertex buffer per chunk and the smaller the chunks the more you definitely don't. Make use of the offset into the vertex buffer you should be able to specify in your render call (I hope).

If you're also using shaders, you can save a good bit of memory by not having tons of redundant x,z coordinates. Each chunk will have the same x,z coordinates + an offset, so instead of having 512x512 x,z coords (2MB), you'd have for example 64x64 (32kb) (coords) + 8x8 (0,5kb)(offsets). But that's only getting interesting for larger maps.

##### Share on other sites
Quote:
 Original post by TriencoWell, unless your goal is to simply visualize the height map, you probably don't want to draw the whole thing as one big pile of polygons, as this effectively keeps you from culling invisible parts and/or applying any form of LoD.512x512 might not be big enough for any fancy LoD schemes, but it never hurts to break the terrain up into chunks of anywhere between 32x32 to 128x128, depending on what you're doing with it. The trade off is how precise you can be with culling and LoDs vs. additional render calls.Next you will wonder, if you should have one vertex buffer per chunk and the smaller the chunks the more you definitely don't. Make use of the offset into the vertex buffer you should be able to specify in your render call (I hope).If you're also using shaders, you can save a good bit of memory by not having tons of redundant x,z coordinates. Each chunk will have the same x,z coordinates + an offset, so instead of having 512x512 x,z coords (2MB), you'd have for example 64x64 (32kb) (coords) + 8x8 (0,5kb)(offsets). But that's only getting interesting for larger maps.

Ok, well thanks a lot for the reply, very informative, i'll have a busy couple of weeks :P
Thanks again

##### Share on other sites

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