Sign in to follow this  

2d line intersection collision detection

This topic is 4688 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

Hey, I'm writing a breakout app and trying to get 2d collision detection working. The app is in opengl and i'm writing it on linux. Here's my collision method that doesn't seem to be quite working. I use a generic graphical object class which I run through all the objects on the screen to see if there are any collisions. I got the algorithm for line intersection from HERE For the rest of the code see http://www.vrac.iastate.edu/~stett/breakout.tar.gz Code fragment below --------
bool collision( int index ) {
  // run through all objects
  for( int i = 0; i < mSize; i++ ) {
    // don't check if an obj collides with itself
    if( i != index ) {
      // run through this obj's vertices
      int kVerts = mObjs[i]->numVerts( );

      for( int k = 0; k < kVerts; k++ ) {
	int kPlusOne  = k + 1;

	Vertex a = *(mObjs[index]->getCenter());
	gmtl::Vec2f vel = mObjs[index]->getVelocity( );
	Vertex b( vel[0]+a[0], vel[1]+a[1] );
	Vertex c = mObjs[i]->getVertices( k );
	if( k == kVerts ) kPlusOne = 0; // circularity of verts
	Vertex d = mObjs[i]->getVertices( kPlusOne );

	assert( !(c == d) || !(a == b)); // don't want a non-dimensional 

	/*
	 * If AB & CD intersect, then
	 *
	 *    A+r(B-A)=C+s(D-C) for some r,s in [0,1]
	 *
	 *    OR:
	 *
	 *    Ax+r(Bx-Ax)=Cx+s(Dx-Cx)
	 *    Ay+r(By-Ay)=Cy+s(Dy-Cy)  for some r,s in [0,1]
	 */

	/*
	 *     (Ay-Cy)(Dx-Cx)-(Ax-Cx)(Dy-Cy)
	 * r = -----------------------------  (eqn 1)
	 *     (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)
	 */
	float denom = (b[0]-a[0]) * (d[1]-c[1]) - (b[1]-a[1]) * (d[0]-c[0]);
	if( denom == 0 ) continue; //lines are parallel
	float r = ( ((a[1]-c[1]) * (d[0]-c[0]) - (a[0]-c[0]) * (d[1]-c[1])) /
		    denom );
	/*
	 *     (Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay)
	 * s = -----------------------------  (eqn 2)
	 *     (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)
	 */
	float s = ( ((a[1]-c[1]) * (b[0]-a[0]) - (a[0]-c[0]) * (b[1]-a[1])) /
		    denom );
	/*
	 * If 0<=r<=1 & 0<=s<=1, intersection exists
	 * r<0 or r>1 or s<0 or s>1 line segments do not intersect
	 */
	if( r < 0 || r > 1 || s < 0 || s > 1 )
	  continue;
	/*
	 * Px=Ax+r(Bx-Ax)
	 * Py=Ay+r(By-Ay)
	 */
	Vertex p( a[0] + r *( b[0] - a[0]),
		  a[1] + r *( b[1] - a[1]) );

	normal = mObjs[i]->getNormal( c, d );
	return true;

	}
    }
  }
  return false;
}
------ End code. [Edited by - discostu on February 12, 2005 8:55:11 PM]

Share this post


Link to post
Share on other sites
I looked at the code, but it would take (me at least) a while to determine if there are any bugs in it.

2D line intersection has been discussed a lot lately, and the solution most people seem to be using is the one you present here, i.e. solving for the intersection of the (infinite) lines that contain the segments, and seeing if the intersection point falls within the segments.

IMO there is a faster and probably more robust way to perform this particular intersection test. Given a point p and a line segment s, you can find the (scaled) distance from p to s like this:

float dist = s.direction.PerpDot(p - s.origin);

Setting aside colinear cases for now, if two line segments intersect, for each segment its endpoints will be on opposite sides of the line supporting the other segment. Therefore, if both endpoints of seg 1 are on the same side of seg 2, there is no intersection. Likewise the other way around. This allows most (nonintersecting) tests to exit after just a couple perp dots - much cheaper than the solution posted above.

If the segments are found to intersect, the intersection point can easily be found using the ratio of the distances from either segment's endpoints to the other segment's supporting line. You've already calculated these, so the intersection point is found at little cost.

That leaves colinear segments. Whether it's important to handle these cases is application-dependent, but they certainly can be handled. In one of my implementations of this test, I think about 85% of the code dealt with the colinear case :-)

Anyway, i think this method is better than the line intersection method, and I'm surprised that that's what most people's google searches turn up.

Anyway, I know I didn't really answer your question, but the algorithm you're using is a little hard to debug (there are a lot of terms to get right).

Share this post


Link to post
Share on other sites
Yea it is hard to debug. I'm sure I have the equations right. I've looked over and over them again. I had some problems with the vector data structures I'm using to store the vertices that make up the objects. Anyway I changed them to pointer arrays and now it mostly works.

It's detecting collisions when the ball bounces off of the walls and reflecting correctly. The only problem is it is also detecting collisions where there are none occasionally in the middle of the screen and changing its velocity.

Thanks.

It probably still has something to do with the data structure cause I tell it to output C and D from the alg. everytime (these are the vertices that make up the line segment of the colliding edge.)

c: (0,470); d: (640,470) <-- this one's ok
c: (630,480); d: (7.9874e-44,5.60519e-45) <-- this one has a bad val for d

EDIT : nevermind I fixed it.
if( k == kVerts ) kPlusOne = 0; // circularity of verts should be
if( k == (kVerts-1) ) kPlusOne = 0; // circularity of verts

Share this post


Link to post
Share on other sites

This topic is 4688 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this