Quadtree or Octree for this type of project?
Author
I have a question on which method would be best for what I want to do, and possibly a reason why. I just want some opinions on the subject if possible.
The project would include LARGE areas of terrain (envision a game such as Asheron''s call (not the mmo aspect just the vast amount of terrain).
Obviously I can''t load the whole map in, so I will have to be loading parts of the map in on another thread (at least I think =])
In my opinion I think a quadtree might be best, as an octree would be too slow for this type of thing, but I''ve never used an octree stucture so I''m unsure if that is totally true.
So the question is, if you were to have such a large seemless area of terrain would you use a quadtree algorithm or octree?
Thanks ahead of time =]
for terrain you could use either, but quadtrees seem to be more comonly used. the good thing about octrees is you can mix indoor and outdoor scenes. quadtrees are somewhat limited to outdoor, and bsp are ideal for indor.
My Homepage
How many Microsoft employees does it take to screw in a light bulb?
None, they just declare drakness as a new standard.
My Homepage
How many Microsoft employees does it take to screw in a light bulb?
None, they just declare drakness as a new standard.
I had something big typed up, but my son started clicking the back button no my mouse. Why does XP make my extra buttons back/forward 
.
Anyways, as I was saying. It''s just as easy to use a quad tree for an indoor environment as it is for an octree. An octree basically just stores a list of objects visible within each of the final nodes. You can store a similar linked list in each of your quad tree nodes, and draw them only if the node is visible. Same concept, same results. Only benefit to the octree, is that an object will no span more than one node (otherwise you''re supposed to break it and draw as 2 objects). You can also just store a flag per object that says if it''s been drawn or not, that way you can have multiple nodes with the same object in it (if it spans many nodes). Or, you can even generate an octree in 2d, since you don''t really have many things high/low in a terrain (besidse how high/low the terrain is, but you won''t gain to much occluding this unless it''s a lot of stuff). An octree is much harder to handle with dynamic objects, so be careful.
Billy - BillyB@mrsnj.com
.Anyways, as I was saying. It''s just as easy to use a quad tree for an indoor environment as it is for an octree. An octree basically just stores a list of objects visible within each of the final nodes. You can store a similar linked list in each of your quad tree nodes, and draw them only if the node is visible. Same concept, same results. Only benefit to the octree, is that an object will no span more than one node (otherwise you''re supposed to break it and draw as 2 objects). You can also just store a flag per object that says if it''s been drawn or not, that way you can have multiple nodes with the same object in it (if it spans many nodes). Or, you can even generate an octree in 2d, since you don''t really have many things high/low in a terrain (besidse how high/low the terrain is, but you won''t gain to much occluding this unless it''s a lot of stuff). An octree is much harder to handle with dynamic objects, so be careful
.Billy - BillyB@mrsnj.com
hmmm... I think it might be possible to make a tree that is both a quadtree and an octree... They both really do the same things only one has 4 nodes and one has 8, plus one accounts for the z node in its sorting/traversing algorithms.
The base node would be a quadtree node, but its children could potentially be an octree node, although an octree node would ONLY have octree node children.
The advantage to this would be that you would start out with a base Quadtree node and then those would each have 4 quadtree node children all with a X and Y length = to the length of the frustum. Making a 4x4 grid of terrain ''patches''
That way of the player moves EAST you simply make sure that the new nodes are rdy. and loaded before the player can get close enough to see them and then shift all 16 ''patches''( the ''grandchildren'' of the primary node ) to the left, and place in the 4 new eastern nodes.
The trick is thought that if any of those new 4 nodes needs to be used as an octree, which can be defined ahead of time by your ''patch'' you simply load an Octree node. If its only going to be flat plains or gently rolling hills, then load the data into a quadtree node.
I''m open to critisism on the idea
~Vendayan
The base node would be a quadtree node, but its children could potentially be an octree node, although an octree node would ONLY have octree node children.
The advantage to this would be that you would start out with a base Quadtree node and then those would each have 4 quadtree node children all with a X and Y length = to the length of the frustum. Making a 4x4 grid of terrain ''patches''
That way of the player moves EAST you simply make sure that the new nodes are rdy. and loaded before the player can get close enough to see them and then shift all 16 ''patches''( the ''grandchildren'' of the primary node ) to the left, and place in the 4 new eastern nodes.
The trick is thought that if any of those new 4 nodes needs to be used as an octree, which can be defined ahead of time by your ''patch'' you simply load an Octree node. If its only going to be flat plains or gently rolling hills, then load the data into a quadtree node.
I''m open to critisism on the idea
~Vendayan
quote:Original post by Vendayan
hmmm... I think it might be possible to make a tree that is both a quadtree and an octree... They both really do the same things only one has 4 nodes and one has 8, plus one accounts for the z node in its sorting/traversing algorithms.
The base node would be a quadtree node, but its children could potentially be an octree node, although an octree node would ONLY have octree node children.
The advantage to this would be that you would start out with a base Quadtree node and then those would each have 4 quadtree node children all with a X and Y length = to the length of the frustum. Making a 4x4 grid of terrain ''patches''
That way of the player moves EAST you simply make sure that the new nodes are rdy. and loaded before the player can get close enough to see them and then shift all 16 ''patches''( the ''grandchildren'' of the primary node ) to the left, and place in the 4 new eastern nodes.
The trick is thought that if any of those new 4 nodes needs to be used as an octree, which can be defined ahead of time by your ''patch'' you simply load an Octree node. If its only going to be flat plains or gently rolling hills, then load the data into a quadtree node.
I''m open to critisism on the idea
~Vendayan
Nice concept, just like you can store BSP trees (even though they''re static, horribly dated, and only useful for collision detection nowadays)in an octree node. Its just the execution you gotta think out, and im not gonna do it for you.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
