Original Post
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: Any ideas how I can speed this up? [Edited by - Koobazaur on March 10, 2007 7:35:16 PM]
//==== 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;
//if not, they cannot be colliding, so go to next triangle
if(D3DXVec3Length(&Distance) > PointsRadius + CollisionRadius)
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;
}
