The reason I'm asking is because I'm wondering if it's worth my time to write a little tutorial on how to do it. When I was making my game Anacondzor, I needed to do swept-sphere vs line-segment intersection testing. I googled and googled but couldn't find anything that helped me. The best I came across was doing a capsule vs line-segment intersection test (by using two circles and a box to build the capsule), but I found that cumbersome, plus it didn't tell me at what time the sphere and line started to intersect (which is what I really needed). I found a way to do test swept-spheres vs infinite-lines, but I needed line-segments. So I decided to do the swept-sphere vs infinite-line test with some extra testing to turn it into a swept-sphere vs line-segment test. Anyway, it works quite well for me and was thinking of writing a little tutorial on it to help others who might need to do swept-sphere vs line-segments tests, but before I invest any of my time I want to see if perhaps I missed an obvious, already well-known way to do this. So, are there any swept-sphere vs line-segment intersection test algorithms that you know of, or should I go ahead and write my humble tutorial?

Do you mean circle to line-segment? Your game looked 2D?

These might be useful. It's my 2D intersection library.
C++ Version
C# Version (probably not optimized)

In order to do a translating circle to static line segment test you simply treat the circle as a point p. Then translate the static line along it's normal the radius of the circle. You then perform a line-segment intersection to line-segment intersection test using p to (p + velocity) and translatedVertex1 to translatedVertex2. This will give you the collision point. Calculate the distance from point p and divide by the magnitude of the velocity to get the time T.

If you indeed meant sphere to line-segment then the idea is actually similar (maybe. I don't do 3D normally).

its not how, its where... I do it in math and physics forum... [grin]

What is your intersection test for? If it is for bullet vs sphere, then you can simply find relative velocity first and do sphere vs line segment.

Also, finding collision time is more than just intersection test.


If you really need swept sphere vs line segment: let sphere is swept from A to B and line segment is between C and D .
There can be two cases: sphere collides with line (part of segment) and sphere collides with one of ends of line segment.

Solve for distance between sphere centre and line equating radius squared:
((C-P)x(D-C))^2/(D-C)^2 = r^2
where P=A+(B-A)*t (and x is cross product, not x coordinate)
solving:
((C-P)x(D-C))^2 = r^2 * (D-C)^2
let q=r^2 * (D-C)^2
let H=(D-C)
((C-A+(B-A)*t)xH)^2 = q

cross product is distributive over addition and subtraction and compatible with scalar multiply:
( CxH-AxH+((B-A)xH)*t )^2 = q

'squaring' a vector (finding square magnitude) is a dot product with itself:
(CxH-AxH+((B-A)xH)*t).(CxH-AxH+((B-A)xH)*t) = q

grouping (CxH-AxH) and expanding:
((C-A)xH)^2 + 2*( ((C-A)xH).((B-A)xH) )*t + ((B-A)xH)^2*t^2 = q

now just plug values into quadratic formula to solve for values of t.

Check the swept-sphere to line intersections for validity ( see if closest point is on the segment for intersection). If it is, then theres collision with sphere touching the segment somewhere between ends.
Else, check for collision between sphere and endpoints of line segment
Do sphere vs segment intersection for sphere centred at zero and segment (C-A , C-B) , and segment (D-A , D-B) . Choose smallest collision t (if exists)

(note: above equations are totally untested, but unless there is typos, them work.)

Quote: Original post by Sirisian
Do you mean circle to line-segment?

[...]

In order to do a translating circle to static line segment test you simply treat the circle as a point p. Then translate the static line along it's normal the radius of the circle. You then perform a line-segment intersection to line-segment intersection test using p to (p + velocity) and translatedVertex1 to translatedVertex2. This will give you the collision point. Calculate the distance from point p and divide by the magnitude of the velocity to get the time T.

No, I mean swept-sphere(or swept-circle, it's pretty much the same in most cases) to line-segment. The sweeping is necessary. That's a really interesting algorithm there though. You'd still have to test the circle/sphere against the line's endpoints and make sure that you translated the line in the correct direction, and I don't know how well it would do in 3D, but I quite like it.

Quote: Original post by Dmytry
its not how, its where... I do it in math and physics forum... [grin]

Yeah, I thought about posting it there, but I'm not really asking for help on how to do it, rather I'm asking the question: "was I just retarded when I needed to find how to do a swept-circle vs line segment test for my game and couldn't find any tips anywhere?" [smile] I'll remember that though next time I might have a similar question.

Quote: Original post by Dmytry
***snip out the equations***

That's how I was doing it, more or less. First I'd sweep the sphere against the end points of the line. Then I'd sweep the sphere against the infinite line, and when it intersected the line, I'd make sure it was actually intersecting the line segment by constructing a new line (parallel to the line segment's normal) with a length twice the radius of the sphere, and seeing if that new line segment intersected the original line segment. Then I'd take the smallest time that these three tests returned (or I'd throw out the times from tests that returned false) and use this as my intersection time.

So it's starting to look like I must have missed something obvious when I was looking for a way to do this, so I guess I won't write a tutorial if it's just redundant. Thanks!

Exactly how much information about the intersection do you need? If you just want a binary yes/no answer then I'd probably turn the swept circle into a line segment, then find the distance between the two line segments and compare against the radius.

However if you need extra information like the exact point of intersection I'm not sure if this approach would still be useful.