Collision detection

This is actually not just a collision detection project, but a series of various very tightly related projects concluding in a simple collision detection.

Bounding volumes

To start with, I made some simple bounding volumes:


Simply by calculating the average point.


– Take a point, and find the one furthest from it. Get the center and make a sphere that takes both points.

– See if any point is not inside the sphere, if found, make a new sphere that takes the previous one and the new point.

– Repeat previous step until no point is missing.

Iterative Ritter:

– Apply Ritter method.

– Take resulting sphere from previous process, shrink it a bit, and start Ritter method from step 2.

– Repeat process as many times as wished for enhanced precision.

Space partitioning: Scene

Then, using the AABBs, the scene is divided in a hierarchy. I have tried constructing the tree top-down, bottom-up and via insertion. The one shown in the video is the top-down, and works similar to a KDTree, in the sense that and axis to divide in two is chosen based of the sizes, but since it is then dividing the objects in halfs, the bounding volumes can still have overlaps.

Space partitioning: Objects

The objects’ triangles are also divided, either using an actual KDTree or an Octree. This servers the purpose of making more precise collision and such, after the bounding volume has yielded a positive.

I will be showing down below both methods, since the KDTree only divides in 2 every single step through a single axis, for comparison purposes, the images change plenty of steps at a time. The octree changes mostly step by step.

OCTREE                                                                                          KDTREE




























And we can keep going, but it is not going to be visually understandable so I will stop here.

Collision detection

Finally, I set up a scene and check for collisions with simple objets.

White: Object hierarchy concludes there is no collision

Green: Bounding volume concludes no collision

Orange: Divisor plane method concludes no collision

Red: There is collision

Note that for the last stage collision detection I have used a method where it tries to find a plane that divides all the vertices of an object to one side and all the vertices of the other object to the other side. This method only works for convex object (see Convex Hull), and is not capable of determining the collision point. For a method that gets more information and works in more cases, we could, for instance, use the Octree or KDTree distribution of the triangles shown above and find the actual colliding triangles.