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
4  3311 
On 1 Dec 2004 12:11:36 -0800, Dave wrote: 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
This will certainly decrease your rounding errors. You'll have to
measure whether any speed decrease is worth the mathematical
improvement.
- Using the epsilon error on the variables to account for known
internal storage errors
Do you mean using something like
if(result < epsilon) result = 0;
That's something I've had to do on occasion. (epsilon usually around
10^-8 I think, but don't quote me on that.)
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.
This might also be a useful optimization trick, if it can often replace
a bunch of floating point calculations with a single boolean comparison.
Getting close to a general solution now but my once clear simple
routine has turned into a logical nightmare!
That does tend to be the way of these things. 99% of all situations are
handled very simply, and then you need a mass of special cases for the
last 1%.
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
These three will probably improve speed but decrease accuracy.
- Use a high precision custom storage class for calculations (speed is
off the essence so might not be an option?)
This could increase accuracy but decrease speed.
I'm working on Windows 2000 using Visual Studio 6 and .net enterprise
architect 2003 (c++).
Have you investigated the Visual Studio "improve floating point
consistency" compilation option? In a couple of projects I've worked
on, it has made a significant improvement. I didn't notice any speed
degradation, but my apps were not as computationally intense as yours
and didn't have real-time requirements.
--
Greg Schmidt gr***@trawna.co m
Trawna Publications http://www.trawna.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.
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.
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.
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.
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
Thanks for your comments Greg
Greg Schmidt <gr***@trawna.c om> wrote in message news:<1j******* *********@trawn a.com>... On 1 Dec 2004 12:11:36 -0800, Dave wrote:
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
This will certainly decrease your rounding errors. You'll have to
measure whether any speed decrease is worth the mathematical
improvement.
- Using the epsilon error on the variables to account for known
internal storage errors
Do you mean using something like
if(result < epsilon) result = 0;
That's something I've had to do on occasion. (epsilon usually around
10^-8 I think, but don't quote me on that.)
That's exactly what I've been doing! Thinking on this a bit more I
guess it's not really useful since it's only accounting for the
internal errors in the floating point operations and not the actual
errors due to the limitation of the storage class? 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.
This might also be a useful optimization trick, if it can often replace
a bunch of floating point calculations with a single boolean comparison.
Certainly did! My first attempt involved testing if the sphere
collided with everthing in the environment. About a 100 refinements
later and the routine now only does any involved maths for a handful
of triangles. Using flags to help control critical situations has also
been useful in terms of performance but not so useful to avoid my
objects slipping through the environment! Getting close to a general solution now but my once clear simple
routine has turned into a logical nightmare!
That does tend to be the way of these things. 99% of all situations are
handled very simply, and then you need a mass of special cases for the
last 1%.
Guess that's why there are only a handful of quick, robust collision
engines out there. 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
These three will probably improve speed but decrease accuracy.
Why so? Working with a quantised system should enable the position and
velocity of an object to be "forced" into allignment. For a simple
environment where objects are alligned with the quantised system I'm
sure such an approach would work (dull game though!) For a complex
environment operations like calculating the point of collision between
a sphere and an off-axis triangle face would be very tricky to
quantise though! - Use a high precision custom storage class for calculations (speed is
off the essence so might not be an option?)
This could increase accuracy but decrease speed.
And I'm not really that sure of the benefits. I think I'm stuck trying
to represent what are ultimately irrational numbers. No storage class
is going to help here! I'm working on Windows 2000 using Visual Studio 6 and .net enterprise
architect 2003 (c++).
Have you investigated the Visual Studio "improve floating point
consistency" compilation option? In a couple of projects I've worked
on, it has made a significant improvement. I didn't notice any speed
degradation, but my apps were not as computationally intense as yours
and didn't have real-time requirements.
Did have a look at this under VS6 but it didn't help too much.
Accuracy marginally improved but still below what is required. Will
have a look to see if .net is any better.
John Nagle <na***@animats. com> wrote in message news:<Z8******* ***********@new ssvr13.news.pro digy.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 This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics | |
by: Donn Cave |
last post by:
I ran into a phenomenon that seemed odd to me, while testing a
build of Python 2.4.1 on BeOS 5.04, on PowerPC 603e.
test_builtin.py, for example, fails a couple of tests with errors
claiming that apparently identical floating point values aren't equal.
But it only does that when imported, and only when the .pyc file
already exists. Not if I execute it directly (python test_builtin.py),
or if I delete the .pyc file before importing it...
|
by: michael.mcgarry |
last post by:
Hi,
I have a question about floating point precision in C.
What is the minimum distinguishable difference between 2 floating point
numbers? Does this differ for various computers?
Is this the EPSILON? I know in float.h a FLT_EPSILON is defined to be
10^-5. Does this mean that the computer cannot distinguish between 2
numbers that differ by less than this epsilon?
|
by: Hiten |
last post by:
Hi
please check ffollowing conditon
variable float1 and float2 holds user entered value.....
Answer=float1 * float2; //output must be 8.5
output must to be 8.5 but it has 8.500002, i am confused at this point
i used calculators and other calculation mathods to see the actual
value and thet give correct 8.5 with no other decimals......
|
by: Chris Stankevitz |
last post by:
Hi,
I have a very large Visual c++ .net 2003 7.1 native c application
(approximately 500,000 lines of code). This application is a simulation
that frequently works with floating point numbers.
From time to time I do something bad -- for example divide by zero or try
to grow a float beyond numeric_limits<float>::max()
I told MSVC .net 2003 7.1 to "Break into the debugger" for ALL exceptions in
|
by: jacob navia |
last post by:
Hi people
I continue to work in the tutorial for lcc-win32, and started to try to
explain the floating point flags.
Here is the relevant part of the tutorial. Since it is a difficult part,
I would like your expert advise before I publish any serious nonsense.
Any comments are welcome, style, organization, hard errors, etc.
| | |
by: dis_is_eagle |
last post by:
hi....i have encountered strange problem regarding floating point
comparison...the problem is...
main()
{
float a=0.7;
if(0.7 a)
printf("hi");
else
printf("hello");
|
by: Peter Sprenger |
last post by:
Hello,
I want to efficient convert floating point numbers (IEEE754) into a
string. I have no library routines that do the job (like sprintf etc.),
because I work in an embedded environment.
My actual algorithm uses multiplying with 10 to shift the fraction into
an integer value and to aquire the used exponent. But the drawback is
obvious: When I have very small numbers like 3.141E-300 I have to make
300 time consuming floating point...
|
by: Keflavich |
last post by:
Hey, I have a bit of code that died on a domain error when doing an
arcsin, and apparently it's because floating point subtraction is
having problems. I know about the impossibility of storing floating
point numbers precisely, but I was under the impression that the
standard used for that last digit would prevent subtraction errors
from compounding.
Is there a simple solution to this problem, or do I need to run some
sort of check at...
|
by: ma740988 |
last post by:
Consider the equation (flight dynamics stuff):
Yaw (Degrees) = Azimuth Angle(Radians) * 180 (Degrees) /
3.1415926535897932384626433832795 (Radians)
There's a valid reason to use single precision floating point types.
The number of decimal digits guaranteed to be correct on my
implementation is 6. (i.e numeric_limits < float >::digits10 = 6 )
If I'm reading the IEEE standard, I'd could paraphrase the issue
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
| | |
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
|
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| | |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |
