Car-Car Collision

is that 2D? Do you use swept volumes or just calculate the overlap?

If you just use an overlap method, the only thing that would needs updating is the collision impulse.

Basically, detect all overlaps, then process overlaps one by one, no matter if it is against a wall, or another car. The only difference is the change of momentum between two cars will be different than when a car hits a wall.

If you want a more accurate algorithm, like a swept volume collisions, it a lot more complicated, but possibly not necessary for a car racing game.

The problem with the overlap method is that it''s innacurate, but many games use this method successfuly.

It''s 3D.

What my plan is, is to first check the bounding spheres so I can eliminate non-collisions, otherwise I''ll do a BB overlap.

Sound any good??

yeah, try it, it should work.

What do you plan to do when two car collides? Do you add an impulse? separate them?

Well this is my current plan:

I've got car-car collision working with BB overlap/sphere intersect test.

Currently all that happens when there is a collision is that the car that has been collided with assumes the velocity of the other car.

What I'm going to do, is calculate the change in momentum (impulse) and therefore the correct velocity. I also need to implement how the car will rotate when hit, any ideas??

Also, the way I'm calculating the BB overlap is as follows:

I loop through all 8 corners of the current car's BB, and compare it to the colliding car's min/max BB coords.
Is this a valid way of doing things??



[edited by - RavNaz on November 29, 2003 1:51:11 PM]

it''s gonna be quite innacurate, and I''m not sure if it will be very solid.

I suspect the car BBs will be oriented as well. Now, I''m in a good mood, so I''ll give you an algorithm to detect collision and generate contact infos

The test is called the separation axis test, extended to generate contact informations.

The deal with this algorithm is to detect is it exists a separation plane between the two boxes, and none of the boxes cross that plane. If you can''t find the separation plane, it means the box intersected.

The only thing you need is a function that calculates the ''span'' of the box along an axis, a bit like projecting the box ox a line and finding its extents.

for boxes against boxes, you only need to test 15 planes. The reason for this is, in short, the collisions that can happen between boxes (or convex hulls) are point-plane and edge-edge collisions. All other type of collisions (edge-plane, point-edge, point-point) are special cases of the two major cases.

first, the box structure

CBox
{
Vector P;
Vector E;
Vector X;
Vector Y;
Vector Z;
};

P is the centre
X, Y, Z are the axes of the box, taken from the orientation matrix. For an axis aligned box, X=(1, 0, 0), Y = (0, 1, 0), z = (0, 0, 1)

E is the dimensions of the box along the three axes X, Y and Z respectively.

The 15 potential separating axes for two boxes B0, B1 are

B0.X
B0.Y
B0.Z
B1.X
B1.Y
B1.Z
B0.X x B1.X
B0.X x B1.Y
B0.X x B1.Z

B0.Y x B1.X
B0.Y x B1.Y
B0.Y x B1.Z

B0.Z x B1.X
B0.Z x B1.Y
B0.Z x B1.Z

The test if two boxes are separated along one of those axes, you compute the span of both (project them onto the line), and see if the spans overlap. Spans are just two floating point values describing the dimensions of the box on those axes

{source]
void ComputSpan(CBox Box, Vector Axis, float& min, float& max)
{
float p = Axis * Box.P;
float r = fabs(Axis * Box.X) * Box.E.x + fabs(Axis * Box.Y) * Box.E.y + fabs(Axis * Box.Z) * Box.E.z;

min = p-r;
max = p+r;
}
[/source]

then to find if two spans overlap,

bool Overlap(float min0, float max0, float min1, float max1)
{
    return (min0 > max1 || max0 < min1);
}

put it together and you have

bool SpanOverlap(float min0, float max0, float min1, float max1)
{
    return !(min0 > max1 || max0 < min1);
}
void ComputSpan(Vector Axis, CBox Box, float& min, float& max)
{
    float p = Axis * Box.P;
    float r = fabs(Axis * Box.X) * Box.E.x + fabs(Axis * Box.Y) * Box.E.y + fabs(Axis * Box.Z) * Box.E.z;

    min = p-r;
    max = p+r;
}
bool AxisOverlap(Vector Axis, CBox B0, CBox B1)
{
    float min0, max0;
    float min1, max1;
    ComputeSpan(Axis, B0, min0, max0);
    ComputeSpan(Axis, B1, min1, max1);

    return SpanOverlap(min0, max0, min1, max1);
}

bool Intersect(CBox B0, CBox B1)
{
    if (!AxisOverlap(B0.X, B0, B1))
         return false;
    if (!AxisOverlap(B0.Y, B0, B1))
         return false;
    if (!AxisOverlap(B0.Z, B0, B1))
         return false;

    if (!AxisOverlap(B0.X.Cross(B1.X), B0, B1))
         return false;
    if (!AxisOverlap(B0.X.Cross(B1.Y), B0, B1))
         return false;
    if (!AxisOverlap(B0.X.Cross(B1.Z), B0, B1))
         return false;

    if (!AxisOverlap(B0.Y.Cross(B1.X), B0, B1))
         return false;
    if (!AxisOverlap(B0.Y.Cross(B1.Y), B0, B1))
         return false;
    if (!AxisOverlap(B0.Y.Cross(B1.Z), B0, B1))
         return false;

    if (!AxisOverlap(B0.Z.Cross(B1.X), B0, B1))
         return false;
    if (!AxisOverlap(B0.Z.Cross(B1.Y), B0, B1))
         return false;
    if (!AxisOverlap(B0.Z.Cross(B1.Z), B0, B1))
         return false;
   
    return true;
}

so there, the box overlap or not. This test is very solid, and very fast, even in its current optimised state (lots of unnecessary calculations).

for the contact calculations, what you can do is store each overlaps, and use the minimum overlap found as your minimum penetration axis.

bool Intersect(CBox B0, CBox B1, Vector& Normal, float& depth)
{
    float min0[15], max0[15];
    float min1[15], max1[15];
    Vector Axis[15];

    Axis[0] = B0.X;
    if (!AxisOverlap(Axis[0], B0, B1, min0[0], max0[0], min1[1], max1[1]))

// ..........

// ..........

// ..........

    depth = 1.0E8f;

    for(int = 0; i < 15; i ++)
    {
         float min = (min1[i] > min0[i])? min1[i] : min0[i];
         float max = (max1[i] < max0[i])? max1[1] : max0[i];
         
         d = max - min;

         float Alength = Axis[i].GetLength();

         if (Alength < 1.0E-8f)
             continue;

         // nromalise the penetration depth, are axes are not normalised

         d /= Alength;

         if (d < depth)
         {
             depth = d;
             Normal = Axis[i] / Alength;
         }
    }

    // make sure the normal points towards the box0

    Vector Diff = Box1.P - Box0.P;

    if (Diff * Normal > 0.0f)
        Normal *= -1.0f;

    return true;
}

and as for the impulse calculations, have a look at this

I''ve got a demo of a box bouncing on a cube, the calculations are based on the document. see below



- Oli.

---

Home

rigid body demo

Simple Z-fail Stencil shadows demo

Sphere/cube/Triangle Collision And Physics demo

swept spheres vs. raw triangles

swept spheres and AABBtree (still in development)

---

Oh my word!!!! :-)

Didn't expect this much, but WOW!! thankyou very much! Its late now, and I'm very tired, so my brain is a bit numb. The only problem I can see @ this point is that my BB's are Object Orientated, so I may have to make some alterations.

Will have a proper look at this 2morrow, but thank you again, I will let you know how I get along.

:-)

[edited by - RavNaz on November 29, 2003 7:23:58 PM]

BTW, the same algorithm works for triangle vs boxes, or triangle triangle if you want...

for box vs triangle, you need 13 axes

Tri.N
Box.X
Box.Y
Box.Z
Box.X x (Tri.E0)
Box.X x (Tri.E1)
Box.X x (Tri.E2)
Box.Y x (Tri.E0)
Box.Y x (Tri.E1)
Box.Y x (Tri.E2)
Box.Z x (Tri.E0)
Box.Z x (Tri.E1)
Box.Z x (Tri.E2)

where
E0 = Tri.V1 - Tri.V0
E1 = Tri.V2 - Tri.V1
E2 = Tri.V0 - Tri.V2

and to find the min and max

void CalcualteSpan(Vector Axis, CTriangle T, float& min, float& max)
{
    float d;

    d = T.V0 * Axis;
    min = d;
    max = d;

    d = T.V1 * Axis;
    if (d < min) min = d; else max = d;

    d = T.V2 * Axis;
    if (d < min) min = d; else max = d;
}

also, I forgot to mention, once you have to collison depth and axis, to find the contact points, you fond the 'support' points of the boxes along that axis.

you'll end up with one, two, or 4 points per box, and depending on the number of points (one versus 4, two versus two, two versus four...), you will have a point plane collisions, or a edge-edge collision, or a edge plane collision, ...

and from there you can calculate the intersection point.

to find the support points, it is very similar to finding the spans. You need the list of vertices which are max for Box0, and min for Box1. You need a list of points, as you might get a collison that could involve several points of contact.


[edited by - oliii on November 30, 2003 9:29:14 AM]

I know it's complicated, I think you'll be better off approximating a box with a collection of spheres, like 6 spheres. It's a LOT simpler.

//====================================================================================

// OVERLAP TESTS

// -------------

//

// returns where a triangle and a sphere overlap. The points returned are the points of contact.

// Same for sphere sphere overlap test. 

//

// for a triangle, test if the sphere bisect the triangle plane. if not, the sphere

// cannot intersect the triangle.

// if it is bisecting, get the closest point on the triangle to the sphere. 

// if that point is not in the sphere, it means that the triangle cannot overlap the sphere

// either, as that point was the closest. 

// if it is in the sphere, the collision point on the sphere will be the point the closest

// to the collision point on the triangle.

//====================================================================================



//----------------------------------------------------

// find closest point on the triangle to another point

//----------------------------------------------------

int FindClosestPointOnTriangle(const Vector* xV, const Vector& xN, const Vector& P, Vector& Ptri)
{
	const Vector* pV0 = xV+2;
	const Vector* pV1 = xV;

	Vector D = P - *pV0;

	for(int i = 0; i < 3; i ++)
	{
		//----------------------------------------------------

		// Edge direction and edge normal

		//----------------------------------------------------

		Vector E = *pV1 - *pV0;

		Vector En = E ^ xN; // cross product


		float d = (D * En); // dot product


		//----------------------------------------------------

		// point front facing edge normal

		//----------------------------------------------------

		if (d > 0.0f)
		{
			float t = (D * E) / (E * E);

			//----------------------------------------------------

			// closest point is Vi

			//----------------------------------------------------

			if (t < 0.0f)
			{
				Ptri = *pV0;
				return i+4;
			}
			
			//----------------------------------------------------

			// closest point is Vi+1

			//----------------------------------------------------

			if (t > 1.0f)
			{
				Ptri = *pV1;
				return i+5;
			}

			//----------------------------------------------------

			// else return closest point on segment

			//----------------------------------------------------

			Ptri = *pV0 + E * t;

			return i+1;
		}

		//----------------------------------------------------

		// move on to next edge.

		//----------------------------------------------------

		D -= E;
		pV0 = pV1;
		pV1++;
	}

	//----------------------------------------------------

	// point is inside the triangle. return the point on plane.

	// if point is already on plane, then Q = P, but 

	// it does not hurt to do a little math anyway

	//----------------------------------------------------

	float d = (P - xV[0]) * xN;

	Ptri = P - xN * d;
	
	return 0;
}


//----------------------------------------------------

// find if a sphere overlaps a triangle, and where

//----------------------------------------------------

bool TriSphereOverlap(const Vector* xV, const Vector& xN, const Vector& P, float Rad, Vector& Ptri, Vector& Psphere)
{
	//-------------------------------------------------------------------

	// distance of sphere cenrte to triangle

	//-------------------------------------------------------------------

	float dp = (P - xV[0]) * xN;

	//-------------------------------------------------------------------

	// plane back facing the sphere, don't process collision coz it's too deep

	//-------------------------------------------------------------------

	if (dp < 0.0f)
		return false;
	
	//-------------------------------------------------------------------

	// sphere too far away from plane, it does not overlap

	//-------------------------------------------------------------------

	if (dp > Rad)
		return false;

	//-------------------------------------------------------------------

	// find closest point on triangle to sphere centre

	//-------------------------------------------------------------------

	FindClosestPointOnTriangle(xV, xN, P, Ptri);

	//-------------------------------------------------------------------

	// calculate the separation vector

	//-------------------------------------------------------------------

	Vector Vseparation = (Ptri - Psphere);

	//-------------------------------------------------------------------

	// check if sphere overlaps the point on tri. If not, because the

	// point on tri is the closest to the sphere, then the sphere

	// cannot overlap the triangle, so return no collision

	//-------------------------------------------------------------------

	float s2 = Vseparation * Vseparation;
	float r2 = Rad*Rad;

	if (s2 > r2)
		return false;

	//-------------------------------------------------------------------

	// calcualte the point on sphere the closest to the point on triangle

	//-------------------------------------------------------------------

	Vseparation /= (float) sqrt(s2);
	
	Psphere = P + Vseparation * Rad;

	return true;
}



bool SphereSphereOverlap(const Vector& P1, float Rad1, const Vector& P2, float Rad2, Vector& P1sphere, Vector& P2sphere)
{
	//-------------------------------------------------------------------

	// calculate the separation vector

	//-------------------------------------------------------------------

	Vector Vseparation = (P2 - P1);

	//-------------------------------------------------------------------

	// check if the sphere centre at a distance greater than the combined radius

	//-------------------------------------------------------------------

	float Rad = Rad1 + Rad2;

	float s2 = Vseparation * Vseparation;
	float r2 = Rad*Rad;

	//-------------------------------------------------------------------

	// if so, they are not overlaping

	//-------------------------------------------------------------------

	if (s2 > r2)
		return false;

	//-------------------------------------------------------------------

	// else calcualte the collsion points

	//-------------------------------------------------------------------

	Vseparation /= (float) sqrt(s2);
	
	P1sphere = P1 + Vseparation * Rad1;
	P2sphere = P2 - Vseparation * Rad2;

	return true;
}

- Oli.

---

Home

rigid body demo

Simple Z-fail Stencil shadows demo

Sphere/cube/Triangle Collision And Physics demo

swept spheres vs. raw triangles

swept spheres and AABBtree (still in development)

---

[edited by - oliii on November 30, 2003 10:39:49 AM]

Its all wonderful to write a physics/collision system, but if you need something to do car to car collision then have a look here. The library is very speedy and free. And if you have a look at the FastCar demo they made with the library you''ll see what I mean.

http://www.oxforddynamics.co.uk/download.htm
Look under the "Free Multibody Package". FastCar Lib is also available, but it aint cheap :-)

I have found the library very easy to use - for collision and physics.

Also there are many other collision systems around. All depends if you want to write one or just use one. You will learn alot writing one, but it may take some very serious time to match some of the available collision systems - mind you that can be a very inspiring thing to do too :-)

Good luck with the car game..

true, for a physics noob, it''s the best solution.

theres also tokamak and ODE for that purpose