Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 

 Home / 3D Theory & Graphics / Segment- or Coverage-buffer? Account Manager
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
Jeroen

March 25, 1999, 02:41 PM

Hi All,

I would like some input on the following problem. I, like most of us here, am working on a 3D-
engine. I have set up the transformation part, and all works well. Right now, I'm trying to
decide which rasterizing algorithm to implement. I've temporarily set up a classic polygon
filler which, if used for complex scenes, would result in a frightening lot of overdraw.
I'm thinking about using one of the variants of span-buffering (Segment- or Coverage-buffer).
Both have their advantages. At first glance, the c-buffer has the advantage, because an
s-buffer requires a complex 'insertion'-routine.
However, the c-buffer requires all the polygons to be depth-sorted in advance, which in
complex scenes can become relatively expensive. On top of this, making the assumption that
there are no intersecting polygons (Which imho is realistic in a real game-engine) means that
a lot of hideous calculations (of the intersection points) are avoided. This greatly simplifies
the insertion routine of the segment-buffer algorithm.
All in all, I think both algorithms come fairly close in terms of performance, and I'm leaning
towards the segment-buffer, because it avoids depth-sorting and because it's pixel-perfect.
However, if anyone has suggestions on this subject, I would like to hear.

Cheerio,

Jeroen

 
Phantom

March 26, 1999, 03:37 AM

Hello Jeroen,

Personally, I prefer the c-buffer, since it handles large volumes of polygons much
better. A c-buffer will link two spans when there are no empty pixels between them,
so searching where a new span must be inserted is much faster than with an s-buffer
where every span needs to be remembered. A well-implemented s-buffer however is
cool too, since it does perfect sorting... But not for free. Doing sorting by
inserting spans, and overlapping them later with another polygon is MUCH more
expensive than applying a quick radix/quick/or even bubblesort on the polygons before
rendering them. Of course, a good 3D engine doesn't need sorting, because it uses
a space partitioning scheme like BSP's or octrees... :)

Greets
Jacco.

Jeroen wrote:
>>Hi All,
>>
>>I would like some input on the following problem. I, like most of us here, am working on a 3D-
>>engine. I have set up the transformation part, and all works well. Right now, I'm trying to
>>decide which rasterizing algorithm to implement. I've temporarily set up a classic polygon
>>filler which, if used for complex scenes, would result in a frightening lot of overdraw.
>>I'm thinking about using one of the variants of span-buffering (Segment- or Coverage-buffer).
>>Both have their advantages. At first glance, the c-buffer has the advantage, because an
>>s-buffer requires a complex 'insertion'-routine.
>>However, the c-buffer requires all the polygons to be depth-sorted in advance, which in
>>complex scenes can become relatively expensive. On top of this, making the assumption that
>>there are no intersecting polygons (Which imho is realistic in a real game-engine) means that
>>a lot of hideous calculations (of the intersection points) are avoided. This greatly simplifies
>>the insertion routine of the segment-buffer algorithm.
>>All in all, I think both algorithms come fairly close in terms of performance, and I'm leaning
>>towards the segment-buffer, because it avoids depth-sorting and because it's pixel-perfect.
>>However, if anyone has suggestions on this subject, I would like to hear.
>>
>>Cheerio,
>>
>> Jeroen

 
Jeroen

March 26, 1999, 06:16 AM



Phantom wrote:
>>Hello Jeroen,
>>
>>Personally, I prefer the c-buffer, since it handles large volumes of polygons much
>>better. A c-buffer will link two spans when there are no empty pixels between them,
>>so searching where a new span must be inserted is much faster than with an s-buffer
>>where every span needs to be remembered. A well-implemented s-buffer however is
>>cool too, since it does perfect sorting... But not for free. Doing sorting by
>>inserting spans, and overlapping them later with another polygon is MUCH more
>>expensive than applying a quick radix/quick/or even bubblesort on the polygons before
>>rendering them. Of course, a good 3D engine doesn't need sorting, because it uses
>>a space partitioning scheme like BSP's or octrees... :)

I see your point, and you're probably right. Maybe I'll just be a hero and implement both,
just to see which one is faster :-).

Anyway, BSP- or Octrees would be a nice subject for the portal column :). I understand the
basic algorithms, but I never got around actually implementing one.

Jeroen


 
Phantom

March 26, 1999, 11:25 AM

Hello Jeroen,

I've discussed your topic proposals with Jaap Suter, and I think
that Jaap will write about the octree, so that leaves the BSP stuff
for me. :) Well, I'll give it a try. You've gotta wait some weeks
though, as we have quite a lot of topics waiting... Maybe I'll just
write a doc about BSP's and release it right away.

Greets
Jacco

Jeroen wrote:
>>
>>
>>Phantom wrote:
>>>>Hello Jeroen,
>>>>
>>>>Personally, I prefer the c-buffer, since it handles large volumes of polygons much
>>>>better. A c-buffer will link two spans when there are no empty pixels between them,
>>>>so searching where a new span must be inserted is much faster than with an s-buffer
>>>>where every span needs to be remembered. A well-implemented s-buffer however is
>>>>cool too, since it does perfect sorting... But not for free. Doing sorting by
>>>>inserting spans, and overlapping them later with another polygon is MUCH more
>>>>expensive than applying a quick radix/quick/or even bubblesort on the polygons before
>>>>rendering them. Of course, a good 3D engine doesn't need sorting, because it uses
>>>>a space partitioning scheme like BSP's or octrees... :)
>>
>>I see your point, and you're probably right. Maybe I'll just be a hero and implement both,
>>just to see which one is faster :-).
>>
>>Anyway, BSP- or Octrees would be a nice subject for the portal column :). I understand the
>>basic algorithms, but I never got around actually implementing one.
>>
>>Jeroen
>>
>>

 
Harmless

April 06, 1999, 02:08 AM

Jeroen wrote:
>>Phantom wrote:
>>>>Personally, I prefer the c-buffer, since it handles large volumes of polygons much
>>>>better. A c-buffer will link two spans when there are no empty pixels between them,
>>>>so searching where a new span must be inserted is much faster than with an s-buffer
>>>>where every span needs to be remembered. A well-implemented s-buffer however is
>>>>cool too, since it does perfect sorting... But not for free. Doing sorting by
>>>>inserting spans, and overlapping them later with another polygon is MUCH more
>>>>expensive than applying a quick radix/quick/or even bubblesort on the polygons before
>>>>rendering them. Of course, a good 3D engine doesn't need sorting, because it uses
>>>>a space partitioning scheme like BSP's or octrees... :)
>>I see your point, and you're probably right. Maybe I'll just be a hero and implement both,
>>just to see which one is faster :-).

Having implemented both, I lean in favor of a coverage buffer for all but the most dynamic worlds. In practice you pay the 'sorting cost' every frame in a span buffer because of the order of magnitude more spans you have to deal with on a per scan-line basis, which to me indicates that if I can pay an O(n^2) to O(n^3) cost to bsp the scene once, I'm willing to do so to avoid dealing with a sorting cost with an average case of (n lg n) and O(n^2) on a per scanline basis.

The numbers above are misleading though, because the bsp case is either a per-scene or per-subdivision level (octree leaves with minibsps, etc) cost whereas the cost for the spanbuffer sort is paid per polygon span per scanline. If you have a highly dynamic low polygon count scene the span buffer wins out, if you have a high polygon count static scene the c-buffer works out.

Problems with the c-buffer are that unless you split all of your dynamic actors up into leaf sized chunks (which is an unrealistic requirement) you need to choose another means to render them, this requires at least a 2-stage pipeline, which in and of itself isnt a bad thing (I _prefer_ to use one because it allows me to render each polygon in a context that is suited to its purpose, i.e. use quick and dirty tricks on fasr moving dynamic objects because no one will notice) but it alo means that if you are using a cbuffer you probably will need to earmark which bsp leaves were visible in each frame in order to be able to render dynamic objects which overlap those leaves.

There is another problem with both algorithms which neither algorithm directly addresses and that is the subject of what light sources can affect the view, in the case you start dealing with shadowcasting point lights life gets difficult for both algorithms. Which is why in the end I abandoned both for a beamtree based vis.

>>Anyway, BSP- or Octrees would be a nice subject for the portal column :). I understand the
>>basic algorithms, but I never got around actually implementing one.

If I can find them, I have several long emails I've sent out to people on the subject I should clean up and post somewhere.

All visible surface and span algorithms in relationship to each other are are different ways ot paying the same cost, the trick is pushing as much of that cost off to preprocessing time as possible.

-Harmless

 
This thread contains 5 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.