## Whats wrong with my collision code?

Member
Posts: 509
Joined: 2002.05
Post: #1
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?

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);} `
denis
Unregistered

Post: #2
Shouldn't the intersection point be calculated more like

ip.x = ball.x - (triangle[i].normal.x * distance);

etc...
Member
Posts: 509
Joined: 2002.05
Post: #3
That helped, but i'm still having problems.
Moderator
Posts: 455
Joined: 2002.09
Post: #4
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.)

Measure twice, cut once, curse three or four times.
melvinator
Unregistered

Post: #5
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.
Member
Posts: 509
Joined: 2002.05
Post: #6
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).
Member
Posts: 148
Joined: 2003.03
Post: #7
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:
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 line-plane 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]; //v1-v2    return sqrt(d.x*d.x + d.y*d.y + d.z*d.z);} `