Sign in to follow this  
Koobazaur

Slow collision detection

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
vector<float> CollisionRadius;			//radius 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;
 float PointsRadius = D3DXVec3Length(&PointsDistance);

 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[i];
	//if not, they cannot be colliding, so go to next triangle
	if(D3DXVec3Length(&Distance) > PointsRadius + CollisionRadius[i])
		continue;


	//calculate the distance of each point to the plane
	Plane_distance[0] = D3DXPlaneDotCoord(&CollisionPlanes[i], &A);
	Plane_distance[1] = D3DXPlaneDotCoord(&CollisionPlanes[i], &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[i][0],CollisionTri[i][1],CollisionTri[i][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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

I recommend to [google] it.

Share this post


Link to post
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this