   Using QuadTrees in maps
  So im creating my own map format for my game. Heres the basic data structure of the map.struct Model{    ModelHeader Header;  ModelVertex *Verts;    ModelTVertex*TVerts;    ModelFace   *Faces;    ModelTextureName *TextureNames;};The faces contain a texture id an indices into the TVerts array and the Verts Array.Ive realized it wouldn't be an efficient way render entire levels of the first person shooter I'm making.(kinda mixed between quake and counterstrike)I've read about BSP trees and theyre more suited for indoor levels. Seeing that my levels will indoor and outdoor(depending on the level). They will mostly be outdoor. I also read about Oct Trees and Quad Trees. Theyre supposed to be more suited for outside environments.Please if anyone has any suggestions on what i should use and any relevant resources which could help me implement my map format please post them:).Also any examples showing me the practical use of quad trees, oct trees or bsp trees will be appreciated   
  The generic term of what you're talking about is Spatial Partitioning.It's useful to get an overview of a few different popular approaches in order to know when it's good to use them and whyThe easy ones (apparently you've read up on these already)QuadTrees - Used for sprawling topology that is roughly-2D in it's nature, like terrain, maybe with items scattered over it such as foliage etc.OcTrees - Often used for when the scene may spread out in all directions around you (up, down, infront, behind, left and right), e.g. Space-sims, Aztec Villages, etc.The old onesBSP (Binary Space Partitioning) - This is actually the generic term for any algorithm that divides space in two sections, but most people associate them with ID's quake-style BSPs which were primarily designed for indoor scenes and to provide a potentially-visible-set.  These BSPs were created at a time where rendering even a single polygon was hard work and we didn't want to stall the CPU while it waits for the GPU to catch up (assuming you even had a GPU), now-a-days things are reversed and we throw everything we can at the GPU and more often than not we find it still sits idle while it waits for our little old CPU to give it more polygons.  I would'nt recommend these for rendering since in modern times we're CPU-limited and the overhead of these is higher than it needs to be - That said if you have a large indoor scene you're of-course more likely benefit from using one than not using one.BVH (Bounding volume hierarchy) - A broadly-termed simple tree based technique where each node is a volume of space that also houses all its child-nodes' volumes.  It is how you specifically generate this tree and its bounding volumes that basically decides how effective it is (you can create a QuadTree-like BVH for example). A BVH is often specialised (in how we create it) so as to make it more useful; as you'll read below.The harder onesKDTree - A specialisation of a BVH and a (non-quake-style) BSP, it's basically a BVH that is built by splitting space in two halves each time (like a BSP) but it is done using a split-plane that is perpendicular to each the coordinate axis one after the other. I *think* Doom3 might use these but don't quote me on that.  They're probably better suited to indoor environments but wouldn't do a bad job at outdoor scenes either.ABT (Adaptive Binary Tree) - Basically an adaptation of a KD-Tree that permits the concept of a 'loose-kdTree' but also changes how the split-plane is chosen so that it is controlled by a heuristic algorithm that decides where splits are made.  What you end up with is an optimised BVH which is specifically an AABB-Tree (Axially aligned bounding box tree), which is efficient for the GPU to render and cheap for the CPU to parse.  ABTs are (I would say) the pinnacle of spatial partitioning, the algorithm will produce an optimised tree (or branch-subset) for both indoor and outdoor scenes.   ;  There's another approach that I use, but it's probably not used for 3D too much. I use a grid in a grid to take advantage of the speed of grid transversal and also allow for large environments while allowing complex small environments. It's very similar to a quadtree, but instead of starting out with a 2x2 grid it starts with a much larger grid then gets smaller for more highly populated regions. Works, well but I haven't tested it for every scenario yet.I also broke up the inside from the outside by creating an indoor spatial partitioned place separate from the world and connecting all of the doors and such via portals. Works extremely well for 2D, but again 3D may suffer. Not sure how many portals you can render efficiently in 3D. (If you leave out windows from the buildings then this would probably be very efficient.   ;  Thanks for the replies! Theyve been really useful. So ive decided to go with OcTrees for my map format because theyre easy to implement. Ive searched for OcTrees on google and brings up a few results but all of them seem to describe the concept of OcTrees without giving any code examples of implementing it. Can someone please explain or post a link to an article on OcTrees that would help me with my map format. Thanks   ;  if your levels are mostly outdoor (and you dont have caves and stuff) your map is going to be mostly packed in just 2 dimensions (X and Z) so Quadtree method is probably best. Octrees can be really memory consuming and traversing the tree in the extra Y dimension could become inefficient. I would only use Octrees if most of the level was going to have a lot of buildings with many floors or extreemly dense amount of faces in a small area for collision detection.Quadtrees divide the world in 2 dimensions (usually X and Z dimension) and each branch in the tree splits the world under it in to 4 other nodes etc. Octrees are similar except split the world in to 8 nodes for the extra dimension. There is a lot of stuff on gamedev and google for Quadtrees and quite a bit on Octrees too (although if you understand one you will find the other fairly easy to understand also).hope this helpsEDIT:apparently a good tutorial on octrees at www.gametutorials.com, posted by iNsAn1tY on this thread: http://www.gamedev.net/community/forums/topic.asp?topic_id=90827;Quote:Original post by jrmcvif your levels are mostly outdoor (and you dont have caves and stuff) your map is going to be mostly packed in just 2 dimensions (X and Z) so Quadtree method is probably best. Octrees can be really memory consuming and traversing the tree in the extra Y dimension could become inefficient. I would only use Octrees if most of the level was going to have a lot of buildings with many floors or extreemly dense amount of faces in a small area for collision detection.Quadtrees divide the world in 2 dimensions (usually X and Z dimension) and each branch in the tree splits the world under it in to 4 other nodes etc. Octrees are similar except split the world in to 8 nodes for the extra dimension. There is a lot of stuff on gamedev and google for Quadtrees and quite a bit on Octrees too (although if you understand one you will find the other fairly easy to understand also).hope this helpsEDIT:apparently a good tutorial on octrees at www.gametutorials.com, posted by iNsAn1tY on this thread: http://www.gamedev.net/community/forums/topic.asp?topic_id=90827Well im making a 3d FPS similar to Quake 2 or 3. I will definitely look into using Quadtrees. Are you sure Quadtrees would be the best because my levels will be indoor and outdoor and quite dense. ;  well i can't assure you but i think you will find quad trees a bit easier to set up and it wouldnt be too hard to upgrade to octrees if you wish to try that. I have had bad experiences with Octrees because i have never used a scene that benefits from them. Most of my stuff is outdoor scenes or Indoor bits with no more than 2 levels so the Octree method doesnt really benefit - just slows it down. I think Octrees would be beneficial to space simulation stuff but i've never done one so cant say.If you are going to have large indoor bits too with multiple floors you could try a hybrid method of a quadtree for your world and smaller Octrees or Portals (like Sirisian mentioned) to represent buildings. This could definetely improve collision detection around those areas. I think Quake 2 used BSP trees (correct me if i am wrong), not sure about Quake 3 but i wouldnt use this method because as dmatter said they can slow things down more on modern GPUs. They are also more difficult to build that Quadtrees or Octrees. BSP was mainly used in the days of software rendering. I think Doom 3 used portals from what i've heard.Sorry i couldnt be more help but dmatters given you a quick guide to some popular methods so you can try googling them.EDIT: typo   ;  One of the best things that can really improve performance (if done efficiently) is Occlusion culling which is avoiding sending objects behind walls etc down the pipeline. This will give you mush better performance in all areas but especially the indoor bits and high poly scenes. I suggest you look in to this after you have set up your spatial partitioning.Gamedev tutorial on quadtrees - click