{"id":146,"date":"2006-02-10T18:08:33","date_gmt":"2006-02-10T23:08:33","guid":{"rendered":"http:\/\/www.shamusyoung.com\/twentysidedtale\/?p=146"},"modified":"2011-04-10T05:43:35","modified_gmt":"2011-04-10T10:43:35","slug":"terrain-part-6","status":"publish","type":"post","link":"https:\/\/www.shamusyoung.com\/twentysidedtale\/?p=146","title":{"rendered":"Terrain, Part 6"},"content":{"rendered":"
Lighting & Shadows<\/div>\n

Work continues on the terrain engine. Part one is available here<\/a>. <\/p>\n

Now comes a moment where I have to make a major choice that will affect many decisions down the road. I want to add shadows, so that the hills can cast shadows on one another. Shadows are very striking and add a great deal of realisim, but they come at a significant price.
\n
\nUp until now I haven’t really worried about lighting. My program tells OpenGL “The sunlight is such-and-such color and is shining from this direction, the ground is this color.” OpenGL then takes all those numbers and crunches them for me, making light fall on the terrain. Hills have a light side and a dark side and everything looks pretty. This took about two minutes to set up and takes up just a few lines of code. It’s easy, simple, and effective. All this simplicity comes at a price, of course. The downside to all of this is that the lighting in OpenGL isn’t very flexible. It lights things. It can’t do shadows. If it could, then it wouldn’t be so simple to use<\/em>. <\/p>\n

As it stands, I can’t really add<\/i> shadows to the existing OpenGL lighting paradigm. This is all or nothing. The upshot is that if I want shadows, I have to write my own lighting code. All that nice stuff OpenGL is doing for me, all the lighting, is now in my hands. I have to add a ton of new code just to get my program to do what OpenGL was already doing. This isn’t hard, but it is a lot of new code and complexity just to duplicate what was already being done. Once that<\/b> code is done, then<\/b> I can add shadows.<\/p>\n

So, I replace the built-in lighting with my own:<\/p>\n


For this image, the sun is very low on the horizon, and I exaggerated the height of the mountains. I was going to have a side-by side comparison here of the new and old lighting systems. I didn’t make any effort to make sure my system would come up with the exact same results as OpenGL. I expected this would lead to slight variations in lighting. Turns out they look exactly the same anyway.<\/em><\/center><\/p>\n

And now it’s time to add shadows. Originally I was going to implement a system where my program does what is called line-of-sight checking. This would work by tracing a line from a given spot on the terrain towards the sun. If the line intersects with any polygon, then something is blocking the sun and the spot is assumed to be in shadow. This would work fine, although it can get a little CPU intensive. Checking to see if an arbitrary line intersects with any of my half-million polygons can get out of hand very quickly.<\/p>\n

Then I thought of an interesting shortcut: What if I make the assumption that the sun will only travel east \/ west and never be angled to the north or south? If I did this, then I wouldn’t have to do all the fancy polygon-checking. <\/p>\n

Let’s say the sun is shining from the west. The western most point on the map cannot therefore be in shadow, since there is nothing to the left of this first point. The sun is striking it. I save the height of this point as my “everything below this point is in shadow”. Just so I don’t have to type that out every time, let’s call it EBTPIIS. <\/p>\n

If the sun was right on the horizon, then the next point over would need to be higher than EBTPIIS to get any sunlight. However, if the sun is coming down at an angle then EBTPIIS needs to be lowered every time we move to the next point. If the sun was coming down at a forty-five degree angle, EBTPIIS would drop by exactly one unit, which is how far apart the points are horizontally. If this next point is above EBTPIIS, then the point is in sunlight and EBTPIIS will be set to the height of this new point. If the point is below EBTPIIS, then the point is in shadow and EBTPIIS remains unchanged. I pass over a single row of the terrain grid like this, moving from west to east. (If the sun is coming from the east, I pass over the grid in the other direction). The result is something like this:<\/p>\n


The blue lines mark the height of EBTPIIS. <\/em><\/center><\/p>\n

I know the explanation might sound odd, but these calculations are very, very fast. This is at least<\/em> ten times faster than line-of-sight checking. It is also far simpler to code. The only drawback is, as I mentioned before, is that the sunlight will only work on the plane defined by the east-west and up-down axis. I couldn’t use this system if I wanted the sun to come from the northwest, for example. This is a pretty minor tradeoff. I’m happy with how this turned out.<\/p>\n


Now with shadows!<\/em><\/center><\/p>\n
Judging Performance<\/div>\n

One of the problems I face on a project like this is figuring out what the various tradeoffs are. I mentioned a while ago out the quality vs. speed tradeoff. I can use less polygons and make the framerate better at the expense of visual quality. But the tradoff is non-linear. Very<\/i> non-linear. So, finding the sweet spot is tricky. Let’s have a look.<\/p>\n

For the purposes of this experiment, I made the terrain much larger and the hills very extreme. This creates a worst-case scenario, which will make the tradeoffs more obvious. So, this time my terrain is 1024 x 1024 squares. Thats 2,097,152 polygons. Ouch! Two million and change. <\/p>\n

<\/center>
\nIn the above image I turned the optimization down to almost nothing. This terrain is a stunning 2,095,088 polygons. This thing is a lot to render. My 2-year-old computer actually has trouble with this. My framerate is just a little better than 10fps.<\/p>\n

<\/center>
\nNow I turn it up a bit and the polygon count drops to 1,078,685. I just cut out half of the polygons from the previous image. I can’t even tell the difference. So, we cut poly count in half and lost no quality. <\/p>\n

<\/center>
\nIn this image we are down to 461,121 polys. At about half a million, I have once again cut the poly count in half. This time however, we can just barely see the difference. It still looks great, though, and my framerate is smooth again.<\/p>\n

<\/center>
\nI cut poly count in half again, down to 249,033. At a quarter million, it still looks good, but the quality loss is visible now. <\/p>\n

<\/center>
\nHalf again. Down to 112,225. We are getting to the point where each step down is taking more and more away from quality. I think this one and the previous one encompas the high and low end of the “sweet spot” on the curve. If this were a game, there would no doubt be some “quality” or “detail” sliders in the options. I would tune things so that high detail would produce the last image, and low detail would yield this one.<\/p>\n

<\/center>
\n51,066. It’s starting to look very bland. The black dots are shadows, which are still appearing even though the hills that created those shadows have been removed. This is unavoidable, unless I want to make the shadow-casting code much more complex. It would not make sense to improve the shadow code so that shadows can look great on horrible terrain. That is just not a good investment of time.<\/p>\n

<\/center>
\nAnd here we are near the bottom at 21,539. Obviously the thing looks totally unacceptable now. We’re down to 1% of the original poly count, but the cost to quality is so severe that we are clearly way<\/em> past the sweet spot.<\/p>\n

This data reinforces what I’ve suspected for a while now: You can dump 85% to 90% of the terrain polygons and get acceptable results, but once you dip below this point by even a few percent the cost in quality becomes pretty drastic.<\/p>\n","protected":false},"excerpt":{"rendered":"

Lighting & Shadows Work continues on the terrain engine. Part one is available here. Now comes a moment where I have to make a major choice that will affect many decisions down the road. I want to add shadows, so that the hills can cast shadows on one another. Shadows are very striking and add […]<\/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-146","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\/146","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=146"}],"version-history":[{"count":0,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/146\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=146"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=146"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=146"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}