Optimize Collision Detection
-
Hello.
In C++ I am attempting to catch when an object collides with another object. I've looked into the GeColliderEngine class and this seems to do what I want, but it does not seem practical to compare every object in the scene to see if any have collided every update.
My end goal is to catch when a object with a dynamics tag has collided with another object, and from that be able to get data such as the velocity and what object has been hit.
Would there be an efficient way to use GeColliderEngine or an alternative way to get what I'm looking for?
Thanks for any help!
John Thomas
-
The GeColliderEngine is a more finer grained approach (Narrow Phase). It is recommended to use it still, but it should be combined with some Broad Phase spatial partitioning hierarchy (KD Tree, Half-Spaces) or bounding hierarchies (AABB Tree, OBB Tree, etc.) which can quickly and easily weed out large swaths of objects that have no collisions by using either bounding boxes (thus, BB) of the objects or blocks of space between them.
At first this may seem contradictory: more code work to do this faster? Yes. This is classic Divide and Conquer. Instead of checking EVERY object against EVERY other object EVERY time no matter what, the faster you can remove objects from consideration by checking a simple overlap/locality, the faster the collision detection algorithm gets.
So, first do a Broad Phase to find only objects that are or may be colliding (even overlapping bounding boxes incur many false positives). Then move to a Narrow Phase to determine the type of collision (if any) and get the details of it. Personally, I found AABB hierarchies to be real-time fast if designed well.
-
Hi John and thanks for reaching us.
With regard to your question, as already suggested by Kuroyume it's relevant to use a broad-phase collision detection prior to the narrow-phase in order to reduce the time complexity of your code to O(log n) rather than O(n^2) or, when "properly" designed, to O(n).
Aside from the notable comment from Kuroyume, I also invite you to evalute Grid acceleration structures performing pretty well for many simple moving objects of about the same size (e.g., many moving discs with similar radii).In addition, I've stumbled upon the chapter 3 of this thesis where collision detection is properly discussed and both narrow and broad space collision detection topics are touched.
Finally, considering that the MAXON API comes with a nice gift in terms of space partitioning structure, I invite you to investigate the maxon::KDTree class as described in the related manual.
Best, Riccardo
-
Hello,
Thanks for the responses. I thought that this might be the case and just wanted to clarify it before moving forward.
John Thomas
