Nesting and Overlapping Translucent Stenciled Windows

Mouthful of a title... This post is about using the stencil buffer to clip window contents, where the windows can be layered or nested (subwindows) and might be see-through. It's also an example of the common experience programmers have with falling through of plans leading to scope expansion.

If dominoes were tangents...

There's the game I'm obstensibly working on... then there's a little subset of rules for mage versus mage non-lethal combat... so I put a little framework together to test these combat rules, which would also stress the (incomplete) GUI a bit more. This proceeded well enough, but I wanted text feedback about what was happening in this mage-duel -- so a little scrolling logger.

Zen of Clipping: leave it to the window system!

The GUI didn't have a way to clip contents to a region yet. Having menu entries extend off the top and bottom of the screen, or text spilling outside of the box it's in... unacceptable. This GUI was used to make a font-browser, and rather than scrolling a list of fonts in a contained box, I drag the giant list up or down off the screen, as shown to the right. Pretty silly. It was time to face this issue.

Oh, I also needed scrolling -- just an extra offset for positioning will do it...

To clip contents I figured I'd use scissoring (glScissor). This is just a simple screen-based clipping rectangle. In practice the GUI would probably only use boxes anyway.

This should be easy. An hour or two.

One week later...

(fig 2) Nesting, overlapping, translucent, shaped, and transformed windows.
Contents of Red are trimmed to its edges, including the round corners. Nested
windows create their own clipped sub-regions while still respecting their parent.

Plans changed... Scissoring was unsatisfactory because windows can have some detailing to their shape (such as the rounded corners, above). Ideally I'd want that very same shape to affect clipping, rather than clipping to some invisible box pulled inward by a safe distance from the window edges. Two alternatives were under consideration for shaped clipping: the stencil buffer, or render-to-texture.

One choice leads to another: if we have arbitrary clipping... that means we can have arbitrary transforms! And if we have transforms (ie. perspective) I'm going to disfavor render-to-texture. This is because rendering the resultant image with potential scaling and rotation suffers the usual texture-sampling limits. (Think of a prerendered page of text rotated or scaled.) Blech. So, stencil it is! One thing I would have liked render-to-texture for is anti-aliasing or alpha-fade on the edge. However, it's easy enough to hide the ragged stencil-edge under a frame.

Leveraging the Stencil Buffer

I had never used the stencil buffer before (okay, some simple use long ago), so I spent a day playing with different ideas, thinking there must be a way to render stencils which can nest or overlap and allow transparent objects to render in correct order. I knew hierarchical bitfields would suffice, but I wasn't sure I could make that work with the stencil operations and only 8 bits (hierarchical bitfields can chew up bits quickly).

This must be a common operation, right? Compositing window managers need to do this kind of thing, so someone's bound to have posted some ideal solution.

I found this page: Clipping in OpenGL. The page starts with basic stenciling, adds transparency, and then considers nested windows without transparency... As I read through it, it was looking promising. I should have jumped to the end, but it was building up so well I was sure it would culminate with what I sought! But at the end: "Finally, combining subwindows and transparency seems possible but hasn't been fully investigated, as well as supporting more than 255 windows."

Boooo!

After seeing the approaches used on that page, I struggled to find a solution which didn't involve hierarchical bitfields, because it was so tantalizing... If I could puzzle out the right order of writing stencil values and using them, maybe I'd only need one sequential stencil value per window (allowing 255 stenciled windows before clearing the stencil buffer). However, I think that was an exercise in futility, with the available stencil-buffer features. It could be done if there was an additional parameter: a "reference" value only for testing and a separate "write" value to update the stencil buffer with.

The Stencil Test

The stencil buffer is like the framebuffer or depthbuffer, but hasn't become such a common term to warrant joining the words. ;) Joking aside, it commonly has 8 bits per pixel. The stencil test has this form:

    keep_the_pixel = (value & mask) op (stencil & mask)

The "op" is a comparison operator, such as less, equal, not equal. These values are set-up using:

    glStencilFunc op value mask;

The remaining stencil value in the test comes from the stencil buffer. During render, any fragment failing this test is discarded. However, the stencil buffer itself can be updated on pass or failure. It can't be written to directly, but has several modes of updating... including increment and decrements, which were a tempting tease as these would work for nested windows, but fails once they can overlap.

For the application described here, op is always gl_equal, and the stencil buffer is only updated on successful write... meaning a fragment has to pass stencil, depth, and alpha testing. This last requirement permits using the alpha-channel to shape the stencil. Without using the fragment shader for "alpha stencil" we'd be limited to stencil shapes built of the polygonal shapes of the primitives.

We're using gl_equal to test specific bitpatterns, albeit masked, as shown in the next section. A more typical use of the stencil operations is to test for less-than or greater-than, without masking, and to either increment or decrement the value written -- this allows for sequential stenciling without needing to clear the stencil buffer, 255 times, before the buffer must be reset/cleared.

For a more in-depth look at stencil operations and an example: http://en.wikibooks.org/wiki/OpenGL_Programming/Stencil_buffer

Rendering with the Stencil Test

This code will set up for rendering a stenciled window with contents. For translucent objects, contents should be rendered in order, from farthest to nearest. The contents may include other stenciled windows, with this one as parent.

    (* Set to update stencil-buffer with value, when test succeeds *)
    glStencilOp gl_keep gl_keep gl_replace;

    (* Constrain stencil rendering to be within parent, but "value" will be written *)
    glStencilFunc gl_equal value parent.mask;

    glStencilMask 0xff; (* enable writing to stencil-buffer *)

    draw stencil_shape;

    glStencilMask 0;    (* disable writing to stencil-buffer *)

    (* Limit further rendering to be within stenciled area...
     * including children! *)
    glStencilFunc gl_equal value mask;

    render contents;

    (* Restore stencil state to that of parent *)
    glStencilFunc gl_equal parent.value parent.mask;

There are four special numbers needed, however: value, mask, parent.value, and parent.mask. Each stenciled window has a value and mask, and computing these is covered in the next section...

Hierarchical Bitfields

What do I mean by "hierarchical bitfields"? You might be familiar with an example: IP addresses. A "class C subnet" (ipv4), for example, has the top 24 bits (first three of the dotted quad) assigned, while the lower 8 bits are free to allocate within the subnet. So you can identify all machines on a subnet by a particular prefix: 203.144.16.xxx, while the individual machines are distinguished by the last byte of the address.

Unicode UTF-8 also uses a hierarchy: certain bit-patterns identify the need for additional bytes.

In our present case, we want stencil-patterns where we can match a masked set of bits to identify "containment". For example, if a parent window has a value of 0100 (in 4 bits), and corresponding mask of 1100... this means any value matching 01xx would be writable -- so the children of this window should all have patterns starting in 01.

The tree of stenciled windows from "fig 2" is shown to the right. We'll work with this as an example. The asterisk is the root window, containing 1 and 4. In "fig 2", the red window is window 1.

I'm going to demonstrate with a similar notation as an ip-address: dotted integers. Each step deeper in the tree adds an integer, and siblings are numbered sequentially with this integer. One more rule: a zero terminates, and represents "the remaining bits are zero". So the example would be written as:

(indentation used to show hierarchy)

    *     0
     1    1.0
      2   1.1.0
       3  1.1.1.0
     4    2.0
      5   2.1.0
      6   2.2.0

Now you can see that we can uniquely match any specific window, or a window and its children. "1" and its children all start with "1.", 4 and its children all start with "2." If we wanted to narrow down window 5 specifically, we need a mask which keeps the first two numbers: "2.1" -- masking the first two numbers, this is the only window which matches "2.1". By comparison, if we examine the first two numbers for "1.1", we get window 2 and its child, 3. With a value and a mask, we can pinpoint a specific window, or widen out to capture children encoded with this kind of "address".

These dotted integers are easily turned into a value and a mask. The essence of this transformation is determining the number of bits required to represent the tier. Take the number of siblings, add 1 for the parent (occupying the "zeroth" slot), and take the base2 log, rounded up, for the number of bits needed. So, off the root window we have two children: this is 2+1 = 3... number of bits needed for three values is 2, so the counting in binary is: 00, 01, 10. And these are the bits for our first "dotted integers". The corresponding mask is sufficient to reveal the significant bits -- or the total number of bits needed for the dotted integers, excluding the trailing zero:

   window  dotted-integers  value  mask
     *      0               0000   0000
     1      1.0             0100   1100
     2      1.1.0           0110   1110
     3      1.1.1.0         0111   1111
     4      2.0             1000   1100
     5      2.1.0           1001   1111
     6      2.2.0           1010   1111

Now these two numbers, value and mask, can be used to control stenciled rendering, allowing for nesting or overlap of windows.

All for a scrolling log-view.

If the available stencil bits are exceeded, the scene-graph can be managed as subtrees which fit within the limit of bits, and the stencil buffer cleared for each subtree. Not ideal. However, I don't think I'll exceed 8 bits in practice. I can imagine using stenciling for some widget and having dozens on the screen but that's okay -- it's nesting that cuts the available addressing in half, and I don't imagine too much nesting.

Oh yeah... the scrolling logger. That's what started this...