Project Unearth Part 6: Kissing Cubes

 By Shamus Jul 13, 2014 31 comments

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.)

Let me bring up this diagram again:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*-----------------------------------------------------------------------------
This shader takes a triangle of type GL_TRIANGLES_ADJACENCY. It takes the 
following form:
 
                 1-----2-----3
                  \   / \   /
                   \ /   \ /
                    0-----4
                     \   /
                      \ /
                       5
Points 0, 2, and 4 are the points of the triangle actually being drawn. 
Points 1, 3, and 5 are corners of adjacent triangles, provided by OpenGL 
for the purposes of being able to analyze the topology here in a geometry
shader.
-----------------------------------------------------------------------------*/

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.

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.. 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…

It turns out that we have a problem:

unearth_kissing1.jpg

Those dark streaks in the center are shadows, reaching off to infinity. We don’t want that.

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:

unearth_kissing2.png

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.

Well, ALMOST. It turns out there is an exception to this rule:

unearth_kissing3.png

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.

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.

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:

unearth_kissing4.png

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.

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…

  1. A major pain in the ass to write.

  2. Super slow, so that it takes EVEN LONGER for this dang scenery to fill in when I run the program.

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.

unearth_kissing8.jpg

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.

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?”

Fine. Easy. When it’s making the model, it looks for kissing cubes and then leaves one of them out of the shadow volume.

I get back to what I was doing. I’m messing around with generating caves and hills when…

unearth_kissing5.jpg

Wait what? Oh, right. Duh:

unearth_kissing6.png

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.

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.

This is a silly little problem.

It turns out the most expedient answer is to just cut the entire chunk in half:

unearth_kissing7.png

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.

I try to feel bad about this, but I have other stuff I’d rather be working on.

We’ll try and do some Cool Stuff next time.

201131 comments. Hurry up and add yours before it becomes passé.


  1. Are you entire chunks as singular polygon meshes? Given the trouble you seem to be having here, would it hypothetically have been cheaper to instead break it down into discrete solids?

    • DaMage says:

      I actually mucked around with that ages back when I was learning shaders. If you try to divide it all into separate cubes you essentially have to draw twice as much, as if you combine into a single model, you can strip out all of the impossible to see face that face beneath the ground.

    • Maybe, but you have to watch out. If the solids are too discreet, they’ll refuse to advertise their presence by casting shadows at all. They may even start increasing their transparency levels.

      • Shamus says:

        I get the reaction a lot when I talk about that color.

        I grew up being taught that pink was pale red: http://www.colorhexa.com/ff8888

        And that ultra-saturated red and blue together was purple: http://www.colorhexa.com/ff00ff

        (Although magenta seems to be a safer name for the latter.)

        I dunno. These two colors are radically different. Seems strange to me to call them both “pink”. But then, color names have always been a strange deal. I’m sure everyone has seen this, but if I don’t post here here then someone else will just do so in a reply: http://blog.xkcd.com/2010/05/03/color-survey-results/

        :)

        • Zukhramm says:

          I’ve always used the same definition, if there’s red and blue in it, it’s purple.

          The purples are actually an unusual set of colors compared to the rest as aside from the violet wavelength, they’re non-spectral, i.e. they only exist as combinations of red and blue light, there is no light with purple wavelengths.

        • Felblood says:

          I think this reply has somehow become attached to the wrong post.

          One minute I was reading about polygons, and suddenly we are talking about colors.

          Is this about the names used for the colors on the diagrams? I am only guessing.

        • For that matter, I understand monitors can have odd effects; the colour I see may well be different from the colour you see.
          I doubtless should have put a smiley on my post in any case–I was just razzin’ ya. But as someone who has put a certain amount of thought to the question of what’s purple and what ain’t–well, it is kind of weird. How our eyes perceive stuff isn’t as simple as linear relationships between proportions of different stuff. I just looked up “imperial purple” on that site. Weird thing: It too is half blue and half red, and yet it looks (fairly) properly purple to my eyes, apparently just because it’s darker.
          Meanwhile, on average I personally find things look purpler if they’re a bit more blue than red, and I think that’s not uncommon. But at that, people see/group/categorize things somewhat differently. The edges of what people consider greens, aquas, and blues vary quite a bit, for instance. This sort of thing raises questions that go beyond Science! Itself! and into philosophy.

  2. The Snide Sniper says:

    Or cause it to prefer convex corners. If you have multiple options for neighbors, look at their normals, and choose one facing away from the current triangle. Note: A better, but more technical, explanation is below.

    Suppose your current triangle has vertexes v1, v2, and v3, and you’re looking at another triangle with vertexes v1, v2, and v4. Compute the normal for the first triangle. Compute the dot product of the normal and (v4 – v1); we’ll call this dot product K. If there are multiple candidates, the one which minimizes K is the one you want as a neighbor.

    This method still has failure states, but they are impossible to reach in a block world.

  3. So you literally ‘hacked’ it in two.

    THANK YOU! I’LL BE HERE ALL NIGHT! BE SURE TO TIP YOUR WAITRESSES!

  4. As one of the missions for this series seems to be “can we render fast enough for VR’s 75Hz x 2 views x 1MP per eye*”, I’m wondering if you’ll be going into the driver/arch efficiencies side? Stuff like how big you want the triangles to be for efficient rendering. Or how many of them you want to pass to the driver in a single batch to efficiently fill the parallel arch (by ensuring a complete warp/wavefront can lockstep over the same workload).

    * with good VR looking like 100Hz+ and 2MP+ per eye and who knows if consumer kit in 2015 can get there when we’re only just seeing the first specs with DK2 this month.

  5. Yikes! Why aren’t you computing centers and using face normals to determine… I mean, you’d want to keep track of which vertexes go with which faces so that… unless you’re trying to build a quarter as many vertexes to save render time because… shadow volumes… manifold…

    Shit. This stuff is complicated.

    So, instead of building cubes out of vertexes, (where you already know which faces go with which vertexes because you just generated them) and then throwing away the ones that are internal… you’re building vertex hulls and then dynamically generating faces based on… something?

    If you’re generating the vertexes and faces in the first place, why are you computing anything? Why don’t you have it keep track of where the faces go when you generate the vertexes?

    Also, why does the surface have to be manifold? Can’t you just project each face outward individually and get the shadow volumes that way? Sure, you’ll have a bunch more “edges” to your shadow volumes… unless that’s what you’re trying to avoid?

    It seems like this whole thing is suffering from lopsided optimization, where the shadow code has convinced you to do funky stuff with the geometry generation. But of course, it’s probably more complicated than it looks.

    In any case, it’s one of those problems that you wouldn’t see unless there were several of these complicated systems all running at the same time. I’m glad its working anyway! Thanks for sharing.

  6. Mephane says:

    I love this series. Not only is it educational for me about 3D graphics programming, I can already see it as very educational for non-programmers about programming itself. That “kissing cubes” shadow problem, this is exactly the kind of strange and hard-to-tackle bug programmers have to deal with all the time. Including even the quick fix that leads to the same bug reoccurring in a different scenario. :D

  7. HiEv says:

    If you can recognize “kissing cubes” for elimination, then instead of eliminating them, could you mark them in some way so that when you get to them it knows how to treat them instead? I mean, you say, “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.” Well, if it wasn’t “gone”, if you kept it somewhere for these special cases, wouldn’t that solve the problem?

    Also, typo: “I could peak at the next-door cube” – Should be “peek”.

  8. Zak McKracken says:

    Hmm… wouldn’t there be an efficient way of dealing with this by keeping tabs on which vertex belongs to which cube? If you can find more than two triangles sharing one edge, pick the one that also shares the same cube. This might be tricky since the faces are technically between cubes, but every face that has been generated means there’s a cube on one side an none on the other.

    Not that I had any idea of how to keep that sort of information around when working on a GPU using shaders …

    Another way I can think of is in case of kissing cubes, there would need to be two vertices in the same place, both associated to the faces of the different cube. I.e. the red-pink-blue chain would be logically separete from the cyan-green chain of edges, and the point where they meet would be two points who coincidentially have the same co-ordinate. Make sense?

  9. Corpital says:

    Very shakespearean post, I like it. Young love, unwanted by the authority, defying all attempts to break them up only to be separated forever at the end.

    • Geebs says:

      …and the real trouble happens when you force them to act independently with each unaware of the other’s status

      • Indeed. We’re just lucky there are no apothecaries in the graphics card.

      • Felblood says:

        Actually, this turns out to be the correct solution.

        When we detect kissing corners, we just tell the triangle stitcher to ignore one of the two cubes and come back to it later, so neither can affect the outcome of the other.

        In this case, this is accomplished by breaking the mass into two or more discreet solids, which might be a bit wasteful, but it accomplishes the goal.

  10. pearly says:

    “I try to feel bad about this.”

    You, almost literally, cut the Gordian Knot presented by this problem and it feels like cheating, almost certainly is cheating by some nebulous definition, but…

    No, I like that very much. Makes me smile.

  11. SteveDJ says:

    Does your lightsaber have to cut through the entire plane? Why not just use it to sever the kissing pair apart, but leave the other areas (i.e. D and G) unaffected?

  12. On the second diagram, there are repeated references to something purple. I don’t see anything purple there (although there is something pink which is perhaps being referred to as “purple”). I demand the presence of my colour!

    • ET says:

      It’s actually magenta, which is sort of like a neon purple. That line’s also placed right next to some other weird colours, so the contrast/optical illusion-osity makes it look pink. :)

      • Volfram says:

        The technical definition should be “Not-Green,” which is why the Subtractive colors are what they are. They’re literally “everything but what we’re subtracting.”

        Magenta = Purple to me, but the exact lines between Purple, Pink, and Orange(I actually use a light orange for skin tones in digital art) are kind of fuzzy.

        • ET says:

          Pure purple for me has about 1.5X to 2X the blue number than the red number, in RGB. So, fully saturated would be something like 0x9600FF for me. :) Pure magenta has equal parts red and blue. Now, where the actual boundary lines between blue, red, magenta and purple are…I could do it, but I’d need to write up some special help-me-name-colours program, which would be waaay to much work. :P

    • I don’t know about you but I prefer to use The Pink Panther as my reference for what is “Pink”.

      For those curious The Pink Panther originates from the opening sequence from the movie of the same name (made in 1963) starring the very talented Peter Sellers as Inspector Clouseau, which I suspect is a French pun for clueless.

      • ET says:

        I think exposure to media has a big effect on what you default to when asked to think of “pink”. For me, I grew up with a cousin who had a pile of Barbie dolls about two feet high*. So, I default to hot pink/Barbie pink when I need to think of “pink”. :)

        * I’m not exaggerating here. It was literally about two feet high, and about as many wide. Yeesh. ^^;

    • Max says:

      The color is a very bright purple, becuase the r and b values are maxed out. If you halve the values it looks much more like a stereotypical purple. Light purple is one of my favorite colors, along with dark yellow.

Leave a Reply

Comments are moderated and may not be posted immediately. Required fields are marked *

*
*

Thanks for joining the discussion. Be nice, don't post angry, and enjoy yourself. This is supposed to be fun.

You can enclose spoilers in <strike> tags like so:
<strike>Darth Vader is Luke's father!</strike>

You can make things italics like this:
Can you imagine having Darth Vader as your <i>father</i>?

You can make things bold like this:
I'm <b>very</b> glad Darth Vader isn't my father.

You can make links like this:
I'm reading about <a href="http://en.wikipedia.org/wiki/Darth_Vader">Darth Vader</a> on Wikipedia!