Odd issue with Separating Axis Theorem

Started by
7 comments, last by snake5 8 years, 7 months ago

I have the collision detection working great. I have a hallway I generate with a box that moves down it. I have gravity that will pull the object down when I raise it with [space]. If I turn off collision response, the box will stop if it's next move will collide, every time. But with collision response on, it will follow most surfaces without penetrating perfectly. But certain spots of some faces will cause the collision response to tell it to go to an opposing face versus along the face it is against. Like if it was moving along the face with an -x normal, it will jump to the face with the -y normal instead. And when I look at the list of axes and min/max, the min/max differences all have a much larger gap that it should. Has anyone run into anything like this?

The hallway is composed of 4 different OBB, one for each wall.

Advertisement

Hard to guess without the code, so I'd recommend posting it here. But if I really had to guess, I'm thinking that maybe you're not picking the axis with the smallest overlap for resolution, but only the first that the collision is detected at or something like that.


	bool Collide(RigidBody* other, Vector4f& collision)
	{
		std::vector<Vector3f> axies;
		std::vector<Vector4f> minmax;
		int count = 0;
		float min0, max0;
		float min1, max1;
		Vector3f dir;
		float dist = 10000.f;
		Vector3f axis;
		bool moving = false;
		bool touching = false;
		int wAxis = -1;
		int which = -1;
		axies.resize(0);
		minmax.resize(0);
		for (count = 0; count < GetFaceSize(); count++)
		{
			dir = GetNormal(count);
			Project(dir, min0, max0);
			other->Project(dir, min1, max1);
			if (max0 < min1 || max1 < min0)
				return false;
			axies.push_back(dir);
			minmax.push_back(Vector4f(min0, max0, min1, max1));
			if (max1 == min0 || max0 == min1)
			{
				touching = true;
			}			
			else
			{
				if (max0 > min1 && dir != Vector3f(0, 0, 0))
				{
					if (dist > max0 - min1 && max0 - min1 > 0.0f)
					{
						dist = max0 - min1;
						axis = dir;
						wAxis = axies.size() - 1;
					}
				}
				else if (dir != Vector3f(0, 0, 0))
				{
					if (dist > max1 - min0 && max1 - min0 > 0.0f)
					{
						dist = max1 - min0;
						axis = dir;
						wAxis = axies.size() - 1;
					}
				}
			}
		}
		for (count = 0; count < other->GetFaceSize(); count++)
		{
			dir = other->GetNormal(count);
			Project(dir, min0, max0);
			other->Project(dir, min1, max1);
			if (max0 < min1 || max1 < min0)
				return false;
			axies.push_back(dir);
			minmax.push_back(Vector4f(min0, max0, min1, max1));

			if (max1 == min0 || max0 == min1)
			{
				touching = true;
			}
			else if (max0 > min1 && dir != Vector3f(0, 0, 0))
			{
				if (dist > max0 - min1 && max0 - min1 > 0.0f)
				{
					dist = max0 - min1;
					axis = dir;
					wAxis = axies.size() - 1;
				}
			}
			else if (dir != Vector3f(0, 0, 0))
			{
				if (dist > max1 - min0 && max1 - min0 > 0.0f)
				{
					dist = max1 - min0;
					axis =  dir;
					wAxis = axies.size() - 1;
				}
			}
		}
		
		int counts;
		for (count = 0; count < GetFaceSize(); count++)
		{
			for (counts = 0; counts < other->GetFaceSize(); counts++)
			{
				dir = GetNormal(count).CrossProduct(other->GetNormal(counts));
				dir.Normalize();
				Project(dir, min0, max0);
				other->Project(dir, min1, max1);
				if (max0 < min1 || max1 < min0)
					return false;

				axies.push_back(dir);
				minmax.push_back(Vector4f(min0, max0, min1, max1));

				if (max1 == min0 || max0 == min1)
				{
					touching = true;
				}
				else if (max0 > min1 && dir != Vector3f(0, 0, 0))
				{
					if (dist > max0 - min1 && max0 - min1 > 0.0f)
					{
						dist = max0 - min1;
						axis = dir;
						wAxis = axies.size() - 1;
					}
				}
				else if (dir != Vector3f(0, 0, 0))
				{
					if (dist > max1 - min0 && max1 - min0 > 0.0f)
					{
						dist = max1 - min0;
						axis = dir;
						wAxis = axies.size() - 1;
					}
				}
			}
		}
		if (touching == true && dist > 1000.0f)
		{
			dist = 0;
		}		
		collision = Vector4f(axis * -1.0f, dist);		
		return true;
	}
  1. Why "dir != Vector3f(0, 0, 0)"? If a face normal is wrong, don't process it at all (and such faces shouldn't exist anyway).
  2. "bool touching = false;" is completely unnecessary.
  3. "max0 > min1" is always true, that's the wrong comparison to make there. You should check whether max0-min1 is smaller than max1-min0 and use the smallest for overlap depth.
  4. "max0 - min1 > 0.0f" - this is pointless, just use "if (max0 <= min1 || max1 <= min0)" (<= instead of <) to filter these cases if you want.
  5. "dir = GetNormal(count).CrossProduct(other->GetNormal(counts));" - WTF. You just need the normals of the other body's faces.

3 and 5 are most important to fix, one of those (or both) is the most likely cause of the issues you're having. Wouldn't hurt to remove those redundancies from code though.

Well the code is mostly fixed.


	bool Collide(RigidBody* other, Vector4f& collision)
	{
		std::vector<Vector3f> axies;
		std::vector<Vector4f> minmax;
		int count = 0;
		float min0, max0;
		float min1, max1;
		Vector3f dir;
		float dist = 10000.f;
		Vector3f axis;
		int wAxis = -1;
		int which = -1;
		axies.resize(0);
		minmax.resize(0);
		Vector3f offset = pos - other->pos;
		for (count = 0; count < GetFaceSize(); count++)
		{
			dir = GetNormal(count);
			Project(dir, min0, max0);
			other->Project(dir, min1, max1);
			if (max0 < min1 || max1 < min0)
				return false;
			axies.push_back(dir);
			minmax.push_back(Vector4f(min0, max0, min1, max1));
		}
		for (count = 0; count < other->GetFaceSize(); count++)
		{
			dir = other->GetNormal(count);
			Project(dir, min0, max0);
			other->Project(dir, min1, max1);
			if (max0 < min1 || max1 < min0)
				return false;
			axies.push_back(dir);
			minmax.push_back(Vector4f(min0, max0, min1, max1));
		}
		
		int counts;
		for (count = 0; count < GetFaceSize(); count++)
		{
			for (counts = 0; counts < other->GetFaceSize(); counts++)
			{
				dir = GetNormal(count).CrossProduct(other->GetNormal(counts));
				dir.Normalize();
				Project(dir, min0, max0);
				other->Project(dir, min1, max1);
				if (max0 < min1 || max1 < min0)
					return false;

				axies.push_back(dir);
				minmax.push_back(Vector4f(min0, max0, min1, max1));
			}
		}
		int aCount = 0;		
		float temp;		
		for (count = 0; count < axies.size(); count++)
		{
			if (!axies[count].isEqual(Vector3f(0, 0, 0)))
			{				
				if ((minmax[count].y - minmax[count].z < minmax[count].w - minmax[count].x) && minmax[count].y > minmax[count].z)
				{
					if (dist > minmax[count].y - minmax[count].z)
					{
						wAxis = count;
						axis = axies[count];
						dist = minmax[count].y - minmax[count].z;
					}
				}
				else if (minmax[count].w > minmax[count].x)
				{
					if (dist > minmax[count].w - minmax[count].x)
					{
						wAxis = count;
						axis = axies[count];
						dist = minmax[count].w - minmax[count].x;
					}
				}
			}
		}		
		if ((pos - other->pos).Dot(axis) < 0)
		{
			axis = axis * -1.0f;
		}
		collision = Vector4f(axis, dist);		
		return true;
	}

The cross product of the 2 box faces is for edge testing. And the check for a 0 direction is because cross product of same directions give you a 0.

Ty snake5 on the min/max, that was a problem, and the "touching == true" was unneccessary.

It works mostly. When two oobs meet, I seem to get caught or pushed out of the hallway.

  1. What edge testing? For two convex polygonal shapes (polyhedrons), the separating plane is guaranteed to be in the same direction as one of the faces.
  2. Why store both max-min values? There's no use for the biggest difference, and there's no use for anything but the difference. One float is enough.
  3. Why store arrays of axes/distances? You just need one distance value (the shortest one) and the axis that goes with it.
  4. What is the point of the last loop? It looks like pointless last-minute decision making, which can be avoided by fixing [2] and most importantly [3]. Since it's also extremely hard to read, I'm guessing that whatever issue you're having now, it's there.

Without edge testing i was getting false positives. And the last loop is testing the mix/max for the smallest overlap. X,Y is min0 and max0. Z,W is min1, max1. I don't plan on keeping it like that, as storing the values is definitely not optimized. It was just for debugging.

Walking passed the "cracks" between 2 oob is apparently a common problem. I am trying to research and see what I can find. Although any suggestions on that would be great.

EDIT:

I am averaging all the collisions together and then applying the average to the object to move it. It appears to be working right now with low gravity. Higher gravity, back to same problem.

I gave two exhaustive talks about the SAT and contact creation. Maybe they are helpful:

Robust Contact Creation for Physics Simulations

http://media.steampowered.com/apps/valve/2015/DirkGregorius_Contacts.pdf

The Separating Axis Test Between Convex Polyhedra

http://media.steampowered.com/apps/valve/2013/DGregorius_GDC2013.zip


Without edge testing i was getting false positives.

In that case some other code must be wrong (like the function that returns normals -- does it return *face* normals?). Because what you're testing there is not edges. A cross product of two random surface normals is basically a random vector. There's no adjacency data being used, no special properties of shapes, it's just random.

This topic is closed to new replies.

Advertisement