Hey guys,

Iv been trying to get some SAT collision working but I cant seem to get it working.

I have been following this guys (http://www.jkh.me/files/tutorials/Separating%20Axis%20Theorem%20for%20Oriented%20Bounding%20Boxes.pdf) to try and convert the maths to code. ATM I'm just trying to get the code working with the long drawn out version (as you will see) as I have a much better understanding of doing it that way and I just want it working for now.

The code I have is as follows

 bool OBB::collisontest(OBB *B)
  {
	  glm::mat3 Brotation = B->returnrotation();
	  glm::vec3 Bhalf = B->returnlenghts();
	  glm::vec3 Bcenter = B->returncenter();

	  glm::vec3 T = Bcenter - centerpos;

	  float Aside;
	  float bside;
	  float projection;

	  for (int i = 0; i < 3; i++)
	  {
		  projection = glm::dot(T, rotation[i]);
		  
		  Aside = glm::dot(halfwaylenghts[0] * rotation[0], rotation[i]) + glm::dot(halfwaylenghts[1] * rotation[1], rotation[i]) + glm::dot(halfwaylenghts[2] * rotation[2], rotation[i]);
		  bside = glm::dot(Bhalf[0] * Brotation[0], rotation[i]) + glm::dot(Bhalf[1] * Brotation[1], rotation[i]) + glm::dot(Bhalf[2] * Brotation[2], rotation[i]);

		  if (projection > Aside + bside)
		  {
			  return false;
		  }

	  }

	  for (int i = 0; i < 3; i++)
	  {
		  projection = glm::dot(T, Brotation[i]);

		  Aside = glm::dot(halfwaylenghts[0] * rotation[0], rotation[i]) + glm::dot(halfwaylenghts[1] * rotation[1], rotation[i]) + glm::dot(halfwaylenghts[2] * rotation[2], rotation[i]);
		  bside = glm::dot(Bhalf[0] * Brotation[0], rotation[i]) + glm::dot(Bhalf[1] * Brotation[1], rotation[i]) + glm::dot(Bhalf[2] * Brotation[2], rotation[i]);

		  if (projection > Aside + bside)
		  {
			  return false;
		  }

	  }

	  glm::vec3 crossaxis = glm::cross(rotation[0], Brotation[0]);

	  projection = glm::dot(T, glm::cross(rotation[0],Brotation[0]));

	  Aside = glm::dot(halfwaylenghts[0] * rotation[0], crossaxis) + glm::dot(halfwaylenghts[1] * rotation[1], crossaxis) + glm::dot(halfwaylenghts[2] * rotation[2], crossaxis);
	  bside = glm::dot(Bhalf[0] * Brotation[0], crossaxis) + glm::dot(Bhalf[1] * Brotation[1], crossaxis) + glm::dot(Bhalf[2] * Brotation[2], crossaxis);

	  if (projection > Aside + bside)
	  {
		  return false;
	  }

	  crossaxis = glm::cross(rotation[0], Brotation[1]);

	  projection = glm::dot(T, glm::cross(rotation[0], Brotation[1]));

	  Aside = glm::dot(halfwaylenghts[0] * rotation[0], crossaxis) + glm::dot(halfwaylenghts[1] * rotation[1], crossaxis) + glm::dot(halfwaylenghts[2] * rotation[2], crossaxis);
	  bside = glm::dot(Bhalf[0] * Brotation[0], crossaxis) + glm::dot(Bhalf[1] * Brotation[1], crossaxis) + glm::dot(Bhalf[2] * Brotation[2], crossaxis);

	  if (projection > Aside + bside)
	  {
		  return false;
	  }

	  crossaxis = glm::cross(rotation[0], Brotation[2]);

	  projection = glm::dot(T, glm::cross(rotation[0], Brotation[2]));

	  Aside = glm::dot(halfwaylenghts[0] * rotation[0], crossaxis) + glm::dot(halfwaylenghts[1] * rotation[1], crossaxis) + glm::dot(halfwaylenghts[2] * rotation[2], crossaxis);
	  bside = glm::dot(Bhalf[0] * Brotation[0], crossaxis) + glm::dot(Bhalf[1] * Brotation[1], crossaxis) + glm::dot(Bhalf[2] * Brotation[2], crossaxis);

	  if (projection > Aside + bside)
	  {
		  return false;
	  }

	  crossaxis = glm::cross(rotation[1], Brotation[0]);

	  projection = glm::dot(T, glm::cross(rotation[1], Brotation[0]));

	  Aside = glm::dot(halfwaylenghts[0] * rotation[0], crossaxis) + glm::dot(halfwaylenghts[1] * rotation[1], crossaxis) + glm::dot(halfwaylenghts[2] * rotation[2], crossaxis);
	  bside = glm::dot(Bhalf[0] * Brotation[0], crossaxis) + glm::dot(Bhalf[1] * Brotation[1], crossaxis) + glm::dot(Bhalf[2] * Brotation[2], crossaxis);

	  if (projection > Aside + bside)
	  {
		  return false;
	  }

	  crossaxis = glm::cross(rotation[1], Brotation[1]);

	  projection = glm::dot(T, glm::cross(rotation[1], Brotation[1]));

	  Aside = glm::dot(halfwaylenghts[0] * rotation[0], crossaxis) + glm::dot(halfwaylenghts[1] * rotation[1], crossaxis) + glm::dot(halfwaylenghts[2] * rotation[2], crossaxis);
	  bside = glm::dot(Bhalf[0] * Brotation[0], crossaxis) + glm::dot(Bhalf[1] * Brotation[1], crossaxis) + glm::dot(Bhalf[2] * Brotation[2], crossaxis);

	  if (projection > Aside + bside)
	  {
		  return false;
	  }


	  crossaxis = glm::cross(rotation[1], Brotation[2]);

	  projection = glm::dot(T, glm::cross(rotation[1], Brotation[2]));

	  Aside = glm::dot(halfwaylenghts[0] * rotation[0], crossaxis) + glm::dot(halfwaylenghts[1] * rotation[1], crossaxis) + glm::dot(halfwaylenghts[2] * rotation[2], crossaxis);
	  bside = glm::dot(Bhalf[0] * Brotation[0], crossaxis) + glm::dot(Bhalf[1] * Brotation[1], crossaxis) + glm::dot(Bhalf[2] * Brotation[2], crossaxis);

	  if (projection > Aside + bside)
	  {
		  return false;
	  }

	  crossaxis = glm::cross(rotation[2], Brotation[0]);

	  projection = glm::dot(T, glm::cross(rotation[2], Brotation[0]));

	  Aside = glm::dot(halfwaylenghts[0] * rotation[0], crossaxis) + glm::dot(halfwaylenghts[1] * rotation[1], crossaxis) + glm::dot(halfwaylenghts[2] * rotation[2], crossaxis);
	  bside = glm::dot(Bhalf[0] * Brotation[0], crossaxis) + glm::dot(Bhalf[1] * Brotation[1], crossaxis) + glm::dot(Bhalf[2] * Brotation[2], crossaxis);

	  if (projection > Aside + bside)
	  {
		  return false;
	  }

		crossaxis = glm::cross(rotation[2], Brotation[1]);

	  projection = glm::dot(T, glm::cross(rotation[2], Brotation[1]));

	  Aside = glm::dot(halfwaylenghts[0] * rotation[0], crossaxis) + glm::dot(halfwaylenghts[1] * rotation[1], crossaxis) + glm::dot(halfwaylenghts[2] * rotation[2], crossaxis);
	  bside = glm::dot(Bhalf[0] * Brotation[0], crossaxis) + glm::dot(Bhalf[1] * Brotation[1], crossaxis) + glm::dot(Bhalf[2] * Brotation[2], crossaxis);

	  if (projection > Aside + bside)
	  {
		  return false;
	  }

	  crossaxis = glm::cross(rotation[2], Brotation[2]);

	  projection = glm::dot(T, glm::cross(rotation[2], Brotation[2]));

	  Aside = glm::dot(halfwaylenghts[0] * rotation[0], crossaxis) + glm::dot(halfwaylenghts[1] * rotation[1], crossaxis) + glm::dot(halfwaylenghts[2] * rotation[2], crossaxis);
	  bside = glm::dot(Bhalf[0] * Brotation[0], crossaxis) + glm::dot(Bhalf[1] * Brotation[1], crossaxis) + glm::dot(Bhalf[2] * Brotation[2], crossaxis);

	  if (projection > Aside + bside)
	  {
		  return false;
	  }

	  return true;

  } 

Does anything look incorrect, from what I understand of it (projecting the vector between the 2 on a plane of an axis (made by the x,y,z rotation vectors or the cross between object A and B) and then projecting the closes parts of both object on that plane added together to see if they are bigger then the difference projected) I cant see anything wrong myself. Just for additional info, it is a crossproduct axis test that causes the test to fail if 2 are clearly on top of each other.

Here is how i create my OBB just incase that might be wrong

void OBB::obbsetup(std::vector<glm::vec3> vetrices)
{
     glm::vec3 tempmin = glm::vec3(0.0f,0.0f,0.0f);
     glm::vec3 tempmax = glm::vec3(0.0f,0.0f,0.0f);


   for(int i = 0; i < vetrices.size(); i++)
   {
     if(vetrices[i].x < tempmin.x)
     {
       tempmin.x = vetrices[i].x;
     }
     if(vetrices[i].y < tempmin.y)
     {
       tempmin.y = vetrices[i].y;
     }
     if(vetrices[i].z < tempmin.z)
     {
       tempmin.z = vetrices[i].z;
     }
    if(vetrices[i].x > tempmax.x)
    {
       tempmax.x = vetrices[i].x;
     }
     if(vetrices[i].y > tempmax.y)
     {
       tempmax.y = vetrices[i].y;
     }
     if(vetrices[i].z > tempmax.z)
     {
       tempmax.z = vetrices[i].z;
     }
  }

   center.x = (tempmax.x - fabs(tempmin.x)) / 2;
   center.y = (tempmax.y - fabs(tempmin.y)) / 2;
   center.z = (tempmax.z - fabs(tempmin.z)) / 2;

   halfwaylenghts.x = tempmax.x - center.x;
   halfwaylenghts.y = tempmax.y - center.y;
   halfwaylenghts.z = tempmax.z - center.z;

}

and for updating

void OBB::update(glm::vec3 pos,glm::quat newqu)
{
    centerpos = pos + center;
    myquad = newqu;
    rotation = glm::toMat3(myquad);
 
}

(am using the GLM library)

Thanks for the time :)

For paralell segments the cross product result is zero in which you should skip the test if you want the collision normal. You do this only for edge-edge tests. I see that you're crossing two face normals. Ideally you'd have to test the faces of the first box against the faces of the second box and all possible non-parallel edge combinations (e.g. an edge of the first box with an another box's edge).

What is not working for your according to your visualization (e.g. what your collision configuration is showing)?

1. ill have to retract the statement that its only the cross axes tests that are failing as sadly they all are.

@Irlan Robson So from what I understand I am doing the first part with the face normals in the 2 for loops and the after that i thought that i was doing all of the edges by doing the cross between the faces. Is this not the correct way?

In terms of what is not working, i am intellectually moving one object into another but no collision is being reported back, if you want something more specific just ask as dont know how best to say.

the axes are based of the matrix which is row major

e.g

x axis row one

I've found this that may solve your problem: http://www.gamedev.net/topic/676408-differentiating-between-an-edge-edge-and-something-face-collision/#entry5278632

Take a look at our comments. Randy posted an excelent article for the 3D case along with an implementation which I highly recommend if you want an OBB-OBB colision test that can be used in production.

The matrix majorness is irrelevant as long your basis vectors are unit and describe the faces of a box. :wink:

The obbsetup code should initialise the min values to +infinity and the max values to -infinity. Otherwise your obb will always include the position {0,0}

void OBB::obbsetup(std::vector<glm::vec3> vetrices)
{
    glm::vec3 tempmin = glm::vec3(+INFINITY,+INFINITY,+INFINITY);
    glm::vec3 tempmax = glm::vec3(-INFINITY,-INFINITY,-INFINITY);
    .....
}

The obbsetup code should initialise the min values to +infinity and the max values to -infinity. Otherwise your obb will always include the position {0,0}

void OBB::obbsetup(std::vector<glm::vec3> vetrices)
{
    glm::vec3 tempmin = glm::vec3(+INFINITY,+INFINITY,+INFINITY);
    glm::vec3 tempmax = glm::vec3(-INFINITY,-INFINITY,-INFINITY);
    .....
}

As a simplification this can be changed to:

min = vertices[ 0 ]
max = vertices[ 0 ]

for ( i = 1; i < N; ++i )
{
    min = Min( min, vertices[ i ] );
    max = Max( max, vertices[ i ] );
}

Hey guys

I have made the changes to my setup but lucky for me at the start it was not problem (still good to know for future :))

Irlan, I have had a little look at what you linked and Randy's blog post, i decided to read up more on SAT from http://www.dyn4j.org/2010/01/sat/ and change my code to more reflect this method but now i have a problem where my code always thinks there is a collision. At this moment in time Im only using the faces as axes (both objects rotation X,Y,Z vectors)

The new code is as follows

The code that decides if there is collison or no

bool OBB::collisontest2(OBB *B)
  {

	  glm::mat3 Brotation = B->returnrotation();

	  axes.clear();
	  axes.push_back(rotation[0]);
	  axes.push_back(rotation[1]);
	  axes.push_back(rotation[2]);
	  axes.push_back(Brotation[0]);
	  axes.push_back(Brotation[1]);
	  axes.push_back(Brotation[2]);


	  for (int i = 0; i < axes.size(); i++)
	  {
		  projection myproject = projectonaxes(axes[i]);
		  projection bproject = B->projectonaxes(axes[i]);

		  if (!overlap(myproject, bproject))
		  {
			  return false;
		  }

	  }

	  return true;
  }

 projection OBB::projectonaxes(glm::vec3 axes)
  {
	  projection newproject;

	  double min = INFINITY;
	  double max = -INFINITY;

	  for (int i = 0; i < vertexes.size(); i++)
	  {
		  double temp = glm::dot(axes, vertexes[i]);
		  double temp2 = glm::dot(axes, vertexes[i]);
		  if (temp < min)
		  {
			  min = temp;
		  }
		  else if (temp > max)
		  {
			  max = temp;
		  }

	  }

	  newproject.max = max;
	  newproject.min = min;

	  return newproject;
  }

Is there anything with my understanding or code. I feel like since i am projecting the 8 vertexes onto these "plans" that it should detect a collision, Or is 3d very different to the 2d Implementation. I will continue to read the post you linked but some clarity here would be very helpful :)

Just for reference these are the vertices that are used (and where it says it is colliding)

Nevermind it seems that my vertex position was not being updated with the actually position of the obb/object.

Seems that that my code is working now :).