Collision detection: Difference between revisions

Revision as of 03:28, 9 November 2024

Revision as of 07:09, 10 November 2024

Line 22:

Objects that cannot be definitively separated in the broad phase are passed to the narrow phase. Here, more precise algorithms determine whether these objects actually intersect. If they do, the narrow phase often calculates the exact time and ___location of the intersection.

== Broad Phasephase ==

This phase aims at quickly finding objects or parts of objects for which we can quickly determine that no further collision test is needed. A useful property of such algorithm is that it is [[Output-sensitive algorithm|output sensitive]]. In the context of collision detection this means that the time complexity of the collision detection is proportional to the number of objects that are close to each other. An early example of that is the I-COLLIDE<ref name=":0" /> where the number of exactnarrow phase collision testtests was <math>O(n + m)</math> where <math>n</math> is the number of objects and <math>m</math> is the number of objects at close proximity. This is a significant improvement over the quadratic complexity of the naive approach.

=== Spatial partitioning ===

Alternative algorithms are grouped under the [[spatial partitioning]] umbrella, which includes [[octree]]s (for 3D), [[Quadtree|quadtrees]] (for 2D) [[binary space partitioning]] (or BSP trees) and other, similar approaches. If one splits space into a number of simple cells, and if two objects can be shown not to be in the same cell, then they need not be checked for intersection. Since BSP trees can be precomputed, that approach is well suited to handling walls and fixed obstacles in games. These algorithms are generally older than the algorithms described above.

=== Exploiting temporal coherence ===

Line 67 ⟶ 70:

Many variants of the algorithms are obtained by choosing something other than a sphere for <math>B(T)</math>. If one chooses [[axis-aligned bounding box]]es, one gets AABBTrees. [[Oriented bounding box]] trees are called OBBTrees. Some trees are easier to update if the underlying object changes. Some trees can accommodate higher order primitives such as [[Spline (mathematics)|spline]]s instead of simple triangles.

===Bounding volume hierarchy===

=== Spatial partitioning ===

When the space of the objects we are computing collision for is complex, a single bounding volume may not provide tight enough approximation to considerably reduce the number of exact collision detections we have to perform. In such cases [[Bounding volume hierarchy| Bounding Volume Hierarchy]] (BVH) may be used. A BVH is a tree structure over a set of bounding volumes. 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>

Alternative algorithms are grouped under the [[spatial partitioning]] umbrella, which includes [[octree]]s, [[binary space partitioning]] (or BSP trees) and other, similar approaches. If one splits space into a number of simple cells, and if two objects can be shown not to be in the same cell, then they need not be checked for intersection. Since BSP trees can be precomputed, that approach is well suited to handling walls and fixed obstacles in games. These algorithms are generally older than the algorithms described above.

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

== Narrow Phasephase ==

Objects that cannot be definitively separated in the broad phase are passed to the narrow phase. HereIn this phase, the objects under consideration are relatively close to each other. Still, attempts to quickly determine if a full intersection is needed are employed first. This step is sometimes referred to as mid-phase.<ref name=":col1" /> Once these tests passed (e.g the pair of objects may be colliding) more precise algorithms determine whether these objects actually intersect. If they do, the narrow phase often calculates the exact time and ___location of the intersection.

===Bounding volumes===

A quick way to potentially avoid a needless expensive computation is to check if the bounding volume enclosing the two objects intersect. If they don't, there is not need to check the actual objects. However, if the [[bounding volume]] intersect, the more expensive computation has to be performed. In order for the bounding-volume test to add value, two properties need to be balanced: a) the cost of intersecting the bounding volume needs to be low and b) the bounding volume needs to be tight enough so that the number of 'false positive' intersection will be low. A false positive intersection in this case means that the bounding volume intersect but the actual objects do not. Different bounding volume types offer different trade-offs for these properties.

In order to accelerate collision detection calculation, [[Bounding volume]]s may be used. A bounding volume is a shape that encloses the object of interest but is simpler to compute collisions for.

[[Minimum bounding box#Axis-aligned minimum bounding box|Axis-Align Bounding Boxes (AABB)]] and [[cuboid]]s are popular due to their simplicity and quick intersection tests. <ref>{{cite web |author=Caldwell, Douglas R. |date=2005-08-29 |title=Unlocking the Mysteries of the Bounding Box |url=http://www.stonybrook.edu/libmap/coordinates/seriesa/no2/a2.htm |url-status=dead |archive-url=https://web.archive.org/web/20120728180104/http://www.stonybrook.edu/libmap/coordinates/seriesa/no2/a2.htm |archive-date=2012-07-28 |access-date=2014-05-13 |publisher=US Army Engineer Research & Development Center, Topographic Engineering Center, Research Division, Information Generation and Management Branch}}</ref> ABounding volumes such as [[Minimum bounding box#Arbitrarily inoriented aminimum videobounding gamebox| isOriented sometimesBounding calledBoxes a(OBB)]], [[Bounding volume#HitboxCommon types|HitboxK-DOPs]]. Otherand boundingConvex-hulls volumesoffer commonlya usedtighter forapproximation collisionof detectionthe includeenclosed [[Convexshape hull]]at andthe [[Minimumexpense boundingof box#Arbitrarilya orientedmore minimumelaborate boundingintersection box| Oriented Bounding Boxes (OBB)]]test.

Bounding volumes are typically used in the early (pruning) stage of collision detection, so that only objects with overlapping bounding volumes need be compared in detail.<ref>{{cite journal |author=Gan B, Dong Q |date=2022 |title=An improved optimal algorithm for collision detection of hybrid hierarchical bounding box |url=https://www.researchgate.net/publication/348937861 |journal=Evolutionary Intelligence |volume=15 |issue=4 |pages=2515–2527 |doi=10.1007/s12065-020-00559-6}}</ref> Computing collision or overlap between bounding volumes involves additional computations, therefore, in order for it to beneficial we need the bounding volume to be relatively tight and the computation overhead to due the collisions to be low.

=== Bounding Volume Hierarchy ===

When the space of the objects we are computing collision for is complex, a single bounding volume may not provide tight enough approximation to considerably reduce the number of exact collision detections we have to perform. In such cases [[Bounding volume hierarchy| Bounding Volume Hierarchy]] (BVH) may be used. A BVH is a tree structure over a set of bounding volumes. 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.

== Narrow Phase ==

Objects that cannot be definitively separated in the broad phase are passed to the narrow phase. Here, more precise algorithms determine whether these objects actually intersect. If they do, the narrow phase often calculates the exact time and ___location of the intersection.

=== Exact pairwise collision detection ===