{"id":22995,"date":"2014-05-15T09:36:13","date_gmt":"2014-05-15T14:36:13","guid":{"rendered":"http:\/\/www.shamusyoung.com\/twentysidedtale\/?p=22995"},"modified":"2014-05-15T09:40:35","modified_gmt":"2014-05-15T14:40:35","slug":"frontier-rebooted-part-3-act-normal","status":"publish","type":"post","link":"https:\/\/www.shamusyoung.com\/twentysidedtale\/?p=22995","title":{"rendered":"Frontier Rebooted Part 3: Act Normal"},"content":{"rendered":"

Working with shaders is a little strange. They’re programs that run on your graphics cardI don’t like to bog you down with terminology, but we’re going to need to use SOME. From here on, your computer is the CPU and the graphics card is the GPU.<\/span>. The pathway between your CPU and the GPU is a bit of a choke point. These two devices can only communicate so fast, and they need to share a monumental amount of data. In an ideal world, you would shove EVERYTHING over to the GPU. Then each frame you would just specify where the camera is, it would crunch all the numbers for you, and in return you’d get the completed image to show to the player. That’s not really feasible outside of the most rudimentary example programs, but we do want to get as close to that idea as possible. <\/p>\n

The GPU is very, very good at crunching 3D spatial values. It’s better than your CPU in the same way that a Formula 1 car is better at Formula 1 racing than a dusty pickup truckNo quasi-technical explanation is complete without a Terrible Car Analogy.<\/span>. It sacrifices flexibility to excel at one very specific task. You can’t run Microsoft Office or a web browser on your GPU. It literally doesn’t have the ability to perform that sort of processing. But the one thing it is good at, it’s really<\/em> good at. This creates an interesting challenge for us. Any job we want to give to the GPU, we have to first translate into the sort of job a GPU can<\/em> do. <\/p>\n

This first one is easy. We just need to calculate some surface normals. <\/p>\n

http:\/\/upload.wikimedia.org\/wikipedia\/commons\/f\/f6\/Surface_normal.png<\/td><\/tr><\/table><\/p>\n

Normals are the vectors that point directly away from a given surface. In a perfect sphere, they would all point directly away from the center. On a nice flat tabletop, they all point directly up. On a complex surface it’s… complex. I suppose one way to think of it is imagine throwing a superball<\/a> at whatever surface you’re interested in. Ignoring gravity (maybe you snuck your superball onto the international space station?) if the ball bounces back along exactly the same vector you threw it, then it traveled along the normal of the point of impact. Also you should probably stop throwing things in here.<\/p>\n

We want to offload this normal-calculating business to the GPU, but we have limited ways of communicating with it, and even more limited ways of getting data from it. We can only give it polygons and textures, and the only thing it can do is draw pixels on the screen.<\/p>\n

So what we do is we make a new shader. This one will also take the heightmap as input, but instead of drawing terrain, it will draw us the normal map we want. This drawing is done between frames, where the user can’t see it happen. We draw a plain square to the screen, and we give the shader the heightmap to work with.<\/p>\n

freboot5.jpg<\/td><\/tr><\/table><\/p>\n

For any given point A, we sample its four neighbors: To the west and east we have X1<\/sub> and X2<\/sub>, and to the north and south we have Z1<\/sub> and Z2<\/sub>. Our goal is to find the normal for A, but we only care about the position of these neighbors. Within the gameworld, this grouping would look so:<\/p>\n

freboot6.jpg<\/td><\/tr><\/table><\/p>\n

Remember that we’re not actually drawing<\/em> these polygons right now. We’re just pulling values out of the heightmap, figuring out where the polygons would be, and using these numbers to calculate the value we want. <\/p>\n

We use these values to generate a couple of vectors. They’re not the vectors we want, but they’re close. If we subtract Z1<\/sub> from Z2<\/sub>, we get a vector that points from one to the other. Likewise, we subtract X1<\/sub> from X2<\/sub> we get the vector that points from one of them to the other. Optional bonus info for go-getters: We have to normalize these two vectors. That just means you divide them by their own length. The resulting vector still points exactly the same direction, but it’s now exactly 1 unit long, regardless of how far apart the original two points were.<\/em><\/p>\n

freboot7.jpg<\/td><\/tr><\/table><\/p>\n

So now we have two vectors, which together form a plane. The normal we want is perpendicular to this plane. Time to calculate the cross product<\/a>. In code, it looks like this:<\/p>\n

(For clarity and absolute precision, we’ve named our two red and blue input vectors potato<\/code> and eisenhower<\/code>, respectively.)<\/p>\n

\r\nvector CrossProduct (vector eisenhower, vector potato)\r\n{\r\n  vector A;\r\n\r\n  A.x = potato.y * eisenhower.z - potato.z * eisenhower.y;\r\n  A.Y = potato.z * eisenhower.x - potato.x * eisenhower.z;\r\n  A.z = potato.x * eisenhower.y - potato.y * eisenhower.x;\r\n  return A;\r\n}\r\n<\/pre>\n
If you’re more of a pencil-and-paper type mathematician, then it looks like this:<\/p>\n
eisenhower × potato = ||eisenhower|| ||potato|| sin θ n<\/em><\/code><\/p>\n
In this case the “×” symbol means “cross product” and not “multiply”. The rest of it is more mysterious to me. I’m never one for labor-intensive tasks like doing arithmetic or finding clean scratch paper. <\/p>\n
Anyway, when you take the cross product of two vectors like this, the result is a new vector that is perpendicular to both. You might notice that there are actually two such answers to this problem. Remember all that left hand \/ right hand crap we had to worry about last time<\/a>? This is one of those situations where it matters. In one coord system, your vector will point out of the surface, and in the other it will point into it. That’s fine either way, as long as you remember which way everything is facing. Or, you know, just flip the vectorMultiply by negative one.<\/span> if it’s backwards from what you want. <\/p>\n
The result:<\/p>\n
freboot8.jpg<\/td><\/tr><\/table><\/p>\n
So now we have the surface normal and a new problem. We can still only write color values. As far as the GPU is concerned, we’re drawing pixels on the screen so the user can look at them. We can write four values: Red green, blue, and alpha. These values are each stored in a single byteYou can make textures that use more or less bytes per color value, but since we’re drawing to the screen we still have to match what the display supports.<\/span> and that’s all we have to work with.  <\/p>\n
Inside of the shader program we’re using real numbers like 0.2<\/code> and -0.67114<\/code>. But as they’re written to the screen they’re clipped into the zero to one range. That’s quite a bit of damage, but then there’s another round of damage when it’s stored in a single byte, throwing away a lot of our precision. The smallest non-zero value we can store is something like 0.00390625<\/code> and the next unique value we can store is 0.0078125<\/code>. Values between these two will get rounded to one or the other0.00390625 because that’s 1\/256, because 256 is the number of distinct values you can store in a single byte.<\/span>. But! We also have some things working in our favor. We want to store the X, Y, and Z values of this vector, and we have red, green, and blue color channels to work with. So that’s handy.<\/p>\n
Normalized vector values fall between -1 and +1, but you might recall from the adventure that was the previous paragraph that color values must be between 0 and +1. So what we do is this: divide by two, add 0.5, and stuff XYZ into RGB. This gives us values centered around 0.5 instead of 0.0.  That’s fine as long as we remember to undo this step later when we extract the normal from the texture map for use. This process of turning spatial values into color values is pretty common when you’re dealing with shaders, and makes for some strange images. Here are some normal maps I found on Google:<\/p>\n
freboot9.jpg<\/td><\/tr><\/table><\/p>\n
We’re creating something along these lines as we process our heightmap. When we’re done, we have an image like one of the above (except showing the contour of our hills instead of brick or whatever that thing in the middle is) sitting on screenThe user doesn’t see it because we’re drawing on the back buffer, which I explained in this post<\/a>.<\/span>. Now we tell OpenGL to grab a spatula and scrape those pixels off the screenSome mobile implementations allow the use of a butterknife instead.<\/span>, then stuff them in a texture map.  <\/p>\n
You might notice this is exactly the sort of situation we’re trying to avoid. We pull that completed image from GPU to CPU, then turn it into a texture map and send it back. This is an area where apparently consoles have an edge. On some consoles, graphics memory and CPU memory all share the same pool, so you can just copy the pixels directly to where you want them. On the PC, we’re doing at least 2 copy operations. There may be more happening deep down in the driver layers that we don’t even know about. This became an issue in RAGE, where they needed to constantly shuffle texture data around to do megatexturing<\/a> and the much-slower Xbox 360 could actually out-perform the PC at certain tasks. <\/p>\n
So now we take our flat-shaded terrain…<\/p>\n
freboot2.jpg<\/td><\/tr><\/table><\/p>\n
…and apply our normal map:<\/p>\n
freboot3.jpg<\/td><\/tr><\/table><\/p>\n
For the record: The world tiles, so as you travel you’ll eventually wrap around and pass the same scenery again and again. That odd seam on the right side of the image is where this wrapping happens. This is caused by using a heightmap with edges that don’t match up. This will be fixed later. <\/p>\n
Next time we’ll be doing something a lot more complex with our shaders.<\/p>\n","protected":false},"excerpt":{"rendered":"
Working with shaders is a little strange. They’re programs that run on your graphics cardI don’t like to bog you down with terminology, but we’re going to need to use SOME. From here on, your computer is the CPU and the graphics card is the GPU.. The pathway between your CPU and the GPU is […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[66],"tags":[387,388],"class_list":["post-22995","post","type-post","status-publish","format-standard","hentry","category-programming","tag-glsl","tag-opengl"],"_links":{"self":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/22995","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=22995"}],"version-history":[{"count":0,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/22995\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=22995"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=22995"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=22995"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}