Sign in to follow this  
lexington

SAT problems (3D)

Recommended Posts

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 :)

Edited by lexington

Share this post


Link to post
Share on other sites

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)?

Edited by Irlan Robson

Share this post


Link to post
Share on other sites

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

y axis row one
z axis row one

Share this post


Link to post
Share on other sites

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:

Edited by Irlan Robson

Share this post


Link to post
Share on other sites

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);
    .....
}
Edited by Dan Danger

Share this post


Link to post
Share on other sites

 

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 ] );
}

Share this post


Link to post
Share on other sites

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 :)

Edited by lexington

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this