Late Night PC

I was looking at the sessions scheduled for the Game Developers Conference and I found one titled Continuous Collision Detection of General Convex Objects Under Translation. The Gilbert-Johnson-Keerthi algorithm (GJK) is used in SOLID. Someone we saw a couple years ago also gave an overview and demos on SOLID. I was impressed then and I'd be willing to see it again. The speaker, Gino van den Bergen, seems to be affiliated with the SOLID project. I haven't yet used the library myself, but if I have time, I might download the FreeSOLID package from SourceForge and try it out. That's a lot of time, but maybe. Anyhow, here's an overview of what I'd expect to do based on the SOLID API Documentation.

Ideas on Starting with FreeSOLID

First off, a simple test of the install could be done by creating a couple of rectangular prisms with dtBox(). This would be a boring test, but it would be easy to do. To do anything interesting, I'd want to load in some real 3D models. I can see how to do that, but I'll come back to it later. For now, imagine boxes. Two of them. And maybe a sphere for good measure - call dtSphere() and pass it the radius. For each of these objects, I'd need to use the same coordinate system to draw corresponding 3D objects. SOLID uses OpenGL coordinate system conventions, and I've only ever done DirectX. If I ever really got into doing this, I'd use SDL - I've heard it really makes life easier. SDL works with OpenGL so I guess that'd be my route too.

Share the same data for OpenGL and collision detection

Getting back to the boxes... There should be a common data structure, even for a simple demo of the technology, that's shared between the graphics (OpenGL) and the collision detection (FreeSOLID). The data structure would simply contain the vertex data for the object. At this point the data could be a raw array, but a more advanced usage would need to store vertices in a graph which could be placed in the scene graph. This should ease translation for both libraries being used.

Basic travel along a path

So when the app starts, it would create the collection of shapes then starts into a loop (don't they always?). Each pass of the loop would update positions of the objects in our little world. FreeSOLID comes with a library for creating the quaternion that we need to control the facing of the objects as well. After creating the quaternion, the app calls dtTranslate() and dtRotate() to set the placement and orientation. The positions and facing have to come from somewhere. The data structure for each object will contain a parameterized path that gives a position based on time. For example:

x = t

y = sin(t*pi/2)

z = 5

where t is time in seconds gives a simple path for an object. Of course the only interesting path for this example is one where objects will collide. I'd draw a couple sketches on paper to come up with a simple example.

Collision detection

Now that should be enough to draw the objects, set them in motion, and keep FreeSOLID in sync with OpenGL. I'm not just doing this to see things move around, though, I want collisions! So tracking a collision with FreeSOLID now looks really simple. All I have to do is register a callback function with the library that tells it what to do when a collision occurs. There are a few options here and it's the first point that I'd like to start testing more advanced features. First I'll paraphrase the documentation.

Different kinds of collisions can trigger different callback functions (called 'responses') from FreeSOLID. There are default, object and paired responses. The paired response applies to a specific set of exactly two objects. Maybe this would be the cue and the white ball in a game of pool. The pair response is called if the two objects that it was registered for have collided. The object response is a callback set for just one object. If that object collides with another and the two don't have a pair response, then the object response is called. This could be a car in a driving game (so we know when we should see sparks). The default response is called for collisions between objects that have neither a paired response or object response.

Each response (whether it's a default response, object response or pair response) has a response type assigned to it. The response type can be simple, witnessed or smart. The response type determines what information is passed to the callback function when it's called. A simple response has no information about the point of collision. A witnessed response includes the point on each of the two objects where the collision occured (in the object's coordinate system). Because they've collided, the points are the same in global space. A smart response includes the closest points on each of the two objects before the collision occured (that is, in the previous frame). The smart response also provides an approximation of the normal to the plane in which the collision took place. This helps for detailed responses (like making the balls bounce the right way in a pool game). For more details on this, go straight to the docs.

So of course I'd have set a default response after creating all the objects back before we started the main loop. FreeSOLID does this with dtSetDefaultResponse(). In my experience a callback function is called asynchronously. The FreeSOLID library documentation states that callback functions are called by having the application call dtTest(). I'd experiment with this by initially calling dtTest() inside the loop. I'd set a breakpoint in the callback function to see what happens. Right now my guess is that the library waits for the application to call dtTest(), then does it's thing. That would allow the application to put things in the right place before collision tests are done. It also gives the application freedom to work within its framerate (I may only want to collision test once per frame).

All that should be enough to give us a working example of some boxes floating around and maybe displaying a message or changing colour when they run in to each other. The reaction, remember, is handled by the application. So once a collision is detected and the response function is called, the application has to decide what to do about it. What I'd do about in this test case is just display a message or some visual feedback.

Collision reaction

As I mentioned earlier, after the simple default collision response works, the collision type is the first thing I would experiment with. One of the useful developments could be a collision reaction that makes the objects bounce off of each other. Using the points and normal information from a smart response, this could be done with some decent realism. With an application this simple, the paired and object responses can be tested easily, but not really applied for anything useful. It is a good way to get familiar with the FreeSOLID library before plunging in to developing the rest of the game, though.

Finally, the homework portion. The objects that I describe in this entirely hypothetical future test application are just boxes and a sphere. For any reasonable approximation of a game, model data has to be used. This means that the vertices of the model have to be given to FreeSOLID so that it can do its job. My first step here would be to replace one of the boxes with a slightly more complex shape. A pyramid or a diamond shape. Imagine up a graph format, something like VRML, and build the vertex data in to the object. This should be a step toward something that can be read in from a model file later, but it still needn't be perfect. The intent at this step is to give the data to FreeSOLID. There are a couple ways to do this, but I think the most useful will be to create the shape, set the vertices, then set the indices of the faces. This should be a loop through just a few functions, which is repeated as you walk the graph that describes the model.

For the simple diamond shape, I would just try it out in one go. First call dtNewComplexShape(), then dtVertexBase() with an array of the vertices of the diamond. Next call dtVertexIndices() with an array of indices into the array of vertices. The call to dtVertexIndices() describes one face. So it has to be called for each of the faces of the object. After the last face, call dtEndComplexShape(). The same data can be used to call OpenGL functions to create the object to be displayed.

Sounds pretty cool, I just might try it.