Octrees are a popular data structure for dividing up a scene to improve the performance of collision detection, etc.
Eric Nevala has provided an introduction (including diagrams and code samples) suitable for intermediate programmers, with the following assumptions:
Before we dive in, I'm going to be making a few assumptions about you as a reader:
- You are very comfortable with programming in a C-syntax-style language (I will be using C# with XNA).
- You have programmed some sort of tree-like data structure in the past, such as a binary search tree and are familiar with recursion and its strengths and pitfalls.
- You know how to do collision detection with bounding rectangles, bounding spheres, and bounding frustums.
- You have a good grasp of common data structures (arrays, lists, etc) and understand Big-O notation (you can also learn about Big-O in this GDnet article).
- You have a development environment project which contains spatial objects which need collision tests.
Read the article HERE on GameDev.net.