Hi all, Currently I am busy writing an S-buffer software renderer which should perform the rendering of flat-shaded 32-bit values into a buffer. For now I am using Paul Nettle''s (MidNight) algorithm, which uses linked lists and a not too efficient insertion routine. Does anyone know of a better span insertion algorithm than the one described in Paul Nettle''s S-buffer FAQ? (if you are interested, just search for it on the Net) I need the software renderer for formfactor calculations in a hemicube radiosity processor, so using hardware rasterisation is not desired. I could have used a Z-buffer renderer, but a well written S-buffer renderer is WAY faster than a Z-buffer renderer, especially when there is a lot of overdraw. For the radiosity purpose I even don''t need to rasterise the polygons. Thanks in advance for any answers, DaBit. (dabit@trybit.com, http://dabit.trybit.com)

One way to optimize it would be to replace the linked-list data structure with a self-balancing BST, like an AVL tree. Insert segments sorted by leftmost x value and when you do your segment comparisons you can go down the BST and isolate only the segments that occur after a given leftmost x value. I say you''d need a self-balancing BST because the insertion routine would seem to favor left side insertions.

SiCrane, thanks.

Do you know where I can find more information about AVL trees and the algorithm you described?

DaBit.

(note: Oops! something went wrong here. Read the next post...)


Edited by - DaBit on 1/17/00 7:04:31 AM

SiCrane, thanks.

Is it also possible to throw unsorted segments (in the X direction, that is) into this algorithm? The segments are not sorted when they are generated from the polygons.

Do you know where I can find more information about AVL trees and the algorithm you described?

DaBit.

The insertion routine is good, it just doesn''t take into account which segment is really infront. I have to admit that S-buffer insertion routines can make some real buggy code. What I did with mine is have code hat performs some of the basic node splits. Make sure you have a complete set of linked list functions. I gave up S-buffering because the engine I was working on just had to many segments in one scene. The memory requirements were huge, so I stopped before my insertion routine was finished, but I may try it agsin.

Domini

Here''s a copy of an e-mail I sent to Sphet regarding AVL trees. The ASCII art was bad to begin with. I''m sure it''s worse on the board. At this rate I should write it up as an article and get it posted here.

quote:

---

Background on AVL trees:

AVL trees were created by two guys: Adelson-Velskii and Landis. The idea is get a binary search tree that keeps it''s balance, so that the depth is O(lg n) in number of nodes. When the depth is O(lg n) most of the BST operations happen in O(lg n). A sorted insert of n elements is O(lg n^2) in a sorted linked list but only O(n lg n) in an AVL tree. Iteration of an AVL tree can also be done in O(n) time codes properly.

Implementation Details:

You keep height information on each node. The height of a node is the maximum of the height of it''s subnodes plus one. A leaf node has height 0 (or 1 depending on implementation). On an AVL tree the heights of two subnodes can only differ by two. If an insertion or deletion operation unbalances a node then you have to rebalance the nodes.

You rebalance nodes by rotating them:
In this case the right side is out of whack, so we rotate the top to get it better.
5
4 6 4
2 -> 2 5
1 3 1 3 6

There are four basic transforms:
3
2 T4 2
1 T3 --> 1 3
T1 T2 T1 T2 T3 T4

1
T1 2 2
T2 3 --> 1 3
T3 T4 T1 T2 T3 T4

3 1
2 T4 T1 2
1 T3 --> T2 3
T1 T2 T3 T4

1 3
T1 2 2 T4
T2 3 --> 1 T3
T3 T4 T1 T2


Which transformation is used depends on how the sub trees are unbalanced.

Here''s a link to an AVL tree implementation in C++ templates:
http://www.moorpark.cc.ca.us/~csalazar/cs20/nonlin.txt
You have to go pretty far down the page to see it.

---

SiCrane:

Does the tree rotations really make the total algorithm faster? Sure, I have to spend less time plumming through the segments since the tree is balanced, but inserting all the segments looks like a costly operation with the AVL tree. How do you think about that? Nice algo for one-time space partition, though.

Domini:

About how many segments were you talking? I also have the problem that I have a lot of segments, since the triangles can get very small due to subdivision. Would a polygon sort from front to back help much, or would it only take more time?

All:

IS s-buffering indeed the best way to cope with lots of small polygons in software renderer?

Will the AVL tree algorithm make the s-buffer faster? Beats me. Try it out.

Inserting into an AVL isn''t really all that bad. Maybe about twice as expensive as inserting into an already balanced BST. It''s definately less expensive than an insert into the unbalanced side of an unbalanced BST.

I suspect, though, that for a lot of small overlapping segments an AVL is a good way to go. The reason for that is that you''ve got a lot of inserts and deletions that happen to consecutive data elements, this would result in a lot of unbalanced chains.

Also don''t underestimate the partitioning effect of having a balanced BST. As the s-buffer routine stands, you have to go down all the elements till you hit a x value that overlaps. With a properly balanced BST, you can go straight to that x value (give or take an getNextLargest call). This would take O(lg n) time as compared to searching down a linked list O(n) time. For about 128 segments per scanline that would translate into an approximate 3 to 5 fold speed increase to find the first relevent segment. Remember that''s segments per scanline, not polygons per scanline. As the algorithm stands you''ve got a lot of segment fragmentation. You could possibly get 128 segments with much much fewer polygons.

I could be totally wrong on the balance issues in s-buffering on a BST. It could be that an ordinary BST would work just fine, but I definately believe that a BST would be better than the sorted linked lists.

As for a implementation details: An ordinary BST takes the same storage space as a doubly linked list. A properly implemented AVL tree uses only a little more memory than a doubly-linked list (maybe 1 byte per node).

With code at hand it is not hard to try it out. I will do that.

About extra memory required for the AVL/BST: As long as the accesses are reasonable cacheable by the L1/L2 cache, I don''t give a f@#k!

Thanks again.
DaBit