   Collision detection beginner
  I''ve just got into Direct3D from DirectDraw, where collision detection is decidedly simpler.I''m no geometry genius and I''ve been scouring the web looking for some tutorials on collision detection.  I''ve got basic sphere collision detection, that was easy, but all this talk of rays and planes and whatnot has got me baffled.  All the tutorials I''ve looked arnt a good guide for beginners, anyone got any links to any decent beginner tutorials that explain the geometry a little more easily? 
  I don''t have any link under my belt, but I''ll give you a quick run through. ray intersection-----------------a point P on a ray, in parametric form, verifies the equationP = O + D.ta point on a plane verifies the equationP * N = da point on a sphere verifies the equation (P - C)^2 = r^2and a point on a cylinder verifies((P - C) x D)^2 = r^2for ray intersections, you replace P in the equations for plane/cylinder/sphere by O + D.t and tryto find Dexample, for a ray and a sphere((O + D.t - C)^2= r^2[(O-C) + D.t]^2 - r^2 = 0develop [(O-C) + D.t]^2, and you get[D^2].t^2 + [2*(O-C)*D].t + [(O-C)^2 - r^2] = 0this is a second order equation in the form a.t^2 + b.t + c = 0 wherea = D^2b = 2*(O-C)*Dc = (O-C)^2 - r^2this equation will yield two solutions for twhere d = b^2 - 4.a.ct0 = (-b-sqrt(d)) / 2.at1 = (-b+sqrt(d)) / 2.aso, you got two value for t, which you replace in the ray equation to get the two points of intersection for a ray and a sphereP0 = O + D.t0P1 = O + D.t1so there, you have the wo points of intersection.for a plane, you''ll end up with a single value tt = (d - (O*N)) / (D.N)ect...for triangle/ray detection, you first find the intersection point of the ray and the triangle plane as above. then you determine if the point is inside the triangle surface. One way to do it is to use the fact that a point inside a triangle would be back-facing planes the are parallel to the triangle normal and each planes containing an edge. The edge plane normal would then face outwards from the edge, and would be perpendicualar to both the edge and the triangle normal.    + V0 / \.  n0/   \   .   ./e0   \    . . /  \.   n2  / x P\ /    e2\/ e1\ V1 +---------------+ V2  | n1  |  |so, a point P is inside the triangle if [(P - V0) . N0 < 0] && [(P - V1) . N1 < 0] && [(P - V2) . N2 < 0]and N0 = (V0 - V1) x NN1 = (V1 - V2) x NN2 = (V2 - V0) x Noverlap detection------------------this type of collision detection tries to detect if two objects intersect, and tries to return the smallest overlap distance between the objects.for sphere/sphere collisions, you know already how it''s donefor sphere/box collisions, you first partition the centre of the sphere with the box''s planes. So the box centre will be closest to either a face off the box, an edge, or a point. Then you find the distance of the face/edge/point to the sphere, which will give you the penetration depth and the normal of collision.    .  .  .   c0  . c1  x    .   x  ..................+-----------------  |  face 1  | x c3    x c2    |   | face 2  |c0 => it is ''outside'' the faces (face2) and (face1) => the spehre is gonna collide with the edge.c1 => it is ''inside'' (face 2) but outside (face 1) => the sphere is gonna collide with (face 1)c2 => it is ''inside'' (face 1) but outside (face 2) => the sphere is gonna collide with (face 2)c3 => it is inside both (face 1) and (face 2), but closer to (face 2) => the sphere is gonna collide with (face 2)for triangle/sphere, it is based on the same strategy, and the ray/triangle strategy.you partition the centre of the spehre, to see which part of the triangle is closest.  .c0    .   .  .. V0.  + x c1   / \/   \ /\    /  \ ./  c2\    .    . / \ .  .  /   \  . V1 +---------------+ V2    ||    ||    ||each edge has an edge plane, similar to the one abovec2 is back facing all the edges (see the equation) => the sphere will collide with an edgec1 is front facing edge 0, but back facing edges 1 and 2, and also, c1 is closest to the edge than to vertices v0 and v1, so the sphere will collide with edge 0c0 is front facing edge 0 and edge 2, and is closest to v0 than any of the edges, the sphere will collide with v0to determine if a sphere is closest to a vertex than to a segment, it''s simpled = ((C1 - V0) * (V1 - V0))if (d < 0) the sphere is closest to V0if (d > (V1 - V0)^2) the spehre is closest to V1else the sphere is closest to the edge segment. one you know you have a sphere/plane, sphere/edge or a sphere/point collision (for the cube or triangle / sphere overlap test), you can work out the normal and overlap distance that way. Say, sphere / plane overlap ----------------------(point P is any point on the plane)N = plane normal d = r - (C - P) * Nspehre / point overlap----------------------N = (C - P).UnitVector()d = r - (C - P).Magnitude()sphere / segment overlap-------------------------first you need the closest on the segment H from the sphereH = [ [(C - V0) * (V1 - V0)] * (V1 - V0) ] / [(V1 - V0)^2]then N = (C - H).UnitVector()d = r - (C - H).Magnitude()box / box overlap, tri / box overlap, tri / tri overlap--------------------------------------------------------this is more complicated. The trick is not to find if two objects overlap (that''s easy), but to find what the contact information is.all the test perform the same algorithm, which is called the separation axis algorithm.the plan is to find a plane that can separate the two objects you test. If you can find a plane that separates the objects, they cannot intersect.there is only a handful of planes that you need to test between objects. For a box box intersections test, there are 15 planes that can potentially separate two boxes. say a box is made of a centre postiion, three orthonormal axes (unit vectors that are perpendicular with each other), and a half-size vector that describes how big the boxes are along those axes. Example, for an axis aligned box that is 6 meters in height, 2 meter in depth, and 4 meters wide, and it''s centre is at the origin, you''d haveBox.pos = (0, 0, 0)box.halfsize = (4/2, 6/2, 2/2)=(2, 3, 1)box.A0 = (1, 0, 0)box.A1 = (0, 1, 0)box.A1 = (0, 0, 1)so, the 15 separation axes between thwo boxes Box0 and Box1 areBox0.A0Box0.A1Box0.A2Box1.A0Box1.A1Box1.A2Box0.A0 x Box1.A0Box0.A0 x Box1.A1Box0.A0 x Box1.A2Box0.A1 x Box1.A0Box0.A1 x Box1.A1Box0.A1 x Box1.A2Box0.A2 x Box1.A0Box0.A2 x Box1.A1Box0.A2 x Box1.A2if the boxes are disjoint along any of those axes, they are not overlaping. To see if they intersect, you calculate what are the box''s spans on those axes, and see if the spans overlap. Imagine two axis aligned boxes, and you test along axis Box.A0 = (1, 0, 0). the Box0''s span (min0, max0) will be (Box0.pos.x - Box0.halfsize.x, Box0.pos.x + Box0.halfsize.x);the Box1''s span (min1, max1) will be (Box1.pos.x - Box1.halfsize.x, Box1.pos.x + Box1.halfsize.x);if (min0 > max1 || min1 > max0), the box are disjoint, and they cannot intersect.for a random axis D, you calculate the span of a box as followD.min = (Box.pos * D) - [ fabs(Box.A0 * D) * Box.halfsize.x + fabs(Box.A1 * D) * Box.halfsize.y + fabs(Box.A2 * D) * Box.halfsize.z ];D.max = (Box.pos * D) + [ fabs(Box.A0 * D) * Box.halfsize.x + fabs(Box.A1 * D) * Box.halfsize.y + fabs(Box.A2 * D) * Box.halfsize.z ];as soon as you find that two spans don;t overlap, the box won;t overlap. here is an example-------------------------------------------------------D = Box0.A0 x Box1.A1r0 = [fabs(Box0.A0 * D) * Box0.halfsize.x + fabs(Box0.A1 * D) * Box0.halfsize.y + fabs(Box0.A2 * D) * Box0.halfsize.z];r1 = [fabs(Box1.A0 * D) * Box1.halfsize.x + fabs(Box1.A1 * D) * Box1.halfsize.y + fabs(Box1.A2 * D) * Box1.halfsize.z];p0 = D * Box0.posp1 = D * Box1.posmin0 = p0 - r0max0 = p0 + r0min1 = p1 - r1max1 = p1 + r1if (min1 > max0 || min0 > max1) return false;------------------------------------------------------------you do that test for the 15 axes, and as soon as one fails (returns false), the box won;t intersectwhen all the 15 tests pass (the box overlap on every axes), what you can do is store the 15 overlap amount for the 15 tests. the 15 tests will also give you a ''normal''. That overlap amount tells you how deep the box intersect along that normal. first, you need to normalise the overlap amount and the normals (divide both by the length of the normal).From those 15 normalised overlap tests, you take the smallest value. That value will give you the penetration depth of the two boxes, and the normal will give you the normal of collision. Also, because you know if the normal was a cross product of two edges, or simply the normal of a face of one of the boxes, you can tell what parts of the box intersected. if the normal was computed using the cross product of two axes of the boxes, two edges intersected. The edges that intersected ar the edges parrallel to the axes of the box. There are 4 of them on each boxes. To simplify, you can try to calcualte the distance of each edge against each other edges on trhe other box, and take the two edges that are the closests. But you can be a lot more clever and directly guess what edges are closest to each other. if the normal is just an axis of the box (one of the first 6 tests performed), it is a point/face collision. In that case, take the point on the box that is the lowest along the normal, and the face that is the closest from the other box'' centre. so there you have it, box/box overlap distance, normal and points of collision. for triangle/triangle and triangle/box, the principle is the same. You test various separation planes, if all spans overlap, take the minimum of overlap into consideration (divide them by the corresponding length of the axis first), that will give you the overlap distance, take the corresponding normal, find the features that are the closest, and find the closest points on those features for the points of contact. for tri/box test, there are 13 testsTri.NBox.A0Box.A1Box.A2Tri.Edge0 x Box.A0Tri.Edge0 x Box.A1Tri.Edge0 x Box.A2Tri.Edge1 x Box.A0Tri.Edge1 x Box.A1Tri.Edge1 x Box.A2Tri.Edge2 x Box.A0Tri.Edge2 x Box.A1Tri.Edge2 x Box.A2for tri/tri collisions, 11 testsTri0.NTri1.NTri0.Edge0 x Tri1.Edge0Tri0.Edge0 x Tri1.Edge1Tri0.Edge0 x Tri1.Edge2Tri0.Edge1 x Tri1.Edge0Tri0.Edge1 x Tri1.Edge1Tri0.Edge1 x Tri1.Edge2Tri0.Edge2 x Tri1.Edge0Tri0.Edge2 x Tri1.Edge1Tri0.Edge2 x Tri1.Edge2that''s about it. Also, for 2 moving spheres intersection test, the test falls down to doing a large static sphere against a segment, which is what a ray/sphere intersection test does. But That''s for another time there are other things, like sorting objects (sweep and prune), octrees/quadtrees/BSP trees, heightmap collision detection, convex hull collision detection... ;  errata"c2 is back facing all the edges (see the equation) => the sphere will collide with an edge"shoudl read"c2 is back facing all the edges (see the equation) => the sphere will collide with the plane"