S-Buffering: The Latest Fad In Software Rendering
Introduction
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.
Fundamental Concepts
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
NNNNNNNIf we were to insert that span, we would first clip its left edge against the "current" span:
CCCCCCC
NNNNThen 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.
Span Overlap
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)
NNNNNNNNNNNNow, most of these are similar, and easy to solve. Lets see what we need to do for each case:
- Reject the new span, totally obscured. Trivial reject
- Break the new span into two pieces, and recur with them, or build new tree branches with them
- Either insert the new span to the right tree branch, or continue processing with curr->right tree branch. Trivial accept/loop cycle
- Either insert the new span to the left tree branch, or continue processing with curr->left tree branch. Trivial accept/loop cycle
- Trim off the portion of span thats obscured, and then perform (3) with the resulting piece. Note you will have to adjust texture pos etc
- Trim off the portion to the right, and then perform (4) with the resulting pieces.
- Simply use this span to root the tree
Data Structures
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 StructureSpan 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 IfA 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.
Pseudo Code For Insert Routine
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 SubroutinePainting The Span Tree
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 SubroutineThis 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
/
EThen 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 D8Will, 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 GGGGGGGGGGGGGGGGGGCould have a structure, stored in addition to the span tree, that stores:
AAABBB CCCCCCCC DDEEFF GGGGGGGGGGGGGGGGGG
111111 22222222 333333 444444444444444444So that if he tried to insert a span Z:
AAABBB CCCCCCCC DDEEFF GGGGGGGGGGGGGGGGGG
111111 22222222 333333 444444444444444444
ZZZZZZZZZZZZZIt could be quickly rejected, as long as G was not the tree root, say a part of the tree was
D
\
F
\
GI 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.
Tom Hammersley, tomh@globalnet.co.uk
