Why do you need Quadtrees, Octrees etc?
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]
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]
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
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
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]
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]
Author
Thanks guys, but I am still thinking that the hardware clipping would be alot faster than my software "clipping"...
CEO Platoon Studios
CEO Platoon Studios
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
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
"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.
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.
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.
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.
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]
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]
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
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
