Whats wrong with my collision code?
I am reading the tutorial from this site, and this is what I have came up with so far.
http://www.edenwaith.com/products/pige/t...lision.php
It seams that the plane collision check is working, but my triangle check isn't working, the angle is never greater than .2 when it should be 2pi. My brain is fried after learning so much in 2 days, does anyone have and help?
http://www.edenwaith.com/products/pige/t...lision.php
It seams that the plane collision check is working, but my triangle check isn't working, the angle is never greater than .2 when it should be 2pi. My brain is fried after learning so much in 2 days, does anyone have and help?
PHP Code:
 (VECTOR) checkCollisions:(VECTOR)ball ballVect:(VECTOR)ballVector
{
VECTOR newBallDir; //The balls new vector after it hits something
VECTOR ip,tip; //The point that the ball hits the triangle
float dAngle;
float epsilon = .01; //How close our number can be to pi
VECTOR vec0,vec1,vec2; //Vectors of the point the ball hit the triangles to the vertice of the triangles
VECTOR vtx0,vtx1,vtx2; //The vertice of the triangles
float distance; //How far the sphere is from the plane
int i; //For counter
for( i = 0; i < levelx*levely*2; i++ ) //step through all the triangles
{
distance = [self dot: ball plus: triangles[i].normal ]; //How far the sphere is from the plane
if (fabs(distance) < 0.2) //if the distance is less than the radius of the ball
{
ip.x = ball.x + ballVector.x*distance; //the point where the ball hit the triange
ip.y = ball.y + ballVector.y*distance;
ip.z = ball.z + ballVector.z*distance;
vtx0.x = triangles[i].vertex[0].x; //turn the triange data into nice vector data so
vtx0.y = triangles[i].vertex[0].y; //we can use the dot product on them
vtx0.z = triangles[i].vertex[0].z;
vtx1.x = triangles[i].vertex[1].x;
vtx1.y = triangles[i].vertex[1].y;
vtx1.z = triangles[i].vertex[1].z;
vtx2.x = triangles[i].vertex[2].x;
vtx2.y = triangles[i].vertex[2].y;
vtx2.z = triangles[i].vertex[2].z;
tip.x = ip.x  vtx0.x; //puts the difference of ip and the first vertex into a temperary vector
tip.y = ip.y  vtx0.y;
tip.z = ip.z  vtx0.z;
vec0 = [self normalize:(tip)]; //normalizes the vector
tip.x = ip.x  vtx1.x;
tip.y = ip.y  vtx1.y;
tip.z = ip.z  vtx1.z;
vec1 = [self normalize:(tip)];
tip.x = ip.x  vtx2.x;
tip.y = ip.y  vtx2.y;
tip.z = ip.z  vtx2.z;
vec2 = [self normalize:(tip)];
/*Adds the angles between the vectors here*/
dAngle = acos([self dot: vec0 plus: vec1]) + acos([self dot: vec1 plus: vec2]) + acos([self dot: vec2 plus: vec0]);
NSLog(@"dAngle = %f",dAngle); //helps me debug
if( fabs( dAngle  2*3.1415926 ) < epsilon ) //if the angle is about 360 degrees we are in the triangle
{
NSLog(@"HIT %d",i);
//R= 2*(I dot N)*N + I
}
}
}
return newBallDir;
}
PHP Code:
 (VECTOR) normalize:(VECTOR)a
{
VECTOR result;
float distance;
result.x = a.x;
result.y = a.y;
result.z = a.z;
distance = sqrt(result.x*result.x + result.y*result.y + result.z*result.z);
result.x = result.x/distance;
result.y = result.y/distance;
result.z = result.z/distance;
return result;
}
 (float) dot:(VECTOR)a plus:(VECTOR)b
{
return (a.x * b.x) + (a.y * b.y) + (a.z * b.z);
}
Shouldn't the intersection point be calculated more like
ip.x = ball.x  (triangle[i].normal.x * distance);
etc...
ip.x = ball.x  (triangle[i].normal.x * distance);
etc...
I can't say I've spotted a problem. The thing that made me a little nervous is the way you are computing the point where the ball touches the triangle's plane. You are allowing a margin of 0.2, which could be quite large depending on how fast the ball is travelling, what the radius is, and how obliquely it is travelling. Imagine for example the ball travelling quickly sideways to, but slowly approaching, the plane of the triangle. Your code will always bounce it back too early, and unless the objects are small the player may notice. Conversely, imagine the ball travelling very fast directly at the plane; it could skip the collision test, depending on the velocity.
There are ways to avoid these problems but they don't have anything to do with your question.
Sometimes what I do when I can't spot where the math is going wrong is to feed it some easy test cases and follow along in the debugger. Setup a ball that is directly in the middle of the triangle already and debug the code, then move the ball off the plane by 0.5r and make sure it still works... You get the idea. Follow along with a calculator and pretty soon you'll find the problem. For me, usually it's something silly: a typo, the sign of something is reversed from what I expect, or a float is accidentally being coerced into an integer in one step of the calculation. Or I've passed in degrees where radians are expected.
Note that I looked for and didn't find any of those particular errors in your code. My point is that errors like that are hard to spot, but if you debug each step of the way and watch the values carefully, you will find it. And setting up a few simple test cases makes the calculations easier to follow.
Sorry I couldn't help more specifically.
p.s. Are you sure the point is being projected onto the plane correctly? If it lies off the plane the angles will always add up to less than 2*pi. (I'd expect them to be more than 0.2 so I don't think that's your problem, but maybe it's worth checking.)
There are ways to avoid these problems but they don't have anything to do with your question.
Sometimes what I do when I can't spot where the math is going wrong is to feed it some easy test cases and follow along in the debugger. Setup a ball that is directly in the middle of the triangle already and debug the code, then move the ball off the plane by 0.5r and make sure it still works... You get the idea. Follow along with a calculator and pretty soon you'll find the problem. For me, usually it's something silly: a typo, the sign of something is reversed from what I expect, or a float is accidentally being coerced into an integer in one step of the calculation. Or I've passed in degrees where radians are expected.
Note that I looked for and didn't find any of those particular errors in your code. My point is that errors like that are hard to spot, but if you debug each step of the way and watch the values carefully, you will find it. And setting up a few simple test cases makes the calculations easier to follow.
Sorry I couldn't help more specifically.
p.s. Are you sure the point is being projected onto the plane correctly? If it lies off the plane the angles will always add up to less than 2*pi. (I'd expect them to be more than 0.2 so I don't think that's your problem, but maybe it's worth checking.)
Measure twice, cut once, curse three or four times.
For the sweeping problems mentioned by MattDiamond there is a pdf and source code at http://www.three14.demon.nl/ than handles both spheres and ellipsoids. Its a little long winded but seems very robust (at least has be in my use of it).
Your code looks at a cursory glance to work like the tutorial. Try setting up a test case on an axis that you can work out by hand to trace where the code blows up.
Hope that helps.
Your code looks at a cursory glance to work like the tutorial. Try setting up a test case on an axis that you can work out by hand to trace where the code blows up.
Hope that helps.
Quote:Originally posted by MattDiamond
I can't say I've spotted a problem. The thing that made me a little nervous is the way you are computing the point where the ball touches the triangle's plane. You are allowing a margin of 0.2, which could be quite large depending on how fast the ball is travelling, what the radius is, and how obliquely it is travelling. Imagine for example the ball travelling quickly sideways to, but slowly approaching, the plane of the triangle. Your code will always bounce it back too early, and unless the objects are small the player may notice. Conversely, imagine the ball travelling very fast directly at the plane; it could skip the collision test, depending on the velocity.
Thanks for the reply. The reason I have .2 is because thats the radius of the golf ball. I am aware of the skipping problem, but I know how to fix that, I will do that after I get everything working
Im going to do that calculator walk through when i have some free time tomorrow, good idea.
Quote:p.s. Are you sure the point is being projected onto the plane correctly? If it lies off the plane the angles will always add up to less than 2*pi. (I'd expect them to be more than 0.2 so I don't think that's your problem, but maybe it's worth checking.)
I don't know, I added some code to draw the normals of the planes, and they all had the right angle, except about 20% faced up and 80% faced down. Should I make them all face up?
Quote:For the sweeping problems mentioned by MattDiamond there is a pdf and source code at http://www.three14.demon.nl/ than handles both spheres and ellipsoids. Its a little long winded but seems very robust (at least has be in my use of it).
Your code looks at a cursory glance to work like the tutorial. Try setting up a test case on an axis that you can work out by hand to trace where the code blows up.
Cool, thanks!
I will post back tomorrow, i am whipped now (mentally and physically).
I'm not sure exactly if this will help, but here's how I achieve collision detection between triangles and particles (Note: the following is experimental):
1) Save particle's current position (old position)
2) Update particle position, velocity, etc.
3) Classify the particle's old and new positions as being either in front, in back, or on the triangle's plane and determine is a collision has occurred between the particle and the triangle's plane.
The function below will return 0, 1, or 2, depending on what side of plane pl the test point v is:
(5:09PM Est)

(Note: I haven't tried this part, since I am using these techniques in a different manner, but it should work)
If the particle's new position (2) is on a different side of the triangles plane than the particle's old position (1), then then particle has collided with the plane, and we continue on to 4. Otherwise, no collision has occurred, and we continue checking other triangles.

4) Since the particle collided with the triangle's plane, you must now check to see if the particle lies within the edges of the triangle.
A) Build a line from the particle's new position(2) to the particle's old position(1).
B) Get the intersection point of the line (4A) and the triangle's plane.
The following function can also be used to replace the classifyPoint function, but as I said at the beginning, this is all experimental for me. Returns TRUE if the line defined by vLineStart and vLineEnd intersects the plane defined by vPointInPlane and vPlaneNormal. If TRUE, also saves the lineplane intersection point in vIntersection:
If getLinePlaneIntersectionPoint returns TRUE (which it always should if we go to this step), then we continue to 4C. Otherwise we stop and start checking other triangles.
C) Check if the intersection point (4B) lies within the edges of the triangle.
The function below returns TRUE if the point v lays inside coplanar polygon p (the triangle can easily be converted to a polygon object)
If TRUE, then the particle is colliding with the triangle and collision response is needed.
(5:09PM Est)
P.S. I know the code is sloppy and there's tons of things that can be improved upon. Also I don't claim that this will work for all scenarios, it just works for what I'm experimenting with right now. Also I'm not sure what effects different triangle vertex ordering (clockwise and counterclockwise) have on the functions. Any improvements/suggestions are welcome.
1) Save particle's current position (old position)
2) Update particle position, velocity, etc.
3) Classify the particle's old and new positions as being either in front, in back, or on the triangle's plane and determine is a collision has occurred between the particle and the triangle's plane.
The function below will return 0, 1, or 2, depending on what side of plane pl the test point v is:
PHP Code:
(int)classifyPoint:(lmVec*)v forPlane:(lmPlane)pl
{
float result;
lmVec vN; COPY_VEC(v,vN); //copy v into vN
lmVec direction;
SUB_VEC(pl.coplanar_point,vN,direction); //subtract parameter 2 from parameter 1, and leave the result in parameter 3
result = DOT_VEC(direction,pl.normal); //dot product of 2 vectors
if(result<0.001) //0.001 is the margin here
return 2; //CP_FRONT;
if(result>0.001)
return 0; //CP_BACK
return 1; //CP_ONPLANE
}
(5:09PM Est)

(Note: I haven't tried this part, since I am using these techniques in a different manner, but it should work)
If the particle's new position (2) is on a different side of the triangles plane than the particle's old position (1), then then particle has collided with the plane, and we continue on to 4. Otherwise, no collision has occurred, and we continue checking other triangles.

4) Since the particle collided with the triangle's plane, you must now check to see if the particle lies within the edges of the triangle.
A) Build a line from the particle's new position(2) to the particle's old position(1).
B) Get the intersection point of the line (4A) and the triangle's plane.
The following function can also be used to replace the classifyPoint function, but as I said at the beginning, this is all experimental for me. Returns TRUE if the line defined by vLineStart and vLineEnd intersects the plane defined by vPointInPlane and vPlaneNormal. If TRUE, also saves the lineplane intersection point in vIntersection:
PHP Code:
(BOOL)getLinePlaneIntersectionPoint:(lmVec*)vLineStart :(lmVec*)vLineEnd :(lmVec*)vPointInPlane :(lmVec*)vPlaneNormal :(lmVec*)vIntersection
{
lmVec vDirection;
lmVec L1;
float fLineLength;
float fDistanceFromPlane;
float fPercentage;
lmVec vLS,vLE;
COPY_VEC(vLineEnd,vLE); COPY_VEC(vLineStart,vLS);
SUB_VEC(vLE,vLS,vDirection);
lmVec vPN;
COPY_VEC(vPlaneNormal,vPN);
fLineLength = DOT_VEC(vDirection,vPN);
if(fabsf(fLineLength)<0.001f)
return FALSE;
lmVec vPP;
COPY_VEC(vPointInPlane,vPP);
SUB_VEC(vPP,vLS,L1);
fDistanceFromPlane = DOT_VEC(L1,vPN);
fPercentage = fDistanceFromPlane/fLineLength;
if(fPercentage<0.0f  fPercentage>1.0f)
return FALSE;
vIntersection>x = vLineStart>x + vDirection.x * fPercentage;
vIntersection>y = vLineStart>y + vDirection.y * fPercentage;
vIntersection>z = vLineStart>z + vDirection.z * fPercentage;
return TRUE;
}
If getLinePlaneIntersectionPoint returns TRUE (which it always should if we go to this step), then we continue to 4C. Otherwise we stop and start checking other triangles.
C) Check if the intersection point (4B) lies within the edges of the triangle.
The function below returns TRUE if the point v lays inside coplanar polygon p (the triangle can easily be converted to a polygon object)
PHP Code:
(BOOL)doesVector:(lmVec)v layInsidePolygon:(lmPolygon)p
{
const float MATCH_FACTOR = 0.9999;
float Angle = 0.0;
lmVec vA,vB;
int i;
for(i=0;i<p.vertex_count;i++)
{
vA = [self vectorBetween:p.vertex[i] :v]; //See PS
vB = [self vectorBetween:p.vertex[(i+1) % p.vertex_count] :v];
Angle=Angle+[self angleBetweenVectors:vA And:vB]; //See PS
}
if(Angle>= (MATCH_FACTOR*(2.0*_PI)))
return TRUE;
return FALSE;
}
If TRUE, then the particle is colliding with the triangle and collision response is needed.
(5:09PM Est)
P.S. I know the code is sloppy and there's tons of things that can be improved upon. Also I don't claim that this will work for all scenarios, it just works for what I'm experimenting with right now. Also I'm not sure what effects different triangle vertex ordering (clockwise and counterclockwise) have on the functions. Any improvements/suggestions are welcome.
PHP Code:
(float)angleBetweenVectors:(lmVec)v1 And:(lmVec)v2
{
float dotProduct = DOT_VEC(v1,v2);
float vectorsMagnitude = MAG_VEC(v1)*MAG_VEC(v2);
float angle = acos(dotProduct/vectorsMagnitude);
if(isnan(angle))
return 0;
return angle;
}
(float)distanceBetweenVectors:(lmVec*)v1 And:(lmVec*)v2
{
lmVec d = [self getVector:v1 minusVector:v2]; //v1v2
return sqrt(d.x*d.x + d.y*d.y + d.z*d.z);
}
Possibly Related Threads...
Thread:  Author  Replies:  Views:  Last Post  
What's wrong with my glutSolidTeapot?  TomorrowPlusX  4  7,352 
Aug 7, 2008 10:27 AM Last Post: arekkusu 

Lighting a sphere with OpenGL lights (normals wrong?)  cecilkorik  3  9,671 
Dec 27, 2007 02:40 PM Last Post: _ibd_ 

What could be wrong here?  Jones  5  3,692 
Jul 1, 2006 08:52 PM Last Post: Jones 

Can someone help a 'noob'? What's wrong with this?  RagingAvatar  7  5,689 
Jun 4, 2006 11:54 PM Last Post: Fenris 

Texture Color is wrong  DesertPenguin  7  5,188 
Feb 14, 2006 09:04 PM Last Post: DesertPenguin 