Re: Floating point errors in collision routines

From: Dave (dalcock_at_stroke.org.uk)
Date: 12/05/04 

Date: 5 Dec 2004 09:39:28 -0800

John Nagle <nagle@animats.com> wrote in message news:<Z8Jrd.27551$zx1.8014@newssvr13.news.prodigy.com>...
> Trying to converge a floating point calculation all the way to
> zero is fundamentally futile. You get characteristic underflow
> before you get zero.
>
> In general, bear in mind that subtracting two large numbers
> to get a tiny result is inherently prone to roundoff error. You
> must design your algorithms to avoid that.
>

Have done this... up to a point! Within each function I have tried to
avoid any such calculations but my code is such a mess that I am
probably doing all sorts of dodgy calculations. Certainly lots of
vector normalisation which I really must tidy up. I can see lots of
scope for improvement here but also many cases where subracting two
large numbers is pretty much inevitable. When you say two large
numbers do you mean two numbers with many decimal places or just large
numbers? Would it help to change the scale of the environment? Do you
know if floating point operations are generally more accurate within a
certain range of numbers? Guessing it's not important where the
decimal place sits as every digit needs to be accounted for!

Need to look out those old maths notes about Nth degree of error on a
caculation?

> Some collision detection algorithms, especially early versions
> of GJK, are badly behaved when two faces are very close to
> parallel. Of course, if you're doing physics right, objects
> in contact come to rest in face-parallel situations, so the
> near-parallel situation gets explored very thoroughly.
> Newer collision engines, like (I think) Gino's SOLID, get
> it right.
>

I think I'm doing the physics right! For objects that have specific
frictional resistance I'm assuming that there will be a deceleration
period where face-face contact must be maintained. This is the messy
bit! This is why I am trying to use flags to maintain stability for
these cases. Please let me know if this assumption is wrong, I studied
physics but am no expert on collision mechanics!

> Developing collision algorithms that don't have floating
> point precision problems yet don't "cheat" on contact analysis
> is hard, but quite possible. See my US patent #6,067,096, which
> covers the first "ragdoll physics" that worked. It's necessary
> to be very careful about the limitations of floating point.
> But once you get it right, it works very well.
>

You're patent is a bit too much for my head on a Sunday evening! Very
impressive though! Were you able to control the floating point errors
by clever algorithm design alone? Did you find it necessary, or
helpful, to trunctate your intermediate results or use the documented
error on floating point operations during comparisons?

> As I usually tell people, either buy a physics engine
> (probably Havok), figure out some way to make gameplay
> work with lousy physics, or expect to spend a few years
> on the problem.
>

Think I'll keep bashing away for now! Have just spent 3 hours playing
Kill Zone (purely for research you understand!) Seems to suffer from
the same sort of issues I am having (and some that I am not!) Perhaps
mine will be finished in time for the PS9!

Thanks again for your comments.

> John Nagle
> Animats
>
> Dave wrote:
>
> > Hi folks,
> >
> > I am trying to develop a routine that will handle sphere-sphere and
> > sphere-triangle collisions and interactions. My aim is to develop a
> > quake style collision engine where a player can interact with a rich
> > 3D environment. Seem to be 90% of the way there! My problems are
> > related to calculations where the result tends to zero (or another
> > defined limit.)
> >
> > Have loads of cases where this kind of interaction occurs but this one
> > is as tricky (?) as any...
> >
> > When a moving sphere approaches a triangulated plane I am using a
> > sphere-plane collision routine to see if a collision will occur. All
> > goes well until I start to have near parallel interactions (e.g. when
> > the sphere has sufficient energy to collide with, and then slide along
> > the plane.) During the next pass of the collision routine the velocity
> > of the sphere is perpendicular (in a single plane) to the face normal
> > of the previous colliding plane. A dot product between the velocity of
> > the sphere and the normal of the colliding plane should be zero. It's
> > close to zero but how close is close enough to warrant no further
> > collision? A "need to collide" case occurs where the sphere is just
> > above the plane with a velocity almost parallel to the plane BUT just
> > on a collision course. The above dot product will be very close to
> > zero again, but this time there should be a collision with this plane!
> >
> > Since I need to account for glancing off faces, approaching faces at
> > right angles, interacting with steps, falling off edges etc the number
> > of vector operations to determine the final position and velocity of
> > the sphere need to be as accurate as possible.
> >
> > I guess my question (sorry for the waffle) is how to minimise rounding
> > errors in floating point operations?
> >
> > So far I've tried to account for the errors (or eliminate them) by:
> >
> > - Using double precision decelerations and calculations
> > - Using the epsilon error on the variables to account for known
> > internal storage errors
> >
> > Unable to eliminate or account for the errors I then set about trying
> > to use flags to ignore colliding objects from future collision during
> > the current recursive collision routine call. Helped in some cases so
> > started to try to account for all near critical iterations using
> > flags.
> >
> > Getting close to a general solution now but my once clear simple
> > routine has turned into a logical nightmare!
> >
> > When working with numbers where accuracy is paramount should I be
> > using a different approach? I've considered the following:
> >
> > - Using a quantised system where all values have to fall along a
> > virtual 3D grid
> > - Using sin and cos tables to support the above goal of quantisation
> > - Using integer mathematics
> > - Use a high precision custom storage class for calculations (speed is
> > off the essence so might not be an option?)
> >
> > Perhaps I am worrying too much! My current "effort" seems to handle
> > interactions in a similar, if much more shaky, way to Unreal
> > Tournament 2004. Kind of clunky at times, stops occasionally and seems
> > to have problems jumping on steps!
> >
> > I'm working on Windows 2000 using Visual Studio 6 and .net enterprise
> > architect 2003 (c++). It's a DirectX application if that makes any
> > difference?
> >
> > Any advice would be really appreciated.
> >
> > Many thanks,
> >
> > Dave