# 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 spans

When 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.

## 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)

NNNNNNNNNNN

Now, 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 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.

## 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 Subroutine

## Painting 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 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.

Tom Hammersley, tomh@globalnet.co.uk