Visualization of Volume Intersections

Visualization of Volume Intersections

Introduction

The trendy thing in real-time rendering these days is ray-tracing. However, traditional rasterization hasn’t disappeared, and it won’t in the near future. I recommend this blog post on the subject: A hybrid rendering pipeline for realtime rendering: (When) is raytracing worth it? 

I find that one of the most neglected elements in the rasterization pipeline is the Stencil Buffer. To get an idea of how neglected it is, I’ve checked the number of appearances of the stencil buffer in the approximately 1000 pages of “Real-Time Rendering”[1]: it appears just 5 times, and there are no more than 4 paragraphs dedicated to it. At least for me, it’s hard to get my head around the stencil buffer because it’s not fully programmable, so I tend to avoid using it. You can only configure it, and to do so you have to think of Boolean algebra, but in 3D.

This blog post is an attempt to demystify the stencil buffer. I will briefly review the rendering pipeline, to see where the stencil sits, and then explain how the stencil works. I will use an example application in WebGL that we use to detect volume intersections, and explain the steps to convert the algorithm in my head to a tabular format that can be used to configure the stencil.

The Rasterization Rendering Pipeline

Rasterization Rendering Pipeline

Rasterization Rendering Pipeline in the GPU. Some stages are fully programmable, others are configurable, and others are completely fixed.

Virtually every GPU implements a rendering pipeline like the one above. In the middle row I tried to illustrate the transformations that we apply to our models until they become an image on the screen. In the vertex shader, we receive the triangles that make up the surface of our 3D model. Then, our vertex shader will apply a series of matrix multiplications to those triangles to convert from the model space (origin of coordinates centered around the model), to world space (origin of coordinates in the world origin), and then to camera space (origin of coordinates in the camera). Then, we apply a projection transform (perspective or orthographic), so the camera frustum becomes a unit cube. Whatever is outside that unit cube gets clipped, and mapped to screen coordinates. Then the rasterizer converts those triangles into pixels, interpolating color values between vertices. Then we can apply operations per pixel in our pixel shader, and blend the result into the frame buffer that we see on screen, in the merger stage.

The merger stage: blending, Z-buffer, and stencil

That merger stage does mainly 2 types of operations: blending and discarding pixels. The blending, or Alpha Blending, blends pixel colors of our object with the colors already in the frame buffer based on the alpha value of the texture of the object. The alpha value is typically 8-bit, so there are only 256 possible values. We can also use the alpha value to discard pixels as well, based on a threshold. Pixels with a value smaller than the threshold will be discarded. That’s referred to as alpha masking.

Pixels can also be discarded thanks to the Z-buffer. The Z-buffer contains the distance (Z) from the camera to the objects in the scene. Say we have rendered the mountain from the illustration above, and now we try to render a tree that’s behind the mountain. The Z-buffer contains the distance to the camera for every pixel of the mountain. We can compare the Z values of the tree, and discard them if the new Z value is greater than the Z we have already. The tree won’t render. Notice that if we change the rendering order and render the tree first, it will get rendered. However, once we draw the mountain the Z-test won’t fail, so the mountain will be rendered on top. So some pixels will be drawn over several times. That’s what we call the overdraw, which can be used to measure efficiency. Sorting the scene is a way of reducing the overdraw.

Lastly, we can use the stencil buffer to discard pixels as well. The stencil buffer is typically an 8-bit buffer, so 256 distinct values are possible. In its simplest form, it can be used as an alpha mask. Say that we are seeing the mountain through a window, and we want to hide everything else. We can mark the pixels that belong to the window with an arbitrary number in the stencil buffer, e.g. a 1 signifies a pixel from the window, and then we configure the stencil buffer to discard everything that it’s not labeled as “window”. When combined with the Z-buffer, the stencil buffer can be used as a powerful tool to create volumetric effects, as we will see in the example later on.

Stencil buffer configuration

To configure the stencil buffer we have 3 types of settings:

  • Comparison functions. This is the function used to decide whether to discard a pixel or not. For instance, “greater than”, or “less than”. See: available stencil functions in WebGL.
  • Mask values. These are 8-bit binary masks. There are 3 types of masks: reference, read mask, and write mask. In WebGL, the reference and read mask are set with the stencil function, whereas the write mask is set with the stencil mask. The reference and read mask are used in conjunction with the comparison function. For instance, if the comparison is set to “greater than”, the stencil test will pass if (refMask & readMask) > (stencil & readMask), where “&” is a bitwise binary AND operation. The write mask gets applied to what we write to the stencil buffer if the test passes and we decide to update it.
  • Stencil operations. These are actions that can be configured in case of a successful or a failed test. You can do things like keep the current stencil value, replace it, or increment it. See: available stencil ops in WebGL. The actions can be configured for the 3 following conditions:
    • fail: the stencil test fails
    • z-fail: the z-test fails (see Z-buffer in previous section)
    • z-pass: both the stencil and the z-test pass.

Writing it down as one big logical operation, for each pixel, the new value of the stencil buffer can be computed as follows:

if (refMask & readMask) Comparison (stencil & readMask): 
    stencil_new = (stencil & ~writeMask) | (writeMask & Operation(stencil))

It does sound very abstract, doesn’t it? How do all these logical operations become something useful? I hope with the example in the next section you learn how to configure the stencil.

Visualizing volume intersections with the stencil buffer

Visualization of cube intersections and back faces

Visualization of cube intersections and back faces

Problem definition

Let start with the problem definition. We want to visualize the volume intersections in a mesh, and any open areas of the mesh. This is a quick way of visually detecting if a mesh is watertight, i.e. the mesh contains no holes and it’s clearly defined inside. Holes are easy to visualize if we render the object in 2 passes. A vertex has 2 sides, front and back. Whether a side is front or back is decided by an arbitrary vertex winding order (it can be configured). When rendering, back faces are usually not rendered, but this culling is one of those things that can be configured in the render pipeline. So we can do a first pass where we render only the back faces in a bright green color, and then a normal pass where we render the rest. If we see green on screen that means that the mesh has a hole in there.

Configuration for volume intersection

For the volume intersection things get a bit more complicated. I know that the stencil should be useful in this, but how do we set it up? I always start writing down on the white board all the examples of triangle layerings that I can think of. Then, I know that in the end I want a stencil mask that marks exactly the intersection area in the given example. What operations can take me there? There are multiple. The challenge is to find one that works for all the examples you’ve written down. There must be a better way to draw this, but this is what I got:

Stencil Configuration by Example

Stencil Configuration by Example. We are trying to figure out a way to create mask for areas of volume intersections.

Then, once I think I have all the cases I need, I try to fill in a table with all the stencil configuration per render pass. From the picture above, you can see that the way I designed it, I’m going to need at least 3 passes:

  • one to render the back faces, where I count the number of back-facing polygons;
  • a second pass to render the front faces and decrease the counter if the z-test fails. We will avoid writing onto the Z-buffer so we can distinguish those 2 circled cases (where front-face B is rendered before front-face A). Because during the back pass we update the Z-buffer, the Z-buffer before starting the 2nd pass contains the z value of the back face closer to the camera. In the non-intersecting example, the order doesn’t matter, because whether the Z-buffer contains the z of the back-face or the z of B, we can detect a z-test failure when trying to draw A and decrease the counter. But in the intersecting example, if we draw face B first and update the Z-buffer, when trying to draw face A the z-test will fail and we will wrongly decrease the counter. To solve this without having to sort the geometry, we will stop all Z-buffer updates (Z-write off) during this pass.
  • a third pass to create a binary mask with the intersection area.
  • I can add an optional 4th pass to render the lighting of the non-intersecting volumes.

Here’s my final stencil table:

Pass Func Ref Read Mask Write Mask Fail? Z-fail? Pass? Z-write
Back ALWAYS 0 0 0xf~f KEEP INCR INCR ON
Front ALWAYS 0 0 0xf~f KEEP DECR KEEP OFF
Front – intersection LESS 0x1 0xf~f 0xf~f KEEP KEEP KEEP ON
Front – light GEQUAL 0x1 0xf~f 0xf~f KEEP KEEP KEEP ON

 

If you want to check how that translates into code, check this pull request in GitHub: self-intersections for WebGL Model Viewer.

Visualization results

Here’s a video of the WebGL Model Viewer in action:

The green areas are back faces, so holes in the mesh, whereas the red areas are the volume intersections. One application of this is to help us spot issues in poses in our avatars. If part of the arm intersects with the chest, we will have problems when trying to dress the avatar with a shirt, because the sleeve will also try to enter the chest and the cloth simulation will struggle. See example below:

Volume intersections and cloth simulation

The visualization of volume intersections (middle) can warn us about future problems in cloth simulation (right).

 

Conclusion

Rasterization is still the most used rendering pipeline in real time graphics. Inside the rasterizer, the Stencil Buffer seems to be the ugly duckling no one wants to hang around with, perhaps only reserved to big graphic gurus. I have showed you with a practical example that we can use the stencil buffer to visualize volume intersections in real time, and that the stencil is not as scary if we describe the problem with examples and in tabular form.

Visualizing volume intersections in real time has a practical application for us. When we author poses for our avatars, we can immediately see if a pose will end up having cloth simulation problems, and correct the limb position accordingly.

For more applications of the stencil buffer, check the “Real-Time Rendering” book [1], and the Wikipedia article.

References

[1] Tomas Akenine-Möller, Eric Haines, Naty Hoffman. Real-Time Rendering, Third Edition. A K Peters, 2008.