Advanced Sphere-Sphere Continuous Collision Detection (CCD)

By , last updated July 21, 2019

In simple collision detection algorithm we have calculated whether the two spheres were colliding. More advanced calculations include finding the time of the collision as well as the direction of the spheres during the test.

Let us assume we have a vector between sphere centers (s), relative speed (v) and sum of radii (radiusSum):
vec{s} = s1.pos - s2.pos
vec{v} = s1.vel - s2.vel
radiusSum = s1.radius + s2.radius

We can calculate squared distance between centers. If the distance (dist) is negative, they already overlap:
dist = vec{s}.dot(vec{s})

Spheres intersect if squared distance between centers is less than squared sum of radii:
dist < radiusSum * radiusSum

If b is 0.0 or positive, they are not moving towards each other:
b = vec{v}.dot(vec{s})
a = vec{v}.dot(vec{v})

If d is negative, no real roots, and therefore no collisions:
d = b*b - a*dist

If we’ve come so far, we can calculate time of the collision:
t = ( -b - sqrt{d}) / a

Read also: Sphere vs AABB collision detection test

Code

	bool testMovingSphereSphere(Scenenode *A, Scenenode *B, double &t)
	{
		Planet *pa = (Planet *) A;
		Planet *pb = (Planet *) B;

		Vector3D<double> s = pa->pos - pb->pos; // vector between the centers of each sphere
		Vector3D<double> v = pa->vel - pb->vel; // relative velocity between spheres
		double r = pa->radius + pb->radius;

		double c = s.dot(s) - r*r; // if negative, they overlap
		if (c < 0.0) // if true, they already overlap
		{
			t = .0;
			return true;
		}

		float a = v.dot(v);

		float b = v.dot(s);
		if (b >= 0.0)
			return false; // does not move towards each other

		float d = b*b - a*c;
		if (d < 0.0)
			return false; // no real roots ... no collision

		t = (-b - sqrt(d)) / a;

		return true;

	}

Professional Software Developer, doing mostly C++. Connect with Kent on Twitter.

Comments

  1. MC July 23, 2020 Leave a Reply

    Hello,
    it seems that this line:
    “If b is 0.0 or positive, they are not moving towards each other:”
    and the code:

    float b = v.dot(s);
    if (b >= 0.0)
    return false; // does not move towards each other

    Are false. If the dot product is positive, the angle between the two vector is <90 degree, meaning that the relative velocity is going somewhat in the same direction as the relative position. Therefore they are moving towards each other.

Leave a Reply


You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*