How Collision Detection Works

This is a bit of information condensed from what is available from the manual and from the source code.

Broad-Phase Collision Detection

In this stage we are only interested in which pair of geoms are potentially intersecting. Geoms with finite extensions are represented only by their AABBs.

There are 4 data structures that can be used in ODE for this: dSimpleSpace, dQuadTreeSpace, dHashSpace and dSAPSpace.

• The dSimpleSpace structure is just a list that tests all O(n^2) pairs of geoms for intersections, and is very fast for a small number of geoms.
• The dQuadTreeSpace, as the name suggests, organizes the geoms into a complete Quadtree. Geoms are placed in the smallest tree cell that contains the geom's AABB. For every populated cell, collision is detected by testing all its geoms against each other (in O(n^2)) and against geoms in the parent cells (all the way up to the root). Thus it's more efficient when geoms are more evenly distributed, and not clumped together.
• The dHashSpace structure is a hash table for AABBs. Depending on the AABB size, it is decomposed into smaller pieces (smaller AABBs), each inserted separately in the hash table. The collision detection is done by iterating through the pieces, and performing queries on the hash table; if there are pieces from more than one AABB stored in the same position, a collision is registered. (The terms in italics are not standard nomenclature on hash spaces, but should be clear enough for everyone)
• The dSAPSpace structure is based on the Sweep And Prune algorithm. Pierre Terdiman wrote a good article about this, on his blog: http://www.codercorner.com/blog/?p=11

After the broad-phase, collideAABBs() (see collision_space_internal.h) is called for the geoms, where category bits are tested, then comes a standard AABB test, and an extra (optional) geom-specific AABB test is done (useful for non-convex shapes, like trimeshes). After that, the user-provided dNearCallback is invoked, and if the user calls dCollide(), comes the expensive narrow-phase collision detection.

Narrow-Phase Collision Detection

In ODE this is done with specialized code for each pair of geom types; there's a big matrix, indexed by the geom type, that stores function pointers. This is hard to maintain (almost half of ODE code is for collision detection); Bullet, for example, has a more elegant approach, through the GJK algorithm. Adding a new geom to ODE requires writing collision detection code for every geom that already exists; adding a new geom to Bullet requires just a single support function (for the GJK algorithm).

Triangle meshes are handled with specialized code (not only on ODE, but on Bullet too); the triangles are usually stored in their own data structure (like an AABB tree), to figure out which triangles are potentially colliding. By default ODE uses OPCODE for this (which is known to be very fast).

Solving the Collisions

ODE only detects collisions after there's already penetration. After this is detected, movement constraints are created between the bodies, and the collision is "solved" by letting the LCP algorithm figure out to solve the system with those constraints, trying to not let things get "worse" (like letting the bodies penetrate further). "Solving" the system means figuring out what the next velocities should be, for all bodies; the velocities are then integrated (currently through an explicit first order method).