News:

Function Finder  Find all the functions within source code files

Main Menu

bit based z buffering / occlusion

Started by kevin, January 05, 2015, 07:34:00 AM

Previous topic - Next topic

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


baggey

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

Kind Regards Baggey
Jesus was only famous because of his dad