Internal
Much of this information is internal documentation. Care has not been made to make links work and make the documentation conprehensible for outsiders.

Clipping is the operation by which the display of graphical primitives is limited to an area of the screen. One way to achieve clipping in object space is to analytically clip the primitives to the shape. This is fairly easy for simples shapes, e.g. clipping lines on a rectangular clipping region, and can be used to quickly discard objects that do not intersect the clipping region. For general clipping with arbitrary shapes, image precision techniques are necessary.

Image precision techniques do the clipping at the very last stage of display, once the primitives have been turned into pixels (called “fragments” in OpenGL). In OpenGL, there are two ways to achieve this type of clipping:

  1. scissoring, which is limited to clipping to

a rectangle parallel to the screen;

  1. using the stencil buffer, which has no

such limitations but requires a stencil buffer

  (not provided by all OpenGL implementations).
  • - The Stencil Buffer —

The stencil buffer is usually an 8-bit deep buffer and therefore can contain values between 0 and 255 (well, on our HP Kayak machines it is actually only 4 bits, i.e. values in 0-15). When stenciling is enabled (glEnable(GL_STENCIL_TEST)), the fragments go through the stencil test just before the depth test. The stencil test accepts or discards the fragment based on the result of test (ref cmp stencil) where

  1. stencil is the value of the stencil buffer at the

position of the fragment location;

  1. cmp is a numeric comparison operator such as < or ⇐,

or the special values Always or Never;

  1. ref is a reference value.

cmp and ref are set by glStencilFunc.

In addition, as a “side effect”, the stencil test can also change the content of the stencil buffer at the location of the fragment according to the result of the test. The available operations are:

  1. do nothing
  2. set stencil to zero
  3. set stencil to the ref value specified in stencil test
  4. increment or decrement stencil
  5. invert stencil

A different operation can be specified for each of the three following cases:

  1. the fragment fails the stencil test (fail)
  2. the fragment passes the stencil test but fails the depth test (zfail)
  3. the fragment passes both the stencil test and the depth test (pass)

These operations are specified with glStencilOp.

The only way to write to the stencil buffer is using this “side-effect” via these operations. This means that writing the stencil buffer occurs as a side effect of fragments going through the OpenGL pipeline. To change the contents of the stencil buffer without drawing to the screen, you need to enable the stencil operation and disable drawing to the framebuffer.

Finally a stencil mask can be set with glStencilMask to define which plane masks of the stencil buffer are written by the operations above. This can be used for example to simulate several independent stencil buffers.

When implemented in hardware, the stencil buffer is (should be) very efficient. In a display that uses 24 bits per pixel, the stencil buffer is likely to use the extra 8 bits that make a 32-bit word. The stencil buffer can therefore be easily cleared with the main framebuffer, with no additional cost.

The stencil buffer is described in pages 385-391 of the “red book”. Some applications of the stencil buffer are described in chapter 14.

  • - Clipping with the stencil buffer —-

Clipping with the stencil buffer involves three steps:

1. drawing the clipping shape in the stencil buffer, e.g.
   by clearing the stencil buffer with the value 0
   and drawing the shape with value 1
2. enabling a stencil test that only accepts fragments where
   the stencil buffer is 1, and a stencil operation
   that does nothing (i.e. leaves the stencil unchanged)
3. drawing to the framebuffer as usual.

Since we can write the stencil buffer by setting the stencil operation, drawing to the stencil buffer (step 1 above) requires the following steps:

1. disabling drawing to the main framebuffer
2. enabling a stencil test that always accepts fragments
3. enabling a stencil operation that sets the values
   in the stencil buffer to 1.
4. drawing the clipping shape

Before using the stencil buffer, remember to clear it by specifying GL_STENCIL_BUFFER_BIT in the call to glClear. The value set when clearing the stencil buffer is defined with glClearStencil. We use 0 in the following algorithms.

  • - Multiple clipping shapes —

If we want to implement a window system with overlapping windows, we need to maintain several clipping shapes (1 per window). In addition, we need to manage the overlapping of windows so that drawing to a window is clipped not only by the window itself but also by the windows on top of it.

Painter algorithm

The easiest way to do this is to use the classical painter algorithm, by drawing the windows back to front:

	clear the framebuffer
	for each window from back to front
		clear the stencil buffer
		draw the window shape in the stencil buffer
		enable clipping
		draw the window content

Note: we can draw the shape of the window on the screen at the same time we draw it in the stencil buffer, by enabling drawing to the frame buffer and drawing with the window background color.

The painter algorithm is expensive because

1. we need to clear the stencil buffer for each window 
  (clearing buffers is expensive)
2. if A overlaps B, we draw all of B, including the part
  that will later be hidden by A.

We can do better by drawing each window shape in the stencil buffer with a different value and enabling clipping for that value only. This saves the call to clear the stencil buffer for each window, but limits the number of windows to 254 (the background uses the value 0):

	clear the framebuffer and the stencil buffer
	i <- 1
	for each window from back to front
		draw the window shape in the stencil buffer with value i
		enable clipping with stencil test "= i"
		draw the window content
		i <- i+1

However we still waste time drawing pixels in parts of windows that are later overlapped.

Clip buffer algorithm

Let's visualize the content of the stencil buffer at the end of the algorithm above: each window shape has been drawn with a different value, from back to front. Therefore each pixel in the stencil buffer tells us which window is there. So by setting the stencil test to =i and drawing to the framebuffer, we write only to the visible parts of window i.

So, if we have less than 254 windows, we can draw all the window shapes in the stencil buffer at once:

	clear the stencil buffer
	i <- 1
	for each window w from back to front
		draw the window shape in the stencil buffer with value i
		i <- i + 1

We only need to redraw the stencil buffer when the location or size of windows changes, or when a window is created or destroyed. Let's call the resulting buffer the clip buffer.

Drawing the contents of the windows can now be done by enabling the proper clipping mode and drawing each window, in any order:

	clear the frame buffer
	for each window w
		enable clipping with stencil test =id(w)
		draw window content

With this method, we only display pixels that are actually visible. Since drawing the window content can be done in any order, it is possible to optimize redisplay accross windows. For example, all objects that use a given texture could be drawn in sequence, or all transparent objects could be drawn together to minimize switching between textures and/or display modes.

If we have more than 254 windows, we can still use the clip buffer technique by drawing the windows in batches:

	for each batch of 254 windows, back to front
		clear the stencil buffer
		draw the clip buffer for these windows
		draw the content of these windows

Variant of the clip buffer

Drawing the clip buffer can be optimized by drawing the window shapes front to back. This avoids drawing the parts of windows that are later overlapped in the stencil buffer:

	clear the stencil buffer with value 0
	i <- 1
	enable stencil test with "i > stencil"
	for each window w from front to back
		draw the window shape in the stencil buffer with value numStencils-i
		i <- i + 1

The stencil buffer starts filled with zeroes. When we draw the shape of window i, only the windows 1 through i-1 have been drawn in the clip buffer, so the stencil buffers only contains the values [0+i-1..numStencils], where numStencils is the number of possible different stencil “layers”. Therefore the stencil test “numStencils-i > stencil” really means ”= 0”, i.e. draw the i-th window shape only where no other window has been drawn yet. In other words, only the visible part of a window is drawn.

We need to use the stencil test “numStencils-i > stencil” rather than “0 = stencil” because the stencil operation is set to “replace” and the value used by the stencil operation is the same as the one used by the stencil test (called ref in the description of the stencil buffer at the beginning of this document).

The test “numStencils-i > stenciol” actually gives us more flexibility that “0 = stencil”: it lets us draw the window shapes in any order, under the condition that the window numbers have been assigned from 1 to n in back to front order. Drawing front to back is the optimal order since it does not write any fragment that will be overwritten, but any other order will give a proper result.

  • - Transparency —

To get proper results, transparent objects need to be drawn after all the objects they overlap. With the algorithms above, transparent objects that are displayed inside windows will be drawn correctly as long as the window itself is opaque.

But if we want to manage windows with a transparent background, such as toolglasses, we need to be careful. First, we need to draw each transparent window after all the windows that it overlaps. This can be done easily by drawing the windows back to front in the Variant of the clip buffer algorithm. Second, we cannot draw the shape of the transparent window in the stencil buffer in advance, as we did in the clip buffer algorithm, since this would prevent from drawing in the areas of the underlying windows that are overlapped by a transparent window: if A is on top of B and B is on top of C, and B is transparent, we can see parts of C through B and therefore we cannot draw the shape of B in the clip buffer because it would hide visible parts of C. If we assume that all windows with transparent backgrounds are above al opaque windows, the latter problem does not occur. So the variant of the clip buffer algorithm will work in this case.

Before presenting a general algorithm, we should note that some applications could solve the problem with simple tricks. For example, if the shape of the transparent window is a rectangle, clipping for this window could be done by scissorring rather than with the stencil buffer. Alternatively if all transparent windows are on top of all opaque windows and they can do their clipping analytically, you can use the above clip buffer algorithm and draw the transparent windows without the stencil buffer.

The general algorithm described here requires redrawing the stencil buffer with each frame, but with exactly one clear of the stencil buffer. The algorithm assumes that the total number of windows (opaque and transparent) is less than 254, but the same technique as described in the previous section can be used if there are 255 or more windows.

First the opaque windows are assigned a number from 1 to n in back-to-front order. The algorithm then draws all the opaque windows using the clip buffer algorithm (or it's variant). Then it assigns numbers 1 to m to all windows with transparent background back to front, and draws all the transparent windows (in this order) updating the clip buffer before drawing each window's content:

	clear the frame and stencil buffers
        i <- 1;
	foreach opaque window w from front to back
		set stencil test to 'numStencils-i > stencil'
		set stencil op to replace passed fragments
		set current color to window background
		draw window background
		set stencil test to 'numStencils-i > stencil'
		set stencil op to do nothing
		draw window content
                i <- i + 1
	enable blending
        i <- 1
	foreach transparent window w from back to front
		set stencil test to 'i > stencil'
		set stencil op to replace
		set current color to window background
		draw window background
		set stencil test to 'i = stencil'
		set stencil op to do nothing
		draw window content
                i <- i + 1
	disable blending

Notes:

  1. the first loop above could draw windows in any order.

Front to back is the optimal order.

  1. the first loop above could be split into two loops:

one to create the clip buffer and one to draw the

  window content. Each loop could go through the
  windows in any order.
- the second loop above //must// go through the transparent
  windows back to front and //must// draw the window shape
  and the window contents in sequence. Otherwise, blending
  would not create the proper transparency effects.
- the window background is drawn in the frame buffer
  at the same time the window shape is written to the
  clip buffer. Note that texture, lighting, etc. could
  be enable to draw more fancy backgrounds.
  • - Subwindows —

Some windows systems such as XWindow implement a hierarchy of windows, where windows can contain subwindows. The visible area of a window is clipped by its parent window. The clip buffer algorithm can be easily extended to support subwindows, assuming that we have less than 254 windows and subwindows in the tree.

The trick is to assign window numbers so that the window number of a window is strictly greater than the window numbers of its subwindows. This is accomplished with a prefix traversal of the window tree:

	int assignWinNumber (w, i) {
		foreach subwindow s of w from front to back {
			i <- assignWinNumber (s, i)
		}
		id(w) <- i-1
		return i-1
	}
	
	assignWinNumber (root, numWindows)

To draw the clip buffer, we draw each window and then it's subwindows, all in front to back order:

	int drawClipBuffer (w) {
		set stencil test to < id(w)
		set color to window background
		draw window shape
		foreach subwindow s of w from front to back
			drawClipBuffer (s)
	}
	
	set stencil op to replace
	drawClipBuffer (root)

When drawing a window “w”, the windows already in the clip buffer are:

  1. the ancestors of w in the tree, which have a number < id(w).
  2. the siblings of w that are in front of w and their subtrees,

which all have a number > id(w)

  1. the siblings of the ancestors of w that are in front

of the ancestor, which all have a number > id(w) Drawing “w” with the stencil test ”< id(w)” ensures that the window is drawn only inside it's ancestors without hiding any window if front of it or one of its ancestors.

Note that this algorithm is not optimal since it draws the parts of a parent window that are overlapped by it's subtree.

With this algorithm, drawing in a window will be clipped by its subwindows, which is the default mode in XWindows. To draw in a window on top of its subwindows, the generation of the clip buffer must be combined with the drawing of the windows content in a way similar to the general algorithm for transparency. The pseudo-code for the algorithm is left as an exercise for the reader.

Finally, combining subwindows and transparency seems possible but hasn't been fully investigated, as well as supporting more than 255 windows. Let me know if you come up with a algorithms for these cases…