Archived

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

Car-Car Collision

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

Recommended Posts

Hi Guyz, Anyone got any tips / know-how on car-car collision?? I''ve got Car to World Collision working using BoundingBox''s, and am planning on using a similar method with Car2Car. How does it change if for example you had Car2Car2Car2Wall Collision? Any help appreciated.

Share on other sites
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.

Share on other sites
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??

Share on other sites
yeah, try it, it should work.

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

Share on other sites
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]

Share on other sites
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;}

Share on other sites
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]

Share on other sites
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]

Share on other sites
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

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]

1. 1
Rutin
26
2. 2
3. 3
4. 4
5. 5

• 9
• 11
• 10
• 13
• 20
• Forum Statistics

• Total Topics
632948
• Total Posts
3009388
• Who's Online (See full list)

There are no registered users currently online

×