Need help on "Quadtree" and "OctTree"
Author
Well, actually, I need help understanding the concepts behind splitting a region into sub-divisions for the purpose of optimising rendering (I'm using "Programming RPG games with Direct X, by Jim Adams)
In essence I understand the need for a viewing frustrum. It makes sense to clip out meshes that do not appear in the fov.
However, I do not see the purpose of sub-dividing the region into nodes. Doesn't the render engine simply index meshes (and only those in view if the viewing frustrum is applied) and renders them?
How can there exist regions where there are no polygons? Perhaps in a 3D asteroid game this is so. But in a first-person-shooter or first-person-rpg there will ALWAYS be polygons in a region. The very ground/terrain the player walks on will contain vertices and polygons.
Any clarification on this concept would be much appreciated. Thanks.
the reason for sub-division is for purpose of grouping
what are the advantages of grouping?
less processor work
if you try to process every single triangle, you have lots of cpu overhead...
if you could divide whats in the world into little groups, then you could check if camera can see "group1", which might contain 300 triangles. thats one check compared to 300 checks (to find out if its in the camera's view).
there are other more complex reasons, but this is the basic one.
and the sub-regions only exist in, well... memory to be technical. they have nothing to do with the graphics api. you simply create them from thin air.
what are the advantages of grouping?
less processor work
if you try to process every single triangle, you have lots of cpu overhead...
if you could divide whats in the world into little groups, then you could check if camera can see "group1", which might contain 300 triangles. thats one check compared to 300 checks (to find out if its in the camera's view).
there are other more complex reasons, but this is the basic one.
and the sub-regions only exist in, well... memory to be technical. they have nothing to do with the graphics api. you simply create them from thin air.
and btw, a graphics api doesnt care where you're camera is at or where it is looking. if you tell it to draw triangles, it will draw triangles. regardless if they are off the screen, viewing window, or even not on the buffer (yes thats possible).
Author
Quote:
if you try to process every single triangle, you have lots of cpu overhead...
if you could divide whats in the world into little groups, then you could check if camera can see "group1", which might contain 300 triangles. thats one check compared to 300 checks (to find out if its in the camera's view)
But this is no different from clipping out polygons that are not in the viewing frustrum.
Number of polygons in frustrum is same regardless of rendering polygons per mesh, or whether you render polygons based on node grouping.
I don't see why node grouping makes life easier for the rendering process.
It can be expensive to test every single object against the view frustum. If you use something like a quadtree or octree, then you can eliminate large portions of the scene from having to be tested for visibility, which is more efficient. If a quadtree node isn't in the view frustum, then you don't have to test any of its children for visibility.
Quote: Quote:
if you try to process every single triangle, you have lots of cpu overhead...
if you could divide whats in the world into little groups, then you could check if camera can see "group1", which might contain 300 triangles. thats one check compared to 300 checks (to find out if its in the camera's view)
But this is no different from clipping out polygons that are not in the viewing frustrum.
There is a differnce. Clipping is done after all the transformations to view space and after lighting. So all the triangles that YOU clip do not need to go through all those transformations.
Quote:Original post by embposQuote:
if you try to process every single triangle, you have lots of cpu overhead...
if you could divide whats in the world into little groups, then you could check if camera can see "group1", which might contain 300 triangles. thats one check compared to 300 checks (to find out if its in the camera's view)
But this is no different from clipping out polygons that are not in the viewing frustrum.
Number of polygons in frustrum is same regardless of rendering polygons per mesh, or whether you render polygons based on node grouping.
I don't see why node grouping makes life easier for the rendering process.
read what Oxyacetylene wrote
Quote:Original post by Bliz23Quote: Quote:
if you try to process every single triangle, you have lots of cpu overhead...
if you could divide whats in the world into little groups, then you could check if camera can see "group1", which might contain 300 triangles. thats one check compared to 300 checks (to find out if its in the camera's view)
But this is no different from clipping out polygons that are not in the viewing frustrum.
There is a differnce. Clipping is done after all the transformations to view space and after lighting. So all the triangles that YOU clip do not need to go through all those transformations.
*nods*
Quote:Original post by embposQuote:
if you try to process every single triangle, you have lots of cpu overhead...
if you could divide whats in the world into little groups, then you could check if camera can see "group1", which might contain 300 triangles. thats one check compared to 300 checks (to find out if its in the camera's view)
But this is no different from clipping out polygons that are not in the viewing frustrum.
Number of polygons in frustrum is same regardless of rendering polygons per mesh, or whether you render polygons based on node grouping.
I don't see why node grouping makes life easier for the rendering process.
the reason why it makes it easier is because it reduces the amount of work the processor has to do to sort through all of your triangles to find out if they are in the FOV or not. in otherwords, the graphics api does not tell you, or have a way of letting you know that polygons are in the FOV. you have to mathematically figure it out for your self. all the graphics api does is DRAW things to the screen. a quad-tree system/oct-tree system is the art of grouping parts of your scene (polygons) into sections to decrease the amount of operations it takes to find out if something can be seen or not.
in other words. you have to sort through every single polygon in your entire game world (or zone, map, whatever) and find out if its visible to the camera. if its not, dont draw it, if it is, draw it. if you were to group those polygons, logically (ie: "all of these polygons are next to each other, if the camera can't see me, then he can't see some of my neighbors"), its less work for the cpu because you just skipped 1500 triangles with one call (instead lf making 1500 calls for each polygon in the "group").
do you get it?
another example
say you have a model in your game. he's a ninja and he has 3000 triangles.
the ninja comes from behind you and jumps over your head, quickly appearing right in front of you at lightning fast speed! then he dodges to the left and escapes after landing.
now, considering he is a lightning fast ninja, lets say he was only on the screen for 60 frames (a common time of about "1 second" in most 3d games). in that one second, do you think you would rather make 3000 calls (60 times in this one second, mind you) to your processor to find out if each triangle in his model was in the camera's view or not? or would you rather make one check/call on his bounding box?
apply this same concept to terrains... which can easily be divided into 4/8/16/32/64
these chunks could save you thousands and thousands of cpu ticks, man. by checking only the chunks, instead of what the chunks contain.
say you have a model in your game. he's a ninja and he has 3000 triangles.
the ninja comes from behind you and jumps over your head, quickly appearing right in front of you at lightning fast speed! then he dodges to the left and escapes after landing.
now, considering he is a lightning fast ninja, lets say he was only on the screen for 60 frames (a common time of about "1 second" in most 3d games). in that one second, do you think you would rather make 3000 calls (60 times in this one second, mind you) to your processor to find out if each triangle in his model was in the camera's view or not? or would you rather make one check/call on his bounding box?
apply this same concept to terrains... which can easily be divided into 4/8/16/32/64
these chunks could save you thousands and thousands of cpu ticks, man. by checking only the chunks, instead of what the chunks contain.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
