Collision detection: Difference between revisions

Revision as of 21:21, 22 November 2024

Revision as of 03:35, 28 November 2024

Line 29:

===Bounding volume hierarchy===

[[Bounding volume hierarchy|Bounding Volume Hierarchy]] (BVH) a tree structure over a set of [[Collision detection#Bounding volumes|bounding volumes]]. Collision is determined by doing a tree traversal starting from the root. If the bounding volume of the root doesn't intersect with the object of interest, the traversal can be stopped. If, however there is an intersection, the traversal proceeds and checks the branches for each there is an intersection. Branches for which there is no intersection with the bounding volume can be culled from further intersection test. Therefore multiple objects can be determined to not intersect at once. BVH can be used with deformable objects such as cloth or soft-bodies but the volume hierarchy has to be adjusted as the shape deforms. For deformable objects we need to be concerned about self-collisions or self intersections. BVH can be used for that end as well. Collision between two objects is computed by computing intersection between the bounding volumes of the root of the tree as there are collision we dive into the sub-trees that intersect. Exact collisions between the actual objects, or its parts (often triangles of a [[triangle mesh]]) need to be computed only between intersecting leaves.<ref>

{{cite journal |last1=Klosowski |first1=James T |last2=Held |first2=Martin |last3=Mitchell |first3=Joseph S.B. |last4=Sowizral |first4=Henry |last5=Zikan |first5=Karel |date=1998 |title=Efficient collision detection using bounding volume hierarchies of k-DOPs |journal=IEEE Transactions on Visualization and Computer Graphics |publisher=IEEE |volume=4 |issue=1 |pages=21–36 |doi=10.1109/2945.675649}}

</ref> The same approach works for pair wise collision and self-collisions.

Line 79:

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

According to the [[Hyperplane separation theorem|separating planes theorem]], for any two disjoint [[convex set|convex]] objects, 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 |last1=Gilbert |first1=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.