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:
- (VECTORcheckCollisions:(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( 0levelx*levely*2i++ )    //step through all the triangles
    
{
        
distance = [self dotball plustriangles[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.ball.ballVector.x*distance;    //the point where the ball hit the triange
            
ip.ball.ballVector.y*distance;
            
ip.ball.ballVector.z*distance;
            
            
vtx0.triangles[i].vertex[0].x;        //turn the triange data into nice vector data so
            
vtx0.triangles[i].vertex[0].y;        //we can use the dot product on them
            
vtx0.triangles[i].vertex[0].z;
            
vtx1.triangles[i].vertex[1].x;
            
vtx1.triangles[i].vertex[1].y;
            
vtx1.triangles[i].vertex[1].z;
            
vtx2.triangles[i].vertex[2].x;
            
vtx2.triangles[i].vertex[2].y;
            
vtx2.triangles[i].vertex[2].z;
            
            
tip.ip.vtx0.x;            //puts the difference of ip  and the first vertex into a temperary vector
            
tip.ip.vtx0.y;
            
tip.ip.vtx0.z;
            
vec0 = [self normalize:(tip)];        //normalizes the vector
            
            
tip.ip.vtx1.x;
            
tip.ip.vtx1.y;
            
tip.ip.vtx1.z;
            
vec1 = [self normalize:(tip)];
            
            
tip.ip.vtx2.x;
            
tip.ip.vtx2.y;
            
tip.ip.vtx2.z;
            
vec2 = [self normalize:(tip)];
        
            
/*Adds the angles between the vectors here*/
            
dAngle acos([self dotvec0 plusvec1]) + acos([self dotvec1 plusvec2]) + acos([self dotvec2 plusvec0]);
            
            
NSLog(@"dAngle =      %f",dAngle);        //helps me debug
            
            
if( fabsdAngle 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:
- (VECTORnormalize:(VECTOR)a
{
    
VECTOR result;
    
float distance;
    
    
result.a.x;
    
result.a.y;
    
result.a.z;
    
    
distance sqrt(result.x*result.result.y*result.result.z*result.z);
    
    
result.result.x/distance;
    
result.result.y/distance;
    
result.result.z/distance;
    
    return 
result;
}

- (float) 
dot:(VECTOR)a plus:(VECTOR)b
{
    return (
a.b.x) + (a.b.y) + (a.b.z);

Quote this message in a reply
denis
Unregistered
 
Post: #2
Shouldn't the intersection point be calculated more like

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

etc...
Quote this message in a reply
Member
Posts: 509
Joined: 2002.05
Post: #3
That helped, but i'm still having problems.
Quote this message in a reply
Moderator
Posts: 434
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.
Quote this message in a reply
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.
Quote this message in a reply
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).
Quote this message in a reply
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 vNCOPY_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->vLineStart->vDirection.fPercentage;
    
vIntersection->vLineStart->vDirection.fPercentage;
    
vIntersection->vLineStart->vDirection.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.d.y*d.d.z*d.z);

Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  What's wrong with my glutSolidTeapot? TomorrowPlusX 4 5,513 Aug 7, 2008 10:27 AM
Last Post: arekkusu
  Lighting a sphere with OpenGL lights (normals wrong?) cecilkorik 3 8,043 Dec 27, 2007 02:40 PM
Last Post: _ibd_
  What could be wrong here? Jones 5 2,796 Jul 1, 2006 08:52 PM
Last Post: Jones
  Can someone help a 'noob'? What's wrong with this? RagingAvatar 7 4,145 Jun 4, 2006 11:54 PM
Last Post: Fenris
  Texture Color is wrong DesertPenguin 7 3,975 Feb 14, 2006 09:04 PM
Last Post: DesertPenguin