Archived

This topic is now archived and is closed to further replies.

Staying with Scanlines

This topic is 4955 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

This is a little idea concerning software rendering that I had a while back, I thought I ought to run it past you guys to see what you thought. There are many situations in which drawing every pixel of a triangle is a wasted effort. An example would be when a polygon is clipped by one closer to the camera, or simply when you''re building the output to test visibility of an object rather than display it. What I was thinking about was delaying the step of converting scanlines into individual pixels. That way, if a triangle is occluded on a given scanline, you can drop the whole scanline in a single go, instead of testing each individual pixel. A scanline is simply a run of pixels; it has a vertical position, and start/end x positions (each of which have attached data like diffuse color or texture coords). So you can define an array of linked lists of scanlines - an array the size of the framebuffer''s height. As you process all your triangles, you break them down into scanlines, and add these scanlines to the appropriate list. Then you take each list and clip/drop the scanlines which are occluded. There are four cases I can come up with when comparing two scanlines:
  1. Scanline B completely occludes scanline A - that is, the z values of B at the endpoints of A are smaller than the z values of A in both cases. A is dropped from the list.
  2. Scanline B occludes one of the endpoints of A. A is clipped to a new length.
  3. Scanline B occludes the center of A; the endpoints are not occluded. This splits A into two new scanlines, each of which are clipped to B as in case (2).
  4. Scanline B intersects scanline A - that is, the triangles are passing through each other. Both scanlines are broken into two new ones at the point of intersection.
The end result is a list of scanlines which have no overdraw whatsoever. You *could* then go on from here to actually render all the pixels, or you could stop and just use these lists to run tests on (checking for any remaining scanlines of a particular triangle, for example). So, thoughts? I acknowledge that this is pretty much totally unncessary with hardware rendering being as powerful as it is these days, but this is more aimed at systems with no such capabilities (such as the GBA). It would save processing things like pixel shaders on such systems for pixels that get overdrawn.

Share this post


Link to post
Share on other sites
Yep, that''s a span buffer (S-buffer). Very popular in the good old days, because you could achieve correct depth rendering without sorting, and without the performance hit of a full perpixel z-buffer.

Share this post


Link to post
Share on other sites
I implemented one way back... the algorithm to have no overlapping spans and minimum number of spans to draw correctly was pretty long and ugly but it''s meant to be quick - I think Carmack (not that I subscribe to the ''Carmack is perfect'' myth) claimed that software S-buffering was as quick as early hardware Z-buffering cards. It''s memory efficient as long as you don''t have many very small triangles in which case it can be very expensive. In theory you could expand it to do proper layered transparency quite easily but I never got that far as I got bored of working in DOS and switched to D3D!

Share this post


Link to post
Share on other sites
quote:
Original post by doynax
hmm.. i think that''s called s-buffering


Oh... right. Well, at least it''s nice to know I''m coming up with good ideas, even if they are a few years late

Share this post


Link to post
Share on other sites
quote:
Original post by Coder
Just to add: AFAIK, today''s z-buffering is actually S-buffering (plus all the super-secret hierarchial craziness, of course).


just without its greatest feature: not needing to do the shading if a triangle gets overpainted later.

thats the power of s-buffering: only shade each pixel once. gpu''s aren''t capable of doing that.. well, mostly, with derefereed, but not 100% yet. and never will i guess.




If that''s not the help you''re after then you''re going to have to explain the problem better than what you have. - joanusdmentia

davepermen.net

Share this post


Link to post
Share on other sites
quote:
Original post by Megahertz
Sounds like it would require a lot of memory to be effective.

-=[ Megahertz ]=-

And a z-buffer isn''t? When it was first suggested, z-buffers were dismissed as being too memory intensive to be practical.

On the other hand, one of the niceties of a z-buffer is constant memory use regardless of scene complexity. An s-buffer I can imagine becomming less suitable with lots of small polys rather than several big ones.

Share this post


Link to post
Share on other sites
The problem with s-buffers is that their efficiency drops with increasing scene complexity. It''s works best if you have big polygons, so there are little tests needed. With a scene with many small polygons, you end up spending more time sorting spans than you would spend with a z-buffer. And with modern SSE instructions, the gap becomes even bigger because then the z-buffer implementation is even faster.

Anyway, if you have a scene with low complexity and high overdraw, it can win you a lot!

Share this post


Link to post
Share on other sites
At GDC many years back, Michael Abrash described how Quake implemented scan-line conversion. He talked about how the algorithm was very similar to a BSP tree.


John Bolton
Page 44 Studios
Current project: NHL Faceoff 2005 PS2

Share this post


Link to post
Share on other sites