27
\$\begingroup\$

If (for the purpose of collision detection) 3D objects are represented in a game by spheres, what is a good algorithm to detect a collision between spheres?

If each object has a position as of the last frame and a new (desired) position, what is a good algorithm that will identify collisions where the spheres didn't intersect in the previous frame, and they may not intersect in the second frame, but they did intersect somewhere in between?

|improve this question
\$\endgroup\$
18
\$\begingroup\$

Basically you're looking for a trace.

This page will probably help you: http://www.realtimerendering.com/intersections.html

Moving Sphere/Sphere: (location) Add the radius of the moving sphere to the static sphere, and treat the moving sphere as a ray. Use this ray to perform ray/sphere intersection. See Gomez; Schroeder for code (article has bug in derivation, code is fine); and RTR2, p. 622.

|improve this answer
\$\endgroup\$
  • 1
    \$\begingroup\$ That doesn't work if both spheres move, (not even if you do it twice). Seems to me that you'd have to first do a distance check between the lines spanning movement a and the one spanning movement b, and if that is less than radius a + radius b you have a possible collision. After that I would do a check to see where that point is in time for sphere a and where for sphere b to see if the times are close. If so I'd check speed against distance in time for that point, if it's still a possible collision I'd do a stepwise refinement. \$\endgroup\$ – Kaj Aug 19 '10 at 7:02
  • 15
    \$\begingroup\$ Actually it does, you just have to make the movement relative. So if both spheres are moving you just subtract the velocity of one of the spheres from both of them so you have one "moving" sphere and one "stationary" sphere. Then you can use the above. \$\endgroup\$ – Tetrad Nov 23 '10 at 17:37
8
\$\begingroup\$

Use a sweep test as demonstrated in this Gamasutra article.

|improve this answer
\$\endgroup\$
4
\$\begingroup\$

Off the top of my head:

  1. Create two line segments from the middle of each circle from where it started to where it moved to in that time step.
  2. Find the min distance between those two line segments; as is explained here.
  3. If that distance is less than or equal to the radius of the first circle plus the second then they collided; otherwise they did not.

And that is all there is to it, I would expect that to be pretty fast.

|improve this answer
\$\endgroup\$
1
\$\begingroup\$

Here's another nice Gamasatura article.

|improve this answer
\$\endgroup\$
  • 1
    \$\begingroup\$ I realize this is 7 years later, but this answer is link only. Fortunately the link is still alive, but if it were not, your answer would...not be an answer. \$\endgroup\$ – Draco18s no longer trusts SE Nov 23 '18 at 4:53
0
\$\begingroup\$

Speaking as someone who's done this: it's not worth the hassle. Unless your game design absolutely needs it, and it almost certainly doesn't, you'll spend far more effort getting sweeping working than you really expect. And it will be slower than you wanted it to be.

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ He could be making a pool game for all you know. \$\endgroup\$ – Kaj Aug 19 '10 at 7:03
  • \$\begingroup\$ If he was making a pool game his "game design absolutely needs it". \$\endgroup\$ – deft_code Nov 24 '10 at 19:11
  • \$\begingroup\$ You are right, don't reinvent the wheel. But just for excersise it may be worth it. \$\endgroup\$ – user712092 Jul 4 '11 at 15:34
  • 4
    \$\begingroup\$ I disagree with direct discouragement as an answer. \$\endgroup\$ – bobobobo Aug 27 '11 at 0:53
  • \$\begingroup\$ I agree with @bobobobo, the question is not if it's worth the hassle or not, a future user that sees this thread might absolutely need the answer no matter the cost. This would be better as a comment. \$\endgroup\$ – TomTsagk Nov 23 '18 at 10:02
0
\$\begingroup\$

There is article about deriving collision detection with math on Flipcode. It has circle-cirle. There is how to detect precisely the point of collision and check if there is a collision at all.

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ I realize this is 7 years later, but this answer is link only. Fortunately the link is still alive, but if it were not, your answer would...not be an answer. \$\endgroup\$ – Draco18s no longer trusts SE Nov 23 '18 at 4:54
0
\$\begingroup\$

Collision detection for moving object is typically called "Swept volume calculation", here are some codes / articles about this subject.

http://www.gpu-voxels.org/demos/ (Demo)

Source code libraries:

https://github.com/fzi-forschungszentrum-informatik/gpu-voxels

https://libigl.github.io/tutorial/#swept-volume

https://github.com/gradientspace/geometry3Sharp

Articles:

http://gamma.cs.unc.edu/SV/sm03.pdf

https://www.cs.columbia.edu/~allen/PAPERS/abrams.swept.pdf (No source code unfortunately)

http://www.realtimerendering.com/intersections.html (Rather heavy collection of links)

|improve this answer
\$\endgroup\$
  • 1
    \$\begingroup\$ Answers that contain only a link (or in this case, several) do not contain an actual answer. You should include the relevant information in your post so that if those links go dead, your post is still understandable. \$\endgroup\$ – Draco18s no longer trusts SE Nov 23 '18 at 4:54
  • \$\begingroup\$ Information behind links slightly better explain than me at the moment. There is also demo videos behind links, which gives some perception about what is happening in real time. \$\endgroup\$ – TarmoPikaro Nov 23 '18 at 5:39
  • 1
    \$\begingroup\$ meta.stackexchange.com/a/8259/313685 \$\endgroup\$ – Draco18s no longer trusts SE Nov 23 '18 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.