Collision detection - Revision history

imported>Morgan22202: /* growthexperiments-addlink-summary-summary:3|0|0 */

2025-12-27T01:00:33Z

growthexperiments-addlink-summary-summary:3|0|0

← Previous revision		Revision as of 01:00, 27 December 2025
Line 29:		Line 29:

	===Bounding volume hierarchy===		===Bounding volume hierarchy===
	[[Bounding volume hierarchy\|Bounding Volume Hierarchy]] (BVH) is a tree structure over a set of [[#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>		[[Bounding volume hierarchy\|Bounding Volume Hierarchy]] (BVH) is a tree structure over a set of [[#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}}		{{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.		</ref> The same approach works for pair wise collision and self-collisions.
Line 85:		Line 85:
	Where most of the objects involved are fixed, as is typical of video games, a priori methods using precomputation can be used to speed up execution.		Where most of the objects involved are fixed, as is typical of video games, a priori methods using precomputation can be used to speed up execution.

	Pruning is also desirable here, both ''n''-body pruning and pairwise pruning, but the algorithms must take time and the types of motions used in the underlying physical system into consideration.		Pruning is also desirable here, both ''n''-body pruning and pairwise pruning, but the algorithms must take time and the types of motions used in the underlying [[physical system]] into consideration.

	When it comes to the exact pairwise collision detection, this is highly trajectory dependent, and one almost has to use a numerical [[root-finding algorithm]] to compute the instant of impact.		When it comes to the exact pairwise collision detection, this is highly trajectory dependent, and one almost has to use a numerical [[root-finding algorithm]] to compute the instant of impact.
Line 92:		Line 92:

	=== Triangle centroid segments ===		=== Triangle centroid segments ===
	A [[triangle mesh]] object is commonly used in 3D body modeling. Normally the collision function is a triangle to triangle intercept or a bounding shape associated with the mesh. A triangle centroid is a [[center of mass]] location such that it would balance on a pencil tip. The simulation need only add a centroid dimension to the physics parameters. Given centroid points in both object and target it is possible to define the line segment connecting these two points.		A [[triangle mesh]] object is commonly used in 3D body modeling. Normally the collision function is a triangle to triangle intercept or a bounding shape associated with the mesh. A triangle centroid is a [[center of mass]] location such that it would balance on a pencil tip. The simulation need only add a centroid dimension to the physics parameters. Given centroid points in both object and target it is possible to define the [[line segment]] connecting these two points.

	The position vector of the centroid of a triangle is the average of the position vectors of its vertices. So if its vertices have Cartesian coordinates <math>(x_1,y_1,z_1)</math>, <math>(x_2,y_2,z_2)</math> and <math>(x_3,y_3,z_3)</math> then the centroid is <math>\left(\frac{(x_1+x_2+x_3)}{3},\frac{(y_1+y_2+y_3)}{3},\frac{(z_1+z_2+z_3)}{3}\right)</math>.		The position vector of the centroid of a triangle is the average of the position vectors of its vertices. So if its vertices have Cartesian coordinates <math>(x_1,y_1,z_1)</math>, <math>(x_2,y_2,z_2)</math> and <math>(x_3,y_3,z_3)</math> then the centroid is <math>\left(\frac{(x_1+x_2+x_3)}{3},\frac{(y_1+y_2+y_3)}{3},\frac{(z_1+z_2+z_3)}{3}\right)</math>.

imported>Dabmasterars: /* Hitbox */ Added example image of a hitbox.

2025-11-14T16:52:18Z

Hitbox: Added example image of a hitbox.

imported>Zharoldr: ce

2025-04-27T01:54:44Z

Show changes

← Previous revision		Revision as of 16:52, 14 November 2025
Line 3:		Line 3:
	{{redirect\|Hitbox}}		{{redirect\|Hitbox}}
	{{Multiple issues\|{{Technical\|section\|date=March 2020}}		{{Multiple issues\|{{Technical\|section\|date=March 2020}}
	{{Tone\|section~~\|{{subst:March 2020}}~~\|date=August 2014}}}}		{{Tone\|section\|date=August 2014}}}}

	'''Collision detection''' is the [[computational problem]] of detecting an [[Intersection (geometry)\|intersection]] of two or more objects in virtual space. More precisely, it deals with the questions of ''if'', ''when'' and ''where'' two or more objects intersect. Collision detection is a classic problem of [[computational geometry]] with applications in [[computer graphics]], [[physical simulation]], [[video game]]s, [[robotics]] (including [[autonomous driving]]) and [[computational physics]]. Collision detection [[algorithm]]s can be divided into operating on 2D or 3D spatial objects.<ref>{{cite journal\|url=https://hal.inria.fr/inria-00394479/document\|title=Collision Detection for Deformable Objects\|year=2005\|doi=10.1111/j.1467-8659.2005.00829.x\|last1=Teschner\|first1=M.\|last2=Kimmerle\|first2=S.\|last3=Heidelberger\|first3=B.\|last4=Zachmann\|first4=G.\|last5=Raghupathi\|first5=L.\|last6=Fuhrmann\|first6=A.\|last7=Cani\|first7=M.-P.\|last8=Faure\|first8=F.\|last9=Magnenat-Thalmann\|first9=N.\|last10=Strasser\|first10=W.\|last11=Volino\|first11=P.\|journal=Computer Graphics Forum\|volume=24\|pages=61–81\|s2cid=1359430\|citeseerx=10.1.1.58.2505}}</ref>		'''Collision detection''' is the [[computational problem]] of detecting an [[Intersection (geometry)\|intersection]] of two or more objects in virtual space. More precisely, it deals with the questions of ''if'', ''when'' and ''where'' two or more objects intersect. Collision detection is a classic problem of [[computational geometry]] with applications in [[computer graphics]], [[physical simulation]], [[video game]]s, [[robotics]] (including [[autonomous driving]]) and [[computational physics]]. Collision detection [[algorithm]]s can be divided into operating on 2D or 3D spatial objects.<ref>{{cite journal\|url=https://hal.inria.fr/inria-00394479/document\|title=Collision Detection for Deformable Objects\|year=2005\|doi=10.1111/j.1467-8659.2005.00829.x\|last1=Teschner\|first1=M.\|last2=Kimmerle\|first2=S.\|last3=Heidelberger\|first3=B.\|last4=Zachmann\|first4=G.\|last5=Raghupathi\|first5=L.\|last6=Fuhrmann\|first6=A.\|last7=Cani\|first7=M.-P.\|last8=Faure\|first8=F.\|last9=Magnenat-Thalmann\|first9=N.\|last10=Strasser\|first10=W.\|last11=Volino\|first11=P.\|journal=Computer Graphics Forum\|volume=24\|pages=61–81\|s2cid=1359430\|citeseerx=10.1.1.58.2505}}</ref>

	== Overview ==		== Overview ==
	[[Image:~~Billiards balls~~.~~jpg~~\|~~right\|200px~~\|thumb\|Billiards balls hitting each other in a virtual space are a classic example where collision detection computations are needed.]]Collision detection is closely linked to calculating the [[Euclidean distance\|distance]] between objects, as ~~two~~ objects ~~(or more) intersect~~ when the distance between them ~~reaches~~ zero ~~or even becomes negative~~.<ref>{{Cite book \|url=https://www.csun.edu/~ctoth/Handbook/HDCG3.html \|title=Handbook of discrete and computational geometry \|date=2018 \|publisher=CRC Press, Taylor & Francis Group, a Chapman & Hall book \|isbn=978-1-4987-1139-5 \|editor-last=Goodman \|editor-first=Jacob E. \|edition=3rd \|series=Discrete mathematics and its applications \|location=Boca Raton London New York \|chapter=39 \|editor-last2=O'Rourke \|editor-first2=Joseph \|editor-last3=Tóth \|editor-first3=Csaba D.}}</ref> Negative ~~distance indicates~~ that one object has penetrated another. Performing collision detection requires more context than just the distance between the objects.		[[Image:FooBillard 3.0a on Linux sshot20040807.png\|upright=1.3\|thumb\|Billiards balls hitting each other in a virtual space are a classic example where collision detection computations are needed.]]Collision detection is closely linked to calculating the [[Euclidean distance\|distance]] between objects, as objects collide when the distance between them is less than or equal to zero.<ref>{{Cite book \|url=https://www.csun.edu/~ctoth/Handbook/HDCG3.html \|title=Handbook of discrete and computational geometry \|date=2018 \|publisher=CRC Press, Taylor & Francis Group, a Chapman & Hall book \|isbn=978-1-4987-1139-5 \|editor-last=Goodman \|editor-first=Jacob E. \|edition=3rd \|series=Discrete mathematics and its applications \|location=Boca Raton London New York \|chapter=39 \|editor-last2=O'Rourke \|editor-first2=Joseph \|editor-last3=Tóth \|editor-first3=Csaba D.}}</ref> Negative distances indicate that one object has penetrated another. Performing collision detection requires more context than just the distance between the objects.

	Accurately identifying the points of contact on both objects' surfaces is also essential for the computation of a physically accurate [[collision response]]. The complexity of this task increases with the level of detail in the objects' representations: the more intricate the model, the greater the computational cost.<ref name=":col0">{{Cite book \|last1=Andrews \|first1=Sheldon \|last2=Erleben \|first2=Kenny \|last3=Ferguson \|first3=Zachary \|chapter=Contact and friction simulation for computer graphics \|date=2022-08-02 \|title=ACM SIGGRAPH 2022 Courses \|chapter-url=https://dl.acm.org/doi/10.1145/3532720.3535640 \|language=en \|publisher=ACM \|pages=1–172 \|doi=10.1145/3532720.3535640 \|isbn=978-1-4503-9362-1}}</ref>		Accurately identifying the points of contact on both objects' surfaces is also essential for the computation of a physically accurate [[collision response]]. The complexity of this task increases with the level of detail in the objects' representations: the more intricate the model, the greater the computational cost.<ref name=":col0">{{Cite book \|last1=Andrews \|first1=Sheldon \|last2=Erleben \|first2=Kenny \|last3=Ferguson \|first3=Zachary \|chapter=Contact and friction simulation for computer graphics \|date=2022-08-02 \|title=ACM SIGGRAPH 2022 Courses \|chapter-url=https://dl.acm.org/doi/10.1145/3532720.3535640 \|language=en \|publisher=ACM \|pages=1–172 \|doi=10.1145/3532720.3535640 \|isbn=978-1-4503-9362-1}}</ref>
Line 40:		Line 40:
	=== Pairwise pruning ===		=== Pairwise pruning ===
	{{Multiple issues\|{{Technical\|section\|date=March 2020}}		{{Multiple issues\|{{Technical\|section\|date=March 2020}}
	{{Tone\|section~~\|{{subst:March 2020}}~~\|date=January 2024}}		{{Tone\|section\|date=January 2024}}
	{{Unreferenced section\|date=July 2024}}\|section=y}}		{{Unreferenced section\|date=July 2024}}\|section=y}}

Line 92:		Line 92:

	=== Triangle centroid segments ===		=== Triangle centroid segments ===
	A [[triangle mesh]] object is commonly used in 3D body modeling. Normally the collision function is a triangle to triangle intercept or a bounding shape associated with the mesh. A triangle centroid is a center of mass location such that it would balance on a pencil tip. The simulation need only add a centroid dimension to the physics parameters. Given centroid points in both object and target it is possible to define the line segment connecting these two points.		A [[triangle mesh]] object is commonly used in 3D body modeling. Normally the collision function is a triangle to triangle intercept or a bounding shape associated with the mesh. A triangle centroid is a [[center of mass]] location such that it would balance on a pencil tip. The simulation need only add a centroid dimension to the physics parameters. Given centroid points in both object and target it is possible to define the line segment connecting these two points.

	The position vector of the centroid of a triangle is the average of the position vectors of its vertices. So if its vertices have Cartesian coordinates <math>(x_1,y_1,z_1)</math>, <math>(x_2,y_2,z_2)</math> and <math>(x_3,y_3,z_3)</math> then the centroid is <math>\left(\frac{(x_1+x_2+x_3)}{3},\frac{(y_1+y_2+y_3)}{3},\frac{(z_1+z_2+z_3)}{3}\right)</math>.		The position vector of the centroid of a triangle is the average of the position vectors of its vertices. So if its vertices have Cartesian coordinates <math>(x_1,y_1,z_1)</math>, <math>(x_2,y_2,z_2)</math> and <math>(x_3,y_3,z_3)</math> then the centroid is <math>\left(\frac{(x_1+x_2+x_3)}{3},\frac{(y_1+y_2+y_3)}{3},\frac{(z_1+z_2+z_3)}{3}\right)</math>.
Line 108:		Line 108:
	Some iterate the linear interpolation ([[Newton's method]]) to calculate the time of collision with a much higher precision than the rest of the simulation. Collision detection utilizes time coherence to allow even finer time steps without much increasing CPU demand, such as in [[air traffic control]].		Some iterate the linear interpolation ([[Newton's method]]) to calculate the time of collision with a much higher precision than the rest of the simulation. Collision detection utilizes time coherence to allow even finer time steps without much increasing CPU demand, such as in [[air traffic control]].

	After an inelastic collision, special states of sliding and resting can occur and, for example, the [[Open Dynamics Engine]] uses constraints to simulate them. Constraints avoid inertia and thus instability. Implementation of rest by means of a [[scene graph]] avoids drift.		After an [[inelastic collision]], special states of sliding and resting can occur and, for example, the [[Open Dynamics Engine]] uses constraints to simulate them. Constraints avoid inertia and thus instability. Implementation of rest by means of a [[scene graph]] avoids drift.

	In other words, physical simulators usually function one of two ways: where the collision is detected ''[[Empirical evidence\|a posteriori]]'' (after the collision occurs) or ''[[A priori and a posteriori\|a priori]]'' (before the collision occurs). In addition to the ''a posteriori'' and ''a priori'' distinction, almost all modern collision detection algorithms are broken into a hierarchy of algorithms. Often the terms "discrete" and "continuous" are used rather than ''a posteriori'' and ''a priori''.		In other words, physical simulators usually function one of two ways: where the collision is detected ''[[Empirical evidence\|a posteriori]]'' (after the collision occurs) or ''[[A priori and a posteriori\|a priori]]'' (before the collision occurs). In addition to the ''a posteriori'' and ''a priori'' distinction, almost all modern collision detection algorithms are broken into a hierarchy of algorithms. Often the terms "discrete" and "continuous" are used rather than ''a posteriori'' and ''a priori''.
Line 135:		Line 135:
	Because games do not need to mimic actual physics, stability is not as much of an issue. Almost all games use ''a posteriori'' collision detection, and collisions are often resolved using very simple rules. For instance, if a character becomes embedded in a wall, they might be simply moved back to their last known good location. Some games will calculate the distance the character can move before getting embedded into a wall, and only allow them to move that far.		Because games do not need to mimic actual physics, stability is not as much of an issue. Almost all games use ''a posteriori'' collision detection, and collisions are often resolved using very simple rules. For instance, if a character becomes embedded in a wall, they might be simply moved back to their last known good location. Some games will calculate the distance the character can move before getting embedded into a wall, and only allow them to move that far.

	In many cases for video games, approximating the characters by a point is sufficient for the purpose of collision detection with the environment. In this case, [[binary space partitioning]] trees provide a viable, efficient and simple algorithm for checking if a point is embedded in the scenery or not. Such a data structure can also be used to handle "resting position" situation gracefully when a character is running along the ground. Collisions between characters, and collisions with projectiles and hazards, are treated separately.		In many cases for video games, approximating the characters by a point is sufficient for the purpose of collision detection with the environment. In this case, [[binary space partitioning]] trees provide a viable, efficient and simple algorithm for checking if a point is embedded in the scenery or not. Such a [[data structure]] can also be used to handle "resting position" situation gracefully when a character is running along the ground. Collisions between characters, and collisions with projectiles and hazards, are treated separately.

	A robust simulator is one that will react to any input in a reasonable way. For instance, if we imagine a high speed [[Racing game\|racecar video game]]~~, from one simulation step to the next~~, it is conceivable that the cars would advance a substantial distance along the race track. If there is a shallow obstacle on the track (such as a brick wall), it is not entirely unlikely that the car will completely leap over it, and this is very undesirable. In other instances, the "fixing" that posteriori algorithms require isn't implemented correctly, resulting in [[software bug\|bug]]s that can trap characters in walls or allow them to pass through them and fall into an endless void where there may or may not be a deadly [[bottomless pit (video gaming)\|bottomless pit]], sometimes referred to as "black hell", "blue hell", or "green hell", depending on the predominant color. These are the hallmarks of a failing collision detection and physical simulation system. ''[[Big Rigs: Over the Road Racing]]'' is an infamous example of a game with a failing or possibly missing collision detection system.		A robust simulator is one that will react to any input in a reasonable way. For instance, if we imagine a high speed [[Racing game\|racecar video game]], it is conceivable that the cars would advance a substantial distance along the race track from one simulation step to the next. If there is a shallow obstacle on the track (such as a brick wall), it is not entirely unlikely that the car will completely leap over it, and this is very undesirable. In other instances, the "fixing" that posteriori algorithms require isn't implemented correctly, resulting in [[software bug\|bug]]s that can trap characters in walls or allow them to pass through them and fall into an endless void where there may or may not be a deadly [[bottomless pit (video gaming)\|bottomless pit]], sometimes referred to as "black hell", "blue hell", or "green hell", depending on the predominant color. These are the hallmarks of a failing collision detection and physical simulation system. ''[[Big Rigs: Over the Road Racing]]'' is an infamous example of a game with a failing or possibly missing collision detection system.

	==== Hitbox ====<!-- Deleted image removed: [[File:GearheadsCollisionBoxSize.png\|thumb\|A [[Debug menu\|debug]] dialogue box in ''[[Gearheads (video game)\|Gearheads]]'' controlling an object's hitbox {{Deletable file-caption\|Tuesday, 9 July 2024\|F7}}]] -->		==== Hitbox ====<!-- Deleted image removed: [[File:GearheadsCollisionBoxSize.png\|thumb\|A [[Debug menu\|debug]] dialogue box in ''[[Gearheads (video game)\|Gearheads]]'' controlling an object's hitbox {{Deletable file-caption\|Tuesday, 9 July 2024\|F7}}]] -->
	<!-- Deleted image removed: [[File:GearheadsCollisionBox.png\|thumb\|The hitbox of a ''[[Gearheads (video game)\|Gearheads]]'' toy, controlled by the above screen {{Deletable file-caption\|Tuesday, 9 July 2024\|F7}}]] -->		<!-- Deleted image removed: [[File:GearheadsCollisionBox.png\|thumb\|The hitbox of a ''[[Gearheads (video game)\|Gearheads]]'' toy, controlled by the above screen {{Deletable file-caption\|Tuesday, 9 July 2024\|F7}}]] -->[[File:Fighter hitbox.svg\|thumb\|upright\|Example of hitboxes of an attacking character in a [[fighting game]]. The green hitbox represents character collision zone, the red hitbox represents the attack's hit zone.]]

	A '''hitbox''' is an invisible shape commonly used in [[video game]]s for real-time collision detection; it is a type of bounding box. It is often a rectangle (in 2D games) or [[cuboid]] (in 3D) that is attached to and follows a point on a visible object (such as a model or a sprite). Circular or spheroidial shapes are also common, though they are still most often called "boxes". It is common for animated objects to have hitboxes attached to each moving part to ensure accuracy during motion.<ref>{{cite web\|title=Hitbox\|work=Valve Developer Community\|url=http://developer.valvesoftware.com/wiki/Hitbox\|publisher=[[Valve Corporation\|Valve]]\|access-date=18 September 2011}}</ref>{{Unreliable source?\|date=March 2018\|Wikis are not suitable sources.}}		A '''hitbox''' is an invisible shape commonly used in [[video game]]s for real-time collision detection; it is a type of bounding box. It is often a rectangle (in 2D games) or [[cuboid]] (in 3D) that is attached to and follows a point on a visible object (such as a model or a sprite). Circular or spheroidial shapes are also common, though they are still most often called "boxes". It is common for animated objects to have hitboxes attached to each moving part to ensure accuracy during motion.<ref>{{cite web\|title=Hitbox\|work=Valve Developer Community\|url=http://developer.valvesoftware.com/wiki/Hitbox\|publisher=[[Valve Corporation\|Valve]]\|access-date=18 September 2011}}</ref>{{Unreliable source?\|date=March 2018\|Wikis are not suitable sources.}}