Sign in to follow this  

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.

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

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;


Free Image Hosting at www.ImageShack.us Any help or suggestions would be appreciated Thanks

Share this post


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


Link to post
Share on other sites
Quote:
Original post by Trienco
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...


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


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


Link to post
Share on other sites
Quote:
Original post by Trienco
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.



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

Share this post


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

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