{"id":23460,"date":"2014-06-26T09:05:46","date_gmt":"2014-06-26T14:05:46","guid":{"rendered":"http:\/\/www.shamusyoung.com\/twentysidedtale\/?p=23460"},"modified":"2014-06-26T14:54:30","modified_gmt":"2014-06-26T19:54:30","slug":"project-unearth-part-2-skimming-hazzard","status":"publish","type":"post","link":"https:\/\/www.shamusyoung.com\/twentysidedtale\/?p=23460","title":{"rendered":"Project Unearth Part 2: Skimming Hazzard"},"content":{"rendered":"

You know what they say<\/a> about when you assume something? When you assume, you might save time by using extrapolated information and pattern recognition to quickly zero in on the solution to the problem.<\/em> No? That’s not what people say about making assumptions? I just kind of assumed people would… oh.<\/p>\n

Well, my assumptions did in fact make an ass of meBut not you. You’re still cool.<\/span> this time. I’ve read about various shadow techniques and I thought I had a decent handle on what I wanted to do. So when I read up on the theory I got to the halfway point and was like, “Yeah, yeah. I got this,” and started skimming. <\/p>\n

Like many 3D concepts, this one begins with a crappy diagram:<\/p>\n

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

Here we’ve mooshed the problem down to two dimensions to make it easier to depict. (And spoiler warning: Also easier to misinterpret if you’re skimming because you think you know what you’re doing already.) On the left we have a light source. The green box is an occluder. On the right we have a wall that, if our technology works right, will have a big ol’ shadow right in the middle thanks to the occluder. <\/p>\n

I’ve looked at a half dozen diagrams just like this one in the past couple of weeks. Light, occluder, and a big object to receive shadows. It seems silly to make ANOTHER version of the same stupid diagram, but that’s what we’re doing.<\/p>\n

As I’ve mentioned in the past, objects are made up of vertices, and vertices have surface normals<\/a>. Here are the normals for this scene:<\/p>\n

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

So what we do is set up a special rendering pass. Before we draw the lighting, we’re going to mask out the areas where the light can’t go. The concept is that you look at the direction of the normal. If it’s facing away from the light, then we calculate a new direction, one going from the light to the vertex:<\/p>\n

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

We take those points and give them a great big shove along this new vector. And by “big shove” I mean “all the way to infinity”. Now we draw our extruded shapes.<\/p>\n

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

Note that we would do the exact same thing to the yellow box as well. We do this for any and all shapes in the scene, and they will all shadow themselves and each other without us needing to figure out the relationships between the objects or calculating which objects are occluding others. I’m just showing the green box to keep this simple. <\/p>\n

So anyway. Everywhere that the extruded green shape is further from the camera than the normal yellow shape is a spot where the light can’t reach. We use this rendering pass to stencil out the next pass, where we draw the lights themselves:<\/p>\n

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

Awesome, right? <\/p>\n

Well, it would be nice if this worked, but everything I just showed you is a clumsy oversimplification of the actual technique. Don’t implement this. It won’t work.<\/p>\n

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

The frustrating thing about this is that it nearly<\/em> works. It works for the various illustrations that people have made to describe how you do this kind of lighting, including mine. It’s so close to working that I spent a lot of time looking for bugs in my shadowing system instead of questioning the design I was using. <\/p>\n

The problem becomes obvious if you don’t use this platonic ideal illustration. Consider a slightly different arrangement of objects:<\/p>\n

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

In this case, only one vertex is facing away from the light. Which means our shadow ends up shaped like this:<\/p>\n

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

When it should be this:<\/p>\n

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

It’s sad. What I implemented produces “pretty good results” a lot of the time. From a lot of lighting angles, it can look correct. And even when it’s wrong, it often looks “right enough” that the eye doesn’t question it. But from other angles it’s horribly and obviously wrong and dumb and bad. It makes all these thin little sliver shadows that aren’t shaped at all like the thing casting the shadow. On block terrain, you end up with shadows that look like they’re being projected by a jagged wall of pikes. <\/p>\n

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

This is sad-making. The easy way is really easy, and almost works. It looks right (or good enough) 80% of the time. But that last 20% looks really wrong. And to do things right – to fix that last 20% – is about four times the work. The pipeline is more complex, you need another shader, and it requires a lot more graphical horsepower. (My way is super-cheap.)<\/p>\n

It sucks when you have a job where a majority of the work goes into a minority of the benefit, but I suppose I can’t call myself an engineer if I’m not willing to put up stuff like this. <\/p>\n

The actual solution – which I finally discovered once I went back and read the theory with a little more care – is that you can’t get away with simply shoving single points. You have to shove entire polygons. Specifically, you need to find polygons that are right on the edge, having some points towards the light and others away from the light. <\/p>\n

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

Once I’m done bellyaching, I realize this is actually a boon for me. Sure, it’s more work. And it’s a lot more complicated. But doing this requires the use of a geometry shader, and learning about those is one of the goals of the project! <\/p>\n

I’ve described shaders before. Here’s a diagram I made a couple of years ago<\/a>:<\/p>\n

octant11_1.png<\/td><\/tr><\/table><\/p>\n

Geometry shaders go between these two steps. So after the vertex leaves the vertex shader it’s available to the geometry shader. (If you’re using one.) The geometry shader is a crazy thing. It takes primitives as inputs. (Triangles, lines, or even just lone vertices.) In our above diagram, the geometry shader would sit between steps 3 and 4. <\/p>\n

The other two shaders produce the same type of output every time, but the geometry shader can generate all kinds of different stuff. It can mind it’s own damn business and pass the values along without doing anything. Or it can make additional changes. Or it can generate entirely new primitives, creating new triangles based on whatever cockamamie system the programmer has devised.<\/p>\n

In our case, it looks for edge triangles and turns them into groups of triangles like so: <\/p>\n

unearth_shadow_volume.png<\/td><\/tr><\/table><\/p>\n

I used this tutorial<\/a> as a guide. It turns out that shader has a bug in it. It doesn’t cap the end of the shadow (the bright magenta triangle in the above diagram) which can leave odd holes in your shadows. If you’re here via google and just want the goods, then here is a fix I came up with: <\/p>\n

\r\n\/*-----------------------------------------------------------------------------\r\nThis shader takes a triangle of type GL_TRIANGLES_ADJACENCY. It tkes the \r\nfollowing form:\r\n\r\n                 1-----2-----3\r\n                  \\   \/ \\   \/\r\n                   \\ \/   \\ \/\r\n                    0-----4\r\n                     \\   \/\r\n                      \\ \/\r\n                       5\r\nPoints 0, 2, and 4 are the points of the triangle actually being drawn. \r\nPoints 1, 3, and 5 are corners of adjacent triangles, provided by OpenGL \r\nfor the purposes of being able to analyze the topology here in a geometry\r\nshader.\r\n\r\nWe're looking for triangles that fall along the edge bewteen surfaces facing \r\ntowards the light, and others facing away from it.\r\nWhen we find such a triangle, we extrude it, turning the 0, 2, 4 triangle \r\ninto a tube that reaches the far clip plane. This makes the shadow volume \r\nfor this triangle, and is used to stencil out regions that the light can't \r\nreach.\r\n-----------------------------------------------------------------------------*\/\r\n\r\n#version 150 compatibility\r\n\r\n#define gVP           gl_ModelViewProjectionMatrix\r\n#define gLightPos     uni_light_position\r\n\r\nlayout (triangles_adjacency) in;\r\nlayout (triangle_strip, max_vertices = 18) out;\r\n\r\nin vec3 WorldPos[];\r\n\r\nuniform vec3        uni_light_position;\r\nuniform mat4        gl_ModelViewProjectionMatrix;\r\n\r\nfloat EPSILON = 0.01;\r\n\r\nvoid EmitQuad(int StartIndex, vec3 StartVertex, int EndIndex, vec3 EndVertex)\r\n{\r\n    vec3 LightDir = normalize(StartVertex - gLightPos);\r\n    vec3 l = LightDir * EPSILON;\r\n    gl_Position = gVP * vec4((StartVertex + l), 1.0);\r\n    EmitVertex();\r\n\r\n    gl_Position = gVP * vec4(LightDir, 0.0);\r\n    EmitVertex();\r\n\r\n    LightDir = normalize(EndVertex - gLightPos);\r\n    l = LightDir * EPSILON;\r\n    gl_Position = gVP * vec4((EndVertex + l), 1.0);\r\n    EmitVertex();\r\n\r\n    gl_Position = gVP * vec4(LightDir, 0.0);\r\n    EmitVertex();\r\n\r\n    EndPrimitive(); \r\n}\r\n\r\nvoid main()\r\n{\r\n  \/\/We take our 6 points and create six edges.\r\n  vec3 e1 = WorldPos[2] - WorldPos[0];\r\n  vec3 e2 = WorldPos[4] - WorldPos[0];\r\n  vec3 e3 = WorldPos[1] - WorldPos[0];\r\n  vec3 e4 = WorldPos[3] - WorldPos[2];\r\n  vec3 e5 = WorldPos[4] - WorldPos[2];\r\n  vec3 e6 = WorldPos[5] - WorldPos[0];\r\n\r\n  \/\/This gives us the normal of this triangle.\r\n  vec3 Normal = cross(e1,e2);\r\n  vec3 LightDir = gLightPos - WorldPos[0];\r\n  \r\n  if (dot(Normal, LightDir) > 0.000001) {\r\n\r\n    Normal = cross(e3,e1);\r\n\r\n    if (dot(Normal, LightDir) <= 0) {\r\n        vec3 StartVertex = WorldPos[0];\r\n        vec3 EndVertex = WorldPos[2];\r\n        EmitQuad(0, StartVertex, 2, EndVertex);\r\n    }\r\n\r\n    Normal = cross(e4,e5);\r\n    LightDir = gLightPos - WorldPos[2];\r\n\r\n    if (dot(Normal, LightDir) <= 0) {\r\n      vec3 StartVertex = WorldPos[2];\r\n      vec3 EndVertex = WorldPos[4];\r\n      EmitQuad(2, StartVertex, 4, EndVertex);\r\n    }\r\n\r\n    Normal = cross(e2,e6);\r\n    LightDir = gLightPos - WorldPos[4];\r\n\r\n    if (dot(Normal, LightDir) <= 0) {\r\n      vec3 StartVertex = WorldPos[4];\r\n      vec3 EndVertex = WorldPos[0];\r\n      EmitQuad(4, StartVertex, 0, EndVertex);\r\n    }\r\n\r\n    vec3 LightDir;\r\n    \/\/Front cap. (Original triangle.)\r\n    LightDir = (normalize(WorldPos[0] - gLightPos)) * EPSILON;\r\n    gl_Position = gVP * vec4((WorldPos[0] + LightDir), 1.0);\r\n    EmitVertex();\r\n    LightDir = (normalize(WorldPos[2] - gLightPos)) * EPSILON;\r\n    gl_Position = gVP * vec4((WorldPos[2] + LightDir), 1.0);\r\n    EmitVertex();\r\n    LightDir = (normalize(WorldPos[4] - gLightPos)) * EPSILON;\r\n    gl_Position = gVP * vec4((WorldPos[4] + LightDir), 1.0);\r\n    EmitVertex();\r\n    EndPrimitive();\r\n\r\n    \/\/Back cap. (Original triangle, projected to infinity.)\r\n    LightDir = (normalize(WorldPos[4] - gLightPos));\r\n    gl_Position = gVP * vec4(LightDir, 0.0);\r\n    EmitVertex();\r\n    LightDir = (normalize(WorldPos[2] - gLightPos));\r\n    gl_Position = gVP * vec4(LightDir, 0.0);\r\n    EmitVertex();\r\n    LightDir = (normalize(WorldPos[0] - gLightPos));\r\n    gl_Position = gVP * vec4(LightDir, 0.0);\r\n    EmitVertex();\r\n    EndPrimitive();\r\n  }\r\n}\r\n<\/pre>\n
I don't promise the above is correct, optimal, portable, sensible, efficient, or clear. This is the effort of a novice trying to correct the work of his betters. Good luck!<\/p>\n
I'll add that I love having an excuse to draw elaborate ASCII diagrams directly into code like this. I've done it many times in the past, and I've never regretted it. Comments are nice, but when you're fooling around with geometry and complex spatial relationships, nothing beats having a picture of the idea right there in the code. <\/p>\n
The result?<\/p>\n
unearth_volume12.jpg<\/td><\/tr><\/table><\/p>\n
The glitches are gone and we're now casting correct shadows. <\/p>\n
The great thing is that now that it all works, it scales up nicely. I can add more lights and more objects and all will continue to work as expected.  All you need is more power. I don't need to add special-case checking for situations where shadows stack, or eat extra texture memory, or where we need to analyze the positions of objects relative to each other. Even better, adding more objects and lights will require more GPU power, but not significantly more CPU power.<\/p>\n
Onward.<\/p>\n","protected":false},"excerpt":{"rendered":"
You know what they say about when you assume something? When you assume, you might save time by using extrapolated information and pattern recognition to quickly zero in on the solution to the problem. No? That’s not what people say about making assumptions? I just kind of assumed people would… oh. Well, my assumptions did […]<\/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":[],"class_list":["post-23460","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\/23460","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=23460"}],"version-history":[{"count":0,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/23460\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=23460"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=23460"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=23460"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}