I'm working on a collision simulation involving a ball and a rectangle. While I've searched the forums for something similar, I've had a hard time piecing anything into my code. In particular, I'm interested not in whether a collision has occured, but at what time and the final position that the collision will occur given the ball's position and velocity and a line segment's position (probably via the endpoints). Here's what I'm trying to write:

class event {
protected:
	vect r;
	vect v;
};

class ball : protected event {
protected:
	real size;
	event contact (segment seg);
public:
	void respond (block player_block);
};

void ball::respond (block player_block) {
// PLAN (code may differ for efficiency purposes)

// 1) get expected contact events for each line

// 2) determine earliest point-of-contact (POC)

// 3) update ball position to POC

// 4) update ball velocity to reflect collision

// 5) update ball position to account for remaining dt (r += v*(dt - contact_time_for_POC))

}

I'm stuck on item 1), writing the contact() function to determine the time and place of each possible collision (ball & segment). A library suggestion would be nice but this simulation is really just a learning thing for me so math or code would really make my day. Thanks for reading! Typos and blatant disregards for the rules of English grammar are all quite intentional and were carefully thought out during the composition of this message. [edited by - n00d on April 4, 2004 9:14:15 PM]

not sure about your event class. The even class should contain a position for the point of contact, a normal for the normal of collision, and a time of collision (or I also use a negative number for penetration depth in case they are embedded).

struct CEvent{    Vector Pcoll;    Vector Ncoll;    union     {        float tcoll;        float dcoll;    };};

then you need to find the time of collision of the ball with line segments. Note that, it is important ofthe line segments are moving or not. I consider the segments having a velocity vector as well (so they could belong to a player, or a paddle for a breakout game, ...).

to test a sphere agaisnt a segment, you first test the sphere against the infinite line, and see if the point of collision on the infinite line is within the segment of not. if not, then test te end points.

that''s some code that compiles. treats the segment as an infinite line bound by two vertices. I didn''t do the overlap checks, but in truth, that should not be necessary (at first anyway).

struct CEvent{	Vector Pcoll;	Vector Ncoll;	Vector Vcoll;	union	{		float tcoll;		float dcoll;	};};struct CSegment{	Vector Vertex[2];	Vector Velocity;};struct CBall{	Vector Position;	Vector Velocity;	float  Radius;	bool Collide(const CSegment& Segment, CEvent& Event, float& tmax) const;	bool Collide(const Vector& P, const Vector& Vel, CEvent& Event, float& tmax) const;};bool CBall::Collide(const CSegment& Segment, CEvent& Event, float& tmax) const{	//-------------------------------------------------------------------------	// cache some data	//-------------------------------------------------------------------------	      Vector  V  = Velocity - Segment.Velocity; // relative velocity	const Vector& C  = Position;	const Vector& P0 = Segment.Vertex[0];	const Vector& P1 = Segment.Vertex[1];	      Vector  D  = C - P0;						// relative position	      Vector  E  = P1 - P0;						// edge	      Vector  N  = Vector(-E.y, E.x);			// normal of edge	float threshold  = 0.0f;						//1.0E-8f;// if you want to deal with overlaps		//-------------------------------------------------------------------------	// find time of collision	//-------------------------------------------------------------------------	float numer = (D * N);	if (numer < 0.0f) { numer = -numer; N = -N; }	float denom = (V * N);	if (denom >= threshold) // ball is moving away from segment	{		return false; // check for overlap?	}		float tcoll = -numer / denom;		if (tcoll < 0.0f || tcoll > tmax)		return false;	//-------------------------------------------------------------------------	// find point of collision, and see what''s collided (vertex or segment)	//-------------------------------------------------------------------------	Vector Pcoll = C + V * tcoll; // point of collsion on the line	       D = Pcoll - P0;	float e2 = (E * E);	float de = (D * E);	if (de < 0.0f) // test with start point of segment	{		return Collide(P0, Segment.Velocity, Event, tmax);	}	if (de > e2) // test with end point of segment	{		return Collide(P1, Segment.Velocity, Event, tmax);	}	//-------------------------------------------------------------------------	// segment has collided, fill in the event info	//-------------------------------------------------------------------------	N.Normalise();	Event.tcoll = tcoll;	Event.Pcoll = Pcoll;	Event.Ncoll = N;	Event.Vcoll = V;	tmax        = tcoll;	return true;}bool CBall::Collide(const Vector& P, const Vector& Vel, CEvent& Event, float& tmax) const{	//-------------------------------------------------------------------------	// cache some data	//-------------------------------------------------------------------------	Vector  D = Position - P;		// relative position	Vector  V = Velocity - Vel;		// relative velocity	float r	  = Radius;				float r2  = Radius * Radius;	const Vector& C = Position;		//-------------------------------------------------------------------------	// solve second order equation to find time of collision	//-------------------------------------------------------------------------	float a = (V * V);	float b = 2.0f * (D * V);	float c = r2 - (D * D);	if (b >= 0.0f) // ball moving away from point		return false;	// possible overlap	if (c <= 0.0f) 	{		return false; // check for overlap?	}	float d = b*b - (4 * a * c);	if (d < 0.0f)		return false;	d = (float) sqrt(d);	//-------------------------------------------------------------------------	// possible times of collision, take the first positive time	//-------------------------------------------------------------------------	float t0 = (-b - d) / (2 * a);	float t1 = (-b + d) / (2 * a);	if (t1 < t0)	{		float temp = t0;		t0 = t1;		t1 = temp;	}	float tcoll = t0;	if (t0 < 0.0f) 		tcoll = t1;	if (tcoll < 0.0f || tcoll > tmax)		return false;	//-------------------------------------------------------------------------	// the collision os valid. fill the collision event	//-------------------------------------------------------------------------	Vector Pcoll = C + V * tcoll;	Vector Ncoll = Pcoll - P;	Ncoll.Normalise();		Event.Pcoll = Pcoll;	Event.tcoll = tcoll;	Event.Ncoll = Ncoll;	Event.Vcoll = V;	tmax        = tcoll;	return true;}

operator ''*'' is a dot product.

when you have found a collision, process the event as an impact, to move the sphere away from the segment. Note that if the segment is actually moving, you have to be careful to move the sphere completely out of the way (add the paddle / player velocity to the sphere velocity, like Ball.Velocity = Event.Vcoll - (2.0f * (Event.Vcoll * Ncoll)) * Ncoll), or else, you''ll have problems. Hence, the Vcoll in the event structure.

to be more accurate, you should have a mass associated for the player, and the ball, and deal with the momentum, but at the moment, it''s assumed that the player has an infinite mass, so the ball gets all the energy.

and before processing the collision, move every objects to the time of collision (or like, 99% of the time of collision). then bounce the ball, then found another collision.

Thanks olliii--very thorough! I''ll see how it works out in my engine.

Typos and blatant disregards for the rules of English grammar are all quite intentional and were carefully thought out during the composition of this message.

dude, I should not have givenm you the code. It''s bugged like hell, and therefore pointless.

right, I got a demo working. It''s all dynamic collision tests, so the ball and paddle can move at very high speed, it still works. good for Breakout and Shufflepuck Cafe games. Grab the full demo at breakout

or mail me if you have problems getting it, or questions.