Archived

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

Damocles

2d line intersection.....

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;
x=radius*xs;
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 this post


Link to post
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
};

Glubo The Mad

Share this post


Link to post
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 this post


Link to post
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

Share this post


Link to post
Share on other sites