Let me tell you about a task that 3D games face a bunch. It’s a difficult task. That task is finding out what’s related to you in 3D space. It’s how you solve scenarios like these:

• I’m a gravity well! I want to know all the triangles close to me so I can pull them towards me (cuz that’s what gravity does)!
• I’m a physics-simulated crate colliding with the ground! I want to know what part of myself is colliding with what part of the ground, so I can bounce off it!
• I’m a camera! I want to know all the triangles in my field of view and nearby, so I can draw them!

These are all different queries. The gravity well wants to know everything within a certain distance, regardless of direction. The crate wants to know the location of a collision between two polygon meshes. The camera wants to know everything in a certain direction and distance. The only thing all these queries have in common is that they are about spatial relationships.

So! In all these cases, we want to give our actor a triangle/list-of-triangles representing the scene geometry they care about. But how can we generate that list? Iterating through every triangle in the whole level is a terrible idea — it’ll take O(n) time for n triangles, and game levels can have hundreds of thousands of triangles. We need some way to quickly reject large batches of triangles at once if we want to make this fast.

Well, thankfully, the problem of high-performance finding a certain item in a list of items has been heavily examined. And there’s a super-common solution — don’t represent your list of every-triangle-in-a-scene as a flat array, represent it as a tree!

Starting with the single top node of the tree that contains all triangles, pick one of multiple child nodes, each containing a subset of all triangles. Every time you go down one level in a tree, you auto-reject all the triangles in all the other branches at that level, and your time to find a triangle goes from O(n) to O(log(n)).

Anyhow, that isn’t a new idea. Video games have been using trees-of-triangles since Doom. There’s mainly two different types of trees-of-triangles used in video games: Binary Space Partition Trees, and Octrees. Each tree type is named after the number of leaves branching out of each node (2 for BSP trees, and 8 for octrees).

Octrees work by subdividing 3D space along the X, Y, and Z axes — the root of an octree represents the entire world, and each of its 8 children represents one of 8 equal-spaced volumes to cut the world up in to: front-right-top, front-right-bottom, front-left-top, front-left-bottom, back-right-top, back-right-bottom, back-left-top, and back-left-bottom. That is, going further positive or negative in each of [X,Y,Z].

To find spatially-related objects in an octree, you just traverse the octree and go left/right, up/down, and forward/back at every node. (you may have to traverse multiple leaves of the octree if your query doesn’t line up with the bounding boxes well).

Octrees are cool because they are simple, and because every time you go down one child, you cut out 7/8ths of the world! However, they have drawbacks in that many triangles will have to go in multiple leaves of the octree, because most triangles aren’t perfectly split along every axis.

Binary Space Partition trees can be implemented in many ways, but the core difference between them and octrees is that instead of subdividing volumes into octets along the X, Y, and Z axes, you only split volumes into two sections — but you can split along any axis you want, and you don’t have to split into even halves. Then, you iterate through and determine whether you’re “outside” or “inside” each split plane to advance down the tree.

Although you can use any split plane, some BSP trees exclusively split volumes such that one of the triangles in the scene lies along the split plane. If you abide by that restriction, then, due to some math that I frankly don’t understand, you can quickly generate a list of triangles sorted by distance from any point in the BSP-tree-represented world — which is great for drawing. Read this incredibly long explanation of BSPs in games for information.

So anyhow! Spatial partitioning systems are a great idea and you should use them.