Slow collision detection

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

Recommended Posts

Greetings, I am working on a way to find if an object (box) intersects with my level geometry. I go about that by checking if any of the line segments making the box intersect with any of the triangles making up my level geometry; however even for a low-triangle levels (less than 2k) it turns out to be really slow, dropping my framerate from 250 to mere 40! I even tried to implement bounding spheres for the line segment and the triangle to see if the segment is even remotly close to the line, but that calculation alone also drops me to 70 fps. Here's the snippet of my code:
//==== Class cLevel ======
//checks if a segment from A to B collides with the level
bool CheckSegmentCollision(D3DXVECTOR3 A, D3DXVECTOR3 B, bool Culling=0);

vector<D3DXVECTOR3*> CollisionTri;		//the triangles defining collision bounds; each pointer is an array of 3
vector<D3DXPLANE> CollisionPlanes;		//the planes of all collision triangles
vector<D3DXVECTOR3> CollisionCenter;	//center of the collision triangle bounding sphere
//==== End Class cLevel ===

//=================================
//checks if a line segment from A to B collides with the level
//=================================
bool cLevel::CheckSegmentCollision(D3DXVECTOR3 A, D3DXVECTOR3 B, bool Culling)
{
//if no collision data, return
if(CollisionTri.empty())
return 0;

//if the two points are equal, they line between them doesn't exist
if(A == B)
return 0;

//first, we calculate the bounding sphere of the two points
D3DXVECTOR3 PointsCenter = (A + B) /2;
D3DXVECTOR3 PointsDistance = A - PointsCenter;

D3DXVECTOR3 Distance;		//distance between the bounding spheres of the points and triangle

float Plane_distance[2];	//distance from the triangle's plane for both points

//the ray of the line segment; Ray:  R(t) = Ray_start + t*Ray_u
D3DXVECTOR3 Ray_start;		//start point of the ray
D3DXVECTOR3 Ray_u;			//the u vector of ray:  ;

//find the ray that goes from A to B
CreateRayFromPoints(A, B, &Ray_start, &Ray_u);

//for each collision triangle
for(int i=0; i < CollisionTri.size(); i++)
{
//first check if the bounding spheres of the two points and our triangle collide
Distance = PointsCenter - CollisionCenter;
//if not, they cannot be colliding, so go to next triangle
continue;

//calculate the distance of each point to the plane
Plane_distance[0] = D3DXPlaneDotCoord(&CollisionPlanes, &A);
Plane_distance[1] = D3DXPlaneDotCoord(&CollisionPlanes, &B);

//now see if we two points are on the opposite sides of the plane
//if both distances are not on opposite sides, no collision!
if( !(Plane_distance[0] < 0 && Plane_distance[1] > 0) &&
!(Plane_distance[0] > 0 && Plane_distance[1] < 0) )
continue;

//now check if the ray intersects with the triangle and return 1 if so
if(RayTriangleInteresection(Ray_start, Ray_u, CollisionTri[0],CollisionTri[1],CollisionTri[2], Culling))
return 1;	// we have collision!
}

//no intersection :(
return 0;
}

//====== CreateRayFromPoints  ===========
// Creates a ray going from point A to B. The ray equation is R(t) = Start + U * t
// D3DXVECTOR3 A		- first point
// D3DXVECTOR3 B		- second point
// D3DXVECTOR3 * Start	- pointer to vector receiving the Start component for the ray
// D3DXVECTOR3 * U		- pointer receiving the U component of ray equation.
//==========================================
void CreateRayFromPoints(D3DXVECTOR3 A, D3DXVECTOR3 B, D3DXVECTOR3 * Start, D3DXVECTOR3 * U)
{
//if the pointers are empty, abort
if(Start == 0 || U == 0)
return;

//the start is just the A point
(*Start) = A;

//the ray's U is just the normalized vector from A to B
(*U) = A - B;
D3DXVec3Normalize(U, U);

return;
}

//====== RayTriangleInteresection  ===========
// Calculates if a ray intersects with a triangle
// algorith developed by Tomas Möller and Ben Trumbore
// D3DXVECTOR3 Ray_Start	- the Start component of a ray
// D3DXVECTOR3 Ray_U		- the U component of a ray
// D3DXVECTOR3 A			- the first triangle vertex
// D3DXVECTOR3 B			- the second triangle vertex
// D3DXVECTOR3 C			- the third triangle vertex
// RETURN: 1 if the ray intersects the triangle, 0 if not
//==========================================
bool RayTriangleInteresection(D3DXVECTOR3 Ray_Start, D3DXVECTOR3 Ray_U, D3DXVECTOR3 C, D3DXVECTOR3 B, D3DXVECTOR3 A, bool Culling)
{
D3DXVECTOR3 edge1, edge2, tvec, pvec, qvec;
float det, inv_det;
float u, v;

// find vectors for two edges sharing A
edge1 = B - A;
edge2 = C - A;

// begin calculating determinant - also used to calculate U parameter
D3DXVec3Cross(&pvec, &Ray_U, &edge2);

// if determinant is near zero, ray lies in plane of triangle
det = D3DXVec3Dot(&edge1, &pvec);

if(Culling)
{
if (det < KD3D9BASICS_EPSILON)
return 0;

//calculate distance from A to ray Ray_Start
tvec = Ray_Start - A;

//calculate U parameter and test bounds
u = D3DXVec3Dot(&tvec, &pvec);
if (u < 0.0f || u > det)
return 0;

// prepare to test V parameter
D3DXVec3Cross(&qvec, &tvec, &edge1);

// calculate V parameter and test bounds
v = D3DXVec3Dot(&Ray_U, &qvec);
if (v < 0.0f || u + v > det)
return 0;

}else{
if (det > -1.0f*KD3D9BASICS_EPSILON && det < KD3D9BASICS_EPSILON)
return 0;
inv_det = 1.0f / det;

// calculate distance from A to ray Ray_Startin
tvec = Ray_Start - A;

// calculate U parameter and test bounds
u = D3DXVec3Dot(&tvec, &pvec) * inv_det;
if (u < 0.0 || u > 1.0f)
return 0;

// prepare to test V parameter
D3DXVec3Cross(&qvec, &tvec, &edge1);

//calculate V parameter and test bounds
v = D3DXVec3Dot(&Ray_U, &qvec) * inv_det;
if (v < 0.0f || u + v > 1.0f)
return 0;
}
return 1;
}


Any ideas how I can speed this up? [Edited by - Koobazaur on March 10, 2007 7:35:16 PM]

Share on other sites
That's not the best way to test for triangle-box intersection. Noneless, 2K triangles is quite a lot. Look up the SAT, especially, the more optimised versions of the algo.

BTW, I would not put a bounding sphere per segment. More like, one per box. Even so, I would take the time to implement a BVH (BOunding volume hierarchy) to speed up the process. In the end, you should only have to do a maximum of around half a dozen triangles per box, not 2000.

Share on other sites
What exactly is SAT ? Googling it sends me to the collegeboard page...

I was figuring per-polygon collision detection was not the best choice, but I didn't expect it to be that slow... What is a good alternative for static level geometry?

Share on other sites
SAT=Separating Axes Theorem
Good stuff and there are many tutorials about it.
Commercial games use BSP trees for object-world and KDOP for object-static object collision.
I dont use any of those, I simply precompute everything I can about the triangles, so i dont have to do it every time (normal,edge1,edge2 etc.) .
I also store the minimum and maximum coordinates for every triangle (AABB), and that speeds up the stuff nicely (6 boolean operators vs. heavy computing).

A voxel-based approach would speed up thing heavily (storing wich triangles are in each of the 20x20x20 cubes), but it eats up memory.

I would choose BSP trees if i wouldnt be so lazy ;)

Share on other sites
I use a Compressed Axis Aligned Binary Axis Aligned Box Tree. CAABBT, or something.

as for the S.A.T., you can check out

http://www.geometrictools.com/Documentation/MethodOfSeparatingAxes.pdf

in an semi-optimised form, it goes something like this
struct Vector{	union	{		struct		{			float x,y,z;		};		struct		{			float v[3];		};	};	Vector() {}	Vector(float _x, float _y, float _z) : x(_x), y(_y), z(_z) {}	Vector(const Vector& V) : x(V.x), y(V.y), z(V.z) {}	Vector& operator += (const Vector& V) { x += V.x; y += V.y; z += V.z; return (*this); }	Vector& operator -= (const Vector& V) { x -= V.x; y -= V.y; z -= V.z; return (*this); }	Vector& operator *= (float		   k) { x *= k;   y *= k;   z *= k;   return (*this); }	Vector& operator /= (float		   k) { (*this) *= (1.0f / k);		  return (*this); }	Vector& operator ^= (const Vector& V) { (*this)  = (*this) ^ V;		  return (*this); }	Vector operator + (const Vector& V) const { return Vector(*this) += V; }	Vector operator - (const Vector& V) const { return Vector(*this) -= V; }	Vector operator * (float         k) const { return Vector(*this) *= k; }	Vector operator / (float         k) const { return Vector(*this) /= k; }	Vector operator ^ (const Vector& V) const { return Vector((y*V.z - z*V.y), (z*V.x - x*V.z), (x*V.y - y*V.x)); }	float  operator * (const Vector& V) const { return (x*V.x + y*V.y + z*V.z); }	Vector operator - ()				const { return Vector(-x, -y, -z); }		friend operator * (float k, const Vector& V) { return (*this) * k; }	float LengthSquared() const { return (*this) * (*this); }	float Length()        const { return (float) sqrt(LengthSquared()); }	float Normalise() { float l = Length(); if (l < 0.00000001f) return l; (*this) /= l; return l; }		};float fmin(float a, float b) { return (a < b)? a : b; }float fmax(float a, float b) { return (a > b)? a : b; }float fmin(float a, float b, float c) { return fmin(fmin(a, b), c); }float fmax(float a, float b, float c) { return fmax(fmax(a, b), c); }bool TriangleBoxIntersection(const Vector& V0, const Vector& V1, const Vector& V2,	// triangle vertices							 const Vector& C,										// box centre							 const Vector& A0, const Vector& A1, const Vector& A2,	// Box axes							 const float a0, const float a1, const float a2)		// box extents{	Vector E0 = V1 - V0; // triangle edge(0)	Vector E1 = V2 - V1; // triangle edge(1)	Vector E2 = V0 - V2; // triangle edge(2)	Vector N  = E0 ^ E1; // triangle normal	Vector AA0 = A0*a0; // box axis(0), scaled by box extent(0)	Vector AA1 = A1*a1; // box axis(1), scaled by box extent(1)	Vector AA2 = A2*a2; // box axis(2), scaled by box extent(2)		Vector L;	float v0, v1, v2, vmin, vmax;	float c, r;		//--------------------------------------------------	L = N;	v0 = V0 * L;	//v1 = v0; 	//v2 = v0;	vmin = vmax = v0;	c = C * L;	r = fabs(AA0 * L) + fabs(AA1 * L) + fabs(AA2 * L);	if (c-r < vmin || c+r > vmax) return false;	//--------------------------------------------------	L = A0;	v0 = V0 * L; 	v1 = V1 * L;	v2 = V2 * L;	vmin = fmin(v0, v1, v2);	vmax = fmax(v0, v1, v2);	c = C * L;	r = a0;	if (c-r < vmin || c+r > vmax) return false;	L = A1;	v0 = V0 * L; 	v1 = V1 * L;	v2 = V2 * L;	vmin = fmin(v0, v1, v2);	vmax = fmax(v0, v1, v2);	c = C * L;	r = a1;	if (c-r < vmin || c+r > vmax) return false;	L = A2;	v0 = V0 * L; 	v1 = V1 * L;	v2 = V2 * L;	vmin = fmin(v0, v1, v2);	vmax = fmax(v0, v1, v2);	c = C * L;	r = a2;	if (c-r < vmin || c+r > vmax) return false;	//--------------------------------------------------	L = A0 ^ E0;	if (L.LengthSquared() > 0.00000001f)	{		v1 = V1 * L; 		v2 = V2 * L;		//v0 = v1;		vmin = fmin(v1, v2);		vmax = fmax(v1, v2);		c = C * L;		r = fabs(AA1 * L) + fabs(AA2 * L);		if (c-r < vmin || c+r > vmax) return false;	}	L = A0 ^ E1;	if (L.LengthSquared() > 0.00000001f)	{		v2 = V2 * L; 		v0 = V0 * L;		//v1 = v2;		vmin = fmin(v2, v0);		vmax = fmax(v2, v0);		c = C * L;		r = fabs(AA1 * L) + fabs(AA2 * L);		if (c-r < vmin || c+r > vmax) return false;	}	L = A0 ^ E2;	if (L.LengthSquared() > 0.00000001f)	{		v0 = V0 * L; 		v1 = V1 * L;		//v2 = v0;		vmin = fmin(v0, v1);		vmax = fmax(v0, v1);		c = C * L;		r = fabs(AA1 * L) + fabs(AA2 * L);		if (c-r < vmin || c+r > vmax) return false;	}	//--------------------------------------------------	L = A1 ^ E0;	if (L.LengthSquared() > 0.00000001f)	{		v1 = V1 * L; 		v2 = V2 * L;		//v0 = v1;		vmin = fmin(v1, v2);		vmax = fmax(v1, v2);		c = C * L;		r = fabs(AA0 * L) + fabs(AA2 * L);		if (c-r < vmin || c+r > vmax) return false;	}	L = A1 ^ E1;	if (L.LengthSquared() > 0.00000001f)	{		v2 = V2 * L; 		v0 = V0 * L;		//v1 = v2;		vmin = fmin(v2, v0);		vmax = fmax(v2, v0);		c = C * L;		r = fabs(AA0 * L) + fabs(AA2 * L);		if (c-r < vmin || c+r > vmax) return false;	}	L = A1 ^ E2;	if (L.LengthSquared() > 0.00000001f)	{		v0 = V0 * L; 		v1 = V1 * L;		//v2 = v0;		vmin = fmin(v0, v1);		vmax = fmax(v0, v1);		c = C * L;		r = fabs(AA0 * L) + fabs(AA2 * L);		if (c-r < vmin || c+r > vmax) return false;	}	//--------------------------------------------------	L = A2 ^ E0;	if (L.LengthSquared() > 0.00000001f)	{		v1 = V1 * L; 		v2 = V2 * L;		//v0 = v1;		vmin = fmin(v1, v2);		vmax = fmax(v1, v2);		c = C * L;		r = fabs(AA0 * L) + fabs(AA1 * L);		if (c-r < vmin || c+r > vmax) return false;	}	L = A2 ^ E1;	if (L.LengthSquared() > 0.00000001f)	{		v2 = V2 * L; 		v0 = V0 * L;		//v1 = v2;		vmin = fmin(v2, v0);		vmax = fmax(v2, v0);		c = C * L;		r = fabs(AA0 * L) + fabs(AA1 * L);		if (c-r < vmin || c+r > vmax) return false;	}	L = A2 ^ E2;	if (L.LengthSquared() > 0.00000001f)	{		v0 = V0 * L; 		v1 = V1 * L;		//v2 = v0;		vmin = fmin(v0, v1);		vmax = fmax(v0, v1);		c = C * L;		r = fabs(AA0 * L) + fabs(AA1 * L);		if (c-r < vmin || c+r > vmax) return false;	}	return true;}

Share on other sites
Okay I just have made KDtrees last night, and the results are really good. It made a 10x speedup.

KDTrees are relatively easy. 100 lines of (pascal) code constructing it, and 50 lines of (pascal again) code, to test, which triangles to consider in the collision detection. This means that you only have to test 10-20 KDTree nodes (basically AABBs) and 4-8 triangles. Definately faster than testing 20K tris.

Share on other sites
You could try building a collision map and traversing through that. If your world is made of of connecting triangles, store the connecting edges of each triangle. Then store which triangle each dynamic object is on when they are initialised. Then each frame from where they were last frame navigate your tree of triangles to see where they are now.

This technique is using whats called 'temporal coherence'. Ie using knowledge from the previous frame to find out where they are the current frame. the most efficient method.

1. 1
2. 2
3. 3
Rutin
20
4. 4
frob
19
5. 5

• 32
• 13
• 10
• 11
• 9
• Forum Statistics

• Total Topics
632561
• Total Posts
3007088

×