bit based z buffering / occlusion

[kevin]

  bit based z buffering  / occlusion

      Been mulling/testing an idea for a bit based z buffering algorithm.   The concept is somewhat derived from span buffering concept, where each row of the display you have a linked list of visible fragments on that row.  So when you draw a polygon/shape you rasterizing the shape and insert the spans into the row.   The inserted span is clipped against the buffer so that only visible portions are kept.    The primary concept is that the clipping helps the render engine avoid as much overdraw as possible.   Obviously there's no point drawing the same pixel opaque 100 times, when you only ever see the last time it was drawn.     I've written a bunch of span clippers over the years, but even though you're removing all the overdraw the list / clipping cost is still quite high.   So that in simple scenes the performance is worse that a brute force (render everything) approach, the benefits only really come through in heavily pixel dense scenes.  

      The bit based zbuffer would store linked 32bit fragments, where each 32 bits represents 32 pixels on screen.    So when rasterizing a span from a polygon, we compute bit masks from the span.  Rather than draw the pixels we insert each 32bit fragment into it's appropriate list on screen.  New fragments are masked against the previous visible fragment, only storing the bit Patten of the visible portions at this depths.    If  there's no change to the the existing 'visible' pixels with the to be drawn pixel mask, we throw this fragment out,  only adding it to the end of the list when numeric difference.  The new fragment is adding to the end of the stack and masked the 'visible' pattern.

      so if you have 5 line fragments converted to bit patterns like such as these,

1) %0000000110000000  (2 pixels to be drawn)
2) %0000001111000000  (4 pixels to be drawn)
3) %0000011111100000  (6 pixels to be drawn)
4) %0000111111110000  (8 pixels to be drawn)
5) %0001111111111000  (10 pixels to be drawn)

  Normally you'd draw rows from  5 down to the 1 (Painters algorithm) ,  drawing 30 pixels in the process, where 20  of those overlap and are never visible.

  But if you masked them from 1 to 5, we're only drawing these bits

1) %0000000110000000  (2 pixels to be drawn)
2) %0000001001000000  (2 pixels to be drawn)
3) %0000010000100000  (2 pixels to be drawn)
4) %0000100000010000  (2 pixels to be drawn)
5) %0001000000001000  (2 pixels to be drawn)

 So we're cut the rendering down to 10 pixels for only 5 spans and it  no longer matters what order you draw the final fragments to the screen, since only set bits make pixels.  So a 60% reduction.  

  Obviously the pixel rendering cost wouldn't be 60% faster,  since the bit buffers need to be flushed and there's insertion overhead per span,  but from the initial 'proof of concept' manager routine the insert routine can be written easily and has lots of early rejection options,  we'll see how it translates to a real world demo later I guess..

[kevin]

  zbit buffering  / occlusion - Testing Prototype library

     Took the raw concept and molded it into a library of sorts, at this point there's only a couple of drawing operations to test for overall conceptual issues.   So drawing is limited to a z buffered Box & Circle.   The prototype is running just in plain old PB code using the DOT to draw the screen of pixels.  So it's not particular quick,  but it does seem to be an easy way of removing overdraw from a scene.   The object shapes still needs to be rasterized and inserted, so even if a shape is occluded there's still a small fix overhead, which is the much the same for regular linked list span buffer.

     The picture bellow is draw from the following controller code. The objects are first drawn to the zbit span buffer, then the screen is drawn to the Pb screen using DOT plots for the time being.   Even though the screen is filled many times over, we're only ever drawing each pixel once.   Bellow the screen it's showing the fragment under the mouse at the time of execution.   Even with a lot objects on screen rarely do you seem to get a deep list, which is interesting, often the list only has one fragment in it, which is the upper most fragment, so everything else is just being thrown away.  

PlayBASIC Code: [Select]

   Screen=DLL_NewZbitScreen(800,600,32)
   
   ;------------------------------------------------------------
   ;------------------------------------------------------------
   SetFPS 60
   ;------------------------------------------------------------
   ;------------------------------------------------------------
   
   

   Randomize 200

   Type TObject
         ObjectType
         x#
         y#
         SpeedX#
         SpeedY#
         Width
         Height
         Colour
         PixelCount
   EndType   

   
   Dim Obj as tobject list


   For lp=1 to 250
         obj=new tObject

         Obj.Objecttype=1   ;int(rnd#(2))

         Obj.x#=rnd(GetScreenWidth())
         Obj.y#=rnd(GetScreenHeight())
         angle#=rnd(360)
         Speed#=rndRange(1,10)

         obj.Speedx#=rndrange#(1,5)
         obj.Speedy#=Sin(Angle#)*Speed#   

         Obj.Width   =rndrange(150,250)
         Obj.Height   =rndrange(150,250)
         Obj.Colour=Rndrgb()         

         if Obj.Objecttype=0
               obj.PixelCount=obj.width*Obj.Height         
         endif

         if Obj.Objecttype=1
               obj.width=obj.width/2
               obj.PixelCount=pi#*(obj.width*obj.width)         
               Obj.Height=Obj.Width
         endif

   next
   
   
   ;------------------------------------------------------------
   ;-[ MAIN LOOP------------------------------------------------
   ;------------------------------------------------------------
   do
      cls $304050
      

      DLL_ZbufferBox(200,200,500,300,$ff00ff)

      DLL_ZbufferBox(350,150,550,250,$0ff00)

      mx=mousex()
      my=mousey()
      
      for lp=1 to 100 step 10   
            ThisRGB=RgbAlphaBlend($f04030,$407040,lp)
            DLL_ZBufferCircle(300+lp,250+lp,lp*3,ThisRGB)
      next


      pixelCount=0

      For each Obj()
         x#=obj.x#+obj.Speedx#   
         y#=obj.y#   
         Width      =obj.width   
         Height   =obj.Height
         Select Obj.Objecttype
            case 0
               dll_zBufferBox(x#,y#,x#+Width,y#+height,Obj.Colour)
            case 1
               Dll_zBufferCircle(x#,y#,Width,obj.colour)      
         EndSelect
         
         pixelCount+=obj.pixelcount
         if X#>800
            x#=-100
         endif
         obj.x#=x#
         
      next

      Size=DLL_GetCurrentSpanDepth()
      
      DLL_ShowZbitStackAtPoint(mX,mY)
      
      DLL_RenderZbitScreen()
      
      dotc mx,my,$ffffff
      dotc mx+1,my,$444444
      dotc mx-1,my,$888888
      

      print "Span Buffer Depth:"+Str$(Size)
      print "Total Pixels:"+Str$(PixelCount)
   
      sync   
   loop
   

 Error Missing Closing Square Bracket

[monkeybot]

nice!

[baggey]

I cant get this to work. Where do i get the Dll file for it?

Kind Regards Baggey