When OBB’s Collide!

Posted by Mike
June 21, 2008

Quick, somebody cover When Worlds Collide for me (by Powerman 5000 for those that just plain aren’t cool). As mentioned in the previous post today we’re going to be discussing OBB’s (Orientated Bounding Boxes) and how to tell if two of them collide or not. Luckily for us I was able to come across a great OBB class for XNA/C# on the Internet from ZiggyWare located here. All props on saving me so much time and loss of sleep go to them on this one.

In addition I’ve done a lot of code cleanup and started commenting everything (commenting more as I speak) so it should help now that our code base is getting larger.

avoidobb

As you may or may not be able to tell in the picture above, we are working with Redridge Mountains from here out because it really has everything in a single map tile. Cliffs, trees, fences, buildings, a bridge, water, etc… The white spots represent points that we can stand on right now. That is to say we know for sure if our character is on any one of those points (s)he will not be colliding with a M2 or a WMO. We do not know if we can walk from one of those points to another (that’s a test for another day and possibly later today). In addition the missing points are obviously not 100% accurate because we are just going by the bounding boxes.

What good is this data? Well it gives us all the points that we know we can start from and it will save us a lot of processing. As you can see the vast majority of the time you can move between any two points that are next to each other (the white points) so a simple OBB around both points test with all the other OBBs in the scene will give us a good portion of the nav mesh very quickly.

Now the first step in this process is our OBB class. Because I didn’t write it and I only slightly understand it I am going to give it to you all at once. Put this in a file called OBB.cs in the Collision folder:

[+]Download obb.cs

Even though I may not be able to explain exaclty how it work, I can give the basics. The entire idea behind the collision is what is called the Seperating-Axis Theorem. To understand it we are going to go low-tech in 2D instead of 3D as it make things a lot easier. The general idea is if you have two convex polygons and you can find a plane that separates them, they are not intersecting.

Now what is a convex polygon?

In Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object. For example, a solid cube is convex, but anything that is hollow or has a dent in it, for example, a crescent shape, is not convex.

So basically if we can find two points in a polygon, draw a line between them, and that line goes outside the edges of our polygon it is not convex!

convex

Why must they be convex? Well first let’s look at how it all works when they are convex (boxes in this instance because that’s what we’re using):

This image shows that we can draw a plane (axis) between these two objects which happen to be convex polygons:

seperating

They are not intersecting, and we know that because we can draw the plane (line in this instance but you get the point) between them. Now what would happen if they were funny non-convex polygons?

not-convex

As you see we cannot draw a line between them, but they still aren’t actually intersecting! This is why our polygons we are using in this theorem MUST be convex!

Does the make sense? I sure hope so because that’s about as much as I understand. How to generate and test each axis needed is beyond me (but at least it’s in the code above).

Now our OBB class is a bit different then our AABB class because it is made with:

howtomakeanobb

Looking at the above picture we can assume we are facing straight down on the box. It has been rotated 30 degrees clockwise around the Y axis (technically around the Y axis of it’s center point but that doesn’t much matter).

Now to the constructor we would pass the Vector3 that represents the center point of this box, a rotation matrix that says to rotate it 30 degrees around the Y axis, as well as the extents. As you can see the extents are just the length from the center point to the outside of our box. The extents are also passed as a Vector3.

Why a vector3? A V3 is simply a group of 3 floats, which is what we want for our extents. A float for the X extent distance, for the Y extent distance, and for the Z extent distance. It just makes life easier.

Ok, so I hope we now understand how our OBB class works and how to create an OBB!

Now if you think back to how we actually draw our boxes for our OBBs in our scene, we first get the AABB for our object, and then rotate it with the object. This actually works out about perfect for us because when we generate our AABB it’s dead simple to find the extents of that box and we already have a rotation matrix that we use to rotate our AABB to our OBB.

So in our AABB.cs file we are going to add two simple new variables:

[-]View Code CSHARP
public Vector3 center;
public Vector3 extents;

Nothing too hard there right? Right!

Now in our method called: buildFromVertList we are going to generate the center and the extents. Directly after:

[-]View Code CSHARP
this.indexList.AddRange(tempIndexArray);

Add this block of code:

[-]View Code CSHARP
this.center = (v8 - v1) * 0.5f;
this.center += v1;
this.extents = (v8 - v1) * .5f;

Remember that v8 contains our largest vector and v1 is our smallest. So let’s assume v1 is at (0,0,0) and v8 is at (10,10,10).

Subtracting a vector from a vector just takes each element (the X, Y, and Z) and subtracts the elements in the other vector from it. Therefor v8 - v1 is a new vector that would be: (10 - 0, 10 - 0, 10 - 0) or (10,10,10). When we multiple that vector by a number it multiplies each element by that number. So we then get:

(10 * .5, 10 * .5, 10 * .5) or (5,5,5) as our vector.

Now in this instance we had 0,0,0 as our v1 so adding it gives us a final vector center point of (5,5,5); however, if say our v1 was at 10,10,10 and our v8 was at 20,20,20 we would do:

(20-10,20-10,20-10) = (10,10,10)

(10 * .5, 10 * .5, 10 * .5) = (5,5,5)

(5 + 10, 5 + 10, 5 + 10) = (15,15,15) which is where our center point is. Simple enough right?

Now for the extents we just don’t adjust our extents to our starting point (review the above math if you’re confused or ask me questions).

Now we are adjusting our AABB constructor that take a v1 and a v8 at a bit to use that method (just for simplicity’s sake). It should be like this from now on:

[-]View Code CSHARP
public AABB(Vector3 v1, Vector3 v8)
{
    Vector3 v2 = new Vector3(v8.X, v1.Y, v1.Z);
    Vector3 v3 = new Vector3(v1.X, v8.Y, v1.Z);
    Vector3 v4 = new Vector3(v8.X, v8.Y, v1.Z);
    Vector3 v5 = new Vector3(v1.X, v1.Y, v8.Z);
    Vector3 v6 = new Vector3(v8.X, v1.Y, v8.Z);
    Vector3 v7 = new Vector3(v1.X, v8.Y, v8.Z);
 
    List vList = new List();
    vList.Add(v1);
    vList.Add(v2);
    vList.Add(v3);
    vList.Add(v4);
    vList.Add(v5);
    vList.Add(v6);
    vList.Add(v7);
    vList.Add(v8);
 
    this.buildFromVertList(vList);
}

Here’s a download of our updated AABB.cs file:

[+]Download aabb.cs

So we now have the classes to hold and test the data we need, we just need to get the data from the M2s, and WMOs into a usable format!

The first thing we are going to do is create (if I haven’t had you create one already) a Collider.cs file in our Collision folder. This is where we are going to do a lot of our collision test work. It should start out something like this:

[-]View Code CSHARP
using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Audio;
using Microsoft.Xna.Framework.Content;
using Microsoft.Xna.Framework.GamerServices;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;
using Microsoft.Xna.Framework.Net;
using Microsoft.Xna.Framework.Storage;
 
namespace MPQNav.Collision
{
    class Collider
    {
 
    }
}

Now we are going to be calling our collider from our ADTManager for now, so we are going to want a variable that holds a reference to the calling ADTManager:

[-]View Code CSHARP
public ADT.ADTManager manager;

Simple enough right? We are also going to want a list of all the OBB’s for the M2s and WMOs as well as a single OBB that we will use to represent our character.

[-]View Code CSHARP
public List m2BBList = new List();
public List wmoBBLIST = new List();
public OBB characterOBB = new OBB(new Vector3(0, 0.8f 0), new Vector3(.3f, .8f, .3f), Matrix.Identity);

Our character OBB is set to a default position of (0,.8,0) for it’s center (remember a tauren is about .6 wide, .6 long, and 1.6 tall) and it’s extents are given as half of it’s size (that I just mentioned). In addition it doesn’t have any rotation (the Matrix.Identity is a 0 scale 0 rotation type of matrix).

Now we have one simple constructor for now:

[-]View Code CSHARP
public Collider(ADT.ADTManager m)
{
    manager = m;
}

And finally we are going to have a method to find all the standable points on an ADT. It should start something like this:

[-]View Code CSHARP
public List getWalkablePoints(List vList)
{
 
}

As you can see it takes a list of our new Vertex element and then returns a list of standable vectors. It’s called getWalkablePoints because later it will be expanded to more then just where we can stand.

First thing we want to do is create an empty list of Vector3’s that we will return after we’re all done:

[-]View Code CSHARP
List returnList = new List();

Once we have that out of the way it’s time to go through all of the vertices given in the vList variable.

[-]View Code CSHARP
for (int i = 0; i < vList.Count; i++)
{
 
}

The first thing we are going to do is check if our vertex is black. If it’s black we know it has a bad slope (we found that out earlier) so we will just ignore it all together as we can’t stand there without falling.

[-]View Code CSHARP
if (vList[i].Color != Color.Black)
{
 
}

We know if we’re within that If check that we’re OK to stand on that point so the next thing to do is check if we collide with anything. The first thing we need to do is adjust where our character’s bounding box is at:

[-]View Code CSHARP
characterOBB.Center = vList[i].Position + new Vector3(0,.8f,0);

This simply places it wherever our current vertex is, and then adds .8 to the height to make sure our box is above the point.

Next we are going to check for any intersections with our M2’s bounding boxes:

[-]View Code CSHARP
Boolean intersects = false;
int j = 0;
while (intersects == false && j < m2BBList.Count)
{
    if (m2BBList[j].Intersects(characterOBB))
    {
        intersects = true;
    }
    j++;
}

Basically we create a boolean first that tells us if we have an intersection or not, and we set it to false (assuming no intersection). We also create an integer to keep track of what M2 we’re on.

We then loop through the M2’s until we either find an intersection or hit the end of our list of OBB’s for our M2s.

Each time through we check if the M2 we’re working with intersections with the character’s OBB and if so we set the intersects boolean to true. We then increment our counter.

After all of that we do the same process for WMOs:

[-]View Code CSHARP
j = 0;
while (intersects == false && j < wmoBBLIST.Count)
{
    if (wmoBBLIST[j].Intersects(characterOBB))
    {
        intersects = true;
    }
    j++;
}

As I hope you noticed with our while loops, as soon as we find an intersection we don’t go any further in either of the loops to save on processing.

After both while loops it’s a simple matter of seeing if we have an intersection, and if we don’t, adding it to the list:

[-]View Code CSHARP
if (intersects == false)
{
    returnList.Add(vList[i].Position);
}

Finally outside of our first For loop but before the end of our method, we return our list:

[-]View Code CSHARP
return returnList;

That’s it for the collider class! (for now at least). Download:

[+]Download collider.cs

The final bit of work and data really goes in our ADTManager.cs file. Now I apologize that I wanted to have all this code much cleaner then it is now (and I have some reworking of how it’s laid out to do) but it was a choice of posting all this for you ASAP or cleaning up my code ASAP and posting when I could. I think I made the right choice.

We are going to add a new variable to our ADTManager:

[-]View Code CSHARP
public Collision.Collider my_collider;

And in our default constructor we are going to assign it:

[-]View Code CSHARP
public ADTManager()
{
    my_collider = new MPQNav.Collision.Collider(this);
}

We are going to add the same line to the constructor that takes a String filePath right above checking if the file exists:

[-]View Code CSHARP
my_collider = new MPQNav.Collision.Collider(this);

That should about take care of all of that.

Now lower on in processM2s there should be a line of code something like this:

[-]View Code CSHARP
m2Reader.BaseStream.Position = ofsBoundingTriangles;
for (int v = 0; v < nBoundingTriangles; v++)
{
    currentM2.colIndexList.Add((int)m2Reader.ReadInt16());
}

If you remember right this is getting our collidable vertices for our M2s.

Below it add (or modify if the creation of the AABB is already there) this:

[-]View Code CSHARP
// Bounding Box Before Rotation
MPQNav.Collision.AABB myAABB = new MPQNav.Collision.AABB(currentM2.colVertexList);
Vector3 extents = myAABB.extents;
Vector3 center = transformVector(myAABB.center, currentADT.MDDFList[i].position.X, currentADT.MDDFList[i].position.Y, currentADT.MDDFList[i].position.Z, currentADT.MDDFList[i].orientation_a, currentADT.MDDFList[i].orientation_b, currentADT.MDDFList[i].orientation_c, currentADT.MDDFList[i].scale);

What is this doing? Well it’s create an AABB from our collidable vertices for our M2, and then we are creating a local vector for the center and the extents of that AABB. Now the extents is pretty basic (for now) but the center looks a little tricky. You have to remember that the collidable vertices haven’t been moved and scaled yet, so all we are doing is moving and scaling our center according to how our M2 is moved and scaled. Why don’t we create a box after the movement and scaling? Because our movement and scaling method also rotates our vertices, so we no longer have our true AABB.

Now the next group of code should look something like this already:

[-]View Code CSHARP
for (int v = 0; v < myAABB.vertList.Count; v++)
{
    Vector3 transformedVector = transformVector(myAABB.vertList[v], currentADT.MDDFList[i].position.X, currentADT.MDDFList[i].position.Y, currentADT.MDDFList[i].position.Z, currentADT.MDDFList[i].orientation_a, currentADT.MDDFList[i].orientation_b, currentADT.MDDFList[i].orientation_c, currentADT.MDDFList[i].scale);
    currentM2.bbVertexList.Add(new VertexPositionNormalColored(transformedVector, Color.White, Vector3.Up));
}
currentM2.bbIndexList = myAABB.indexList;
 
for (int v = 0; v < currentM2.colVertexList.Count; v++)
{
    Vector3 transformedVector = transformVector(currentM2.colVertexList[v].Position, currentADT.MDDFList[i].position.X, currentADT.MDDFList[i].position.Y, currentADT.MDDFList[i].position.Z, currentADT.MDDFList[i].orientation_a, currentADT.MDDFList[i].orientation_b, currentADT.MDDFList[i].orientation_c, currentADT.MDDFList[i].scale);
    currentM2.colVertexList[v] = new VertexPositionNormalColored(transformedVector, Color.Pink, Vector3.Up);
}

That’s just setting up the list of bounding vertices and collidable vertices from before.

[-]View Code CSHARP
if (currentM2.colVertexList.Count { 0)
{
    extents = extents * new Vector3(currentADT.MDDFList[i].scale, currentADT.MDDFList[i].scale, currentADT.MDDFList[i].scale);
    my_collider.m2BBList.Add(new MPQNav.Collision.OBB(center, extents, Matrix.CreateRotationY((currentADT.MDDFList[i].orientation_b - 90) * 0.0174532925f)));
}

This is the final bit of code adjusts for the movement and scaling. The first thing we do is scale our extents by how much our M2 is scaled. After that we add a new OBB to our collider for our M2 with the center point we got before, our new scaled extents, and a rotation matrix that rotates around the Y axis like before (I still haven’t done X and Z rotation but it’s on my long list).

That’s it for our M2s ( won’t go over our WMOs as they are nearly the same except without the scaling, look at the code if you’re curious about it).

*note* Not covered here in this post is a few things relating to adding the center points to the WMO and M2 OBB’s and rendering them, it’s in the code if you’re curious and it’s very simple. I just added a list to the WMO and M2 class to hold some fectors, and then when we find the center for the OBB I added it to that list. Later on it’s rendered *note*

Now in our Game1.cs we need to render the points. At the end of ParseADT() add:

[-]View Code CSHARP
List vList = new List();
for (int i = 0; i < this.ADTVerticies.Length; i++)
{
    vList.Add(new VertexPositionNormalColored(ADTVerticies[i].Position, ADTVerticies[i].Color, Vector3.Up));
}
List walkablePoints = manager.my_collider.getWalkablePoints(vList);
this.pointList = new VertexPositionNormalColored[walkablePoints.Count];
for (int i = 0; i < walkablePoints.Count; i++)
{
    this.pointList[i] = new VertexPositionNormalColored(walkablePoints[i], Color.White, Vector3.Up);
}

This basically takes our ADT vertices and converts them from an array to a list. There’s probably a better way to do this but it works. We then get the walkable points, add it to a pointlist variable that may or may not be declared in your Game1.cs file, and call it a day.

Now in our DrawADT() method we add a bit of code that renders a pointlist (much like a traingle list, but it’s just a group of points to be rendered):

[-]View Code CSHARP
            graphics.GraphicsDevice.RenderState.PointSize = 5;
            graphics.GraphicsDevice.DrawUserPrimitives(
                PrimitiveType.PointList,
                this.pointList,
                0,  // index of the first vertex to draw
                this.pointList.Length   // number of primitives
            );

I’m sure I left something out, so please download the entire code here: MPQNav 0.0.7

As always thanks for reading and hit me up with any questions!

General, collision, theory

If you enjoyed this post, please consider to leave a comment or subscribe to the feed and get future articles delivered to your feed reader.

Comments
Comment by Ziggyware XNA News and Tutorials on June 23, 2008 @ 11:05 am

There are several typo’s in your obb.cs file that you have listed. Be sure to check that your code compiles before sending it out to the community :)

Comment by admin on June 23, 2008 @ 5:45 pm

I’ll give it another look over, for some reason Windows Live Writer was being a bit of a pain with this post and converting some characters within my pre tags to their HTML equivalents (such as >, &, etc…).

Comment by haavis on June 25, 2008 @ 6:13 am

I’ve been reading through your stuff here now, and this is freakingly similar to the things I’ve been doing in my spare time over quite some time ;)

Great stuff, and I’ll be keeping a close eye to your posts. They are informative and entertaining! Love it!

Keep it up!

.h

Leave a comment

(required)

(required)