 ## 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 ray-mesh 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.

### Ray-Mesh 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 triangle-based 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 ray-mesh 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 Ray-Mesh 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 ray-box 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_cube = PlatformCube(L"PlatformCube.x", 10.0f, 10.0f, 10.0f, 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 ray-mesh 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->y-cube_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->y-cube_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!