Hello devs! I've searched high and low to find an accurate swept sphere formula without success. I do own Realtime Collision Detection by C Ericson and it didn't help because I can't math.

Here's the code I have (it's in javascript but lang doesn't matter as long as it's vector math). It only sort of works because it doesn't take into account the angle of the sphere's velocity - I don't know how to get the actual time of impact. Please help with code! I'm REALLY bad at math, sorry…

sweepSphereVsCapsule(a, c) {
	const info = closestSegmentSegment(a.position, a.projection, c.start, c.end)
	const radii = a.radius + c.radius
	if (info.dist2 <= radii * radii) {
		vec.copy(info.closest2).sub(info.closest1)
		info.penetration = radii - vec.getLength() // ←-- this is the problem
		info.hit = true
	}
	return info
}

And here's what the issue is: [broken image link]

You haven't instantiated the variable vec in this code snippet, but let's assume vec is a global variable defined somewhere else (*shocked face looking down upon you*). To help you solve your problem, I will describe elastic collision below.

1. Project the velocity vector of the sphere onto the line of collision.

2. Project the velocity vector of the capsule onto the line of collision.

proj u onto v = u . v / |v^2| * v

3. Add step 1 and step 2 together. Multiply by -2 (to flip the direction so the sphere reflects away from the capsule).

4. Add the result in step 3 to the velocity vector of the sphere, and add negative the result to the velocity vector of the capsule.

Try this fixed pseudo code:

sweepSphereVsCapsule(a, c) {
	const info = closestSegmentSegment(a.position, a.projection, c.start, c.end)
	const radii = a.radius + c.radius
	if (info.dist2 <= radii * radii) {
	    // the direction from the center of the sphere to the center of the capsule (where is this?)
		let direction = new Vector().copy(info.closest2).sub(info.closest1)
		// a.velocity is a Vector. projectOnto returns a new Vector.
		info.projectionVector = a.velocity.projectOnto(direction);
		info.hit = true
	}
	// Add -2 * projectionVector to a.velocity somewhere.
	// Add 2 * projectionVector to c.velocity somewhere if you wish for the capsule to move.
	return info
}

TODO: Account for the mass of the sphere and capsule. Research Elastic Collisions Using Vectors.

AFAICT you're not doing an actual sweep test (ie a process which will report the correct time of collision), you're only doing a yes/no overlap test between the capsule swept by the circle, and the static capsule.

This means the only info you can get out of it is will the circle sweep through the capsule, not when/where.

IIRC Ericson mentions using this sort of test as a compromise between a plain circle-vs-capsule overlap test (which will miss fast movements) and a true sweep test (which is more complex). With your method, you know there will be a collision, but not where/when: now you can either bisect/substep to find a more accurate approximation to the time of intersection, or perform a proper sweep test to find it exactly.

I might be wrong but I don't think there's a “nice” way to sweep a circle vs a lineseg with a single code-path, in the past I've implemented it as three tests: sweep the circle vs both the lineseg endpoints, and sweep the circle vs the plane containing the line. It looks like there are several posts which might help with some code/explanation: https://www.google.com/search?q=swept+circle+vs+lineseg&oq=swept+circle+vs+lineseg&aqs=chrome..69i57j0i271l2j69i60l2j69i61j69i60l2.14030j0j7&sourceid=chrome&ie=UTF-8

(note: I assumed this was in 2d, but in 3d the sweep test should be the same: sweep the circle vs the two endpoints (each test is equivalent to a ray-vs-sphere query) and then vs the line containing the capsule lineseg (I'm not sure if this is best handled as sphere-vs-line (then checking if the contact point is on the segment), but I bet google probably knows.)

Euthyphro said:

Try this fixed pseudo code: …

Thank you for the reply! I just tried that and it results in… strange behavior. I did leave out a bit of code, sorry - that vec is instantiated elsewhere and reused to avoid garbage collection. I'm using threejs' Vector class, but in 2d so some methods are removed, but I have no idea if it's right.

raigan said:

AFAICT you're not doing an actual sweep test (ie a process which will report the correct time of collision), you're only doing a yes/no overlap test between the capsule swept by the circle, and the static capsule.

Thanks and yes, that is correct - I'm looking for the time of collision, not a simple intersection test which I already have. At the moment I can only take the closest point along the velocity vector of the circle and basically subtract circle.radius + capsule.radius but as my screenshot shows… it is not accurate, because the time of collision can happen much earlier than that simple formula I've been using.

Apparently I need to calculate the Minkowski Sum, but I only know how to copy/paste, not read mathematical syntax.

@dp2k No problem. I guess I don't really understand what is going on. If you are doing real-time collision, why would you need to know the time in advance of the collision?

Concerning preinitializing every local variable you would ever use, I recommend strongly against it because there is no performance benefit. This would be silly:

var i, j, k, min, max, vec1, vec2, vec3;
for(i = 0; i<max; i++) {
	for(j = 0; j<max; j++) {

	}
}

"Minkowski sum” is just a fancy term for the geometry of the problem.

In your case the geometry is a ray (the directed line segment between the sphere's old and new positions), and a capsule (a line segment between two static points, whose radius is the sum of the input sphere + capsule radii).

So, the problem you're trying to solve is equivalent to: find the time of intersection between a ray and a capsule. Googling “ray capsule intersection 3D” should lead you to some code you can copy+paste; for example, this is code for testing ray-vs-capsule intersection in 3D: https://www.geometrictools.com/GTE/Mathematics/IntrRay3Capsule3.h​

However, note that this code itself decomposes the problem into two pieces: calculating the time(s) of intersection between the line containing the ray and the capsule, then checking if these times correspond to the segment of the ray you're interested in. (Also the code is a bit hard to follow since it's referencing code in other files).

Anyway, this demonstrates what I was trying to communicate above: there's no simple direct solution to swept-sphere-vs-static-capsule, instead you need to decompose the problem into simpler sub-problems. Another decomposition that works, which I mentioned, is: sweep your sphere vs the spheres at either end of the capsule, and then sweep your sphere vs the cylindrical body of the capsule. The earliest valid time of collision between these three is the moment the sphere touches the capsule. This is less efficient than the geomtools approach, but maybe more intuitively easy to grasp, and also relies on easily-googlable code (eg search “ray vs sphere” (for the sphere-vs-sphere sweeps) and “ray vs cylinder" (for the sphere-vs-cylender sweep)).

raigan said:

So, the problem you're trying to solve is equivalent to: find the time of intersection between a ray and a capsule.

I've read a number of people saying this is the case, but it never made sense to me… until for some reason I just remembered C Ericson talking about swept sphere vs AABB, wherein he simple casts a ray from sphere.position and “expands” the AABB by sphere.radius. Clever man!

So that's what I did: cast a ray at the capsule, but adjust the capsule's radius by +sphere.radius first. And it worked ??

Thanks everyone for your help!

Euthyphro said:

@dp2k No problem. I guess I don't really understand what is going on. If you are doing real-time collision, why would you need to know the time in advance of the collision?

Sorry for the double-post, but to answer your question: it is necessary to know the time of collision in advance for fast-moving objects, such as bullets. A “fast” object in a physics world is one that moves more than its size within a single frame (or physics step).

A specific term for this phenomenon is called “tunneling" and the solution is called “continuous collision detection” which uses ”swept volumes". The Unity docs have an excellent article on this if you want to know more.

Regarding pre-initializing local variables… what you've shown is technically true, however that is not variable initialization, just basic declaration which, as you pointed out, does nothing (the variable is still undefined). A vector class or any other Object (with a capital “O”, not just a primitive object like a number) is rather expensive to initialize/instantiate in both CPU and memory (eg var v = new Vector()). So to avoid GC performance penalties, the vector is initialized outside the function once, and reused within the function from then on. This is basically caching, and a more elaborate implementation of this is called object pooling. It is essential to do this for heavy functions that get called many times per frame.

@dp2k Congratulations on solving the problem, and thanks for the information. I never thought of the performance difference between new and clone/copy before.