Closest Point on Polygon Boundry
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?
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!
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 pigignorance I've come to expect from you noncreative garbage."
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 nonelastic 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.
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 nonelastic 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.
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 lineline distance checks. It gets a bit trickier, but is doable
[edit] This is a good source for and tutorial for 2D collision detection stuff:
http://www.harveycartel.org/metanet/tuto...rialA.html
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 lineline distance checks. It gets a bit trickier, but is doable
[edit] 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  9,858 
Aug 28, 2009 08:12 AM Last Post: mikey 

2D Polygon intersection testing  unknown  6  7,896 
Aug 15, 2006 04:17 PM Last Post: unknown 