{"id":3166,"date":"2009-04-30T08:00:19","date_gmt":"2009-04-30T12:00:19","guid":{"rendered":"http:\/\/www.shamusyoung.com\/twentysidedtale\/?p=3166"},"modified":"2010-10-24T08:05:57","modified_gmt":"2010-10-24T13:05:57","slug":"procedural-city-part-10-more-performance","status":"publish","type":"post","link":"https:\/\/www.shamusyoung.com\/twentysidedtale\/?p=3166","title":{"rendered":"Procedural City, Part 10: More Performance"},"content":{"rendered":"<p><span class=\"date\">More Performance Enhancements<\/span><\/p>\n<ul>\n<li>I put more blank space between the buildings, gave the existing buildings a slightly larger footprint, and made the streets wider. Surprisingly, this ended up cutting about 25% of the buildings in the scene, which actually looked <em>better<\/em>.\n<\/li>\n<li>I merged the individual street lights into strips, like Christmas lights.  This means all the lights on the same side of the street are actually one big polygon.  This means streetlights look goofy if you get too low, but eliminated thousands and thousands of polygons from the scene. I doubt I&#8217;ll ever be really happy with how the streets look, but I think I at least have it to the point where I can live with it.\n<\/li>\n<li>I added a widescreen \/ letterbox mode where the drawn area will only take up part of the screen space. This saved a not-at-all-impressive 2fps on my machine, but I&#8217;m hoping it will make the thing run better on low-end graphics cards.  Users with fill-rate problems should see improvement when they use it.\n<\/li>\n<li>I limit the cars to ten updates per second.  The car movement code is fairly cheap, but there will potentially be a lot of cars in the scene and after few hundred iterations it starts to add up.  Limiting the cars to 10fps means that their movement would look a bit stuttering up close.  But since they creep along far away from the camera, there is no reason to waste time calculating each and every tiny little movement, most of which will be too minute to be visible to the user.<\/li>\n<li>Cars are limited in how far away you can see them.  After a car gets a certain distance from the camera, it&#8217;s taken out of play and dropped somewhere into the visible area in front of the camera.  This keeps the apparent car density high.\n<\/li>\n<li>Related to the above, the &#8220;distance&#8221; of the car is calculated in manhattan units.  (I can&#8217;t find a definition of manhattan units anywhere online.  I know I&#8217;m not the only person to use this term.  I wonder what other people call it?)  MU are a distance check that involves calculating the distance between A and B by simply adding the horizontal and vertical offset. If you&#8217;re a kilometer east and a kilometer south, then you&#8217;d walk about 1.4 kilometers on the diagonal but you&#8217;re 2 kilometers away in manhattan units. A <em>real<\/em> distance check calculates how from from A to B if you were flying.  A manhattan check (do you still capitalize it when it&#8217;s the name of a unit and not a place?) figures out how far you would travel if you went from A to B by traveling only along one axis at a time.  A real distance check requires two multiply operations, an add operation, and then a square root.  Manhattan units require a simple addition operation.  Using MU for visibility means that you can see farther looking down a grid-aligned street than you can by looking diagonally over the city.  But this is ideal, since buildings are usually blocking the diagonal view.  The cases where the user might see through a gap in the buildings several diagonal blocks away are rare and fleeting, and the user is not likely to notice a lack of cars.  The performance boost from this is probably too small to measure, but I loved finding a case where I could shamelessly cut corners with no perceptible loss in quality.\n<\/li>\n<li>I fixed a bug where I was rendering all of the black flat-color stuff <em>twice<\/em>. I was rendering it once with the rest of a building, and with a texture on it.  (Although since I wasn&#8217;t setting texture coordinates, it was just taking a single pixel and smearing it all over the object.)  So it was being drawn once with a pure black section of a texture covering it, and then drawn again later as black polygons with no texture.  I&#8217;m sure I don&#8217;t have to explain why this mistake wasn&#8217;t visible while the program was running.\n<\/li>\n<\/ul>\n<p>The final tally: The program is taking up my entire 1920&#215;1200 desktop and runs at over 200fps. It goes down to ~90 when bloom lighting is on and becomes very fill-rate sensitive (finally! it&#8217;s nice to know the GPU has some sort of limits) but I&#8217;m happy enough with performance now.  <\/p>\n<p>The biggest drain on performance now is bloom lighting, which is optional. I can really make bloom work twice as fast, but make it look a little less appealing.  In fact, it&#8217;s only now that I&#8217;m questioning if I&#8217;m doing bloom &#8220;right&#8221;.<\/p>\n<p><span class=\"date\">A Bit About Bloom<\/span><\/p>\n<p>I&#8217;ve never looked up how other programs generate bloom lighting.  I saw bloom in action for the first time when I played <a href=\"?p=1607\">Deus Ex 2<\/a>. I looked at the blobby artifacts it created and made some assumptions about how it was done. Here is how I thought I worked:<\/p>\n<p>(Note that the example bloom I&#8217;m using here is a simulated effect, generated in Paint Shop Pro. The artifact I want to show you is really visible in motion, but actually kind of subtle in a still frame, so I&#8217;m exaggerating the effect for demonstration purposes.)<\/p>\n<p>This is the full view of the scene at a given instant during the run of the program:<\/p>\n<p><table width='600'  cellpadding='0' cellspacing='0' border='0' align='center'><tr><td><img src='https:\/\/www.shamusyoung.com\/twentysidedtale\/images\/pixelcity_bloom1.jpg' class='insetimage' width='600' alt='The city, without bloom.' title='The city, without bloom.'\/><\/td><\/tr><tr><td class='insetcaption'>The city, without bloom.<\/td><\/tr><\/table><\/p>\n<p>But before I render that, I render a lower-resolution version of the scene into a texture:<\/p>\n<p><table width='600'  cellpadding='0' cellspacing='0' border='0' align='center'><tr><td><img src='https:\/\/www.shamusyoung.com\/twentysidedtale\/images\/pixelcity_bloom2.jpg' class='insetimage' width='600' alt='The bloom buffer, if you will. It&#8217;s actually not THIS pixelated, but you get the idea.' title='The bloom buffer, if you will. It&#8217;s actually not THIS pixelated, but you get the idea.'\/><\/td><\/tr><tr><td class='insetcaption'>The bloom buffer, if you will. It&#8217;s actually not THIS pixelated, but you get the idea.<\/td><\/tr><\/table><\/p>\n<p>After I have a low-res version of the scene saved in a little texture, I render the real, full screen deal for the viewer. (The first image.)  Once I have that rendered, I take the pixelated bloom buffer and blend it with the scene using a &#8220;brighten filter&#8221;. People using Photoshop call it the &#8220;Screen&#8221; effect, I believe.  OpenGL programmers call it <tt>glBlendFunc (GL_ONE, GL_ONE);<\/tt>. <\/p>\n<p><table width='600'  cellpadding='0' cellspacing='0' border='0' align='center'><tr><td><img src='https:\/\/www.shamusyoung.com\/twentysidedtale\/images\/pixelcity_bloom3.jpg' class='insetimage' width='600' alt='Split image.  On the left side, the bloom is pixelated.  On the right, it&#8217;s smooth.' title='Split image.  On the left side, the bloom is pixelated.  On the right, it&#8217;s smooth.'\/><\/td><\/tr><tr><td class='insetcaption'>Split image.  On the left side, the bloom is pixelated.  On the right, it&#8217;s smooth.<\/td><\/tr><\/table><\/p>\n<p>What you end up with is the left half of the above image: big glowy <em>rectangles<\/em> over bright areas of the scene, instead of blurry circular blobs of light.  Again, it looks fine in stillframe, but when the camera is flying around the scene the rectangles tend to stick out.  <\/p>\n<p>But you can soften the rectangles out by rendering the bloom layer more than once, and displacing it slightly each time.  This fuzzes out the edges of the rectangle and gives it the dreamy glow I want.  It also means blending a huge, screen-covering polygon multiple times.  As I mentioned in my previous post, blending is (or can be) slow. <\/p>\n<p>Is this how games do bloom?  I don&#8217;t know. (Actually, modern games will invariably be using pixel shaders to achieve this effect, which will be faster and probably let them soften those edges in a single draw.  But I&#8217;m bull-headed and insist on building this thing using stone knives and bearskins.) At any rate, there is an annoying but unsurprising trade off between performance and quality going on here, and the &#8220;sweet spot&#8221; between the two is <em>guaranteed<\/em> to be very different for different hardware. Bloom way well be unusably slow just two GPU generations ago.  All I can do is give users a way to turn it off and see how it goes. <\/p>\n<p><span class=\"date\">Feedback &#038; Performance Suggestions<\/span><\/p>\n<p>Some people made some great suggestions on how the program could be further sped up.  The use of vertex buffers was suggested.  A vertex buffer lets the program gather up all of the geometry in the world  and stick it right on the graphics card. (Assuming the graphics card has the memory for it, which isn&#8217;t a problem in my case.) This would eliminate the most expensive thing my program has to do, which is shoveling geometry to the GPU as fast as it can.  However, I&#8217;m pretty sure integrated graphics cards don&#8217;t support them.  (Actually, data on what hardware supports them and what doesn&#8217;t is as scarce as copies of Duke Nukem Forever.)  Since I can&#8217;t count on all users having VB support, I&#8217;d have to use two rendering paths:  The one I have now for people with low-end hardware, and the super-duper fast one for people with newer hardware.  This means people with great hardware will go even <em>faster still<\/em>, and people with lower hardware will have no benefit.  Adding a bunch of code to push my framerate up to 500fps while doing nothing to help the guy chugging along at 20fps is a brilliant way to expend effort in such a way so as to not benefit anyone.  So let&#8217;s skip that. (This is assuming I&#8217;m right that there are computers less than five years old that don&#8217;t support VB&#8217;s.)<\/p>\n<p>Someone else suggested that a <a href=\"http:\/\/en.wikipedia.org\/wiki\/Quadtree\">quadtree<\/a> would be an ideal way to handle the culling I was doing in my last post.  It&#8217;s tempting, but that would be a lot of work and I&#8217;ve already hit my vaguely defined goal.  <\/p>\n<p>I know I promised a wrap-up to this series this week, but <a href=\"?p=3196\">the tiresome impositions of my mortal form<\/a> have frustrated my progress. <small>Also I played a bunch of Left 4 Dead.<\/small> But I am actually done working on the thing.  I just need to write about the final steps and release it. My plan is to release it two ways:<\/p>\n<p>1) The source and project files, so others may tinker or point and laugh.<br \/>\n2) As a Windows screensaver.<\/p>\n<p>Next time: Finishing touches.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>More Performance Enhancements I put more blank space between the buildings, gave the existing buildings a slightly larger footprint, and made the streets wider. Surprisingly, this ended up cutting about 25% of the buildings in the scene, which actually looked better. I merged the individual street lights into strips, like Christmas lights. This means all [&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,10],"tags":[],"class_list":["post-3166","post","type-post","status-publish","format-standard","hentry","category-programming","category-projects"],"_links":{"self":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/3166","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=3166"}],"version-history":[{"count":0,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/3166\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3166"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3166"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3166"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}