OctTrees and Collision / Long Distance
Author
I''ve read a bit about OctTrees. So far, I understand the space partitioning, but I am not sure how I can use it.
I guess the idea is, you have these cubes and you only load the ones you need, so the ones in the far distance can be left out, but what about if we need to see things in the distance?
So, suppose my map is an open desert, and I am in a particular octree zone, but I want to render a cactus that is a few zones away in front of me, how do octrees help me? With octrees, am I loading several zones up in front of me? Or only loading one zone at a time?
What about collision detection? If I only have one cubish zone loaded, then what happens if I send a projectile, we''ll call it a rocket. My rocket hits the border of the zone I am in (the only zone I have in memory) and then what happens?
You can think of an octree as a special version of a 3d grid. In fact, you can even code it that way.
Imagine you have a 3d grid with 10x10x10 m^3 sized cells. You can cast rays from one grid cell to the next by finding the ray
''s intersection with each grid cell. This way you skip any cells that aren''t along the ray''s path.
Well, in a desert world as you describe, 99% of the grid cells in the sky will be totally empty. That seems a bit of a waste. What if you could make the empty areas use larger cells than the full areas. You could have a low-res grid that was 80x80x80 cells, for the empty ones, and then 10x10x10 for the cells with something inside. Well, maybe you could just skip the empty cells altogther and not store them at all!
This line of thinking can lead you to creating an octtree. An octtree can be implemented as a ''sparse grid''. The idea is that the root node has up to 8 child nodes, each 1/8 the size of the root node. If a child node is empty, then it can be deleted, or you can make sure it has no children, or you can force it to subdivide anyway.
If we applied this idea to the desert, only the portion of the octtree near the desert floor would have many smaller cells. The rest of the tree would be fewer large, empty cells.
So, you don''t leave out visible cells in the distance, but you don''t have to store empty cells in the distance, like you would for a 3d grid.
I am using an octree for my engine for the high-level scene mgt. I force a subdivision down to 16x16x16 meters or so. It is very convenient for frustum culling.
One main idea regarding octtrees is that large areas of your world are empty or contain only a few objects, and you can store these in bigger cells with no children, and then save the small cells for areas with the detail in it. This allows your ray cast to totally skip large areas of the sky, for instance, and just do work when the bullet gets near the ground.
Imagine you have a 3d grid with 10x10x10 m^3 sized cells. You can cast rays from one grid cell to the next by finding the ray
''s intersection with each grid cell. This way you skip any cells that aren''t along the ray''s path.
Well, in a desert world as you describe, 99% of the grid cells in the sky will be totally empty. That seems a bit of a waste. What if you could make the empty areas use larger cells than the full areas. You could have a low-res grid that was 80x80x80 cells, for the empty ones, and then 10x10x10 for the cells with something inside. Well, maybe you could just skip the empty cells altogther and not store them at all!
This line of thinking can lead you to creating an octtree. An octtree can be implemented as a ''sparse grid''. The idea is that the root node has up to 8 child nodes, each 1/8 the size of the root node. If a child node is empty, then it can be deleted, or you can make sure it has no children, or you can force it to subdivide anyway.
If we applied this idea to the desert, only the portion of the octtree near the desert floor would have many smaller cells. The rest of the tree would be fewer large, empty cells.
So, you don''t leave out visible cells in the distance, but you don''t have to store empty cells in the distance, like you would for a 3d grid.
I am using an octree for my engine for the high-level scene mgt. I force a subdivision down to 16x16x16 meters or so. It is very convenient for frustum culling.
One main idea regarding octtrees is that large areas of your world are empty or contain only a few objects, and you can store these in bigger cells with no children, and then save the small cells for areas with the detail in it. This allows your ray cast to totally skip large areas of the sky, for instance, and just do work when the bullet gets near the ground.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement