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) < (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.
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 :)
Related Topics
- Collision
- Actor/Collision
Discussion
Unknown: This page should maybe merge with Collision Detection.
SuperApe: So, OCD is Object Collision Detection? This page can most likely be reworked into Collision, Actor/Collision or something.
CH3Z: Its all good information although some of it is already on other pages. Like the first bit about the constants (which aren't really constants, but simple boolean flags and there at least 5 of them) are already on Actor_(UT)/Collision. Parts of it could be worked into other pages as well. If this page is not refactored into appropriate pages, it should at least be gone over and probably named something else if nothing more than undoing the acronym to "Object Collision Detection".
CH3Z:Come to think of it, the topic of collision seems to be scattered about and none of the page titles really elude to what kind of information specific to the topic will be found there. It would be nice if someone who has a good overview of what collision data is here could devise an organizational plan to tie the whole topic up in a more comprehensive way. ie maybe if we renamed the sub-pages of Actor to for example /Collision_Topics, /Lighting_Topics etc. and then alot of the scattered pages relating to the topic could be made into sub-pages of that _Topics page? Or maybe some thing like Category Collision would be better. But there are other topics here that seem to need to be tied together somehow as well. I wonder if a new tag like Collision Topics instead of more category tags would be better. Then category tags could be exclusive to the category of page ie tutorial, class, engine version, etc. and the Topic tags would be the equivelant of the Category tags for more UnrealEngine aspect related subdivision of this information like collision, lighting, AI etc.
Xian: Considering around 90% of the text is related to how Actor Collision works, maybe it should be moved to it and create a new subcategory there called "Collision Procedures" or something... From what I saw, UT2004 has some new stuff added to this, so I am not sure how we should organize this chapter.