Summary: This wiki will serve as an online tracking system for an attempt at building a collision detection library in C# so that it might be used in writing XNA 3D games.

Preface: First, I'd like to say that I hate, hate, hate to do this. I consider a collision detection library strictly plumping, and not something exciting. But, the first crack of XNA doesn't ship with many high-level components. In time, I think, either MS or a kind-hearted soul will make available a much more robust collision detection library, but in the short & medium term, I need one, and there isn't one, so, here goes.

Goals: Simple & fast collision test of two static meshes. Physics & collision response can come later.

A)
Geometric Intersection Tests - math library to test one primative geometry against another.

Oriented Bounding Box Intersection Test
http://MiddaySoftware.com/MinhsBlogs/DirectGallery/obb_intersect.gif
Woot!

B)
Storing the mesh as a spatial tree.
Spatial Partitioning - database optimize for 3D data. Necessary for broad phase & narrow phase.
Choosing a scheme: QuadTree, OctTree, kDTree?
ColDet3D doesn't seem to be using any of the above tree type. It splits nodes along the node's longest dimension. What is that called?

The closest is the kD-Tree. But a book I'm reading suggests that kD-Trees simply alternate the dimension of the split, not really caring about the size of the node being split.

C)
Broad Phase - elimination of geometries that have no chance of collision

D)
Narrow Phase - testing of geometries that may be colliding

---

(Movie of close, but not quite intersection test)


(Movie of successful test)

---

References:

Collision Queries using Oriented Bounding Boxes
Stefan Gottschalk
http://www.cs.unc.edu/~geom/theses/gottschalk/main.pdf

This appears to be the definitive algorithm for calculating whether 2 oriented bounding box intersect each other. You'd think that this problem would be solved 200 years ago, but, in fact, Stefan Gottschalk has only published his thesis in 2000. I suppose the problems & solutions evolve together. There probably hasn't been a need to do this sort of intersection test until hierarchical spatial trees come along & there was a need to do intersection test REALLY REALLY fast for video games.

---

A Fast Triangle-Triangle Intersection Test
Tomas Moller
http://knight.cis.temple.edu/~lakaemper/courses/cis3502004/etc/moellertriangle.pdf

A way to determine if 2 triangles intersect. This test will ultimately be used by the narrow phase, when 2 bounding boxes with geometries (leaf nodes) are found to intersect, and we would have to test the geometries (should be 1 triangle per node) against each other.

Movie of successful implementation of Moller

---

DxDot v0.2
http://www.dxdot.net/

A simple C# collision detection / physics library. Currently, it only supports sphere collision detection right now, but, it'll be a good place to start.

---

ColDet3D v1.1
http://sourceforge.net/projects/coldet
This is a C++ library that I used in the past. It supports per-triangle detection, but the code is really messy and hard to understand.

---

An Oriented Bounding Box (OBB) Intersection Test
http://www.gamasutra.com/features/19991018/Gomez_5.htm

---

Nuclex.Geometry
http://www.nuclex.org/articles/Programming/Math/Collisions
Contains XNA implementations of several primitive vs. primitive collision tests (AABB-AABB, Cylinder-Sphere, OBB-Sphere, OBB-OBB, ABB-OBB and Sphere-Sphere for now).