Should an octree be rebuilt every frame?

When using an octree for collision det开发者_运维百科ection in a game, should the tree be rebuilt every frame or is there a better way assuming half the objects move in a frame?

If you have a lot of static geometry in your scenes, consider building separate octrees. You could also express the same idea by having more complicated leaf nodes that differentiate between static and non-static geometry.

Bottom line: only regenerate what you have to.

If the scene changes with every frame, then you have to redo the tree.

If you have very dynamic data moving every single frame and still need to accelerate collision detection, I actually recommend using a fixed 3D grid for it. 2-dimensional equivalent:

It can also double over as a free list to allow constant-time removals, like so (utilizing the next index as either an index to the next element in the same grid cell or the next free element to pop off from the free stack if it has been removed):

Another example:

Now in 3 dimensions, this might seem like it'd require explosive memory. However, the trick is to just make each cell store a 32-bit index into an array and basically serve as a singly-linked index list. That reduces the size of each cell down to 32-bits. Now if you store a 100x100x100 grid (1 million cells), that'd take less than 4 megabytes.

When elements move around, you can just remove them from the cells they occupy, move them, and insert them into the new cells. All you have to do in order to do this is manipulate some 32-bit indices (no memory allocation/deallocation to transfer elements from one set of cells to others). This is all constant-time and doesn't require rebalancing trees or splitting octants that become too crowded or anything like that.

You can also use a hierarchy of grids (this might sound like an octree but different). What I mean by that is that you might have one coarse grid for whole mesh objects in your scene. Then each mesh object might store a coarse grid, say, 10x10x10, for each of its parts. Then each part stores a fine grid or octree for each of its polygons. This allows non-organic meshes which are, say, rigid with parts that are just rotating like a robot to avoid having to update the fine grid/octree of polygons and just update its own coarse grid of parts and the coarse grid of world objects when it starts rotating its legs and arms, e.g. Only organic models need to update their fine grids when they get deformed by bones, e.g.

The octree I'd keep for your completely static elements/parts that never need to be updated per-frame and I'd use a nice octree, sparse with maybe some post-processing for cache-friendly memory access. You have a bit more time available to accelerate searches into those and minimize their memory use if you can assume that the octree never needs to be updated once it is built.