3D Engine 07

Hail every programmer who are still checking my pages arround if there's something new. I'm sorry for my slackness and i promise to speed up. For today i promised i will focus on S-buffers. And it's here ... At first i shall tell you :

What the S-Buffer is and how does it work ?

S-Buffer is according to it's name buffer of S .. ? Segments (or sometimes also spans) It's not working exactly like Z-buffer, but there's some similarity. Z-buffer is solving visibility per pixel and S-buffer is solving visibility per segment. It's obvious S-buffer works again for saving z-coordinates all around our screen, but it's utilizing properties of our linear space - z-coordinate can be interpolated over segments. So - when drawing polygon, you create a set of segments (one per scanline) and solve visibility for them. Notice nothing is drawn ! Segments are just stored into buffer. So when is it drawn ? It's drawn when whole scene is finished, just before frame flipping. You can see that segments will need also information about texture / lighting, etc to be drawn properly.

S-Buffer versus Z-Buffer

S-Buffer

Less resolution - dependent (size = height)
Null overdraw (so we're (almost) not limited by fillrate)
Perfect accurate object intersections
Low memory requirements
But ... it's speed is quite dependent on scene complexity

Z-Buffer

Resolution dependent (size = width * height)
Unlimited overdraw
Perfect accurate object intersections
Requires some memory
Not dependent on scene complexity

That was rough S-buffer to Z-buffer comparison. Just to adress the scene complexity dependence. S-buffer was quite good for drawing low-poly models, but with growing number of polygons there will be far more segments to intersect and searching in segment - lists will slow down. And drawing will slow down as well, because smaller segments will be drawn and every of them will need perspective correction for textures. But that will bother you with models counting thousands of polygons ...

Variants of S-Buffer

You can also see S-Buffer used as C-Bufer. C is for coverage. Coverage buffer will require depth - sorted faces that don't intersect. You simply draw them front-to-back and when the screen is full (ie. every scanline is full), nothing else can be drawn. Segments are also in difference from S-buffer drawn immediately after adding to buffer so segments itself can be easily connected, because they don't have any texturing/depth informations. (connecting quite helps when drawing complex models, because segment number stays low) There are also hybrid variants of S / C-Buffer.

Realization

The best for S-Buffer will be the two-way link list (hope it's translated correctly). Why ? because you will need to have segments sorted by x-coordinate (screen-space x) and you will need to quickly insert / delete segments. Disatvantage is you can't use binary searching. Maybe i'm wrong and it would be faster with pointer arrays and fast binary searches, you should try that.
I can explain what i mean by two-way link list. It will be some kind of structure like this :


struct Cell {
    // data
    struct Cell *prev, *next;
};

That's how should it look like in C. Each cell in list has pointer to it's previous and next cell. (first one has no previous and last one has no next so pointer will be null) You just keep pointer to first cell where our list begins. It's quite important not to forget to update this pointer when removing first cell ... Advantage is cell adding / removing, you just change a few pointers and done. Disadvantage is you can't linearly address this list, you have to jump step-by-step to cell you want ...
We will also need some memory manager that will give us new segments. The one i wrote is very simple. It's just array of arrays of segments. When all segments in first array are allocated, manager create next array. Why array of arrays ? Because we need to have constant pointers and when calling realloc() you got pointer change.

Next we need some scanline structure that will keep our segment list :


struct {
    Segment *seg;
    int n_seg_num;
    int n_seg_used;
} Scanline;

seg is pointer to first segment, n_seg_num is number of all segments in scanline and n_seg_used is number of used segments. Segments are added to scanline and when deleted, segment moves to the end of scanline (because of fast memory manager - can't afford returning segments back to it) and will be reused when necessary.
So we have as much scanlines as the screen resolution is and for start we will put 50 empty segments into each. Don't forget set n_seg_used to zero !
Now we will need our core function for segment intersecting. How should that work ? Our segments can be just in a few positions :

segment placement

The segment positions in example are marked with these numbers so you can compare it. For each case There are a few posibilities : New segment will be whole behind or whole in front or will intersect and left side will be behind / right side will be behind old segment. That's whole magic. Segment intersections are computed by line equation (you can notice it's in x = -0x1000, that's just for better float preciseness)

Example

Example is on the same level like previous one, but instead of BSP-trees is using S-Buffer. It's not ideal example, because in the room with pillars is nothing to cause any significant overdraw. That's why i included a new BSP - simple world with triangular tunnel. When you look trough it, most of pixels will be overdrawn three times (with BSP). (note it has been on my old P133 computer - i really can't see any diference now ... it would require some procedural texture to slow down fillrate)

Directx.cpp
DirectX interface. No changes here ... (of course when working in DOS / Linux you have to replace this ...)

Font_Eng.cpp
Neither this changed. There's function for loading truecolor bitmap and drawing simple bitmap font ... (i plan some graphics format page with code to load some common formats like jpeg / png / gif / pcx / tga ... + i'm writing some paper on how jpeg works)

Load_3ds.cpp
Module for loading *.3ds files. Maybe i'll add some more formats, for example Q3a and some more autodesk formats ...

Main.cpp
In WinMain() function are loading and init functions ... What's interesting is in timer callback :


InitScreen();

for(i = 0; i < svet->n_object_num; i ++) {
    DrawObject(&svet->object[i].mobject, &cmatrix,
        &svet->object[i], svet->material);
}
// draw world

ReleaseScreen(buffer);

InitScreen() cleans S-Buffer (set count of used segments in all scanlines to zero. it's analogy to Clean_ZBuffer()) The object drawing loop is still the same, the only change will be in DrawObject() function. Finally ReleaseScreen() draw contents of s-buffer to screen.

Matrix.cpp
Just matrices ...

Pyramid.cpp
Clipping pyramid.

Raster.cpp
There will be some changes at here. In Init_Engine() the S-Buffer is created :


InitSManager();
if(!(s_buffer = (Scanline*)malloc(Height * sizeof(Scanline))))
    return 0;
for(i = 0; i < Height; i ++) {
    if(!InitScanline(st_segs, &s_buffer[i]))
        return 0;
    s_buffer[i].n_seg_used = 0;
}
// initialize s-buffer

As i mentioned above, create array of scanlines as long as screen's height, put some (it's twenty in our case) segments into each and clear used segment counters. (that's in fact useless, because InitScreen() would do it for us, but it's just for the order) It's simple ... Yes, and the first line calls function, allocating some memory for storing segments. In the Uninit_Engine() are some calls to segment manager to free memory we allocated for segments and scanlines. It's simple.
Next change is in Draw_Polygon(), but it's just cosmetic one. We don't call function for drawing segments, but fill the segment structure and pass it to visibility code instead. After all the drawing you call Release_Screen() which take segments and draw them. Someone who's paying attention could say the Init_Screen() is redundant, because we could clear it during Release_Screen(), but we could need the buffer, for example when drawing transparent surfaces. Segments of such a surfaces won't be added into scanline, we will only cull their non-visible portions and draw the rest immediately. It's not included into the example, because it's quite trivial and you can do it yourself. In the example is only function for solving segment visibility (true / false) that can be usefull when doing portal rendering / etc ...

Seg_Man.cpp
It's S-Buffer core. At the beginning there are some constants :
startup_seg (1024) - starting number of segments
seg_inc (256) - number of segments that will be allocated everytime when the rest ran out
They don't necessarily have to be powers of two, it's just picture of coder's poor imagination ... Next there is array called stack, that's first dimension of our array of arrays. Next dimensions will be array of 1024 segments and next ones arrays of 256 segments. I already mentioned, but once more just for clarify, it's because we need segments to have constant adresses and address of array changes with every realloc(). Now, the address of first dimension changes, but the other dimensions stay constant ...
Next there are some functions for memory management :
UninitSManager() - free all allocated memory
Reset_SManager() - set all segments as unused (doesn't free anything)
GetMem_Usage() - returns how many bytes of memory is used
GetMem_Status() - return if there is enough memory
Grow_Reservoir() - allocates seg_inc more segments ...
Following functions are for segment operations :

int InitScanline(int seg_n, Scanline *sl)
    - add seg_n segments to the end of scanline sl

inline Segment *Get_Segment(Scanline *sl, Segment *seg)
    - get the first unused segment and copy contents of seg into that (aparts from next and prev pointers, of course)

inline Segment *GetSegmentBehind(Scanline *sl, Segment *cur, Segment *seg)
    - get segment lying before cur and copy contents of seg again

inline Segment *GetSegmentNext(Scanline *sl, Segment *cur, Segment *seg)
    - same like previous one, but segment will be next to cur

inline void RemoveSegment(Scanline *sl, Segment *seg)
    - remove segment (place to the end of scanline and decrease number of used segments)

Every function call Grow_Reservoir() when there's not enough segments in scanline. And we have the main function, called by rasterizer and used to determine visibility of segment :


void _fastcall AddSegment(Segment *seg, Scanline *sc)
{
    Segment *tmp, *cur;
    int i = 0, x, s;

    cur = sc->segm;
    while(i < sc->n_seg_used) {
        if(seg->x2 <= cur->x1) { // Case # 1
            GetSegmentBehind(sc, cur, seg);
            return;
        } else if(seg->x1 >= cur->x2) { // Case # 2
            i ++;
            cur = cur->next;
            continue;
        } else if(seg->x2 > cur->x1 && seg->x1 < cur->x1 && seg->x2 < cur->x2) {
                                                                     // Case # 3
            x = SEG_SPLIT(seg, cur);
            if(x > cur->x1 && x < seg->x2) {
                if(SEG_Z(cur, -0x1000) < SEG_Z(seg, -0x1000)) {
                    cur->x1 = x;
                    seg->x2 = x;
                    GetSegmentBehind(sc, cur, seg);
                    return;
                } else {
                    s = cur->x1;
                    cur->x1 = seg->x2;
                    if(!(tmp = GetSegmentBehind(sc, cur, seg)))
                        return;
                    tmp->x1 = x;
                    // cur = tmp;
                    // cur = cur->next;
                    if(!(tmp = GetSegmentBehind(sc, tmp/*cur*/, cur)))
                        return;
                    tmp->x1 = s;
                    tmp->x2 = x;
                    if(!(tmp = GetSegmentBehind(sc, tmp/*cur*/, seg)))
                        return;
                    tmp->x2 = s;
                    return;
                }
            } else {
                x = cur->x1 + (int)((float)(seg->x2 - cur->x1) / 2 + 0.5);
                if(SEG_Z(cur, x) < SEG_Z(seg, x)) {
                    cur->x1 = seg->x2;
                    GetSegmentBehind(sc, cur, seg);
                    return;
                } else {
                    seg->x2 = cur->x1;
                    GetSegmentBehind(sc, cur, seg);
                    return;
                }
            }
        } else if(seg->x1 > cur->x1 && seg->x1 < cur->x2 && seg->x2 > cur->x2) {
                                                                     // Case # 4
            x = SEG_SPLIT(seg, cur);
            if(x > seg->x1 && x < cur->x2) {
                if(SEG_Z(cur, -0x1000) < SEG_Z(seg, -0x1000)) {
                    s = cur->x2;
                    cur->x2 = seg->x1;
                    if(!(tmp = GetSegmentNext(sc, cur, seg)))
                        return;
                    tmp->x2 = x;
                    if(!(tmp = GetSegmentNext(sc, tmp, cur)))
                        return;
                    tmp->x1 = x;
                    tmp->x2 = s;
                    seg->x1 = s;
                    cur = tmp;
                    i += 2;
                    continue;
                } else {
                    cur->x2 = x;
                    seg->x1 = x;
                    cur = cur->next;
                    i ++;
                    continue;
                }
            } else {
                x = seg->x1 + (int)((float)(cur->x2 - seg->x1) / 2 + 0.5);
                if(SEG_Z(cur, x) < SEG_Z(seg, x)) {
                    cur->x2 = seg->x1;
                    i ++;
                    cur = cur->next;
                    continue;
                } else {
                    seg->x1 = cur->x2;
                    i ++;
                    cur = cur->next;
                    continue;
                }
            }
        } else if(seg->x1 > cur->x1 && seg->x2 < cur->x2) { // Case # 5
            x = SEG_SPLIT(seg, cur);
            if(x > seg->x1 && x < seg->x2) {
                if(SEG_Z(cur, -0x1000) < SEG_Z(seg, -0x1000)) {
                    seg->x2 = x;
                    if(!(tmp = GetSegmentNext(sc, cur, seg)))
                        return;
                    if(!(tmp = GetSegmentNext(sc, cur->next, cur)))
                        return;
                    tmp->x1 = x;
                    cur->x2 = seg->x1;
                    return;
                } else {
                    seg->x1 = x;
                    if(!(tmp = GetSegmentNext(sc, cur, seg)))
                        return;
                    if(!(tmp = GetSegmentNext(sc, cur->next, cur)))
                        return;
                    tmp->x1 = seg->x2;
                    cur->x2 = x;
                    return;
                }
            } else {
                x = seg->x1 + (int)((float)(seg->x2 - seg->x1) / 2 + 0.5);
                if(SEG_Z(cur, x) < SEG_Z(seg, x)) {
                    if(!(tmp = GetSegmentNext(sc, cur, seg)))
                        return;
                    if(!(tmp = GetSegmentNext(sc, cur->next, cur)))
                        return;
                    tmp->x1 = seg->x2;
                    cur->x2 = seg->x1;
                    return;
                }
                return;
            }
        } else if(seg->x1 < cur->x1 && seg->x2 > cur->x2) { // Case # 6
            x = SEG_SPLIT(seg, cur);
            if(x > cur->x1 && x < cur->x2) {
                if(SEG_Z(cur, -0x1000) < SEG_Z(seg, -0x1000)) {
                    s = cur->x2;
                    cur->x1 = x;
                    if(!(tmp = GetSegmentBehind(sc, cur, seg)))
                        return;
                    tmp->x2 = x;
                    seg->x1 = s;
                    cur = cur->next;
                    i += 2;
                    continue;
                } else {
                    s = cur->x1;
                    cur->x2 = x;
                    if(!(tmp = GetSegmentBehind(sc, cur, seg)))
                        return;
                    tmp->x2 = s;
                    seg->x1 = x;
                    cur = cur->next;
                    i += 2;
                    continue;
                }
            } else {
                x = cur->x1 + (int)((float)(cur->x2 - cur->x1) / 2 + 0.5);
                if(SEG_Z(cur, x) < SEG_Z(seg, x)) {
                    tmp = cur;
                    cur = cur->next;
                    RemoveSegment(sc, tmp);
                    continue;
                } else {
                    x = cur->x1;
                    s = cur->x2;
                    if(!(tmp = GetSegmentBehind(sc, cur, seg)))
                        return;
                    tmp->x2 = x;
                    seg->x1 = s;
                    cur = cur->next;
                    i += 2;
                    continue;
                }
            }
        } else if(seg->x1 == cur->x1 && seg->x2 < cur->x2) { // Case # 7a
            x = SEG_SPLIT(seg, cur);
            if(x > seg->x1 && x < seg->x2) {
                if(SEG_Z(cur, -0x1000) < SEG_Z(seg, -0x1000)) {
                    seg->x2 = x;
                    cur->x1 = x;
                    GetSegmentBehind(sc, cur, seg);
                    return;
                } else {
                    s = cur->x2;
                    cur->x2 = x;
                    if(!(tmp = GetSegmentNext(sc, cur, seg)))
                        return;
                    tmp->x1 = x;
                    if(!(tmp = GetSegmentNext(sc, cur->next, cur)))
                        return;
                    tmp->x1 = seg->x2;
                    tmp->x2 = s;
                    return;
                }
            } else {
                x = seg->x1 + (int)((float)(seg->x2 - seg->x1) / 2 + 0.5);
                if(SEG_Z(cur, x) < SEG_Z(seg, x)) {
                    cur->x1 = seg->x2;
                    GetSegmentBehind(sc, cur, seg);
                    return;
                }
                return;
            }
        } else if(seg->x1 == cur->x1 && seg->x2 > cur->x2) { // Case # 7b
            x = SEG_SPLIT(seg, cur);
            if(x > cur->x1 && x < cur->x2) {
                if(SEG_Z(cur, -0x1000) < SEG_Z(seg, -0x1000)) {
                    s = cur->x2;
                    cur->x1 = x;
                    if(!(tmp = GetSegmentBehind(sc, cur, seg)))
                        return;
                    tmp->x2 = x;
                    seg->x1 = s;
                    cur = cur->next;
                    i += 2;
                    continue;
                } else {
                    cur->x2 = x;
                    seg->x1 = x;
                    i ++;
                    cur = cur->next;
                    continue;
                }
            } else {
                x = cur->x1 + (int)((float)(cur->x2 - cur->x1) / 2 + 0.5);
                if(SEG_Z(cur, x) < SEG_Z(seg, x)) {
                    tmp = cur;
                    cur = cur->next;
                    RemoveSegment(sc, tmp);
                    continue;
                } else {
                    seg->x1 = cur->x2;
                    i ++;
                    cur = cur->next;
                    continue;
                }
            }
        } else if(seg->x1 > cur->x1 && seg->x2 == cur->x2) { // Case # 8a
            x = SEG_SPLIT(seg, cur);
            if(x > seg->x1 && x < seg->x2) {
                if(SEG_Z(cur, -0x1000) < SEG_Z(seg, -0x1000)) {
                    s = cur->x2;
                    cur->x2 = seg->x1;
                    seg->x2 = x;
                    if(!(tmp = GetSegmentNext(sc, cur, seg)))
                        return;
                    if(!(tmp = GetSegmentNext(sc, cur->next, cur)))
                        return;
                    tmp->x1 = x;
                    tmp->x2 = s;
                    return;
                } else {
                    cur->x2 = x;
                    seg->x1 = x;
                    GetSegmentNext(sc, cur, seg);
                    return;
                }
            } else {
                x = seg->x1 + (int)((float)(seg->x2 - seg->x1) / 2 + 0.5);
                if(SEG_Z(cur, x) < SEG_Z(seg, x)) {
                    cur->x2 = seg->x1;
                    GetSegmentNext(sc, cur, seg);
                    return;
                }
                return;
            }
        } else if(seg->x1 < cur->x1 && seg->x2 == cur->x2) { // Case # 8b
            x = SEG_SPLIT(cur, seg);
            if(x > cur->x1 && x < cur->x2) {
                if(SEG_Z(cur, -0x1000) < SEG_Z(seg, -0x1000)) {
                    seg->x2 = x;
                    cur->x1 = x;
                    GetSegmentBehind(sc, cur, seg);
                    return;
                } else {
                    cur->x2 = x;
                    if(!(tmp = GetSegmentNext(sc, cur, seg)))
                        return;
                    tmp->x1 = x;
                    seg->x2 = cur->x1;
                    GetSegmentBehind(sc, cur, seg);
                    return;
                }
            } else {
                x = cur->x1 + (int)((float)(cur->x2 - cur->x1) / 2 + 0.5);
                if(SEG_Z(cur, x) < SEG_Z(seg, x)) {
                    seg->prev = cur->prev;
                    seg->next = cur->next;
                    memcpy(cur, seg, sizeof(Segment));
                    return;
                } else {
                    seg->x2 = cur->x1;
                    GetSegmentBehind(sc, cur, seg);
                    return;
                }
            }
        } else if(seg->x1 == cur->x1 && seg->x2 == cur->x2) { // Case # 9
            x = SEG_SPLIT(seg, cur);
            if(x > seg->x1 && x < seg->x2) {
                if(SEG_Z(cur, -0x1000) < SEG_Z(seg, -0x1000)) {
                    seg->x2 = x;
                    cur->x1 = x;
                    GetSegmentBehind(sc, cur, seg);
                    return;
                } else {
                    seg->x1 = x;
                    cur->x2 = x;
                    GetSegmentNext(sc, cur, seg);
                    return;
                }
            } else {
                x = seg->x1 + (int)((float)(seg->x2 - seg->x1) / 2 + 0.5);
                if(SEG_Z(cur, x) < SEG_Z(seg, x)) {
                    seg->prev = cur->prev;
                    seg->next = cur->next;
                    memcpy(cur, seg, sizeof(Segment));
                    return;
                }
                return;
            }
        }
        
        cur = cur->next;
        i ++;
    }

    if(!Get_Segment(sc, seg))
        return;
}

There are just a few unexplained macros. SEG_Z(seg, x) compute z-coord of segment seg on some x coordinate. SEG_SPLIT(a, b) tells x-coord of two segments a, b) intersection. Next there is mentioned function, returning true / false visibility of segment. Segment actually shouldn't be part of scanline, otherwise it may return false :
int _fastcall Segment_Visibility(Segment *seg, Scanline *sc)

Now, i think i told everything (well, not averything) to this theme ...

Now, download your example + source :

S-Buffer Engine

Well - and what is it going to be about next time ? When you see the image, you can see the "holes" in the ceiling are a bit "strewn" - the texture resolution is larger than screen resolution in that place so some pixels are missed and texture looks noisy. We will elliminate by method called mip-mapping. (but that will be really next time ...)

Yes, and i prepared some graphs of segment lengths for two scenes :

simple scene