05-21-2000, 09:01 AM

I need help coding for collision detection. Can someone please help me? thanks

View Full Version : Collision Detection?

05-21-2000, 09:01 AM

I need help coding for collision detection. Can someone please help me? thanks

Glenn Upton

05-21-2000, 08:42 PM

Lots of stuff on this here website, also gamasutra. None of it is simple tho.

05-22-2000, 06:30 AM

This is the way I did it for a project, but it seems pretty complicated. There's probably an easier way (and if anybody knows one for convex polygon perfect collision detection, I'm all ears...)

In my project, I didn't want any polygon from one object to intersect any polygons from the other objects in the scene. This was accomplished by making sure no line segment of any polygon from one object intersected any polygon from the other object.

1) First I test whether the line intersects the polygons plane. This is not required, but speeds up things a bit. I test if both points of the line are on the left, or if both points are on the right (using dot product, see crappy code below). Exit with no collision if true.

2)Then I determined the x,y,z coords of the intersection of the plane, by changing into parametric equations and getting the t value for this.

3)Now, is this point in the polygon? Picture it in the center. If you draw a line segment from this point to a point on the polygon, then swoop it around to every other point in order, you should go 360 degrees. However, outside the polygon, you should get less than this. So, add up all the angles I mentioned. If it is between 359 and 361, assume your line has intersected your polygon.

Here's some code, hope it's not too bad http://www.opengl.org/discussion_boards/ubb/smile.gif

//determines if line intersects triangle

//code might be hard to understand

int detLineCol(vector *plane, vector *line)

{

vector normal,intersectionP;

GLfloat t,angleSum;

//plane's normal

normal = crossVec(subVec(plane[0],plane[1]),subVec(plane[1],plane[2]));

//intersect plane?

if( dotVec( subVec(line[0],plane[0]), normal)>0&& //both points on left of plane

dotVec( subVec(line[1],plane[0]), normal)>0)

return(FALSE); //so no intersection

if( dotVec( subVec(line[0],plane[0]), normal)<0&& //both point on right of plane

dotVec( subVec(line[1],plane[0]), normal)<0)

return(FALSE); //so no intersection

//if intersect plane, get point of intersection

angleSum=0;

t = - (normal.x*(line[0].x -plane[0].x) + normal.y*(line[0].y-plane[0].y) + normal.z*(line[0].z - plane[0].z))/

(normal.x*(line[1].x - line[0].x) + normal.y*(line[1].y - line[0].y) + normal.z*(line[1].z - line[0].z));

intersectionP.x = line[0].x + (line[1].x - line[0].x)*t;

intersectionP.y = line[0].y + (line[1].y - line[0].y)*t;

intersectionP.z = line[0].z + (line[1].z - line[0].z)*t;

angleSum+=(float)acos(dotVec(normalizeVec(subVec(i ntersectionP,plane[0])),normalizeVec(subVec(intersectionP,plane[1]))));

angleSum+=(float)acos(dotVec(normalizeVec(subVec(i ntersectionP,plane[1])),normalizeVec(subVec(intersectionP,plane[2]))));

angleSum+=(float)acos(dotVec(normalizeVec(subVec(i ntersectionP,plane[2])),normalizeVec(subVec(intersectionP,plane[3]))));

angleSum+=(float)acos(dotVec(normalizeVec(subVec(i ntersectionP,plane[3])),normalizeVec(subVec(intersectionP,plane[0]))));

if(angleSum>2*3.14&&angleSum<2*3.142){

return(TRUE);

}

return(FALSE);

}

In my project, I didn't want any polygon from one object to intersect any polygons from the other objects in the scene. This was accomplished by making sure no line segment of any polygon from one object intersected any polygon from the other object.

1) First I test whether the line intersects the polygons plane. This is not required, but speeds up things a bit. I test if both points of the line are on the left, or if both points are on the right (using dot product, see crappy code below). Exit with no collision if true.

2)Then I determined the x,y,z coords of the intersection of the plane, by changing into parametric equations and getting the t value for this.

3)Now, is this point in the polygon? Picture it in the center. If you draw a line segment from this point to a point on the polygon, then swoop it around to every other point in order, you should go 360 degrees. However, outside the polygon, you should get less than this. So, add up all the angles I mentioned. If it is between 359 and 361, assume your line has intersected your polygon.

Here's some code, hope it's not too bad http://www.opengl.org/discussion_boards/ubb/smile.gif

//determines if line intersects triangle

//code might be hard to understand

int detLineCol(vector *plane, vector *line)

{

vector normal,intersectionP;

GLfloat t,angleSum;

//plane's normal

normal = crossVec(subVec(plane[0],plane[1]),subVec(plane[1],plane[2]));

//intersect plane?

if( dotVec( subVec(line[0],plane[0]), normal)>0&& //both points on left of plane

dotVec( subVec(line[1],plane[0]), normal)>0)

return(FALSE); //so no intersection

if( dotVec( subVec(line[0],plane[0]), normal)<0&& //both point on right of plane

dotVec( subVec(line[1],plane[0]), normal)<0)

return(FALSE); //so no intersection

//if intersect plane, get point of intersection

angleSum=0;

t = - (normal.x*(line[0].x -plane[0].x) + normal.y*(line[0].y-plane[0].y) + normal.z*(line[0].z - plane[0].z))/

(normal.x*(line[1].x - line[0].x) + normal.y*(line[1].y - line[0].y) + normal.z*(line[1].z - line[0].z));

intersectionP.x = line[0].x + (line[1].x - line[0].x)*t;

intersectionP.y = line[0].y + (line[1].y - line[0].y)*t;

intersectionP.z = line[0].z + (line[1].z - line[0].z)*t;

angleSum+=(float)acos(dotVec(normalizeVec(subVec(i ntersectionP,plane[0])),normalizeVec(subVec(intersectionP,plane[1]))));

angleSum+=(float)acos(dotVec(normalizeVec(subVec(i ntersectionP,plane[1])),normalizeVec(subVec(intersectionP,plane[2]))));

angleSum+=(float)acos(dotVec(normalizeVec(subVec(i ntersectionP,plane[2])),normalizeVec(subVec(intersectionP,plane[3]))));

angleSum+=(float)acos(dotVec(normalizeVec(subVec(i ntersectionP,plane[3])),normalizeVec(subVec(intersectionP,plane[0]))));

if(angleSum>2*3.14&&angleSum<2*3.142){

return(TRUE);

}

return(FALSE);

}

Powered by vBulletin® Version 4.2.2 Copyright © 2014 vBulletin Solutions, Inc. All rights reserved.