[This article continues the prelude about collision detection published here. It refreshes and completes the older Collision detection in XNA posts –parts I, II and III-, written a long time ago and which were demanded to be completed many times. Finally, here it is]
Using those tests, almost any kind of game-like intersection can be achieved. You must remember that a Mesh-Whatever intersection is expensive (depending in the number of polygons, of course), and should be left for special cases in which a very high intersection accuracy is needed. So, it’s usually preferred to approximate a complex geometry by a bunch of spheres or boxes, than using the real triangles (see Part 1).
There´s a very good post at Sharky´s blog about XNA collisions, specially focused in approximating generic shapes with bounding spheres. You can find it here.
Accurate collision detection
As commented earlier, sometimes a more accurate intersection method is needed. For example, for lighting calculations (where tracing rays are the best and more usual approach to modeling lights –see pic on your right-), the Ray-Mesh intersection test seems to be the best option. In D3D, there´s a Mesh.Intersect method ready for you, that performs the desired intersection test, but in XNA, there´s not such a method, and we will have to do it on our own.
To do it, we will need a system-memory copy of the geometry. Unfortunately, meshes are usually created with the ReadOnly flag in XNA (to make their management fast), what won´t allow us to access their geometry at runtime. To do so, we´ll have to deal with Custom Content Processing.
Note: Here you will find and introduction to Custom Content Processing.
You can put in here all the information you need. By the moment, it will be enough to store the vertices, indices and face normals.
When VisualStudio processes each model with our ContentProcessor, it will write the model´s data to an XNB file. When it finds a MeshData object, will search for a writer that is able to serialize it, so we have to write our custom ContentTypeWriter for the MeshData class:
In a similar way, when the ContentPipeline tries to read back the XNB file, it will search for a deserializer for the type MeshData, so we have to write our own ContentTypeReader:
Finally, our Custom Content Processor that fills up the MeshData objects for each model that goes through it. Note: some parts taken from ZiggyWare.
Now that we have all the information needed, we will focus in the Collision Detection implementation itself.
The following method performs a Ray-Mesh test getting as parameter a MeshData object generated by the previous content processor. Note that a lot of optimization can be done here, quick discarding triangles. Just google a bit for it.
The only part left is the Ray-Triangle intersection test, but there is so much information around the net about this issue that I´ll just leave it for you. However, you can check the following links:
http://www.devmaster.net/wiki/Ray-triangle_intersection
http://www.graphics.cornell.edu/pubs/1997/MT97.html
http://www.graphics.cornell.edu/pubs/1997/MT97.pdf
http://www.acm.org/pubs/tog/editors/erich/ptinpoly/
Hope with 4 references is enough, and that you liked the post.
Enjoy!
Simple Collision Detection
XNA includes simple intersection tests for shapes like: Bounding Spheres, AABB (Axis Aligned Bound Box), Planes, Rays, Rectangles, Frustums, etc, and any combination of them. And what is even more useful, 3D models already have bounding spheres for their parts.Using those tests, almost any kind of game-like intersection can be achieved. You must remember that a Mesh-Whatever intersection is expensive (depending in the number of polygons, of course), and should be left for special cases in which a very high intersection accuracy is needed. So, it’s usually preferred to approximate a complex geometry by a bunch of spheres or boxes, than using the real triangles (see Part 1).
There´s a very good post at Sharky´s blog about XNA collisions, specially focused in approximating generic shapes with bounding spheres. You can find it here.
Accurate collision detection
As commented earlier, sometimes a more accurate intersection method is needed. For example, for lighting calculations (where tracing rays are the best and more usual approach to modeling lights –see pic on your right-), the Ray-Mesh intersection test seems to be the best option. In D3D, there´s a Mesh.Intersect method ready for you, that performs the desired intersection test, but in XNA, there´s not such a method, and we will have to do it on our own.
To do it, we will need a system-memory copy of the geometry. Unfortunately, meshes are usually created with the ReadOnly flag in XNA (to make their management fast), what won´t allow us to access their geometry at runtime. To do so, we´ll have to deal with Custom Content Processing.
Note: Here you will find and introduction to Custom Content Processing.
Implementing a Custom Content Processor for collision detection
The solution to the previous problem is to make a custom content processor that stores a copy of the geometry information at build time, where there´s still access to it. All the information needed will be stored in a new class we will name MeshData.
public class MeshData
{
public VertexPositionNormalTexture[] Vertices;
public int[] Indices;
public Vector3[] FaceNormals;
public MeshData(VertexPositionNormalTexture[] Vertices, int[] Indices, Vector3[] pFaceNormals)
{
this.Vertices = Vertices;
this.Indices = Indices;
this.FaceNormals = pFaceNormals;
}
}
When VisualStudio processes each model with our ContentProcessor, it will write the model´s data to an XNB file. When it finds a MeshData object, will search for a writer that is able to serialize it, so we have to write our custom ContentTypeWriter for the MeshData class:
[ContentTypeWriter]
public class ModelVertexDataWriter : ContentTypeWriter<MeshData>
{
protected override void Write(ContentWriter output, MeshData value)
{
output.Write((int)value.Vertices.Length);
for (int x = 0; x < value.Vertices.Length; x++)
{
output.Write(value.Vertices[x].Position);
output.Write(value.Vertices[x].Normal);
output.Write(value.Vertices[x].TextureCoordinate);
}
output.Write(value.Indices.Length);
for (int x = 0; x < value.Indices.Length; x++)
output.Write(value.Indices[x]);
output.Write(value.FaceNormals.Length);
for (int x = 0; x < value.FaceNormals.Length; x++)
output.Write(value.FaceNormals[x]);
}
public override string GetRuntimeType(TargetPlatform targetPlatform)
{
return typeof(MeshData).AssemblyQualifiedName;
}
public override string GetRuntimeReader(TargetPlatform targetPlatform)
{
return "ContentProcessors.ModelVertexDataReader, ContentProcessors, Version=1.0.0.0, Culture=neutral";
}
}
public class ModelVertexDataReader : ContentTypeReader<MeshData>
{
protected override MeshData Read(ContentReader input, MeshData existingInstance)
{
int i = input.ReadInt32();
VertexPositionNormalTexture[] vb = new VertexPositionNormalTexture[i];
for (int x = 0; x < i; x++)
{
vb[x].Position = input.ReadVector3();
vb[x].Normal = input.ReadVector3();
vb[x].TextureCoordinate = input.ReadVector2();
}
i = input.ReadInt32();
int[] ib = new int[i];
for (int x = 0; x < i; x++)
ib[x] = input.ReadInt32();
i = input.ReadInt32();
Vector3[] normals = new Vector3[i];
for (int x = 0; x < i; x++)
normals[x] = input.ReadVector3();
return new MeshData(vb, ib, normals);
}
}
[ContentProcessor(DisplayName = "Custom Mesh Processor")]
public class PositionNormalTexture : ModelProcessor
{
public override ModelContent Process(NodeContent input, ContentProcessorContext context)
{
ModelContent model = base.Process(input, context);
foreach (ModelMeshContent mesh in model.Meshes)
{
// Put the data in the tag.
VertexPositionNormalTexture[] vb;
MemoryStream ms = new MemoryStream(mesh.VertexBuffer.VertexData);
BinaryReader reader = new BinaryReader(ms);
VertexElement[] elems = mesh.MeshParts[0].GetVertexDeclaration();
int num = mesh.VertexBuffer.VertexData.Length / VertexDeclaration.GetVertexStrideSize(elems, 0);
vb = new VertexPositionNormalTexture[num];
for (int i = 0; i < num; i++)
{
foreach (VertexElement e in elems)
{
switch (e.VertexElementUsage)
{
case VertexElementUsage.Position:
vb[i].Position.X = reader.ReadSingle();
vb[i].Position.Y = reader.ReadSingle();
vb[i].Position.Z = reader.ReadSingle();
break;
case VertexElementUsage.Normal:
vb[i].Normal.X = reader.ReadSingle();
vb[i].Normal.Y = reader.ReadSingle();
vb[i].Normal.Z = reader.ReadSingle();
break;
case VertexElementUsage.TextureCoordinate:
if (e.UsageIndex != 0)
continue;
vb[i].TextureCoordinate.X = reader.ReadSingle();
vb[i].TextureCoordinate.Y = reader.ReadSingle();
break;
default:
Console.WriteLine(e.VertexElementFormat.ToString());
switch (e.VertexElementFormat)
{
case VertexElementFormat.Color:
reader.ReadUInt32();
break;
case VertexElementFormat.Vector3:
reader.ReadSingle();
reader.ReadSingle();
reader.ReadSingle();
break;
case VertexElementFormat.Vector2:
reader.ReadSingle();
reader.ReadSingle();
break;
}
break;
}
}
} // for i < num
reader.Close();
int[] ib = new int[mesh.IndexBuffer.Count];
mesh.IndexBuffer.CopyTo(ib, 0);
Vector3[] normals = new Vector3[mesh.IndexBuffer.Count / 3];
for (int i = 0, conta = 0; i < mesh.IndexBuffer.Count; i += 3, conta++)
{
Vector3 v0 = vb[mesh.IndexBuffer[i]].Position;
Vector3 v1 = vb[mesh.IndexBuffer[i + 1]].Position;
Vector3 v2 = vb[mesh.IndexBuffer[i + 2]].Position;
Vector3 edge1 = v1 - v0;
Vector3 edge2 = v2 - v0;
Vector3 normal = Vector3.Cross(edge1, edge2);
normal.Normalize();
normals[conta] = normal;
}
mesh.Tag = new MeshData(vb, ib, normals);
} // foreach mesh
return model;
}
}
Implementing the Ray-Mesh test using the MeshData
Many people thinks that the D3D Mesh.Intersect method does some kind of optimized "magic" to test for intersection, but in fact it just loops through all the triangles of the mesh doing a triangle-ray intersection test, and keeping track of the closest collision point (or all of them, depending on the overloaded version you use). Of course it applies some well known optimizations, like quick discarding polygons, back faces, and so on. That is exactly what we have to do now with the info generated at the Content Processor.The following method performs a Ray-Mesh test getting as parameter a MeshData object generated by the previous content processor. Note that a lot of optimization can be done here, quick discarding triangles. Just google a bit for it.
public static bool RayMesh(Vector3 orig, Vector3 dir, MeshData pMesh, ref Vector3 pContactPoint, ref float pDist, ref int pFaceIdx)
{
Vector3 maxContactPoint = Vector3.Zero;
int maxFaceIdx = -1;
float minT = float.MaxValue;
for (int i = 0, countFace = 0; i < pMesh.Indices.Length; i += 3, countFace++)
{
int ia = pMesh.Indices[i];
int ib = pMesh.Indices[i + 1];
int ic = pMesh.Indices[i + 2];
Vector3 v0 = pMesh.Vertices[ia].Position;
Vector3 v1 = pMesh.Vertices[ib].Position;
Vector3 v2 = pMesh.Vertices[ic].Position;
double t = 0f;
double u = 0f;
double v = 0f;
if (RayTriangle(orig, dir, v0, v1, v2, ref t, ref u, ref v))
{
Vector3 appPoint = orig + (dir * (float)t);
if (t < minT)
{
minT = (float)t;
maxFaceIdx = countFace;
maxContactPoint = appPoint;
}
}
}
pContactPoint = maxContactPoint;
pFaceIdx = maxFaceIdx;
pDist = minT;
return (minT < float.MaxValue);
}
http://www.devmaster.net/wiki/Ray-triangle_intersection
http://www.graphics.cornell.edu/pubs/1997/MT97.html
http://www.graphics.cornell.edu/pubs/1997/MT97.pdf
http://www.acm.org/pubs/tog/editors/erich/ptinpoly/
Hope with 4 references is enough, and that you liked the post.
Enjoy!
As you can see, it has a VERY LOW level of detail. Take a look at the shadow the box projects to the floor. It is a gradient through the geometry, where no vertex appears, so that gradient cannot be hold by Vertex Lighting. 
They were widely used in Quake to store lighting and are a great way to add realism to your 3D engine. Since then, Lightmaps are a must in any modern 3D application. 
