I would like to know the advantages and disadvantages of using octree or quadtree for spacial data structures? In a 3d gaming setting would you ever need more than 4 children nodes? Does it take longer to traverse through oct tree than quad tree? Is one of the two by all means faster than the other or is it a trade off sort of thing?
closed as too broad by congusbongus, Seth Battin, bummzack, Josh♦ Mar 26 '15 at 17:14
Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
I'm not really good at fabricating N- statements, but the minimum search times for an object at child of every child should be close to the same +- a dimension. If the object falls at child of every child the calculation for the octtree could be as much as N^2(?) longer.
Since you don't specify how/why the tree is being used, it's hard to give a definitive answer.
The advantage is based on your objects' perspective/degrees-of-freedom.
Here are two examples:
If your world is a quad-based terrain-style game, and your objects are all earth-bound, there's no reason to add a third dimension to your search. That is to say that your objects all traverse the terrain by moving from (X, Z) to (X1, Z1), interpolating their Y-values from an arbitrary second source (height map). The Y value also provides hints to the objects about what is in-between them (line-of-sight/collision ray-casting). In all cases, down is down. From your objects' perspective, other objects may be higher or lower, but always appear in one of 4 quadrants.
An anti-example of this would be ray-casting the mouse cursor with an octtree in SimCity. Do you care if you are hovering the top-half of the building vs. the bottom half? You wouldn't save any time by sorting the top half of every sky-scraper into a separate search dimension. For SimCity, we need to know if any part of a building is hovered, or not. In SimCity, each building occupies an (X, Z) and has a variable height.
If many of your objects can move in 3D, an octtree may make more sense. In a space simulator, objects could be out-of-range, or out-of-scope, in more ways (above/below). Culling things behind you is still necessary, but now your object's are able to orient arbitrarily; "down" is no longer down, "forward" is now down, and "down" is now backward. From your objects' perspective, other objects may appear in any one of the 8 quadrants.
Using C&C, a quad-based, terrain-style game with flying units ("down" is always down, even for aircraft), as an example, where all flying units still occupy an (X, Z) but maintain a height of (heightmap + 20), neglecting combat animations. While ray-casting through the extra dimension, even on a quad-based game, the node directly above your test-object contains only flying units. Air-to-air craft don't have to test against units in the same node as the terrain; in other words, when an air-to-air jet is testing for objects in front of it, any node returned that contains the terrain, can be skipped. Likewise, a bomber aircraft that can only target ground-based objects, can skip all nodes that do not contain the terrain. Surface-to-air missile launchers wouldn't need to test terrain nodes either.
A similar anti-example would be jet aircraft in Battlefield-style games. You can move up and down, but you must do so by only flying "forward". A jet in Battlefield cannot fly or shoot in any direction other than forward, so if you used an octtree while flying, you would always skip 4 of the 8 quadrants. Another jet shooting you from behind requires the same (only) 4 quadrants that you are using. A helicopter or VTOL, however, can move straight "down" and, if equipped with turrets, shoot in semi-vehicle-independent directions. The turrets can only see and shoot "forward".
Hopefully this highlights the differences in needs/advantages. Don't get locked into one or the other, use them when applicable.
One more edit:
Back to the Battlefield example, if you maintain separate air-only and ground-only octrees that are identical in every other way, neither the overall object count nor the overall dimension count increase, so overhead does not increase (neglecting the increased memory footprint). So, for a vehicle that can shoot "bullets" (at land and air vehicles) and can also shoot lock-on style anti-air missiles at only air-craft, the difference, for targeting purposes, is a matter of which tree(s) to test, not how long it will take (the node coordinates/dimensions are identical). A bullet from a jet can skip ground-nodes until the bullet enters a node that contains the terrain. A ground-node returned from the air-tree, could link directly to the corresponding node in the ground-tree, allowing the bullet to be "handed off" to the ground tree. Separating the objects into different, nearly-identical trees ahead of time may help your performance if your game has to frequently distinguish between the two. Indexing between two 3D trees is a 4D tree. (X, Y, Z, WhichTree)