gdalgorithms-list

[Algorithms] floats, doubles, epsilons, joy

[Jason Z. <zi...@n-...>]

I've been working on some collision stuff lately and I keep running into
problems with floating point inaccuracies.  Specifically if the player is
standing on top of a triangle, the distance should be zero, but with float
it was very close to zero but not quite.  So I converted all my code to use
double and its much better but I'm still not getting exactly zero.  With
float they were large enough to cause unwanted movement, with double they
are tiny but I can easily imagine the player finding a way to make these
values be higher than my epsilon amount (0.00001).  Just so everyone knows,
I'm doing ellipsoid vs. triangle collision with an algorithm I found on
Flipcode (http://www.flipcode.com/tutorials/tut_coll-ellipsoids.shtml).

This is the first time I've run into this, I'm wondering if there are some
common ways to get around these types of problems?

Also I was wondering if there was a down side to using doubles rather than
floats.  This code doesn't use any ram so size doesn't matter, but is doing
floating point math with doubles much slower or have other unwanted side
effects?

Thanks for any suggestions,

- Jason Zisk
- nFusion Interactive LLC

Re: [Algorithms] floats, doubles, epsilons, joy

[Gil G. <gg...@ma...>]

I wouldn't use doubles, they just obscure the problem but don't eliminate
it. If an algorithm is unstable with floats, it is usually unstable with
doubles too.

So, how to solve the problem? The only solution is carefully analize the
situation and do things robustly. That isn't very helpful, but it is true,
you gotta really think about the situation to solve the problem.

I solve your collision problem like this typically. I don't attempt to rest
directly on the floor, I attempt to hover .1 inches or so off the floor.
Therefore, even with floating point inaccuracy, I never find I am IN the
floor at the start of the next round. This does use a tolerence, but it is
subtly different than your approach. Your approach attempts to correct the
problem after is occurs and my approach is proactive, insuring the problem
does not occur. (This all assumes finding yourself in the floor is the
problem).

Even if you get this problem licked, if you are doing anything interesting,
like say having things push the player, you will run into half a dozen other
more subtle problems. You gotta think through each one to figure out how to
solve the problem with inexact arithmatic. It is really really hard work.

-Gil


> I've been working on some collision stuff lately and I keep running into
> problems with floating point inaccuracies.  Specifically if the player is
> standing on top of a triangle, the distance should be zero, but with float
> it was very close to zero but not quite.  So I converted all my code to
use
> double and its much better but I'm still not getting exactly zero.  With
> float they were large enough to cause unwanted movement, with double they
> are tiny but I can easily imagine the player finding a way to make these
> values be higher than my epsilon amount (0.00001).  Just so everyone
knows,
> I'm doing ellipsoid vs. triangle collision with an algorithm I found on
> Flipcode (http://www.flipcode.com/tutorials/tut_coll-ellipsoids.shtml).
>
> This is the first time I've run into this, I'm wondering if there are some
> common ways to get around these types of problems?
>
> Also I was wondering if there was a down side to using doubles rather than
> floats.  This code doesn't use any ram so size doesn't matter, but is
doing
> floating point math with doubles much slower or have other unwanted side
> effects?
>
> Thanks for any suggestions,
>
> - Jason Zisk
> - nFusion Interactive LLC
>
>
>
>
>
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] floats, doubles, epsilons, joy

[Jason Z. <zi...@n-...>]

A bit of buffer, good idea.  So the general algorithm would be: after I find
the distance to collision make sure its always at least X (maybe 0.01 like
Steve suggested) units.  If its larger than X units, move X-0.01 units
instead of the full X.  This sounds like it will make the system much more
robust, thanks again.

- Jason Zisk
- nFusion Interactive LLC


----- Original Message -----
From: "Gil Gribb" <gg...@ma...>
To: <gda...@li...>
Sent: Thursday, August 31, 2000 3:36 PM
Subject: Re: [Algorithms] floats, doubles, epsilons, joy


> I wouldn't use doubles, they just obscure the problem but don't eliminate
> it. If an algorithm is unstable with floats, it is usually unstable with
> doubles too.
>
> So, how to solve the problem? The only solution is carefully analize the
> situation and do things robustly. That isn't very helpful, but it is true,
> you gotta really think about the situation to solve the problem.
>
> I solve your collision problem like this typically. I don't attempt to
rest
> directly on the floor, I attempt to hover .1 inches or so off the floor.
> Therefore, even with floating point inaccuracy, I never find I am IN the
> floor at the start of the next round. This does use a tolerence, but it is
> subtly different than your approach. Your approach attempts to correct the
> problem after is occurs and my approach is proactive, insuring the problem
> does not occur. (This all assumes finding yourself in the floor is the
> problem).
>
> Even if you get this problem licked, if you are doing anything
interesting,
> like say having things push the player, you will run into half a dozen
other
> more subtle problems. You gotta think through each one to figure out how
to
> solve the problem with inexact arithmatic. It is really really hard work.
>
> -Gil
>
>
> > I've been working on some collision stuff lately and I keep running into
> > problems with floating point inaccuracies.  Specifically if the player
is
> > standing on top of a triangle, the distance should be zero, but with
float
> > it was very close to zero but not quite.  So I converted all my code to
> use
> > double and its much better but I'm still not getting exactly zero.  With
> > float they were large enough to cause unwanted movement, with double
they
> > are tiny but I can easily imagine the player finding a way to make these
> > values be higher than my epsilon amount (0.00001).  Just so everyone
> knows,
> > I'm doing ellipsoid vs. triangle collision with an algorithm I found on
> > Flipcode (http://www.flipcode.com/tutorials/tut_coll-ellipsoids.shtml).
> >
> > This is the first time I've run into this, I'm wondering if there are
some
> > common ways to get around these types of problems?
> >
> > Also I was wondering if there was a down side to using doubles rather
than
> > floats.  This code doesn't use any ram so size doesn't matter, but is
> doing
> > floating point math with doubles much slower or have other unwanted side
> > effects?
> >
> > Thanks for any suggestions,
> >
> > - Jason Zisk
> > - nFusion Interactive LLC
> >
> >
> >
> >
> >
> >
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

RE: [Algorithms] floats, doubles, epsilons, joy

[Akbar A. <sye...@ea...>]

>This is the first time I've run into this, I'm wondering if there are some
>common ways to get around these types of problems?

*cough* hack;
but it really depends on your type of application.

often you would just do a check, if it's between this number and this
number, then just set it to the number it *should* (this is a hack as well)
be.
it takes a "hell-of-a-lot-" of tweaking to get right.
just design your code with these thoughts, and make sure to add in these
"checks", if you don't you will run into lots of subtle bugs.
but there comes a point, where you just have to stop, or you might be get
the "just one more time syndrome".


>Also I was wondering if there was a down side to using doubles rather than
>floats.  This code doesn't use any ram so size doesn't matter, but is doing
>floating point math with doubles much slower or have other unwanted side
>effects?
there is no reason to "downsize" your program if you don't have to :)
anyways, i wrote up a small little test case just to make sure the
performance question.

i'm on a p3 750

time it took for double calculation 3562
time it took for float calculation 985



// time.cpp
#include <stdio.h>
#include <windows.h>
#include <iostream.h>

int main()
{
	float trash = 0;
	double trash2 = 0;
	DWORD timer;
	DWORD elapsed;
	int i;

	printf("double size = %i\n", sizeof(double));
	printf("float size = %i\n", sizeof(int));

	timer = GetTickCount();
	for(i = 0; i < 99999999; i++)	{
		trash2 += 0.23533423533412;
	}
	elapsed = GetTickCount() - timer;
	cout<<"time it took for double calculation "<<elapsed<<endl;

	timer = GetTickCount();

	for(i = 0; i < 99999999; i++)	{
		trash += 0.123412f;
	}

	elapsed = GetTickCount() - timer;
	cout<<"time it took for float calculation "<<elapsed<<endl;
}

/////////

cl -o crap time.cpp
crap :)

you could go ahead and try a while version just to be totally sure about
this issue.


peace.
akbar A.


isn't it ironic, in the paper "A Characterization of Ten Hidden-Surface
Algorithms", by sutherland, sproull and schumacker that we use the eleventh
algorithm ;)
makes you really think


-----Original Message-----
From: gda...@li...
[mailto:gda...@li...]On Behalf Of Jason
Zisk
Sent: Thursday, August 31, 2000 12:14 PM
To: gda...@li...
Subject: [Algorithms] floats, doubles, epsilons, joy


I've been working on some collision stuff lately and I keep running into
problems with floating point inaccuracies.  Specifically if the player is
standing on top of a triangle, the distance should be zero, but with float
it was very close to zero but not quite.  So I converted all my code to use
double and its much better but I'm still not getting exactly zero.  With
float they were large enough to cause unwanted movement, with double they
are tiny but I can easily imagine the player finding a way to make these
values be higher than my epsilon amount (0.00001).  Just so everyone knows,
I'm doing ellipsoid vs. triangle collision with an algorithm I found on
Flipcode (http://www.flipcode.com/tutorials/tut_coll-ellipsoids.shtml).

This is the first time I've run into this, I'm wondering if there are some
common ways to get around these types of problems?

Also I was wondering if there was a down side to using doubles rather than
floats.  This code doesn't use any ram so size doesn't matter, but is doing
floating point math with doubles much slower or have other unwanted side
effects?

Thanks for any suggestions,

- Jason Zisk
- nFusion Interactive LLC







_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] floats, doubles, epsilons, joy

[Pierre T. <p.t...@wa...>]

Errr..............

Doubles notoriously are slower than floats. Moreover if you use D3D you
really shouldn't be messing around with doubles. From the DX7 docs:

"Applications that require double-precision accuracy can include the
DDSCL_FPUPRESERVE flag when calling the IDirectDraw7::SetCooperativeLevel
method to set the DirectDraw cooperative level. When the DDSCL_FPUPRESERVE
flag is used, the system still uses single-precision mode, but it saves the
state of the FPU prior to changing the precision mode, then restores the
mode when it returns control to the application. (Calling the method again
using the DDSCL_FPUSETUP flag returns Direct3D to its default behavior.)
Obviously, this check, save, then restore process takes time and can
noticeably affect performance. This flag should only be used when the
application must have double-precision accuracy and you do not want to
include code to manually set and restore the FPU mode as the application
requires."

And all in all, using doubles is just a way to hide a problem, not a way to
fix it. No magic bullet there, it really depends on the piece of code
involved I'm afraid.

Pierre


----- Original Message -----
From: Jason Zisk <zi...@n-...>
To: <gda...@li...>
Sent: Thursday, August 31, 2000 7:14 PM
Subject: [Algorithms] floats, doubles, epsilons, joy


> I've been working on some collision stuff lately and I keep running into
> problems with floating point inaccuracies.  Specifically if the player is
> standing on top of a triangle, the distance should be zero, but with float
> it was very close to zero but not quite.  So I converted all my code to
use
> double and its much better but I'm still not getting exactly zero.  With
> float they were large enough to cause unwanted movement, with double they
> are tiny but I can easily imagine the player finding a way to make these
> values be higher than my epsilon amount (0.00001).  Just so everyone
knows,
> I'm doing ellipsoid vs. triangle collision with an algorithm I found on
> Flipcode (http://www.flipcode.com/tutorials/tut_coll-ellipsoids.shtml).
>
> This is the first time I've run into this, I'm wondering if there are some
> common ways to get around these types of problems?
>
> Also I was wondering if there was a down side to using doubles rather than
> floats.  This code doesn't use any ram so size doesn't matter, but is
doing
> floating point math with doubles much slower or have other unwanted side
> effects?
>
> Thanks for any suggestions,
>
> - Jason Zisk
> - nFusion Interactive LLC
>
>
>
>
>
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] floats, doubles, epsilons, joy

[Jamie F. <j.f...@re...>]

>
> Also I was wondering if there was a down side to using doubles rather than
> floats.  This code doesn't use any ram so size doesn't matter, but is doing
> floating point math with doubles much slower or have other unwanted side
> effects?

Not all platforms have hardware support for doubles.

Jamie