OCD

Every actor in UT has a precise Location, which is in fact a point with 3D cartesian coordinates (X, Y and Z). It also has 3 collision constants, bCollideWorld, bCollideActors and bBlockActors (or is it bBlockPlayer ?).

Every actor that is supposed to collide with the rest of the world has a CollisionHeight and a CollisionRadius. These define a cylinder box that represents the "body" of the actor.

To check whether two objects are colliding in UT, the engine first checks the collide constants. If enough of them is set to True, it then checks the Z positions of each actor, taking into account the CollisionHeight:

bActorsCollide = Actor1.Location.Z - Actor2.Location.Z < Actor1.CollisionHeight + Actor2.CollisionHeight

Then it checks the distance between the two actors:

bActorsCollide &= (Actor1.Location.X - Actor2.Location.X) *  (Actor1.Location.X - Actor2.Location.X) 
   +  (Actor1.Location.Y - Actor2.Location.Y) * (Actor1.Location.Y - Actor2.Location.Y) 
   < (Actor1.CollisionRadius + Actor2.CollisionRadius) * (Actor1.CollisionRadius + Actor2.CollisionRadius)

Done.

Now it wouldn't be really practical to check every possible pair of objects in a level, so there's a simple optimisation in UT: the engine only checks the collision of objects that are on the same side of a BSP tree plane. Of course this system is very basic, and has very frustrating limitations.

Coming soon: explanation on Object Collision Detection in U2 and UT2 – Why future is always brighter (for programmers)

A plane in 3DSpace is described mathematically by a Cartesian Equation, which comes in the following form:

A*x + B*y +C*z + D = 0

So you can store all the info you need about a plane in an array of four numbers, the constants A, B, C, D.

To know whether a point (which coordinates are X, Y, Z) is behind the plane, before the plane or on the plane, you just have to compute its coordinates through the cartesian equation of the plane:

if A*X + B*Y + C*Z + D < 0 => the point is behind the plane
if A*X + B*Y + C*Z + D > 0 => the point is before the plane
if A*X + B*Y + C*Z + D 0 0 => the point is part of the plane

Now let's say you have a mesh. You can put this mesh inside a simple Convex Bounding Box (CBB), which is the smallest convex (= whose angles between planes are never superior to 180 degrees) box in which the mesh can fit. It is made of a certain number of polys that all are part of a different plane. So you can store the info on the CBBox in an array of arrays of four numbers.

Now to test whether a point is inside, outside, or touching the mesh, you just have to compute the point's coordinates through every plane's cartesian equation:

if the point is behind or on every plane, it is inside the mesh, otherwise it is outside.

You can quicken the computation by making several layers of CBBoxes, from a simple 6-Polys CBB to a more complex but closer to the mesh 144-Polys CBB, just like russian dolls. This is useful if it is unlikely that objects ever collide, but in FPS games like UT, objects DO collide a lot

So a simpler, yet more useful optimization is to use an ellipsoid (a deformed sphere) as a Bounding Box. This way you can have one simple calculus to compute each time you want to know if two objects are colliding. If the result is positive, then you use the more complex but more accurate CBBs. Simply put, it lets you know whether 2 objects are:

certainly colliding
perhaps colliding
not colliding at all

Only in the second case do you have to do the heavy calculation.

How do we determine the collision of two meshes and not just a point with a mesh? We just process the formulas with every point of the potentially-colliding mesh. Ewww, that's a lot of computing, you say. And you're right. That's an awful lot, and that's why Object Collision Detection is the most CPU-consuming task in most 3D games. UT uses one more optimization: it doesn't do checks for objects which are not in the same leaf of the BSP Tree (which is a complicated way to say that UT doesn't bother computing all this awful formulas for objects that are not in the same room).

Not-So-Convex meshes

We just have to divide them into convex parts, just like a BSP tree does for a Map. This can even save the CPU some calculus, as an object's part cannot collide with another object's part if they're not on the same side of a plane. This can in fact be a dramatic boost in the OCD process, since it works for both potentially-colliding objects. And that's what's coming with U2 and UT2003

This page should maybe merge with Collision Detection