Jump to content
  • Advertisement
Sign in to follow this  
Lazy Foo

So I need a new collision detection method

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

When looking up how sweep tests work, I had trouble finding any decent articles on it. Now I found out it was because floating point errors make it too unreliable to use in anything other than a sweep test demo. I'm getting some incredibly absurd situations such as: 620 + -1000 * .062 = -000001.78069. If I change epsilon, I just get errors in a different decimal place. I'm going to try two's compliment comparison tomorrow, but even if it works right it cannot be worth the headache. So what alternatives are there so doing collision detection between two high speed objects? If it matters, I'm going to have objects with velocities of up to 1080 pixels per frame (to simulate light speeds).

Share this post


Link to post
Share on other sites
Advertisement
Either stick to fixed-point math / decimals, or learn interesting stuff about floating point numbers:

I quote myself from a similar thread you opened some days ago:
Quote:

For proper enlightenment, here's a gem:

* Goldberg, "What every [computer] scientist should know about floating point math" (html, pdf)


It really is not only for scientists, but also for every graphics programmer and anyone who relies on floats - it tells you everything about ieee floating point numbers, and if you ever intend to seriously discuss about those issues, grok it (I haven't read it completely, but then I also do not discuss this topic :P). Have fun!



This thread is also interesting: click.

Share this post


Link to post
Share on other sites
Plus: You haven't mentioned which method you use? The most exact method would of course be based spacetime intersections, but in that topic I am not an expert; I just give the advice to know your tools and read Goldberg.

Share this post


Link to post
Share on other sites
Quote:
Original post by phresnel
Plus: You haven't mentioned which method you use?


Well here are my functions for comparing floating points:
const float MAX_ERROR = 0.00001;

//Equal To
bool fp_et( float a, float b )
{
return ( fabs( a - b ) < MAX_ERROR );
}

//Less Than
bool fp_lt( float a, float b )
{
return !fp_et( a, b ) && ( a < b );
}

//Greater Than
bool fp_gt( float a, float b )
{
return !fp_et( a, b ) && ( a > b );
}

Less than or Equal to
bool fp_le( float a, float b )
{
return fp_et( a, b ) || fp_lt( a, b );
}

Greater than or Equal to
bool fp_ge( float a, float b )
{
return fp_et( a, b ) || fp_gt( a, b );
}




And here's my functions for calculating the time intervals.

float min_time( float minA, float maxA, float minB, float maxB, float vel )
{
float tMinA = 0;

//No motion along axis
if( fp_et( vel, 0 ) )
{
if( fp_le( maxA, minB ) || fp_ge( minA, maxB ) )
{
//Collision is impossible
tMinA = 2;
}
else
{
//Will overlap for whole frame
tMinA = 0;
}
}
//Moving forward
else if( fp_ge( vel, 0 ) )
{
//Has already moved past
if( fp_ge( minA, maxB ) )
{
//Collision is impossible
tMinA = 2;
}
else
{
//Find intervals of collision
tMinA = ( minB - maxA ) / vel;
}
}
//Moving back
else if( fp_le( vel, 0 ) )
{
//Has already moved past
if( fp_le( maxA, minB ) )
{
//Collision is impossible
tMinA = 2;
}
else
{
//Find intervals of collision
tMinA = ( minA - maxB ) / -vel;
}
}

return tMinA;
}

float max_time( float minA, float maxA, float minB, float maxB, float vel )
{
float tMaxA = 0;

//No motion along axis
if( fp_et( vel, 0 ) )
{
if( fp_le( maxA, minB ) || fp_ge( minA, maxB ) )
{
//Collision is impossible
tMaxA = 2;
}
else
{
//Will overlap for whole frame
tMaxA = 1;
}
}
//Moving forward
else if( fp_ge( vel, 0 ) )
{
//Has already moved past
if( fp_ge( minA, maxB ) )
{
//Collision is impossible
tMaxA = 2;
}
else
{
//Find intervals of collision
tMaxA = ( maxB - minA ) / vel;
}
}
//Moving back
else if( fp_le( vel, 0 ) )
{
//Has already moved past
if( fp_le( maxA, minB ) )
{
//Collision is impossible
tMaxA = 2;
}
else
{
//Find intervals of collision
tMaxA = ( minA - ( minB - ( maxA - minA ) ) )/ -vel;
}
}

return tMaxA;
}



And lastly, how I find the time of collision
float col_time( ColIntervals &i )
{
float time = 2;

//If the collision happened
if( fp_ge( i.tMaxY, i.tMinX ) && fp_ge( i.tMaxX, i.tMinY ) )
{
//Get time
time = std::max( i.tMinX, i.tMinY );
}

return time;
}




I doubt the logic is wrong on that because I have a logger that spits out the data before the error occurred and I do the math by hand and double check it and my variables should be right.

For example, I'll have a box at x = 360 with an x Velocity = -1000. It's heading towards a collision box with it's right side at x = 0. This means it needs to move -360 pixels over.

My sweep test calculates a time of 0.36. 0.36 * -1000 is equal to -360.

But after the line:

xPos += xVel * time;

xPos is now "-1.14441e-005" instead of 0 like it should be. If I adjust epsilon to be higher, I'll just get a different floating point error.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!