title: How can I optimize my basic physics simulator?
body: <p>I've written a simple physics modeler that allows me to bounce balls around the screen.  You can click and drag to launch a ball, or you can generate balls hundreds at a time and watch them interact with each other.</p>
  
  <p><a href="https://i.stack.imgur.com/xRoTW.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/xRoTW.png" alt="alt text"></a><br>
  <a href="http://i43.tinypic.com/j0k67o.png" rel="nofollow noreferrer">[Link to larger version]</a></p>
  
  <p>It has been a fun little program to work on and I want to take it further if I can. I know they say pre-mature optimization is the root of all evil but I'm starting to hit actual performance barriers and I want to know if anyone who is experienced in game/simulator development can help me out.</p>
  
  <p><strong>Problem:</strong></p>
  
  <p>Right now, my program chokes if you add too many balls (it can't seem to handle more than 800 on my machine).  If you do, the simulation is no longer realistic and all the balls overlap each other on the bottom.</p>
  
  <p>The problem is in collision detection.  In the most naive case, collision detection is an O(N^2) problem.  Each ball checks every other ball.  This gets poor performance pretty quickly (after even 100 balls you'll be doing 10k collision checks per loop cycle).</p>
  
  <p>If you look here, you can see a screenshot of where I have added several hundred balls.  The simulator can't keep up and they begin to overlap each other.  </p>
  
  <p><a href="https://i.stack.imgur.com/L8zoE.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/L8zoE.png" alt="alt text"></a><br>
  <a href="http://i39.tinypic.com/2jes2fb.png" rel="nofollow noreferrer">[Link to larger version]</a></p>
  
  <p>Currently, I detect collisions by looking for overlapping balls.  If I find two balls that are overlapping, I separate them by their minimum translation distance (MTD), or push them apart.  I then use a simple physics equation to adjust their impulse vectors and off they go in different directions after the collision.</p>
  
  <p>It works great except if there are too many balls the minimum translation distance becomes noticeable.  They begin overlapping by large amounts and constantly jostle each other on the bottom.  It gets worse the more I increase "gravity".  The pressure on them is increased and the amount they are compressed/overlap each other increases.</p>
  
  <p>Again, I have no issues until I hit a sizable N number of balls.</p>
  
  <p><strong>Current Optimization Method</strong>:  </p>
  
  <p>Collision Detection -<br>
  <em><a href="https://en.wikipedia.org/wiki/Sweep_and_prune" rel="nofollow noreferrer">Sweep and prune</a></em> - (aka. Sort and Sweep)</p>
  
  <p>I use an insertion sort on my balls each loop cycle along their x axis.  Because of the nature of Insertion Sort I can exploit the <a href="https://en.wikipedia.org/wiki/Collision_detection" rel="nofollow noreferrer">temporal coherence</a> of my simulator.  Frame to frame, the balls positions change only slightly so the sort doesn't have much work to do.  This brings Linear Sorts amortized runtime to O(N) or linear rather than its average runtime of O(N^2).  </p>
  
  <p>Since the balls are sorted, I do a couple pre-checks in my second loop before checking collisions.  Now I only have to check the balls near each other (because they are sorted along the x-axis), and I break out of the second loop anytime I check a ball against another ball whose xmin is greater than the xmax of the current ball.  So it skips thousands of checks.</p>
  
  <p>When I implemented this, it brought a huge speed improvement.  However, I would still like to be able to handle more than 600-800 balls. I've read about Physics Engines that easily handle collision detection between 10k objects simultaneously, so I would like to think I could reach 1-2k with a little work.</p>
  
  <p>After running a <em>profiler</em> it came out that Collision Detection was eating up about 55% of my time while rendering was eating up about 45%.  So, these are my two most expensive costs.  </p>
  
  <hr>
  
  <p><em>Question:</em></p>
  
  <p><strong>Can you think of any better algorithms or techniques that would allow my simulator to be able to handle more balls?</strong></p>
  
  <hr>
  
  <p>Relevant Code:  </p>
  
  <p><strong>Entire Project:</strong> </p>
  
  <blockquote>
    <p>svn checkout <a href="http://simucal-projects.googlecode.com/svn/ballbounce/trunk/" rel="nofollow noreferrer">http://simucal-projects.googlecode.com/svn/ballbounce/trunk/</a>  </p>
  </blockquote>
  
  <p>or, click <a href="https://web.archive.org/web/20140916104935/http://simucal-projects.googlecode.com/svn/ballbounce/trunk/" rel="nofollow noreferrer">here</a> to browse the files manually in your browser.</p>
  
  <p><strong>Sections of Interest:</strong></p>
  
  <ul>
  <li><a href="https://pastebin.com/f1163dfa6" rel="nofollow noreferrer">Pastebin: checkCollisions()</a> - w/ Sweep and Prune  </li>
  <li><a href="https://pastebin.com/f76b6f565" rel="nofollow noreferrer">Pastebin: resolveCollision()</a> - Expensive true collision check and resolution if still not removed by Sweep and Prune.</li>
  <li><a href="https://pastebin.com/f2598b49" rel="nofollow noreferrer">Pastebin: render()</a> - Rendering alone eats up about 45% of my time.</li>
  </ul>
  
  <pre><code>
  </code></pre>