

Tutorial 6  Mesh Collisions
Overview
Characters in 3D games usually interact or collide with different objects while you
control them. Here we will be looking at how to create a simple 3D platform game using
raymesh intersection tests to create walls and platforms(See Figure 13).
The idea is that you create an environment in a 3d modelling program with simple
shapes like pentagon platforms that you want to use as the objects you collide
with, where these simple shapes are invisible,
and you create a different, more complex environment that you actually see
over the top of it.
Figure 13.
Here are some modifications I made to this demo to include a character(See Figure 14).
You can download all the source for this project here:
CharacterPlatformDemo.zip
Figure 14.
Meshes
Every mesh, or 3d model in other words, in DirectX applications is made up of triangles(See Figure 15).
Figure 15.
Each triangle is made up of 3 vertices(See Figure 16), a point in 3d space for each corner of the triangle.
A triangle is also called a face.
Figure 16.
Every mesh is defined by a list of vertices, and sometimes a mesh contains
a description of how these vertices are linked up to create triangles.
For example, the first vertex in the list has index 0, the second index 1, the third
index 2 and so on. Therefore a triangle can be defined by three indices.
If two triangles, or more, share the same vertex, then both triangles can be defined by
the index of each of those vertices to save having duplicated vertices with the same
positions where they are not needed(See Figure 17).
Figure 17.
The reason I am telling you this stuff is so that the code I am about to show you will make some sense.
Rays
A ray is a point with a direction(See Figure 18), or a point and a vector of some length that has it's tail starting at the point.
Figure 18.
RayMesh Intersections
Mathematically, it is possible to find the point of intersection that a ray has with a triangle using
an equation. This allows us to determine whether a cube for example collides with a trianglebased mesh.
We can use rays therefore to make a character stop when it falls and collides with a platform such
as the pentigon platforms shown in Figure 13 above.
DirectX has a function called D3DXIntersect() that performs a raymesh intersection test and gives us
the point a ray intersects with a triangle in a mesh if there is an intersection. Note:
This function performs the intersection test with the given ray and the mesh in it's untransformed state.
There is a sample(Called Pick.sln) in the DirectX samples folder that comes with the DirectX SDK that demonstrates
how to perform a RayMesh intersection test using D3DXIntersect() or how to do it yourself. I believe
D3DXIntersect() also checks every triangle for intersection so it's a good idea to use it sparingly
otherwise you could end up with a game that runs slow.
Creating Platforms
I will go over the theory of how to create platforms such as the pentigon ones shown and then
present the code. If you are not interested in the code and would rather just use it, then
feel free to skip this part.
First, we can define the base of a cube by four corners. We want to get
the distance to the first platform downwards from the base of the cube so we
know when it should stop falling. So first we can cast a ray down for each
of the four corners.
The distance to the point of intersection with the platform mesh is how far it is to fall(See Figure 19).
Figure 19.
The ray intersection test for these corners will give us the distance to fall.
Now consider if we rotate the cube around the "Up" axis, it is possible that one of these
four rays will miss the platform or ground below.
(See Figure 20)
Figure 20.
The cube will fall straight through the platform;
To get round this problem we cast rays up from the vertices that lie within the base of the cube.
The distance from one of these rays to the point of intersection with the cube, is
how far it will take to fall onto the platform.
Figure 21.
Now it wouldn't look very good if the cube jumped upward and passed straight through objects
would it? So we want to do the same thing as described for getting the "fall" distance
but in the opposite direction to get the
"above collision distance". This will be done by casting rays up from the roof of the cube
rather than down from the base of the cube.
I won't bother explaining how this is done but if you can understand the concept for getting
the "fall" distance, you should have no problem understanding the code.
Now hopefully you understand the theory behind getting the distance to a platform above and below
a cube.
Next, there are a few more collision checks we need to perform if we want our cube to collide
properly with different sized or shaped models.
Intersection Tests
There are four basic intersection tests we can perform that don't require
too much processor power. Once we have determined if the cube intersects
with a mesh we can make the cube respond to the collision and move or rotate the
cube so it does no longer intersect with any objects:
 1. Determine if there is a vertex inside the cube
 2. Determine if there is a face inside the cube above
one of the four corners of the base of the cube  A thin pentagon platform may
sit within the cube for example if we walk/move into it.
 3. Determine if base of cube intersects a triangle.  Stops
cube from moving through large walls.
 4. Determine if roof of cube intersects a triangle.  Stops
cube from jumping through thin walls(See Figure 22).
Figure 22.
The Code
Since there is quite a bit of code I will not put it all on this web page.
I will just describe the classes used for the demo and how to use them.
You can examine their implementation if you are interested in how it all works.
You can download the source code and files here:
CubePlatformDemo.zip
Besides the classes we have already been using in previous tutorials I have added a few new ones:
 PlatformRectangle
 PlatformCube
 VertexStruct
I have also made modifications to the Camera class.
class PlatformRectangle
PlatformRectangle defines a rectangle with corners A, B, C and D given the
width and length of the rectangle we provide. It allows us to transform
the rectangle with a rotation matrix and get the transformed points
with GetCornerA(), GetCornerB(), GetCornerC() and GetCornerD().
We can then use these transformed corners to do some ray casting.
I have made an instance of this class a member of PlatformCube and
we do not use it directly at all in this tutorial, only through an instance
of PlatformCube.
class PlatformCube
PlatformCube is the main class we will be working with. It has such methods as
MoveForward(), MoveBackwards(), Turn(float degrees) and Jump() that we can use
to control the cube. If you look at Game::UpdateGame, you can see how this is done.
We then call platform_cube.Update(&platform_mesh, deltaTime) passing the mesh that contains
all the game platforms and walls as a parameter. This Update function takes care
of the speed of the cube and movement/rotation upon collisions with objects in the world.
As an example of how to include an instance of the cube we will be controlling, here
is the modified Game class:
class Game
{
public:
~Game();
bool InitGame(HWND render_window);
void UpdateGame(float deltaTime);
void RenderWorld();
private:
bool InitializeDirect3D();
void FreeAllResources();
void OnDeviceGained();
void OnDeviceLost();
private:
//Member Variables have m_ prefix
HWND m_mainWindow;
IDirect3DDevice9* m_d3dDevice;
D3DPRESENT_PARAMETERS m_present_parameters;
int m_deviceStatus;
ID3DXEffect* m_pEffect;
private:
//Helper Functions.
D3DPRESENT_PARAMETERS CreatePresentParameters(HWND render_window);
private:
Camera camera1;
Mesh platform_mesh;
PlatformCube platform_cube;
Mesh scenery;
};
You need to load the mesh defining the game platforms, "PlatformWorld.x". You also need to load the cube/box
mesh that will be used for raybox intersections, "PlatformCube.x". I have exported a cube of
dimensions 10x10x10, these need to be the same as the cube itself in the constructor parameters of
PlatformCube(...width,length,height). And finally the scenery that will be visible, "scenery1.x", as opposed to
the invisible models that are used only for collision detection.
bool Game::InitGame(HWND render_window)
{
...
platform_mesh.Load(L"PlatformWorld.X", m_d3dDevice);
platform_cube = PlatformCube(L"PlatformCube.x", 10.0f, 10.0f, 10.0f, m_d3dDevice);
scenery.Load(L"scenery1.x", m_d3dDevice);
return true;
}
You also have to free any memory used by these objects:
void Game::FreeAllResources()
{
platform_mesh.Release();
platform_cube.Release();
scenery.Release();
SAFE_RELEASE(m_pEffect);
SAFE_RELEASE(m_d3dDevice);
}
Render them:
void Game::RenderWorld()
{
...
scenery.Render("Lighting", m_d3dDevice, m_pEffect);
platform_cube.Render(m_d3dDevice, m_pEffect);
...
}
Collision Detection Methods
The following methods of PlatformCube exactly implement the theory described at the top of this
page on how to get the distance to fall and the distance to collide with an object above(See Figure 19):
float PlatformCube::GetDistanceToFall(Mesh* PlatformMesh);
float PlatformCube::GetDistanceToFall2(Mesh* PlatformMesh);
float PlatformCube::GetAboveCollisionDistance(Mesh* PlatformMesh);
float PlatformCube::GetAboveCollisionDistance2(Mesh* PlatformMesh);
The following methods return true if an intersection has actually occurred
with the cube and any of the platforms or walls:
/*
Returns true if there is a vertex inside the cube.
*/
bool PlatformCube::CubeIntersectsMesh1(Mesh* PlatformMesh)
/*
Returns true if there is a face inside the cube above
one of the four corners of the base of the cube.
*/
bool PlatformCube::CubeIntersectsMesh2(Mesh* PlatformMesh);
/*
This next function is for large walls.
Determine if base of cube intersects a triangle.
 Stops cube from moving through large walls.
*/
bool PlatformCube::CubeIntersectsMesh3(Mesh* PlatformMesh);
Example of raymesh detection code:
/*
Returns true if there is a vertex inside the cube.
*/
bool PlatformCube::CubeIntersectsMesh1(Mesh* PlatformMesh)
{
float above_collision_distance = 1000000.0f;
//Variables for D3DXIntersect()
BOOL bHit = false;
DWORD faceIndex = 0;
float tu = 0.0f;
float tv = 0.0f;
float distance = 0.0f;
DWORD FVF = PlatformMesh>pMesh>GetFVF();
//FVF = 258
//DWORD Format = D3DFVF_XYZ + D3DFVF_TEX1;
//Get the vertices of the mesh.
LPDIRECT3DVERTEXBUFFER9 pVB;
LPDIRECT3DINDEXBUFFER9 pIB;
PlatformMesh>pMesh>GetVertexBuffer( &pVB );
PlatformMesh>pMesh>GetIndexBuffer( &pIB );
WORD* pIndices;
D3DVERTEX* pVertices;
pIB>Lock( 0, 0, ( void** )&pIndices, 0 );
pVB>Lock( 0, 0, ( void** )&pVertices, 0 );
//Get the inverse world matrix of the cube.
D3DXMATRIX T, M;
D3DXMatrixTranslation(&T, cube_mesh.x, cube_mesh.y, cube_mesh.z);
D3DXMatrixInverse( &M, NULL, &(cube_mesh.rotation*T) );
//M is used to transform a coordinate by the opposite of
//the cube transformation, for example, if we moved an object
//by x,y,z, M would undo that transformation so x,y,z.
bool bInside = false;
DWORD dwNumFaces = PlatformMesh>pMesh>GetNumFaces();
for( DWORD i = 0; i < dwNumFaces; i++ )
{
//The vertex is the origin of each ray.
D3DXVECTOR3 v0 = pVertices[pIndices[3 * i + 0]].p;
D3DXVECTOR3 v1 = pVertices[pIndices[3 * i + 1]].p;
D3DXVECTOR3 v2 = pVertices[pIndices[3 * i + 2]].p;
//First Vertex.
if(rect_base.IsPointInsideRectangle(v0.x, v0.z) && v0.y > (this>ycube_height/2.0f)){
//Transform the ray so that it is relative to the inverse transform of the cube.
D3DXVec3TransformCoord(&v0, &v0, &M);
D3DXIntersect(cube_mesh.pMesh, &v0, &UpRay, &bHit, &faceIndex, &tu, &tv, &distance, NULL, NULL);
if(bHit){
//Vertex is inside cube because it intersects with the roof of the cube.
bInside = true;
break;
}
}
//Second Vertex.
if(rect_base.IsPointInsideRectangle(v1.x, v1.z) && v1.y > (this>ycube_height/2.0f)){
//Transform the ray so that it is relative to the inverse transform of the cube.
D3DXVec3TransformCoord(&v1, &v1, &M);
D3DXIntersect(cube_mesh.pMesh, &v1, &UpRay, &bHit, &faceIndex, &tu, &tv, &distance, NULL, NULL);
if(bHit){
//Vertex is inside cube because it intersects with the roof of the cube.
bInside = true;
break;
}
}
//Third Vertex.
if(rect_base.IsPointInsideRectangle(v2.x, v2.z) && v2.y > (this>y)cube_height/2.0f){//(this>y  this>cube_height/2.0f)
//Transform the ray so that it is relative to the inverse transform of the cube.
D3DXVec3TransformCoord(&v2, &v2, &M);
D3DXIntersect(cube_mesh.pMesh, &v2, &UpRay, &bHit, &faceIndex, &tu, &tv, &distance, NULL, NULL);
if(bHit){
//Vertex is inside cube because it intersects with the roof of the cube.
bInside = true;
break;
}
}
}
pVB>Unlock();
pIB>Unlock();
SAFE_RELEASE(pVB);
SAFE_RELEASE(pIB);
return bInside;
}
Conclusion
You can download the source code and files here:
CubePlatformDemo.zip
Have Fun!
