Swept circle circle intersection test isn't working correctly.

06038bd876add42c26fb4628ff49e1b0
0
Dr_Spankenstein 101 Feb 21, 2010 at 14:22

Is this method correct for a swept circle circle test?

I test 2 circles (A and B)

  • Create a ray from circle B
  • Position = B.Position
  • Direction = Relative velocity of A and B (B.Vel - A.Vel)
  • Create a circle C by using A’s position with a radius of A + B (Minkowski)
  • Test ray against circle C

In code:

        public static bool TestSweptCircleCircle(Shape s1, Shape s2, ref Contact2D contact)
        {
            CD_Circle a = (CD_Circle)s1;
            CD_Circle b = (CD_Circle)s2;

            //===========================================================
            //---[Swept Test]--------------------------------------------
            //===========================================================

            // Convert the circle for b into a 2D ray
            Vector2 origin = b.Position;                                // Origin of ray
            Vector2 direction = b.Velocity - a.Velocity;                // Direction of ray

            // Expand the circle a by the radius of the circle b
            // This transforms a circle/circle collision test into a ray/circle collision test
            CD_Circle c = new CD_Circle(a.Position, a.Radius + b.Radius);

            // Test ray for intersection against expanded circle
            return RayCircleIntersect(origin, direction, c, ref contact);
        }

        private static bool RayCircleIntersect(Vector2 ray_Origin, Vector2 ray_Direction, CD_Circle circle, ref Contact2D contact)
        {
            Vector2 m = ray_Origin - circle.Position;
            float c = Vector2.Dot(m, m) - circle.Radius * circle.Radius;
            float b = Vector2.Dot(m, ray_Direction);

            // Early exit if:
            // - Ray origin outside circle (c > 0) AND 
            // - Ray pointing away from circle (b > 0)  
            if (c > 0.0f && b > 0.0f)
            {
                return false;
            }

            // Discriminant (Quadratic equation) = b^2 - c
            float discr = b * b - c;

            // A negative discriminant corresponds to Ray missing Sphere
            if (discr < 0.0f)
            {
                return false;
            }

            // Now Ray must hit Sphere

            // Compute smallest value of intersection (t)
            float t = -b - (float)Math.Sqrt(discr);

            // If (t) is negative, Ray started inside Sphere so clamp (t) to zero
            if (t < 0.0f)
            {
                t = 0.0f;
            }
       
            //contact.penetration = t;
            contact.point = ray_Origin + t * ray_Direction;
            contact.normal = Vector2.Normalize(contact.point - circle.Position);

            return true;
        }

There is something incorrect with my method as the collision response doesn’t work.

The penetration depth is incorrect and the method returns true even when the circles are not intersecting.

Can anyone point out where I have gone wrong please?

1 Reply

Please log in or register to post a reply.

33891991e3da356e7edf0275c240d709
0
Kweepa 101 Jun 03, 2010 at 21:49

Your ray circle intersection test is wrong.
It looks like you were assuming that the ‘a’ part of the quadratic equation is 1.0.
Also, the discriminant should be 4ac. So:

float a = Vector2.Dot(ray_Direction, ray_Direction);
float discr = b*b - 4*a*c; // note the 4
...
float t = (-b - (float)Math.Sqrt(discr))/(2*a);

And so on from there.