The Coverage Buffer (C-Buffer)
by (13 January 1999)



Return to The Archives
Introduction


As you probably know, there is a nice way to prevent overdraw in software rendering engines. It is called an 's-buffer', wich is basically a structure in wich you keep track of what parts of each scanline are filled with pixel data already. It can be filled with the spans that make up your polygon when you rasterize it. The s-buffer thus consists of either a linked list, or, slightly more advanced, a tree that holds the spans that where send to a specific scanline, in the correct order. When a new span is inserted somewhere where already a span is, the new span is either clipped, split, or rejected.


Examples


Some examples, the 'x' line is the new span, '=' means spans already in the tree:

      xxxxxxxxxxxx
             ============
In this case, the new span is clipped: A portion of the right side of this span is clipped of so that the new s-buffer for this screen line becomes:

      xxxxxxx============
One more example:
      xxxxxxxxxxxxxxxxxxxxxxxxxxxx
                ==========
In this case, the span is split in two parts, wich are both added to the tree. The result should be:

      xxxxxxxxxx==========xxxxxxxx
This of course requires that your spans are already correctly sorted, you should insert the nearest polygons or spans first, then the rest. When the entire s-buffer is filled (for each scanline on the screen) you can draw it. This requires of course that you stored not only the begin position and length of each span in the s-buffer, but also U/V information for the texturemapper. And maybe also U/V info for the phongshader, R/G/B info for the gouraud shader and U/V info for the bumpmapper. Bug plus is that the entire screen is filled sequentially once the s-buffer is ready: You draw s-buffer lines from left to right, so the screen is nicely filled, from left to right, top to bottom. To prevent massive storage of information in the s-buffer, you might ignore this potential cache advantage, and write each span directly to the screen. In that case, you only have to store the beginning of each span, and it's length. You could theoretically also write an s-buffer algorithm that doesn't require the spans to be z-sorted. In that case, you take the depth of each span into account, so that you can split a span that halfway an existing span goes behind it. This kind of s-buffer is extremely difficult to implement, in my opinion; if you really need perfect sorting you could better use a BSP renderer and the s-buffer I just described.


C-Buffer


If you chose the first variant I described, you can now proceed to the c-buffer, wich was first explained to me by Edward Kmett (of Harmless Entertainment).

For the c-buffer, you must draw your spans directly to the screen. As you might have noticed, the data in the s-buffer now only tells you wich areas are already filled, and wich not. So, you could as well link spans that are exactly next to each other... So, whenever a span gets clipped on the left side because there was already a span at that position, you do the clipping (because you need the clipped info for drawing this span) and then you simply extend the span that caused the clip with the length of the clipped span. Ideally, at the end of the rendering process each scanline on screen should be represented by a SINGLE entry in the s-buffer (which should now be called a c-buffer). You can imagine that this is a huge performance boost for complex scenes, especially compared to the classic s-buffer, where you would have to traverse an enormous linked list for each inserted span, even if the inserted span is just a few pixels...


Closing


The biggest advantage of this algorithm is probably that it makes software rendering a lot more like hardware rendering. Normally, software rendering suffers enormously from overdraw, especially when you use more complex rasterizers like bumpmappers or phongshaders. Hardware is much more tolerant, since the fill-rate is usually very high. Advanced techniques to cut down overdraw are usually not worth the trouble on hardware ('let the z-buffer sort 'm out') but absolutely neccessary in software. With the c-buffer however, you can just toss huge polygons to your screen without worying: The visible pixels count, and nothing more. This should make it slightly easier to write a 3D engine that runs both on software and hardware, without huge architectural differences.

Enjoy life,
Jacco Bikker - a.k.a. "THE PHANTOM"

 

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.