Collision detection and collision response

Have you ever seen somebody going through a wall? Probably not. In reality it is impossible to pass through solid surfaces and since games usually try to fake reality this behavior should be reproduced there. This is why good collision detection and collision response are needed. The collision detection has to determine whether objects have moved through or into obstacles in every step and if so the collision response has to determine a position to which the object can move without getting into obstacles.

The most common collision response for first and third person games makes objects slide along walls, if they try to move into them. This has the advantage that the player does not stop moving as he gets towards a wall, which is important as a sudden stop can be very irritating in fast games. With Ultimate 3D 2.0 and its ray tracing based collision detection it has been very difficult to get reliable collision detection. This was basically the biggest weakness of Ultimate 3D. For Ultimate 3D 2.1 I completely redesigned the entire collision detection system and made a built in collision response system. Now collision detection and collision response is one of Ultimate 3D's strengths. Credits for this achievement go to Kasper Fauerby who wrote a paper describing the technique the collision detection and collision response mechanisms used are based on.

Since the system is built in it is very easy to use and quite efficient, since no slow GML code needs to be executed. The sliding collision response described above can be implemented in five lines of code. You simply set all objects, which should be checked by the collision detection functions to solid through an Ultimate 3D function and call one function for the objects, which should perform collision detection and collision response. Then you are done.

Collision detection based upon ellipsoids

Before we can get to this one magic function, which solves all of your problems (at least those related to collisions), we need to do some theory. The first necessary consideration is, which shape can be used for good collision response. It should not have any corners, to avoid that it can hang somewhere, it should be versatile enough to contain objects with very different shapes and it should be easy to describe. The obvious choice is an ellipsoid (a scaled sphere). So we no longer need to think about collision detection for moving character models, we just need to think about collision detection for moving ellipsoids. The following illustration shows an ellipsoid.

Games are usually frame based and therefore the objects do not really move continuous, they jump from one position to another in every step. In one step the object may not collide with anything and in the next step it may already be inside the geometry. The following illustration demonstrates this.

It is not enough to check whether the green area is intersected, it is not enough to check whether the the yellow area is intersected and it is not enough to check whether the red area is intersected. All these areas need to be checked. So the shape for which collisions actually need to be detected is not an ellipsoid, but a so called swept ellipsoid. A swept ellipsoid is made up of two ellipsoids and a scaled cylinder connecting them. This is the shape Ultimate 3D works with. This should be enough theory for now.

ObjectID
The ID of the object for which you want to perform a collision detection. This can be the ID of a model, a terrain or a primitive object or the keyword all. In the latter case all objects, which are set to solid through SetObjectSolidity(...) and are in the right room will be checked. In addition all objects, which are set to globally solid through SetObjectSolidity(...), will be checked then, no matter which room they are in.

StartX, StartY, StartZ
The start position of the swept ellipsoid (see the illustration above).

DestinationX, DestinationY, DestinationZ
The destination position of the swept ellipsoid (see the illustration above). These parameters can equal StartX/Y/Z. In this case Ultimate 3D will perform a less computing time intensive unswept ellipsoid intersection test.

RotX, RotY, RotZ, ScalingX, ScalingY, ScalingZ
The rotation and scaling of the ellipsoid. The ellipsoid is a unit sphere (sphere with radius one) scaled by ScalingX/Y/Z and rotated by RotX/Y/Z.

RoomIndex
This parameter is only relevant if all is specified as first parameter. If it is negative objects in all rooms will be checked. Otherwise only objects, which are in the room with the given index and globally solid objects will be checked (see SetObjectRoom(...)).

Just knowing that a collision has occurred is quite useless though. More information is needed to be able to respond to the collision (in case you do not use the built in collision response). For this reason there is a couple of functions, which return relevant information about the occurred collisions. All these functions return information about the results of the last call to CheckSweptEllipsoidIntersection(...).

This function returns the number of triangles, which have been intersected by the swept ellipsoid specified in the last call to CheckSweptEllipsoidIntersection(...).

This function returns the time at which the given intersected triangle has been intersected by the swept ellipsoid specified in the last call to CheckSweptEllipsoidIntersection(...). The return value lies in the range from 0.0 to 1.0, where 0.0 refers to the time at which the ellipsoid was at the start position of the swept unit sphere and 1.0 refers to the time at which it was at the destination position.

IntersectedTriangleIndex
The index of the intersected triangle for which you want to to retrieve the intersection time. This is an integer value in the range from 0 to GetTriangleIntersectionCount()-1.

This function outputs the position at which the swept ellipsoid specified in the last call to CheckSweptEllipsoidIntersection(...) has first intersected the given intersected triangle.

OutputVectorID
See the description in the chapter about the math functions.

IntersectedTriangleIndex
The index of the intersected triangle (see the description of GetIntersectionTime(...) for more details).

OutputVectorID
See the description in the chapter about the math functions.

IntersectedTriangleIndex
The index of the intersected triangle (see the description of GetIntersectionTime(...) for more details).

OutputVectorID
See the description in the chapter about the math functions.

IntersectedTriangleIndex
The index of the intersected triangle (see the description of GetIntersectionTime(...) for more details).

With these functions you can program custom collision response. For example you can make objects bounce back if they collide with something, or you can deform them dependent on how they collided. Anyway these collision response mechanisms are usually not what is wanted. The most common collision response mechanism still is the one with the sliding. And that is the one we will get to now. As I already said only one function is needed for this. It does all the collision detection and response automatically. Here it is.

OutputVectorID
See the description in the chapter about the math functions.

ObjectID, StartX, StartY, StartZ, DestinationX, DestinationY, DestinationZ, RotX, RotY, RotZ, ScalingX, ScalingY, ScalingZ, RoomIndex
See the description of CheckSweptEllipsoidIntersection(...).

For an example on how to use this function see the code in the step event of the camera object in the SDK. Of course one more function needs to be explained here. It already has been mentioned above and it is really simple, though here is an explanation.

SolidityState
The new solidity state, which is to be set up. This can be true, to reach that the object will be checked, if all is specified as parameter for ObjectID and if RoomIndex matches the room index of this object in a call to CheckSweptEllipsoidIntersection(...), AttemptMoveToPosition(...) or CheckRayIntersection(...). It can be false to reach that the object will not be checked if all is specified as parameter for ObjectID.

GlobalSoliditySate
The new global solidity state, which is to be set up. This can be true, to reach that the object will always be checked, if all is specified for ObjectID or false to reach that it will not be checked in this case. The difference between SolidityState and GlobalSolidityState is that GlobalSolidityState is independent from the RoomIndex parameter. Using this makes sense for objects, which are in rooms, which use enforced visibility, like doors (see SetRoomVisibilityEnforcement(...)).

This function combined with the portal engine (in particular with SetObjectRoom(...)) offers a very comfortable and efficient way to specify which objects need to be regarded by the automatic collision detection. You can use it so that objects perform collision detection always just for the objects, which are in the same room and for the objects which are between rooms, like doors (those can have global solidity set up). This makes the collision detection very efficient.

Ray tracing

Another method, which is important for collision detection is ray tracing or to be more precise the ray-mesh intersection test. A ray tracing tests checks whether a given ray intersects a piece of geometry. This is e.g. useful if you want to check, whether a weapon points at some object, to find out what is hit when the weapon is fired. To give you a a better understanding of what ray tracing means here is a more thorough explanation.

Imagine you have a ray. If you do not remember this from math at school, a ray is a straight line that begins at one point and is infinitely long. A good way to imagine this is a laser pointer. The position at which the laser pointer is, is the origin of the ray and the laser pointer emits an infinitely long ray (in theory). If you use the laser pointer to point at some object, you will see a small dot at the position where the ray meets the object. This is the point of interest. The following graphic illustrates this.

A ray-mesh intersection test uses a mathematical method to test whether the given ray intersects triangles of the given object. If so it calculates the position at which the ray first intersects the object (the blue dot on the illustration). The ray tracing function is very similar to CheckSweptEllipsoidIntersection(...), but since rays are easier to describe than swept ellipsoids it is significantly simpler.

ObjectID
See the description of CheckSweptEllipsoidIntersection(...).

RayOriginX, RayOriginY, RayOriginZ
The origin of the ray.

RayDirectionLongitude, RayDirectionLatitude
The direction of the ray. To get more information about these two parameters have a look at the description of the function Move(...).

RoomIndex
See the description of CheckSweptEllipsoidIntersection(...).

Again there are some functions to get more information about the intersected triangle.

This function outputs the normal vector of the triangle, which has been intersected by the ray specified in the last call to CheckRayIntersection(...). The normal of a triangle is a normalized vector, which lies perpendicular to the triangle and points away from its front side.

OutputVectorID
See the description in the chapter about the math functions.

This function returns the index of the material, which is used by the triangle intersected in the last call to CheckRayIntersection(...), which used a model object as parameter for ObjectID.

Using these functions you can find out more about the surrounding of an object. For example you can send a ray straight down from the hip of the character to find out how far the ground is away. Then you can use GetRayTracingNormal(...) to find out how strong the slope of the ground is at this position. And after that you can use GetIntersectedMaterialIndex() to find out, whether the character is standing on metal or on grass.

© Christoph Peters. Some rights reserved.