Note: This is an early screenshot which goes a few levels deeper. It's based on an 256x256 heightmap. (I'm not sure where I got the original terrain example from)
I think the best solution for the quadtree is:
- One big vertex buffer with the entire terrain
- Tree leafs contain an array of indices, which I can copy together in one "frustum only" index buffer.
- Based on that, I think the indices need somehow be formed in rectangles (about 25x25 triangles in width), instead of strip based.
- There are, right now, 16 leafs in the entire map.
If anyone is interested in seeing this visualized, Wireframe:
gamedata.zip(390kb)
As you can see, I've got the basics working, but the indexbuffer is really a problem for me :).
Two other small questions:
1) How is it called if vertices, are being merged, since they are the same around each other? This could optimize my terrain. But searching on "combine, merge, simplify" etc, didn't really help me yet.
2) Why would the release version of the exe crash, and the debug version doesn't? :) (new to VC++ :P)
Anyone that can shed some light on the indexbuffers? It would wonderfull :)
Regards,
ajoling
Edit: Forgot to say the mouse only works outside the window with the demo, since it isn't an exclusive device.
QuadTrees and indices?
Author
Hi everyone,
Recently I decided to start with (V)C++, after working in quite some other languages for years.
Right now I'm working on the terrain rendering part.
Things are going quite well. I've done a LOT of research the last days. About ROAM, CLOD, LOD, Space partitioning, etc. Math isn't my strongest point, so I needed a lot of info :).
Already got 24 terrain/QuadTree's samples gathered around. I've read every documentation, I could find.
I got my quadtrees working, and the frustum culling checks works nice too. BUT! The index buffer is giving me a really hard time, unfortunatly. I simply don't get how it works in theory (I could write the code for locking memcpy, etc)
So, maybe someone can help me a bit on the way, how I should make my index buffer for the terrain.
My terrain is -1020 to 1020, with a gridsize of 20. (102*20 = 2040/2 = 1020).
The terrain is simply a trianglelist, Row/Column.
My quadtree is -1024 to 1024, It goes down to squares of 256x256, like shown below:
Note: This is an early screenshot which goes a few levels deeper. It's based on an 256x256 heightmap. (I'm not sure where I got the original terrain example from)
I think the best solution for the quadtree is:
- One big vertex buffer with the entire terrain
- Tree leafs contain an array of indices, which I can copy together in one "frustum only" index buffer.
- Based on that, I think the indices need somehow be formed in rectangles (about 25x25 triangles in width), instead of strip based.
- There are, right now, 16 leafs in the entire map.
If anyone is interested in seeing this visualized, Wireframe:
gamedata.zip(390kb)
As you can see, I've got the basics working, but the indexbuffer is really a problem for me :).
Two other small questions:
1) How is it called if vertices, are being merged, since they are the same around each other? This could optimize my terrain. But searching on "combine, merge, simplify" etc, didn't really help me yet.
2) Why would the release version of the exe crash, and the debug version doesn't? :) (new to VC++ :P)
Anyone that can shed some light on the indexbuffers? It would wonderfull :)
Regards,
ajoling
Edit: Forgot to say the mouse only works outside the window with the demo, since it isn't an exclusive device.
Note: This is an early screenshot which goes a few levels deeper. It's based on an 256x256 heightmap. (I'm not sure where I got the original terrain example from)
I think the best solution for the quadtree is:
- One big vertex buffer with the entire terrain
- Tree leafs contain an array of indices, which I can copy together in one "frustum only" index buffer.
- Based on that, I think the indices need somehow be formed in rectangles (about 25x25 triangles in width), instead of strip based.
- There are, right now, 16 leafs in the entire map.
If anyone is interested in seeing this visualized, Wireframe:
gamedata.zip(390kb)
As you can see, I've got the basics working, but the indexbuffer is really a problem for me :).
Two other small questions:
1) How is it called if vertices, are being merged, since they are the same around each other? This could optimize my terrain. But searching on "combine, merge, simplify" etc, didn't really help me yet.
2) Why would the release version of the exe crash, and the debug version doesn't? :) (new to VC++ :P)
Anyone that can shed some light on the indexbuffers? It would wonderfull :)
Regards,
ajoling
Edit: Forgot to say the mouse only works outside the window with the demo, since it isn't an exclusive device.
greetz, index buffers are used by DirectX to figure out which vertices to render. This way, you can have one big vertex buffer and simply indicate to dx which vertices you wish to render via the index buffer. So if your buffer is {0,1,2,3,4,5,6,...}. so in your quadtree you just say from one quatant- render 0-3. in the next quatant you say, render {4-7}. so what ya can do is put all these indicies in one huge index buffer. so then when ya do a DrawIndexedPrimitive you render out all the indicies for that quatant. Get it?
below is a code example i use in my octree:
m_pd3dDevice->DrawIndexedPrimitive(D3DPT_TRIANGLELIST,0, s.m_nMinIndex, s.m_nVertices,s.m_nIndexStart,s.m_nPrimitives);
what i do when a mesh is added to my octree is rearrange the vertices and indicies into sequential order so i can use the above method. seems to work extremely well on radeon cards,etc.
below is a code example i use in my octree:
m_pd3dDevice->DrawIndexedPrimitive(D3DPT_TRIANGLELIST,0, s.m_nMinIndex, s.m_nVertices,s.m_nIndexStart,s.m_nPrimitives);
what i do when a mesh is added to my octree is rearrange the vertices and indicies into sequential order so i can use the above method. seems to work extremely well on radeon cards,etc.
Author
Hi,
Yeah, That's about exactly the same as I wanted to do it. :).
With sequential order, do you mean just large strips of vertices.. or have them "in squares" for each quad?
One other question for that DrawIndexedPrimitive, the vertices count.. is that the count of the entire vertexbuffer, or just the count from the indices/quadtree quad?
-ajoling
Yeah, That's about exactly the same as I wanted to do it. :).
With sequential order, do you mean just large strips of vertices.. or have them "in squares" for each quad?
One other question for that DrawIndexedPrimitive, the vertices count.. is that the count of the entire vertexbuffer, or just the count from the indices/quadtree quad?
-ajoling
Yes that is exactly what I meant. Since you are using a 2D partitioning tree, your mesh will get divided into perfect little squares. An optimial quadtree might only store it's on bound as a rectangle and the range of vertices it stores. Let's say your mesh has 20,000 vertices and the original index buffer counts from 0-20,000. In my partitioning tree, I rearrange the vertex/index buffers so that I can use the same vertex/index buffer for the entire thing. So quatant 1 may index into 0-5000. quatant 2 might have 5000-10000. quatant 3 might have 10,000-15,000. and finally the last quatant contains 15,000-20,000.
So now during rendering- if quatant 1 is within frustum it tells DrawIndexPrimitive that his min vertex is 0. His total # of primitives is 5000/3, etc.
There is a moderator, Yann L, that has made some excellent posts about something he calls sliding slots. Once you start messing around with huge terrains you might want to search these forums for posts on that. I haven't used it myself yet but it sounds like a good technique.
So now during rendering- if quatant 1 is within frustum it tells DrawIndexPrimitive that his min vertex is 0. His total # of primitives is 5000/3, etc.
There is a moderator, Yann L, that has made some excellent posts about something he calls sliding slots. Once you start messing around with huge terrains you might want to search these forums for posts on that. I haven't used it myself yet but it sounds like a good technique.
Author
Hm, I've been toyin around with indexbuffers all morning, and came indeed t othe conclusion that I need to rearrange my vertices somehow. When I tried rendering the first 25x25 row/cols, it rendered the entire strip in width, and a bit in depth too.
Hm, I dislike working directly with vertices the most. But, I will give it a try ofcourse :).
I also found out how it's called if you combine vertices together, I believe it's called "welding"...
Hm, I dislike working directly with vertices the most. But, I will give it a try ofcourse :).
I also found out how it's called if you combine vertices together, I believe it's called "welding"...
In my octree I didn't actually alter the vertex buffer at all. What i did was rearrange the index buffer so the card can keep the same index buffer in video memory. So if vertices 34-56 fit within a quatant, i basically rearranged the indicies during the construction phase so those indicies can be directly drawn by the quatant when visible. so don't worry bout welding or tearing apart the mesh. all you're really doing is telling directx the best way to display your mesh.
Author
I tried that, but somehow, I just couldn't get it to work.
This is how I make my indices for the entire terrain. You see, it goes from Top, bottom, from left to right.
Now, I tried changing this to index the first quad, which is from 0,0 - 25,25. unfortunatly, It would still render long strips, instead of a quadrant :-(.
I've tried a LOT. I also tried collecting all the indexes ONLY between the specified X,Y coords (bit messy, but it was just another attempt):
which resulted in the same problem :). It gives like the first 4000 indices - without any stop. Which is hard to believe, since it should return something like:
***---------
***---------
***---------
Instead of
************
****--------
------------
(What it's doing now)
This is how I make my indices for the entire terrain. You see, it goes from Top, bottom, from left to right.
Now, I tried changing this to index the first quad, which is from 0,0 - 25,25. unfortunatly, It would still render long strips, instead of a quadrant :-(.
WORD n = 0, y = 0; for (y = 0; y < m_wRows; y++) { for (x = 0; x < m_wCols; x++) { int startvert = ((y*m_wCols) + x); pIndices[n++] = startvert+m_wCols; // triangle 1 pIndices[n++] = startvert; pIndices[n++] = startvert+m_wCols+1; pIndices[n++] = startvert+1; // triangle 2 pIndices[n++] = startvert+m_wCols+1; pIndices[n++] = startvert; } }I've tried a LOT. I also tried collecting all the indexes ONLY between the specified X,Y coords (bit messy, but it was just another attempt):
//////Note down our needed vertices: //if (y >=0 && y < 25) { // if (x >= 0 && x < 25) { // j=n; // // //Add N to our array. //// for (j = (n-6); j < n+1;j++) { //// pLeafIndices[indexcount++] = startvert+m_wCols; // triangle 1 //// pLeafIndices[indexcount++] = startvert; //// pLeafIndices[indexcount++] = startvert+m_wCols+1; //// pLeafIndices[indexcount++] = startvert+1; // triangle 2 //// pLeafIndices[indexcount++] = startvert+m_wCols+1; //// pLeafIndices[indexcount++] = startvert; //// } //// // } //}which resulted in the same problem :). It gives like the first 4000 indices - without any stop. Which is hard to believe, since it should return something like:
***---------
***---------
***---------
Instead of
************
****--------
------------
(What it's doing now)
Hya there,
I think what some other people have mentioned is that you create a sequential TRIANGLE_LIST index buffer. By sequential I mean one index buffer where no parts of the terrain are repeated but a quad tree's indices are next to each other. Check this out
-----------------
| 1 | 2 | 5 | 6 |
-----------------
| 3 | 4 | 7 | 8 |
----------------- Level 3 of the quadtree (l1 = 1, l2 =
| 9 | 10|13 |15 | 4, l3 = 16
-----------------
|11 | 12|14 |16 |
-----------------
In the above diagram the terrain is split up in to 16 leaf's (or leaves) (1 to 16). Now it's all in how you put these in to an index buffer.
The best index buffer would look like this
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
And you'd replace each number (1 to 16 indicating the leaf) with the indices for the leaf.
What this means that all of the indices for leaf 1 are together and leaf 2 are together etc. But this also means that further up the tree the indices are together.
Check this out
---------
| 1 | 2 |
---------
| 3 | 4 |
---------
The above diagram is level 2 of the quadtree. In the picture 1 has the indices of leaf 1, leaf 2, leaf 3 and leaf 4. Quad 2 has the indices of leaf 5, leaf 6, leaf 7 and leaf 8. (Remember that at level 2 there aren't any leaves).
What this means is that Even at level 2 the indices are still grouped togeter so to render quad 1 of level 2 youd simply render leaves 1 - 4 which is one continuous piece of the index buffer.
This can be done for as many quad levels as you like.
To do this simply build your quadtree and assign indices to the leaves then recurse the quadtree and every time you get to a leaf add the indices to the index buffer.
However, if your interested, I'm not sure that this method of rendering is too great. If you've got really big terrain then your going to have one really big vertex buffer and one really big index buffer which isn't great.
At the moment I've split my indices and vertices between the quads so that each quadtree leaf has it's own vertex and index buffer. I'm then planning to use dynamic buffers to render only what is in the view frustum.
I hope some of that helps you out.
Matt
I think what some other people have mentioned is that you create a sequential TRIANGLE_LIST index buffer. By sequential I mean one index buffer where no parts of the terrain are repeated but a quad tree's indices are next to each other. Check this out
-----------------
| 1 | 2 | 5 | 6 |
-----------------
| 3 | 4 | 7 | 8 |
----------------- Level 3 of the quadtree (l1 = 1, l2 =
| 9 | 10|13 |15 | 4, l3 = 16
-----------------
|11 | 12|14 |16 |
-----------------
In the above diagram the terrain is split up in to 16 leaf's (or leaves) (1 to 16). Now it's all in how you put these in to an index buffer.
The best index buffer would look like this
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
And you'd replace each number (1 to 16 indicating the leaf) with the indices for the leaf.
What this means that all of the indices for leaf 1 are together and leaf 2 are together etc. But this also means that further up the tree the indices are together.
Check this out
---------
| 1 | 2 |
---------
| 3 | 4 |
---------
The above diagram is level 2 of the quadtree. In the picture 1 has the indices of leaf 1, leaf 2, leaf 3 and leaf 4. Quad 2 has the indices of leaf 5, leaf 6, leaf 7 and leaf 8. (Remember that at level 2 there aren't any leaves).
What this means is that Even at level 2 the indices are still grouped togeter so to render quad 1 of level 2 youd simply render leaves 1 - 4 which is one continuous piece of the index buffer.
This can be done for as many quad levels as you like.
To do this simply build your quadtree and assign indices to the leaves then recurse the quadtree and every time you get to a leaf add the indices to the index buffer.
However, if your interested, I'm not sure that this method of rendering is too great. If you've got really big terrain then your going to have one really big vertex buffer and one really big index buffer which isn't great.
At the moment I've split my indices and vertices between the quads so that each quadtree leaf has it's own vertex and index buffer. I'm then planning to use dynamic buffers to render only what is in the view frustum.
I hope some of that helps you out.
Matt
Author
Well, that's what I'm trying to do. :) My terrain is as sequential as you showed:
Row {
Col {
}
}
Generating the index buffer is my problem. I got something which already starts to look like something...
Like you showed, I'm trying to get 1,2,3,4 for my first quad. (which is 0,0 to 25,25.. my terrain is 100x100 / 4x4 = 25 per square.)
Right now I have:
I'll fiddle around a bit more.. :)
Row {
Col {
}
}
Generating the index buffer is my problem. I got something which already starts to look like something...
Like you showed, I'm trying to get 1,2,3,4 for my first quad. (which is 0,0 to 25,25.. my terrain is 100x100 / 4x4 = 25 per square.)
Right now I have:
[source language="cpp"] WORD n = 0, y = 0, x = 0; WORD EndRows = (m_wRows / 4); WORD EndCols = (m_wCols / 4); for (y = 0; y < m_wRows; y++) { for (x = 0; x < m_wCols; x++) { if (y < EndRows +1 && x < EndCols+1) { int startvert = ((y*m_wCols) + x); pIndices[n++] = startvert+m_wCols; // triangle 1 pIndices[n++] = startvert; pIndices[n++] = startvert+m_wCols+1; pIndices[n++] = startvert+1; // triangle 2 pIndices[n++] = startvert+m_wCols+1; pIndices[n++] = startvert; } } }I'll fiddle around a bit more.. :)
Author
Humm. I thought this function would put everything in the right order:
But the same thing happens as the screenshot above :(. I'm clueless :).
//Loop through all indices WORD rowcount = 0, colcount = 0; WORD a = 0, b = 0, c = 0; for (y =0; y < EndRows; y++) { a = (IndicesPerRow * y); b = a + IndicesPerColQuad; for (x = a; x < b; x++){ pIndices[c++] = pIndices[x]; } }But the same thing happens as the screenshot above :(. I'm clueless :).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
