Z-COLLIDE

Z-Collide was my first collision detection library, built on top of ICE. I did this when discovering the world of collision detection, trying to re-implement pretty much all the CD algorithms I could see in the litterature - and to improve them while I was at it. Nowadays, it is slightly obsolete.

Old demo: the cube hell !

Click here for a screenshot. 

Last version:

Z-Collide :

• supports collision detection of multiple rigid bodies
• works on arbitrary models (convex or not), and also handles polygon soups
• uses a four-stages collision detection pipeline
• the first stage divides the world into multiple independent sectors
• the second stage uses a revisited sweep-and-prune algorithm and works with bounding volumes
• the third stage uses OBB trees for concave objects and polygon soups, and an enhanced GJK + separating vector algorithm for convex ones
• the last stage goes down to the triangle level, and reports closest points

Regarding OBB trees, Z-Collide is similar to V-Collide in spirit, but it’s much more efficient :

• the sweep-and-prune algorithm always runs in linear time, without relying on temporal coherence.
• the OBBTree code has been optimized. A big part of the original code comes from the RAPID library.
• memory requirement is more than 3 times smaller. (see my notes somewhere on the site, and Gottschalk's comments)

Regarding GJK and separating vectors, Z-Collide is similar to Q-Collide, but also shares similarities with Van Den Bergen and Cameron's GJK implementations:

• temporal coherence is fully exploited
• the search for supporting vertices uses hill-climbing / local search
• initial supporting vertices are precomputed in a little table
• GJK termination condition is more robust than the original one
• GJK and separating vectors are combined in a single algorithm

Original version :

The old first demo is still available here, but that one only includes the early OBB-trees.

Green bounding boxes aren't colliding (not on the pic)

Red bounding boxes are colliding, but the objects aren't.

Yellow bounding boxes are colliding, and the objects as well.

Colliding faces are marked as white.