{"id":16210,"date":"2012-06-10T15:02:31","date_gmt":"2012-06-10T20:02:31","guid":{"rendered":"http:\/\/www.shamusyoung.com\/twentysidedtale\/?p=16210"},"modified":"2012-06-10T22:02:16","modified_gmt":"2012-06-11T03:02:16","slug":"physics-engine","status":"publish","type":"post","link":"https:\/\/www.shamusyoung.com\/twentysidedtale\/?p=16210","title":{"rendered":"Physics Engine"},"content":{"rendered":"<p>When I do the &#8220;ask me a question&#8221; things, I generally stick to questions I can actually answer. But in this case I think what the curious person is looking for is a rough overview, not a detailed <a href=\"http:\/\/en.wikipedia.org\/wiki\/White_paper\">white paper<\/a>. This being the case, I think I can help. As always, remember that my understanding is probably a few years out of date. <\/p>\n<p>Reader Kronski asks:<\/p>\n<blockquote><p>I don&#39;t know if you&#39;ve seen <a href=\"http:\/\/www.youtube.com\/watch?v=KppTmsNFneg\">this video<\/a>.<\/p>\n<p>It&#39;s demonstration of a physics engine where a truck gets banged up all to hell. My question is, how does a physics engine like this work?\n<\/p><\/blockquote>\n<p>So you don&#8217;t have to head over to YouTube, the video in question is this one:<\/p>\n<p><table class='nomargin' cellspacing='0' width='100%' cellpadding='0' align='center' border='0'><tr><td><iframe loading=\"lazy\" width=\"1024\" height=\"576\" src=\"https:\/\/www.youtube.com\/embed\/KppTmsNFneg\" frameborder=\"0\" allowfullscreen class=\"embed\"><\/iframe><br\/><small><a href='http:\/\/www.youtube.com\/watch?v=KppTmsNFneg'>Link (YouTube)<\/a><\/small><\/td><\/tr><\/table><\/p>\n<p>The basics of a physics engine are easy to grasp.  The finer details are beyond me.  Let&#8217;s start with the essentials. You can see the ultimate demonstration of basic physics at work in the <a href=\"http:\/\/www.bridgebuilder-game.com\/bb-info.php\">bridge builder game<\/a>.<\/p>\n<p>The idea is pretty simple: It&#8217;s a simulation of points in space. You have a bunch of points and you subject them to gravity and collision.  The trick is that you link the points together. Let me swipe a screen shot from the bridge game:<\/p>\n<p><!--more--><table   class=\"\" cellpadding='0' cellspacing='0' border='0' align='center'><tr><td><img src='https:\/\/www.shamusyoung.com\/twentysidedtale\/images\/physics1.jpg' class='insetimage'   alt='physics1.jpg' title='physics1.jpg'\/><\/td><\/tr><\/table><\/p>\n<p>The goal is to subject the points to gravity and collision, with the requirement that <em>all of the lines between them remain the same length<\/em>.  Now, you can&#8217;t insist that all lines remain exactly the same length. Simple rounding errors and limits on precision make that impossible, or at least a pain in the ass to code. If you try to make the links 100% rigid then you&#8217;ll end up with all sorts of nonsense behavior, division by zero problems, or other unwanted side-effects.<\/p>\n<p>So what you do is you make each line have a <em>desired<\/em> length. The more it deviates from that length, the harder it will push to return to the desired size. Internally, this is a multi-pass excercise:<\/p>\n<ol>\n<li>Gravity and momentum.  Look at each point, see if it&#8217;s moving and how fast, and have it try to maintain that speed, as objects in motion tend to do. Also inflict gravity on it.  Again, we&#8217;re just doing this to points and ignoring the lines for now.\n<\/li>\n<li>Do collision.  Keep the points from going through things. If a falling point hits the ground, make it stop.<\/li>\n<li>Pass over the simulation on a per-line basis. Have each line try to correct its length. If it&#8217;s too long, it will pull its two endpoints together, and if it&#8217;s being crushed or compressed it will try to push them apart. Don&#8217;t apply these changes right away.  Save them until you&#8217;re done processing all lines. <\/li>\n<li>Take all of the &#8220;corrections&#8221; generated in the previous step and apply it to your points.  For example check out the top-most point of the bridge in the screenshot above.  Gravity will pull it down a bit, moving it closer to the three points to which it&#8217;s joined. Those three lines will push back, holding the top-most point up but also pushing down on the lower points, thus letting the &#8220;weight&#8221; of the upper point rest on them. <\/li>\n<li>Now, in a perfect world you&#8217;d be done at this point.  But here we have the thorny problem that maybe some of those corrections we just applied have created a need for more collision detection.  Points may have been shoved into the ground, for example.  We can do another round of collision if we want, which will lift those points out of the ground.  But doing this will create a need for us to go back and process all the lines again, which might push points into the ground, which&#8230;\n<p>We could be here all freakin&#8217; day, is what I&#8217;m saying. How you handle this very much depends on what&#8217;s important to your simulation and how much you value the speed vs. accuracy tradeoff.  Right here is generally where things seem to get kind of glitchy.  If you&#8217;ve ever stepped out of your car in Saints Row The Third and saw your tire was half-buried in the street and was jittering up and down in an attempt to dislodge itself, then you were probably seeing a problem with this part of the simulation.<\/p>\n<\/li>\n<\/ol>\n<p><table   class=\"\" cellpadding='0' cellspacing='0' border='0' align='center'><tr><td><img src='https:\/\/www.shamusyoung.com\/twentysidedtale\/images\/physics2.jpg' class='insetimage'   alt='physics2.jpg' title='physics2.jpg'\/><\/td><\/tr><\/table><\/p>\n<p>Ignoring this thorny issue, we now have everything required to make our own bridge builder game.  That&#8217;s it. Everything else: Sagging, balance, center of gravity, weight distribution&#8230; it&#8217;s all emergent. Following these simple rules will make it possible to build a lopsided tower and have it fall over as expected. It&#8217;s actually kind of beautiful how such simplicity can create such a robust set of behaviors.<\/p>\n<p>However, this presents the programmer with a bit of a trap.  They see these simple rules and how amazing the results are, and they assume that just a few more rules can yield even more amazing results.  (And to be fair, in a AAA game you would need a bit more than this.  In the system I&#8217;ve outlined, all points weigh the same, which can lead to undesirable outcomes. Also, collision is a bit more complicated in a real game environment, but I&#8217;m trying to keep this simple.) And so the hapless coder blunders into the dangerous waters of <a href=\"?p=1200\">oversimulation<\/a>.<\/p>\n<p>At any rate, everything we&#8217;re doing can be applied to 3D just as easily as 2D. So now we have the makings of a physics engine. This is probably not the only approach, but it&#8217;s the one I&#8217;m familiar with.<\/p>\n<p>How much &#8220;play&#8221; your lines have in them will determine how our physics object behaves.  If the lines try to stay as close to their desired length as possible, then you&#8217;ll have a very rigid object.  If the lines don&#8217;t start pushing back until they&#8217;re far from the original size, then your object will be very rubbery.  If lines resist stretching but ignore compression, then you&#8217;ll have something that behaves like it&#8217;s made out of rope.  If you have lines that are rigid until they undergo enough compressing force, after which they will compress and then treat their new, smaller size as the new &#8220;proper&#8221; size, then you will have an object that can be crumpled up like a soda can.<\/p>\n<p>For making objects move in a game, an artist usually creates the visible model.  This is then joined to our scaffolding of physics points and lines.  Similar to how a 3D character model will be animated by a skeleton, our model will move according to what the physics object is doing. <\/p>\n<p>As always, there&#8217;s a trade-off at work here. You can make a simple eight-cornered cube and make that the physics model for the entire pickup truck.  The result will not be particularly convincing.  If you want a good simulation then you&#8217;ll make the body of the physics model out of many, many points. You&#8217;ll use very rigid links for most of the body, and more &#8220;rubbery&#8221; ones for the link between the car body and the axle. (Or the wheels. Depends on how meticulous you are about your car simulation.  The fidelity requirements of Gran Turismo are obviously very different from, say, Burnout.) Do this right and you&#8217;ll have a working suspension system and you&#8217;ll be able to see the car rock and shift as it corners and brakes.  However, the more points and lines you use, the more CPU power you need.  <\/p>\n<p>As for making the body of the visible model crumple up like that? How does it know when to crumple up the fenders, when to shear them off, or when to have them detach entirely? <\/p>\n<p>I have no idea.  I mean, I could take a guess and muse over how I&#8217;d research such a problem, but it would be all conjecture and hard for me to relate in non-technical terms. And above all, it would probably be wrong.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>When I do the &#8220;ask me a question&#8221; things, I generally stick to questions I can actually answer. But in this case I think what the curious person is looking for is a rough overview, not a detailed white paper. This being the case, I think I can help. As always, remember that my understanding [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[66],"tags":[],"class_list":["post-16210","post","type-post","status-publish","format-standard","hentry","category-programming"],"_links":{"self":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/16210","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=16210"}],"version-history":[{"count":0,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/16210\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=16210"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=16210"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=16210"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}