Swept Sphere / Bounding Box Collision

[3dben]

Can anyone point me to some working code to test for a swept sphere/bounding box intersections? Im doing this in 2D but welcome 3D algo's.

Thanks.

-=ben

[PoV]

I tend to hate the Morgan Kaufmann series of books, but there is one great book in the series on collision detection.

http://www.amazon.com/exec/obidos/tg/detail/-/1558607323/qid=1123791647/sr=8-1/ref=pd_bbs_1/103-6648471-1027030?v=glance&s=books&n=507846

Page 228 (Section 5.5.7) has the code and some decent documentation, but it relies on a number of other testing functions developed in the book. If you're doing a much collision/physics stuffs, I seriously suggest nabbing this one, the big orange hard cover book. :D

[digriz]

I can recommend a good book

Real Time Collision detection (http://www.bookpool.com/sm/1558607323)

EDIT: Doh! pipped to the post.

[Bad Sector]

Can anyone point me to some working code to test for a swept sphere/bounding box intersections? Im doing this in 2D but welcome 3D algo's.

I didn't understood this: you want collision detection for sphere-to-sphere or sphere-to-boundingbox (and if it's the second, what kind of bounding box? axis-aligned or oriented?)

[PoV]

A "swept sphere" is a shape also called a capsule, which looks like a cylinder with rounded ends. It's commonly defined by a line segment and a radius.

Likely, he's trying to test a sphere in motion, which creates the shape of a capsule as it moves from point A to point B.

[Bad Sector]

@PoV:
i know that :-P what i don't understand if he wants to test the (swept) sphere A against another (swept) sphere B or against another bounding box B.

[PoV]

Ah. I see your point.

[iopred]

I've seen implementations whereby the swept circle is actually represented by two circles, and a rotated rectangle.

2 CirclevsRectangles, and a RectanglevsRectangle is much easier than developing a crazy new algorithm.

Not sure on the speed of implementation tho, cant say I see it being that bad, as in best case scenario, you only have to check one of the shapes.

It doesnt work so well in 3d, as you need 2 Spheres and a Cylinder

[Bad Sector]

You cannot express mathematically a swept sphere with a single formula, so you have to break it in more primitive volumes.

My idea is to use two spheres and a line segment to check for a sweptsphere-to-sphere collision detection (since you move only one sphere per time - not two at the same time). In very brief the process is like:

1. check the distance between the static sphere's center and the (infinite) line. If it's greater than the sum of the static sphere's and the sweptsphere's radii then forget it; they don't collide :-)
2. check the distance between each sphere in the sweptsphere and the static sphere. If it's less or equal than the same sum as in 1 then they do collide at in that point you may want to get the first hit point.
3. if the sum is greater, then project the static sphere's center to the (infinite) line and check if the point is inside the line segment that defines the sweptsphere (made by the centers of the two spheres of the sweptsphere). If it is outside then they don't collide.
4. if it is inside, then check the distance between the projected point and the static sphere's center; if it is less or equal than the sum in 1, then they do collide and you can get the first hit point there.

Getting the first hit point (the point where the sweptsphere and the static sphere first touch each other):
a. For case 2, the hit point is a vector from the center of the sphere in sweptsphere that touched the static sphere to the center of the static sphere and has the same length as the radius of the sweptsphere.
b. For case 4, the hit point is a vector from the projected point to the center of the static sphere and has the same length as the radius of the sweptsphere.

The vector in "a" and "b" is

V = |P - C| * r;


where V is the vector, P is the projected point for case b or the center of the sphere in sweptsphere's radius, C is the static sphere's center and r is the sweptsphere's radius.

Once you have that you may also want to have a nice response, but that's a whole new thing and since you didn't asked... :D

If you need more information, just ask.

[Robert Cummings]

T2D approaches swept collisions with a convex poly method (yes even for spheres and rects) - you should do the same, life is much simpler :)

[Bad Sector]

this sounds slow

and checking if two convex polygons intersect is not as trivial

(well, of course in the 2D domain things are much simpler)

[3dben]

Thanks for the feedback thus far. Let me clarify, I need a good 2D test for testing a moving sphere with a moving AABB. I have one for two moving AABB's which I might end up using and then test the radius for the collision point if one occured. However I wanted to see if there was something specifcally built for what I need that might be more effiecient.

Thanks.

-=ben