• ### Popular Now

• 15
• 15
• 11
• 9
• 10

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

## Recommended Posts

Hi, I think I’m beginning to confuse myself and was wondering if anyone could help clarify the situation for me. Currently my code works fine for rendering a small terrain. The position of each vertex is calculated and then stored in an array and then this is copied into a vertex buffer. Like wise I calculate the correct order of the indices and then copy them into an array which is copied into an index buffer. Fore example
	//deal with the vertices
cVBManager::GetInstance()->CreateBuffer(miNumVertices* sizeof(TerVertex),TerVertex::FVF);

TerVertex* TerVertices = new TerVertex[miNumVertices];

for(int j = 0; j <miNumVerticesColumn; ++j)
{
for(int i = 0; i <miNumVerticesRow; ++i)
{
// compute the correct index.
int index =  j * miNumVerticesRow + i;
TerVertices[index] = TerVertex(i*miCellSize,
vHeightmap[index],
j*miCellSize);
}
}

float fSizeOfTerVertices = sizeof(TerVertex)*miNumVertices;


and

cIBManager::GetInstance()->CreateBuffer(3*miNumTriangles*sizeof(WORD));

//work out the indicies

WORD* Indices = new WORD [3*miNumTriangles];

int Index = 0;

for(int i = 0; i < miNumCellsColumn; i++)
{
for(int j = 0; j < miNumCellsRow; j++)
{
Indices[Index]     =	 i   * miNumVerticesRow + j;
Indices[Index + 1] =	(i+1) * miNumVerticesRow + j;
Indices[Index + 2] =	(i+1) * miNumVerticesRow + j + 1;

Indices[Index + 3] =	i   * miNumVerticesRow + j;
Indices[Index + 4] =	(i+1) * miNumVerticesRow + j + 1;
Indices[Index + 5] =	i   * miNumVerticesRow + j + 1;

Index += 6;
}
}

float fSizeOfIndices = sizeof(WORD)*3*miNumTriangles;


The AddToBuffer copies the memory into a dynamic vertex/index buffer, which will be filled and then, once full, rendered etc. Now what i want to do is split my terrain using a quad tree. At each node i want to store an array contain the vertices and an array contain the indicies. When a node is included i will simply add this to a larger array and then add this to the buffer once (only one lock/unlock). However, i am getting confused as to the best way to keep my index of the correct values, as this will need to be based on the number of vertices already stored and, i believe, there will need to be some overlap with the ones already in there. Does this make sense and if so can someone suggest some guidance or, possibly, a better way of doing it? Thanks, Matt

##### Share on other sites
What you're really asking here is info on how to implement a quad tree. There are a number of articles here on GameDev and on the internet in general that talk about this.

You seem to have a good grasp about how to fill vertex/index buffers with dynamic data so your question seems more related to algorithms than to DirectX in particular.

As a suggestion, the nodes in your quadtree could store only indices. You could have all your vertices in one buffer and just use the index buffer to origanize the specific triangles you'll be rendering.

Do a search here on GameDev for quadtrees and you'll come up with lots of good information.

neneboricua

##### Share on other sites
I understand quadtrees and know how to implement it. It is actually my understanding of implementing the dynamic buffer that is getting me confused.

If all the vertices are inlcuded it is trivial to work out the indicies and get them in the correct winding order. However, when i may have an arbitary number of vertices included, depending on what sections of the quadtree are visible, i am geting confused as to how to index them and really need someone to explain it so i can get it clear in my head!

Thanks,

Matt

##### Share on other sites
Ok. I'm not sure what you meant in your origianl message about there possibly being some kind of overlap in vertices or indices while traversing your quadtree. Could this possibly refer to having a triangle on a boundary of the quadtree? Most quadtree algorithms will duplicate this triangle in both nodes of the quadtree boundary.

In any case, there are a couple of ways to do what you're asking; it all depends on how you implemented your quadtree.

Option 1.
This is the one I think you're currently doing. If you directly store both the vertices and indices of an object in a tree node and the indices are specified in a way that they are local to this node, then when you traverse your quadtree, you'll need to keep track of how many vertices are currently in your vertex buffer.

Let me try to explain a bit more. Say you traverse your quadtree and find that you need to render nodes 0, 4, and 5.

Node 0 contains: verts={ ... } indices{ 0, 2, 4, 3, 4, 5, 5, 7, 6, .... }
Node 4 contains: verts={ ... } indices{ 2, 4, 3, 6, 4, 7, 8, 9, 7, .... }
Node 5 contains: verts={ ... } indices{ 5, 4, 2, 8, 7, 5, 9, 4, 6, .... }

In other words, the indices in each node correspond to the vertices stored in this node.

If you were to simply dump the indices of each node into an index buffer, then you would be refering to incorrect vertices because the vertices in your dynamic vertex buffer are no longer in the same location as they were in the nodes of your quadtree.

To fix this, you would need to keep track of how many vertices are in your vertex buffer as you traverse your quadtree. So say you add Node 0 to your dynamic vertex and index buffers. Everything is fine so far. When you add Node 4 to the same dynamic vertex and index buffers, you need to take into account that the vertices from Node 4 are no longer in the same locations once you copy them to your dynamic vertex buffer. So you would need to offset the indices from Node 4 by the number of vertices currently in your dynamic vertex buffer.
// Copy indices to dynamic index buffer.for( int i = 0; i < Node4.numIndices; i++ ){    dynamicIndexBuffer[TotalNumIndices-1+i] = Node4.indexBuffer + numVertsInDynamicVertexBuffer;}TotalNumIndices+=Node4.numIndices;// Copy vertices to dynamic vertex buffer.for( int i = 0; i < Node4.numVertices; i++ ){    dynamicVertexBuffer[TotalNumVertices-1+i = Node4.vertexBuffer;}TotaNumVertices+=Node4.numVertices;

You could easily put this code in a loop to traverse your quadtree and build your dynamic vertex and index buffers.

Option 2.

Its up to you how you want to do it. I hope I've understood your question correctly and that this helps you out.

neneboricua

##### Share on other sites
You understood it better tahn i could explain it. This is great, thanks. It was one of those things where the more i considered it the more i confused myself and i really needed to take a step backand have someone explain it. I was actaully making it more complicated than it needed to be; I was atempting to work out a way of calculating the entire index buffer at once - I didn;t think of simply storing it local to each leaf of the tree and then simply adding the offset...oops :)

I was orginally going to go with 1 as my terrain will be height editable (you can change the y component, but not the x and z so the quad tree will be instact). However, i am now drawn towards 2 and using a vertex shader to address the height as i can keep the vertex buffer static. All these decisions... :)

Once again,thanks,

Matt

[Edited by - mattm on February 11, 2005 6:51:07 AM]