So I need a new collision detection method
Author
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).
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:
This thread is also interesting: click.
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.
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.
Author
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 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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
