search

idmillington / cyclone-physics

The Physics engine that accompanies the book "Game Physics Engine Design"
MIT License
927 stars 262 forks source link

Broadphase Not Checking Collisions Between Children #33

Open neon64 opened 9 years ago

neon64 commented 9 years ago

While trying to implement your system, it came to my attention that if there are two BVHNodes that don't collide, it won't check collisions between children.

As far as I'm aware that means that if the two root's children aren't colliding, then no more collisions will be tested amongst objects deeper in the tree. Upon implementing this system, I have found that hardly any collisions are generated because they are all occurring within children deep down in the tree that are never being checked.

This article on a Dynamic AABB Tree has a different algorithm that I am about to compare to see if it fixes my issue:

http://allenchou.net/2014/02/game-physics-broadphase-dynamic-aabb-tree/

Hopefully you can point me towards some information as to whether this is a bug or just my misunderstanding.

YukinoHayakawa commented 9 years ago

if the two root's children aren't colliding, then no more collisions will be tested amongst objects deeper in the tree.

Not really. Two objects can collide within a child of the root while they are both far away from another child. The bounding volumes of two children don't touch only means there won't be any collision between any pairs containing an object from child A and another from child B, which is independent of the check of collisions inside each of the children. The early-out routine should descend into every level of the hierarchy in order to consider every possible collision pair. So I consider it as a bug because it ignores one of the major situations. There also has been a related post in stackoverflow which may help. http://stackoverflow.com/questions/8260848/bvh-collision-traversal-algorithm-not-looking-within-each-descendant