Collision detection: Difference between revisions

Revision as of 15:17, 11 November 2024

Revision as of 03:42, 13 November 2024

Line 23:

== Broad phase ==

This phase aims at quickly finding objects or parts of objects for which weit can be quickly determinedetermined that no further collision test is needed. A useful property of such algorithmapproach 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 required narrow phase collision tests 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 ===

AlternativeSeveral algorithmsapproaches arecan 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. SinceDynamic BSPscenes treesand candeformable beobjects precomputed,require thatupdating approachthe ispartitioning wellwhich suitedcan toadd handling walls and fixed obstacles in gamesoverhead. These algorithms are generally older than the algorithms described above.

===Bounding volume hierarchy===

When[[Bounding thevolume spacehierarchy|Bounding ofVolume theHierarchy]] objects(BVH) wea aretree computingstructure collisionover fora set of [[Collision detection#Bounding volumes|bounding volumes]]. Collision is complex,determined by doing a singletree traversal starting from the root. If a the bounding volume mayof notthe provideroot tightdoesn't enoughintersect approximationwith tothe considerablyobject reduceof interest, the numbertraversal ofcan exactbe collisionstopped. detectionsIf, wehowever havethere tois perform.an Inintersection, suchthe casestraversal [[Boundingproceeds volumeand hierarchy|checks Boundingthe Volumebranches Hierarchy]]for (BVH)each maythere beis an usedintersection. ABranches BVHfor which there is ano treeintersection structurewith overthe abounding setvolume ofcan boundingbe volumesculled 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.

=== Exploiting temporal coherence ===

{{Multiple issues|{{Technical|section|date=March 2020}}

Line 70 ⟶ 74:

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===

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 ==