Jump to content
  • Advertisement
VanillaSnake21

Help with separating axis algorithm implementation

Recommended Posts

I'm having some difficulty with my SAT implementation. I'm basing it on Dynamic Collision Detect by David Eberly et al and I'm getting stuck on a part where I have to calculate the two radiuses. I'm listing here the equation that calculates the two radiuses as the paper has them (scroll down to the bottom of the post, the equations are linked as images) and some code that I wrote based on them. If any one could please at least point me in the right direction. 

My first question is what does the word "Sign" mean exactly in the equation? I've understood it to be a sign vector that is used to get all the 8 vertices, but I'm having doubts about it.

My second question is does he calculate the radiuses for each vertex or is that formula used just once? I've taken it to mean for each vertex, because otherwise it doesn't make sense to me. So basically what I'm doing in my code is finding the radius0 for every one of the 8 vertices of the first box, then out of those 8 radiuses I pick the one that has the largest value. The paper doesn't say to do that, but that's the only way I see that makes any sense to me. I do the same for the second box. 

Here is the function I've written based on the paper that should work in theory (but it doesn't)

 

bool CollisionBox::mCheckOverlapOnAxis(const XMVECTOR& boxCenter, const XMVECTOR& xAxis, const XMVECTOR& yAxis, const XMVECTOR& zAxis, XMFLOAT3 xyzExtents, const XMVECTOR& projectionAxis)

{

  //define a sign vector to get all the points
	int sign[8][3];
	sign[0][0] = 1;
	sign[0][1] = 1;
	sign[0][2] = 1;

	sign[1][0] = 1;
	sign[1][1] = 1;
	sign[1][2] = -1;

	sign[2][0] = -1;
	sign[2][1] = 1; 
	sign[2][2] = -1;

	sign[3][0] = -1;
	sign[3][1] = 1;
	sign[3][2] = 1;

	sign[4][0] = 1;
	sign[4][1] = -1;
	sign[4][2] = 1;

	sign[5][0] = 1;
	sign[5][1] = -1;
	sign[5][2] = -1;

	sign[6][0] = -1;
	sign[6][1] = -1;
	sign[6][2] = -1;

	sign[7][0] = -1;
	sign[7][1] = -1;
	sign[7][2] = 1;

  	//the first box is the box in this class 
	XMVECTOR axesA[3] = { mXAxis, mYAxis, mZAxis };
	XMVECTOR center = { 0.0f, 0.0f, 0.0f };
	float  extentsA[3] = { mXExtent, mYExtent, mZExtent };

  	//the second box is the box passed to the class in this way "thisClass.isCollising(secondBox)" 
	XMVECTOR axesB[3] = { xAxis, yAxis, zAxis };
	XMVECTOR centerB = { boxCenter - mCenter }; //offset the center so the first box is at zero
	float  extentsB[3] = { xyzExtents.x, xyzExtents.y, xyzExtents.z };



  	//start the sum with zero vectors
	XMVECTOR radiusA = { 0.0f, 0.0f, 0.0f };
	XMVECTOR radiusB = { 0.0f, 0.0f, 0.0f };

	for (int vertexCount = 0; vertexCount < 8; vertexCount++)
	{
		XMVECTOR sumA = { 0.0f, 0.0f, 0.0f };
		XMVECTOR sumB = { 0.0f, 0.0f, 0.0f };
		for (int i = 0; i < 3; i++)
		{
          	//this is based on the equation linked at the bottom, for each box
			sumA += extentsA[i] * sign[vertexCount][i] * (projectionAxis * axesA[i])*(projectionAxis * axesA[i]);
			sumB += extentsB[i] * sign[vertexCount][i] * (projectionAxis * axesB[i])*(projectionAxis * axesB[i]);
		}


      	//this section just finds the greatest radius
		XMVECTOR sumALen = XMVector3Length(sumA);
		XMVECTOR radiusALen = XMVector3Length(radiusA);

		XMFLOAT3 sumALenF, radiusALenF;
		XMStoreFloat3(&sumALenF, sumALen);
		XMStoreFloat3(&radiusALenF, radiusALen);

		if (sumALenF.x > radiusALenF.x)
			radiusA = sumA;


		XMVECTOR sumBLen = XMVector3Length(sumB);
		XMVECTOR radiusBLen = XMVector3Length(radiusB);

		XMFLOAT3 sumBLenF, radiusBLenF;
		XMStoreFloat3(&sumBLenF, sumBLen);
		XMStoreFloat3(&radiusBLenF, radiusB);

		if (sumBLenF.x > radiusBLenF.x)
			radiusB = sumB;

	}


  	//now we just do a comparison test L*D > r0+r1
	XMVECTOR centerDistance = centerB - center;
	XMVECTOR R = projectionAxis * centerDistance;
	XMVECTOR radiusSum = radiusA + radiusB;

	XMVECTOR Rlen = XMVector3Length(R);
	XMVECTOR rLen = XMVector3Length(radiusSum);

	XMFLOAT3 RLenF, rLenF;
	XMStoreFloat3(&RLenF, Rlen);
	XMStoreFloat3(&rLenF, rLen);

  	//if L*D > r0 + r1, there is no collision, otherwise intersection is there
	if (RLenF.x > rLenF.x)
		return false;
	else
		return true;
}

eq2.jpg.79af4f73a8f9a87ea0aa0ce40f1d194e.jpg

Share this post


Link to post
Share on other sites
Advertisement

I'm looking over the code, and it's pretty convoluted because of the damn DX vector math, so probably won't get too many people wanting to look over it, but if you can just answer the questions in the OP, are we finding the r0 (in the equation all the way at the bttom) for every vertex or is that equation meant to be solved as it is with just two iterations of the sigma?

Share this post


Link to post
Share on other sites

We were talking about the SAT in another thread, yes? I'd be happy to help here as well, although as you note there's a lot of code (and although I'm familiar with Eberly's paper, I'd have to review it to comment on that part of things, which would take some time).

For now I'll just ask, are you wanting a continuous test, or a discrete test? You code suggests discrete, but it might be helpful to clarify.

Share this post


Link to post
Share on other sites
Posted (edited)

 

4 hours ago, Zakwayda said:

We were talking about the SAT in another thread, yes? I'd be happy to help here as well, although as you note there's a lot of code (and although I'm familiar with Eberly's paper, I'd have to review it to comment on that part of things, which would take some time).

 For now I'll just ask, are you wanting a continuous test, or a discrete test? You code suggests discrete, but it might be helpful to clarify.

Hey Zakwayda, so glad to see you here. Yes, you helped me out in the previous thread as well. You know what happened last time? I got it working as per your specifications, but as soon as the positions of the collision boxes changed because my terrain size increased, they started to miss. Since all the code was pretty much borrowed I didn't even have a know where to begin fixing it so I decided to just fully write everything from scratch.

Anyways, back to this, the test is run on two non-static collision boxes, not on collision box vs a static mesh, so yes it's my intention to use a discrete test.

Another thing about the paper is that it has a lot of other stuff in there such as OBB collisions with triangles etc, I don't really need that at this point, it's mainly down to two pages (all my code above is based on them) which I will link below.

I'd be tremendously grateful if you can offer any advice at all on where to go from here.

 

I've also rewritten the code, changed the variable names and added more comments to be as clear as possible on what I'm doing

bool CollisionBox::mCheckOverlapOnAxis(const XMVECTOR& in_boxBCenter, const XMVECTOR& in_xAxis, const XMVECTOR& in_yAxis, const XMVECTOR& in_zAxis, XMFLOAT3 in_xyzExtents, const XMVECTOR& in_projectionAxis)

{

	//sign vector used to get all the 8 vertices
	//this is to accomodate the Sign() in the equations
	int sign[8][3];
	sign[0][0] = 1;
	sign[0][1] = 1;
	sign[0][2] = 1;

	sign[1][0] = 1;
	sign[1][1] = 1;
	sign[1][2] = -1;

	sign[2][0] = -1;
	sign[2][1] = 1; 
	sign[2][2] = -1;

	sign[3][0] = -1;
	sign[3][1] = 1;
	sign[3][2] = 1;

	sign[4][0] = 1;
	sign[4][1] = -1;
	sign[4][2] = 1;

	sign[5][0] = 1;
	sign[5][1] = -1;
	sign[5][2] = -1;

	sign[6][0] = -1;
	sign[6][1] = -1;
	sign[6][2] = -1;

	sign[7][0] = -1;
	sign[7][1] = -1;
	sign[7][2] = 1;

	//values of the box in this class
	XMVECTOR axesA[3] = { this->mXAxis, this->mYAxis, this->mZAxis };
	float    extentsA[3] = { this->mXExtent, this->mYExtent, this->mZExtent };
	XMVECTOR centerA = { 0.0f, 0.0f, 0.0f }; //paper says to use zero as boxA's center


	//values of the passed in box
	XMVECTOR axesB[3] = {  in_xAxis, in_yAxis, in_zAxis };
	float  extentsB[3] = { in_xyzExtents.x, in_xyzExtents.y, in_xyzExtents.z };
	XMVECTOR centerB = { in_boxBCenter - mCenter }; //not sure if this should be done, but I figured if centerA is always taken to be zero, then centerB should be moved over as well


	//start with radius of zero for comparison
	XMVECTOR radiusA = { 0.0f, 0.0f, 0.0f };
	XMVECTOR radiusB = { 0.0f, 0.0f, 0.0f };

	for (int vertexCount = 0; vertexCount < 8; vertexCount++)
	{
      	//get the radii of individual vertices
      	//this is based on the formula r = Sigma(0 to 2) a[i] * Sign(L*A[i])*(L*A[i])
      	// where a[i] are the extents, Sign() I took to be the sign vector, L is the projectionAxis, A[i] are the box's axes
		XMVECTOR vertexRadiusA = { 0.0f, 0.0f, 0.0f };
		XMVECTOR vertexRadiusB = { 0.0f, 0.0f, 0.0f };
		for (int i = 0; i < 3; i++)
		{
			vertexRadiusA += extentsA[i] * sign[vertexCount][i] * (in_projectionAxis * axesA[i])*(in_projectionAxis * axesA[i]);
			vertexRadiusB += extentsB[i] * sign[vertexCount][i] * (in_projectionAxis * axesB[i])*(in_projectionAxis * axesB[i]);
		}

		//now find which vertex has the largest radius and use that
        //not sure if this should be done, but I figured that we have to find the radius that encompasses
      	//all of the vertices, so it has to be the largest one 
		XMVECTOR vertexRadiusALength = XMVector3Length(vertexRadiusA);
		XMVECTOR radiusALen = XMVector3Length(radiusA);

		XMVECTOR vertexRadiusBLength = XMVector3Length(vertexRadiusB);
		XMVECTOR radiusBLen = XMVector3Length(radiusB);

		//just converting vectors to floats so we can read them
		XMFLOAT3 vertexRadiusALengthF, radiusALenF;
		XMStoreFloat3(&vertexRadiusALengthF, vertexRadiusALength);
		XMStoreFloat3(&radiusALenF, radiusALen);
		XMFLOAT3 vertexRadiusBLengthF, radiusBLenF;
		XMStoreFloat3(&vertexRadiusBLengthF, vertexRadiusBLength);
		XMStoreFloat3(&radiusBLenF, radiusB);

		//if current vertex length is greater then radius length, set the radius to be that vertex's radius
		//using .x because XMVector3Length returns length in a vector where x,y,z are all the same value, that is of the length
		if (vertexRadiusALengthF.x > radiusALenF.x)
			radiusA = vertexRadiusA;

		if (vertexRadiusALengthF.x > radiusBLenF.x)
			radiusB = vertexRadiusB;

	}


	//find the distance between two box's centers
	XMVECTOR centerDistance = centerB - centerA;
	//L*D
	XMVECTOR R = in_projectionAxis * centerDistance;
	//r0 + r1
	XMVECTOR radiusSum = radiusA + radiusB;

	//not sure if this should be done
	//but it's done to compare the length of vector R to the sum of lengths of r0 and r1
	XMVECTOR Rlen = XMVector3Length(R);
	XMVECTOR rLen = XMVector3Length(radiusSum);

	//just converting to floats so we can read the values
	XMFLOAT3 RLenF, rLenF;
	XMStoreFloat3(&RLenF, Rlen);
	XMStoreFloat3(&rLenF, rLen);

	//using .x because XMVector3Length returns length in a vector where x,y,z are all the same value, that is of the length
	if (RLenF.x > rLenF.x)
		return false;
	else
		return true;
}

 

p5.jpg

 

p6.jpg

Edited by VanillaSnake21

Share this post


Link to post
Share on other sites
Posted (edited)

Ok, good news, I think I got it to work, some assistance in the other thread gave me a heads up. The most important thing I was doing wrong is using the " * " (multiplication sign) in code when I encountered it on paper. That just resulted in member wise multiplication of vectors. (Why does DX even define * for vectors?) I should have been using dot products at every step of the way. 

 

This is the final working implementation of the entire algorithm, thanks to everyone who helped!

bool CollisionBox::mCheckForCollision(const CollisionBox& box)
{
	//define world axes
	XMVECTOR xAxis = { 1.0f, 0.0f, 0.0f };
	XMVECTOR yAxis = { 0.0f, 1.0f, 0.0f };
	XMVECTOR zAxis = { 0.0f, 0.0f, 1.0f };

	XMVECTOR inCenter = box.GetCenter();
	XMVECTOR inXAxis = box.GetXAxis();
	XMVECTOR inYAxis = box.GetYAxis();
	XMVECTOR inZAxis = box.GetZAxis();
	XMFLOAT3 inExtents = box.GetExtents();

	//define our 15 projection axes
	XMVECTOR ProjectionAxes[15];
	ProjectionAxes[0] = xAxis;
	ProjectionAxes[1] = yAxis;
	ProjectionAxes[2] = zAxis;
	ProjectionAxes[3] = inXAxis;
	ProjectionAxes[4] = inYAxis;
	ProjectionAxes[5] = inZAxis;
	ProjectionAxes[6] = XMVector3Cross(xAxis, inXAxis);
	ProjectionAxes[7] = XMVector3Cross(xAxis, inYAxis);
	ProjectionAxes[8] = XMVector3Cross(xAxis, inZAxis);
	ProjectionAxes[9] = XMVector3Cross(yAxis, inXAxis);
	ProjectionAxes[10] = XMVector3Cross(yAxis, inYAxis);
	ProjectionAxes[11] = XMVector3Cross(yAxis, inZAxis);
	ProjectionAxes[12] = XMVector3Cross(zAxis, inXAxis);
	ProjectionAxes[13] = XMVector3Cross(zAxis, inYAxis);
	ProjectionAxes[14] = XMVector3Cross(zAxis, inZAxis);


	//for each axis, check if the projections overlap
	//if an axis is found where the projections don't overlap, that means the objects are not colliding
	//if all projections overlap along all 15 axes then the objects are touching
	for (int i = 0; i < 15; i++)
		if (mCheckOverlapOnAxis(inCenter, inXAxis, inYAxis, inZAxis, inExtents, ProjectionAxes[i]) == false)
			return false;

	return true;

}

                      
                           
bool CollisionBox::mCheckOverlapOnAxis(const XMVECTOR& in_boxBCenter, const XMVECTOR& in_xAxis, const XMVECTOR& in_yAxis, const XMVECTOR& in_zAxis, XMFLOAT3 in_xyzExtents, const XMVECTOR& in_projectionAxis)
{

	//sign vector used to get all the 8 vertices
	//this is to accomodate the Sign() in the equations
	int sign[8][3];
	sign[0][0] = 1;
	sign[0][1] = 1;
	sign[0][2] = 1;

	sign[1][0] = 1;
	sign[1][1] = 1;
	sign[1][2] = -1;

	sign[2][0] = -1;
	sign[2][1] = 1; 
	sign[2][2] = -1;

	sign[3][0] = -1;
	sign[3][1] = 1;
	sign[3][2] = 1;

	sign[4][0] = 1;
	sign[4][1] = -1;
	sign[4][2] = 1;

	sign[5][0] = 1;
	sign[5][1] = -1;
	sign[5][2] = -1;

	sign[6][0] = -1;
	sign[6][1] = -1;
	sign[6][2] = -1;

	sign[7][0] = -1;
	sign[7][1] = -1;
	sign[7][2] = 1;

	//values of the box in this class
	XMVECTOR axesA[3] = { this->mXAxis, this->mYAxis, this->mZAxis };
	float    extentsA[3] = { this->mXExtent, this->mYExtent, this->mZExtent };
	XMVECTOR centerA = { 0.0f, 0.0f, 0.0f };


	//values of the passed in box
	XMVECTOR axesB[3] = {  in_xAxis, in_yAxis, in_zAxis };
	float  extentsB[3] = { in_xyzExtents.x, in_xyzExtents.y, in_xyzExtents.z };
	XMVECTOR centerB = { in_boxBCenter - mCenter }; //not sure if this should be done, but I figured if centerA is always taken to be zero, then centerB should be moved over as well


	//start with radius of zero for comparison
	float radiusA = 0.0f;
	float radiusB = 0.0f;

	for (int vertexCount = 0; vertexCount < 8; vertexCount++)
	{
		float vertexRadiusA = 0.0f;
		float vertexRadiusB = 0.0f;
		for (int i = 0; i < 3; i++)
		{
			//project each vertex onto the plane and find the distance to each one
			XMVECTOR projDotAxesA = XMVector3Dot(in_projectionAxis, axesA[i]);
			XMVECTOR projDotAxesB = XMVector3Dot(in_projectionAxis, axesB[i]);

			XMFLOAT3 projDotAxesAF, projDotAxesBF;
			XMStoreFloat3(&projDotAxesAF, projDotAxesA);
			XMStoreFloat3(&projDotAxesBF, projDotAxesB);


			vertexRadiusA += abs(extentsA[i] * sign[vertexCount][i] * projDotAxesAF.x);
			vertexRadiusB += abs(extentsB[i] * sign[vertexCount][i] * projDotAxesBF.x);
		}


		//find the vertex with the largest distance and set that as the radius of the cicle
		if (vertexRadiusA > radiusA)
			radiusA = vertexRadiusA;

		if (vertexRadiusB > radiusB)
			radiusB = vertexRadiusB;

	}


	//find the distance between two box's centers
	XMVECTOR centerDistance = centerB - centerA;
	
	//L*D
	XMVECTOR R = XMVector3Dot(in_projectionAxis, centerDistance);
	XMFLOAT3 Rf;
	XMStoreFloat3(&Rf, R);


	//find if two circle shadows overlap or not
	if (abs(Rf.x) > radiusA + radiusB)
		return false;
	else
		return true;
}

                           

 

 

Edited by VanillaSnake21

Share this post


Link to post
Share on other sites

Glad you got it working :)

I know you probably don't want to change anything now that it's working, but I'll just mention a couple things for possible future reference.

First, like in your previous implementation (if I remember correctly) you're not addressing the possible numerical issues that can arise due to taking the cross product of parallel or nearly parallel axes. I found this thread:

https://gamedev.stackexchange.com/questions/44500/how-many-and-which-axes-to-use-for-3d-obb-collision-with-sat

Which, in addition to including some helpful images, mentions the parallel axes issue. However, the example code presented there only checks for exactly parallel axes (in practice it's probably advisable to check for nearly parallel axes as well).

Second, I don't know what the context is in the paper you're using, but generally you don't have to deal with individual vertices when implementing the SAT for oriented boxes. The projected extent can be computed directly from the box axes and extents, which, if I recall correctly, was what you were doing previously. I'm sure there's a reason for the discussion of individual vertices in the paper, but I'm wondering if maybe there's some context you might be missing, because, as far as I know at least, using the vertices isn't required (and involves significant extra work).

If you look in the 'code' section on Eberly's site, you can find an implementation of the SAT for oriented boxes. It discusses and deals with the numerical issues I've mentioned, and also appears to compute the projected extents directly from the axes and extents, as I mentioned, rather than using vertices. Be forewarned though that the implementation is optimized and therefore isn't necessarily intuitive.

In summary, the numerical issues might be worth looking into, as those could actually lead to incorrect results. The vertex issue, on the other hand, is basically just an optimization issue, but since you were doing it the more optimal way before, it seems like your previous implementation (with any bugs fixed of course) might've been closer to the mark.

Share this post


Link to post
Share on other sites
8 hours ago, Zakwayda said:

Glad you got it working :)

I know you probably don't want to change anything now that it's working, but I'll just mention a couple things for possible future reference.

First, like in your previous implementation (if I remember correctly) you're not addressing the possible numerical issues that can arise due to taking the cross product of parallel or nearly parallel axes. I found this thread:

https://gamedev.stackexchange.com/questions/44500/how-many-and-which-axes-to-use-for-3d-obb-collision-with-sat

Which, in addition to including some helpful images, mentions the parallel axes issue. However, the example code presented there only checks for exactly parallel axes (in practice it's probably advisable to check for nearly parallel axes as well).

Second, I don't know what the context is in the paper you're using, but generally you don't have to deal with individual vertices when implementing the SAT for oriented boxes. The projected extent can be computed directly from the box axes and extents, which, if I recall correctly, was what you were doing previously. I'm sure there's a reason for the discussion of individual vertices in the paper, but I'm wondering if maybe there's some context you might be missing, because, as far as I know at least, using the vertices isn't required (and involves significant extra work).

If you look in the 'code' section on Eberly's site, you can find an implementation of the SAT for oriented boxes. It discusses and deals with the numerical issues I've mentioned, and also appears to compute the projected extents directly from the axes and extents, as I mentioned, rather than using vertices. Be forewarned though that the implementation is optimized and therefore isn't necessarily intuitive.

In summary, the numerical issues might be worth looking into, as those could actually lead to incorrect results. The vertex issue, on the other hand, is basically just an optimization issue, but since you were doing it the more optimal way before, it seems like your previous implementation (with any bugs fixed of course) might've been closer to the mark.

 

Ok, well I don't even know where to begin. I didn't even realize he had a site (although it's listed right there at the top of the paper). It's a treasure trove. There are so many good resources there, not just on SAT but DX11 graphics and math algorithms, I've spent the better part of today just skimming it, and it's like a rabbit hole. Thanks for pointing it out. 

 

So the SAT, it appears that I have completely mis-implemented it. I'm trying to rewrite some of my code with his implementation but as you mentioned, he doesn't use verticies at all. He just goes directly through axes and extents. Also he does have a very clear way to handle the parallel test, and now that I'm seeing it, I can't believe I haven't implemented it earlier. Especially in my case since none of my boxes tumble, I can just end the test after testing the first 6 face normals and not even have to do the edges, which I imagine will speed up the test considerably. And yes, his code is optimized. You weren't kidding about that. I'm trying to "de-optimize" it a little just so that it's easier to read and debug at least for now, but overall, it's not so bad. He writes very clearly and comments often, so I feel pretty confident I can do this :)

Also, just to note, he has a book out, which looks to be a very interesting read. 

But yea man, thanks a bunch (again), you definitely steered me in the right direction this time as well. Cheers!

 

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

  • Advertisement
×

Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!