Collision detection very slow :S

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

Recommended Posts

Hi folks, I have been busy with a collision detectionsystem for my racing game adn for now it works kinda(It does not work perfectly and just returns true for the collision at moment i think it is not collided yet (but close). Also it is too slow at the moment and I would like to get some input from you guys about my implementation, please give all the feedback, correction you can even if it is all carbage and i should rewrite it. every line to speed it up is welcome. here is the main code for the collision:
void SingleRace::HandleGameEvents() {
player->Handle();

// check which kind of block i am :D
// get my blockplace.
player->BlockOldPosition.x = player->BlockPosition.x;
player->BlockOldPosition.y = player->BlockPosition.y;
player->BlockPosition.x = (int)floor(-(player->getPosition().x - (0.5f*BLOCKSIZE)) / BLOCKSIZE);
player->BlockPosition.y = (int)floor(-(player->getPosition().z - (0.5f*BLOCKSIZE)) / BLOCKSIZE);

//get the current trackpart
if(player->BlockPosition.x != player->BlockOldPosition.x || player->BlockPosition.y != player->BlockOldPosition.y) {
currentPart = NULL;
currentPart = Track->at(player->BlockPosition.y)->at(player->BlockPosition.x);
}

// do some collision detection
if(currentPart != NULL){

if (CheckIntersectionBetweenTwoObjects(player->getObjPlane(), currentPart->getObj(), player->getPosition(), currentPart->getPosition(), player->getRoll())) {
// reset the plane
player->setToOldPosition();
}
}

}
at the moment I do nothing only place the player back to it original position if collision is detected. here is the other needed code:
bool CheckForIntersection(ScePspFVector3 v1, ScePspFVector3 v2, ScePspFVector3 v3, ScePspFVector3 u1, ScePspFVector3 u2, ScePspFVector3 u3) {

ScePspFVector3 planePartEquation1, planePartEquation2, Normal1, Normal2, directionVec;

// creating the plane equation.
planePartEquation1 = Vector3D::Substract(v2, v1);
planePartEquation2 = Vector3D::Substract(v3, v1);
Normal1 = Vector3D::CrossProduct(planePartEquation1, planePartEquation2);
float distance1 = -(Vector3D::DotProduct(Normal1, v1));

//checking u's against the plane equation.
float distanceU1 = Vector3D::DotProduct(Normal1, u1) + distance1;
float distanceU2 = Vector3D::DotProduct(Normal1, u2) + distance1;
float distanceU3 = Vector3D::DotProduct(Normal1, u3) + distance1;

//check to see if they are on 1 side.
float u12 = distanceU1 * distanceU2;
float u13 = distanceU1 * distanceU3;
if(u12>0.0f && u13 > 0.0f)
return false;					// no intersection

// creating the plane equation.
planePartEquation1 = Vector3D::Substract(u2, u1);
planePartEquation2 = Vector3D::Substract(u3, u1);
Normal2 = Vector3D::CrossProduct(planePartEquation1, planePartEquation2);
float distance2 = -(Vector3D::DotProduct(Normal2, u1));

//checking u's against the plane equation.
float distanceV1 = Vector3D::DotProduct(Normal2, v1) + distance2;
float distanceV2 = Vector3D::DotProduct(Normal2, v2) + distance2;
float distanceV3 = Vector3D::DotProduct(Normal2, v3) + distance2;

//check to see if they are on 1 side.
float v12 = distanceV1 * distanceV2;
float v13 = distanceV1 * distanceV3;
if(v12>0.0f && v13 > 0.0f)
return false;					// no intersection

// compute the direction of intersection.
directionVec = Vector3D::CrossProduct(Normal1, Normal2);

// compute the largest component of the vector.
float max = fabs(directionVec.x);
int index = 0;
float bb = fabs(directionVec.y);
float cc = fabs(directionVec.z);
if(bb>max) { max = bb; index = 1; }
if(cc>max) { max = cc; index = 2; }

// simplified projection onto L

float vp1 = 0.0f, vp2 = 0.0f, vp3 = 0.0f, up1 = 0.0f, up2 = 0.0f, up3 = 0.0f;

if(index==1) {
vp1 = v1.x; vp2 = v2.x; vp3 = v3.x;
up1 = u1.x; up2 = u2.x; up3 = v3.x;
}
else if(index==2) {
vp1 = v1.y; vp2 = v2.y; vp3 = v3.y;
up1 = u1.y; up2 = u2.y; up3 = v3.y;
}
else if(index==3) {
vp1 = v1.z; vp2 = v2.z; vp3 = v3.z;
up1 = u1.z; up2 = u2.z; up3 = v3.z;
}

float a, b, c, d, e, f, x1, x2, y1, y2;

// compute interval for triangle 1 and 2
if(!Vector3D::ComputeInterval(vp1, vp2, vp3, distanceV1, distanceV2, distanceV3, v12, v13, a, b, c, x1, x2)) return false;
if(!Vector3D::ComputeInterval(up1, up2, up3, distanceU1, distanceU2, distanceU3, u12, u13, d, e, f, y1, y2)) return false;

float xx, yy, xxyy, tmp;
ScePspFVector2 isect1, isect2;

xx = x1 * x2;
yy = y1 * y2;
xxyy = xx * yy;

tmp = a * xxyy;

isect1.x=tmp+b*x2*yy;
isect1.y=tmp+c*x1*yy;

tmp = d * xxyy;
isect2.x=tmp+e*xx*y2;
isect2.y=tmp+f*xx*y1;

if(isect1.x > isect1.y){
tmp = isect1.x;
isect1.x = isect1.y;
isect1.y = tmp;
}
if(isect2.x > isect2.y){
tmp = isect2.x;
isect2.x = isect2.y;
isect2.y = tmp;
}

if(isect1.y<isect2.x || isect2.y<isect1.x) return false;

return true;
};

bool CheckIntersectionBetweenTwoObjects(Obj* obj1, Obj* obj2, const ScePspFVector3& pos1, const ScePspFVector3& pos2, float yaw) {

ObjColFace* face1;
ObjColFace* face2;

obj1->AlterCollisionFaces(pos1, pos2, yaw);

for(int i=0;i<obj1->TotalCollisionTriangles() - 1;i++) {
for(int j=0;j<obj2->TotalCollisionTriangles() - 1;j++) {
face1 = obj1->getCollisionFaceAltered(i);
face2 = obj2->getCollisionFace(j);
//DebugTools::PrintText("Tjah ff kijken hoor...\n");
if (CheckForIntersection(face1->vertices[0], face1->vertices[1], face1->vertices[2], face2->vertices[0], face2->vertices[1], face2->vertices[2]))
return true;
}
}

return false;
}
and the functions of the object as last:
	void Obj::AlterCollisionFaces(const ScePspFVector3& posOwn, const ScePspFVector3& posOther, float yaw) {
unsigned int indx;
for (indx = 0; indx < collisionFacesAltered.size(); indx++) {
// y = z because the y is up and down and the coordinates are 2d so y becomes z.
// first rotate this object
collisionFacesAltered[indx]->vertices[0].x = collisionFaces[indx]->vertices[0].z * sin(yaw) + collisionFaces[indx]->vertices[0].x * cos(yaw);
collisionFacesAltered[indx]->vertices[1].x = collisionFaces[indx]->vertices[1].z * sin(yaw) + collisionFaces[indx]->vertices[1].x * cos(yaw);
collisionFacesAltered[indx]->vertices[2].x = collisionFaces[indx]->vertices[2].z * sin(yaw) + collisionFaces[indx]->vertices[2].x * cos(yaw);

collisionFacesAltered[indx]->vertices[0].z = collisionFaces[indx]->vertices[0].z * cos(yaw) - collisionFaces[indx]->vertices[0].x * sin(yaw);
collisionFacesAltered[indx]->vertices[1].z = collisionFaces[indx]->vertices[1].z * cos(yaw) - collisionFaces[indx]->vertices[1].x * sin(yaw);
collisionFacesAltered[indx]->vertices[2].z = collisionFaces[indx]->vertices[2].z * cos(yaw) - collisionFaces[indx]->vertices[2].x * sin(yaw);

// then translate
collisionFacesAltered[indx]->vertices[0].x = collisionFaces[indx]->vertices[0].x + -posOwn.x - posOther.x;
collisionFacesAltered[indx]->vertices[1].x = collisionFaces[indx]->vertices[1].x + -posOwn.x - posOther.x;
collisionFacesAltered[indx]->vertices[2].x = collisionFaces[indx]->vertices[2].x + -posOwn.x - posOther.x;
collisionFacesAltered[indx]->vertices[0].y = collisionFaces[indx]->vertices[0].y + -posOwn.y - posOther.y;
collisionFacesAltered[indx]->vertices[1].y = collisionFaces[indx]->vertices[1].y + -posOwn.y - posOther.y;
collisionFacesAltered[indx]->vertices[2].y = collisionFaces[indx]->vertices[2].y + -posOwn.y - posOther.y;
collisionFacesAltered[indx]->vertices[0].z = collisionFaces[indx]->vertices[0].z + -posOwn.z - posOther.z;
collisionFacesAltered[indx]->vertices[1].z = collisionFaces[indx]->vertices[1].z + -posOwn.z - posOther.z;
collisionFacesAltered[indx]->vertices[2].z = collisionFaces[indx]->vertices[2].z + -posOwn.z - posOther.z;
}
}
I hope you guys can give me some pointers or better ways of doing stuff. hope to get alot of feedback !!!! thanks in advance

Share on other sites
Are you doing a bounding volume to bounding volume collision check before the triangle-to-triangle collision detection? If not, I suggest you look into using collision detection with AABB's or spheres. It will give you a HUGE speed boost.

Share on other sites
Well I don't know if it would make a difference but I'll hope you can tell me if it would. My track consists of parts, every part has around 32 vertices on which collision will be detected with the player. Instead of the 40-100 trackparts I only check collision with the trackpart the player is on.

Share on other sites
It would help me to help you if I had a visual of what a typical piece of track looked like. if the track is straight, then you can template a lot of the collisions without ever doing a polygon check. if the track is curved, then you can use a radius check for the inner and outer wall. Break things down into planes basically.

as far as the XZ plane goes, a straight peice of track would have a linear equation representing the middle, and the -B value would be the distance from that center to a wall, where the B value would be the other wall. good old y=mx+b.

on a curved peice of track, you know where the center of the arc is. a short radius tells you how close the inner wall is, and a long radius tells you how far away the outer wall is.

for the Y axis then, all you have to do is check the ground for it's y value. if the ground value is higher then the vehicle y value, then force the vehicle to that absolute value, compress the shocks based on the refracted force, mess with the tire grip, etc.

so yeah, the biggest improvement you could do, is look at your track in a linear and curved fashion.

if B=0 is the middle of the straight track, -20 is one wall, and 20 is the other wall. if your B value is < -20 or > 20, then you hit one of the walls.

if R=10 is the inner arc, and R=50 is the outer arc. if your R value is < 10 or > 50, then you hit one of the walls.

any parts of the track that are non-movable, and wouldn't fit within a series of linear or curved equations, use the boxing method check first before polygon checking them.

hope that helped. And again, a picture of a sample track would help me to understand your needs more.