{"id":23667,"date":"2014-07-13T23:28:10","date_gmt":"2014-07-14T04:28:10","guid":{"rendered":"http:\/\/www.shamusyoung.com\/twentysidedtale\/?p=23667"},"modified":"2014-07-14T09:53:05","modified_gmt":"2014-07-14T14:53:05","slug":"project-unearth-part-6-kissing-cubes","status":"publish","type":"post","link":"https:\/\/www.shamusyoung.com\/twentysidedtale\/?p=23667","title":{"rendered":"Project Unearth Part 6: Kissing Cubes"},"content":{"rendered":"

Shadow volumes are interesting things. For everything that casts a shadow, you need to have a fully enclosed solid. Because of the way our shader works, for every triangle we need to know what its 3 adjacent neighbors are. And when I say “need” I don’t mean “ought to” I mean it’s impossible to do otherwise. You can’t supply a triangle to the shader without neighbors for the same reason you can’t draw a triangle with less than three vertices. It wouldn’t make any sense. (And if there aren’t 3 neighbors? Then this isn’t an enclosed solid.) <\/p>\n

Let me bring up this diagram again:<\/p>\n

\r\n\/*-----------------------------------------------------------------------------\r\nThis shader takes a triangle of type GL_TRIANGLES_ADJACENCY. It takes 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\n<\/pre>\n
This is no big deal when you’re using models made by artists. Maybe the artist has some kind of tool or conversion utility for identifying all the triangle relationships. But this becomes tricky when we’re building objects on the fly. When I’m building a particular cube, I can’t hook its triangles up to its neighbors, because at least half of them haven’t been built yet. I could peek at the next-door cube to see what I will eventually build there, but I won’t know what vertices it will use until I get there. So what you have to do is just build a bunch of triangles and then stitch them together when you’re done. <\/p>\n
This is actually really time consuming. Like, 90% of the time spent waiting for chunks to appear is waiting for it to thrash through these huge lists of triangles and figure out which ones are neighborsThis is the major reason I’m not using larger chunk sizes. Larger chunks make this triangle-matching less efficient. There are ways to improve this, but I haven’t gotten around to it yet.<\/span>. Eventually I’m going to have to fix that. Chunks take about a quarter second to form. A given scene with even a modest view distance will have hundreds and hundreds of chunks. Which means filling in a scene can take a few minutes. While this doesn’t matter from a gameplay standpoint (this isn’t a game, and nobody is ever going to play it, so who cares?) it does matter from a testing perspective because I do a lot of tests and I’m really impatient. But this is a challenge for a future post. In the meantime…<\/p>\n
It turns out that we have a problem:<\/p>\n
unearth_kissing1.jpg<\/td><\/tr><\/table><\/p>\n
Those dark streaks in the center are shadows, reaching off to infinity. We don’t want that. <\/p>\n
Let’s flatten the problem out to 2 dimensions. So instead of building triangles around cubes we’re building lines around squares. Imagine the dark squares are solid and the white ones are empty space:<\/p>\n
unearth_kissing2.png<\/td><\/tr><\/table><\/p>\n
Blue line A has 2 neighbors, lines B and C. You can look at this diagram and see that no matter what sorts of squares I make or where I put them, every group of squares would be surrounded by line segments and every line segment would have exactly 2 neighbors. <\/p>\n
Well, ALMOST. It turns out there is an exception to this rule:<\/p>\n
unearth_kissing3.png<\/td><\/tr><\/table><\/p>\n
These two squares share a corner, so they’re “kissing”. This means that the purple line now has 4 neighbors. Sort of. Four lines all converge on the same point, and it’s not at all clear who should be neighbors. If we add a cube at point X, then purple’s neighbors would be red and cyan. If X is empty, then purple should be neighbors with red and blue. <\/p>\n
The crazy shadows I showed you earlier happen when a couple of kissing cubes confuse the triangle-stitching code. It puts the wrong neighbors together, which results in holes in our shadow volume, which results in the broken shadows you see above. <\/p>\n
Visually, it’s pretty clear that red and blue are the “real” adjacent lines in the above diagram, and the other two belong to a different cube. But it’s only obvious because you’re a human being with a fabulous human brain and I’ve drawn you this handy diagram. To the computer:<\/p>\n
unearth_kissing4.png<\/td><\/tr><\/table><\/p>\n
It doesn’t know what you’re trying to build. It can’t “see” the squares and intuit what it’s supposed to do. It just sees this list of points and these arbitrary relationships between them. There’s nothing here to suggest that blue is a more correct neighbor for purple than cyan or green. We need some way to explain it to the computer. <\/p>\n
Unfortunately, this is harder than it sounds. When we’re building the lines the information isn’t ready yet, and when we’re hooking up neighbors later the information about the ownership of these polygons is gone. We could probably sort it out by doing some kind of complex spatial analysis. But that would be…<\/p>\n
    \n
  1. A major pain in the ass to write.\n
  2. Super slow, so that it takes EVEN LONGER for this dang scenery to fill in when I run the program.\n<\/ol>\n
    So I am not crazy about this solution. In fact, I’d be happy if I could just hack around this problem. I’ve kind of had my fill of cube logic for now and I want to be working on other stuff. But it’s really annoying to have these massive bogus shadows cutting across my view while I’m trying to test. <\/p>\n
    unearth_kissing8.jpg<\/td><\/tr><\/table><\/p>\n
    I’ve been trying to ignore this for a while now. Usually when a bad dice roll results in a couple of kissing cubes I’ve been just hunting them down manually and deleting one of them. As far as solutions go, that’s kind of pathetic. Also time consuming. These shadows can originate from anywhere in the scene, so often I have to fly a long way to reach the culprit. <\/p>\n
    So the quick-and-easy solution seems to be having it detect and automatically delete one of the offending cubes. Actually, I don’t even need it to delete the cube itself, it just needs to leave the cube out of the shadow volume. What this means is that when we have a pair of kissing cubes, one of them won’t cast a shadow. In the words of the great philosopher Strong Bad, “Who cares?”<\/p>\n
    Fine. Easy. When it’s making the model, it looks for kissing cubes and then leaves one of them out of the shadow volume. <\/p>\n
    I get back to what I was doing. I’m messing around with generating caves and hills when…<\/p>\n
    unearth_kissing5.jpg<\/td><\/tr><\/table><\/p>\n
    Wait what? Oh, right. Duh:<\/p>\n
    unearth_kissing6.png<\/td><\/tr><\/table><\/p>\n
    A and B are kissing. But if I remove A then C and D become kissing cubes. This is probably what we see in the previous screenshot: It tried to fix one set of kissing cubes and ended up creating another.  I could ADD a cube at point E (or just force a shadow there) but that would create a new connection between E and F. <\/p>\n
    And remember that while this looks simple and clean in these diagrams, I’m actually dealing with the problem in 3 dimensions. A 3D cube has 12 edges, which means there are 12 possible relationships to worry about and 12 places where we can inadvertently create kissing pairs by adding or removing cubes. <\/p>\n
    This is a silly little problem.<\/p>\n
    It turns out the most expedient answer is to just cut the entire chunk in half:<\/p>\n
    unearth_kissing7.png<\/td><\/tr><\/table><\/p>\n
    If we find a kissing pair, we whip out our lightsaber and slice the whole chunk right down through the problem edge. This will result in slightly more total faces. Before the slice, D and G were part of the same volume. After the cut they’re isolated from each other, and they have (wasted) polygons facing one another. <\/p>\n
    I try to feel bad about this, but I have other stuff I’d rather be working on. <\/p>\n
    We’ll try and do some Cool Stuff next time.<\/p>\n","protected":false},"excerpt":{"rendered":"
    Shadow volumes are interesting things. For everything that casts a shadow, you need to have a fully enclosed solid. Because of the way our shader works, for every triangle we need to know what its 3 adjacent neighbors are. And when I say “need” I don’t mean “ought to” I mean it’s impossible to do […]<\/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-23667","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\/23667","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=23667"}],"version-history":[{"count":0,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/23667\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=23667"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=23667"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=23667"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}