Meta Balls - Light Blobs

[kevin]

  Meta Balls - Light Blobs


     This example recreates a popular demo effect known as meta balls/blobs.   The scene is calculated by working out the amount of energy that each pixel receives from the surround 'blobs' or lights.   The more lights the more work each pixel has to be do.

     So if you did all the work (calc the distance etc) in the inner most loops, you'd get a pretty heavy per pixel calculation.  Such a loop would run slowly even in assembly/machine code.    So what we need to do is come up with some ways we can simplify the inner loop to get the cost per pixel down as much as possible.

     The code bellow we're starting from an already opt'd inner loop with method 1,  where we've pre computed the energy values at all possible distances into a 2D table. So we can just look those values up.    This gives us a demo that runs, but there's still a lot of work per pixel being done.

     Method #1 Inner Loop

PlayBASIC Code: [Select]

            For xlp=0 to TW-1

               Dx1= abs(Xlp-X1)
               DX2= abs(Xlp-X2)
               DX3= abs(Xlp-X3)
               DX4= abs(Xlp-X4)
               
               Dist =LightMap(DX1,DY1) 
               Dist+=LightMap(DX2,DY2) 
               Dist+=LightMap(DX3,DY3) 
               Dist+=LightMap(DX4,DY4) 
               FastDot xlp,ylp,Palette(Dist)

            next

     So every pixel we're getting the absolute distance from each light, then using those values in our LightMap to compute the amount of energy.  Once we have this we pull the colour from the palette and draw it..    it's looks simple, but around 17/18 operations happening to compute a pixels colour.

    Now there's a few ways to reduce the overhead and one would be by converting those 2D array accesses to 1D.    So in the inner loop of method 2, were build an 1d array of 1d arrays.  Then at the start of each scan line we seed our arrays to the line of light map data and continue on.       Instruction wise, we're about the same number of instruction per pixel, but those instructions are less complex, so can be executed by the runtime easier.


    Method #2 Inner Loop

PlayBASIC Code: [Select]

            Row1()=RowMap(DY1)
            Row2()=RowMap(DY2)
            Row3()=RowMap(DY3)
            Row4()=RowMap(DY4)
         
            For xlp=0 to TW-1
            
               Dx1= abs(Xlp-X1)
               DX2= abs(Xlp-X2)
               DX3= abs(Xlp-X3)
               DX4= abs(Xlp-X4)
               
               Dist =Row1(Dx1)
               Dist+=Row2(DX2)
               Dist+=Row3(DX3) 
               Dist+=Row4(DX4) 

               FastDot xlp,ylp,Palette(Dist)

            next

    Method #3 Inner Loop

PlayBASIC Code: [Select]

            // Draw as 5 segments, so inner loop is simpler and program runs faster
            For xlp=SpanX0 to SpanX1-1
      
               Dist =Row1(SpanX1-xlp)
               Dist+=Row2(SpanX2-xlp)
               Dist+=Row3(SpanX3-xlp)
               Dist+=Row4(SpanX4-xlp)

               FastDot xlp,ylp,Palette(Dist)

            next
            
            
            For xlp=SpanX1 to SpanX2-1
      
               Dist =Row1(xlp      -SpanX1)
               Dist+=Row2(SpanX2   -xlp)
               Dist+=Row3(SpanX3   -xlp)
               Dist+=Row4(SpanX4   -xlp)

               FastDot xlp,ylp,Palette(Dist)

            next


            For xlp=SpanX2 to SpanX3-1
      
               Dist =Row1(xlp      -SpanX1)
               Dist+=Row2(xlp      -SpanX2)
               Dist+=Row3(SpanX3   -xlp)
               Dist+=Row4(SpanX4   -xlp)

               FastDot xlp,ylp,Palette(Dist)

            next


            For xlp=SpanX3 to SpanX4-1
      
               Dist =Row1(xlp      -SpanX1)
               Dist+=Row2(xlp      -SpanX2)
               Dist+=Row3(xlp      -SpanX3)
               Dist+=Row4(SpanX4   -xlp)

               FastDot xlp,ylp,Palette(Dist)

            next

            For xlp=SpanX4 to TW-1
            
               Dist =Row1(xlp      -SpanX1)
               Dist+=Row2(xlp      -SpanX2)
               Dist+=Row3(xlp      -SpanX3)
               Dist+=Row4(xlp      -SpanX4)
               FastDot xlp,ylp,Palette(Dist)

            next

   

     In this last version,  we're going to rearrange the inner loop to remove the ABS() functions.     To do this, we need to sort the lights from left to right, then draw the horizontal segments in spans.   So each segement is manually get out so that the subtraction is always positive.   This bring the instruction cost per pixel down to about 15 per pixel whcih the demo running in the low 20's on my legacy test hardware.  Not too bad for the old PlayBASIC runtime.      


     This is not the most optimal version, but the point i'm trying to make here is that how you go about solving the problems in your programs can make a big difference to it's performance.




 Source Code:

PlayBASIC Code: [Select]

;*=-----------------------------------------------------------------------------=*   
;
;                              >> Meta Balls / Light Blobs <<
;
;                                  By Kevin Picone
;
;                            Built Using PlayBasic V1.65 beta9
;
;                  Copyright 2016 by Kevin Picone All Rights Reserved.
;
;*=-----------------------------------------------------------------------------=*   
;                     www.UnderwareDesign.com  -  www.PLayBASIC.com
;*=-----------------------------------------------------------------------------=*   

   ; Compute a 16 by 9 screen size. 
   ScreenWidth   =960
   ScreenHeight=ScreenWidth*(9.0/16)
   
   if ScreenWidth<>GetSCreenWidth()
      if ScreenHeight<>GetSCreenHeight()
         OPenScreen ScreenWidth,ScreenHeight,32,1   
      endif
   endif



   // Build the Palette
   Dim Palette($ffff)
   
   Pos=DrawPalette(0      ,200   ,rgb( 10, 20, 30),Rgb(100,50,50))
   Pos=DrawPalette(pos   ,400   ,rgb(100, 50, 50),Rgb(180,120,90))
   Pos=DrawPalette(pos   ,500   ,rgb(180,120, 90),Rgb(255,255,255))

   for lp=pos to getarrayelements(Palette())
         Palette(lp)=Palette(pos-1)
   next



   // Build Light map
   SceneScale#   = (240/800.0)

   TextureWidth   =GetScreenWidth()*SceneScale#
   TextureHeight   =GetScreenHeight()*SceneScale#

   Texture=NewIMage(TextureWidth,TextureHeight,2)

   Dim LightMap(TextureWidth,TExtureHeight)

   For ylp = 0 To TextureHeight
      For xlp = 0 To TextureWidth
               dist#=GetDistance2d(0,0,xlp,ylp)
               if Dist#=0
                     Dist#=12000
               else
                     Dist#=12000/Dist#
               endif               
               LightMap(xlp, ylp) =  Dist#*(SceneScale#*2)
         Next
   Next 
   LightMap(0, 0) = 1000*(SceneScale#*2)   ;pos



   // Light Coordinates
   
   Type   tLIght
            x#,y#   
   EndType

   // Array of lights
   Dim Lights(4) as tlight

   

   mx#=500
   my#=300
   
   Method=2

   // ------------------------------------------------------------------
   do
   // ------------------------------------------------------------------



      ; ----------------------------------------------
      ; Set up the lights
      ; ----------------------------------------------

      Angle1#=wrapangle(Angle1#,5)
      Angle2#=wrapangle(Angle2#,6)
      MX#=curvevalue(MouseX(),mx#,10)
      MY#=curvevalue(MouseY(),my#,10)



      MX=floor(mx#)
      MY=floor(mY#)
      

      sw=GetScreenWidth()
      sh=GetScreenHeight()

      LIghts(1).x =mx
      LIghts(1).y =my

      ; move light in ellipse
      LIghts(2).x =(Sw / 2)+Cos(Angle1#)*(SW*0.4)
      LIghts(2).y =(Sh / 2)+Sin(Angle1#)*(SH*0.4)

      ; move light left/right
      LIghts(3).x =600+Cos(Angle2#)*200
      LIghts(3).y =150+Cos(Angle2#)*90

      LIghts(4).x =400
      LIghts(4).y =400

      ; ----------------------------------------------
      ; Call render function by name
      ; ----------------------------------------------
      CallFunction "Render_Method"+Str$(Method+1),Texture



      ; ----------------------------------------------
      ; render to the texture to the screen
      ; ----------------------------------------------
      sw=TextureWidth
      sh=TextureHeight
      lockbuffer
      TextureQuad Texture,0,0,0,0,GetScreenWidth(),0,sw,0,GetScreenWidth(),GetScreenHeight(),sw,sh,0,GetScreenHeight(),0,sh,8
      unlockbuffer
      


      ; ----------------------------------------------
      ; Draw info
      ; ----------------------------------------------

      setcursor 0,0
      print "Method:"+Str$(Method+1)+" of 3"
      print "Fps:"+Str$(Fps())

      ; Key key to toggle render method
      if Spacekey()
            Method=Mod(Method+1,3)

Login required to view complete source code

 Video:

   

 Related Links:

      -  A Crash Course In BASIC program Optimization