Collision detection: Difference between revisions

Revision as of 02:22, 16 November 2024

Revision as of 03:18, 16 November 2024

Line 78:

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

According to the [[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 that plane. This property allows 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 such 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" />.

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.