28
\$\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\$
2
  • \$\begingroup\$ There is [article about deriving collision detection with math on Flipcode][1]. It has circle-cirle. There is how to detect precisely the point of collision and check if there is a collision at all. [1]:flipcode.com/archives/… \$\endgroup\$
    – user712092
    Jul 4, 2011 at 15:39
  • \$\begingroup\$ Here's another nice Gamasatura article. \$\endgroup\$
    – Mateen Ulhaq
    Aug 27, 2011 at 0:35

6 Answers 6

Reset to default
19
\$\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\$
2
  • 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, 2010 at 7:02
  • 18
    \$\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, 2010 at 17:37
8
\$\begingroup\$

Use a sweep test as demonstrated in this Gamasutra article. (Or the port to gamedeveloper.com...)

Improve this answer
\$\endgroup\$
5
\$\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\$
3
\$\begingroup\$

Answers here well explained the concept, but seems code answer was not posted yet:

// predicts collision time between two moving objects
// objects are spheres moving in 3D space with constant velocities
// returns PositiveInfinity if collision will never happen

float GetCollisionTime(WorldObject a, WorldObject b)
    {
    // relative velocity and position
    var rel_v = a.Velocity - b.Velocity;
    var rel_pos = a.Position - b.Position;

    float start_dist_squared = rel_pos.LengthSquared();
    double need_dist_squared = M.Pow(a.Radius + b.Radius, 2);

    // skip if already collide
    if (start_dist_squared <= need_dist_squared)
        return 0;

    float rel_dot = Vector3.Dot(rel_pos, rel_v);
    float rel_v_squared = rel_v.LengthSquared();

    // skip if they move away
    if (rel_dot > 0 || rel_v_squared == 0)
        return float.PositiveInfinity;

    float min_dist_t = -rel_dot / rel_v_squared;
    float min_dist_squared = (rel_pos + rel_v * min_dist_t).LengthSquared();

    // skip if they never touch
    if (min_dist_squared > need_dist_squared)
        return float.PositiveInfinity;

    double collide_dist_to_min_squared = need_dist_squared - min_dist_squared;
    float collide_t_before_min = (float)M.Sqrt(collide_dist_to_min_squared / rel_v_squared);

    return min_dist_t - collide_t_before_min;
    }

Squared distances are used only to optimize out slow root calculations.

Improve this answer
\$\endgroup\$
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\$
3
  • 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, 2018 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, 2018 at 5:39
  • 1
    \$\begingroup\$ meta.stackexchange.com/a/8259/313685 \$\endgroup\$
    – Draco18s no longer trusts SE
    Nov 23, 2018 at 14:27
-3
\$\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\$
5
  • 1
    \$\begingroup\$ He could be making a pool game for all you know. \$\endgroup\$
    – Kaj
    Aug 19, 2010 at 7:03
  • 1
    \$\begingroup\$ If he was making a pool game his "game design absolutely needs it". \$\endgroup\$
    – deft_code
    Nov 24, 2010 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, 2011 at 15:34
  • 6
    \$\begingroup\$ I disagree with direct discouragement as an answer. \$\endgroup\$
    – bobobobo
    Aug 27, 2011 at 0:53
  • 1
    \$\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\$
    – Tom Tsagkatos
    Nov 23, 2018 at 10:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .