Collision system overview

Introduction

Implementing a robust, flexible collision system that can meet the needs of both rendering, gameplay, and physics code in realtime is a difficult task. Torque provides a flexible scene database that can fulfill a variety of collision queries, including ray casts/line of sight queries, requests for polylists, and requests for convex hulls. It first checks against a bin system, then performs query-specific processing against the results to determine the final output.

Broad Phase

Most spatial queries in Torque happen by first working with the spatial hash or binning data structure that is implemented in Container. Container also implements several other queries, but in the end it usually ends up coming up against the bin system to narrow things down.

Bins

Some simple code to query for all the objects intersecting a given box's bounds looks like this:

   // Do the query.
   SimpleQueryList sql;
   mObject->getContainer()->findObjects(box, colMask,SimpleQueryList::insertionCallback, &sql);
 
   // Process the results.
   for (U32 i = 0; i < sql.mList.size(); i++)
      sql.mList[i]->buildConvex(box, this);

Within Container::findObjects, Torque figures out what bin or bins the passed box intersects, then goes through the list of objects in each bin to see which if any have intersecting world boxes. Since there are only a finite number of bins, they are tiled to cover infinite space. As a result, the objects in a given bin could be in that bin, or any repetition of that bin in the whole world, so it's important to check if they're really what you expect.

SimpleQueryList just stores results in a list, but you can easily write your own filtering function to do more complex behavior (this is frequently the case for collision code). However, in this example, from collision/convex.cc, an axis aligned world box check is enough.

Masks

Every object in the game world also has a typemask, which is a 32 bit word. Collisions may be filtered by object types, which are defined in game/objectTypes.h. They're just arbitrary, provided for convenience of filtering. If you specify a mask to a findObjects or other collision call, only objects with one or more of the specified bits are allowed into the results.

Narrow Phase Queries

Once a broad set of results are returned from the bin system, more specific tests are done to determine exactly what is needed. Depending on what sort of collision query is happening, different approaches are used.

Note that there are two sides to every collision query! There is the querying side, where you request information on which to base game behavior, and there is the implementation side, where you implement the code e.g. to return the point where a ray would strike an object type. This section discussed the former side, the query side. The next section discussed what it takes, briefly, to make an object respond to queries of each type.

castRay

castRay provides functionality to intersect a line segment with the world, returning the first point that that line segment strikes, with material, object, and normal information, as well as a coefficient, t, describing the distance along the line segment. This is very similar to a ray cast, but has a defined end point (which allows significantly more efficient checks to be performed). castRay is defined in SceneObject.

The mission editor uses SceneObject::collideBox, which is identical to normal castRay except that it only does collision checks against object's bounding boxes. This is used to make it faster and easier to select and move boxes.

Here is a simple C++ castRay example:

// Setup the currentContainer to either the server container or the client container. 
// In your code you might know if you are on the server or not already. In which case you
// could use the gClientContainer or gServerContainer directly
Container * currentContainer;
if(isClientObject()) // Client object. 
{
   currentContainer = &gClientContainer;
}
else // Server object. 
{
   currentContainer =  &gServerContainer;
}
 
RayInfo rInfo; // Will return info on what the castRay found including object information.
Point3F start, end;
Point3F myPoint; // Init this to the point which you want to goto
 
start.x = end.x = myPoint.x; //some x (whatever value you want)
start.y = end.y = myPoint.y; //some y (whatever value you want)
start.z = 2000; // Really high, might be over kill
end.z = -2000; // really low, might be overkill
 
// Look for flags set for pretty much everything.
// Note: An object could have more than one flag set
if(currentContainer->castRay(start, end, 
   StaticObjectType | 
   InteriorObjectType | 
   WaterObjectType | 
   ShapeBaseObjectType | 
   StaticShapeObjectType | 
   ItemObjectType | 
   TerrainObjectType |
   StaticTSObjectType 
   , &rInfo))
{
     myPoint.z = rInfo.point.z;
}
else
{
   // didn't find anything, no TerrainObjectType or anything... 
   // you decide how to handle this error
}

castRay optimizes the normal findObjects case a bit - since we know we're dealing with a line, approximating it with a world aligned bounding box would be very inefficient (imagine a diagonal line!). So instead, we just walk the bins that intersect the line, and process the objects in just those bins. We walk from front to back on the line, and if we consider all the objects in a bin and take the first one, we know we have the first hit, so this saves us a lot of processing.

PolyLists

Polylists can either be returned directly from an object, or from a Convex implementation. In either case the same basic code is used to return an arbitrary list of polygons to an implementation of the AbstractPolyList class. Different implementations gather and process different kinds of data for later use.

Typically Container::buildPolyList will be used if you want all the geometry in a given area. For instance, if you want to cast a shadow in a given volume, you'll use Container::buildPolyList.

Convexes

All of Torque's game objects currently use the convex collision path. This path assumes convex collision meshes. A convex object has no indentations or inward curves. Convex objects have many nice properties, especially for physics simulations, so especially for dynamic objects they are the collision method of choice.

There are some classes that require this more than others. The Player class uses convexes but does not require the geometry they return be convex, as it uses a lot of custom-tweaked physics and a hardcoded bounding box. Atlas terrain returns every polygon as a small convex polytope, and thus supports delivering "poly soup" style collision. Vehicles definitely require convex hulls to collide with and against, for stability of simulation.

In basic terms, when calculating for collision a vertex and our collision mesh are detected to be within a certain range of each other, then collision detection for that vertex 'turned on'. If the vertex intersects with one of the polygons in our collision mesh, a collision has happened.

Most Torque objects do extra work to cache the data for objects they're colliding with, as there is a lot of frame coherency in physics calculations, ie, something you're colliding with or nearly colliding with at one instant is like to be colliding or nearly colliding the next.

Implementing Collision

castRay

Take a start and end point, return true if something got hit, and write out into the passed RayInfo the normal and position of it. Note that some information is recalculated by the Container::castRay function that is calling your object's castRay! Most notable this is the collision position. So you don't need to set the RayInfo position yourself.

All data into and out of this function should be in object-local coordinates - the points you receive are in local coordinates, and the normal you return should be local.

getPolyList

Fill out the passed AbstractPolyList subclass with the relevant collision info for your object. You also get passed a bounding box; if you can, cull what you return by this but don't try too hard if it's not a problem.

buildConvex

Take the object space bounding box, and in buildConvex, link any new Convexes you want to create to the provided one. Also link them to your own internal list so you can delete them as needed. See the tutorial collision object for an excellent example and explanation of this process.