Home       About Me       Contact       Downloads       Part 30    Part 32   

Part 31: Decals

September 2, 2011

Fig 1: Part 4 block selection
All the way back in Part 4, I had a UI for creating and destroying blocks. In all the versions since then, this UI has never reappeared. Why not?

The feature I needed was the ability to highlight the selected block (see Figure 1.) This isn't as simple as it looks.

In the part 4 code, I was drawing each cube independently each frame, not buffering them. That meant that when the UI needed to highlight a cube, it could just draw the highlight texture (the black box) when the cube was drawn, using multi-texturing of the cube faces.

In later parts, I switched to using vertex and index buffers to draw batches of cubes, so that all the vertexes could be moved to the display and drawn with a single call. In that code, I had no way to highlight a cube, because I couldn't change a cube without rebuilding the entire buffer.

Without the ability to highlight a cube, there's no way for the user to know which cube he's about to delete or add next to. So the whole UI and ability to modify the landscape disappeared from the demos.

I knew that adding highlighting back in was going to be a hassle, so I kept putting it off. But if I want to release a playable demo again, it has to be there. Here's what I did.

Let the Shader Do It!

Fig 2: Octree blocks have different sizes
I currently have a custom shader for drawing my cubes. It takes the compressed vertex format I described in Part 16. If I modify this, I can have it take the selected cube as a parameter, and just add the highlight when it draws this cube in the buffer. However, there are some problems with this approach.

First, since I'm using an Octree, cubes come in different sizes (see Figure 2). If a 4 by 4 cube face is showing, and I want to highlight just one cube, I can't simply texture the entire face. I would get a 4 by 4 grid of frames. Instead, I have to give the shader a bit more information. In that special case, there would be an offset for the position of the highlight texture. In the fragment shader, I can make sure only a portion of the face is highlighted.

Next, there's the question of how to identify which cube I want highlighted. Each cube generates up to 6 faces of 4 vertexes. Adjacent cubes touch, and so a vertex like (x,y,z) = (10,10,10) might actually be shared by eight cubes. So I can't use the coordinates to identify the selected cube.

Instead, I have to keep track of which vertexes belong to which cubes. OpenGL keeps a "VertexID" which the shader can read. This is the sequence number of the vertex in the buffer, from 0 to N-1. Assuming I draw all the faces of my cube in sequence (I do), I can give the shader a range of vertex IDs to check for. If a vertex is within this range, the vertex shader can tell the fragment shader to multi-texture that triangle with the selection frame.

Fig 3: How to draw this in the shader?

But the big problem for this approach is non-cubical shapes (see Figure 3). If I want a highlight box around the sphere, steps or columns, I can't draw that in the shader. The box vertexes just aren't in the shape being drawn. Without a geometry shader (which I don't have in OpenGL 2.1), I can't create them. So I'm stuck.

I thought about just adding a box to all the shapes. The box vertexes would have to be marked so that they aren't drawn all the time, but only when there's a selection. I could do this with the steps and columns, since the shader can specify the points I need. But on the spheres, I would need to change the interface of the shader. The current sphere is a single color, not even a texture, so it has no texture coordinates.

Staying with the shader-based approach means that all future block shapes also have to be able to draw a cube, so that I can draw the highlight. And I have to put the code for highlighting in the shaders for each shape, and it has to be written in both OpenGL 2.1 and OpenGL 3.3 flavors.

After my previous experience with shaders, I'm also a bit nervous about putting a lot of conditional logic in them. They are great when it comes to multiplies, texturing, etc., but terrible when it comes to loops and array subscripts and conditionals. I worry that if I put a lot of this code in the shaders, I will regret it on slow displays.

Also, I keep running into weird issues with shaders. This time, I notice there's a "bool" type in the shader language. I naturally use it for my "selected" flag. Then I discover that for reasons only known to standards committees and the insane, you cannot pass a bool from the vertex shader to the fragment shader. I have to use an "int." Not a problem, just one of those things that make you wonder what they were thinking.

In any case, after fooling with my shaders and testing them on all my machines, I decide I don't like this approach.


Fig 4: A stencil selects the area to be textured
I could also do this with a decal. This is bit of transparent graphics, like a crack or bullet hole, added into the scene after it's drawn. I thought this would be perfect. I could draw the entire scene and just add the selection texture as the last bit of graphics.

I had never implemented a decal before. If you just draw a transparent triangle in the same location as an opaque one, you get z-fighting. This happens when the two triangles are drawn slightly differently by the hardware. At some pixels, the first triangle will be closer, and at other pixels, the second triangle. So some of the decal would be eliminated by the depth test.

I looked up decals, and read that you avoid this by using the stencil buffer. This is a bit mask over your graphics. With this enabled, only pixels where there is a "1" in the stencil will be drawn. The problem is to get this bit pattern generated in the first place.

To do that, they tell you to draw your background, setting the stencil function to record which pixels are drawn, and which are eliminated because they are behind some other object. This would leave you with a mask of only the visible portions. In Figure 4, it would be the top face of the gray stone, clipped by the closer grass block.

Once you have this stencil mask, you can turn off depth testing and just draw the transparent stencil. It will overwrite the existing graphics unconditionally (no z fighting), but be masked by the stencil. Without the stencil, turning off the depth test would just draw the black frame through the surrounding grass.

I implemented this, and it didn't work. It took me awhile to realize why. I was drawing the entire scene, then drawing the face of the cube I wanted to select (with the stencil enabled), then drawing the selection pattern (with depth testing disabled.) But nothing was happening.

Fig 5: Z-fighting when vertexes are not identical
The problem is that the top face of the stone is already in the scene, because I drew the entire scene first. So when I draw it again, the depth test fails and the stencil is all zeros. So none of the selection texture is drawn.

The right way to fix this would be to eliminate that face from the vertex buffer, and draw it later, with the stencil enabled. I can't do that, since eliminating the face means rebuilding the vertex buffer.

What I did was change the depth function, from the default "less than", to "less than or equal." This means the second draw of the cube face is not eliminated and does set the stencil, without having to change the original vertex buffer.

The problem with this is that the vertexes have to be identical on the two passes, or the hardware could draw them differently. In the cube case, this doesn't happen. But for the step shape, it actually does. See Figure 5.

The step shape is half as high as a cube. Even though the midpoints are in the same plane as the full cube face, the different vertexes mean the hardware can draw the triangle boundaries differently. Then, depending on your exact position, some points are nearer than others. This is z-fighting, and the results of this depth test cause the stencil to have this same pattern of bits, which ruins the selection texture.

One way to fix this for steps would be to have a custom selection pattern with the same height, and yet another drawing method, which decals the shorter selection texture onto the shorter step faces.

Fig 6: Not like this...
Fig 7: Part 4 did it right

I was reasonably happy with this though, until I ran into the case I should have expected all along. My arch enemy -- transparency! As you can see in Figure 6, as far as the depth buffer is concerned, the transparent cubes are opaque (because they are closer). So the stencil buffer will not include those overlapped regions. The selection frame is clipped by the transparent cubes in front.

Even if the clipping were right, it would not solve the problem. The transparent cubes in front of the selection should change the color. The right look is what I had back in part 4, shown in Figure 7.

There is no way to fix this with decals applied at the end. The selection texture must be sorted into the scene and drawn in the right order with the transparent cubes.

Inserting the Decals

Fig 8: Selected bricks are transparent
Inserting the decals isn't really hard -- it's just a bit ugly. I currently generate all the cube vertexes by traversing my Octree. There are two passes -- one for opaque and one for transparent. This is because the transparent cubes are sorted and re-sorted as you move.

Whenever the selected brick changes, I need to traverse the Octree again to find it. I keep track of how many indexes I've written to the index buffer. When the selected brick is seen, I record the current position and the number of indexes generated by the shape (currently: cube, sphere, step, or column).

With the position of the brick in the index buffer known, I can split the buffer. I draw the part up to the selected brick, then the part after. This removes the brick from the scene without rebuilding the buffers.

The selected brick is drawn during the transparent pass. I split that buffer as well, drawing everything before the insert position. Then I draw the selected brick with its frame. The scene is finished by drawing the rest of the transparent data after the insert position. If the selected brick is transparent, the insert position will be the normal position of that brick.

I originally thought I could decal the opaque bricks in place. But if you consider Figure 8, you'll see this doesn't work. The frame turns the opaque sphere into a transparent brick -- you can see the background scenery through it. So it has to be rendered in the correct order for transparent bricks.

This isn't much additional code, it doesn't require special shaders, and the performance is fine. It does require some extra time whenever the selected cube changes, but that's tolerable.

Coming Soon

So now I have selection highlighting again. Yay! There's no video or demo this week, but next week should see Crafty return in usable form.

Home       About Me       Contact       Downloads       Part 30    Part 32   

blog comments powered by Disqus