I had the idea of taking each vertex in both of the polygons and calculating a line segment between the current point=(x,y) and the old point (at time when not intersecting)=(x-vx, y-vy) for each polygon, where vx and vy is the relative velocity between the two objects (ie. polyA.vx-polyB.vx, etc) and testing that line segment against each edge of the other polygon.
Not sure if im on the right track or not (espeically with the [relative]velocities), or if there is a better/standard way?
Any help would be appreicated. Thanks.
Two polygons, finding point of collision
Author
Hey guys,
Im using Seperating Axis Theorem (SAT) to detect if two polygons intersect, which works great.. but now I need to find the point where they collide. How would I go about doing this? the two polygons are moving at their own individual velocities vx,vy. Obviously where they intersect there is going to be a patch of intersection, so ideally id like to be able to shift the objects back in "time" along their velocity vectors to the point where they collide, and use the first vertex to intersect with an edge of the other polygon as the point of intersection.
The SAT provides a way of finding a minimumTranslationVector which can be used to shift the objects back enough so that they dont touch, but along the side which has the minimum overlap, but this doesnt take into account the objects velocities, thus yeilds an innaccurate result in determining a point of first intersection.
Here is an image I threw together quickly to clarify:
The blue poly has collided with the larger one, and the green poly would be the blue one shifted back along its velocity vector to the point where it first intersects.
I had the idea of taking each vertex in both of the polygons and calculating a line segment between the current point=(x,y) and the old point (at time when not intersecting)=(x-vx, y-vy) for each polygon, where vx and vy is the relative velocity between the two objects (ie. polyA.vx-polyB.vx, etc) and testing that line segment against each edge of the other polygon.
Not sure if im on the right track or not (espeically with the [relative]velocities), or if there is a better/standard way?
Any help would be appreicated. Thanks.
I had the idea of taking each vertex in both of the polygons and calculating a line segment between the current point=(x,y) and the old point (at time when not intersecting)=(x-vx, y-vy) for each polygon, where vx and vy is the relative velocity between the two objects (ie. polyA.vx-polyB.vx, etc) and testing that line segment against each edge of the other polygon.
Not sure if im on the right track or not (espeically with the [relative]velocities), or if there is a better/standard way?
Any help would be appreicated. Thanks.
Look at Erin Catto's Box2D presentation. He presents an algorithm how to find the full contact manifold using a clipping approach.
www.gphysics.com
Basically you first identify the axis of minimum penetration which gives you the associated reference face. Next you find the incident face and clip the incidcent face against the side planes of the reference face. This is very simple and very robust. It is all there with documentation and souce so it should be fairly simple to adopt this for your problem.
He also presents a conservative advancement (CA) approach how to find the time of impact (TOI). Still you need to build the manifold at the TOI as described above. CA also considers angular velocity what might be not needed in your context. IIRC Christer Ericson has a presentation about GJK for moving objects on his site. There might also be a presentation about SAT for moving objects. Not sure though. You find the presentations here:
www.realtimecollisiondetection.net
Cheers,
-Dirk
www.gphysics.com
Basically you first identify the axis of minimum penetration which gives you the associated reference face. Next you find the incident face and clip the incidcent face against the side planes of the reference face. This is very simple and very robust. It is all there with documentation and souce so it should be fairly simple to adopt this for your problem.
He also presents a conservative advancement (CA) approach how to find the time of impact (TOI). Still you need to build the manifold at the TOI as described above. CA also considers angular velocity what might be not needed in your context. IIRC Christer Ericson has a presentation about GJK for moving objects on his site. There might also be a presentation about SAT for moving objects. Not sure though. You find the presentations here:
www.realtimecollisiondetection.net
Cheers,
-Dirk
you can just transpose the SAT with linear velocities. If you project the velocities on the separation axes, that will give you the time of impact. You need to be careful about the time intervals.
clicky.
clicky.
If you only need an approximate collision point to do some collision response you might try sampling along the line segment until it you find a point inside the other polygon. Then use binary search to improve accuracy if needed.
Author
Quote:Original post by oliii
you can just transpose the SAT with linear velocities. If you project the velocities on the separation axes, that will give you the time of impact. You need to be careful about the time intervals.
clicky.
Wow, very awesome examples and tutorial! this would have saved me days of work, haha! is it published anywhere? i'm sure there would be a ton of people who would find it useful.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
