January 18th, 2007 by Sharky

kick it on GameDevKicks.com 

Greetings earthlings.

My game build releases have been a bit sparse lately. So you’re possibly wondering what I’ve been working on. Well, as the title suggests – Collision Detection.

The technique used in the current release of my game is as simple as they come, and it’s been bugging me. I haven’t released it yet, but the next release of my game will have much improved collision detection.

But boy, has it been a struggle! There has been a real lack of collision detection tutorials relating to 3D models under XNA, so I’ve had to learn the hard way. So I’m going to attempt to share what I’ve learnt, and hopefully save some other poor souls the pain.

First a caveat…

I don’t claim to be an expert on this subject at all – not by a long stretch. But hopefully I’ll be at least close to correct. Also, this is not really a tutorial either. Don’t expect a working sample with source code. I may get round to that later. Right now my code is a bit embarrassing, given the experimental nature of what I was trying to do.

Second caveat…

these enhancements to my game are not yet released. So for now you’ll just have to trust me when I say it is an improvement. Stay tuned.

The Radius technique…primitive.

The simplest collision detection technique of all is to simply imagine a radius around all your object’s world positions. Then it is just a matter of checking whether any two objects have come within radius distance of each other. This is how my current release of Air Legends works, and if you watch closely it’ll be fairly evident. Depending on the orientation of the two planes a collision will still occur when clearly the planes were not even close.

A better alternative…

XNA provides two classes specifically for collision detection. BoundingSphere & BoundingBox. Both are non-visual, and contain an Intersects() method that will tell you if your BoundingBox/Sphere collides with another.

e.g.

if (bulletBoundingBox.Intersects(planeBoundingBox))
{
//plane's been hit. Cue imminent death...
}

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.

There in lies a problem with using BoundingBox. BoundingBox is apparently an Axis Aligned Bounding Box (AABB). Not something I’d heard of until recently. I’m a bit sketchy on exactly what this means, but this is my take on it.

Imagine my plane model with an invisible box around it. This is our BoundingBox used for collision detection with other planes/bullets etc…

Plane in BoundingBox
A BoundingBox’s shape and position is simply defined by a Min & Max. These a Vector3 types, so we have an X, Y & Z value for the Min corner, and an X, Y & Z value for Max corner. Min & Max represent two diagonally opposite corners of a cube.Fine so far, right?

So what happens if our model is rotated? We want to rotate our invisible BoundingBox’s Min & Max corners to reflect this.

XNA has methods to transform these Vector3’s with rotation’s, so that’s achievable. We’d imagine our rotated BoundingBox to be something like this right?

Plane in BoundingBox
WRONG!Sure we can imagine it like that. We can even write code to render such a rotated Box for Debug purposes. However that is not how the BoundingBox’s Intersects() method sees this shape at all. It’s more like this…

Plane in BoundingBox
Our Min & Max points are rotated just the same, but since the BoundingBox is Axis Aligned all that really happens is the box has been squished like the picture.This is one reason why I chose to go with BoundingSpheres instead of BoundingBoxes. Rotation is not really an issue with a sphere. It’s still a sphere no matter how you turn it!

Now you’re probably thinking, “How’s a sphere any different to the Radius technique mentioned above?”. And you’d be right. A single sphere around our model would be no improvement. However, you could break it up into multiple smaller BoundingSphere’s to represent different parts of the Model’s shape, and then we’d really be cooking!

It’s late, so I’ll stop there and continue in Part 2 soonish.

Ok, I couldn’t resist it. Here’s a sneak peak…

Plane in BoundingBox

Average Rating: 5 out of 5 based on 220 user reviews.

17 Responses to “”

  1. Ultrahead Says:

    Cannot wait for part 2. And of course a new release … don’t forget the radar … :)

  2. Garrett Hoofman Says:

    That’s exactly how I did it when I was playing with my 3D characters. One for the lower legs, one for the upper legs, one for the body, and one for the head. It worked great.

  3. abi Says:

    Nice screens and a good solution for the 2 planes in the last picture.
    But wouldn’t it be nicer to have real polygon-based collision testing like in MDX without having to hand-create these spheres yourself? Worked great in Rocket Commander and was just a few lines of code. Its really a pity that XNA does not allow access to the model vertices, I guess polygon based collision testing is only possible through own model formats and lots of own code to handle any intersections.

  4. Sharky Says:

    Yeah, that’d be nice.

    I hope future XNA releases can provide some sort of good-enough mesh collision detection out of the box.

    For now I’m just trying to eek out what I can from the existing BoundingSpheres you get automatically in the ContentPipeline loaded Model. More on how I do that in Part 2!

  5. Steve (Jinkster LA) Says:

    This article sheds some light on why my collision detections sucks the big one. I thought of it the same way as the author.

    Anyway, I’m new to game programming, but wouldn’t it make sense to tie collision detection more closely to 3d objects or sprites? I mean, using totally different objects to do collision detections seems a bit primitive and counter productive…especially when you can’t physically seem them!

    Maybe they are doing that way for performance reasons, but in that case there should be different objects.

    For instance,

    3d object 1- with no bounding box …so no collision detection possible

    3d object 2 – includes a bounding box…which is UPDATED automatically with scaling and rotation. Collision detection possible with a built in “intersects” method.

    It just makes more sense to me to do it this way…they could even make the boudingbox’s size adjustable….

  6. Sharky Says:

    Yep, I agree. I imagine performance is always going to be big consideration. Also Microsoft are probably leaving the Framework pure & bloat-free so as to be flexible & performant. That is wise IMHO, but it would be nice if there were optional bits like you say.

  7. Gogs Says:

    I started my first gamelast night. Luckily i started converting a game i wrote in blitz basic that mostly had spheres. I was in hysteric at some of the stuff i was coming up with where the balls would transfer energy into each other and change their rotation. although my balls started sticking to eachother more than i liked hopefully i can eventually get some deflection going today without one ball taking priority over the others.

  8. Sharky Says:

    nice

  9. RJ Says:

    I was going to use a model for a level but this means its impossible to implement the collision detection because I can’t get at the verticies. How are you supposed to make a first person shooter in XNA? I guess you can’t. The model which i use as a level is too detailed for me to attempt to add hundreds of boxes and spheres and to try and manage them myself would be a waste of effort.

    I know having a model for a level is probably not the pro the way to do it but for a really simple game it would have worked fine because the 360 is quite powerfull. I was amazed at how well it was running actually the framerate is great even with an enormous model as a level. Now I will have to try and build some kind of home brew level editor?

    Perhaps I should stick to a 2d game until they finish xna. Or am I missing something big? I’m very disapointed.

  10. Sharky Says:

    I’m guessing Microsoft are brewing up some goodies for the next release. Here’s hoping there’ll be more support for more serious collision detection. :p

    I can appreciate how the technique used in this article would certainly be less effective in FPS style games. The player tends to be a lot more aware of whether a shot should have hit or missed. Sphere’s are a bit two approximate for that – unless your character IS a sphere. (mental note to oneself: game idea #76. “Pacman 2007″)

    ;)

  11. Cogs Says:

    What 3d model editor are you guys using?
    Are you outputting a collision from the 3d editor ?

  12. Sharky Says:

    No, I’m not outputting any collision from the 3d editor. Do you mean like some kind of low poly collision mesh?

    As far as editors go, I built most of my model with Milkshape, but was having problems with that and export formats until I tried 3DStudio Max. That’s what my model was exported with in the end, but I’ve done no more work with 3DStudio Max since. I want to find a tool I can actually afford.

    I really want to use the Softimage|XSI Mod Tool. It’s free, powerful and relatively intuitive. Just having some problems with its .x export at the moment.

    See this thread…
    https://creators.xna.com/forums/thread/1211.aspx

  13. Shtivo Says:

    Is this Sharky an architect tutor from Oxford Brookes??????????

  14. Dave Says:

    Great.
    This work fine, I’m never using bounding boxes again, until I absolutly need them. Using bounding spheres is far quicker and if used correctly, accurate for collisions between round objects and straight objects.
    Keep up the good work!

  15. Sharky Says:

    Thanks Dave. :)

  16. Cupido Says:

    Hi, Great tutorial here for boundingsphere. Do u have a simple way to create a boundingbox for a model? Any example codes for it? Please help me as I already spent 1 full week on this topic. Thanks. :)

  17. Sharky Says:

    Hi, and thanks.

    I’m not sure, but I did notice the creators.xna.com site now has a sample on collision that includes an OrientedBoundingBox (i.e. not axis-aligned like the standed BoundingBox).

    Take a look at it here. It’s for XNA 4.0, but if it’s XNA 3.1 your after, perhaps the BoundingOrientedBox.cs class could be ported over easily?

    Otherwise google for terms like non-axis alligned bounding box, oriented bounding box etc…

Leave a Reply