World geometry and trees.

When a virtual world has a lot of entities in it, which is not uncommon for modern games, there needs to be a fast way to:

- decide what gets drawn on screen.

- decide what entities are interacting with others.
- decide what geometry to disregard ( geometry that is useless )

The first is decided using multiple methods of culling, some of which include:
 - Frustum culling
 - Back face culling
 - LoD (l evel of detail )
 - PVS ( potential visbility sets )
 - Portals

The more methods you implement, the better suited your engine will be for large enviroments with lot of geometry and entities.  It should also be noted that the more methods used, the more expensive it will cost CPU wise to perform these calculations.  If your implementations are not optimized accordingly i.e seperate threads you can suffer extreme frame rate loss.

So we know how to manage what gets drawn on screen, how do we manage what entites are interacting with each other? To decide whether or not a entity is placed on something or should be falling depends on whether or not something is located underneath it, and in order to determine that, we need a realtime method for asking the question if something is underneath it or not.

You can ask yourself what is a good way to do this. Ultimately, if you're not using a tree you're eventually going to have problems making things fast. The simplest (but useless) way to ask if something is underneath an entity is to check the distance and position of every individual triangle in the world against the entity.  This would give you the most accurate answer but would be slow, O(N) for every single frame, and for an operation that needs to be done multiple times per frame it's not an effective solution.  A tree allows us to do something in a O(log N) fashion, by divding all the worlds triangles in half, or in eighths, or in some other number, as many times needed until we get to the most effective target point.

There are quite a few types of trees that will allow us to do this, to list a few:
 - Octree
 - Binary Space Partitioning Trees ( what Quake uses ) a.k.a BSP
 - KD - Trees

There are thousands, if not millions of tutorials / examples online that can get you started on implementing an efficient and effective tree system for your engine.  The one I would recomend if you're going for a high detailed engine with realtime lighting and raytracing would be KD - Trees.  If you're looking for something that's easy to modify in a realtime enviroment, perhaps a in-game map editor I would suggest Octrees.  If you're looking for a highly optimal solution, then stick to BSP.

you can also give your attempt at implementing your own hybrid, which in some cases might be an optimal choice, however you can easily get lost in your train of thought when you need to manage not thousands but millions of nodes.