Talk:Collision detection

From Wikipedia, the free encyclopedia

WikiProject Physics This article is within the scope of WikiProject Physics, which collaborates on articles related to physics.
B This article has been rated as B-Class on the assessment scale.
Low This article is on a subject of Low importance within physics.

Help with this template This article has been rated but has no comments. If appropriate, please review the article and leave comments here to identify the strengths and weaknesses of the article and what work it will need.

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)

Contents

[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

"If you used an implicit method, for example, it would be unconditionally stable." Actually, as one of the few people to ever try ragdoll physics with an implicit integrator, I can report that it doesn't help much. The problem is that the integration becomes more stable, but solving the implicit system when it is highly stiff turns out to be difficult. Getting the solution to converge can require very small steps in a high-dimensional nonlinear space and very frequent recomputation of the Jacobian. Overall, it turned out to be slower than using an RK4 integrator and tiny time steps. But it would violate WP:OR to put that in the article. --John Nagle 02:50, 10 June 2007 (UTC)
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)

--Isc ekul 05:17, 2 May 2007 (UTC)

I tend to aggree with 'steve baker' or someone else (can't follow the posts) above on finding the billiard ball thing slightly missleading - ok it does become chaotic - but to describe it as computationally unstable sounds a bit over the top. It would be numerically unstable quite quickly if you only use 1% accuracy on the vectors, eventually any computer will get the answers wrong - but nowadays I'd imagine the ball to come to a rest before the positions were significantly out?
Surely any similation involving repeated collisions is unstable - is that what it is trying to say? I guess so. But as it is it sounds like a lot of air - no substance - with that statement I'd like to see some work associated.. or something.


As to the above I hope you meant 10 digits of precision in decimal and 250 digits in binary - other wise I'd imagine you to have a very broken computer (just my joke)87.102.17.177 22:03, 19 June 2007 (UTC)

[edit] Collision detection vs. collision response

In this field, there's generally a strong distinction between collision detection, which is a purely geometric problem, and collision response, which is concerned with the physics of simulating what happens when collisions are detected. Material on the latter should be moved out to physics engine or ragdoll physics, where it's already covered. --John Nagle 07:02, 6 May 2007 (UTC)

Did some cleanup work, but the article is still something of a mess. I've cleaned up the description of the Lin-Canny / GJK convex polyhedron systems, which I know something about. Now we need a better description of the precomputation-based approaches, where trees are precomputed from level maps and collision with the fixed features is computed cheaply. That's not something I've worked with, and someone who really understands that stuff should write it up.

Actually, numerical stability in collision detection isn't a serious problem any more. (It was ten years ago, but we're past that.) Numerical stability in collision response is still tough. But that's a different subject. --John Nagle 07:39, 6 May 2007 (UTC)

[edit] minor point

great article nice to see a mention of bounding volumes etc - this would be a good start for someone to learn about computer games physics programming - assuming they could understand all the words, but the section Collision_detection#Video_games states "Almost all games use a posteriori collision detection" - I don't think this is nowadays true - I think most new 3d games use an "a priori" method on a frame by frame basis - (is this a mixture of a priori and a posteriori?) - so in a give 1/50sec frame a typical engine would calculate the distance to intersection when moving in a given direction and then compare with the distance travelled in that time - effectively calculating the when the touch things are touching. This applies to linear motion.

If the the object is rotating I know of two methods that are still commonplace - one is to approximate the area produced by the rotating line by a triangle, the other is to solve the quadratic associated with rotation (more accurate) - both are still a priori.

When an object is rotating and translating approximations are used - typically using both the translation and rotation detection one each in turn - this obviously is an approximation - but typically the movements are small in given frame and the approximation is satisfactory for games.

In case of objects moving under gravity etc usually a 'a priori' method is used on a frame by frame basic with the approximation used that an arc (parabola) is well estimated by a series of short straight lines along its path.

I'm not aware of any method that uses a 'a posteriori' method on a frame by frame basis nowadays though I can imagine that it used to be used.

The methods I've described above would calcualted friction etc in between the frames - effectively they convert the 'smooth' motion of a thing into a series of small straight lines (typically one line per frame) and then accurately test for the exact touching point on collision of the thing moving along that line.87.102.20.50 00:39, 10 June 2007 (UTC)

Now I've read in more detail I realise the article to be shit in parts - see below. The bits on bsp trees was quite good though.

[edit] Added better references

Added links to the two main collision detection research groups: Berkeley and Oxford. Cited M.C. Lin paper properly. We could use more on precomputed spatial partitioning methods, which is how most games do walls. --John Nagle 16:39, 16 June 2007 (UTC)

[edit] ?

"binary search is known to be relatively inefficient compared to other root-finding algorithms such as Newton's method."

I removed this. It was put back in - what does newtons method for finding roots have to do with collision detection

—Preceding unsigned comment added by 87.102.17.177 (talk • contribs) 14:25, 19 June 2007

Dear anonymous editor,

Collision detection involves finding when the distance d(x,y) between two objects x and y becomes zero (i.e., root finding on the distance function d). Two such methods are bisection and Newton's method, but there are many other methods as well.

I reverted you the previous time, I will revert you this one additional time. If you delete this passage again, I will rely upon another editor to make the appropriate decision.

I don't know if it would be possible for me to make a request of you, but if you don't understand something, would it be possible for you to ask on the talk page instead of modifying the article?

Thank you very much,

What about the question? ie is there a single example in which newtons method is USEFUL in finding a collision point - if so name it - otherwise why did you revert.?

Lin's findings are not relevant for inclusion - just because you found means nothing - is that why you reverted - because you didn't like your additions removed? Loisel 15:58, 19 June 2007 (UTC)

Addendum: for an overview, see section 2.3 of this paper. [3] Loisel 16:18, 19 June 2007 (UTC)

Oh great a sarcastic cunt- thanks - I asked a question see above.

A. What does the linked page Newton's method have do do with finding a collision in any general case - for simple motion - linear, rotating exact solutions are known. For more complex cases eg motion in magnetic fields the equations of motion are complex and it may not be possible to even solve the differential equation giving the motion.

B. What does the 'binary search' refer to in this case - is it some sort of iterative method to get to a best estimate of the collision distance - in which case the phrase 'binary search' hardly is a good discription. If not what is it exactly?

I doubt you can even fucking answer these - thats why the biggest thing you can do is revert on site - am I right?87.102.17.177 16:37, 19 June 2007 (UTC)

Also Ph.D students 'MC Lin' or whatever - that paper is (as the article states) useless (a lot like most students) so why does it even get a mention? Is the author a friend of Lin or wants to be friends. Any idiot can come up with an unworkable idea - the real methods involve bsp or bounding volumes etc and triangle triangle intersections or similar.87.102.17.177 16:42, 19 June 2007 (UTC)

this bit "Better methods have since been developed. Very fast algorithms are available for finding the closest points on the surface of two convex polyhedral objects. Early work by M. C. Lin [1] used"... why??

First off, let me point you to WP:CIVIL, which is official policy. Please do not violate this rule again.

Second, if you want to learn about rootfinding and collision detection, consult the literature, it is easy. I found a rough paper which I linked above, and a google search also yields http://www.springerlink.com/content/y485230u8147111r/, which is in Springer. "An Integrated Runge–Kutta Root Finding Method for Reliable Collision Detection in Multibody Systems" by Gerald Grabner and Andrés Kecskeméthy.

Third, I have never met M. C. Lin, never spoken to her, and she does not know of me. We're not in the same field at all. I'm a numerical mathematician at Temple University http://www.math.temple.edu/~loisel/ and she's a professor of computer science at UNC http://www.cs.unc.edu/~lin/. I've never set foot in North Carolina.

Finally, the point of that paragraph is not to pitch this algorithm to anyone, but this being an encyclopedia, I was just trying to give as many alternatives as I knew of. Loisel 16:59, 19 June 2007 (UTC)

[edit] ? continued

ok I removed this

"Given that exact numbers are impossible to obtain, one can also use a simple a posteriori algorithm, and then use a binary search to attempt to compute the first moment of collision, if any. However, aside from the fact that this approach may miss some collisions, binary search is known to be relatively inefficient compared to other root-finding algorithms such as Newton's method."

In what way are exact numbers impossible to obtain.?

"one can also use a simple a posteriori algorithm, and then use a binary search to attempt to compute the first moment of collision, if any" should be at least "one can also use a simple a posteriori algorithm such as a binary search to attempt to compute the first moment of collision, if any"

Is binary search actually inefficient compared to another iterative process such as newtons method? - calculating with binary search takes n steps to get to more than n bits accuracy - and the only compuation required is to test whether the object has crossed another object.

Newton's method involves calculating a (potentionally complex) function a number of times - for complex motion (as I stated above) the equation of motion may not even be known. Unless small time frames are used bsp partioning or similar will break down (cease to reduce the amount of objects to be considered)

I'd expect a reference that states that a root finding algorthym is better than binary search.

—Preceding unsigned comment added by 87.102.17.177 (talk • contribs) 17:41, 19 June 2007

First, please consult WP:SIG and sign your further comments by putting three or four tildes at the end of your comments.

Second, the article that I gave above, http://www.springerlink.com/content/y485230u8147111r/, uses a much more complicated root finding algorithm than binary search. First, the "event function" (the d(x,y) distance function) is interpolated using a polynomial. This is done by augmenting the ODE of the system by adjoining differential equations for the distance functions. Then the RK integrator gives a dense output, consisting of a polynomial which interpolates the true solution (including the event function) over the time interval. Third, the roots of this polynomial over the time interval are found using Sturm sequences (I do something similar, but I use the Durand-Kerner method instead.) Finally, the exact zero of the distance functions are found by running a Newton-Raphson rootfinding algorithm on the (nonpolynomial) distance functions, and using the roots found by the Sturm sequence algorithm as initial guesses. The overall algorithm is compared to LSODAR, which is a black-box numerical integrator that includes event handling. By comparison, LSODAR apparently uses a variant of the secant method and bisection method, as does MATLAB's ODE suite (see Brent's method.) The black-box algorithms can sometimes be faster, but part of the point of the Grabner paper is that the interpolation method more reliably catches the first event in a time interval. Apparently, they found that for 25+ spheres, LSODAR works 20-30% slower than their algorithm.

Loisel 18:05, 19 June 2007 (UTC)

Well you certainly used a lot of names there but that really doesn't help. I'm assuming that you were saying that the root finding algorhythm was better. if the distance functions are not polynomials then why does it need a rootfinding algorhythm to find the zero? typing error? Also as you say LSDOR is an integrator - does that use a binary search then ? Otherwise what you've just said is irrelevant? (it's definately not 100% binary search by a long shot is it?)

and my other questions/comments - any thoughts?.

(comment - It seems that you must be looking at more complex movements of simple shapes (particle physics or something?) whereas I tend to imaging the problem in term of examples where motion is relatively simple - but shapes may be very complex ?? so I may not fully understand the type of methods you need to use)

[edit] exact pairwise collision detection

why doesn't the article decribe a method that works eg test for ray/plane (6 of) and line/line collsion (9 of) (brackets give the numbers for a single triangle)

- and what is the obsession with convex polyhedra - utilising only convex shapes doesn't give such a major reduction in computation as bounding volumes etc (also described) - as far as I can tell this is info that is just an academic curiosity no more?

Also the link to the Gilbert-Johnson-Keerthi distance algorithm has a link within that is to a paysite - this link *"The Gilbert-Johnson-Keerthi distance algorithm: a fast version for incremental motions", Ong and Gilbert this should be removed.

Also how is MC Lins work relevant?

Also why no mention that linear motion is a good approximation when dealing with small time frames eg 1/20 - 1/60 sec for computer graphics? —Preceding unsigned comment added by 87.102.17.177 (talk • contribs)

Most of the commercial physics engines, like Havok and Ageia, support convex polyhedra and use GJK.[4] Incremental enhanced GJK is so fast that "pairwise pruning" can slow things down. You need a coarse level system to decide which pairs to examine, but axis-oriented bounding boxes do that. --John Nagle 21:41, 15 November 2007 (UTC)

[edit] also ????

" We note here that if the trajectories of the vertices are assumed to be linear polynomials in t then the final sixty functions are in fact cubic polynomials, and in this exceptional case, it is possible to locate the exact collision time using the formula for the roots of the cubic. Some numerical analysts suggest that using the formula for the roots of the cubic is not as numerically stable as using a root finder for polynomials."

most of this should be removed.

1. "..assumed to be linear polynomials in t then the final sixty functions are in fact cubic polynomials" comment if the trajectories of verticies are for example quartics the final sixty functions are NOT CUBICS - the paragraph as it is is simply wrong - what was it meant to say?

2. "Some numerical analysts suggest that using the formula for the roots of the cubic is not as numerically stable as using a root finder for polynomials" - needs a citation - is this hearsay or what?

Is the paragraph trying to say that complex motion equations can be approximated by cubics over a small time frame? (that's my guess) - I expect this to be deleted or substationally corrected - as it stands it is nonsense - please help. Thank you.

I have no idea what it is supposed to say so I cannot begin to correct it.

[edit] unforced error

Collision_detection#Exact_pairwise_collision_detection third paragraph (including the one line paragraph at beginning - quote "There are twenty such planes." - as far as I can tell this should be 18 reason - the two planes formed by the triangles don't count? I'm assuming I've understood - can someone please check this.87.102.17.177 20:53, 19 June 2007 (UTC)

[edit] Collision_detection#Exact_pairwise_collision_detection

The algorhytm described isn't very good (to test whether or not two stationary triangles intersect)- a simpler one would be to:

Part A

1. Find the equation describing the line (call in line X) formed by the intersection of the two planes defined by the two triangles (if the triangles are parallel the equation includes a divide by zero, if the triangles are coplanar the equation reduces to zero divided by zero see Part B)
2. taking an edge of the triangle (any edge) find the intersection of this edge with the line X - if this intersection lies between the two points defining the triangle edge the trinagles are intersecting = TRUE and stop obviously
3. taking an edge of the same triangle (any of the two remaining edges) find the intersection of this edge with the line X - if this intersection lies between the two points defining the triangle edge the trinagles are intersecting = TRUE and stop here
4. If this point has been reached then the triangles are not intersecting

Part B

The triangles have been found to be coplanar in part A.1.
Use a method of your choice to test whether the coplanar triangles are interseting - possible methods include:
1. Express each of the 6 points in terms of vectors formed by the edges of the other triangle
eg triangles ABC and DEF
point D =A+nAB+mAC (AB is vector from A to B) if n>=0 AND m>=0 AND n+m<=1 then that point is inside the triangle = TRUE, stop. otherwise check the other five points..
If you checked all six points and none were inside the other triangle then triangles ABC and DEF are coplanar but do not insect. stop anyway.
2. Alternatively use a different test (can't think of one off hand)

I'm sure that this test will use less compatation than the 18 (20? see previous question) planes each with 2 cross products to be calculated. Note that part B will be used very rarely but can be included for completeness.

In the vast majority of cases part B is rarely used (unless for some reason all your triangles tend to be coplanar in 3d space - why?)
(trivia Note that on average Part A2 catches 2/3 of intersections)


Personally I'd recommend an 'a priori' method instead that attempts to calculate the intersections in small time frames (for rag-doll type stuff) using linear approximations to rotary motion if you don't want to solve the quadratic associated with rotary motion. Under rare conditions this will miss collisions but no more than any other method (except those which find exact solutions)

missed objects = mostly very thin objects moving past other very thin objects whilst rotating about the axis formed by the linear motion - in general use though it catches ALL usefull collisions - such collisions might tend to slice past each other anyway in real life?

I'm sure that anyone who knows maths should be easily able to find a references for this method and recognise it's betterness as well as maybe give it a name. According to wiki-law I can't include it now as without references it would be original research - no way is such a simple method original though.87.102.17.177 21:28, 19 June 2007 (UTC)

Write it up, post it somewhere else, and link to it. That's what everyone else does to get their original research incorporated. Rogerborg 11:19, 11 July 2007 (UTC)