#### Archived

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

# 2d line intersection.....

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

## Recommended Posts

Ok, I thought I had this down pat, but it''s not working Basically, I want to use a mixture of circular and rectangular collisions in my code, so I made it that when a circle needs to be tested against a rectangle, I get the centre point of the circle, plot a line between the centre of the circle and the centr of the rectangle. I then get a point at the radius limit of the circle and this becomes the end point of a line (start at the circle centre). I then do four line intersection checks against the four sides of the rectangle. But the collision just isn''t happening I won''t give you the whole code as it gets rather messy using recursion and many checks to speed things up, but instead I''ll give you these two peices:

float x,y,xs,ys,l;
// these two lines get the vector to the second object

x=B->centreX-( A->Owner->getXPos()+A->xoffset+(A->w*0.5f) );
y=B->centreY-( A->Owner->getYPos()+A->yoffset+(A->h*0.5f) );
l=dist(x,y); // dist = distance of the vector x/y

xs=x/l;
ys=x/l;
y=radius*ys;  // get the end point

if (LineToBoxIntersect(centreX, centreY, centreX+x, centreY+y, A))
return true;



bool ACollision::LineToBoxIntersect(float ax, float ay, float bx, float by,	ACollision* box)
{
// check all four box sides vs the intersector line

float cx,cy,dx,dy;
// left side

cx=box->Owner->getXPos() + box->xoffset;
cy=box->Owner->getYPos() + box->yoffset;
dx=box->Owner->getXPos() + box->xoffset;
dy=box->Owner->getYPos() + box->yoffset + box->h;
if (LineIntersect(ax,ay,bx,by,cx,cy,dx,dy))
return true;
// right side

cx=box->Owner->getXPos() + box->xoffset + box->w;
cy=box->Owner->getYPos() + box->yoffset;
dx=box->Owner->getXPos() + box->xoffset + box->w;
dy=box->Owner->getYPos() + box->yoffset + box->h;
if (LineIntersect(ax,ay,bx,by,cx,cy,dx,dy))
return true;
// top side

cx=box->Owner->getXPos() + box->xoffset;
cy=box->Owner->getYPos() + box->yoffset;
dx=box->Owner->getXPos() + box->xoffset + box->w;
dy=box->Owner->getYPos() + box->yoffset;
if (LineIntersect(ax,ay,bx,by,cx,cy,dx,dy))
return true;
// bottom side

cx=box->Owner->getXPos() + box->xoffset;
cy=box->Owner->getYPos() + box->yoffset + box->h;
dx=box->Owner->getXPos() + box->xoffset + box->w;
dy=box->Owner->getYPos() + box->yoffset + box->h;
if (LineIntersect(ax,ay,bx,by,cx,cy,dx,dy))
return true;
return false;
}

bool ACollision::LineIntersect(float ax, float ay, float bx, float by,float cx, float cy, float dx, float dy)
{
// line intersection test

float s = (cy - dy) * (bx - ax) - (cx - dx) * (by - ay);
if (s == 0)
{
// Lines don''t intersect

return false;
}
s = ((cy - ay) * (bx - ax) - (cx - ax) * (by - ay)) / s;
if (s < 0 || s > 1)
{
// Lines don''t intersect

return false;
}
return true;
}

I know.... without knowing most of the code behind this, it gets confusing. But can anyone spot any fundamental errors with the intersection code and principle maths? The collision just doesn''t work at all

##### Share on other sites
I don''t understand your code for line2line collision, I think that the error is there, if I tried it on simple situation(
a=[1,1] b=[2,2] c=[2,1] d=1,2]) it returned that the lines doesn''t collide but they does. I suggest U to use some easier code for example something like this pseudo-code:

bool lineinline(ax,ay,bx,by,cx,cy,dx,dy)
{
if(((ax-cx)*(ax-dx))>0)return false;
if(((ay-cy)*(ay-dy))>0)return false;
if(((bx-cx)*(bx-dx))>0)return false;
if(((by-cy)*(by-dy))>0)return false;
return true
};

##### Share on other sites
I tried it with the code you suggested instead, and the ecxact same thing, no intersections at all. Perhaps the problem lies in the code where I create the first line (the one running from the centre point to the radial point)

##### Share on other sites
Okay, I''m almost there now. The collisions are happening, but there''s a small problem, they aren''t accurate completely. They are accurate for 3/4 of the collision shape, but the upper left corner of the collision seems to be comletely innacurate.

Below is a picture of what I mean. The white boxes are the two collision boxes for the player ship, the red lines indicate where the collision boundaries seem to be...

So, here''s the new code......(there''s quite a bit of it)

  bool ACollision::DoesPlayerCollide(Actor* B){	if (B->CollisionBox==NULL)		return false;	if (B->CollisionBox->Owner==NULL)		return false;	if (B->CollisionBox->colType==CT_NULL)		return false;	if (Plyr->bDying || Plyr->newLifeDelay>0.0f)		return false;	float minX1=Plyr->xpos;	float maxX1=Plyr->xpos+Plyr->w;	float minY1=Plyr->ypos;	float maxY1=Plyr->ypos+Plyr->h;	float minX2=B->getXPos();	float maxX2=B->getXPos()+B->getWidth();	float minY2=B->getYPos();	float maxY2=B->getYPos()+B->getHeight();	if (maxY1<minY2) return false;	if (minY1>maxY2) return false;	if (maxX1<minX2) return false;	if (minX1>maxX2) return false;	else	{		return AdvancedCheckPlayer(Plyr->CollisionBox, B->CollisionBox);	}	return false;}bool ACollision::AdvancedCheckPlayer(ACollision* A, ACollision* B){	// do more advanced polygonal checks for collisions	// recursion is used to check for multiple polygons per object	// if (colA collides colB)	//		return true	// else	//		if (colA->next!=NULL)	//			AdvancedCheck(colA->next, colB)	//		else	//			if (colB->next!=NULL)	//				advancedCheck(colA, colB->next)	bool bCollided=false;	if (A->colType==CT_Box && B->colType==CT_Box)	{		bCollided=true;		float minX1=Plyr->xpos+A->xoffset;		float maxX1=Plyr->xpos+A->xoffset+A->w;		float minY1=Plyr->ypos+A->yoffset;		float maxY1=Plyr->ypos+A->yoffset+A->h;		float minX2=B->Owner->getXPos()+B->xoffset;		float maxX2=B->Owner->getXPos()+B->xoffset+B->w;		float minY2=B->Owner->getYPos()+B->yoffset;		float maxY2=B->Owner->getYPos()+B->yoffset+B->h;		if (maxY1<minY2) bCollided=false;		if (minY1>maxY2) bCollided=false;		if (maxX1<minX2) bCollided=false;		if (minX1>maxX2) bCollided=false;	}	else if (A->colType==CT_Circle && B->colType==CT_Box)	{		// get point for circle A and circle A centre and do point checks		// get centre point and check		bCollided=false;		A->PreRotate();		// get directional radial point and do collision point check		float x,y,xs,ys,l;		x=( B->Owner->getXPos()+B->xoffset+(B->w*0.5f) )-A->centreX;		y=( B->Owner->getYPos()+B->yoffset+(B->h*0.5f) )-A->centreY;		l=dist(x,y);		xs=x/l;		ys=x/l;		x=radius*xs;		y=radius*ys;		if (LineToBoxIntersectPlayer(A->centreX, A->centreY, A->centreX+x, A->centreY+y, B))			return true;	}	else if (A->colType==CT_Box && B->colType==CT_Circle)	{		// do point checks by reversing B and A		bCollided=false;		B->PreRotate();		// get directional radial point and do line->box collision check		float x,y,xs,ys,l;		x=( Plyr->xpos+A->xoffset+(A->w*0.5f) )-B->centreX;		y=( Plyr->ypos+A->yoffset+(A->h*0.5f) )-B->centreY;		l=dist(x,y);		xs=x/l;		ys=x/l;		x=radius*xs;		y=radius*ys;		if (LineToBoxIntersectPlayer(B->centreX, B->centreY, B->centreX+x, B->centreY+y, A))			return true;	}	else if (A->colType==CT_Circle && B->colType==CT_Circle)	{		bCollided=false;		A->PreRotate();		B->PreRotate();		// get directional radial point and do collision point check		float x,y,l;		x=A->centreX-B->centreX;		y=A->centreY-B->centreY;		l=dist(x,y);		if (l<0.0f)			l*=-1;		if (l<(A->radius+B->radius))			return true;	}	if (bCollided)		return true;	else	{		if (A->next!=NULL)		{			bCollided=AdvancedCheckPlayer(A->next, B);			if (bCollided)				return true;		}		else if (B->next!=NULL)		{			bCollided=AdvancedCheckPlayer(Plyr->CollisionBox, B->next);			if (bCollided)				return true;		}	}	return bCollided;}

That''s the two main checking functions, that handle the recursion and general box checks. Here''s the maths side of things:

  void ACollision::PreRotate(){	// rotate the centre point around the owners rotation origins	if (Owner!=NULL)	{		baseCentreX=Owner->getXPos()+xoffset+(w*0.5f);		baseCentreY=Owner->getYPos()+yoffset+(h*0.5f);		if (Owner->drawType==DT_Rotating)		{			float r = deg2rad(Owner->rotation);			centreX=cosf(r) * (baseCentreX-Owner->rotX) - sinf(r) * (baseCentreY-Owner->rotY) + Owner->rotX;			centreY=sinf(r) * (baseCentreX-Owner->rotX) + cosf(r) * (baseCentreY-Owner->rotY) + Owner->rotY;		}		else		{			centreX=baseCentreX;			centreY=baseCentreY;		}	}	else	{		centreX=Plyr->xpos+xoffset+(w*0.5f);		centreY=Plyr->ypos+yoffset+(h*0.5f);	}}bool ACollision::LineIntersect(float ax, float ay, float bx, float by,				float cx, float cy, float dx, float dy){	// line intersection test	float s = (cy - dy) * (bx - ax) - (cx - dx) * (by - ay);	if (s == 0)	{		// Lines don''t intersect		return false;	}	s = ((cy - ay) * (bx - ax) - (cx - ax) * (by - ay)) / s;	if (s < 0 || s > 1)	{		// Lines don''t intersect		return false;	}	// tbd: use this intersection point code	//p0 = c0 + s * (d0 - c0)	//p1 = c1 + s * (d1 - c1)	return true;}bool ACollision::LineToBoxIntersectPlayer(float ax, float ay, float bx, float by,							ACollision* box){	// check all four box sides vs the intersector line	float cx,cy,dx,dy;	// left side	cx=Plyr->xpos+box->xoffset;	cy=Plyr->ypos+box->yoffset;	dx=Plyr->xpos+box->xoffset;	dy=Plyr->ypos+box->yoffset+box->h;	if (LineIntersect(ax,ay,bx,by,cx,cy,dx,dy))		return true;	// right side	cx=Plyr->xpos+box->xoffset+box->w;	cy=Plyr->ypos+box->yoffset;	dx=Plyr->xpos+box->xoffset+box->w;	dy=Plyr->ypos+box->yoffset+box->h;	if (LineIntersect(ax,ay,bx,by,cx,cy,dx,dy))		return true;	// top side	cx=Plyr->xpos+box->xoffset;	cy=Plyr->ypos+box->yoffset;	dx=Plyr->xpos+box->xoffset+box->w;	dy=Plyr->ypos+box->yoffset;	if (LineIntersect(ax,ay,bx,by,cx,cy,dx,dy))		return true;	// bottom side	cx=Plyr->xpos+box->xoffset;	cy=Plyr->ypos+box->yoffset+box->h;	dx=Plyr->xpos+box->xoffset+box->w;	dy=Plyr->ypos+box->yoffset+box->h;	if (LineIntersect(ax,ay,bx,by,cx,cy,dx,dy))		return true;	return false;}

So each object has a pointer to a collision object, and that collision object uses a linked list (via the ''next'' pointer) to the next one in the collisions list. This allows me to add as many layers of collision detail as I feel necessary. So it recurses through the collision shapes, doing the checks againt one another, but somehow, in the situation where a circular collision is striking the player (box collisions) the collision shapes go funny like in the diagram above. Box vs Box collisions work perfecty as do circle vs circle collisions. but when they mix n match it goes funny

1. 1
Rutin
44
2. 2
3. 3
4. 4
5. 5

• 11
• 9
• 12
• 10
• 13
• ### Forum Statistics

• Total Topics
632984
• Total Posts
3009710
• ### Who's Online (See full list)

There are no registered users currently online

×

## Important Information

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!