Creating a Quadtree with a Height-map generated Terrain.

Started by
38 comments, last by ChaosPhoenix 17 years, 7 months ago
Quote:Original post by TheAdmiral
Actually, no. I fixed the fencepost error so that all the patches render seamlessly. The problem (I did say, a couple of posts back) is that your 'spacing' is not a divisor of the patch dimension. In the mesh creation routine, you have
for(int z = m_iMinZ; z <= m_iMaxZ; z += CHeightMap::GetInstance()->GetSpacing())

Currently, the iCellSpacing value isn't a factor of 47, the patch dimension, so z is overshooting m_iMaxZ and the last row & column of quads isn't getting created.

I fixed this by setting iCellSpacing to 1. Any value will do so long as it goes into the patch width perfectly. Unfortunately for you, 47 is a prime number so only 1 will do in this case. Perhaps you could tweak your map width or triangles-per-patch threshold.

Regards
Admiral


(Sorry for the late reply, busy weekend)

Ah, I think I understand. But how can you control something like patch dimension or get a good mathematic equation to determine patch dimension? According to my math I'm coming up with something like 60 triangles per patch. Setting the CellSpacing to 1 does seem to work, but obviously it makes the terrain look like garbage.
Advertisement
I don't like the way you've organised your scaling functions, but I didn't touch them in case they were part of some greater scheme I was unaware of.

A reliable method of scaling your terrain involves only a uniform scaling factor (GetScale(), shall we say) and perhaps a height-scale (GetHeightScale()), if your heightmap image didn't take care of it for you. I'm assuming you're not planning on implementing any geomipmapping ('cause then things get a bit more complicated).

When creating the mesh, you should calculate absolutely everything as if it were on a 1:1:1 scale (so there will be no need to call GetScale, GetSpacing etc. during the loop) but just before you put the data into the buffer, scale the x, y, z values accordingly. This way, you can eliminate the modulus error you're getting. An example follows.

int CQuadTree::NumTrianglesInRange(){	return (m_iMaxX - m_iMinX) * (m_iMaxZ - m_iMinZ) * 2;}void CQuadTree::CreateRenderMesh(){	// Get our triangle count.	int triangleCount = NumTrianglesInRange();	CHeightMap::terrainVertex* vertex;	if(FAILED(D3DXCreateMeshFVF(triangleCount, (triangleCount *3), D3DXMESH_MANAGED, D3DFVF_XYZ |D3DFVF_TEX1, CRenderer::GetInstance()->GetDevice(), &m_pMesh)))	{		MessageBox(NULL, "FAILED", "FAILED", MB_OK);	}	// Populate the VB.	if(FAILED(m_pMesh->LockVertexBuffer(0, (void**)&vertex)))	{		MessageBox(NULL, "FAILED", "FAILED", MB_OK);	}	int PatchVertexWidth = (m_iMaxX - m_iMinX) + 1;	int vertexIndex = 0;	int i = 0;	int j = 0;	for(int z = m_iMinZ; z <= m_iMaxZ; z += 1)	{		for(int x = m_iMinX; x <= m_iMaxX; x += 1)		{			i = x - m_iMinX;			j = z - m_iMinZ;			int index = j * PatchVertexWidth + i;			float height = CHeightMap::GetInstance()->GetHeightMapEntry(x, z);			vertex[index].x = (float) x GetScale();			vertex[index].y = height * GetScale() * GetHeightScale();			// vertex[index].y = 0.0f;			vertex[index].z = (float) z GetScale();			vertex[index].u = 0.0f;			vertex[index].v = 0.0f;		}	}	if(FAILED(m_pMesh->UnlockVertexBuffer()))	{		MessageBox(NULL, "FAILED", "FAILED", MB_OK);	}	// Populate the Index Buffer.	WORD* indexBuffer = 0;	if(FAILED(m_pMesh->LockIndexBuffer(0, (void**)&indexBuffer)))	{		MessageBox(NULL, "FAILED", "FAILED", MB_OK);	}	int baseIndex = 0;	int PatchIndexXWidth = (m_iMaxX - m_iMinX);	int PatchIndexZWidth = (m_iMaxZ - m_iMinZ);	for(int i = 0; i < PatchIndexZWidth; i++)	{		for(int j = 0; j < PatchIndexXWidth; j++)		{			indexBuffer[baseIndex] = i * PatchVertexWidth + j;			indexBuffer[baseIndex + 1] = i * PatchVertexWidth + j + 1;			indexBuffer[baseIndex + 2] = (i + 1) * PatchVertexWidth + j;			indexBuffer[baseIndex + 3] = (i + 1) * PatchVertexWidth + j;			indexBuffer[baseIndex + 4] = i * PatchVertexWidth + j + 1;			indexBuffer[baseIndex + 5] = (i + 1) * PatchVertexWidth + j + 1;			baseIndex += 6;		}	}	if(FAILED(m_pMesh->UnlockIndexBuffer()))	{		MessageBox(NULL, "FAILED", "FAILED", MB_OK);	}	// Populate attribute buffer, all triangles = Subset 0	DWORD* attributeBuffer = 0;	if(FAILED(m_pMesh->LockAttributeBuffer(0, &attributeBuffer)))	{		MessageBox(NULL, "FAILED", "FAILED", MB_OK);	}	for(int i = 0; i < triangleCount; i++)	{		attributeBuffer = 0;	}	if(FAILED(m_pMesh->UnlockAttributeBuffer()))	{		MessageBox(NULL, "FAILED", "FAILED", MB_OK);	}	// Optimization functions.	DWORD* adjacencyBuffer = new DWORD[m_pMesh->GetNumFaces() * 3];	if(FAILED(m_pMesh->GenerateAdjacency(0.001f, &adjacencyBuffer[0])))	{		MessageBox(NULL, "FAILED", "FAILED", MB_OK);	}	if(FAILED(m_pMesh->OptimizeInplace(D3DXMESHOPT_IGNOREVERTS, &adjacencyBuffer[0], NULL, NULL, NULL)))	{		MessageBox(NULL, "FAILED", "FAILED", MB_OK);	}	delete [] adjacencyBuffer;}


Note that this code requires the quadtree to be initialised with dimensionless values (so XMin etc. represent the number of vertices, rather than the physical size of the terrain). Also GetHeightmapEntry() will need adaptation. In general, dimensionless units are easier to manage, so after all the painstaking conversion, your code will be smaller, cleaner and you'll never look back.

Regards
Admiral
Ring3 Circus - Diary of a programmer, journal of a hacker.
That makes much more sense than the way I've been going about it. Taking out all scaling issues would make division of the heightmap, object placement, and texture issues just disappear.

I am a huge fan of what you just proposed and I'll begin work on converting what I have to what you suggested.
Well, after trying to convert everything (which really wasn't too difficult, basically removing all instances of GetSpacing() and changing a few things around in the for loop like you show), I'm getting some very weird, albeit interesting, results.


(Don't mind the frame rate, this isn't my normal PC and it only has a GeForce 2 MX 200)

Source Code:

CreateRenderMesh
void CQuadTree::CreateRenderMesh(){		// Get our triangle count.		int triangleCount = NumTrianglesInRange();		CHeightMap::terrainVertex* vertex;		if(FAILED(D3DXCreateMeshFVF(triangleCount, (triangleCount *3), D3DXMESH_MANAGED, D3DFVF_XYZ |D3DFVF_TEX1, CRenderer::GetInstance()->GetDevice(), &m_pMesh)))		{			MessageBox(NULL, "FAILED", "FAILED", MB_OK);		}				// Populate the VB.		if(FAILED(m_pMesh->LockVertexBuffer(0, (void**)&vertex)))		{			MessageBox(NULL, "FAILED", "FAILED", MB_OK);		}				int PatchVertexWidth = (m_iMaxX - m_iMinX) + 1;		int vertexIndex = 0;		int i = 0;		int j = 0;		for(int z = m_iMinZ; z <= m_iMaxZ; z += 1)		{					for(int x = m_iMinX; x <= m_iMaxX; x += 1)			{				int index = i * PatchVertexWidth + j;				i = x - m_iMinX;				j = z - m_iMinZ;				int entryX = x * CHeightMap::GetInstance()->GetSpacing();				int entryZ = z * CHeightMap::GetInstance()->GetSpacing();				//vertex[index] = CHeightMap::terrainVertex((float) x, ((float)CHeightMap::GetInstance()->GetHeightMapEntry(entryX, entryZ) * CHeightMap::GetInstance()->GetScale()), (float) z, 0.0f, 0.0f);				vertex[index] = CHeightMap::terrainVertex((float) x, 0, (float) z, 0, 0);							}					}				if(FAILED(m_pMesh->UnlockVertexBuffer()))		{			MessageBox(NULL, "FAILED", "FAILED", MB_OK);		}		// Populate the Index Buffer.		WORD* indexBuffer = 0;		if(FAILED(m_pMesh->LockIndexBuffer(0, (void**)&indexBuffer)))		{			MessageBox(NULL, "FAILED", "FAILED", MB_OK);		}		int baseIndex = 0;		int PatchIndexXWidth = (m_iMaxX - m_iMinX);		int PatchIndexZWidth = (m_iMaxZ - m_iMinZ);		for(int i = 0; i < PatchIndexZWidth; i++)		{			for(int j = 0; j < PatchIndexXWidth; j++)			{				indexBuffer[baseIndex] = i * PatchVertexWidth + j;				indexBuffer[baseIndex + 1] = i * PatchVertexWidth + j + 1;				indexBuffer[baseIndex + 2] = (i + 1) * PatchVertexWidth + j;				indexBuffer[baseIndex + 3] = (i + 1) * PatchVertexWidth + j;				indexBuffer[baseIndex + 4] = i * PatchVertexWidth + j + 1;				indexBuffer[baseIndex + 5] = (i + 1) * PatchVertexWidth + j + 1;								baseIndex += 6;			}		}		if(FAILED(m_pMesh->UnlockIndexBuffer()))		{			MessageBox(NULL, "FAILED", "FAILED", MB_OK);		}				// Populate attribute buffer, all triangles = Subset 0		DWORD* attributeBuffer = 0;		if(FAILED(m_pMesh->LockAttributeBuffer(0, &attributeBuffer)))		{			MessageBox(NULL, "FAILED", "FAILED", MB_OK);		}				for(int i = 0; i < triangleCount; i++)		{			attributeBuffer = 0;		}		if(FAILED(m_pMesh->UnlockAttributeBuffer()))		{			MessageBox(NULL, "FAILED", "FAILED", MB_OK);		}		// Optimization functions.		DWORD* adjacencyBuffer = new DWORD[m_pMesh->GetNumFaces() * 3];		if(FAILED(m_pMesh->GenerateAdjacency(0.001f, &adjacencyBuffer[0])))		{			MessageBox(NULL, "FAILED", "FAILED", MB_OK);		}		if(FAILED(m_pMesh->OptimizeInplace(D3DXMESHOPT_IGNOREVERTS, &adjacencyBuffer[0], NULL, NULL, NULL)))		{			MessageBox(NULL, "FAILED", "FAILED", MB_OK);		}		delete [] adjacencyBuffer;}


GetNumTriangles
int CQuadTree::NumTrianglesInRange(){	//  ( MaxX / Spacing - MinX / Spacing ) * ( MaxZ / Spacing - MinZ / Spacing ) * 2	return (m_iMaxX - m_iMinX) * (m_iMaxZ - m_iMinZ) * 2;}


QuadTree Creation in the Renderer
m_pQuadTree = new CQuadTree(0, (hMap->GetHeightMapWidth() - 1),								0, (hMap->GetHeightMapHeight() - 1), 0);


I'm going to continue to toy with it and debug away, but if you see any glaring oversight, please let me know.
I'm not at my computer at the moment, so I can't test your source, but after a brief inspection, it seems that your vertices are being created out of sync. Either way, the screenshot looks decidedly like an index/vertex buffer mismatch. I think your problem lies with the lines:
int index = i * PatchVertexWidth + j;i = x - m_iMinX;j = z - m_iMinZ;
Since index depends on i and j, it would make sense to update i and j first. If you swap these lines around, it looks a lot like the code I supplied. I'll give it a test when I get back.

Regards
Admiral
Ring3 Circus - Diary of a programmer, journal of a hacker.
Quote:Original post by TheAdmiral
I'm not at my computer at the moment, so I can't test your source, but after a brief inspection, it seems that your vertices are being created out of sync. Either way, the screenshot looks decidedly like an index/vertex buffer mismatch. I think your problem lies with the lines:
int index = i * PatchVertexWidth + j;i = x - m_iMinX;j = z - m_iMinZ;
Since index depends on i and j, it would make sense to update i and j first. If you swap these lines around, it looks a lot like the code I supplied. I'll give it a test when I get back.

Regards
Admiral


Yea, I actually saw that and changed the code to see if it would fix the issue, turns out it made it worse. :D

I'm still playing with it in my spare time, let me know anything you find out.
One more point: When creating the root of the quadtree, you shouldn't subtract one from the heightmap dimensions. The quadtree class creates geometry within, but spanning the coordinates it receives. So the coordinates are exclusive: If you want 100 quads across, pass (0, 100) as the X extremals. This won't fix your rendering issues though [wink].

If you upload your current source, I'd happily take another look at it. It looks like you're on the brink of having the quadtree working perfectly. I guess I'd like to be there when she blossoms [smile].

Regards
Admiral
Ring3 Circus - Diary of a programmer, journal of a hacker.
Quote:Original post by TheAdmiral
One more point: When creating the root of the quadtree, you shouldn't subtract one from the heightmap dimensions. The quadtree class creates geometry within, but spanning the coordinates it receives. So the coordinates are exclusive: If you want 100 quads across, pass (0, 100) as the X extremals. This won't fix your rendering issues though [wink].

If you upload your current source, I'd happily take another look at it. It looks like you're on the brink of having the quadtree working perfectly. I guess I'd like to be there when she blossoms [smile].

Regards
Admiral


Again, I can't thank you enough for all the help. Graphics programming and related data structures is defintely my weakest field in games programming, but I'm slowly getting better.

I messed with the code last night and got it ~95% working. There are no gaps, it uses the height map correctly, however I'm getting 2 extra rows of Quads on each side of the map. It originally was causing extremely strange looking geometry (since the height map was returning invalid values when you tried to look up a value not in range), but I changed the height map class to just return 0 if the value is out of range. You can pretty easily see where the height map ends and the extra quads are being shown. I wanted to play with it some more but I didn't get the time.

Here is the updated source:
http://www.animehack.com/source/Terrain%20Generator(Updated).rar

Also, on a related note, for terrain following which would be the best path? I've heard of 2 formulas (and implemented one of those versions before); using a list of triangles to find the closest triangle to the player and align to it, or using the heightmap and Lerp to align to the triangle closest to the player.
Regarding terrain following, the 'nearest triangle' method is a little unnecessary for most smooth heightmaps. I guess the rule is that if you can't see any noticeably sharp edges in the terrain then calculating which triangle of the quad the actor is on is wasteful.
Lerping between the precalculated heightmap normals (which you can get DirectX to calculate for you) tends to do the trick with minimal processor waste.

Regards
Admiral
Ring3 Circus - Diary of a programmer, journal of a hacker.
Quote:Original post by TheAdmiral
Regarding terrain following, the 'nearest triangle' method is a little unnecessary for most smooth heightmaps. I guess the rule is that if you can't see any noticeably sharp edges in the terrain then calculating which triangle of the quad the actor is on is wasteful.
Lerping between the precalculated heightmap normals (which you can get DirectX to calculate for you) tends to do the trick with minimal processor waste.

Regards
Admiral


Sounds good to me.

Any thoughts on the extra Quads being drawn?

This topic is closed to new replies.

Advertisement