Real-Time Physics Simulation Forum

collision with very big static object

2006-05-28T18:33:46+00:00

You are probably right and I am wrong. :(

Almost humble?! Doesn't sound at all like the child who first posted this belligerent post:

Wow, thanks you for letting it me know about that algebraic identity (I feel so much empowered now). Is this a principle you came up with? Would that be the Ericson?s inequivalence of the transitivity principle of algebra for better factorization? [other vitriol deleted]

which you edited into the above post (yes, I caught your initial post before you retracted it).

There's no "probably" right here. Let me elaborate on why the expressions A*A-B*B and (A+B)*(A-B) have different numerical errors, and what this has to do with the GJK algorithm (and all other algorithms implemented in floating-point arithmetic).

Under IEEE-754 floating-point arithmetic we are guaranteed the expression "A op B" (where op is +, -, *, or /) will result in the value (A op B) * (1 + epsilon) where |epsilon| <= u, where u is the machine epsilon. This error is due to rounding of the result to the nearest machine-representable number. For the first expression, A*A-B*B, what is actually computed numerically is therefore:

(A*A*(1+e1) - B*B*(1+e2))*(1+e3)

where each error ei is of the order |ei|<=u, where u is the machine epsilon.

Expanded, this gives:

A*A - B*B + A*A*(e1 + e3) - B*B*(e2 + e3) + O(u^2)

where O(u^2) contains all the rest terms involving two or more error terms (which are so small that they can be safely ignored).

The second expression, (A+B)*(A-B), will be evaluated as:

((A+B)*(1+e1)*(A-B)*(1+e2))*(1+e3)

This expands to:

A*A - B*B + A*A*(e1 + e2 + e3) - B*B*(e1 + e2 + e3) + O(u^2)

For comparison purposes, we can drop the insignificant O(u^2) error terms. Then, as one can see, when computed in floating-point, the expression A*A-B*B has an error of A*A*(e1 + e3) - B*B*(e2 + e3) whereas the expression (A+B)*(A-B) has an error of A*A*(e1 + e2 + e3) - B*B*(e1 + e2 + e3). These errors are clearly different.

Going beyond this simple example, we have that just about any two different but mathematically equivalent expression will have different numerical errors when subject to an error analysis as above.

This applies to the expressions computed in the distance calculations of GJK too (or any other algorithm for that matter). Thus, if you express the "Johnson's subdistance algorithm" bit of GJK in two different ways, they will have different numerical errors even if those two ways are mathematically equivalent.

A good resource for learning more about error analysis of floating-point expressions is Wilkinson's "Rounding Errors in Algebraic Processes" (in reprint from Dover for just a few dollars).

Next time you have an urge to post some malevolent drivel, first consider if you actually have a clue what you're talking about, then, when you decide to post it regardless, be a man and post under your real name.

Statistics: Posted by Christer Ericson — Sun May 28, 2006 6:33 pm

collision with very big static object

2006-05-25T16:58:12+00:00

You are probably right and I am wrong.

Statistics: Posted by Etherton — Thu May 25, 2006 4:58 pm

collision with very big static object

2006-05-24T21:22:40+00:00

Maybe I should had said they are numerically equivalent

You could say that, but that would be wrong, assuming you by "numerically equivalent" mean having the same error numerically. (If you mean something else, you need to define what you mean by that nonstandard term.) For example, consider the expressions A*A - B*B and (A+B)*(A-B). They are mathematically equivalent, but they have different numerical errors. It is an incredibly rare occurance for two mathematically equivalent (yet different) expressions to have the same numerical error!

Statistics: Posted by Christer Ericson — Wed May 24, 2006 9:22 pm

collision with very big static object

2006-05-24T13:41:20+00:00

You misunderstood. It is trivially the case that we can have two expressions, A and B, which are different looking but mathematically equivalent, and where one has less numerical errors than the other. Obviously, by rewriting A as B (or B as A) you can achieve the same error, but that presupposes (a) that you realize that A can be written as B, and (b) that such a rewrite is easy to perform in the form in which A is given.

In that light, the point I was trying to make was that a cascaded, recursive expression gives less control over how you deal with numerical errors compared to a case-by-case approach where the numerical error in each case can be explored and handled independently from each other.

Maybe I should had said they are numerically equivalent, it is not truth calculating the closest distance to a tetrahedron could be done with more accuracy using Voronoi feature search, than using Lagrange multipliers minimization (wich is what GJK originally uses). That is simple false.

The truth is that any given implementation of GJK is extremely sensitive to lost of significant bit in floating point operations, and since GJK is a steepest descend search method each time an incorrect search direction is selected it lead to infinite cycling.
This has nothing to do with breaking the test for more optimization, or making then more intuitive or even implementing then is cache friendly way or not.

edit:
I must say that GJK implemented using Voronoi search is a good implementation of the algorithm, and it does has the bonus that is can be seen as a strictly geometrically method that do not required the knowledge of more advanced algebraic techniques.

However that does not make it in any way more intuitive, less error tolerance, more geometrical, or more efficient than any other flavor of the same algorithm, as it is has been sold.

Statistics: Posted by Etherton — Wed May 24, 2006 1:41 pm

collision with very big static object

2006-05-24T07:15:41+00:00

As I remember it was said that by using Voronoi space search the numerical errors due to lost of precision in the analytical distance calculation are avoided. In fact it can be proven that both methods are mathematically equivalent.

You misunderstood. It is trivially the case that we can have two expressions, A and B, which are different looking but mathematically equivalent, and where one has less numerical errors than the other. Obviously, by rewriting A as B (or B as A) you can achieve the same error, but that presupposes (a) that you realize that A can be written as B, and (b) that such a rewrite is easy to perform in the form in which A is given.

In that light, the point I was trying to make was that a cascaded, recursive expression gives less control over how you deal with numerical errors compared to a case-by-case approach where the numerical error in each case can be explored and handled independently from each other.

Statistics: Posted by Christer Ericson — Wed May 24, 2006 7:15 am

collision with very big static object

2006-05-23T23:37:10+00:00

Very good maybe now you can document that Bullet does not have the limitation that Havok and Ageia has in its GJK.
I think that Bullet is a very good library and before it, there were only three legs on physics: Havok, Agia and ODE, now with Bullet quatrenium is completed.

PS:
On the bright side from this criticism the result was positive: an improvement of what was already excellent and know is brilliant

Statistics: Posted by Etherton — Tue May 23, 2006 11:37 pm

collision with very big static object

2006-05-23T22:31:09+00:00

I just improved the Bullet GJK implementation so it can handle object sizes of up to 1000 units.

The updated source code is online here:
http://www.continuousphysics.com/ftp/pu ... source.zip

Still it's best to stay below those sizes. Preferably use a static triangle mesh, with triangles up to 10 units.
Thanks,
Erwin

Statistics: Posted by Erwin Coumans — Tue May 23, 2006 10:31 pm

collision with very big static object

2006-05-23T20:41:29+00:00

As I remember it was said that by using Voronoi space search the numerical errors due to lost of precision in the analytical distance calculation are avoided. In fact it can be proven that both methods are mathematically equivalent.

Unfortunately they are indeed mathematically equivalent. The reason why I chose for Christer Ericson's implementation is intuition, and the oportunity to easier optimize individual cases. This is discussed on Molly Rocket's forum here: http://www.mollyrocket.com/forums/viewt ... b87b50d844

Perhaps this intuition leads to better understanding so we can sort out this problem. I found that affinely dependent points in the simplex is one part of the puzzle.

But saying that all physics engine has that limitation is absolutely not true.

If you can name me one current physics engine using PGS that doesn't suffer the mass ratio problem, please let us know. As Erin pointed out, I would also be very interested to know how to solve this problem (without reverting to shock propagation)

Bullet has a SAT implementation, a contribution by Simon Hobbs, that actually works for this case (250x10x250 box). It has been in Bullet for a few months now, and you can enable it by adding #define TEST_HULL 1
in ConvexConvexAlgorithm.cpp. See the Hull class in http://www.continuousphysics.com/Bullet ... index.html

As Erin pointed out in a conversation recently, this SAT Convex Hull implementation has some issues, because it doesn't search some edge-edge combinations. This might lead to 'floating' objects, especially for long thin objects. It should be fine for boxes, so not all convex polyhedra are affected by this edge problem.

The mass ratio limitation is for heavy on light. Light on heavy is quite stable.

Indeed, I assumed heavy on light.

Thanks,
Erwin

Statistics: Posted by Erwin Coumans — Tue May 23, 2006 8:41 pm

collision with very big static object

2006-05-23T20:19:44+00:00

The mass ratio limitation is for heavy on light. Light on heavy is quite stable.

The last time I tried to balance a sofa on a shoe box, it was also unstable.

That said, we would love to hear about an O(n) algorithm that can handle heavy on light. It should also require only 10 iterations at 60Hz. Also, weight should be transmitted correctly (no shock propagation).

Statistics: Posted by Erin Catto — Tue May 23, 2006 8:19 pm

collision with very big static object

2006-05-23T19:48:23+00:00

ODE uses SAT, so it is not using GJK (yet).

Maybe I am wrong but I think I did play a test demo with bullet integration.
Anyway when you add bullet to ODE/Bullet combined will probably be the best physicist solution ever implemented. I am just salivating for that.

Where was this assumed? Except for extreme size ratios, that can be avoided, GJK works fine. The GJK implementations that I know of (Havok, Solid and Bullet) all have limitations in extreme cases due to floating point and the nature of the algorithm/implementation. Improvements can be made, but for most scenarios its practical to limit the maximum object size.

In truth I do not think it is important because a body with such irregular aspect ratio lead to such heavy and skew mass matrix that not solver is capable of handle it with enough stability, so it will be only practical for static geometry. However the fact is that one user just changed the size for 50 to 250 (5/1 ratio) and it did produced a failure. Maybe he did it wrong but that does not seem as extreme as you are saying, and that is a fact.

The superiority of Bullet to ordinary GJK was assumed everywhere, more than that. It was introduced as the new panacea to the normal implementation of GJK. As I remember it was said that by using Voronoi space search the numerical errors due to lost of precision in the analytical distance calculation are avoided. In fact it can be proven that both methods are mathematically equivalent.

The mass ratio problem currently exists in all engines using PGS iterative solvers, including Havok, Ageia/PhysX, ODE, Bullet etc. For an actual confession for Havok, see
Erwin

Well I do not have proof about Havok, Ageia/PhysX because I have never seen the source code, I did worked on a game using Havok and I do not remember having such problems, maybe they hide it, but who am I to say?
You seem to have seen the source and therefore you can make that confirmation, maybe then you can be more specific and said that Bullet, have the same limitations of Havok, Ageia and ODE. But saying that all physics engine has that limitation is absolutely not true.

Statistics: Posted by Etherton — Tue May 23, 2006 7:48 pm