Jump to content
  • Advertisement
Sign in to follow this  
extralongpants

Intersection Time of Circle and Polygon Using SAT

This topic is 4058 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

I'm having trouble accurately determining the time of intersection between a moving oriented box (implemented as a 2d polygon) and a circle. My static intersection test for a circle and an obb seems to work perfectly, but when I try and calculate the intersection time of the shapes when they're moving, I don't always get good results. Sometimes my intersection method reports back an intersection time of 0. This causes several problems, the worst of which is that I don't get a sensible collision normal, causing my collision reaction code to screw up. This wouldn't be entirely surprising if my objects were moving really fast, or if my objects were ending up very close to each other after a previous collision and floating point innaccuracy crept into the equation, but I don't think that is the case here. The code I'm using to test for axis separation after the shapes have been projected is more-or-less copied straight out of Dave Eberly's Box3Box3 intersection code, from his Wild Magic Engine . I suspect then, that the problem lies elsewhere in the code. Here are what I perceive to be the relevant parts of my code. Let me know if you need me to post any more. Separating axis stuff. The separating axes for the box are the two normalized extent vectors.

protected float SeparatingAxisTest(Vector2[] axes, Vector2 relVel, Circle other,
	out Vector2 colNormThis, out Vector2 colNormOther)
{
	int axisIdx;
	int vertIdx;
	float curDot;
	float minThis, maxThis;
	float minOther, maxOther;
	float velDot;
	float minT = 0.0f;
	float maxT = float.MaxValue;

	colNormOther = axes[0];
	colNormThis = -axes[0];


	// test against poly's separating axes
	for (axisIdx = 0; axisIdx < axes.Length; ++axisIdx)
	{
		// project relative velocity onto current axis
		Vector2.Dot(ref relVel, ref axes[axisIdx], out velDot);

		// project each point onto the separating axis (edge normal)
		// and find the region of projection (using min and max values of projection)
		Vector2.Dot(ref Verts[0], ref axes[axisIdx], out minThis);
		maxThis = minThis;

		// go through this poly's verts
		for (vertIdx = 1; vertIdx < Verts.Length; ++vertIdx)
		{
			Vector2.Dot(ref Verts[vertIdx], ref axes[axisIdx], out curDot);

			if (curDot > maxThis)
			{
				maxThis = curDot;
			}
			else if (curDot < minThis)
			{
				minThis = curDot;
			}
		}

		// now project the circle onto the line
		Vector2.Dot(ref other.Center, ref axes[axisIdx], out minOther);
		maxOther = minOther + other.Radius;
		minOther -= other.Radius;

		float oldMinT = minT;
		if (IsSeparated(minThis, maxThis, minOther, maxOther, velDot, ref minT, ref maxT))
		{
			return -1.0f;
		}

		if (oldMinT != minT)
		{
			// we found a new time
			colNormThis = axes[axisIdx];
			colNormOther = -axes[axisIdx];
		}			
	}

	return minT;
}



protected bool IsSeparated(float minThis, float maxThis, float minOther, float maxOther,
	float speed, ref float minTime, ref float maxTime)
{
	float invSpeed;
	float curT;

	if (maxOther < minThis)
	{
		// we are on the right of the other shape

		if (speed <= 0.0f)
		{
			// moving away...
			return true;
		}

		// get time to intersection
		invSpeed = 1.0f / speed;
		curT = (minThis - maxOther) * invSpeed;
		
		if (curT > minTime)
		{
			minTime = curT;
		}

		if (minTime > 1.0f)
		{
			// beyond the distance we're travelling
			return true;
		}

		curT = (maxThis = minOther) * invSpeed;
		if (curT < maxTime)
		{
			maxTime = curT;
		}

		if (minTime > maxTime)
		{
			return true;
		}
	}
	else if (maxThis < minOther)
	{
		// we are on the left side of the other shape

		if (speed >= 0.0f)
		{
			// travelling away...
			return true;
		}

		// calculate time to intersection
		invSpeed = 1.0f / speed;
		curT = (maxThis - minOther) * invSpeed;
		
		if (curT > minTime)
		{
			minTime = curT;
		}

		if (minTime > 1.0f)
		{
			// beyond the distance we're travelling
			return true;
		}

		curT = (minThis - maxOther) * invSpeed;
		if (curT < maxTime)
		{
			maxTime = curT;
		}

		if (minTime > maxTime)
		{
			return true;
		}
	}
	else
	{
		// we are overlapping on this axis, even without moving
		// along our velocity

		if ( speed > 0.0f )
		{
			curT = (maxThis - minOther) / speed;

			if ( curT < maxTime )
			{
				maxTime = curT;
			}

			if ( minTime > maxTime )
			{
				return true;
			}
		}
		else if (speed < 0.0f)
		{
			curT = (minThis - maxOther) / speed;


			if (curT < maxTime)
			{
				maxTime = curT;
			}

			if (minTime > maxTime)
			{
				return true;
			}
		}
	}

	return false;
}


The calling function, where the potential separating axes are calculated and the results of the test are returned. Again, the separating axes of the box are the normalized extent vectors.
float t1 = SeparatingAxisTest(SeparatingAxes, otherVel - thisVel, circle, out tempNormThis1, out tempNormOther1);

if (t1 < 0.0f)
{
	return t1;
}

// calculate separating axis for the circle
Vector2[] circleAxes = new Vector2[1];
float curDist;
float minDist = float.MaxValue;

// search for closest point to circle and use that to determine
// the separating axis
for (int axisIdx = 0; axisIdx < Verts.Length; ++axisIdx)
{
	curDist = Vector2.DistanceSquared(circle.Center, Verts[axisIdx]);
	if (curDist < minDist)
	{
		minDist = curDist;
		circleAxes[0] = circle.Center - Verts[axisIdx];
		circleAxes[0].Normalize();
	}
}


float t2 = SeparatingAxisTest(circleAxes, otherVel - thisVel, circle, out tempNormThis2, out tempNormOther2);

if (t2 < 0.0f)
{
	return t2;
}

// return the minimum collision time
if (t1 > t2)
{
	return t1;
}
else
{
	return t2;
}


Thanks in advance for any help or information.

Share this post


Link to post
Share on other sites
Advertisement
I have moving-circle-rectangle code at my site. Have you tried this? I used to have a sample application that illustrates. I recall it worked just fine, but as most folks know, code can "rot" over time (as related code is modified). I can resurrect it if need be.

Share this post


Link to post
Share on other sites
I remember trying swept SAT with circles and polygons, and the result was OK, but there was some major imprecisions when the displacement was large. It's not as accurate as the polygon test, it can lead to false positives afaik, where the polygon and sphere are found to be colliding yet when you move them to the supposedly time of collision, there do not quite touch.

Share this post


Link to post
Share on other sites
Quote:
Original post by Dave Eberly
I have moving-circle-rectangle code at my site. Have you tried this? I used to have a sample application that illustrates. I recall it worked just fine, but as most folks know, code can "rot" over time (as related code is modified). I can resurrect it if need be.

I may just resort to that [smile]. I wanted SAT working because the code could work for any convex polygon, but it may not be worth it.

The situation is frustrating because the code detects static collisions perfectly fine. It's just a matter of calculating the correct time of intersection, which seems like an easy task when working with SAT.

Quote:
Original post by oliii
I remember trying swept SAT with circles and polygons, and the result was OK, but there was some major imprecisions when the displacement was large. It's not as accurate as the polygon test, it can lead to false positives afaik, where the polygon and sphere are found to be colliding yet when you move them to the supposedly time of collision, there do not quite touch.

Yeah, I've actually seen that occur sometimes, but I'm OK with that kind of precision error right now. At this point I'd rather have the circle stop a little too soon than stop too late [lol].

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!