# 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.

## 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 on other sites
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 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 on other sites
Quote:
 Original post by phresnelPlus: You haven't mentioned which method you use?

Well here are my functions for comparing floating points:
const float MAX_ERROR = 0.00001;//Equal Tobool fp_et( float a, float b ){    return ( fabs( a - b ) < MAX_ERROR );}//Less Thanbool fp_lt( float a, float b ){    return !fp_et( a, b ) && ( a < b );}//Greater Thanbool fp_gt( float a, float b ){    return !fp_et( a, b ) && ( a > b );}Less than or Equal tobool fp_le( float a, float b ){    return fp_et( a, b ) || fp_lt( a, b );}Greater than or Equal tobool 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 on other sites
It looks like basically you are applying binary comparison, but that works stable only if there is a maximum velocity that is somehow dependent on the smallest occludible object's size.

I suggest to apply other (analytical) intersection methods, like Ray/Plane, Box/Box, and the like. An overview is here: http://www.realtimerendering.com/intersections.html.

1. 1
2. 2
3. 3
Rutin
23
4. 4
5. 5
khawk
14

• 9
• 11
• 11
• 23
• 10
• ### Forum Statistics

• Total Topics
633653
• Total Posts
3013153
×