Darwinbots3/Physics - Revision history

Numsgil at 09:56, 16 May 2009

2009-05-16T09:56:22Z

Numsgil: Replacing page with 'Darwinbots3/Physics/Response Collision Response - Article covers math behind responding to collisions Darwinbots3/Physics/Detection Collision Detection - Article covers...'

2009-05-16T09:55:23Z

Replacing page with 'Darwinbots3/Physics/Response Collision Response - Article covers math behind responding to collisions Darwinbots3/Physics/Detection Collision Detection - Article covers...'

Show changes

Numsgil: /* Linked list sort */

2009-05-16T09:50:21Z

‎Linked list sort

Numsgil at 09:47, 16 May 2009

2009-05-16T09:47:18Z

Numsgil: /* Multiple collisions */

2009-04-29T01:00:58Z

‎Multiple collisions

Numsgil: /* Multiple collisions */

2009-04-28T22:00:09Z

‎Multiple collisions

Numsgil: /* Multiple collisions */

2009-04-28T21:28:04Z

‎Multiple collisions

Numsgil: /* Multiple collisions */

2009-04-28T21:27:38Z

‎Multiple collisions

Numsgil: /* Multiple collisions */

2009-04-28T21:26:34Z

‎Multiple collisions

Numsgil: /* Multiple collisions */

2009-04-28T21:25:55Z

‎Multiple collisions

← Older revision		Revision as of 09:56, 16 May 2009
Line 1:		Line 1:
−	[[Darwinbots3/Physics/Response Collision Response]] - Article covers math behind responding to collisions	+	* [[Darwinbots3/Physics/Response \| Collision Response]] - Article covers math behind responding to collisions
−	[[Darwinbots3/Physics/Detection Collision Detection]] - Article covers methods of broad and narrow phase collision detection for simple 2D shapes	+	* [[Darwinbots3/Physics/Detection \| Collision Detection]] - Article covers methods of broad and narrow phase collision detection for simple 2D shapes

@@ Line 249: / Line 249: @@
 Naively sorting the lists every cycle is a <math>O(m n log(n))</math> operation.  However by saving the lists between cycles and realizing that most bodies will not have changed order too much (temporal and spatial coherence), the sort comes down to a <math>O(m n)</math> operation.
-So similar to grid methods the average case should be <math>O(n)</math>, though in practice grid methods should do a better job of culling collisions.  If multiple axis are used and chosen well, I ''think'' the worst case performance becomes <math>O(m n log(n))</math>.
+So similar to grid methods the average case should be <math>O(n)</math>, though in practice grid methods should do a better job of culling collisions.
 It is usually a good idea to choose axis that are not the x or y axis, since bodies will tend to clump along the y axis (think lots of balls sitting at the bottom of the screen) and x axis (think a vertical stack of bodies).  If two axis are used, they should be orthogonal to each other.  More than two I'm not sure, but probably evenly distributed on the unit circle is a good idea.

← Older revision		Revision as of 09:47, 16 May 2009
Line 179:		Line 179:

	Which can then be solved in <math>O(N^3)</math>.		Which can then be solved in <math>O(N^3)</math>.
		+
		+	= Collision detection =
		+	Consider the case where all objects in the world are static (not moving). Suppose we want to find a list of bodies which ''might'' be colliding. This list might have false positives, but it's much cheaper than the complete collision test. Finding this list of ''maybe'' collisions is called '''broad phase collision detection'''. The complete collision test where the possibility of false positives and false negatives is eliminated is called '''narrow phase collision detection'''.
		+
		+	== Broad phase collision detection ==
		+	This is a mostly comprehensive list of methods for broad phase collision detection:
		+
		+	=== Naive ===
		+	The naive broad phase algorithm is just to assume that all bodies might be colliding with each other. The first body is tested against the second, third, fourth, ... nth. The second body is tested against the third, fourth, ... nth. For a total of <math>\frac{n^2}{2}</math> narrow phase collision checks.
		+
		+	The primary advantage to this method is its simplicity to implement and no memory overhead. The downside is that the operation is <math>O(n^2)</math>, which makes anything more than about 1000 bodies too slow.
		+
		+	=== Uniform grid ===
		+	A '''uniform grid''' (also sometimes called a '''spatial hash''') divides the universe into a regular grid of boxes, like a chess board. Each grid square has a list of bodies which are at least partially inside that grid square.
		+
		+	If there are more bodies than grid squares:
		+
		+	For each grid square
		+	For each pair of bodies in that grid square
		+	Pass that pair on to narrow phase collision detection
		+
		+	(Watch out for colliding the same pair more than once).
		+
		+	If there are more grid squares than bodies:
		+
		+	For each body
		+	For each grid square that body overlaps
		+	For each otherBody in the current gridSquare
		+	Pass this body and otherBody on to narrow phase
		+
		+	(Again watch out for colliding the same pair more than once. If each body has a unique serial number, you can just test that the serial number for this body is < the serial number for otherBody).
		+
		+	Worst case performance is still <math>O(n^2)</math> in the case where all bodies are in the same grid square. Average case performance is <math>O(n)</math>. It's important to choose an appropriate size for the grid squares. Too large and it's too permissive about passing collisions on to narrow phase. Too small and it starts to waste lots of memory. It also works best when the bodies are all approximately the same size.
		+
		+	Sources: [http://www.metanetsoftware.com/technique/tutorialB.html 1] [http://freespace.virgin.net/hugo.elias/models/m_colide.htm 2]
		+
		+	=== Hierarchical grid ===
		+	An extension of uniform grids from above. A grid size is chosen to be as small as possible without burning too much memory. Above this is constructed a larger grid such that four of the smaller grid squares fit in one of these larger grid squares. This continues recursively up to the very top level. Bodies are placed on the smallest grid level such that they take up only 4 or fewer grid squares.
		+
		+	The primary advantage over uniform grids is a better handling of large bodies. Worst case performance is still <math>O(n^2)</math>, though it becomes harder to reach worst case. Average case is still <math>O(n)</math>.
		+
		+	=== Linked list sort ===
		+	By using the separating axis theorem, we know that a necessary (but not sufficient) effect of two bodies colliding is that their projections onto an arbitrary axis also collide. If we project all bodies on to arbitrary axes, and then sort the result in a linked list, it becomes an <math>O(n)</math> operation to find possible collision pairs. Adding axis allows the test to become more accurate at the cost of handling more objects.
		+
		+	The algorithm looks like:
		+
		+	For each body
		+	Find projection of body on to axis. Projection is in form of interval (min and max bounds)
		+	Add min bounds to linked list
		+	Add max bounds to linked list
		+
		+	Sort the list(s)
		+
		+	For each list
		+	For each entry in list
		+	if entry is a min bounds
		+	body = body which created entry
		+	otherEntry = entry->next
		+	while(otherEntry != max bounds for body)
		+	add body and otherEntry's body to this list's collection of possible collisions
		+	otherEntry = entry->next
		+
		+	pass to narrow phase any collision pairs which appear in all lists' collections of possible collisions
		+
		+	The primary advantage over grid methods is memory use. The linked lists scale linearly with the number of bodies. Likewise finite bounds for the universe aren't necessary, so it becomes a reasonable method for things like a simulation of stars.
		+
		+	If the axis are chosen poorly it can degenerate in to <math>O(n^2)</math>, though the more axis chosen the less the chance for this. Too many axis can also be a problem too, since searching all the possible collision lists is an <math>O(m^2)</math> operation for <math>m</math> lists. Though this can be made into a <math>O(n)</math> order operation by using a hash table to find hash conflicts between the possible collision lists.
		+
		+	Naively sorting the lists every cycle is a <math>O(m n log(n))</math> operation. However by saving the lists between cycles and realizing that most bodies will not have changed order too much (temporal and spatial coherence), the sort comes down to a <math>O(m n)</math> operation.
		+
		+	So similar to grid methods the average case should be <math>O(n)</math>, though in practice grid methods should do a better job of culling collisions. If multiple axis are used and chosen well, I ''think'' the worst case performance becomes <math>O(m n log(n))</math>.
		+
		+	It is usually a good idea to choose axis that are not the x or y axis, since bodies will tend to clump along the y axis (think lots of balls sitting at the bottom of the screen) and x axis (think a vertical stack of bodies). If two axis are used, they should be orthogonal to each other. More than two I'm not sure, but probably evenly distributed on the unit circle is a good idea.
		+
		+	=== Hash sort ===
		+	Sort of a combination of the grid methods and the linked list sort. Just like with the linked list sort bodies are projected against arbitrary axes. However instead of adding the results to a linked list, each axis has a hash table. Possible collisions are from hash collisions.
		+
		+	The primary advantage over a linked list is that the sorting is done implicitly, which eliminates a large amount of computation. The primary disadvantage over a linked list is that the universe must be finitely bounded like with grid methods.
		+
		+	Just like with a grids, a hierarchical hash table can be used instead of a uniform hash table. The smallest level in the hash table such that the body takes up at most two cells is chosen.

← Older revision		Revision as of 01:00, 29 April 2009
Line 133:		Line 133:


−	: <math>\large{V_{BPi} - V_{APi} = b_i}</math>	+	: <math>\large{V_{BPi} + V_{APi} = b_i}</math>

← Older revision		Revision as of 22:00, 28 April 2009
Line 142:		Line 142:


−	: <math>\large{qX_k = \frac{ (\vec{r^{XPi}_\perp} \cdot \vec{n_i}) \cdot (\vec{r^{XPk}_\perp} \cdot \vec{n_k})}{I}}</math>	+	: <math>\large{qX_k = \frac{ (\vec{r^{XPi}_\perp} \cdot \vec{n_i}) \cdot (\vec{r^{XPk}_\perp} \cdot \vec{n_k})}{I_X}}</math>

← Older revision		Revision as of 21:28, 28 April 2009
Line 157:		Line 157:


−	For an example, suppose that there are 4 collisions. One between body A and body B (collision 0), two between body B and body C (collision 1 and 2), and one between body C and body D (collision 3).	+	For an example, suppose that there are 4 collisions. One between body A and body B (collision 0), two between body B and body C (collision 1 and 2), and one between body C and body D (collision 3). If we take the equation for <math>V_{XPi}</math> above, are replace <math>j_k</math> with commas, we can form the system of equations into a matrix:
−
−
−	If we take the equation for <math>V_{XPi}</math> above, are replace <math>j_k</math> with commas, we can form the system of equations into a matrix:

	: <math> \large{		: <math> \large{

← Older revision		Revision as of 21:27, 28 April 2009
Line 181:		Line 181:


−	Which can then be solved in O(n^3).	+	Which can then be solved in <math>O(N^3)</math>.

← Older revision		Revision as of 21:26, 28 April 2009
Line 181:		Line 181:


−	Which can then ~~easily~~ be solved.	+	Which can then be solved in O(n^3).

@@ Line 120: / Line 120: @@
 Consider the case of collisions between '''N''' bodies simultaneously.  We can expand from the last section to handle N contact points.  The change in linear and angular velocity of a body is described by the equation:
-: <math>\Delta\vec{v} = \Large{\frac{\sum_{i=0}^{N-1} j_i \cdot \vec{n}}{m_X}}</math>
+: <math>\Delta\vec{v} = \Large{\frac{\sum_{i=0}^{N-1} j_i \cdot \vec{n}}{m}}</math>
-: <math>\Delta\omega = \Large{\frac{\sum_{i=0}^{N-1} j_i \cdot \vec{r_{\perp}^{XPi}} \cdot \vec{n}}{I_X}}</math>
+: <math>\Delta\omega = \Large{\frac{\sum_{i=0}^{N-1} j_i \cdot \vec{r_{\perp}^{Pi}} \cdot \vec{n}}{I}}</math>
 where:
 * <math>j_i</math> is 0 if that contact point isn't part of that body's collision.