## Closest Point on Polygon Boundry

Sage
Posts: 1,403
Joined: 2005.07
Post: #1
Im trying to get some collision response now, but it requires some information I dont have or know how to calculate,

I can detect the collision fine, but I need to get a point of collision and a normal. I've thought about various ways to do this but most of them would be quite likely to produce bad results or very slow.

I have two points in time, just before the collision occurred and just after. Im thinking now of going to the time just before the collision like this:

and then attempting to find two points, one on the boundary of each polygon, such that the two points are the closest possible, I can use the vector from one point to the other as the normal (blue), and the midpoint (red) as the point the collision occurred.

Just now I imagine I would have to go through each point on polygon A and find the minimum distance to each line on polygon B and taking the minimum one. I guess that would get really slow when a polygon with lots of edges collides multiple times per frame.

Does anyone know of a better way of finding the point and normal (given two intersecting or non intersection polygons composed of triangles) or a fast algorithm to find the two points like I was describing?

Sir, e^iÏ€ + 1 = 0, hence God exists; reply!
Moderator
Posts: 529
Joined: 2003.03
Post: #2
unknown Wrote:Just now I imagine I would have to go through each point on polygon A and find the minimum distance to each line on polygon B and taking the minimum one. I guess that would get really slow when a polygon with lots of edges collides multiple times per frame.

Would you really have to compare to every line? You already know which ones collided.

"Yes, well, that's the sort of blinkered, Philistine pig-ignorance I've come to expect from you non-creative garbage."
Sage
Posts: 1,487
Joined: 2002.09
Post: #3
I don't remember exactly what they are called, but when creating your poly regions, you can create a bitmap with the normal and distance information in it. It doesn't even need to be full resolution as you can interpolate to get a decent approximation.

When looking for the collision point, you simply poll the vertices in one poly against the map of the other. I've never used this myself as I only handle convex polys, but it sounds interesting.

What I do to approximate collision points is simply to use the current positions of the predicted penetrating vertices in the next time step. If you want a good non-elastic collision, you may need more than one. That works as a good approximation as long as things aren't moving to fast, otherwise you can get some screwy rotation.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Member
Posts: 26
Joined: 2006.09
Post: #4
The easiest way to detect the collision between a circle and edge is to calculate the distance between the edge and the point. That will handle all cases nicely, even the corners. The direction from the center of the collider to the nearest point on edge is the normal of the collision.

Since you can operate on the level of edges, it does not matter if you have holes in the polygons or not. Just make sure your polygons are winded correctly, that allows you to do "backface culling". If the dot product of the direction from your collider to the edge with the normal of the edge is negative, you can skip the edge. The normal of the edge is perproduct of the direction of the edge (that is, either (y, -x) or (-y, x) depending on the winding order). Another way to speed it up is to fist check if the point is inside the AABB of the shape (of course you have to pad the bbox with the radius of the collider, or check AABB vs. AABB),

Here's code to calculte the nearest point. I'm not 100% sure it works, I was unable to test it.

Vec2 NearestPointOnSegment(const Vec2& pt, const Vec2& p0, const Vec2& p1)
{
Vec2 dir = p1 - p0;
float len = Dot(dir, dir);
if(len < EPSILON) return p0; // Zero len segment.
Vec2 diff = pt - p0;
float u = Dot(dir, diff);

u /= len;

if (u > 0.0f)
{
if (u < 1.0f)
return p0 + u * dir;
else
return p1;
}
else
return p0;
}

If you want to test a (fast) moving object, you can use line-line distance checks. It gets a bit trickier, but is doable

 This is a good source for and tutorial for 2D collision detection stuff:
http://www.harveycartel.org/metanet/tuto...rialA.html

Possibly Related Threads...
 Thread: Author Replies: Views: Last Post Finding the closest point to (x1,y1) in array of [x1,y1,z1,x2... mikey 17 13,147 Aug 28, 2009 08:12 AM Last Post: mikey 2D Polygon intersection testing unknown 6 9,385 Aug 15, 2006 04:17 PM Last Post: unknown