When using an octree for collision detection in a game, should the tree be rebuilt every frame or is there a better way assuming half the objects move in a frame?
Asked
Active
Viewed 2,602 times
3 Answers
11
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.
luke
- 36,103
- 8
- 58
- 81
7
If the scene changes with every frame, then you have to redo the tree.
duffymo
- 305,152
- 44
- 369
- 561
-
3If the scene changes with every frame, then you must update the tree. It is not always necessary to "redo" the entire tree. My own implementation can update as needed when objects move. Weather you can do that or not depends on how you implement it. – phkahler Dec 01 '10 at 16:08
-
redo == update; I consider them synonyms. But your point is correct - it's almost like you'd need a dirty flag to mark pieces that changed. – duffymo Dec 01 '10 at 16:58
4
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.
-
1I have two clarifying questions. If an entity ends up overlapping two tiles/squares (due to width/height), and it moves, how do you efficiently update its position(s) in the grid? Second, how can you efficiently query for all *unique* entities if they can be stored in multiple places? – Paragon Aug 07 '18 at 15:51
-
That's a fairly elaborate. I have a ridiculously long-winded answer here on all the possibilities: https://stackoverflow.com/questions/41946007/efficient-and-well-explained-implementation-of-a-quadtree-for-2d-collision-det. The easiest way is if your agents have a small range in terms of their size, like your biggest agent isn't that much bigger than your smallest agent, then you can use the upper bound radius or something to this effect whenever you search for colliding agents at a particular point. You expand the search radius by the upper-bound size/radius of the largest agent... – Nov 26 '18 at 10:15
-
... that's a sort of goofy solution but it can be very efficient when it's appropriate and it's naturally very simple. When you do that, even if your agent overlaps multiple grid cells, you only need to treat it like a point and store it in the one cell its center point occupies. An alternative is a loose structure, and in that verbose answer above I give an example of how to do a loose grid as well as a loose quadtree (which extends easily to loose octree in 3-dimensions). Finallly just redundantly store the agent in all the cells it overlaps. If you do that, then the trickiness [...] – Nov 26 '18 at 10:17
-
[...] is that you want to use large enough cells so that you don't have like a giant agent occupying like 2000 grid cells which would suck. Another is that you want to store some flyweight pointer store of thing to the agent -- make it as light as possible. Finally if you want to efficiently find the unique entities when there's overlap and redundancy, one way is to store like a boolean (could be a single bit) to the agent. When you do your queries, only add the agent to the list if this boolean is set to false. If it is, set it to true. When done, loop through the resulting set and set [...] – Nov 26 '18 at 10:20
-
[...] those booleans back to false. That's a cheap and dirty kind of trick to find unique sets in linear time (with dirt-cheap iterations) without a more expensive hash lookup or a linearithmic algorithm involving a tree data structure to represent the unique set. – Nov 26 '18 at 10:21
-
Thanks a lot! All of those answers help. I did think of the boolean idea but figured there must be a better way. I was additionally worried that if another query began before this one finished (some asynchronous call in JavaScript causing a second query), the boolean system wouldn't work. Cheers! – Paragon Nov 27 '18 at 02:46
-
If the queries are occurring asynchronously in parallel then yeah, the intrusive solution storing booleans/bits directly in the entities is going to be problematic (race condition or thread bottleneck). In that case I'd just go for like a fast set container like a good and cheap hash table that's quick to construct. Another option is if your data can be accessed by index and the indices are fairly dense (not sparsely distributed) over a range that's not ginormous, then you could use a bitset parallel to the array of entities and avoid storing data intrusively into the entity that way. – Nov 27 '18 at 03:14
-
In that case once you traverse the 52nd entity, you set/mark the 52nd bit in that parallel bitset and append it to a sequence if that 52nd bit wasn't already set. And that parallel bitset becomes temporary local object you can store per thread making a query and then discard when query is finished to avoid shared data. – Nov 27 '18 at 03:17
-
Yet another option (there are many ways to tackle this) is to just gather the duplicates in the queries and then sort and remove duplicates. That might sound gross algorithmically but usually your collision queries are going to, provided the data structure is reasonable, yield a fairly small number of results (even with duplicates thrown in). So the time to sort and filter out duplicates could be quite trivial here depending on the context (can do with one linear pass with radix sort), and it might not be such a bad tradeoff if you want to be able to do multiple queries in parallel. – Nov 27 '18 at 03:26
-
But I'm kinda mulling over this and brainstorming a bit at the same time. I'm not used to parallelizing the actual collision queries. In most contexts I've devoted a single thread to collision detection and other threads to other tasks. If you want to devote more threads to just collision detection itself, I'd probably be more strongly swayed to utilizing a loose data structure which doesn't even involve duplicate entries in the data structure no matter what. – Nov 27 '18 at 03:29