Databases
StackOverflow2013
Postsdbo
POHow can I optimize my basic physics simulator?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow can I optimize my basic physics simulator?
    primarykey
    data
    text
    <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 eachother.</p> <p><a href="http://i41.tinypic.com/2zr0oic.png" rel="noreferrer">alt text http://i41.tinypic.com/2zr0oic.png</a><br> <a href="http://i43.tinypic.com/j0k67o.png" rel="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="http://i41.tinypic.com/2nsnuqd.png" rel="noreferrer">alt text http://i41.tinypic.com/2nsnuqd.png</a><br> <a href="http://i39.tinypic.com/2jes2fb.png" rel="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 eachother 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="http://en.wikipedia.org/wiki/Sweep_and_prune" rel="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="http://en.wikipedia.org/wiki/Collision_detection#Exploiting_temporal_coherence" rel="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="noreferrer">http://simucal-projects.googlecode.com/svn/ballbounce/trunk/</a> </p> </blockquote> <p>or, click <a href="http://simucal-projects.googlecode.com/svn/ballbounce/trunk/" rel="noreferrer">here</a> to browse the files manually in your browser.</p> <p><strong>Sections of Interest:</strong></p> <ul> <li><a href="http://pastebin.com/f1163dfa6" rel="noreferrer">Pastebin: checkCollisions()</a> - w/ Sweep and Prune </li> <li><a href="http://pastebin.com/f76b6f565" rel="noreferrer">Pastebin: resolveCollision()</a> - Expensive true collision check and resolution if still not removed by Sweep and Prune.</li> <li><a href="http://pastebin.com/f2598b49" rel="noreferrer">Pastebin: render()</a> - Rendering alone eats up about 45% of my time.</li> </ul>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USmmcdole
    1. USmmcdole
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHow can I optimize my basic physics simulator?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POHow can I optimize my basic physics simulator?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POHow can I optimize my basic physics simulator?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COHow much of the work is used for drawing the balls?
      singulars
      1. POHow can I optimize my basic physics simulator?
      1. USGeorg Schölly
    2. CO@gs, about 45% based off some profiling I did. A lot.
      singulars
      1. POHow can I optimize my basic physics simulator?
      1. USmmcdole
    3. COI'm not writing .Net code, so I can't help much. But there are certainly many improvements possible. Antialiasing off / drawing all circles at the same time…
      singulars
      1. POHow can I optimize my basic physics simulator?
      1. USGeorg Schölly
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload