Draw that Circle

[SMcNeill]

One big point of efficiency is to swap to _MEMPUT over _MEMFILL. It's hard to beat a simple _MEMPUT when it comes to working with shoving values into memory.

Code: (Select All)

_Title "Fast Circle Test"

Dim As Long scrn
Dim As Long count
Dim As Single t0, t1
Dim As String en

Type tRESULTS
    As Single time
    As String test
End Type

Dim As tRESULTS res(10)

scrn = _NewImage(800, 500, 256)
Screen scrn
Const iterations = 640000
'____________________________________________________________________________________________________________________________________

res(0).test = "Bresenham Normal Test"
Locate 20, 1
Print res(0).test
Input "Press Enter to start ..."; en

count = 0
t0 = Timer
Do
    '   CircleBresenham Int(Rnd * 800), Int(Rnd * 500), 30, Int(Rnd * 255)
    count = count + 1
Loop While count < iterations
t1 = Timer
res(0).time = t1 - t0
'____________________________________________________________________________________________________________________________________
res(1).test = "Bresenham MEM 1bpp (no clip)"
Locate 20, 1
Print res(1).test
Input "Press Enter to start ..."; en

count = 0
t0 = Timer
Dim As _MEM scr
scr = _MemImage(scrn)
Do
    CircleBresenham1bpp scr, 30 + Int(Rnd * 740), 30 + Int(Rnd * 440), 30, Int(Rnd * 255)
    count = count + 1
Loop While count < iterations
_MemFree scr
t1 = Timer
res(1).time = t1 - t0
'____________________________________________________________________________________________________________________________________
res(2).test = "Bresenham MEM 4bpp (no clip)"
Locate 20, 1
Print res(2).test
Input "Press Enter to start ..."; en

_Title "Fast Circle Test"
scrn = _NewImage(800, 500, 32)
Screen scrn
Locate 20, 1
count = 0
t0 = Timer
scr = _MemImage(scrn)
Do
    CircleBresenham4bpp scr, 30 + Int(Rnd * 740), 30 + Int(Rnd * 440), 30, _RGB32(Int(Rnd * 255), Int(Rnd * 255), Int(Rnd * 255))
    count = count + 1
Loop While count < iterations
_MemFree scr
t1 = Timer
res(2).time = t1 - t0
'____________________________________________________________________________________________________________________________________

Print "Circle count:"; iterations
For count = 0 To 2
    Print res(count).test; "  Time:"; res(count).time
Next


'____________________________________________________________________________________________________________________________________
Sub CircleBresenham (xc As Long, yc As Long, r As Long, c As Long)
    Dim As Long e, x, y, w
    Dim As Long l0, l1
    w = _Width(0) * 4
    x = r
    y = 0
    e = 0
    $Checking:Off
    Do
        l0 = x * 2
        l1 = y * 2

        Line (xc - x, yc - y)-(xc - x + l0, yc - y), c
        Line (xc - x, yc + y)-(xc - x + l0, yc + y), c
        Line (xc - y, yc - x)-(xc - y + l1, yc - x), c
        Line (xc - y, yc + x)-(xc - y + l1, yc + x), c

        If x <= y Then Exit Do
        e = e + y * 2 + 1
        y = y + 1
        If e > x Then
            e = e + 1 - x * 2
            x = x - 1
        End If
    Loop
    $Checking:On
End Sub


Sub CircleBresenham1bpp (scr As _MEM, xc As Long, yc As Long, r As Long, c As _Unsigned _Byte)
    Dim As Long e, x, y, w
    Dim As Long xof0, xof1, xof2, xof3, l0, l1
    Dim As Long yof0, yof1, yof2, yof3
    Dim As Long xq0, yq0, xq1, yq1, xq2, yq2, xq3, yq3
    w = _Width(0)
    x = r
    y = 0
    e = 0
    $Checking:Off
    Do
        l0 = x * 2
        l1 = y * 2

        xq0 = xc - x
        yq0 = yc - y
        xof0 = xq0
        yof0 = yq0 * w
        _MemFill scr, scr.OFFSET + xof0 + yof0, l0, c As _UNSIGNED _BYTE
        xq1 = xc - x
        yq1 = yc + y
        xof1 = xq1
        yof1 = yq1 * w
        _MemFill scr, scr.OFFSET + xof1 + yof1, l0, c As _UNSIGNED _BYTE
        xq2 = xc - y
        yq2 = yc - x
        xof2 = xq2
        yof2 = yq2 * w
        _MemFill scr, scr.OFFSET + xof2 + yof2, l1, c As _UNSIGNED _BYTE
        xq3 = xc - y
        yq3 = yc + x
        xof3 = xq3
        yof3 = yq3 * w
        _MemFill scr, scr.OFFSET + xof3 + yof3, l1, c As _UNSIGNED _BYTE

        If x <= y Then Exit Do
        e = e + y * 2 + 1
        y = y + 1
        If e > x Then
            e = e + 1 - x * 2
            x = x - 1
        End If
    Loop
    $Checking:On
End Sub

Sub CircleBresenham4bpp (scr As _MEM, xc As Long, yc As Long, r As Long, c As _Unsigned Long)
    Dim As _Offset e, x, y, w
    Dim As _Offset xof0, xof1, xof2, xof3, l0, l1
    Dim As _Offset yof0, yof1, yof2, yof3
    Dim As _Offset xq0, yq0, xq1, yq1, xq2, yq2, xq3, yq3
    w = _Width(0) * 4
    x = r
    y = 0
    e = 0
    $Checking:Off
    'start time of 7.03 seconds
    'by swapping to memput, the time is now 1.9 seconds.
    Dim As _Offset start, finish
    Do
        l0 = x * 8
        l1 = y * 8
        xq0 = scr.OFFSET + (xc - x) * 4
        yq0 = (yc - y) * w
        ' _MemFill scr, xq0 + yq0, l0, c
        start = xq0 + yq0
        finish = start + l0
        Do
            _MemPut scr, start, c
            start = start + 4
        Loop Until start > finish
        yq1 = (yc + y) * w
        '_MemFill scr, xq0 + yq1, l0, c
        start = xq0 + yq1
        finish = start + l0
        Do
            _MemPut scr, start, c
            start = start + 4
        Loop Until start > finish


        xq2 = scr.OFFSET + (xc - y) * 4
        yq2 = (yc - x) * w
        '_MemFill scr, xq2 + yq2, l1, c
        start = xq2 + yq2
        finish = start + l1
        Do
            _MemPut scr, start, c
            start = start + 4
        Loop Until start > finish

        yq3 = (yc + x) * w
        '_MemFill scr, xq2 + yq3, l1, c
        start = xq2 + yq3
        finish = start + l1
        Do
            _MemPut scr, start, c
            start = start + 4
        Loop Until start > finish
        If x <= y Then Exit Do
        e = e + y + y + 1
        y = y + 1
        If e > x Then
            e = e + 1 - x - x
            x = x - 1
        End If
    Loop
    $Checking:On
End Sub

This went from 7 seconds down to less than 2 seconds on my PC. All you'd need to do is comment out the _MEMPUT and uncomment the _MEMFILL statements, and you can see the difference at play.

I think you'd really need to optimize the math itself to reduce times much more. For example, instead of counting x = x + 1, count x = x + 4 (move by 4 bytes instead of 1 pixel coordinate). Same with y. Instead of y = y + 1, y = y + w. (move a row of 4 byte pixels instead of by a coordinate) Then you can get rid of the * 4 and * w operators, simplifying the number of processes which your loop has to make before finishing.

But your biggest change is going to be _MEMPUT over _MEMFILL (a 300%+ speed improvement!).