Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Samith

Point/Triangle collision in 2d

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

I need to be able to do collision detection between a circle or a point and a triangle in 2d. The only way I can think to do it is by testing if it''s on the inside of each line. The problem with that is that I don''t know how to find what the "inside" side of line is. I could store a sort of "normal" to each line in the triangle that points towards the center of the triangle, but I don''t know. Is there any kind of generally accepted point/triangle collision test? Thanks in advance, Samith.

Share this post


Link to post
Share on other sites
Advertisement
that's a good one, actually. you want to test if the sphere is on the positive (or negative) half-plane of the lines going through the edges. if you think of those lines as being actually planes that stretch through the screen, it's easier.

now, the normal of that plane (which will be also the edge normal), is simply EdgeNormal = Vector(-EdgeDir.y, EdgeDir.x).

in 3D, the edge normal of a triangle would be (EdgeDir x TriangleNormal).

anyway, to find out is a point is on the positive of negative side of a plane such as this, you simply do

float sign = (Point - PointOnPlane).Dot(PlaneNormal);

so, for an edge made of vertices V0, V1, it falls down to this

Vector EdgeDir = V1 - V0;
Vector EdgeNormal = Vector(-EdgeDir.y, EdgeDir.x);
float sign = (Point - V0).Dot(EdgeNormal);

and to find out if a point is in a triangle, you do


bool PointInPolygon(Vector Point, CPolygon Polygon)
{
for(int i = 0; i < Polygon.NumVertices; i ++)
{
Vector V0 = Polygon.V[i];
Vector V1 = Polygon.V[(i+1) % Polygon.NumVertices];
Vector EdgeDir = V1 - V0;
Vector EdgeNormal = Vector(-EdgeDir.y, EdgeDir.x);
float sign = (Point - V0).Dot(EdgeNormal);

if (sign > 0.0f) return false; // point not in polygon

}
return true; // point in polygon

}



a small optimisation. '%' is expensive. .. and of course other optimisations might follow


bool PointInPolygon(Vector Point, CPolygon Polygon)
{
int j = 2;
for(int i = 0; i < Polygon.NumVertices; j = i, i ++)
{
Vector V0 = Polygon.V[j];
Vector V1 = Polygon.V[i];
Vector EdgeDir = V1 - V0;
Vector EdgeNormal = Vector(-EdgeDir.y, EdgeDir.x);
float sign = (Point - V0).Dot(EdgeNormal);

if (sign > 0.0f) return false; // point not in polygon

}
return true; // point in polygon

}




OK, so that tells you is a point is inside a triangle or not. not very useful, for spheres, but you can base an algorithm on that.

the goal is to find the closest point on the triangle to the sphere centre. using the algorithm above, you can scan the edges, to find the closest point to the sphere centre.

once you have that point, check if that point is within the sphere's radius. if it is, there is your collision point on the triangle. Then the corresponding collision point on the sphere is trivial.

What you can do at first, is to push the sphere away from that point on the triangle so the two collision points meet.

here is an attempt at the algo, but it's untested. just to give pointers.

dot product of two vectors, by the way...

A.B = A.x*B.x + A.y*B.y;


float PointPolygonDistanceSquared(Vector Point, CPolygon Polygon, Vector& PointOnTriangle, bool& bInTriangle)
{
float mindist2 = 1.0E12f;
bInTriangle = true;
int j = 2;
for(int i = 0; i < Polygon.NumVertices; j = i, i ++)
{
Vector V0 = Polygon.V[j];
Vector V1 = Polygon.V[i];
Vector EdgeDir = V1 - V0;
Vector EdgeNormal = Vector(-EdgeDir.y, EdgeDir.x);
Vector Diff = (Point - V0);
float h2 = Diff.Dot(EdgeNormal);
float e2 = EdgeDir * EdgeDir;

if (h2 > 0.0f)
bInTriangle = false;

float t = Diff.Dot(EdgeDir) / e2;
if (t < 0.0f)
t = 0.0f;
else if (t > 1.0f)
t = 1.0f;
Vector PointOnEdge = V0 + EdgeDir * t;
Diff = PointOnEdge - Point;
float diff2 = Diff.Dot(Diff);
if (diff2 < mindist2)
{
mindist2 = diff2;
PointOnTriangle = PointOnEdge;
}
}
return mindist2;
}

bool SpherePolygonCollide(CSphere& Sphere, CPolygon Poly)
{
float r2 = Sphere.Radius * Sphere.Radius;
Vector PointOnPolygon;
bool bSphereCentreInTriangle;
float dist2 = PointPolygonDistanceSquared(Sphere.Position, Polygon, PointOnPolygon, bSphereCentreInTriangle);

if (dist2 > r2 && !bSphereCentreInTriangle)
return false;

float dist = (float) sqrt(dist2);
Vector PushVector = (PointOnPolygon - Sphere.Position);
float r = Sphere.Radius;
if (bInTriangle)
r *= 1.001f;
PushVector *= r / dist;

Sphere.Position += PushVector;
return true;
}



Now, if you can digest the maths...

[edited by - oliii on June 6, 2004 7:32:40 PM]

Share this post


Link to post
Share on other sites
Wow, it''s going to take me a while before I''m sure about what all that stuff does, but thanks a lot!

Now, one more question. This stuff you sent me is all good for discrete collision detection, but what about continuous? And instead of a sphere, it''s an AABB? My thought''s on that would be to check a line to line intersection with each line on the bounding box, if that doesn''t turn up anything, then check if the center of the box is inside the triangle, if THAT doesn''t turn up anything then there is no collision.

My only problem with that is, when you''re testing the line from the objects last position to it''s new position to see if there were any collisions on the way, is how you find the first spot that there could have been a collision. I can think of a method using some trig functions, but trig functions are really slow, and there has to be a better way.

Share this post


Link to post
Share on other sites
for CCD, first with a sphere, you just do a sphere versus each edges, and take the first collision. CCD of a sphere with a edge, is like doing a ray versus a segment ''fattened'' by the sphere radius, or called a capsule.

for a box versus a triangle, the only type of collision you''re gonna encounter will be a vertex versus an edge. edge versus edge are reduced to doing vertices against edges.

so from there, it''s quite easy. you trace each vertex of the box against the edges of the triangles, and each vertex of the triangle BACKWARDS against the stationary box. You take the first ocuring collision. If you find two vertex collisions with a time of impact very close to each other, then you can consider a edge-edge collision, if you need to.

that would work if the box and triangle are disjoint. so you can also check if they overlap beforehand, in case. The method for that is the method of the Separation Axis.

to do both at the same time, the method of the Separation Axis can be extended to do CCD as well as overlap. Check out Dave Eberly''s website for information (under source code, documentation, if I remember correctly. lots of docs).

http://www.magic-software.com

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!