Archived

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

papa

2D polygon-polygon intersection

Recommended Posts

hi. I am looking for a fast way to detect two polygons intersecting. Could someone explain the math for me please. I am not sure if I am doing it right. Say I have T (triangle 1) & R (triangle 2) I take triangles T one edge and calculate normal vector. T.norm = crossProduct(T.b - T.a) then I know I should take a list of vertices from R (3 vertices for triangle) and test each vertex of R. I pinched some code from here : Intersection of Convex Objects: http://www.magic-software.com/Documentation/MethodOfSeparatingAxes.pdf and I dont quite understand it. Can somebody explain and correct me if I am right. According to this paper I should do the following: for( i=0 i-T.a); } Dot product returns scalar value. but is it all I need to determine if both polygons collide. Will it be valid detection when for eg. one polygon sits inside another. Because for example I wrote another test which is testing if point lies inside a poly but it doesnt work when one poly is inside another. Then my test says all points are outside but there is collision. Thats why I try to implement it as above. But I dont quite understand this method. Could someone exaplin please. Thank you. [edited by - papa on April 5, 2004 4:30:55 PM]

Share this post


Link to post
Share on other sites
dot product is simply


A.Dot(B) = A.x * B.x + A.y * B.y; // + A.z * B.z; // for 3D dot products



and yeah, you need dot products for collision tests, and obviously vector additions, substractions, and multiplications (by scalars). Which are straight forwards.

the surest, and fastest way to detect if two polygon collide or not, is the method of separation axis.

to put it simply, in 2D, for example, a triangle is defined the area inside three intersecting lines. a point is inside the triangle is the point is inside the three lines.

for polygon-polygon collision detection, you try to fit a plane that separates the two polygons. If you can find a plane (or in 2D, if you can trace a line between the two polygons), then it means that the polygons don;t intersect.

so, as you can see, there would be an infinite number of lines between two disjoint polygons. Fortunately, for triangle-triangle collision detection, you can reduce the number of lines to 6, which are the edges of the polygons themselves. To find if the edge E separates the two triangles, you find the intervals of the two triangles along that edge. if the two intervals don''t overlap, then the edge separates the two triangles, and the triangles are disjoint (don''t intersect).

for example, taking an edge (V0, V1) from triangle A, you find the intervals (or also called spans) of triangle A and B along the vector N(V0.y - V1.y, V1.x, V0.x). if the spans don;t overlap, then the edge E separates the triangles.

in code, it gives



// calculate the span (or also called interval) of a polygon along an axis N.

void CalculateSpan(const Vector& N, const Vector* V, int Vnum, float& min, float& max)
{
float d = V[0].Dot(N);
min = max = d;

for(int i = 1; i < Vnum; i ++)
{
d = V[i].Dot(N);
if (d < min) min = d; else if (d > max) max = d;
}
}

// calculate the span (or also called interval) of two polygon along an axis N, and see if the intervals overlap

bool SpanOverlap(const Vector& N, const Vector* V, int Vnum, const Vector* W, int Wnum)
{
float minv, maxv;
float minw, maxw;

CalculateSpan(N, V, Vnum, minv, maxv);
CalculateSpan(N, W, Wnum, minw, maxw);

// check if intervals overlap or not

if (minw > maxv || minv > maxw) return false;

return true;
}


// check if two polygons intersect or not

// from the separating axis algorithm, the polygons are dijoint

// if each edges separate the polygons.

// if one edge is found to separate the two polygons, then the

// polygons cannot posibly intersect.

bool PolygonIntersect(const Vector* V, int Vnum, const Vector* W, int Wnum)
{
for(int i = 0; i < Vnum; i ++)
{
// the end vertex of the edge

int j = (i+1); if (j == Vnum) j = 0;

// a vector perpendicular to the edge,

// which defines a potential separation axis

Vector N((V[i].y - V[j].y), (V[j].x - V[i].x));

// the edge separates the polygons, they are therefore disjoint

if (!SpanOverlap(N, V, Vnum, W, Wnum))
return false;
}

for(int i = 0; i < Wnum; i ++)
{
// the end vertex of the edge

int j = (i+1); if (j == Wnum) j = 0;

// a vector perpendicular to the edge,

// which defines a potential separation axis

Vector N((W[i].y - W[j].y), (W[j].x - W[i].x));

// the edge separates the polygons, they are therefore disjoint

if (!SpanOverlap(N, V, Vnum, W, Wnum))
return false;
}

// there are no possible lines that separates the triangles.

// they must intersect.

return true;
}

Share this post


Link to post
Share on other sites
"to find if the edge E separates the two triangles, you find the intervals of the two triangles along that edge"

sorry,

"To find if the edge E separates the two triangles, you find the intervals of the two triangles along a line perpendicular to the edge"

Share this post


Link to post
Share on other sites
also, you can detect the best collision line between the polygons by taking the separation axis with the minimum amount of overlap between the spans. that gives you a collision pplane, and you can bounce the objects on that plane.

2D collision demo

that''s what I use for the box-box collisions here. the algo above is a slight modification, which takes polygons with any number of vertices. As long as the polygons are convex (no angles between adjacent edges are above 180 degrees), it will work.

Share this post


Link to post
Share on other sites
Thank you Olii for your code and explanation. BTW: Nice demo.
I guess you are doing similar what the I found here: http://www.magic-software.com/Documentation/MethodOfSeparatingAxes.pdf

ie.

int WhichSide (PointSet S, Point D, Point P)
{
// S vertices are projected to the form P+t*D. Return value is +1 if all t > 0,

// -1 if all t < 0, 0 otherwise, in which case the line splits the polygon.

positive = 0; negative = 0;
for (i = 0; i < C.N; i++)
{
t = Dot(D,S.V(i)-P);
if ( t > 0 ) positive++; else if ( t < 0 ) negative++;
if ( positive && negative ) return 0;
}
return ( positive ? +1 : -1 );
}


bool TestIntersection2D (ConvexPolygon C0, ConvexPolygon C1)
{
// Test edges of C0 for separation. Because of the counterclockwise ordering,

// the projection interval for C0 is [m,0] where m <= 0. only try to determine

// if C1 is on the ‘positive’ side of the line.

for (i0 = 0, i1 = C0.N-1; i0 < C0.N; i1 = i0, i0++)
{
D = Perp(C0.V(i0) - C0.V(i1));
if ( WhichSide(C1.V,D,C0.V(i0)) > 0 )
{ // C1 is entirely on ‘positive’ side of line C0.V(i0)+t*D

return false;
}
}
// Test edges of C1 for separation. Because of the counterclockwise ordering,

// the projection interval for C1 is [m,0] where m <= 0. only try to determine

// if C0 is on the ‘positive’ side of the line.

for (i0 = 0, i1 = C1.N-1; i0 < C1.N; i1 = i0, i0++)
{
3
D = Perp(C1.V(i0) - C1.V(i1));
if ( WhichSide(C0.V,D,C1.V(i0)) > 0 )
{ // C0 is entirely on ‘positive’ side of line C1.V(i0)+t*D

return false;
}
}
return true;
}


Olii please come back in a while. I bet I will have some questions for you. Now I am going to try to understand it.

Actually I have already question. Sorry its stupid but I am so behind so I have to ask for basics too. Is it how we get cross product in 2D? which is the normal vector:
Vector N = ( a.y - b.y, b.x - a.x );

So say I have :
a=(2,2)
b=(4,4)

N.x = (2-4) = -2
N.y = (4-2) = 2

result: N = (-2,2)

If I draw this on paper it does look as it is perpendicular but when I draw it from origin to the point (-2,2). Say if I want to draw on screen the normal in the middle of the edge then how can I do it? I have to somehow translate the line dont I?
Arghhh.. I am so behind!!




[edited by - papa on April 5, 2004 5:19:42 PM]

[edited by - papa on April 5, 2004 5:21:44 PM]

Share this post


Link to post
Share on other sites
a normal is a direction vector. It's not a position vector, like a vertex on an edge. to draw a normal from an edge, you need, say the centre point on the edge, and the normal. You'll probably have to normalise it, for visualisation, but the separation axis tests do not need normalisation.


void RenderEdgeNormal(const Vector& P0, const Vector& P1)
{
Vector Mid = (P0 + P1) * 0.5f;
Vector N(P0.y - P1.y, P1.x - P0.x);

// float n_length = sqrt(N.x*N.x + N.y*N.y);

// N.x /= n_length;

// N.y /= n_length;

// normalisation is equivalent to the code above

N.Normalise();

Vector N0 = Mid;
Vector N1 = Mid + N * 5.0f; // 5.0f is the length of the normal segment to draw


glColor4f(1.0f, 1.0f, 1.0f, 1.0f);
glBegin(GL_LINES);
glVertex2fv(&N0.x);
glVertex2fv(&N1.x);
glEnd();
}


and yes, the code at Magic software is basically what I'm doing. The paper is for 3D, but for 2D, it's the same principle. The only thing that changes are the separation axis computations. The axes are different and are, the polygon plane normals, and the cross products of every edges of one polygon against the edges of the other polygon. There are some optimisations you can perform, to reduce the maths, but that can come after.

the code you have is the same thing, although they assume the polygons are already counter-clockwise, so you don't actually need to get the intervals, just make sure the polygons say on the positive half space of one the edges of the other polygon. Or the negative half space, depending if the normals are point inwards of the poly or outwards.

in 3D, you can't rely on that though (when you cross the edge, the normals can point in either direction).

[edited by - oliii on April 5, 2004 7:41:14 PM]

Share this post


Link to post
Share on other sites