XNA Collision Detection for 3D models – Part 2

January 30th, 2007 by Sharky

kick it on GameDevKicks.com 

Hi there.

In Part 1 of this tutorial we looked briefly at one of the simplest techniques for collision detections – the radius (forgive me, if there’s a fancy name for it). A perfectly adequate solution for some games.

We also looked into what XNA has to offer out of the box, and why the BoundingBox class may not be suitable for some games, due to it’s Axis Aligned nature, and how that doesn’t work so well with rotated models.

If you missed part 1, check it out here

Meanwhile, lets get on with this 2nd, and if all goes well, final part. By the end of this I hope I’ll have shared some sort of solution. I see it as an interim solution as I really hope Microsoft will address this in a future version of XNA.

In Part 1 I mentioned that there would be no working code sample. I lied. I found it so difficult to explain it all from bits and pieces of my game’s code, that I bit the bullet and made a working sample.

As you may already be aware, I’ve published this sample on the blog already. Feel free to grab it over here. I will be refering to code in the sample throughout the rest of this tutorial.

Bye bye BoundingBox, hello BoundingSphere.

Besides BoundingBox, XNA provides an BoundingSphere class for collision detection. Once again, it is purely a non-visual class with an Intersects() method to tell you if your BoundingSphere collides with another.

e.g.

if (bulletBoundingSphere.Intersects(planeBoundingSphere))
{
//plane's been hit. cue smoke, flames, snakes in a panic, singing nuns, whatever...
}

…yes, I’m a movie fan.

In true movie style let’s flashback to part 1 briefly… Remember this bit???

What is not immediately obvious is this:

  • it’s up to you to update the position of these objects, as the visual thing they represent moves around the the game’s world.
  • You may even scale your model, so perhaps the BoundingBox/Sphere would need to be scaled too.
  • Your game’s 3D model may also be rotated at times, so your collision detection needs to be be able to handle that.

Well, a sphere is a sphere no matter how you rotate it. So with rotation out of the picture, we no longer have the Axis Aligned Bounding Box (AABB) issue to complicate things. We will still need to update the BoundingSphere’s position in the world, and since our model may be scaled the size of our BoundingSphere would need to be scaled too.

Journey to the Center of the… BoundingSphere

…ok, another movie reference slipped in there.

Moving right along then. A BoundingSphere is even simpler than a BoundingBox. All it really has is a Center, represented by a Vector3 type (i.e. X, Y, Z), and a Radius. When our model moves we’ll need to move the Center to the corresponding place in the world. We would also need to adjust the Radius if the Model’s size is scaled.

With all this talk about BoundingSphere’s, you’re possibly wondering “ok, so where do these BoundingSphere’s come from?”

Well, you can instantiate them yourself easy enough, but there’s no great need to. XNA’s Model class automatically creates a BoundingSphere for each ModelMesh within the model.

(my game’s spitfire Model has several ModelMeshes. e.g. Wings, Fuselage, Cockpit, Propeller, Tail etc…)

Here is an example of how you might iterate through a loaded Model’s BoundingSpheres…

//Load the model using my game's instance of a ContentManager.
Model myModel = MyGame.ContentManager.Load<Model>("ContentMeshesMyModel");
 
foreach (ModelMesh mesh in myModel.Meshes)
{
//Do stuff with mesh.BoundingSphere
}
 

When XNA’s ContentManager loads the Model, it creates, positions and sizes a BoundingSphere to surround each part of the model. The position, mesh.BoundingSphere.Center, is essentially an offset from the entire Model’s center (x=0,y=0,z=0). I believe that’s sometimes refered to as “Object space” coordinates. Not to be confused with “World space” coordinates that describe a position within an entire scene.

If you could actually render these BoundingSphere’s they’d look something like this on my Spitfire model…

Plane in BoundingBox

You’ll see there’s a sphere for each part of my plane Model:

  • Bright green for the Wings
  • Orange for the tail
  • etc…

These “default” BoundingSphere’s may be perfectly adequate depending on the shape of your model. In the case of my game’s Spitfire Model, they simply aren’t good enough though. Overall they’d make my plane seem an even bigger target than if I’d just used the single Radius technique mentioned in Part 1!

Let’s fix that…

Divide and Conquer

While these “default” BoundingSphere’s don’t really cut the mustard, they still give us some indispensable runtime information about our model. So we’re going to use that information to make multiple new BoundingSphere’s that fit our model’s shape better.

Like this…

Plane in BoundingBox
Plane in BoundingBox

We will generate these new BoundingSpheres immediately after the Model is loaded, and store them for later use. Here’s how I’ve done it. (I’m sure there’s room for improvement, so comments are welcome).

Take a look at the sample code now and you’ll see in the MyGame.cs class I have the following code…

private void AnalyseModel()
{
//Take a copy of the Model's BoneTransforms (transforms to be applied to each part of the model)
GetBoneTransforms();
 
//Build BoundingParts for Collision Detection
BuildBoundingParts();
}
 
private void GetBoneTransforms()
{
_modelBoneTransforms = new Matrix[_model.Bones.Count];
_model.CopyAbsoluteBoneTransformsTo(_modelBoneTransforms);
}

You’ll see that immediately after Loading the Model with the ContentManager, I call the AnalyseModel() method.

GetBoneTransforms() grabs a copy of the loaded Model’s BoneTransform Matrices for use later. Put simply, the BoneTransform’s tell XNA how to position, rotate (possibly even scale) different parts of our Model. If we ignored them, our Plane’s parts (e.g.Wings, Fuselage, Tail) could be arranged quite differently to how the 3D Model Designer intended.

Yaaawwwwnnnn….

Yes, this is all very exciting, so here’s a good stuff. Near the top of the MyGame.cs class you’ll see the following intriguing code…

//Blob mesh
private string[] _modelBoundingPartNames = new string[]
{
"Fuselage",
"Wing",
"Tail"
};
 
private Color[] _modelBoundingPartColours = new Color[]
{
Color.Blue,
Color.Red,
Color.GreenYellow
};
 
 
private Vector4[][] _modelBoundingPartSubdivisions = new Vector4[][]
{
//Fuselage
new Vector4[] { new Vector4(0.50f, 0.10f, 0.46f, 0.20f),
new Vector4(0.50f, 0.30f, 0.46f, 0.27f),
new Vector4(0.50f, 0.60f, 0.48f, 0.26f)
},
//Wing
new Vector4[] { new Vector4(0.07f, 0.51f, 0.50f, 0.20f),
new Vector4(0.30f, 0.515f, 0.50f, 0.25f),
new Vector4(0.50f, 0.515f, 0.50f, 0.27f),
new Vector4(0.70f, 0.515f, 0.50f, 0.25f),
new Vector4(0.93f, 0.51f, 0.50f, 0.20f)
},
//Tail
new Vector4[] { new Vector4(0.25f, 0.52f, 0.45f, 0.40f),
new Vector4(0.50f, 0.56f, 0.53f, 0.55f),
new Vector4(0.75f, 0.52f, 0.45f, 0.40f)
}
};
 

These arrays are used later in the sample, but the key one to study here is the _modelBoundingPartSubdivisions array.

It describes how we’ll make new BoundingSphere’s out of XNA’s “default” ones that get generated for us when the Model is first loaded.

Observe how the Wing will be made up of 5 spheres defined by Vector4 types. A Vector4 is essentially an X, Y, Z & W float all wrapped up into a type. I’m using the X, Y & Z to represent percentages to offset of our new sphere’s in the X, Y & Z axis. The W represents a percentage to scale the Radius.

Now, at last, take a look at the BuildBoundingParts() method and see how this stuff remarkably has a purpose!…

/// <summary>
/// Builds a collection of BoundingParts for each ModelMesh in the Model.
/// Each BoundingPart will contain one or many BoundingSphere as defined in the _modelBoundingPartSubdivisions array.
/// </summary>
private void BuildBoundingParts()
{
_modelBoundingParts = new List<BoundingPart>();
 
BoundingPart boundingPart;
 
int meshIndex = 0;
foreach (ModelMesh mesh in _model.Meshes)
{
BoundingSphere[] pieces = new BoundingSphere[_modelBoundingPartSubdivisions[meshIndex].Length];
int pieceIndex = 0;
 
//Create, Scale and Position new BoundingSphere's according to the defined subdivisions for this part of the model.
foreach (Vector4 subdivision in _modelBoundingPartSubdivisions[meshIndex])
{
//Determine the new BoundingSphere's Radius
float radius = subdivision.W * mesh.BoundingSphere.Radius;
 
//Determine the new BoundingSphere's Center by interpolating.
//The subdivision's X, Y, Z represent percentages in each axis. They will used across the full diameter of XNA's "default" BoundingSphere.
float x = MathHelper.Lerp(mesh.BoundingSphere.Center.X - mesh.BoundingSphere.Radius, mesh.BoundingSphere.Center.X + mesh.BoundingSphere.Radius, subdivision.X);
float y = MathHelper.Lerp(mesh.BoundingSphere.Center.Y - mesh.BoundingSphere.Radius, mesh.BoundingSphere.Center.Y + mesh.BoundingSphere.Radius, subdivision.Y);
float z = MathHelper.Lerp(mesh.BoundingSphere.Center.Z - mesh.BoundingSphere.Radius, mesh.BoundingSphere.Center.Z + mesh.BoundingSphere.Radius, subdivision.Z);
Vector3 centre = new Vector3(x, y, z);
 
pieces[pieceIndex] = new BoundingSphere(centre, radius);
 
pieceIndex++;
}
boundingPart = new BoundingPart(pieces, _modelBoneTransforms[mesh.ParentBone.Index], _modelBoundingPartNames[meshIndex], _modelBoundingPartColours[meshIndex]);
 
_modelBoundingParts.Add(boundingPart);
meshIndex++;
}
}
 

I’ll get on to explaining the BoundingPart class later. For now, all you need to know is that it is a wrapper class that contains multiple BoundingSphere objects. This method populates a collection of BoundingPart’s (one per ModelMesh in the Model), and the BoundingSphere collections within them.

Here’s how it works…

I iterate through each ModelMesh in the model.

Using it’s index I then iterate through the matching indexed _modelBoundingPartSubdivisions array.

This gives me a Vector4 to play with and using XNA’s MathHelper.Lerp method (lineer interpolation) I use the X, Y, Z & W to construct a new sphere’s Center and Radius.

I love Lerp. Lerp is cooler than The Fonz! Basically it lets you say “give may the value that’s 70% between 100 & 200″.

0% is 100.

100% is 200.

So 70% must be 170.

In the case of this code I’m using the Radius of the XNA’s “default” sphere to give me the ranges.

e.g. The min value is it’s Center.X – Radius. The max value is the Center.X + Radius. So I Lerp between these values with the subdivision’s X.

The BoundingPart class get’s populated with these freshly tailored spheres, and then added to the main collection.

Ok, so now I’m having technical difficulties with Windows Live Writer. I think my tutorial has got too long, so I’ll stop now and do the rest in a Part 3 shortly…

17 Responses to “XNA Collision Detection for 3D models – Part 2”

  1. Ultrahead Says:

    “So 70% must be 170.” … :)

  2. John Says:

    How do you know the vector 4 values? Is their a way to calculate this during runtime?

    //Tail
    new Vector4[] { new Vector4(0.25f, 0.52f, 0.45f, 0.40f), new Vector4(0.50f, 0.56f, 0.53f, 0.55f), new Vector4(0.75f, 0.52f, 0.45f, 0.40f)

  3. Sharky Says:

    Hi John.

    The Vector4 values are where you can get creative.

    You choices really depend on the shape of that particular piece of the model.
    Something long and thin like a wing for instance. You might choose to define 3 or 4 smallish spheres along whatever Axis the wing goes. The spheres near the wing tips will likely be a little smaller the the one(s) around the center, because that’s typically how wings go.

    For something fat and generally spherical like a propeller cone, you might do just 1 sphere.

    The important thing to remember is that the values in the Vector4’s are like percentages along an imaginary line in the given Axis (0.5 = 50%, 1 = 100%). Where the length and center of the line is determined by XNA’s default sphere (a sphere that exactly surrounds that bit of the model).

    Hope that clarifies things a little more. :)

  4. Me Says:

    but it’s not on runtime…

  5. sueds Says:

    I would like to know if its possible to use this method in a not subdived character ?

  6. Sharky Says:

    Hi Sueds.

    I think you could still use this technique but your Model would only have one ModelMesh in its Meshes property. That ModelMesh would therefore have a default bounding sphere big enough to surround the whole model. You could use its radius to position and scale a bunch of BoundingParts just as I do in the tutorial.

    p.s. I just remembered this sample is still for XNA 1.0. I really should convert it to 2.0 one day. The ideas the same.

  7. Michael Says:

    Nice work, i’ve always found collision quite tricky, this will be a great help.

    lol at Lerp being cooler then the Fonz

  8. Tin Says:

    how to generate _modelBoundingPartSubdivisions array.??

  9. mike rothery Says:

    just been introduced to xna coding through uni, i am more of a graphics man.

    currently working on a version of the classic ‘asteroids’ though in mine you shoot at russian sats lol. Anyhow my boundingsphere code is pinched from the tutorial ‘Make a game in 60 mins’ > http://msdn.microsoft.com/en-us/library/bb975644.aspx <

    i am having trouble as they seem to happen at random rather than as expected can you possibly give me some pointers (well more pointers) as to make these collisions more reliable

    would be much appreciated

  10. mike rothery Says:

    infact i must say… most my code is from that tutorial … man thats a weight off my chest … just with additions such as a timing system and ways to reward objectives within the game

  11. Sharky Says:

    Hi Mike.

    This is the first time I’ve actually looked at the “60 mins” tutorial, but here’s a thought to consider…

    Do you scale you models when you draw them at all?

    In the their tutorial they don’t appear to be scaling their model when it draws. So their mesh’s BoundingSphere.Radius will be correct.
    However, if you are scaling your models, you need to make sure you factor that into the BoundingSphere size as well.

    So, if you Draw your models at 3 times the size, remember to triple the mesh’s BoundingSphere.Radius as well.
    Likewise if you are making things smaller.

  12. mike rothery Says:

    thanks for the swift reply,
    unfortunately i am not scaling all of that is done within maya before exporting it as a suitable fbx file, quite the ball ache as it’s a case of trial and error lol, if you have any other ideas would be great however thanks for even taking the time, glad to see masters of xna willing to help us beginners.

    take care

  13. Sharky Says:

    LOL.

    Hmmmm…. puzzling.

    Best bet is being able to visualize what these BoundingSpheres look like.
    If you look at my sample I have a code for rendering the spheres.
    See you if you can hack that into your code. It might give you a clue as to what’s going wrong. Like, are they too big? in the wrong place? etc…

    Debug rendering stuff is great when you’ve got it working. But while I was debugging that I was not always sure if it was my debug rendering code at fault, or truly the Spheres. I got it working in the end, so perhaps you could try that too.

  14. mike rothery Says:

    can i also offer my graphics to you (free of charge),

    would be great to have such a chance, though if thats your own plane not only hats off; as i think its cool, but can understand why you don’t want mine :P

    again take care my man

  15. Sharky Says:

    the other possibility is the exported model could be at fault. XNA ContentPipeline is simply deriving the BoundingSphere from the exported model.

    So with Debug rendering of the spheres you could check the sphere represents the extent of your model’s geometry, and is not wildly different.

    The modeling tool/export you use may be exporting Camera/lighting objects etc… as part of the FBX and confusing things perhaps?

  16. mike rothery Says:

    … your reply hadn’t come up when was typing lol

    cheers for input

  17. Sharky Says:

    no problem.

    Actually to test the exported model itself you could just take my sample, and substitute your FBX model into it to see the spheres.

    • Add it to the Content\Meshes
    • Add a texture file with a matching name in Content\Textures.
    • Add a really simple XML file with matching name into the MeshInfo folder. something with just one BoundingPart with xyz’s=0.5, 0.5, 0.5 and w=1.0
    • Change the line of code that defines which model it loads. private string _modelContentName = "TutorialPlane";

    … and voila, you should see what XNA’s derived sphere looks like.

Leave a Reply