Collision detection: Difference between revisions

Revision as of 04:56, 9 September 2024

Revision as of 00:44, 13 October 2024

Line 116:

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.

===Bounding boxesvolumes===

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.

[[Bounding box]]es (or [[bounding volume]]s) are most often a 2D rectangle or 3D [[cuboid]], but other shapes are possible. A bounding box in a video game is sometimes called a [[#Hitbox|Hitbox]].

The bounding diamond, the minimum bounding parallelogram, the convex hull, the bounding circle or bounding ball, and the bounding ellipse have all been tried, but bounding boxes remain the most popular due to their simplicity.<ref>{{cite web |

[[Minimum bounding box#Axis-aligned minimum bounding box|Axis-Align Bounding Boxes (AABB)]] bounding boxes and [[cuboid]]s are popular due to their simplicity <ref>{{cite web |

url=http://www.stonybrook.edu/libmap/coordinates/seriesa/no2/a2.htm |

title=Unlocking the Mysteries of the Bounding Box |

Line 127 ⟶ 128:

archive-url=https://web.archive.org/web/20120728180104/http://www.stonybrook.edu/libmap/coordinates/seriesa/no2/a2.htm |

archive-date=2012-07-28 |

url-status=dead }}</ref> Bounding boxesA arebounding typically usedbox in thea earlyvideo (pruning)game stageis ofsometimes called a [[#Hitbox|Hitbox]]. Other bounding volumes commonly used for collision detection, soinclude that[[Convex onlyhull]] objectsand with overlapping[[Minimum bounding boxesbox#Arbitrarily needoriented beminimum comparedbounding inbox| detail.<ref>{{citeOriented journalBounding Boxes (OBB)]].

Bounding volumes are typically used in the early (pruning) stage of collision detection, so that only objects with overlapping bounding boxes need be compared in detail.<ref>{{cite journal

| author= Gan B, Dong Q

| title= An improved optimal algorithm for collision detection of hybrid hierarchical bounding box

Line 136 ⟶ 139:

| pages= 2515–2527

| doi= 10.1007/s12065-020-00559-6

| url= https://www.researchgate.net/publication/348937861 }}</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.

=== Triangle centroid segments ===