# Collision Detection

This topic is 4885 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

After a few weeks of work I've got a fairly robust implementation of an ObbTree and Obb class. I'm at the point now where I can detect which leafs of one ObbTree intersect with leafs of another. Each leaf of the obb tree holds a pointer to the polygon it represents. I want all of my collision detection/response to be on a triangle-triangle basis. I'm a little lost of as where to go now, I understand how to do tri-tri intersections, I'm pretty sure I need to know the penetration depth of one object into another and somehow calculate how far to move the object back along its direction vector so there are no more intersections. I'm just not sure how to tie all this together.

##### Share on other sites
Welcome to the world of collision detection - you've just hit one of the trickiest areas!

I don't know how you represent your objects, but generally, poly-soup object versus poly-soup object is not easy to solve for the info you need. Most physics engine only support convex-object versus poly-soup object and use alogithms such as SAT, or GJK. For non-convex objects, they generally get split up into a collection of convex objects so the problem is still solvable.

Also, you aren't too clear about what you are trying to solve. If you're moving a character through a static world, then swept sphere/epsiloid/aabb versus static triangle is probably what you are after. You could use your ObbTree of the static world to find out which triangles your moving primitive overlaps (broad phase). You could then perform narrow phase detection with the triangles to find the closest time of impact, and the normal of the collided surface. With those results, you can slide/bounce your object along the plane.

##### Share on other sites
Each leaf of my ObbTree contains the polygons from the loaded object that it represents and a convex hull of those points. My end goal here is to develop my own dynamic physics engine. I already have a simple physics simulation in place in which I calculate the moment of inertia from the convex hull of an object and it allows forces to be applied along its faces to produce translational and rotational movement.

Currently i've implemented the SAT for the obbtree-obbtree collision detection. I guess what i'm looking for is the ability to import any polygonal object and have the ability to collide it with another polygonal object. If I have to put a constraint that the object must be convex, thats not an issue since I've implemented a convex hull algorithm which I can use to calculate the convex hull and simply create an ObbTree from that rather than the convex mesh.

##### Share on other sites
Ok I think I can define exactly what I need, I need a method to collide a convex polygon (an object I want to simulate) against a polygon soup (my level), if anyone has any resources they can point me towards, that would be great.

##### Share on other sites
Quote:
 Original post by GorwookenOk I think I can define exactly what I need, I need a method to collide a convex polygon (an object I want to simulate) against a polygon soup (my level), if anyone has any resources they can point me towards, that would be great.

I suppose you have your hash map (octree, matrix, BSP ?) from which you extract a 'smaller' set of polygons (obviously you cannot test your object agains EVERY polygon!!!)

convex object - polygon intersection

##### Share on other sites
a convex polygon? Surely you mean a convex polyhedron (convex hull). Else, you'll be in a world of pain. Already convex object vs polygon soup isn't that much fun. but anyways,....

http://members.gamedev.net/oliii/sweptsphere.zip
http://uk.geocities.com/olivier_rebellion/Cube3D.zip

##### Share on other sites
Your obb tree already provides a first step for colliding a polygon against a polygon soup. You collide the obb containing your polygon against the obb tree made of obbs containing your polygons. When the obbs don't collide, you know the objects contained in those obbs don't collide either. Now you only need to check for collisions between objects when their obbs do collide.

The obb tree allows you to quickly narrow down the possible collisions to a smaller number. Once you find a leaf that collides with your polygon's obb, you do a collision check between the geometry in the leaf and the actual geometry of the polygon (or you can do intermediate tests, for example a test between convex hulls, it really depends what you're trying to do and what the geometry is). You just need to find how to perform a collision test between two polygons.

I guess that in itself is kind of tricky. And then finding the penetration depth is even trickier. Really you want some sort of penetration vector, ideally the vector with minimal magnitude that represents a translation that will leave the objects separated. I think I remember something about being able to find this for two polygons by constructing the minkowski difference between them and then finding the smallest vector from the origin to the boundary of the resulting polygon...I think the idea is that two polygons intersect if their minkowski difference contains the origin, and a vector from the origin to the boundary represents a translation that will separate the objects. The minkowski difference of two polygons is another polygon. I think the minkowski difference can be calculated in an amount of time linear to the sum of the number of vertices of the polygons. It might also be an efficient method to find if two polygons intersect (by checking if the minkowski difference contains the origin).

If the polygons are very complicated, it is easy to make a tradeoff between accuracy and speed by using pre-calculated simplified geometry for the collisions.

##### Share on other sites
The method you're describing using minkowski difference seems to be exactly what i'm looking for. I can use my Obb Tree to get the intersecting polygons and then use the convex hull of the object to calculate the minkowski difference.

##### Share on other sites
Minkowski difference ? Hey guys, what are you talking about ? [smile]

Test intersection between convex object and polygon is very simple!

If you can handle this you can extend the method to convex object-object (the second object becomes a list of polygons).

You can also modify the algorithm, as I've done in my simulation, by inflating the convex hull of the object if you need a 'shield'.
In this case simply translate each plane of the frustum

 newplane.N = plane.N newplane.d = plane.d + thickness

In fact you may want to detect not only intersection but also proximity to avoid and/or reduce penetrations (it depends by your time step)

When you detect a collision you can backtrack the collided object(s) or apply more complex dynamics.

##### Share on other sites
I just did a little more reading on the subject...actually it seems the GJK method is related to what I was saying about the minkowski difference. Apparently there's a collision detection package called SOLID that uses a modified GJK algorithm to find penetration depth between convex polyhedra, so you can try looking for that.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 11
• 11
• 15
• 11
• 11
• ### Forum Statistics

• Total Topics
634149
• Total Posts
3015834
×