Flavius Gruian & Magdalene Grantson
December 13, 2001
Detecting colliding objects is a must in any graphic engine or simulation environment. Real-time 3D simulations, consisting of complex scenes with many moving objects, require fast collision detection algorithms in order to keep a high frame rate. More complexity is added if one intends to handle variable size bodies, i.e. deforming bodies.
Moreover, there has to be a tight connection between collision detection and the part implementing the kinematics/physical behavior of the simulated universe. From this point of view, the collision detection part has to be able to provide enough information about each collision, information used to recompute the accelerations, speed, or/and forces that change the behavior of the object. A good separation between the collision detection part and the timely behavior of the universe (kinematics, physics) is also required if one expects to employ various approaches for any of these two parts. Having an efficient interface (API) between these plug-ins is, thus, a must. These are just some of the problems to be overcome in writing a good collision detection plug-in.
The focus of this project is on enhancing the already existent Crystal Space [ See Crystal Space Documentation at http://crystal.linuxgames.com/. ] collision detection plug-in. The current plug-in is based on RAPID [ See OBB-Tree: A Hierarchical Structure for Rapid Interference Detection, S. Gottschalk, M.C. Lin and D. Manocha Technical report TR96-013, Department of Computer Science, University of N. Carolina, Chapel Hill. Proc. of ACM, Siggraph'96.. ] and can only handle a small to moderate number of rigid objects. In an initial phase, it constructs a object oriented bounding box (OBB) hierarchy for each collider 1 . At runtime, the user is expected to perform collision queries between pairs of colliders. In a bad implementation, every pair of dynamic objects in the universe have to be checked for collisions. In practice, only "close" objects can collide, so only these should be tested for an accelerated query. There are several approaches that for detecting "close" object pairs, such as:
Combinations of these and other approaches can also be imagined. One example is V-COLLIDE [ See V-COLLIDE Website: http://www.cs.unc.edu/~geom/V_COLLIDE/index.html. ].
Another drawback with the current collision detection plug-in, is the lack of any information about the surface (or point) of impact between the two colliders. We just know if the objects collide or not. This is not enough to derive a reasonable physical model. We plan to extend the current collision detection mechanism with some feedback about the impact surface (volume, point). This improvement should be usable with the current csPhyziks library, but general enough to be used with any other physics plug-in.
Finally, the existent iCollideSystem plug-in can not handle dynamic meshes. That is, objects with growing size or deforming features. This would imply recomputing the OBB hierarchy each time the object deforms, which can be quite time consuming. We aim at including a fast way of recomputing an OBB hierarchy after a deformation. This should be the first step towards adding soft bodies in the csPhyziks library.
We will modify the iCollideSystem plug-in to include accelerated queries, support for deforming bodies and return the point/surface/volume of contact. If the first enhancement may be transparent to the user of the collision system, the next two require a well defined API. More precisely the interface would be something as follows:
(also referred to as "frame coherence") Functions for setting and updating the location of the objects and possibly their orientation too:
void iCollisionSystem::SetPostion(Collider object, csVector3 position)
void iCollisionSystem::UpdatePosition(Collider object, csVector3 position)
These are required for accurate tracking of "closeness" between objects.
We will assume that only the position of certain vertices can change (i.e. no vertices or edges are inserted or deleted). Every time a deformation occurs, meaning some vertices changed their position, relative to the other vertices of the same object, there should be a way to report this back to the collider for that object. A list of pairs containing old position and the new position of a vertex have to be reported in this case:
void Collider::Difform(list_of_vertex_pairs)
Our implementation will have to identify the OBBs that were affected and adjust the hierarchy correspondingly.
Any collision check between two objects should return the point/surface or volume of contact in some way. In principle, only impact forces and their origin points are interesting. This is the least clear part of the project, and we have to do more literature survey before we can define the right approach.
The demo application(s) should show the power of our enhancements. For the first enhancement we need a large number of colliders - i.e. a room full of bouncing balls, possibly different in size, that can collide with the walls and among them. We chose balls (spheres) since the point of contact in this case is very easy to compute, in case we can not finish the last enhancement in time. For the last two enhancements, the best demo would be a deforming L shaped object falling down some stairs. With each collision, the shape would change and finally at the end of the staircase, the L shape will be all crumbled together. If we implement only the first two enhancements, deforming we could make a demo with a lot of bouncing objects (spheres) changing sizes. Finally, the demo will depend on how much we manage to implement.
Our aim will be to extend the RAPID collision detection plug-in which will also be useful in the csPhyziks library.
Using csPhyziks, define a room full of bouncing balls of different sizes, possibly size changing too. The balls collide with the floor, walls, and among them. Compare the speed between using only RAPID (check each pair of balls) and our own enhancement for different number of balls ranging from 10 to 1000.
The report will take the following format: