Archived

This topic is now archived and is closed to further replies.

Why do you need Quadtrees, Octrees etc?

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

Yes it does. But if you give ogl or d3d every poly in your level it will take it ages for it to sort it all out. Using a quadtree, octree whatever you can quickly work out what polygons the player will see(and some just out of view) pass them to ogl and d3d and all the sorting and clipping stuff is done much quicker.

Also think of collision detection. Say your using sphere to polugon collision to test your player against the level. w/o a quadtreee,octree etc you have to test that sphere against every polygon in the level every frame! With quadtree,octree etc you can quickly work out which polygons the sphere could be intersecting then check with those.

[edited by - Monder on July 25, 2002 7:47:54 AM]

Share this post


Link to post
Share on other sites
why do you have a binary tree of your 4billion values?
you can find every item by going through the 4 billion values, wheres the problem? the binary tree only helps you that you find your value with AT MAX 32 iterations. but thats not much less than 4billion iterations at max..

structured data can reduce the amount of data that neads to be read, processed, changed, send, what ever. thats what a quadtree is for. or an octree, or a bsp, or what ever sort of trees. they are for sorting, changing an O(n) algo to O(lg2(N)) or at best O(1). from 4billion triangles you have to check against the frustum to 32cubes you have to check against the frustum..

its only useful where speed is needed, realtime applications that dont have the time of several month to calculate one frame..

"take a look around" - limp bizkit
www.google.com

Share this post


Link to post
Share on other sites
It's not just speed issues. An Octree/Quadtree can help you to organize your scene (it functions as a sort of scene graph).

You can use it to sort your scene as well, which helps with Transparent objects (if you don't know why, do a search).

Collision detection is nice too but frustum culling achieves much the same results (check out my site for a tutorial on Octree Collision Detection though).

And the main reason I use them, it allows you, the user, to decide what triangles should be sent to the video card to be prcoessed. See, even if the video card does the clipping on the poly's anyways, you're still sending it the polys and it still has to evaluate them and decide they don't need to be drawn. you help the video card by telling it only to draw what you are positive it needs to draw. Then it still does it's clipping, but it doesn't waste that many resources on it. NOTE: This suggests a clip test is expensive. I believe it is not, but with a large scene the overhead can drown the card.

"Love all, trust a few. Do wrong to none." - Shakespeare

Dirge - Aurelio Reis
www.CodeFortress.com
Current Causes:
Nissan sues Nissan

[edited by - Dirge on July 25, 2002 12:21:36 AM]

[edited by - Dirge on July 25, 2002 12:22:22 AM]

Share this post


Link to post
Share on other sites
You''re missing the point. We''re not clipping every vertex, thats done automatically on hardware (it''s called z occlusion clipping (or z-clipping) or frustum clipping). Of course hardware clipping is faster than software. It would be near impossible to do software clipping even on modern cpu''s actually. What you should do (with a spatial subdividing system) is to help the video card by not sending a group of vertices/faces for z-clipping tests. You are culling away parts of the scene.

Simple (heh) tests on the cpu help save the video card (our savior) lots of stupid tests, which gives us overall better performance. It''s proven. You don''t believe it, play Unreal Tournement or Quake 3. If you have the source, see if you can remove the bsp frustum culling out.

Summery: Nothing on software will ever beat something done in hardware (performance wise), but you can ease the burden on hardware (which can still become overburdened) by using the cpu to create "filters".

"Love all, trust a few. Do wrong to none." - Shakespeare

Dirge - Aurelio Reis
www.CodeFortress.com
Current Causes:
Nissan sues Nissan

Share this post


Link to post
Share on other sites
"The fastest polygons are those that never get sent to the card. The second fastest are those that are never drawn."

See, the idea is that you''re culling masses of polygons at once: you just check four (!) vertices for visibility, and if they''re not visible, you can cull all triangles in between. That''s the beauty of it, and it''s a concept you should get used to anyway when doing realtime stuff: grouping data to minimize processing. You''ll probably (have to) do it with a lot of things in whatever game you are making.


- hillip@xenoage.de''>JQ
Full Speed Games. Period.

Share this post


Link to post
Share on other sites
You''ve all come close, but not hit the mark.

The main reason you get a speed benefit by NOT sending stuff to the video card is because the memory interface of the video card is a bottleneck. You can only send so much data to the card, and usually this is less data than the card''s chipset can handle. So, by reducing the amount of data you''re sending, you are clearing a lot of space on the memory interface. You don''t win on the actual processing of the vertices, as much as winning on not hogging the memory interface with stuff that won''t get drawn. Per unit time, you''ll be able to send more stuff that WILL in fact get into the rasteriser, which will increase your framerate.

That''s also one of the reasons that hardware LOD stuff can be useful - making more geometry out of less, but AFTER you''ve managed to cross the memory interface. Another indication that current video cards can actually draw stuff quicker than they can be sent stuff.

Share this post


Link to post
Share on other sites
Using Tree structure is like when we, human, search in a phone directory. I'm positively sure you won't start at the first page, reading every single name on every single page until you get the guy you seek for.

No, you first try to locate the right letter by spliting the directory at about the right place (you know A is at the beggining, M at middle and Z at end). Then you find the second letter with the same process until you get pages, columns, and names, it will take at most 2 minutes instead of a complete week.

Octrees do the exact same thing but with 3 dimensions instead of only one.

Why is it faster in software? It's like going downtown with a car. Sometime there are such gridlocks that it's faster walking than driving even tough cars are usually faster than pedestrian.

Each time you send a vertex to the card, it takes time to get to the card, it takes time to transform it and it takes time to calculate the normal to know if it should be clipped, culled or displayed. Why should we let the hardware do all that stuff if we can positively know that half the scene won't be displayed by making ONE test?


[edited by - Coincoin on July 26, 2002 9:17:40 PM]

Share this post


Link to post
Share on other sites
you clip one cube against your frustum and you know if 10''000 of triangles are visible or not..

now tell me your pc is slower at checking one cube gainst the frustum than your gpu can draw/not draw 10''000 of triangles?

"take a look around" - limp bizkit
www.google.com

Share this post


Link to post
Share on other sites