Talk:Collision detection

This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Physics Low‑importance This article is within the scope of WikiProject Physics, a collaborative effort to improve the coverage of Physics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.PhysicsWikipedia:WikiProject PhysicsTemplate:WikiProject Physicsphysics articles Low This article has been rated as Low-importance on the project's importance scale. Video games Low‑importance This article is within the scope of WikiProject Video games, a collaborative effort to improve the coverage of video games on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Video gamesWikipedia:WikiProject Video gamesTemplate:WikiProject Video gamesvideo game articles Low This article has been rated as Low-importance on the project's importance scale. Summary of Video games WikiProject open tasks: Summary of Video games WikiProject open tasks view watch edit history shell vg talk alerts purge AfDs Atomas (1 participant) PLAY: The Games Festival (2 participants) FloodSim (1 participant) Kunimitsu and Kunimitsu II (1 participant) Blast Monkeys (2 participants) Godzilla 2: War of the Monsters (6 participants) Free Internet Chess Server (9 participants) Gilman Louie (3 participants; relisted) Yoshimitsu (5 participants; relisted) Emote (3 participants; relisted) Preston Arsement (6 participants; relisted) Jackpot World (3 participants; relisted) Merge discussions Legacy of Kain: Soul Reaver 1 & 2 Remastered (discussion) Pokémon Essentials (discussion) Harvest Moon DS: Sunshine Islands (discussion) Input lag (discussion) Neo Geo Pocket (discussion) Minecraft – Volume Beta (discussion) Other discussions No major discussions Featured content candidates Claire Redfield (nom) Pokémon episodes removed from rotation (nom) Donkey Kong (nom) Good article nominations Kim Kitsuragi (start) Miner 2049er (start) Pixel Piracy (start) The Outer Worlds (nom) River Raid (start) The Great Giana Sisters (start) Haunter (Pokémon) (start) Bit City (start) Dendy (start) Dark Urge (start) Pokémon Scarlet and Violet (start) Jeanette Voerman (start) Crono (start) Deathloop (start) Quiver (video game) (start) Regi (Pokémon) (start) Ridley (Metroid) (start) Blast Wind (start) Project Zero 2: Wii Edition (start) Shiori Fujisaki (nom) Barry Burton (start) Sea of Stars (start) Pokémon Smile (start) Pokémon Stadium (start) Otogirisō (start) M&M's Break' Em (start) DYK nominations Sun Haven Reviews and reassessments A Space for the Unbound (rev) Wild Arms (video game) (nom) Bejeweled (video game) (rev) The Legend of Dragoon (rev) The Legend of Zelda: A Link to the Past (nom) Articles that need... assessment (3) (0) reassessment (0) cleanup (7) infoboxes (12) cover art (235) screenshots (8,936) photos (68) translation from japan (187) creation merging Computing Low‑importance This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing articles Low This article has been rated as Low-importance on the project's importance scale.

The contents of the Hitbox page were merged into Collision detection on 23 July 2019. For the contribution history and old versions of the redirected page, please see its history; for the discussion at that location, see its talk page.

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)[reply]

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)[reply]

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

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)[reply]

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)[reply]

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)[reply]

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

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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.

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)[reply]

"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)[reply]

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

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)

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)[reply]

" 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.

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)[reply]

I agree. The plane going through (v1, v2, v3) and the plane going through (v4, v5, v6) cannot be used as separating planes as the triangles (v1, v2, v3) and (v4, v5, v6), respectively, lie within these planes - therefore one cannot speak of a separating plane.

By the way - what about the article Separating axis theorem - wouldn't this be a good wikilink addition to this article? --Abdull (talk) 12:44, 14 June 2008 (UTC)[reply]

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)[reply]

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)[reply]

Would efforts to devise an automated method for detecting traffic collisions fall under the scope of this article? 69.140.152.55 (talk) 01:21, 10 September 2008 (UTC)[reply]

Not really; this article deals with collision detection in computer physics simulations. -- intgr [talk] 08:56, 10 September 2008 (UTC)[reply]

This seems to be producing an ongoing series of edits. First, this is really a collision response or game physics issue, not a collision detection issue. That whole discussion belongs in Game physics. Second, the discussion here seems to be mostly original research. Third, what I think someone is trying for here is to talk about simulation systems where there's a "fixup step" in handling collisions. This is a hack that tries to back out of a collision hard case in a way that's not physically valid but usually yields plausible gameplay. The technology of modern physics engines has gone beyond that, but some older games did it that way.

The actual distinctions in collision detection are more related to the geometry. There are algorithms for spheres (easy and fast). There are algorithms for convex polyhedra (hard, bur fast). There are algorithms for "polygon soups" of arbitrary triangles (hard and can be slow). There are algorithms that work against "height fields" for terrain (medium hard, and fast). There are algorithms for vertical walls (complex, require precomputation, but very fast). Some algorithms only measure the distance between objects; others support interpenetration, and have a notion of "interpenetration distance" or "negative distance". "Negative distance" has its own set of problems; Prof. Steven Cameron at Oxford has come up with some ideas in that area.

Personally, I think about half the material in the article is bogus. (I used to write physics engines; I seem to be the first one who made a ragdoll physics engine that really worked, back in 1997, and hold a key patent in this area.) Much of the uncited material in this article could be deleted. Game physics and Ragdoll physics have better citations and cover some of the same material. --John Nagle (talk) 04:37, 27 September 2008 (UTC)[reply]

Actually, discussion of this subject belongs in game physics, but since someone put the term "impulse" in the article, it's worth mentioning. In the real world, there are forces, but no impulses. An "impulse" is a simplified abstraction - an infinite force applied over zero time with finite energy, resulting in an instantaneous change in velocity. Collisions between infinitely rigid objects (which do not exist in reality) behave that way. Using this abstraction makes computation faster, although it doesn't look right for big objects. --John Nagle (talk) 17:57, 29 October 2010 (UTC)[reply]

It might be useful to have an image from a game which compares the apperance of an object with its collision model. Maybe something similar to these two images: Models Hitboxes Toomai Glittershine (talk) 03:17, 10 June 2011 (UTC)[reply]

As far as I can see, the section "Optimization" spends a lot of time describing specific techniques and implementation instead of explaining the principles, mentioning existing techniques, discussing general issues and giving an overview. The "Exploiting temporal coherence" subsection seems to explain a particular implementation of sweep and prune, going into more detail than the sweep and prune article itself, and spends little time on temporal coherence in general. The "Pairwise pruning" subsection does not mention that other pairwise pruning methods exists, such as precise but expensive bounding volumes like the convex hull of non-convex objects, and spends very little time on general issues. The "Exact pairwise collision detection" focuses first and foremost on collisions between triangles in 3 dimensions, and other issues, approaches and collision objects are not discussed, such as images and volumes, other geometric representations, and morphing vs. rigid objects.

Furthermore, the organization is inconsistent: While the first couple of subsections suggests starting from the broadest phase of collision detection to a narrower and narrower phase (n-body/broad phase pruning ("Exploiting temporal coherence"), pair-wise pruning, exact pair-wise collision detection), "a priori pruning" is then mentioned, and coming back to "spatial partitioning", which is a broad phase pruning technique.

Finally, the subsections seems to constitute a narrative, making it harder to read, understand subsections independently of each other, as well as making it difficult to edit and add to the section.

I believe that a rewrite of the section is needed, with a focus on the following properties:

• Better organization (such as presenting the different phases of collision detection and then discussing them in order)
• More focus on general issues instead of focusing on particular issues and implementations
• Independent sections

Does anyone disagree? — Preceding unsigned comment added by Poxelcoll (talk • contribs) 16:46, 5 April 2012 (UTC)[reply]

The article could certainly be improved. There's confusion between algorithms that use closed volumetric representations (spheres, boxes, polyhedra) and ones that just look for surface elements in contact ("polygon soup" algorithms). The whole "A posteriori (discrete) versus a priori (continuous)" distinction seems to confuse things further. The psuedo-math under "Temporal coherence" doesn't help much. (The basic idea there is simple. Each object has an bounding box aligned with the axes. The system tracks which boxes are overlapping in each axis as the the boxes move. This is done by keeping sorted lists of boxes for each axis. When two boxes overlap on all axes, the boxes intersect. If most boxes aren't moving much, the updates are very fast.) It's also possible to exploit temporal coherence for collision detection of complex polyhedra in GJK. This is done by using the result from the last calculation of the closest points as the starting point for the search next time. If the objects aren't rotating fast, the compute time is almost constant. All this is what we were doing in the late 1990s, and there's been progress since. --John Nagle (talk) 17:34, 5 April 2012 (UTC)[reply]

I suggest we move the "Bounding boxes" section up to just above "Exploiting temporal coherence" because I think it kind of explains what the sections above says, just much simpler and it will be kind of like a preview.

I haven't read everything under "optimization" mostly because I think its hard to understand it, but from what I have understood from that I read about it I think it is kind of the same.
--Sebbes333 (talk) 13:50, 16 December 2013 (UTC)[reply]

Rewrote that part, using an academic reference. We need a good reference in this article to a respected book on game programming. We have a reference to the seminal paper by Lin on how to do collision detection fast, but later books are clearer. "Real-Time Collision Detection (The Morgan Kaufmann Series in Interactive 3-D Technology)" by Ericson, for example. John Nagle (talk) 05:52, 13 May 2014 (UTC)[reply]

As the article now stands, there are forty-some uses of the pronoun "we", some of which are used in ways generally considered unencylopedic. Per the link from

This article's tone or style may not reflect the encyclopedic tone used on Wikipedia. See Wikipedia's guide to writing better articles for suggestions. (Learn how and when to remove this message)

the relevant text is:

Articles should generally not be written from a first or second person perspective. In prose writing, the first person ("I" and "we") point of view and second person ("you" and "your") point of view typically evoke a strong narrator. While this is acceptable in works of fiction, it is generally unsuitable in an encyclopedia, where the writer should be invisible to the reader.

However, there is also

As with many such guidelines, however, there are exceptions: for instance, in professional mathematics writing, use of the first person plural ("we") as "inclusive we" is widespread.

Now I would argue that the use of "we" in this article is sometimes, but not always the inclusive we; in a mathematics article the author and reader are following a shared line of reasoning, so it is not incorrect to say something like "…and we can see from Lemma 22 that…". Some of the uses here are in the same vein. However, we also have sentences like "In physical simulation, we wish to conduct experiments, such as playing billiards." In these sentences, the assertion is not that the reader wants to conduct billiards experiments; the "we" is a "we" of unspecified person, and could be replaced with the more formal "one".

Still, there may be other reasons to preserve these "we"s that I am overlooking. If the consensus is that there are, please pardon my boldness and remove the template. 98.23.158.64 (talk) 03:30, 27 August 2014 (UTC)[reply]

I have a new scheme for fast collision detection. It relies on a maintenance of the mesh triangle's centroid. Given a single point detector. Just use the 3D Cartesian coordinates. So with sets of centroid, a state of collision can be defined as a certain scalar distance between target and object centroid points. The threshold for action is defined.

Exact triangle intersection is avoided. This method is just as valid of all others because the mesh form is approximative also.

I updated the page. I got help from a sci.math newsgroup mathematician. I will reference him if this method is well received. — Preceding unsigned comment added by Millsseintific (talk • contribs) 13:50, 29 May 2016 (UTC)[reply]

108.31.110.233 (talk) 14:00, 26 May 2016 (UTC)[reply]

I don't see how we can write a fully-fledged article on this, especially as reliable sources (at least on the web) seem to be scarce. Adam9007 (talk) 00:06, 27 March 2018 (UTC)[reply]

• Support, there is no real difference between the two, so a merger seems ideal as it would reduce redundancy between the two articles. ~ Dissident93 ^(talk) 20:05, 12 November 2018 (UTC)[reply]

@OnlyNano: Why does this section have this cleanup tag? Jarble (talk) 04:08, 28 January 2024 (UTC)[reply]

I was wondering the same thing. (It is unreferenced; I added a tag for that.) Cheers! DoctorMatt (talk) 05:13, 28 January 2024 (UTC)[reply]

Don't remember why I added that there, might have been a mistaken placement, as there was some manual-like language later on... I removed it. Thanks for noticing! OnlyNano 15:51, 29 January 2024 (UTC)[reply]

The first section says: This particular example also turns out to be ill conditioned: as a small error in any calculation will cause drastic changes in the final position of the billiard balls.

I think this is mischaracterization of what is actually going on. In physical simulation, a tiny change in the initial condition (or any intermediate step) can make a big change in the evolution of the simulation over time. This is not due to the system being ill conditioned, but because it is chaotic. Any type of change: be it an error, a different approximation or a slight change in initial positions and velocities of the billiard balls would lead to be big change in the outcome.

More importantly, this discussion of change in final position of the billiard balls should not be part of this page as collision detection should focus on ways to detect if the balls touch each other or intersect. Not on how the balls move post a collision. This should be discussed in the context of simulation or specific collision responses. I guess I agree with many previous talk topics on this page. ThothOfTheSouth (talk) 04:06, 7 November 2024 (UTC)[reply]