Line to Line intersection not working.

[2NywAqkS]

I am trying to do some bullet collision detection in a platform game. I want this to be continuous collision detection so my method is
1. To represent a bullet as a line segment between its current position and its previous position.
2. Players are represented a box of 4 line segment.
3. Do four line-to-line intersection tests for the bullet's line and the four sides of the player's box.

This logic seems sound to me, however it's the line-to-line intersection test I think isn't working. The in-game result are completely wrong.

Here's some source:

// The line-to-line intersection test
bool LLIntersection(Vector p1, Vector p2, Vector p3, Vector p4)
{
	// Store the values for fast access and easy
	// equations-to-code conversion
	double x1 = p1.x, x2 = p2.x, x3 = p3.x, x4 = p4.x;
	double y1 = p1.y, y2 = p2.y, y3 = p3.y, y4 = p4.y;
 
	double d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
	// If d is zero, there is no intersection
	if (d == 0.0) return false;
 
	// Get the x and y
	double pre = (x1*y2 - y1*x2), post = (x3*y4 - y3*x4);
	double x = ( pre * (x3 - x4) - (x1 - x2) * post ) / d;
	double y = ( pre * (y3 - y4) - (y1 - y2) * post ) / d;
 
	// Check if the x and y coordinates are within both lines
	if ( x < std::min(x1, x2) || x > std::max(x1, x2) || x < std::min(x3, x4) || x > std::max(x3, x4) ) return false;
	if ( y < std::min(y1, y2) || y > std::max(y1, y2) || y < std::min(y3, y4) || y > std::max(y3, y4) ) return false;

	return true;
}

// The box-to-line intersection test
bool LBIntersection(Vector p1, Vector p2, double x1, double y1, double x2, double y2)
{
	Vector p3, p4, p5, p6;
	p3.x = x1, p4.x = x2, p5.x = x2, p6.x = x1;
	p3.y = y1, p4.y = y1, p5.y = y2, p6.y = y2;
	// Check each side of the box
	if(LLIntersection(p1, p2, p3, p4)) return true;
	if(LLIntersection(p1, p2, p4, p5)) return true;
	if(LLIntersection(p1, p2, p5, p6)) return true;
	if(LLIntersection(p1, p2, p6, p3)) return true;
	return false;
}

// The code in the collision detection loop
LBIntersection(bulletPtr->position, bulletPtr->lastPosition, playerPtr->position.x - 10.0, playerPtr->position.y - 16.0, playerPtr->position.x + 10.0, playerPtr->position.y + 16.0)

[Disch]

You probably should try testing LLIntersection on its own to make sure it works, before using it in LBIntersection. That way you're more likely to find the problem.

That said... I'm not sure I follow how the calculations you use to acquire 'x' and 'y' (the collision point) are supposed to work. When I do this I usually take the vector representing the line segment, rather than working with the endpoints of the line.

I can't tell you how to fix your routine... but I can give you the one I use... which I know for a fact works:

//! Returns the perpendicular dot product given two vectors
inline double dot(const Vector& a, const Vector& b) { return (a.x*b.x) + (a.y*b.y); }

//! Returns the perpendicular dot product given two vectors
inline double perpDot(const Vector& a, const Vector& b) { return (a.y*b.x) - (a.x*b.y); }


/*! Detects if two line segments intersect.
    \returns true if the lines intersect.  false otherwise.
    \remarks Two line segments are formed.  One with given vectors A and B, and another with vectors C and D.
    If the lines intersect, the out param is filled with the point, scaled to range [0..1], along line CD
    that the intersection occurred.  The exact point of intersection can be obtained with
    C + out*(D-C).
    */
bool lineCollision( const Vector& A, const Vector& B,
                    const Vector& C, const Vector& D,
                    double* out )
{
    Vector vBA(B - A);
    Vector vDC(D - C);

    double f = perpDot(vDC,vBA);
    if(!f)      // lines are parallel
        return false;
    
    Vector vCA(C - A);
    double k = perpDot(vDC,vCA) / f;
    if(k <  0)          return false;
    if(k >= 1)          return false;

    double m = perpDot(vBA,vCA) / f;
    if(m <  0)          return false;
    if(m >= 1)          return false;

    if(out)
        *out = m;

    return true;
}

[2NywAqkS]

I'm not trying to find any collision point, just a boolean value for whether there is a collision or not. Anyway I'll try out your method and see if I have any-more luck.

[2NywAqkS]

Still not working...
It must be something else. I'll continue trying to debug.

[2NywAqkS]

Ok, so I've fixed it now. Turns out it was a dumb-ass mistake I'd made elsewhere in the code.
Sorry for time-wasting and thanks Disch for your support
-Rowan