Welcome to...

ECoDS Project Page

ECoDS is the acronym for Enhanced Collision Detection System. This is our project for the Game Engine Technology Course (aka GET).

Read more about ECoDS in our reviewed project proposal(pdf)
Our old project proposal.

Brief Description

The goal of the project is to improve the Crystal Space collision detection system, which is currently based on RAPID. We will focus mainly on three improvements:

• Faster proximity queries using temporal/spatial coherency.
• Support for deforming bodies.
• Contact point/area/volume detection for impulse computation support.

Project Members

• Magdalene Grantson
• Flavius Gruian

Progress

• 2001-12-14 ECoDS web page up.
• 2001-12-17 New information: According to the SOLID creators:
  • AABB hierarchies are better suited for deforming bodies, since refitting the hierarchy may only need local changes (property shared by Discrete Orientation Polytopes - DOPs)
  • collision detection using AABB herarchies is at least 50% slower than those using OBB hierarchies. On the other hand AABBs require less storage than OBBs: 6 scalars vs. 15 scalars
  • AABBs and SSVs seem to be better suited for computing the penetration depths of two convex polyhedra. (i.e. Gilbert-Johnson-Keerthi GJK algorithm)
  Consequences:
  • RAPID, based on OBB, might not be the best choice for our project. We need to look closer into implementing an AABB hierarchy.
  • Proximity queries for non-convex objects (penetration depth, area of contact, etc.) might be too hard to implement. We may restrict our implementation to convex objects.
  • More reading on incremental algorithms for collision detection and distance queries such as Lin-Canny and GJK
• 2002-01-08 The reviewed project proposal(pdf) is up.
• 2002-01-17 We finally decided on the algorithms that we will implement. In principle is a V-COLLIDE a bit more sophisticated. In each frame the following happends:
  1. Keep the AABB x,y,z ordered list for the objects that did not move/difform - fixed objects O(n)
  2. For the objects that DID move compute the new AABBs and insert them in the already sorted list of not moved objects from the previous point O(n log(n))
  3. POSSIBLY: If the AABBs of some moved objects changed only very little relative to a certain inter-object distance, consider them as fixed O(n)(?)
  4. Check the AABB x,y,z list for pairs of potentially colliding objects. If a pair contains only fixed objects, return the collision result from the previous frame (frame-to-frame coherence). If the pair contains at least one moved object, add the pair to the PCO list
  5. For each pair of objects in the PCO list, call RAPID
  Note: if an object difforms we take the simplest approach for the moment, recompute its OBB tree and mark the object as moved.
• 2002-02-19 ECoDS Up and Running!
  Here are a few snapshots from a demo. The demo consists a room full of colliding spaceships that fly around like crazy. Every time two of them collide they change their course and pitch, roll, yaw.
  15 ships (not all in pic):
  30 ships (not all in pic):
  We're working on the report right now, soon to be available even here, on this very page.
• 2002-02-28 A preliminary version of our report ECoDS: An Enhanced Collision Detection System for Crystal Space (pdf 770k) is available for download.
  The demo source code containing ECoDS is also available. If unpacked in the CS directory (version +0.92) it will overwrite the apps/tutorial/simpcd application. Tested on Solaris and Linux.