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
[pbcode]
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
[/pbcode]
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
[pbcode]
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
[/pbcode]
Method #3 Inner Loop
[pbcode]
// 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
[/pbcode]
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:[pbcode]
;*=-----------------------------------------------------------------------------=*
;
; >> 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)
flushkeys
endif
Sync
loop
; --------------------------------------------------------------------------------------
; --------------------------------------------------------------------------------------
; --------------------------------------------------------------------------------------
; --------------------------------------------------------------------------------------
; --------------------------------------------------------------------------------------
; --------------------------------------------------------------------------------------
Function Render_Method1(Screen)
sw=GetSCreenWidth()
sh=GetSCreenHeight()
tw=GetIMageWidth(Screen)
th=GetIMageHeight(Screen)
rendertoimage SCreen
; scale from the screen to texture
ScaleX#=Float(TW)/sw
ScaleY#=Float(TH)/sh
X1=LIghts(1).X*ScaleX#
X2=LIghts(2).X*ScaleX#
X3=LIghts(3).X*ScaleX#
X4=LIghts(4).X*ScaleX#
lockbuffer
ThisRGB=POint(0,0)
For ylp=0 to TH-1
Dy1=abs(Ylp-(LIghts(1).Y*ScaleY#))
Dy2=abs(Ylp-(LIghts(2).Y*ScaleY#))
Dy3=abs(Ylp-(LIghts(3).Y*ScaleY#))
Dy4=abs(Ylp-(LIghts(4).Y*ScaleY#))
DY1=ClipRange(DY1,0,TH-1)
DY2=ClipRange(DY2,0,TH-1)
DY3=ClipRange(DY3,0,TH-1)
DY4=ClipRange(DY4,0,TH-1)
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
next
unlockbuffer
rendertoscreen
EndFUnction
; --------------------------------------------------------------------------------------
; --------------------------------------------------------------------------------------
; --------------------------------------------------------------------------------------
; --------------------------------------------------------------------------------------
; --------------------------------------------------------------------------------------
; --------------------------------------------------------------------------------------
Function Render_Method2(Screen)
rendertoimage SCreen
TW=GetSurfaceWidth()
TH=GetSurfaceHeight()
Static InitFunction
if InitFunction=false
Dim RowMap(TH)
for ylp =0 to TH
RowMap(ylp)=MakeLightMapRowArray(ylp)
next
InitFunction=true
MakeArray Row1()
MakeArray Row2()
MakeArray Row3()
MakeArray Row4()
endif
ScaleX#=Float(TW)/GetSCreenWidth()
ScaleY#=Float(TH)/GetSCreenHeight()
X1=LIghts(1).X*ScaleX#
X2=LIghts(2).X*ScaleX#
X3=LIghts(3).X*ScaleX#
X4=LIghts(4).X*ScaleX#
lockbuffer
ThisRGB=POint(0,0)
For ylp=0 to TH-1
Dy1=abs(Ylp-(LIghts(1).Y*ScaleY#))
Dy2=abs(Ylp-(LIghts(2).Y*ScaleY#))
Dy3=abs(Ylp-(LIghts(3).Y*ScaleY#))
Dy4=abs(Ylp-(LIghts(4).Y*ScaleY#))
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
next
unlockbuffer
rendertoscreen
EndFUnction
; --------------------------------------------------------------------------------------
; --------------------------------------------------------------------------------------
; -------------------------------[ METHOD 3 - SORTED ]----------------------------------
; --------------------------------------------------------------------------------------
; --------------------------------------------------------------------------------------
; --------------------------------------------------------------------------------------
Function Render_Method3(Screen)
rendertoimage SCreen
TW=GetSurfaceWidth()
TH=GetSurfaceHeight()
Static InitFunction
if InitFunction=false
Dim RowMap(TH)
for ylp =0 to TH
RowMap(ylp)=MakeLightMapRowArray(ylp)
next
InitFunction=true
MakeArray Row1()
MakeArray Row2()
MakeArray Row3()
MakeArray Row4()
; Buddle thew light values on the Width
DIm SortOrder(4)
endif
; ---------------------------------
; Set the default order
; ---------------------------------
For lp =1 to 4
SortOrder(lp) =lp
next
; ---------------------------------
; Sort lights across X axis
; ---------------------------------
For Pass=1 to 5
For lp=1 to 3
SrcIndex =SortOrder(lp)
NextIndex =SortOrder(lp+1)
X1 =LIghts(SrcIndex).X
X2 =LIghts(NextIndex).X
if (X1>X2)
SortOrder(lp) =NextIndex
SortOrder(lp+1) =SrcIndex
endif
next
next
ScaleX#=Float(TW)/GetSCreenWidth()
ScaleY#=Float(TH)/GetSCreenHeight()
; Get the Cords of the SORTed lights
SpanX0 = 0
SpanY0 = 0
Index =SortOrder(1)
SpanX1 =floor(LIghts(Index).X*ScaleX#)
SpanY1 =floor(LIghts(Index).Y*ScaleY#)
Index =SortOrder(2)
SpanX2 =floor(LIghts(Index).X*ScaleX#)
SpanY2 =floor(LIghts(Index).Y*ScaleY#)
Index =SortOrder(3)
SpanX3 =floor(LIghts(Index).X*ScaleX#)
SpanY3 =floor(LIghts(Index).Y*ScaleY#)
Index =SortOrder(4)
SpanX4 =floor(LIghts(Index).X*ScaleX#)
SpanY4 =floor(LIghts(Index).Y*ScaleY#)
SpanX1=ClipRange(SpanX1,1,TW-1)
SpanX2=ClipRange(SpanX2,1,TW-1)
SpanX3=ClipRange(SpanX3,1,TW-1)
SpanX4=ClipRange(SpanX4,1,TW-1)
SpanY1=ClipRange(SpanY1,1,TH-1)
SpanY2=ClipRange(SpanY2,1,TH-1)
SpanY3=ClipRange(SpanY3,1,TH-1)
SpanY4=ClipRange(SpanY4,1,TH-1)
lockbuffer
ThisRGB=POint(0,0)
For ylp=0 to TH-1
Dy1=abs(Ylp-SpanY1)
Dy2=abs(Ylp-SpanY2)
Dy3=abs(Ylp-SpanY3)
Dy4=abs(Ylp-SpanY4)
; get the row
Row1()=RowMap(DY1)
Row2()=RowMap(DY2)
Row3()=RowMap(DY3)
Row4()=RowMap(DY4)
// 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
next
unlockbuffer
rendertoscreen
EndFUnction
; --------------------------------------------------------------------------------------
; --------------------------------------------------------------------------------------
; --------------------------------------------------------------------------------------
; --------------------------------------------------------------------------------------
; --------------------------------------------------------------------------------------
; --------------------------------------------------------------------------------------
Function MakeLightMapRowArray(ThisRow)
Size=getArrayelements(LightMap())
Dim Row(Size)
For lp =0 to Size
Row(lp)=LightMap(lp,ThisROW)
next
EndFunction Row()
; --------------------------------------------------------------------------------------
; --------------------------------------------------------------------------------------
; --------------------------------------------------------------------------------------
; --------------------------------------------------------------------------------------
; --------------------------------------------------------------------------------------
; --------------------------------------------------------------------------------------
Function DrawPalette(StartLP,EndLP,Col1,Col2)
Dist#=EndLP-StartLP
For lp=StartLP to EndLP
Scale#=(lp-StartLP)/Dist#
Palette(lp)=RgbAlphaBlend(Col1,COl2,Scale#*100)
next
EndFunction LP
[/pbcode]
Video: Related Links: - A Crash Course In BASIC program Optimization (http://www.underwaredesign.com/forums/index.php?topic=2548.0)