Sign in to follow this  
atheus

Finding point of collision

Recommended Posts

Hi, i've written a 2d collision detection system for convex polygons using the separating axis theorem. It tells me when two objects intersect, but now I need to find the actual point of collision for the response phase. I plan to search the current time-slice to get as close as possible (but never exact) to the actual time of collision but i still need to find the type (vertex-vertex, edge-vertex, edge-edge) and the location of the contact. Is this information obtainable from SAT? Do i need new and complex math to do this, or is there a simple way to guess? Thanks for any help.

Share this post


Link to post
Share on other sites
As usual, I should mention oliii's tutorials, which I believe cover this material - perhaps he'll provide a link. Meanwhile, yes, you can get this info from the SAT test with a little work.

It sounds like you're finding the intersection through subdivision. I'll just mention that there's also a continuous version of the SAT test that would eliminate the need for an iterative approach. It would be a little more work to code, but would probably be both more efficient and more effective.

Both the swept and static SAT tests return a minimum/last separating axis. The features that will come into contact are the support features of the polygons along this axis. To find the actual contact points, you clip the features together. The most common case, point vs. edge, is fairly trivial; edge-edge requires clipping two parallel line segment together.

I have code for all this, but it's not really cohesive enough to post. If you need additional references other than oliii's code though, I'll be glad to provide further info or post relevant bits from my own implementation.

Share this post


Link to post
Share on other sites
I would first read this and this, and use that code.

and a physics demo here.

to find the actual points of contact, it's explained briefly in the posts, second page. I can write further posts to explain it completely. When I won't feel too lazy.

EDIT : Actually no, I don;t give details. It's in the physics demo though, but it might feel a bit winded. I'll see if I can be bothered tomorrow :)

Share this post


Link to post
Share on other sites
jyk - Yea, I'm gonna use subdivision to find the time of collision.The swept test sounds good, but I can't find an implimentation for arbitrary convex polygons, just AABBs and spheres.

oliii - Thanks for the links, looks like you're the physics engine guru around here :)

OK, here's what i'm thinking:

Broad phase -

1 - Sweep bounding circles into capsules to catch tunneling objects.

2 - Continue to narrow phase for any objects whose bounds collide.

Narrow Phase -

1 - Divide the time-slice into whatever is reqired to find any collision between objects of that size and speed.

2 - Binary search the time segments to find a point where the objects are about to collide but are not yet in contact.

3 - Find the closest two features and their types. This will provide the type of collision (face-vertex, etc).

4 - For face-vertex project the vertex onto the face to find P (point of collision) and use the face as N (collision normal). For face-face use either face as N and use the midpoint of the colliding parts of the faces for P. Treat vertex-vertex as vertex-face for now.


What do you think?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this