Collision detection: Difference between revisions

Revision as of 13:49, 13 November 2024

Revision as of 02:22, 16 November 2024

Line 75:

{{manual|section|date=January 2024}}

OnceObjects we'refor donewhich pruning, weapproaches arecould leftnot withrule aout numberthe possibility of candidatea collision pairshave to checkundergo foran exact collision detection computation.

==== Collision detection between convex objects ====

A basic observation is that for any two [[convex set|convex]] objects which are disjoint, one can find a plane in space so that one object lies completely on one side of that plane, and the other object lies on the opposite side of that plane. This allows the development of very fast collision detection algorithms for convex objects.

BetterAccording methodsto havethe since[[Hyperplane separation theorem|separating planes theorem]], for any two disjoint [[convex set|convex]] objects which, there exists a plane so that one object lies completely on one side of that plane, and the other object lies on the opposite side of beenthat developedplane. This Veryproperty fastallows the development of efficient collision detection algorithms between convex objects. Several algorithms are available for finding the closest points on the surface of two convex polyhedral objects - and determining collision. Early work by [[Ming C. Lin]]<ref name=":1">{{cite web |author=Lin, Ming C |year=1993 |title=Efficient Collision Detection for Animation and Robotics (thesis) |url=https://wwwx.cs.unc.edu/~geom/papers/documents/dissertations/lin93.pdf |archive-url=https://web.archive.org/web/20140728124049/https://wwwx.cs.unc.edu/~geom/papers/documents/dissertations/lin93.pdf |archive-date=2014-07-28 |publisher=University of California, Berkeley}}

</ref> that used a variation on the [[simplex algorithm]] from [[linear programming]] and the [[Gilbert-Johnson-Keerthi distance algorithm]]<ref>{{Cite journal |last=Gilbert |first=E.G. |last2=Johnson |first2=D.W. |last3=Keerthi |first3=S.S. |date=1988 |title=A fast procedure for computing the distance between complex objects in three-dimensional space |url=https://graphics.stanford.edu/courses/cs448b-00-winter/papers/gilbert.pdf |journal=IEEE Journal on Robotics and Automation |volume=4 |issue=2 |pages=193–203 |doi=10.1109/56.2083}}</ref> are two examples. These algorithms approach constant time when applied repeatedly to pairs of stationary or slow-moving objects, and every step is initialized from the previous collision check<ref name=":1" />.

Early work in this area involved "[[Separating axis theorem|separating plane]]" methods. Two triangles collide essentially only when they can not be separated by a plane going through three vertices. That is, if the triangles are <math>{v_1,v_2,v_3}</math> and <math>{v_4,v_5,v_6}</math> where each <math>v_j</math> is a vector in <math>\mathbb R^3</math>, then we can take three vertices, <math>v_i,v_j,v_k</math>, find a plane going through all three vertices, and check to see if this is a separating plane. If any such plane is a separating plane, then the triangles are deemed to be disjoint. On the other hand, if none of these planes are separating planes, then the triangles are deemed to intersect. There are twenty such planes.

If the triangles are coplanar, this test is not entirely successful. One can add some extra planes, for instance, planes that are [[normal (geometry)|normal]] to triangle edges, to fix the problem entirely. In other cases, objects that meet at a flat face must necessarily also meet at an angle elsewhere, hence the overall collision detection will be able to find the collision.

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 [[Ming C. Lin]]<ref>{{cite web |author=Lin, Ming C |year=1993 |title=Efficient Collision Detection for Animation and Robotics (thesis) |url=https://wwwx.cs.unc.edu/~geom/papers/documents/dissertations/lin93.pdf |archive-url=https://web.archive.org/web/20140728124049/https://wwwx.cs.unc.edu/~geom/papers/documents/dissertations/lin93.pdf |archive-date=2014-07-28 |publisher=University of California, Berkeley}}

</ref> used a variation on the [[simplex algorithm]] from [[linear programming]]. The [[Gilbert-Johnson-Keerthi distance algorithm]] has superseded that approach. These algorithms approach constant time when applied repeatedly to pairs of stationary or slow-moving objects, when used with starting points from the previous collision check.

The result of all this algorithmic work is that collision detection can be done efficiently for thousands of moving objects in real time on typical personal computers and game consoles.