Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question

6 Answers 6

up vote 16 down vote accepted

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.

share|improve this answer
1  
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. –  Kaj Aug 19 '10 at 7:02
14  
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. –  Tetrad Nov 23 '10 at 17:37

Use a sweep test as demonstrated in this Gamasutra article.

share|improve this answer

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.

share|improve this answer

Here's another nice Gamasatura article.

share|improve this answer

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.

share|improve this answer
    
He could be making a pool game for all you know. –  Kaj Aug 19 '10 at 7:03
    
If he was making a pool game his "game design absolutely needs it". –  deft_code Nov 24 '10 at 19:11
    
You are right, don't reinvent the wheel. But just for excersise it may be worth it. –  user712092 Jul 4 '11 at 15:34
1  
I disagree with direct discouragement as an answer. –  bobobobo Aug 27 '11 at 0:53

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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