Creating a Quadtree with a Height-map generated Terrain.

242

Author

August 25, 2006 09:54 AM

Well, my QuadTree structure looks complete. However, I'm not drawing any geometry, even when I force all leaf nodes to render(i.e. make everything visible).

Here is my code to create the Mesh, if I had to take a guess I would say the issue is somewhere in here.

void CQuadTree::CreateRenderMesh(){		// Iterate through and find all the triangles within our range.		int triangleCount = 0;		vector<CHeightMap::terrainTriangle*>* pTriangles = CHeightMap::GetInstance()->GetTriangleList();		for(unsigned int i = 0; i < pTriangles->size(); ++i)		{			for (int k = 0; k < 3; ++k)			{				if(((*pTriangles)->vertices[k].x >= m_iMinX) &&					((*pTriangles)->vertices[k].x <= m_iMaxX) &&					((*pTriangles)->vertices[k].z >= m_iMinZ) &&					((*pTriangles)->vertices[k].z <= m_iMaxZ))				{					// One of the Triangles vertices is within range, add the entire triangle.					triangleCount++;					break;				}			}		}		char buffer[256] = {0};		sprintf(buffer, "Render Mesh Create called, NumTriangles %d\n", triangleCount);		CLogger::GetInstance()->WriteToFile(buffer);		// Make sure we found some Triangles.		if(triangleCount)		{			char buffer[256] = {0};			sprintf(buffer, "Creating Renderable Mesh. Triangle Count: %d\n",					triangleCount);			CLogger::GetInstance()->WriteToFile(buffer);			// Begin Creating the actual Mesh.			CHeightMap::terrainVertex* vertex;			D3DXCreateMeshFVF((triangleCount * 2),(triangleCount *3), D3DXMESH_MANAGED, D3DFVF_XYZ |D3DFVF_TEX1, CRenderer::GetInstance()->GetDevice(), &m_pMesh);						m_pMesh->LockVertexBuffer(0, (void**)&vertex);			int vertexIndex = 0;						for(unsigned int i = 0; i < pTriangles->size(); ++i)			{				for (int k = 0; k < 3; ++k)				{					if(((*pTriangles)->vertices[k].x >= m_iMinX) &&						((*pTriangles)->vertices[k].x <= m_iMaxX) &&						((*pTriangles)->vertices[k].z >= m_iMinZ) &&						((*pTriangles)->vertices[k].z <= m_iMaxZ))					{						// Triangle is in range, copy its vertices into our Vertex buffer.						vertex[vertexIndex] = (*pTriangles)->vertices[0];						vertex[vertexIndex+1] = (*pTriangles)->vertices[1];						vertex[vertexIndex+2] = (*pTriangles)->vertices[2];						vertexIndex += 3;												break;					}				}			}			m_pMesh->UnlockVertexBuffer();			WORD* indexBuffer = 0;			m_pMesh->LockIndexBuffer(0, (void**)&indexBuffer);			for(int i = 0; i < (triangleCount * 3); i++)			{				indexBuffer = i;			}			m_pMesh->UnlockIndexBuffer();			DWORD* attributeBuffer = 0;			m_pMesh->LockAttributeBuffer(0, &attributeBuffer);			for(int i = 0; i < triangleCount; i++)			{				attributeBuffer = 0;			}			m_pMesh->UnlockAttributeBuffer();			std::vector<DWORD> adjacencyBuffer(m_pMesh->GetNumFaces() * 3);			m_pMesh->GenerateAdjacency(0.001f, &adjacencyBuffer[0]);			m_pMesh->OptimizeInplace(D3DXMESHOPT_IGNOREVERTS,									 &adjacencyBuffer[0], NULL, NULL, NULL);					}}

Thoughts?

EDIT:

Log file showing the QuadTree is structured correctly and does find Triangles for the mesh:

CQuadTree Constructor called. MinX: 0, MaxX: 504, MinZ: 0, MaxZ: 504, Level: 0 Splicing, Creating more Children. New Level: 0 CQuadTree Constructor called. MinX: 0, MaxX: 252, MinZ: 0, MaxZ: 252, Level: 1 Splicing, Creating more Children. New Level: 1 CQuadTree Constructor called. MinX: 0, MaxX: 126, MinZ: 0, MaxZ: 126, Level: 2 Render Mesh Create called, NumTriangles 496 Creating Renderable Mesh. Triangle Count: 496 CQuadTree Constructor called. MinX: 126, MaxX: 252, MinZ: 0, MaxZ: 126, Level: 2 Render Mesh Create called, NumTriangles 496 Creating Renderable Mesh. Triangle Count: 496 CQuadTree Constructor called. MinX: 0, MaxX: 126, MinZ: 126, MaxZ: 252, Level: 2 Render Mesh Create called, NumTriangles 512 Creating Renderable Mesh. Triangle Count: 512 CQuadTree Constructor called. MinX: 126, MaxX: 252, MinZ: 126, MaxZ: 252, Level: 2 Render Mesh Create called, NumTriangles 512 Creating Renderable Mesh. Triangle Count: 512 CQuadTree Constructor called. MinX: 252, MaxX: 504, MinZ: 0, MaxZ: 252, Level: 1 Splicing, Creating more Children. New Level: 1 CQuadTree Constructor called. MinX: 252, MaxX: 378, MinZ: 0, MaxZ: 126, Level: 2 Render Mesh Create called, NumTriangles 496 Creating Renderable Mesh. Triangle Count: 496 CQuadTree Constructor called. MinX: 378, MaxX: 504, MinZ: 0, MaxZ: 126, Level: 2 Render Mesh Create called, NumTriangles 465 Creating Renderable Mesh. Triangle Count: 465 CQuadTree Constructor called. MinX: 252, MaxX: 378, MinZ: 126, MaxZ: 252, Level: 2 Render Mesh Create called, NumTriangles 512 Creating Renderable Mesh. Triangle Count: 512 CQuadTree Constructor called. MinX: 378, MaxX: 504, MinZ: 126, MaxZ: 252, Level: 2 Render Mesh Create called, NumTriangles 480 Creating Renderable Mesh. Triangle Count: 480 CQuadTree Constructor called. MinX: 0, MaxX: 252, MinZ: 252, MaxZ: 504, Level: 1 Splicing, Creating more Children. New Level: 1 CQuadTree Constructor called. MinX: 0, MaxX: 126, MinZ: 252, MaxZ: 378, Level: 2 Render Mesh Create called, NumTriangles 512 Creating Renderable Mesh. Triangle Count: 512 CQuadTree Constructor called. MinX: 126, MaxX: 252, MinZ: 252, MaxZ: 378, Level: 2 Render Mesh Create called, NumTriangles 512 Creating Renderable Mesh. Triangle Count: 512 CQuadTree Constructor called. MinX: 0, MaxX: 126, MinZ: 378, MaxZ: 504, Level: 2 Render Mesh Create called, NumTriangles 496 Creating Renderable Mesh. Triangle Count: 496 CQuadTree Constructor called. MinX: 126, MaxX: 252, MinZ: 378, MaxZ: 504, Level: 2 Render Mesh Create called, NumTriangles 496 Creating Renderable Mesh. Triangle Count: 496 CQuadTree Constructor called. MinX: 252, MaxX: 504, MinZ: 252, MaxZ: 504, Level: 1 Splicing, Creating more Children. New Level: 1 CQuadTree Constructor called. MinX: 252, MaxX: 378, MinZ: 252, MaxZ: 378, Level: 2 Render Mesh Create called, NumTriangles 512 Creating Renderable Mesh. Triangle Count: 512 CQuadTree Constructor called. MinX: 378, MaxX: 504, MinZ: 252, MaxZ: 378, Level: 2 Render Mesh Create called, NumTriangles 480 Creating Renderable Mesh. Triangle Count: 480 CQuadTree Constructor called. MinX: 252, MaxX: 378, MinZ: 378, MaxZ: 504, Level: 2 Render Mesh Create called, NumTriangles 496 Creating Renderable Mesh. Triangle Count: 496 CQuadTree Constructor called. MinX: 378, MaxX: 504, MinZ: 378, MaxZ: 504, Level: 2 Render Mesh Create called, NumTriangles 465 Creating Renderable Mesh. Triangle Count: 465

rgirard413

133

August 25, 2006 03:24 PM

this isnt an answer to your question but i have to ask. Why are you looping through all the triangles twice? I would think you would just loop through them once and if they are in your bounding box, put them in this leaf and increment the triangle count. then if you have a triangle count, fill your vertex buffer. Maybe im wrong though?

http://www.thedizzle.com

ChaosPhoenix

242

Author

August 25, 2006 03:41 PM

Quote:Original post by rgirard413
this isnt an answer to your question but i have to ask. Why are you looping through all the triangles twice? I would think you would just loop through them once and if they are in your bounding box, put them in this leaf and increment the triangle count. then if you have a triangle count, fill your vertex buffer. Maybe im wrong though?

Yea, I'm not a fan of it either. The problem is I don't know for sure how many triangles each sector has, given that some triangles may be overlapping boundaries due to float-to-int truncation and such. I can't create my vertex buffer in my mesh without an exact number of vertices(to my knowledge), so I loop through once to get a count of all the vertices, create my vertex buffer, and finally loop through again to put the vertices in the vertex buffer. I don't keep a vector of triangles when I'm counting through, although that might be a good idea. I may change it to that once I get things rendering properly.

TheAdmiral

1,122

August 25, 2006 05:59 PM

There's something highly tautological about that two-pass geometry construction:

One way to create all the triangles between (MinX, MinZ)-(MaxX, MaxZ) is to cycle through all the triangles in the world, compiling a list of the ones in the specified range, then later iterate over your completed list. Another would be to simply create all the triangles in that range in the first place [wink].

The quadtree and its bounds are axis-aligned, so your patches are regular, orthogonal grids. You should create the geometry something like this:

// Vertex Bufferint c = 0;VERTEX *CurrentVertex = NULL;for (int z = MinZ; z <= MaxZ; z++) {    for (int x = MinX; x <= MaxX; x++) {        CurrentVertex = &m_VertexBuffer[c++];        CurrentVertex.x = (float) x;        CurrentVertex.z = (float) z;        CurrentVertex.y = TerrainHeight(x, z);    }}// Index Bufferc = 0;int XRange = MaxX - MinX;int ZRange = ZMax - ZMin;for (int z = 0; z < ZRange - 1; z++) {    for (int x = 0; x < XRange - 1; x++) {        // Upper-left triangle        m_IndexBuffer[c++] = (float) (z+1) * XRange + (x+0);        m_IndexBuffer[c++] = (float) (z+0) * XRange + (x+1);        m_IndexBuffer[c++] = (float) (z+0) * XRange + (x+0);        // Lower-right triangle        m_IndexBuffer[c++] = (float) (z+1) * XRange + (x+1);        m_IndexBuffer[c++] = (float) (z+0) * XRange + (x+1);        m_IndexBuffer[c++] = (float) (z+1) * XRange + (x+0);    }}

Assuming you're using an index buffer, you simply fill the VB sequentially with every vertex in your axis-aligned range, then fill the IB to connect the grid-points up into pairs of triangles accordingly. If you need varying texture coordinates at triangle junctions, there's no need for an index buffer and the triangle-building code will need to go in the VB construction routine.

I hope this clears things up a bit.
Admiral

Ps: That code hasn't been tested and is for, err, illustrative purposes only [smile].
Edit: I have assumed that your terrain is a regular grid. If not, then you'll need to do things more like you were originally.

Ring3 Circus - Diary of a programmer, journal of a hacker.

ChaosPhoenix

242

Author

August 25, 2006 10:32 PM

I went ahead and just created the vertices as you suggest, but I'm still not able to render anything. Even forcing all meshes in the tree to render(I put a break point at DrawSubset and it is being called) gives me nothing. I have a good camera class so I'm able to wander around the world and I see no sign of the geometry at all.

One problem, just out of no where, with creating the vertices on the fly, is I want a copy for physics calculations. But maybe I should just create a seperate tree entirely for that with a lower threshold that just doesnt ever create the ID3DXMesh structure.

I also think your above Index creation loop may be wrong, but I tried it my way and your way and got no results.

My way:

	indexBuffer[baseIndex] = i * XWidth + j;				indexBuffer[baseIndex + 1] = i * XWidth + j + 1;				indexBuffer[baseIndex + 2] = (i + 1) * XWidth + j;				indexBuffer[baseIndex + 3] = (i + 1) *XWidth + j;				indexBuffer[baseIndex + 4] = i * XWidth + j + 1;				indexBuffer[baseIndex + 5] = (i + 1) * XWidth + j + 1;

TheAdmiral

1,122

August 26, 2006 08:13 PM

Our index orderings are more or less the same. You are just using your i & j the other way around (probably thrashing your CPU cache at the same time) and permuting the vertices in the triangles. Something to note is that your method creates the triangles with clockwise winding (viewed from above) whereas mine runs anticlockwise. If you are using backface culling, this is significant.

As for the invisibleness, have you checked all the usual problem areas? Clear the screen to a medium grey, Turn off lighting, culling (backface and quadtree) and disable alpha blending and the z-buffer. If you still get no results, trace through the routine that creates the geometry patches, paying particular attention to the lock and unlock calls. If they fail, you will get entirely unpredictable results. If you're still at a loss, turn your API debugging level up to the max and check the return value of each and every function call that has anything to do with your rendering.

Failing that, if you have a FPS counter, you can try rendeing the geometry several (say 100) times per frame and see if your framerate changes significantly. If so, vertices are being processed (at a minimum). If the framerate changes as you move your camera, some fillrate is being consumed (in which case you should have a look at your alpha settings).

Hopefully something here will help you solve the problem.

Regards
Admiral

Ring3 Circus - Diary of a programmer, journal of a hacker.

ChaosPhoenix

242

Author

August 26, 2006 08:24 PM

I'll try those things. I already have commands to turn off and on culling, lighting is disabled by default. I have a normal ID3DXMesh cube that I draw and it shows up fine, the landscape showed up fine before putting into the QuadTree so I know the heightmap is fine. Its gotta either be something with my actual mesh creation, or a setting like you suggested.

While I test out these other methods, do you see anything in the way I create my mesh that just stands out wrong? (The code source above should have my mesh creation code, it hasn't changed much. I'll edit this with the actual code in a second when I can get to my coding PC).

EDIT:

void CQuadTree::CreateRenderMesh(){		int triangleCount = NumTrianglesInRange();		// Begin Creating the actual Mesh.*/		CHeightMap::terrainVertex* vertex;		D3DXCreateMeshFVF((triangleCount * 2),(triangleCount *3), D3DXMESH_MANAGED, D3DFVF_XYZ |D3DFVF_TEX1, CRenderer::GetInstance()->GetDevice(), &m_pMesh);				m_pMesh->LockVertexBuffer(0, (void**)&vertex);		int vertexIndex = 0;				int i = 0;		for(int z = m_iMinZ; z <= m_iMaxZ; z += CHeightMap::GetInstance()->GetSpacing())		{			int j = 0;			for(int x = m_iMinX; x <= m_iMaxX; x += CHeightMap::GetInstance()->GetSpacing())			{				int index = i * CHeightMap::GetInstance()->GetHeightMapWidth() + j;				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);				j++;			}			i++;		}		m_pMesh->UnlockVertexBuffer();		WORD* indexBuffer = 0;		m_pMesh->LockIndexBuffer(0, (void**)&indexBuffer);		int baseIndex = 0;		int XWidth = m_iMaxX - m_iMinX /  CHeightMap::GetInstance()->GetSpacing();		int ZWidth = m_iMaxZ - m_iMaxZ /  CHeightMap::GetInstance()->GetSpacing();		for(int i = 0; i < ZWidth - 1; i++)		{			for(int j = 0; j < XWidth - 1; j++)			{				/*indexBuffer[baseIndex] = i * XWidth + j;				indexBuffer[baseIndex + 1] = i * XWidth + j + 1;				indexBuffer[baseIndex + 2] = (i + 1) * XWidth + j;				indexBuffer[baseIndex + 3] = (i + 1) *XWidth + j;				indexBuffer[baseIndex + 4] = i * XWidth + j + 1;				indexBuffer[baseIndex + 5] = (i + 1) * XWidth + j + 1;*/				  indexBuffer[baseIndex] = (float) (i+1) * XWidth + (j+0);				  indexBuffer[baseIndex + 1] = (float) (i+0) * XWidth + (j+1);				  indexBuffer[baseIndex + 2] = (float) (i+0) * XWidth + (j+0);				// Lower-right triangle				 indexBuffer[baseIndex + 3] = (float) (i+1) * XWidth + (j+1);				 indexBuffer[baseIndex + 4] = (float) (i+0) * XWidth + (j+1);				 indexBuffer[baseIndex + 5] = (float) (i+1) * XWidth + (j+0);								baseIndex += 6;						}		}		m_pMesh->UnlockIndexBuffer();		DWORD* attributeBuffer = 0;		m_pMesh->LockAttributeBuffer(0, &attributeBuffer);		for(int i = 0; i < triangleCount; i++)		{			attributeBuffer = 0;		}		m_pMesh->UnlockAttributeBuffer();		std::vector<DWORD> adjacencyBuffer(m_pMesh->GetNumFaces() * 3);		m_pMesh->GenerateAdjacency(0.001f, &adjacencyBuffer[0]);		m_pMesh->OptimizeInplace(D3DXMESHOPT_IGNOREVERTS,									&adjacencyBuffer[0], NULL, NULL, NULL);					}

ChaosPhoenix

242

Author

August 27, 2006 12:00 PM

So, I put in FAILED macros on all my ID3DXMesh functions, DrawSubset calls, and anything else D3D related. Nothing is failing. My framerate is constant with or without trying to force the QuadTree to render all nodes, so obviously nothing is being drawn.

Really stuck here.

TheAdmiral

1,122

August 27, 2006 02:25 PM

The routine looks fine, but it uses a lot of functions that mean nothing to us. Have you tried tracing through the for loops to ensure that the first iterations on each variable are creating the correct coordinates? Only you are in the position to do this as we can't verify the results of your GetHeightMapWidth, GetSpacing etc.

Just before your unlock calls, take a look at the memory dumps of the buffers you locked with. Check over each component, with your vertex struct at hand to be absolutely sure that the vertex & index data is spot on. If it is, then the problem must lie in the rendering process.

You have probably already done this, but of course you should comment out the vertex buffer optimisation calls while you're debugging. Also, I trust that you are also doing the Rendering fine, but you haven't showed us that function yet (DrawSubset(0), right?).

If you are still stumped, it may be worth throwing together a very basic vertex shader, simply so you can debug the vertex processing pipeline. If your vertex data is not getting to the card or is somehow getting corrupted, it will be apparent from inside your vertex shader routine.

Regards
Admiral

Ring3 Circus - Diary of a programmer, journal of a hacker.

ChaosPhoenix

242

Author

August 28, 2006 08:45 AM

I tried a few things and still am having a hard time figuring out the issue.

I went ahead and just RAR'd everything(its a very very small project, just a basic D3D window, camera, and currently 1 D3DXMesh cube being rendered), so if anyone has time to just glance over it, that would be amazing.

URL:
http://www.animehack.com/demos/Terrain%20Generator.rar (15Kb)

I'm going to continue playing with things and seeing what I find.

EDIT: Quick camera / debug control overview

W - Forward
S - Backwards
A - Left
D - Right
R - Up
F - Down
Q - Rotate CCW
E - Rotate CW

Mouse = Mouse look

F1 - Wireframe
F2 - Force all Quadtree nodes to render
F3 - Disable CCW Culling
F4 - Enable CCW Culling
F5 - QuadTree render based on Camera Position

Esc - Quit

Creating a Quadtree with a Height-map generated Terrain.

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Creating a Quadtree with a Height-map generated Terrain.

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines