+- QB64 Phoenix Edition (https://staging.qb64phoenix.com)
+-- Forum: Official Links (https://staging.qb64phoenix.com/forumdisplay.php?fid=16)
+--- Forum: Learning Resources and Archives (https://staging.qb64phoenix.com/forumdisplay.php?fid=13)
+--- Thread: Optimizing for Speed (/showthread.php?tid=377)
Optimizing for Speed - TarotRedhand - 05-08-2022
Constructed from a series of letters that I posted in the QB ECHO of FIDONET quite a long time ago. Note that this tutorial was all about speeding things up which may not be quite the problem it was back then. Anyway, here is the original tutorial. In addition to the line drawing routine that is used to illustrate this tutorial on optimisation, I have included a couple of other graphics primitives routines. Fill is a seed fill routine and doros is an integer circle drawing routine. Doros is based on an algorithm discovered by a professor Doros and is a variation of the standard bresenham routine. The only drawback to it is that in order for it to produce circular circles it needs square pixels (i.e. SCREEN 12).
As there doesn't seem to be a lot of code floating around at present and we have quite a few newbies here I thought I would give an example of the way I have developed stuff in the past. Now as most people who are new to programming are interested in graphics I thought I'd use an example based in this area. Below is a small program that illustrates a different method of drawing a line on the screen than the one that is built into QB. The actual algorithm used is called a digital difference engine and while it is small it does have some drawbacks <g>.
Try it now and see if you can spot what they are. When you have done that go to the end of this message for an explanation of what they are and how the algorithm works.
Code: (Select All)
CONST FromX = 10
CONST FromY = 10
CONST ToX = 310
CONST ToY = 190
SCREEN 13
_FullScreen _SquarePixels
FOR index = 1 TO 5
LINE (FromX, FromY)-(ToX, ToY), 15
Sleep
DigitalDifferenceEngine FromX, FromY, ToX, ToY, 12
Sleep
NEXT index
SLEEP
END
SUB DigitalDifferenceEngine (X1, Y1, X2, Y2, C)
XS = 1
YS = 1
XI = 1
YI = 1
DX = X2 - X1
DY = Y2 - Y1
IF DX < 0 THEN XS = -1
IF DY < 0 THEN YS = -1
NX = ABS(DX)
NY = ABS(DY)
IF NX >= NY THEN
NP = NX
YI = NY / NX
ELSE
NP = NY
XI = NX / NY
END IF
FOR Q = 0 TO NP
X = X1 + XS * INT(Q * XI + .5)
Y = Y1 + YS * INT(Q * YI + .5)
PSET (X, Y), C
NEXT Q
END SUBO.K. So first lets mention what is good about this routine. First the layout is almost perfect and second flow of control is good i.e. no spaghetti. Thirdly it does what it is supposed to do. So what's bad about it. Well the majority of the variable names are either one or two letters long which makes it a lot harder to understand than necessary. Apart from this it is *slow*. Its slow because it uses floating point routines instead of integer and it is not optimised at all. However, before we can optimise it we have to understand how it works. The first step to understanding how it works is too change the variable names to something more meaningful.
Code: (Select All)
CONST FromX = 10
CONST FromY = 10
CONST ToX = 310
CONST ToY = 190
SCREEN 13
_FullScreen _SquarePixels
FOR index = 1 TO 5
LINE (FromX, FromY)-(ToX, ToY), 15
Sleep
DigitalDifferenceEngine FromX, FromY, ToX, ToY, 12
Sleep
NEXT index
SLEEP
END
SUB DigitalDifferenceEngine (X1, Y1, X2, Y2, Colour)
DirectionX = 1
DirectionY = 1
XIncrement = 1
YIncrement = 1
DistanceX = X2 - X1
DistanceY = Y2 - Y1
IF DistanceX < 0 THEN DirectionX = -1
IF DistanceY < 0 THEN DirectionY = -1
NewDistanceX = ABS(DistanceX)
NewDistanceY = ABS(DistanceY)
IF NewDistanceX >= NewDistanceY THEN
NumberOfPoints = NewDistanceX
YIncrement = NewDistanceY / NewDistanceX
ELSE
NumberOfPoints = NewDistanceY
XIncrement = NewDistanceX / NewDistanceY
END IF
FOR PointNumber = 0 TO NumberOfPoints
X = X1 + DirectionX * INT(PointNumber * XIncrement + .5)
Y = Y1 + DirectionY * INT(PointNumber * YIncrement + .5)
PSET (X, Y), Colour
NEXT PointNumber
END SUBSo how does this work? First we set the variables that determine the direction that the line will be drawn in (i.e. up and to the right etc.) to one each. We also set the variables that determine the rate of change in both the X and Y directions, to one each. After this we determine the distance between the start and end points for both the X and Y directions. Having got a value for the distances we then test for these values being negative and if they are we correct the relevant direction variables to reflect this. We then make sure that we have positive values for both distance variables. We are now ready to determine how many points need to be set for our line. We do this by testing to see which of the two distance variables is the larger. Once we have determined this we set the number of points to be equal to the larger value. We also reduce the value held in the variable that determines the rate of change for the other direction. So if the distance between the 2 X coordinates is larger than that between the 2 Y coordinates we change the YIncrement variable. The new value that is assigned to this variable is less than one and is determined by dividing the smaller distance by the longer. We are now, finally, ready to draw our line. See if you can work out how the X and Y coordinates are finally determined in the body of the for-next loop.
OK so how do we go about optimising this? Well first we need to analyse it in a little more depth. Looking at it a bit more closely it becomes apparent that *both* the longest and shortest distances are important. We have already established that the longest distance is the number of pixels (-1) that we need to turn on for our line. The shortest distance is the number of times we need to alter our other coordinate. For example if the longest distance is in the X direction then we will need to change our Y coordinate DistanceY times. We can use this fact a little later to enable us to optimise our routine.
Now as our major concern is to speed this routine up, the most obvious change would be to convert it from floating point to integer because floating point operations are *slow* by comparison. This is easy enough until we get to the point where fractions are used. However there is a way around this. In order to illustrate this I will assume that the distance between the two X coordinates is the longest. Looking at our routine we can see that in this case our DistanceX corresponds to an IncrementX of precisely 1. What this does is to ensure that for every pass through our for-next loop, a new pixel is set in the X direction. We also see that our IncrementY is a fraction of 1. This means that it takes a more than 1 pass (except in one special case mentioned later) through our for-next loop before we change the Y coordinate of the pixels that we are setting. We can simulate this by use of a variable that holds an intermediate value. What we do is to assign a value of zero to this variable before we enter the for-next loop. Then on every pass through the loop we add the DistanceY to this variable and compare the result with our DistanceX. When the value in our variable equals or exceeds that of DistanceX we alter the Y coordinate and subtract the value of DistanceX from it.
We are now almost there. We can now (if we so desire) convert our line drawing routine from being floating point to integer. However there is still some optimisation we can do to our routine. Again the 2 distance variables are central to this. This is because there are some cases where we do not need to do any comparisons within the for-next loop. Remember, every time that we need to make a comparison we are using processor time. Fortunately these cases are easy enough to detect by examining the values of the 2 distance variables.
The first special case is detected when both distance variables hold the value zero. When this is the case it means that we are dealing with a single pixel that needs to set and not a line to be drawn so we can use PSET and return from our SUB.
The second case is where the DistanceX variable holds zero and DistanceY does not. This means that we need to draw a vertical line.
In the third case it is DistanceY that holds zero and DistanceX does not. In this case we need to draw a horizontal line.
The final special case is where neither distance variable holds zero but both contain the same value. This is where we need to draw a diagonal line at 45 degrees (at least in modes with square pixels). This means that for each new pixel there is a new X and Y coordinate pair.
This leaves the 2 cases that will be used most often. Where the DistanceX is greater than the DistanceY and where the DistanceY is greater than the DistanceX. As we have separated out the other 4 cases in the interests of speed optimisation it makes sense to do the same for this last pair of cases.
The final design decision that I have taken is to implement the whole thing as a number of SUBs. This makes it easier to test and also, I hope, easier to understand.
Code: (Select All)
CONST FromX = 10
CONST FromY = 10
CONST ToX = 310
CONST ToY = 190
SCREEN 13
_FullScreen _SquarePixels
FOR Index = 1 TO 5
LINE (FromX, FromY)-(ToX, ToY), 15
Sleep
DDE2 FromX, FromY, ToX, ToY, 12
Sleep
NEXT Index
SLEEP
END
SUB DDE2 (X1%, Y1%, X2%, Y2%, Colour%)
XLength% = X2% - X1%
XIncrement% = SGN(XLength%)
XLength% = XLength% * XIncrement%
YLength% = Y2% - Y1%
YIncrement% = SGN(YLength%)
YLength% = YLength% * YIncrement%
IF XLength% = 0 AND YLength% = 0 THEN
PSET (X1%, Y1%), Colour%
ELSEIF XLength% = YLength% THEN
Do45Degrees X1%, Y1%, XIncrement%, YIncrement%, XLength%, Colour%
ELSEIF XLength% = 0 THEN
DoVertical X1%, Y1%, Y2%, YIncrement%, Colour%
ELSEIF YLength% = 0 THEN
DoHorizontal X1%, X2%, Y1%, XIncrement%, Colour%
ELSEIF XLength% > YLength% THEN
XGreater X1%, Y1%, XLength%, YLength%, XIncrement%, YIncrement%, Colour%
ELSE
YGreater X1%, Y1%, XLength%, YLength%, XIncrement%, YIncrement%, Colour%
END IF
END SUB
SUB Do45Degrees (XStart%, YStart%, XIncrement%, YIncrement%, Length%, Colour%)
X% = XStart%
Y% = YStart%
PSET (X%, Y%), Colour%
FOR Index% = 1 TO Length%
X% = X% + XIncrement%
Y% = Y% + YIncrement%
PSET (X%, Y%), Colour%
NEXT Index%
END SUB
SUB DoHorizontal (X1%, X2%, Y%, XIncrement%, Colour%)
FOR X% = X1% TO X2% STEP XIncrement%
PSET (X%, Y%), Colour%
NEXT X%
END SUB
SUB DoVertical (X%, Y1%, Y2%, YIncrement%, Colour%)
FOR Y% = Y1% TO Y2% STEP YIncrement%
PSET (X%, Y%), Colour%
NEXT Y%
END SUB
SUB XGreater (XStart%, YStart%, XLength%, YLength%, XIncrement%, YIncrement%, Colour%)
X% = XStart%
Y% = YStart%
ChangeY% = 0
PSET (X%, Y%), Colour%
FOR Index% = 1 TO XLength%
X% = X% + XIncrement%
ChangeY% = ChangeY% + YLength%
IF ChangeY% >= XLength% THEN
Y% = Y% + YIncrement%
ChangeY% = ChangeY% - XLength%
END IF
PSET (X%, Y%), Colour%
NEXT Index%
END SUB
SUB YGreater (XStart%, YStart%, XLength%, YLength%, XIncrement%, YIncrement%, Colour%)
X% = XStart%
Y% = YStart%
ChangeX% = 0
PSET (X%, Y%), Colour%
FOR Index% = 1 TO YLength%
Y% = Y% + YIncrement%
ChangeX% = ChangeX% + XLength%
IF ChangeX% >= YLength% THEN
X% = X% + XIncrement%
ChangeX% = ChangeX% - YLength%
END IF
PSET (X%, Y%), Colour%
NEXT Index%
END SUBFinally a few notes.
IMPORTANT - There is absolutely *no* error detection in either routine! So be careful and add them in yourself. This was done for clarity.
At this point you may be saying 'But QB already has a LINE command, why do we need another one? Not only that, but this new line does less than the built in one!' True, but the built-in commands won't work with any of the varieties of modex. And what happens if for some reason you need to write a line drawing routine in some other language say assembly? Well now you've got an algorithm that you can use.
Once you've run these routines you may be saying 'Well it appears to work but it doesn't draw exactly the same line as the built-in routine.' True again <g>. This just shows that there are a number of different algorithms that can be used to achieve the same end. I strongly suspect that the built-in routine is a variety of the more commonly used Bresenham algorithm. Because the Bresenham algorithm has error-correction built-in it draws a more accurate line, but this can slow the drawing down. Even though the Bresenham algorithm is more accurate both algorithms start and end at exactly the same point, so the choice is yours <g>.
Fill and Doros follow in next 2 posts.
TR
RE: Optimizing for Speed - TarotRedhand - 05-08-2022
Here is the integer circle drawing routine including a small demo -
Doros.BAS
Code: (Select All)
Screen 12 'square pixels
_FullScreen _SquarePixels
CC% = 1
For Radius% = 50 To 190 Step 10
DrawCircle 320, 240, Radius%, CC%
CC% = CC% + 1
_Delay 0.125
Next Radius%
End
Sub DrawCircle (XCenter%, YCenter%, Radius%, Colour%)
S% = Radius%
X% = S%
Y% = 0
For Octant% = 1 To 8
If (Octant% And 1) = 0 Then
S% = S% + X% * 2
Do While Y% >= 0
S% = S% - Y% * 2 + 1
Y% = Y% - 1
If S% < 0 Then
S% = S% + X% * 2 + 2
X% = X% + 1
End If
If X% <> Y% Then
Select Case Octant%
Case 1
ActualX% = XCenter% + X%
ActualY% = YCenter% + Y%
Case 2
ActualX% = XCenter% + Y%
ActualY% = YCenter% + X%
Case 3
ActualX% = XCenter% - Y%
ActualY% = YCenter% + X%
Case 4
ActualX% = XCenter% - X%
ActualY% = YCenter% + Y%
Case 5
ActualX% = XCenter% - X%
ActualY% = YCenter% - Y%
Case 6
ActualX% = XCenter% - Y%
ActualY% = YCenter% - X%
Case 7
ActualX% = XCenter% + Y%
ActualY% = YCenter% - X%
Case 8
ActualX% = XCenter% + X%
ActualY% = YCenter% - Y%
End Select
PSet (ActualX%, ActualY%), Colour%
End If
Loop
Else
S% = S% - X% * 2
Do While Y% <= X%
Select Case Octant%
Case 1
ActualX% = XCenter% + X%
ActualY% = YCenter% + Y%
Case 2
ActualX% = XCenter% + Y%
ActualY% = YCenter% + X%
Case 3
ActualX% = XCenter% - Y%
ActualY% = YCenter% + X%
Case 4
ActualX% = XCenter% - X%
ActualY% = YCenter% + Y%
Case 5
ActualX% = XCenter% - X%
ActualY% = YCenter% - Y%
Case 6
ActualX% = XCenter% - Y%
ActualY% = YCenter% - X%
Case 7
ActualX% = XCenter% + Y%
ActualY% = YCenter% - X%
Case 8
ActualX% = XCenter% + X%
ActualY% = YCenter% - Y%
End Select
PSet (ActualX%, ActualY%), Colour%
S% = S% + Y% * 2 + 1
Y% = Y% + 1
If S% >= 0 Then
S% = S% - X% * 2 + 2
X% = X% - 1
End If
Loop
End If
Next Octant%
End SubTR
RE: Optimizing for Speed - TarotRedhand - 05-08-2022
And the flood fill routine that makes use of a simple stack. TBH, I was actually quite proud of this one. Only problem is that modern machines are so fast that (oh irony of ironies) you'll have to add in delays to see how it works like in the old 8/16 bit days.
Fill.BAS
Code: (Select All)
Const TRUE = -1
Const FALSE = Not TRUE
Const MaxX% = 319 'SCREEN 13
Const MaxY% = 199 'SCREEN 13
Screen 13
_FullScreen _SquarePixels
Line (50, 50)-(250, 140), 14, B
Line (100, 70)-(200, 125), 14, B
Line (60, 60)-(90, 90), 14, B
Line (70, 100)-(95, 120), 14, B
Circle (225, 75), 20, 14
Sleep
SeedFill 225, 100, 12, 14
Sleep
End
Sub InitialiseStack (MyStack%(), TopOfStack%, StackEmpty%)
For Index% = 1 To 200
MyStack%(Index%, 1) = 0
MyStack%(Index%, 2) = 0
Next
TopOfStack% = 0
StackEmpty% = TRUE
End Sub
Sub Push (X%, Y%, MyStack%(), TopOfStack%, StackEmpty%)
TopOfStack% = TopOfStack% + 1
MyStack%(TopOfStack%, 1) = X%
MyStack%(TopOfStack%, 2) = Y%
StackEmpty% = FALSE
End Sub
Sub Pop (X%, Y%, MyStack%(), TopOfStack%, StackEmpty%)
X% = MyStack%(TopOfStack%, 1)
Y% = MyStack%(TopOfStack%, 2)
TopOfStack% = TopOfStack% - 1
StackEmpty% = (TopOfStack% = 0)
End Sub
Sub SeedFill (SeedX%, SeedY%, FillColour%, BorderColour%)
Dim MyStack%(1 To 200, 1 To 2)
InitialiseStack MyStack%(), TopOfStack%, StackEmpty%
Push SeedX%, SeedY%, MyStack%(), TopOfStack%, StackEmpty%
Do While Not StackEmpty%
Pop X%, Y%, MyStack%(), TopOfStack%, StackEmpty%
PSet (X%, Y%), FillColour%
SaveX% = X%
SaveY% = Y%
X% = X% + 1
Do
If X% > MaxX% Then Exit Do
Colour% = Point(X%, Y%)
If Colour% = BorderColour% Then Exit Do
PSet (X%, Y%), FillColour%
X% = X% + 1
Loop
RightX% = X% - 1
X% = SaveX%
If X% > 0 Then
X% = X% - 1
Do
Colour% = Point(X%, Y%)
If Colour% = BorderColour% Then Exit Do
PSet (X%, Y%), FillColour%
If X% = 0 Then Exit Do
X% = X% - 1
Loop
End If
If X% = 0 Then
LeftX% = X%
Else
X% = X% + 1
LeftX% = X%
End If
Y% = Y% + 1
If Y% <= MaxY% Then
Do While X% <= RightX%
Colour% = Point(X%, Y%)
If ((Colour% = FillColour%) Or (Colour% = BorderColour%)) Then
Do
X% = X% + 1
If X% >= RightX% Then Exit Do
Colour% = Point(X%, Y%)
If ((Colour% <> FillColour%) And (Colour% <> BorderColour%)) Then Exit Do
Loop
Else
Push X%, Y%, MyStack%(), TopOfStack%, StackEmpty%
Do
X% = X% + 1
If X% >= RightX% Then Exit Do
Colour% = Point(X%, Y%)
If ((Colour% = FillColour%) Or (Colour% = BorderColour%)) Then Exit Do
Loop
End If
Loop
End If
X% = LeftX%
Y% = SaveY% - 1
If ((Y% >= 0) And (Y% < MaxY%)) Then
Do While X% <= RightX%
Colour% = Point(X%, Y%)
If ((Colour% = FillColour%) Or (Colour% = BorderColour%)) Then
Do
X% = X% + 1
If X% >= RightX% Then Exit Do
Colour% = Point(X%, Y%)
If ((Colour% <> FillColour%) And (Colour% <> BorderColour%)) Then Exit Do
Loop
Else
Push X%, Y%, MyStack%(), TopOfStack%, StackEmpty%
Do
X% = X% + 1
If X% >= RightX% Then Exit Do
Colour% = Point(X%, Y%)
If ((Colour% = FillColour%) Or (Colour% = BorderColour%)) Then Exit Do
Loop
End If
Loop
End If
Loop
End SubTR