I don't need to test my programs. I have an error-correcting modem.

# Legacy:OCD

Every Actor in UT has a precise Location, which is in fact a point with 3D cartesian coordinates (X, Y and Z). Optionally, it can also have a Rotation (a rotator with short integer values of Pitch, Yaw and Roll) which can later be used in tracing, FOV checks or other vectorial based procedures. Collision is mainly detected using 4 collision flags: bCollideActors (it's a constant, which can be either changed in defaultproperties blocks or using the SetCollision() function), bCollideWorld, bBlockActors and bBlockPlayers.

An Actor that is supposed to collide with the rest of the world geometry (returned as 'Level', as a variable pointer, and 'LevelInfo' as the Class in tracing or other Collision procedures) or other Actors has a CollisionHeight and a CollisionRadius. These define a cylinder box that represents the "body" of the actor. Unfortunately the bounding box is not as flexible as we'd like it to be. While it would be easier to define a size using X, Y and Z values, it is reduced to Radius, which surround the Actor itself, and a Height (which represents the Z value). While this offers limitations on one side, another HUGE limitation is the fact that the bounding cylinder is always fixed. This means that rotating the Actor by say, 90º clockwise, will not change the bounding box itself (the Z axis will not become the X or Y axis), it will just rotate the Mesh.

To check whether two objects are colliding in UT, the engine first checks the Collision constants. If enough of them are 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)

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.

Another avantage of using Colliding Actors is for iteration. Although at a first glance the AllActors iterator will iterate only the specified Class, it will, unfortunately, check ALL the Actors stored in that Level. When an Actor with bCollideWorld or bCollideWhenPlacing (bCollideWhenPlacing must be True and it must be created server-side, or for short, the NetMode must not be NM_Client) is Spawned, it will add it in the CollidingActors list. To access it, we can use the VisibleCollidingActors iterator, which is a lot faster than the normal AllActors iterator.

Apart from the usual uses, Collision is also used by Tracing (Trace(), FastTrace(), LineOfSightTo() etc.).

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 (meaning 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.

hmm... if the point is outside the Mesh (box for example), then it is anyway behind some planes and on some planes. (but it may not work on more complex Meshes)

You can quicken the computation by making several layers of CBBs, from a simple 6-Polys CBB to a more complex one 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 :D

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 :)