S-Buffering is pretty much one of the latest crazes in software rendering, especially since the release of Quake. (Update: I'm not sure if Quake uses S-Buffers exactly, or if its a variation on Edge Tables. I'll try and find out ... ) But what is it? It was originally described in a FAQ by Paul Nettle. However, I have seen literature being referenced going back much further than that. In simple, S-Buffering is used to reduce overdraw, by sorting and splitting spans. Hence Span-Buffering. Its often used where there is a large overhead when writing a pixel; for example perspective texture mapping, or true phong shading. It works best with systems dealing with a small-medium polygon load, and a large per-pixel overhead, with large polygons.
Span buffering is built about the concept of a span. But what is a span? A span is simply a horizontal row of pixels, all on the same scanline (Y), with a start, an end, and some fill information:
X <- Pixel XXXXXXX <- Span AAAAABBCCCCCDDDEE <- Row of screen built from multiple spansWhen rasterising our polygons, we convert them to spans, and insert them to some data structure. Commonly, this data structure is a linked list, which, has its benefits. However, I feel that a better structure for this is a binary tree (greets Jazzvibe :). You'll soon realize why later on.
Also we shall present spans to the renderer in front->back order. This means that we must clip new spans against existing spans; so that the new spans only fill "new" portions of screen. For example:
C = current span
N = new span
CCCCCCC
NNNNNNN
If we were to insert that span, we would first clip its left edge against
the "current" span:
CCCCCCC
NNNN
Then we would insert it to the right branch of "current"s binary tree; or,
if a branch already exists, we would then traverse that sub-branch.
This presents us with the problem of working out how to handle each case and sub-case of span-overlap; its quite an extensive problem, and is the key to obtaining fast performance from an s-buffer.
There are a number of cases that can occur when inserting spans; however a lot of them are similar, and so we can build an if() tree to handle them.
C = Current
N = New
1) CCCCCCCCCCC
NNNNNNNNN
2) CCCC
NNNNNNNNNNN
3) CCCCC
NNNNN
4) CCCCC
NNNNN
5) CCCCCC
NNNNNNN
6) CCCCCC
NNNNNNN
7) (no span)
NNNNNNNNNNN
Now, most of these are similar, and easy to solve. Lets see what we need to
do for each case:
Now, you may be wondering what kind of data structures we will need for this. Well, two things are needed; a table of span pointers for every scanline, and a span structure. Something like:
Structure Span
Integer x1
Integer x2
Integer Width
Colour colour
Texture Pointer texture
Integer u
Integer v
Integer du
Integer dv
Span Pointer left
Span Pointer right
End Structure
Span Pointer spantable[YResolution]
Initially, spantable will all be set to NULL. Also, as each new span is allocated/freed, its left and right members will also be set to NULL. These pointers will then be updated as we go. When we are complete, we will have a binary tree, storing that scanline. And, with this tree, we can traverse it, to give us scanline order - more on that later.
Now, some notes on inserting spans. Where above I said "insert" the span, I meant insert it to the part of the tree, so if you have a span that is totally to the right of the current span, you would do something like:
If Span.x1 > Current.x2 Then (totally to the right)
If Current.right == NULL Then
Current.right = Span
Return
Else
Current = Current.right
Next Loop
End If
End If
A similar piece of code would be used for the left. Note that in the above
cases, span overlap cases that are not trivial accept/reject will be reduced
to that by the use of clipping. Then it will simply become a case of
inserting the span, or traversing the corresponding branch.
The insert routine is perhaps the most critical routine in an S-Buffer engine; every span must pass through it, both its coding and design must provide for efficient operation. If the routine is slow, then inserting the span will take longer than the overdraw would have cost. Likewise if a very large number of polygons are processed, the benefits will disappear, as insert time rises sharply with the number of polygons, and this growth is only compensated for by the level of overdraw; too little overdraw, and it'll work *slower* than painters. With plenty of overdraw, it'll give speed gains.
A general "rule of thumb" for working out the efficiency is quite simply; the efficiency is the average time taken to insert a span, multiplied by the number of spans, divided by the level of overdraw. Its not very accurate, but it gives a crude estimate of the efficiency.
This should insert a span to the span tree. Note it doesn't handle case (7),
that is simple enough to do.
Subroute InsertSpan(Span Pointer span, Span Pointer current)
While((current != NULL) And (span != NULL))
If span.x1 > current.x2 Then
If current.right == NULL Then
current.right = span
Return
Else
current = current.right
Next While
End If
Else If span.x2 < current.x1 Then
If current.left == NULL Then
current.left = span
Return
Else
current = current.left
Next While
Else If span.x1 >= current.x1 Then
If span.x2 <= current.x2 Then
Free(span)
Return
End If
If span.x1 <= current.x2 Then
(you should adjust u, v here)
span.x1 = current.x2
span.width = span.x2 - span.x1
If current.right == NULL Then
current.right = span
Return
Else
current = current.right
Next While
End If
End If
Else If span.x1 < current.x1 Then
If span.x2 > current.x2 Then
newspan = NewCopyOfSpan(span)
span.x2 = current.x1
span.width = span.x2 - span.x1
newspan.x1 = current.x2
newspan.width = newspan.x2 - newspan.x1
If current.left == NULL Then
current.left = span
span = NULL
Else
InsertSpan(span, current.left)
End If
If current.right == NULL Then
current.right = newspan
Return
Else
InsertSpan(newspan, current.right)
End If
Else If span.x2 <= current.x2 Then
span.x2 = current.x1
span.width = span.x2 - span.x1
If current.left == NULL Then
current.left = span
Return
Else
current = current.left
Next While
End If
End If
End If
End While
End Subroutine
Painting the span tree is simple enough, just a recursive process. However, recursion may not be the most efficient process for this; I've been toying with the idea of including a span pointer called "parent", to let me climb back up the tree, without using recursion. Haven't tried it yet, but I might do soon. But, for now, heres pseudo code for a function to draw the span tree:
Subroutine DrawSpanTree(Span Pointer root)
If root.left != NULL Then
DrawSpanTree(root.left)
End If
DrawSpan(root)
If root.right != NULL Then
DrawSpanTree(root.right)
End If
End Subroutine
This routine is quite special; it gives us ascending X order. This is handy,
because it will maximize cache access. If you consider that your painters
algorithm or Z-Buffer render may be passing it polygons that could appear
anywhere. You could have one in the top left corner, then one in the bottom
right, then one in the centre, etc, etc. With S-Buffer, we are going from
top->bottom, then left->right. Very handy.
Again, this function needs to be optimized for fast performance. Also, I think it might be interesting to see if you can come up with a way of balancing the tree, so that both less recursion is used, and also the insert time should be reduced. If you consider the tree:
A
/------|-------\
B B B
/
C
/
D
/
E
Then inserting to (E) will be fairly expensive, as you have to go further
down the tree, examine more spans, and so on. But inserting to (B) will be
quick. However, the tree:
A1
/------^------\
B1 B2
/ \ / \
C1 C2 C3 C4
/ \ / \ / \ / \
D1 D2D3 D4D5 D6 D7 D8
Will, on average, have a roughly similar insert time for each level of the
tree. Inserting to any (C) will be a similar speed, as will (D) or (B). Note
that I say similar; tree structure is just one part of getting increased
speed; organizing the tree to have the minimum number of clipped spans will
also help matters, and even more so if you reduce the number of broken spans.
Coming back to this tree though, run the DrawSpanTree pseudo-code through
you head. You should find that we get the order:
[D1, C1, D2, B1, D3, C2, D4(, etc...)]. Thats the order of increasing X,
another benefit.
Also note that polygons over triangles will give an increased speed using S-Buffers, due to the reduction in the number of spans to process. Consider:
|------------| |------------| |AAAAAAAAAAAA| |AA\BBBBBBBBB| |AAAAAAAAAAAA| |AAAAA\BBBBBB| |AAAAAAAAAAAA|(1) vs |AAAAAAAA\BBB|(2) |AAAAAAAAAAAA| |AAAAAAAAAAA\| |------------| |------------|Case (2) will give us twice as many spans to insert as case (1). Similar increases may be found as the number of vertices increases.
Another point to consider is that of trivial rejection; if we could somehow build a structure containing the bounding spans of spans, then we could further increase the speed of trivial rejection. For example:
AAABBB CCCCCCCC DDEEFF GGGGGGGGGGGGGGGGGG
Could have a structure, stored in addition to the span tree, that stores:
AAABBB CCCCCCCC DDEEFF GGGGGGGGGGGGGGGGGG
111111 22222222 333333 444444444444444444
So that if he tried to insert a span Z:
AAABBB CCCCCCCC DDEEFF GGGGGGGGGGGGGGGGGG
111111 22222222 333333 444444444444444444
ZZZZZZZZZZZZZ
It could be quickly rejected, as long as G was not the tree root, say a part
of the tree was
D
\
F
\
G
I also tried a "span mask" to try and reject spans quickly. What I did was keep a bit mask of the pixels that were currently covered by spans, updating it as new spans were inserted. However, it had a flaw: It was crap.
Well, thats all I can think of for now. I'm going to explore the concept of spans a little further though, they seem pretty useful in a non-3D-accelerated system.