title: Collision Detection between Accelerating Spheres
body: <p>I am writing a physics engine/simulator which incorporates 3D space flight, planetary/stellar gravitation, ship thrust and relativistic effects.  So far, it is going very well, however, one thing that I need help with is the math of the collision detection algorithm.</p>
  
  <p>The iterative simulation of movement that I am using is basically as follows:</p>
  
  <p>(Note: 3D Vectors are ALL CAPS.)</p>
  
  <pre><code>For each obj
  
      obj.ACC = Sum(all acceleration influences)
  
      obj.POS = obj.POS + (obj.VEL * dT) + (obj.ACC * dT^2)/2     (*EQ.2*)
  
      obj.VEL = obj.VEL + (obj.ACC * dT)
  
  Next
  </code></pre>
  
  <p>Where:</p>
  
  <pre><code>obj.ACC is the acceleration vector of the object
  obj.POS is the position or location vector of the object
  obj.VEL is the velocity vector of the object
  
  obj.Radius is the radius (scalar) of the object
  
  dT is the time delta or increment
  </code></pre>
  
  <p>What I basically need to do is to find some efficient formula that derives from (<em>EQ.2</em>) above for two objects (obj1, obj2) and tell if they ever collide, and if so, at what time.  I need the exact time both so that I can determine if it is in this particular time increment (because acceleration will be different at different time increments) and also so that I can locate the exact position (which I know how to do, given the time)</p>
  
  <p>For this engine, I am modelling all objects as spheres, all this formula/algorithm needs to do is to figure out at what points:</p>
  
  <pre><code>(obj1.POS - obj2.POS).Distance = (obj1.Radius + obj2.Radius)
  </code></pre>
  
  <p>where .Distance is a positive scalar value.  (You can also square both sides if this is easier, to avoid the square root function implicit in the .Distance calculation).</p>
  
  <p>(yes, I am aware of many, many other collision detection questions, however, their solutions all seem to be very particular to their engine and assumptions, and none appear to match my conditions: 3D, spheres, and acceleration applied within the simulation increments.  Let me know if I am wrong.)</p>
  
  <hr>
  
  <p>Some Clarifications:</p>
  
  <p>1) It is not sufficient for me to check for <em>Intersection</em> of the two spheres before and after the time increment.  In many cases their velocities and position changes will far exceed their radii.</p>
  
  <p>2) RE: efficiency, I do not need help (at this point anyway) with respect to determine likely candidates for collisions, I think that I have that covered.</p>
  
  <hr>
  
  <p>Another clarification, which seems to be coming up a lot:</p>
  
  <p>3) My equation (<em>EQ.2</em>) of incremental movement is a quadratic equation that applies both Velocity <em>and</em> Acceleration:</p>
  
  <pre><code>obj.POS = obj.POS + (obj.VEL * dT) + (obj.ACC * dT^2)/2
  </code></pre>
  
  <p>In the physics engines that I have seen, (and certainly every game engine that I ever heard of) only <em>linear</em> equations of incremental movement that apply <em>only</em> Velocity:</p>
  
  <pre><code>obj.POS = obj.POS + (obj.VEL * dT)
  </code></pre>
  
  <p>This is why I cannot use the commonly published solutions for collision detection found on StackOverflow, on Wikipedia and all over the Web, such as finding the intersection/closest approach of two line segments.  My simulation deals with variable accelerations that are fundamental to the results, so what I need is the intersection/closest approach of two <em>parabolic</em> segments.</p>