|
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" |
|
|