• Advertisement
Sign in to follow this  

Quad Tree - Each node contain its vertices?

This topic is 4644 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

I am busy working my old quad tree class into Dx9 with just a few minor mods. I was just curious if the following is still good: -Recursively split a heightmap into nodes/leaves. -Each leaf contains vertices and indices. -Cull out nodes and add any leaves vertices and indices to a buffer -Render the buffer ...After writing this I think I will have a indice matching vertice problem here. I am goona have to use a seperate buffer for each leaf or somehow manually rebuild the indices each frame...Unless I can have the tree add the vertices/indices to the buffer appropriately in order.

Share this post


Link to post
Share on other sites
Advertisement
I think you should store all the vertices in a large vertex buffer. The quadtree nodes just contain indices. Each frame you fill a dynamic index buffer with the indices and render it.

Share this post


Link to post
Share on other sites
But wouldn't it be faster to walk the list of visible nodes and invoke DrawIndexedPrimitive for each node? I'm curious. Which method is faster?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Test it.

Share this post


Link to post
Share on other sites
I use one large vertex buffer and one index buffer for every node in my tree.
I tried out both methods, and unless I´ve done something terrible wrong it was faster to DrawIndexedPrimitive() every node that was visible. But I also did check for the largest nodes I should render (if every child of a node is visible, render the parent node and so on).
When I build an index buffer every frame containing all the indices every frame it was significantly slower, but as I said: Perhaps I did something terribly wrong.

Share this post


Link to post
Share on other sites
First of all my first method or working this out was to render each node with a seperate call to DrawIndexedPrimitive.

I would run a frustum check and render only the nodes within the frustum.


Now I cannot proove this for sure but everything including many MSDN documents has led me to believe that filling one large buffer is the way to go.

-First of all, less calls to DrawPrimitive is an incredible boost.
-Using one big buffer will allow the GPU to be in use once for the whole terrain instead of at random occasions for each node.


So, each frame the nodes are culled, any un-culled node will add its vertices to the large buffer. The large buffer will be sized to assume it will contain every possible triangle in the terrain (up to the max # of primitives). This way, each frame, a buffer can be updated, then locked and filled into the vertex buffer. Using a dynamic buffer locked with discard everything seems to happen very fast.




Edit:
- Another proof, my first particle system would check if a particle was active then render it. My new one just renders the whole batch in one call and any inactive particle is size 0 so it is invisible. The new method was so fast at even rendering 1000 particles that only 0.5ms per frame was taken instead of about 2-3ms per frame. Clearly it is better to use less calls.
My only big concern now is that I believe I will have update the indices each frame for two reasons:
- The indices will not point correctly to the vertices once they are in the big buffer
- I cannot remeber how triangleList indices work, can I indice triangles all over the place (ABC JKL MNO) or does it have to follow order like the triangleStrips (ABCDEFGH).

[Edited by - Halsafar on June 1, 2005 7:26:52 PM]

Share this post


Link to post
Share on other sites
Triangle Lists:
Yes, you can index the triangles in any order you want when using a triangle list, since any group of three indices is used as a triangle.
{1,2,3, 5,8,9}
would make two triangles, one consisting of points 1,2 and 3, and the other consisting of 5,8 and 9.

One big buffer vs distinct buffers for nodes:
hmm.... I´ll have to try that out then. On the other hand I don´t have more than 20 draw calls for a 513x513 terrain. And: a buffer lock is terribly slow, too.
Anyways I´ll give it a shot, perhaps it rocks :)

Share this post


Link to post
Share on other sites
I am using a large heightmap which could total more triangles than my card can support primitives/indices.

Since I am culling againt the frustrum really only something like 3000 vertices are being dealt with a frame.

During the recursive quad tree cull routine anytime a leaf is found and is in the frustum it adds its vertices to a buffer. That buffer is then added with a quick lock to the vertex buffer.

Now, thanks to your point that I can indice however I want, I am going to build the indices once, since no matter how the vertices are added, the indices should ALWAYS be the same.


I spent 5 brain bending, mind exploding, eye shattering hours attempting to work out what I have explained and ooooh boy I just wasn't having a good day I guess. Error's error's error's, and then more error's, and then error's that didn't make sense.

Just curious, each frame I need to determine the number of primitives I am rendering for the call to DIP(......primitive count)
With triangle_list is that simply (numIndices / 3)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement