Jump to content
  • Advertisement
Sign in to follow this  
xennon

Separating Axis Test in C++

This topic is 4950 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey :-) Basically, i'm at the end of my tether while trying to get this thing to work. I've tried everything I can think of, and I just can't get it to work. I understand what the test does, and how it works, but when coding it, it just won't do what I want. I can get it to test correctly if two boxes are axis aligned, but as soon as they are oriented, it won't work. I will follow with my code This is where the OBB is updated. Its extent and edge vectors are set.
void drawBox()
     {          
          glPushMatrix();     

          glColor3f(1.0,1.0,1.0);
          
          center.x = center.x + dMove*cos(PI/2+turn1*PI/180.0);
          center.y = center.y + dMove*sin(PI/2+turn1*PI/180.0);     
     
          glTranslatef(center.x, center.y, center.z);
          glRotatef(turn1,0.0,0.0,1.0);
          glRotatef(turn2,0.0,1.0,0.0);
          
          //Rotation Vector
          Vec3d temp;
          temp.Set(0, turn2, turn1);

          //Sets extremity vector and edge vectors
          extrem.Set(center.x+width/2, center.y+height/2, center.z+depth/2);
          edgeX.Set(center.x+width/2, center.y, center.z);
          edgeY.Set(center.x, center.y+height/2, center.z);
          edgeZ.Set(center.x, center.y, center.z+depth/2);

          //Rotates those vectors with the box
          extrem.Rotate(center.xyz,temp); 
          edgeX.Rotate(center.xyz,temp);
          edgeY.Rotate(center.xyz,temp);
          edgeZ.Rotate(center.xyz,temp);
          glScalef(width, height, depth);
          glutWireCube(1);
     
          glPopMatrix();     
     }

This is where the test is performed. Anything with 'this' is the local box (BOX A) and anything with 'box' is the passed in box (BOX B).
bool checkCollision(OBB *box)
     {
          Vec3d     CA;  
          Vec3d     CB;  
          Vec3d     L;
          Vec3d centerB, Labs;
          
          //Extent Vectors of Boxes relative to their local axis
          CA.Set(this->extrem-this->center);
          CB.Set(box->extrem-box->center);
          
          centerB.Set(box->center-this->center);

          for (int i = 0; i < 3; ++i)
          {
               //The 3 edge vectors of the box A (anything with 'this' is box A)
               if(i == 0)
               {
                    L.Set(this->edgeX-this->center);
               }
               else if( i == 1)
               {
                    L.Set(this->edgeY-this->center);
               }
               else if(i == 2)
               {
                    L.Set(this->edgeZ-this->center);
               }     
               
               L.Normalize();

               //|L|
               Labs.Set(fabs(L.x), fabs(L.y), fabs(L.z));

               float min1 = L.Dot(this->center-this->center) - Labs.Dot(CA);
               float max1 = L.Dot(this->center-this->center) + Labs.Dot(CA);
               float min2 = L.Dot(centerB) - Labs.Dot(CB);
               float max2 = L.Dot(centerB) + Labs.Dot(CB);

               float d0 = min1 - max2;
               float d1 = min2 - max1;    
          
               if(d0>0 || d1>0)
               {
                    return false;
               }
          
               //Edge vectors of box B (anything with 'box->' is box B)
               if(i == 0)
               {
                    L.Set((box->edgeX-box->center+centerB));
               }
               else if( i == 1)
               {
                    L.Set((box->edgeY-box->center+centerB));
               }
               else if(i == 2)
               {
                    L.Set((box->edgeZ-box->center+centerB));
               }          
          
               L.Normalize();
               Labs.Set(fabs(L.x), fabs(L.y), fabs(L.z));
               min1 = L.Dot(this->center-this->center) - Labs.Dot(CA);
               max1 = L.Dot(this->center-this->center) + Labs.Dot(CA);
               min2 = L.Dot(centerB) - Labs.Dot(CB);
               max2 = L.Dot(centerB) + Labs.Dot(CB);

               d0 = min1 - max2;
               d1 = min2 - max1;    

               if(d0>0 || d1>0)
               {
                    return false;
               }          
          }
     
          // and now for the cross product axes
          for (int i = 0; i < 3; ++i)
          {
               if(i == 0)
               {
                    L.Set(this->edgeX-this->center);
               }
               else if( i == 1)
               {
                    L.Set(this->edgeY-this->center);
               }
               else if(i == 2)
               {
                    L.Set(this->edgeZ-this->center);
               }

               for (int j = 0; j < 3; ++j)
               {
                    Vec3d temp3;
                    if(j == 0)
                    {                    
                         temp3.Set((box->edgeX-box->center+centerB));
                         L.Set(L.Cross(temp3));
                    }
                    else if( j == 1)
                    {
                         temp3.Set((box->edgeY-box->center+centerB));
                         L.Set(L.Cross(temp3));
                    }
                    else if(j == 2)
                    {
                         temp3.Set((box->edgeZ-box->center+centerB));
                         L.Set(L.Cross(temp3));
                    }

                    L.Normalize();
                    Labs.Set(fabs(L.x), fabs(L.y), fabs(L.z));
                    float min1 = L.Dot(this->center-this->center) - Labs.Dot(CA);
                    float max1 = L.Dot(this->center-this->center) + Labs.Dot(CA);
                    float min2 = L.Dot(centerB) - Labs.Dot(CB);
                    float max2 = L.Dot(centerB) + Labs.Dot(CB);

                    float d0 = min1 - max2;
                    float d1 = min2 - max1;    

                    if(d0>0 || d1>0)
                    {
                         return false;
                    }                    
               }
          }     

          return true;
          }

I have checked every website I can find, and spent hours trying lots of different things to get this test to work. I have Van Den Bergens 'Collision detection in interactive 3d environments' which is where I got the theory from, and I think I understand it. I really just need help with this code and getting it to work. PLEASE, i'm seriously desperate :-) Sorry about the formatting of the code, but the forum doesn't seem to like it :-/ If you want to know anything which will help you help me then I will answer as best I can. I can also provide the files if this is too hard to read :-) [Edited by - xennon on April 27, 2005 6:09:38 AM]

Share this post


Link to post
Share on other sites
Advertisement
Hello,

I just took a look at your code, but had some difficulty sorting through it. Although I'm sure I could figure it out with enough time, a first step in fixing your problem might be to sort out some details here and there. So although I don't have a solution for you, I do have a few more or less random suggestions.

1. The source tags can be a little finicky sometimes. I've found that I have to replace all my tabs with spaces for it to format correctly on gamedev. I don't know if that was the problem you were having, but if you can somehow get it to format correctly it will be easier to go through.

2. The way you're doing things is a little unorthodox, which isn't necessarily bad, but you may be missing out on a) some efficiency, and b) the advantage of representing things the same way standard references do, so that it's easier to compare. Typically for an OBB you store a center, an orthonormal basis (i.e. three mutually perpendicular unit-length axes), and the extents (or 'half-widths') along those axes.

3. You may already know this, but you generally don't need to use 'this->' unless there's some sort of scope conflict, and the code would probably be more readable without it.

4. I used to make my intersection tests member functions also, but I found it sort of confusing to have one object be 'this' and the other be 'box', or whatever. I think it reads better if you make it a static or friend function and have two arguments such as box1 and box2. It reads more like the reference material and makes it easier to double-check. Just IMO.

5. Should you maybe be scaling by the half-extents rather than the full width, height, and depth?

6. There are other possible issues with what your Rotate() function is doing in relation to what OpenGL is doing, but I'd have to see more code to say anything about that.

Anyway, once you figure it out the algorithm is fairly straightforward. I think if your code were a little cleaner and more standardized, it would become easier (for me at least) to spot the error.

Share this post


Link to post
Share on other sites
Hi, thanks for your reply :-)

Quote:
Typically for an OBB you store a center, an orthonormal basis (i.e. three mutually perpendicular unit-length axes), and the extents (or 'half-widths') along those axes.


I'm not actually sure what you mean by this.... so maybe thats where i'm going wrong :-D By this do you mean an orthogonal 3x3 matrix? Cause i've read that somewhere. I thought it was just a method of representing the axis vectors, which I did as edgeX, edgeY and edgeZ. If i've misunderstood this, could you possibly explain to me exactly what it should be?


Quote:
5. Should you maybe be scaling by the half-extents rather than the full width, height, and depth?

6. There are other possible issues with what your Rotate() function is doing in relation to what OpenGL is doing, but I'd have to see more code to say anything about that.


As far as I know, this all works correctly. When running the program I draw points at all the important vector locations in the test, and they all seem to follow their rotations correctly, so I don't think there is a problem.

Here is a (poor :-D ) picture of what info the OBB's use for the testing.


[Edited by - xennon on April 27, 2005 6:41:12 AM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by xennon
Hey :-)

Basically, i'm at the end of my tether while trying to get this thing to work. I've tried everything I can think of, and I just can't get it to work. I understand what the test does, and how it works, but when coding it, it just won't do what I want. I can get it to test correctly if two boxes are axis aligned, but as soon as they are oriented, it won't work.

I will follow with my code

This is where the OBB is updated. Its extent and edge vectors are set.

*** Source Snippet Removed ***

This is where the test is performed. Anything with 'this' is the local box (BOX A) and anything with 'box' is the passed in box (BOX B).
*** Source Snippet Removed ***

I have checked every website I can find, and spent hours trying lots of different things to get this test to work. I have Van Den Bergens 'Collision detection in interactive 3d environments' which is where I got the theory from, and I think I understand it.

I really just need help with this code and getting it to work. PLEASE, i'm seriously desperate :-)

Sorry about the formatting of the code, but the forum doesn't seem to like it :-/ If you want to know anything which will help you help me then I will answer as best I can. I can also provide the files if this is too hard to read :-)





You might also do a bit of optomization.

float min1 = L.Dot(this->center-this->center) - Labs.Dot(CA);
float max1 = L.Dot(this->center-this->center) + Labs.Dot(CA);
float min2 = L.Dot(centerB) - Labs.Dot(CB);
float max2 = L.Dot(centerB) + Labs.Dot(CB);

You are repeating the DOT PRODUCT calls on the same data repeatedly in more than a few places.....



Share this post


Link to post
Share on other sites
Guest Anonymous Poster


Isnt the point of Axis Aligned Bounding Boxes the ability to do collision tests
with a minimal number of checks (no dotproducts or crossproducts etc...)

Just if-then logic to detect overlap of box extents of all 3 axis .......

Share this post


Link to post
Share on other sites
I'm not worried about optimisation at the moment. I need to get it working first :-)

This isn't for AABB's, its for OBB's. It works when the OBB's are axis aligned, but i want it to work when they are oriented.

Share this post


Link to post
Share on other sites
Hi,

As for the scaling issue, if you scale by the widths instead of the half-widths, everything will *look* correct, but what you see may actually be different than how your OBBs are being represented internally. So I still think it may be the half-widths, not the widths, that you want (although I'm not sure).
Quote:
I'm not actually sure what you mean by this.... so maybe thats where i'm going wrong :-D By this do you mean an orthogonal 3x3 matrix? Cause i've read that somewhere. I thought it was just a method of representing the axis vectors, which I did as edgeX, edgeY and edgeZ. If i've misunderstood this, could you possibly explain to me exactly what it should be?
Right, an orthogonal 3x3 matrix can represent an orthonormal basis - the three axes go in the rows or columns (depending on your convention) of the matrix.

So you could store the axes as a 3x3 matrix, or as three vectors - your choice. Currently, your 'edges' are basically non-unit-length axes whose lengths are equal to the half-widths. Regardless of other considerations, the name 'edge' is kind of confusing in this case, so I would rename them 'axes' or something similar. As for the length, for some purposes it's ok to have them extend to the sides of the box, but overall I think it's more useful for them to be normalized (unit-length). In any case, the way I see OBBs represented most often is something like:

Vector3 C; // Center of the box
Vector3 A[3]; // Unit-length axes
float e[3]; // Extents (half-widths) along each axis

Anyway, there's quite a lot to this subject, so feel free to ask if you have more questions.

Share this post


Link to post
Share on other sites
Ok, i'll try recoding it so its all 'standard' and see if that helps me out :-)

I'll be back if I still have problems :-D

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!