XNA Collision Detection for 3D models – Part 3

January 30th, 2007 by Sharky

kick it on GameDevKicks.com 

After some technical difficulties with Windows Live Writer, I think I’m back in action.

;)

So continuing from where I left off in Part 2 (part 1 is here)…

What about this BoundingPart class then?

As mentioned earlier it wraps a Collection of BoundingSphere’s. Well actually it contains two Collections of BoundingSpheres.

  1. One collection is the sphere’s populated as we saw above. These sphere’s coordinates are in Object Space and are populated when the Model is first loaded.
  2. The second collection is for holding Transformed versions of these spheres. Their coordinates will be transformed into World Space, and the Radius scaled on each frame of our game. Think of these as being the Spheres as they are positioned and scaled in our game’s world. This is necessary so we can test for Collisions! Object Space simply wouldn’t cut the mustard, since it would be equivalent to having all our models stacked on top of each other at the same (0,0,0) position. They’d always be colliding like some kind of roman orgy. World Space puts them in their rightful place with their hands in their pockets.

To help with the Transformation, the BoundingPart also contains an individual BoneTransform matrix that was grabbed earlier in GetBoneTransforms(), and set during the BuildBoundingParts() method.

There is also a Name & Colour (english spelling) thrown in for good measure – debug purposes really.

There’s not much to say about the Intersects() method. It simply tests all this BoundingPart’s spheres for collision with all of another BoundingPart’s spheres. If any are colliding it will return true and things should go BANG!!!

/// <summary>
/// Returns True if any of this BoundingPart's BoundingSpheres collide with the given BoundingSphere.
/// </summary>
/// <param name="boundingPart"></param>
/// <returns></returns>
public bool Intersects(BoundingSphere boundingSphere)
{
foreach (BoundingSphere thisBS in _boundingSpheresTransformed)
{
if (thisBS.Intersects(boundingSphere))
{
return true;
}
}
return false;
}

However, there’s no point calling Intersects() if our game hasn’t called Transform() first!

When called, the Transform() method updates the collection of transformed Spheres into World Space ready for collision detection. It will be called on each frame, and given the exact same scale & matrices used to eventually render the model on screen.

/// <summary>
/// Transform each of the part's BoundingSpheres into it's World Space position, scale & orientation.
/// The resulting transformed BoundingSphere's can then be used to test for Collisions.
/// </summary>
/// <param name="scale"></param>
/// <param name="rotationMatrix"></param>
/// <param name="positionMatrix"></param>
public void Transform(float scale, Matrix rotationMatrix, Matrix positionMatrix)
{
int bsIndex = 0;
foreach (BoundingSphere bs in _boundingSpheres)
{
Matrix scaleMatrix = Matrix.CreateScale(new Vector3(scale));
#if BONE_TRANSFORM
Matrix localWorld = _boneTransform * rotationMatrix * scaleMatrix * positionMatrix;
#else
Matrix localWorld = rotationMatrix * scaleMatrix * positionMatrix;
#endif
BoundingSphere bsTransformed = _boundingSpheresTransformed[bsIndex];
bsTransformed.Center = Vector3.Transform(bs.Center, localWorld);
//BoneTransforms can include some scaling, so scaling the radius by our defined scale may not be sufficient.
//Big thanks to Shawn Hargreaves (http://blogs.msdn.com/shawnhar/default.aspx) for the following solution using localWorld.Forward.Length() instead.
bsTransformed.Radius = bs.Radius * localWorld.Forward.Length();
_boundingSpheresTransformed[bsIndex] = bsTransformed;
bsIndex++;
}
}

NOTE: there is a conditional compile switch “BONE_TRANSFORM” used in the sample. Try removing this switch if you’d like to see what happens when the BoneTransforms are ignored. Fun and hilarity may ensue.

Mini me, you complete me

Just to complete the picture, I simply call the Transform() method on all my Model’s BoundingPart’s with each frame.

So burried in my game’s Update() method is the following code:

foreach (BoundingPart bp in _modelBoundingParts)
{
bp.Transform(_modelScale, rotationMatrix, positionMatrix);
}

The important thing here, is that the scale and Matrices passed in need to be the same as used when the model eventually Renders in the Draw() method.

Wrapping up

Besides what I’ve covered in the tutorial so far, the rest of the Working Sample is devoted to rendering the model and it’s Transformed spheres. There is a fairly rushed and dodgy 3D Mouse cursor for testing collisions. It goes White when a collision is detected, otherwise black. You use the mouse scroll wheel to move the cursor in & out of the scene.

Working Sample
If you haven’t already got it, you can download the sample code here.I think that about covers all the essentials. I’m bound to have forgotten something, so no doubt I’ll refine this post further.Remember, your comments & feedback are most welcome. (click on the “comments” link to add a comment)

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

  1. Ultrahead Says:

    “The second collection is for holding Transformed versions of these spheres. ”

    An idea: if you can hold both the BoundingSpheres created by default by XNA for each MeshPart and your BoundingPart, you could skip the process of transforming the spheres each frame and instead, you could only transfor each frame per request.

    I mean, let’s say you can check collision on the default bounding sphere of any models (”default” = the big one that encloses a MeshPart of the model), then if two default BS collide, you:
    1) start querying down each “child” sphere in the respective BoundingParts.
    2) for each sphere queried, call the Tranform method (but only to affect that BS, so the Transform method must be modified accordingly).
    3) check for collisions between current child spheres.

    If no collisions were found, just continue from 2) for next pair of “child” bounding spheres until you find a collision or the query ends (no collision).

    That way you avoid the following things:
    1) To call the Transform() method every frame.
    2) To transform child BS that you won’t be using that frame (either beacuse there was no collision between default BS or if it was, you found a collision in a former child node).
    3) To check for collision of all “child” BS each frame (you will check only those that you need, of course, you need to set a criteria like “check the BS with the largest surface first” or so).

    I’m just thinking loud as I type so my apologies if I’m not clear enough …

  2. Ultrahead Says:

    Errata: “… you could only transfor each frame per request.” … it should say “… you could tranform those “child” BS that need processing on a per-case basis” …

    As Sharky’s remarked “comments and feedback are most welcome” … :)

  3. Sharky Says:

    Yeah, I agree. Definately room for optimizing. I’m pretty sure you’d still have to Transform() at least one sphere on every Update regardless.

    XNA’s “default” sphere is still in Object Space.

  4. Ultrahead Says:

    “I’m pretty sure you’d still have to Transform() at least one sphere on every Update regardless.”

    Yes, the default one, the main one, the partent of all childs in the BoundingPart, the … well, you know …

    What I’m going to say is not applicable to your project since there are only two planes fighting each other, but imagine a lot of planes -and thus, meshparts- that must be checked for collisions every frame. If you can find a way to “truncate” the loop when needed, unless you really need to check all of the nodes, the better …

  5. Sharky Says:

    Yeah, for sure.

    :)

  6. Ultrahead Says:

    I also agree with Benjamin’s comment on this post (abi): http://sharky.bluecog.co.nz/?p=108, regarding polygon-based collision testing.

    I don’t know whether I’d prefer to check for collisions on the original mesh, but I’m sure I’d love to do it for a simplied version of that mesh (and with “simplified version” I mean a second mesh built with the sole purpose of enclosing the original mesh for collision testing) so as to gain some performance at the expense of accuracy (not as simple as checking AABB, OBB, and BS but still less faces to check than with the original mesh) …

  7. xtamillion Says:

    To optimize: use two AABB covering the entire planes and just check if anything collide with the boxes ;-) stop testing after one hit is a bad design imo as you can probably bit the plane several times, and i doubt the benefits will be bigger then the complexity. by creating big primary boxes you can just create a few big ones covering multiple rounds for even bigger effect. That way you can reduce 20 spheres on the plane + 100 shots to perhaps 1 for the plane and 10 for the shots as a rough test. If your half as bad a pilot as me that would reduce the collision detection a lot =P

  8. Sharky Says:

    Yep. Although, transforming an AABB for the plane’s rotation, is more of a deform really (see part 1).

    Because it is axis-aligned, it wouldn’t always adequately enclose the entire model, so I would think an “primary” Sphere would still be better?  Unless a non-AABB can be implemented?

  9. Ultrahead Says:

    Yes OOB can be implemented (remember this post: http://amapplease.blogspot.com/2007/01/oob-intersection-test-using-xna-as-we.html), but a boundingsphere approach works quite ok …

    Glad to see that you’ve implemented the tree approach to optimize your collision testing process …

  10. Chris Says:

    http://andyq.no-ip.com/blog/?p=16

    this blog contains code for a dll to help with making a bb from the mesh
    haven’t tried it yet but looks promissing. It creates a handler for the content pipeline that stores the bb in the tag property of the mesh.

  11. Banzai Says:

    I have created a 3D level and collision mesh for it (optimized version, takes a few hundred faces off) and I must admit I am Not a great programmer, more of a technical designer. Is there anyway I can just use the mesh I made for collision or am I going to have to sphere/box the whole darn thing? For an entire level that could take a while….

  12. Sharky Says:

    Banzai, sorry I’m really not sure. I’m no expert I’m afraid.

    Have you asked in the http://creators.xna.com forums? Someone will know, and the microsoft fellas are very good at responding too.

  13. Andrew Cooper Says:

    I’v created a setup at the moment and i’m having trouble with the Boinding Sphere’s not being inline with the “ModelMesh”. If you could please tell me how to determin the Location and Radius of a Bounding Sphere for a ModelMesh it would be a great help. Its probally in you demo app, but i cant see it. Thanks.

  14. I make indie xbox 360 games Says:

    Thanks for the tutorial, im new to 3D game development and I must say that I’m still clueless to many aspects, I couldn’t even begin to imagine 3d physics *cry*.

    Anyways I wanted to mention to Banzai that you do not need to use a bounding box to check ground collision, the only way I know of that is “easier” is getting all the Y points of the models height points and then check that vs the y point of your model, if that makes sense.

  15. Sharky Says:

    Thanks. I’m glad the tutorial is still helping people. I really should update it for XNA 4.0.

    In my own projects I have also changed the MeshInfo xml files to a content type loaded with the Content Manager.

  16. Jonathoin Gohan Says:

    Thanks Sharky . thank u so much………

    Really this tutorial is like a helping hand in our project where we thought collision detection would be of great difficulty…..

    thank u so much ……….

    if u don’t mind can we have ur mail id please.

    thanks sharky

  17. Tyson Zangetsu Says:

    Thanks a lot Sharky………i was able to complete the collision detection easily with ur help.

    arigatho

  18. Jegan Srinivas Ram Says:

    i was working with collision detection with the source code u have uploaded and the tutorial u have posted in the site to make collision detection in my game….but when i was following i felt that the source code was advanced than that u have posted in the site………so could u please mail me the old source code or please update the site……or help me abt how to create a proximity sphere for my model…………..help me pls

  19. Sharky Says:

    Hi Jegan.

    The old source code that matches the tutorial text is here…

    http://sharky.bluecog.co.nz/uploads/code/Sharky.3DCollisionDetection.Tutorial_v1.0.0.2.zip

    It’s so long ago that I don’t remember what version of XNA Game Studio you would need to open the project.

    I’m sorry I can’t update the tutorial text right now, as I’m right in the middle of completing my second game for publishing. I certainly would like to update it one day, but I have no idea when that would be.

  20. Playfa Says:

    hi Sharky,
    i really need updated version (XNA 4.0),
    did you develop it for xna 4.0?

  21. Sharky Says:

    Hey there.

    I can’t remember if the version I’m using at home is XNA 4 yet. I’ll have a look.
    There is a XNA v3 version on my blog however.

    here…
    http://sharky.bluecog.co.nz/?p=311

    Hopefully not too difficult to upgrade.

    cheers,

    Lawrence.

Leave a Reply