Jump to content
  • Advertisement
Sign in to follow this  
Lazy Foo

Circle/AABB sweep test

This topic is 3175 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 get that a Circle/AABB sweep test involves creating a capsule by adding a border to the AABB as thick as the radius of the circle and then finding the point of intersection where the center of the cricle meets the capsule. What I can't figure out or find is how to calculate the point where the center of the circle meets the capsule. I've been googling around and been finding incomplete explanations and broken links. So how do I calculate the time the center of the circle hits the capsule?

Share this post


Link to post
Share on other sites
Advertisement
The capsule can be constructed as an AABB in the middle, and a circle at each end. Divide the problem into three tests, one point-AABB test, and two point-circle tests.

Share this post


Link to post
Share on other sites
No it can't, that's not what he meant. He meant he's turning the AABB into a larger rounded rectangle.

Anyway : You don't need to explicitly do that. I've never written a SweptCircle->AABB collision test but I have written a SweptCircle->Polygon collision test, which is the generalized form of the problem. It just iterates over every edge and checks them against the swept circle, so all you ultimately need is a SweptCircle->LineSegment test.

Now, instead of just returning a bool, the function calculates how far the circle would move before hitting the segment (If it ever hits at all), and returns a Resting Point; where the center of the circle will be when it's stopped. When checking against the polygon, the closest collision is the one to use.


public static bool CollideSweptCircleWithSegment(SweptCircle Circle, Vector2 P0, Vector2 P1,
out Vector2 ContactPoint, out Vector2 RestingPoint)
{
ContactPoint = P0;
RestingPoint = P0;

//Find the normal of the segment by rotating it 90 degrees.
Vector2 Normal = VectorUtility.Perpendicular(P1 - P0);
Normal.Normalize();

if (Vector2.Dot(Circle.Direction, Normal) >= -TMath.Epsilon) return false; //Cull backfaces.

//The circle comes with the left and right extremes, perpendicular to the direction
//of motion, already calculated. So if both points are out beyond the left side,
//or both are out beyond the right side, there can't be a collision.
//And if either one is inside, there MUST be a collision!
if (VectorUtility.CrossZ(Circle.Direction, P0 - Circle.Left) < 0.0f
&& VectorUtility.CrossZ(Circle.Direction, P1 - Circle.Left) < 0.0f) return false; //Cull outside.
if (VectorUtility.CrossZ(Circle.Direction, P0 - Circle.Right) > 0.0f
&& VectorUtility.CrossZ(Circle.Direction, P1 - Circle.Right) > 0.0f) return false; //Cull outside.


//After this finding the actual resting point is just a line->line intersection test
//and a bit of tweaking things.

//Build a line in front of the line to be intersected with.
Vector2 RP0 = P0 + Normal * Circle.Radius;
Vector2 RP1 = P1 + Normal * Circle.Radius;

if (!Intersection.LineWithLine(Circle.Center, Circle.Center + Circle.Direction, RP0, RP1, out RestingPoint)) return false; //Parallel maybe

Vector2 U = Normal;
Vector2 V = P1 - P0;
Vector2 W = RestingPoint - P0;
float D = VectorUtility.CrossZ(U, V);

if (TMath.AlmostZero(Math.Abs(D)))
return false; //Parallel

float SI = VectorUtility.CrossZ(V, W) / D;
ContactPoint = RestingPoint + (SI * U);

//All we have to do now is make sure the collision didn't happen out beyond
//the end of the segment. If it did, the contact point is an end point, and we
//need to recalculate the resting point.
float TI = VectorUtility.CrossZ(U, W) / D;
if (TI >= 0 && TI <= 1)
{
if (Vector2.Dot(ContactPoint - Circle.Center, Circle.Direction) <= 0.0f) return false;
return true; //Contact point is on the line segment;
}

if (TI < 0)
ContactPoint = P0;
if (TI > 1)
ContactPoint = P1;

if (Vector2.Dot(ContactPoint - Circle.Center, Circle.Direction) <= 0.0f) return false;

//Calculate new RestingPoint

Vector2 IntersectionPoint;
Intersection.LineWithLine(Circle.Center, Circle.Center + Circle.Direction,
ContactPoint, ContactPoint + VectorUtility.Perpendicular(Circle.Direction), out IntersectionPoint);

float SegmentLength = (IntersectionPoint - ContactPoint).Length();

float SecondSegmentLength = (float)Math.Sqrt(Circle.Radius * Circle.Radius - SegmentLength * SegmentLength);

Vector2 ReverseDirection = -Circle.Direction;
ReverseDirection.Normalize();
RestingPoint = IntersectionPoint + (ReverseDirection * SecondSegmentLength);

return true;

}

Share this post


Link to post
Share on other sites
I see. The same principle should apply though, just that the rounded rect has four cicles in the corners instead, though perhaps a polygonal approximation is easier..
Anyway, these are the shapes, unless I'm mistaken:


And a point-to-rounded-rect collision is exactly the same as a circle-AABB collision. The rounded rect can be describes as two AABBs and four circles, where the AABBs are extended in the horizontal or the vertical direction, with the circle radius in each direction.


So to solve this, you could do a line-segment intersection against each of those 6 elements in the rounded rect, and the closest collision is the answer. This will easily give you correct surface information, if you want to slide against the corners etc.

Share this post


Link to post
Share on other sites
Notice that my solution would just treat the edges of the original AABB as line segments, and then only has 4 tests - and the corners behave properly too.

Share this post


Link to post
Share on other sites
True, though for both efficiency and simplicity I think each of those tests is quite expensive. Actually it can be simplified further, into a single line-AABB intersection test, and possibly one line-circle test, depending on the outcome of first test.
As seen in the image below, a single line-test to a larger AABB, expanded with the circle radius from the original AABB, decides whether or not the swept circle can hit at all. If it does hit, one needs only to check if the collision point is in any of the corners (colored in the image). If that is the case, the real collision point is always the line-circle intersection to that circle, and otherwise it's the collision point from the first test.

Share this post


Link to post
Share on other sites
I have an implementation for circle-rectangle intersection, any orientation rectangle and the objects can be moving. See my Intersection page. See the files Wm4IntrCircle2Box2.{h,cpp}. I used to have a sample application illustrating this, but I'd have to fetch it from my archives.

That page also has an implementation for sphere-box intersection, any orientation box and the objects can be moving. Same web page, files Wm4IntrSphere3Box3.{h,cpp}.

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!