6
\$\begingroup\$

As I understand it there are 3 popular strategies for spatial partitioning: sweep and prune, quad/oct tree and uniform grid. Uniform grid is problematic for me because I have not set an upper limit on how big each entity can become so every time an entity move I may need to update multiple grids.

So right now I am exploring sweep and prune vs trees on which is better for my use case. I know for sure that a majority of my objects contained in the structure will be moving every frame. I need to support 2 tests: 1) whether any objects overlap/collide with each other and 2) whether any object will overlap/collide with a ray that can traverse through the entire playing region.

I know for question like these the answer is usually impossible to know beforehand without testing etc. But certainly this is a very common problem and many of you have experience with. If so, can you share the strength/weakness of each method with respect to my use case and which method is more likely to produce better results? And for the record I am trying to animate 1k+ dynamic entities in 3D space so brute forcing is unlikely to be enough. I also have another structure for static objects so all contained entities are dynamic.

Improve this question
\$\endgroup\$

1 Answer 1

Reset to default
4
\$\begingroup\$

I recently went through this exercise and evaluated both on a couple of platforms.

I found that my engine had many moving objects clustering on top of each other. As they moved around the Sweep and Prune (SAP) implementation caused too much sorting and overlap callbacks every frame. It was crippling my platform, which is not too powerful. I did all the tricks - use quantized floats stored as integers to allow for integer compares, stab entries, etc.

My research covered reading up on how commercial engines were doing it as well as discussions on a number of message boards.

In the end I chose a dynamic bounding tree based on the implementation in Box2D. You can find a great implementation here: https://code.google.com/p/box2d/source/browse/trunk/Box2D/Box2D/Collision/b2DynamicTree.h

A number of people have used this version and converted it to 3D with much success.

The key is that the objects, when put the tree, have their AABB inflated in the direction of their velocity by some platform and use-case amount. When the object moves, if it doesn't travel outside of the AABB, the tree is not modified. This effectively amortizes the cost of tree updates over multiple frames.

This structure is normally paired with a OverlappingPairCache - a cache that stores A/B pairs of objects. Every frame that cache is walked and collisions performed between them.

I would encourage you to start with the bounding tree. If I had I probably would never have looked back. Instead I burned a lot of time tinkering with my SAP before giving up and looking elsewhere. This seems consistent with what people are seeing in Box2D, Bullet, PhysX and maybe even new versions of Havok.

If you want more details on implementation details, let me know. The thread on the Bullet Physics Research forum I found most interesting is here:

http://www.bulletphysics.org/Bullet/phpBB3/viewtopic.php?f=4&t=9800

And Randy Gaul's write is really good, too:

http://www.randygaul.net/2013/08/06/dynamic-aabb-tree/

Improve this answer
\$\endgroup\$
8
  • \$\begingroup\$ Thank you for your comment! I have looked at the links provided and a few more. Let us assume we are working in 1D for now. I understand that the branch nodes contains an area bigger than its 2 children and a branch always contains 2 children. I dont understand how node insertion works. Suppose if the branch is [2,10] with 2 children (3,5) and (8,9) and I am inserting a new node with value (6,7), what does the tree look like after insertion? What if I am inserting (4,5)? \$\endgroup\$
    – user55267
    Nov 22, 2014 at 4:16
  • 1
    \$\begingroup\$ The goal is to always keep the tree balanced, and so there are times when it will be rotated. After inserting 6,7 the root will have two children: one child with with its own two children (3,5) and (6,7). The other child will be (6,7) and a null node. The tree balancing is performed to keep the tree efficient and employs a heuristic called Surface Area Heuristic, which sums the perimeter of each AABB and scores them. Randy Gaul has a good writeup on it here: randygaul.net/2013/08/06/dynamic-aabb-tree \$\endgroup\$
    – Steven
    Nov 22, 2014 at 4:29
  • \$\begingroup\$ Sorry that should be one child with it's own two children (3,5) and (6,7). It would have the bunds of (3,7). The other child of the root has one node (8,9) and a NULL node. It would have the bounds of (8,9). The root node would have the bounds of (3,9). \$\endgroup\$
    – Steven
    Nov 22, 2014 at 4:36
  • \$\begingroup\$ So the branch node does not keep an range bigger than both its children? \$\endgroup\$
    – user55267
    Nov 22, 2014 at 4:39
  • \$\begingroup\$ That's right. The root node would contain an AABB that encloses all of the final leaves. Each inner node contains an AABB that encloses it's children, on down the tree. When you want to test for collision, you keep descending the tree as long as the search AABB intersects the node's AABB. \$\endgroup\$
    – Steven
    Nov 22, 2014 at 5:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .