Talk:Collision detection

From Wikipedia, the free encyclopedia

	Physics Portal This article is within the scope of WikiProject Physics, which collaborates on articles related to physics.
???	This article has not yet received a rating on the assessment scale. [FAQ]
???	This article has not yet received an importance rating within physics.
Help with this template Please rate this article, and then leave comments here to explain the ratings and/or to identify the strengths and weaknesses of the article.

Added a link to the GJK algorithm, the best algorithm known for distance between convex polytopes.

I've been doing some work on the ragdoll physics article and related subjects. --Nagle 05:13, 9 March 2006 (UTC)

[edit] Request for "sweep and prune" algorithm

For anyone interested, there is a request for the "sweep and prune" collision detection algorithm on Wikipedia:Requested articles/Applied arts and sciences/Computer science, computing, and Internet#Algorithms. Quick external link: [1]; a wealth of information can be found on Google. When done, please create the article sweep and prune to redirect here to the relevant section, and remove the request from the requested articles list. -- intgr 01:36, 17 December 2006 (UTC)

Done. Loisel 18:52, 17 December 2006 (UTC)

[edit] Why do say that the billiard ball simulation is numerically unstable?

This statement is unqualified. How can you say that the numerical algorithm is unstable when you haven't even presented the numerical algorithm? If you used an implicit method, for example, it would be unconditionally stable. Certain explicit algorithms would be unconditionally unstable, but some of course would be stable provided the time step is sufficiently small. Moreover, one would probably use an adaptive time stepper because the problem would become very stiff once collisions start to take place... Discostu5 18:40, 13 January 2007

The actual line of the article says this:

"This particular example also turns out to be numerically unstable: a small error in any calculation will cause catastrophic changes in the final position of the billiard balls."

So what is meant here is not 'instability' in the sense of the numbers blowing up to infinity or something - although many practical physics engines do exhibit these kinds of instabilities. What is meant here (I believe) is that a comparison of reality versus the simulation would be very sensitive to small numerical errors - such as might result from normal arithmetic precision issues. For example, if the black ball only just enters into a pocket after being hit by the cue ball, a very small error in calculating the trajectory of the cue ball could result in a much larger error in the post-collision trajectory of the black ball - which in turn might allow it to just ricochet off the side of the pocket - which in turn could result in half a dozen balls winding up half a meter away from where they should be. This is a consequence of 'sensitive dependance on initial conditions' - Chaos theory and all that stuff. In most applications of collision detection, (ie video games), we might not care - if the outcome was that close, do we really care?

So I'm not really defending this line in the article - I think it's misleading - but there is little doubt that there exist no really reliable collision detection algorithms that work in finite time and which never make errors other than those due solely to arithmetic precision. Yes, you can go with smaller and smaller time-slices - but there is always the possibility that your time slices aren't small enough - or that an unreasonably small time-slice might be needed in order to resolve a collision correctly.

The article needs to say something about the limits of what these algorithms can actually manage. Since they universally fall short of perfection.

SteveBaker 01:04, 14 January 2007 (UTC)

The billiards problem is essentially a version of problem #2 from the SIAM 100 digit challenge [2]. The photon in that problem bounces a few times (seven? I forget) but if you compute the bounces using double precision, the answer is completely incorrect. To obtain 10 digits, I had to use something like 250 digits of precision in my calculations.

To see the similarity with billiards, think of the photon as the cue ball, and the mirrors as the other 15 balls on the table. Loisel 22:10, 14 January 2007 (UTC)