Author Topic: Is this fast enough as general circle fill?  (Read 1148 times)

Offline Petr

  • I am instructed.
Re: Is this fast enough as general circle fill?
« Reply #45 on: June 27, 2018, 03:27:20 PM »
Thanks a lot for these tips! I did not know about an integer division so far :-D Yeah, and you're right with math. Why did not I teach it better? Because I have to use it for practical use long after school, 've had it at school all the time, and I did not think of a connection at all at that time! And I started with GWbasic under DOS 5.0 now I can see the equation and I can see how it could be used in the program .... in one case, of the hundreds I can write in the program,and IF IT WORKS, then it is a lot of glory .... :-D . This is funny. Nothing is lost. I will continue to experiment! Thanks a lot!

Re: Is this fast enough as general circle fill?
« Reply #46 on: June 27, 2018, 06:33:54 PM »
I've been thinking and I think I know why BF is faster.
without BF: multiple line segments that need to be calculated using floating point math. (as line can be of any angle)
with BF: Y horizontal lines of length_X that only require integral math.(for initializing the drawing loop)

Re: Is this fast enough as general circle fill?
« Reply #47 on: June 27, 2018, 07:39:21 PM »
I've been thinking and I think I know why BF is faster.
without BF: multiple line segments that need to be calculated using floating point math. (as line can be of any angle)
with BF: Y horizontal lines of length_X that only require integral math.(for initializing the drawing loop)

Any line can be drawn without any floating point math using the this algorithm:
https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

Offline SMcNeill

  • QB64 Developer
Re: Is this fast enough as general circle fill?
« Reply #48 on: June 27, 2018, 07:50:45 PM »
Three more changes to your routine Petr, and the time goes from 3.4 seconds to 2.6, then 1.68, then 1.47....

The fastest version is this one:

Code: [Select]
DIM SHARED m AS _MEM
J& = _NEWIMAGE(800, 600, 32)
m = _MEMIMAGE(J&)
SCREEN J&

T = TIMER

FOR test = 1 TO 1000
    vinceCircleFill 400, 300, 200, _RGB32(0, 255, 0)
NEXT test

PRINT TIMER - T

SUB vinceCircleFill (x AS LONG, y AS LONG, R AS LONG, C AS _UNSIGNED LONG)
    x0 = R
    y0 = 0
    e = 0
    DO WHILE y0 < x0
        IF e <= 0 THEN
            y0 = y0 + 1
            MEM_LINE x - x0, y + y0, x + x0, y + y0, C
            MEM_LINE x - x0, y - y0, x + x0, y - y0, C
            e = e + 2 * y0
        ELSE
            MEM_LINE x - y0, y - x0, x + y0, y - x0, C
            MEM_LINE x - y0, y + x0, x + y0, y + x0, C
            x0 = x0 - 1
            e = e - 2 * x0
        END IF
    LOOP
    MEM_LINE x - R, y, x + R, y, C
END SUB

SUB MEM_LINE (x1t AS INTEGER, y1t AS INTEGER, x2t AS INTEGER, y2t AS INTEGER, clr AS LONG)
    DEFLNG A-Z
    $CHECKING:OFF
    w = _WIDTH
    x1 = x1t * 4: x2 = x2t * 4
    y1 = y1t * w * 4: y2 = y2t * w * 4
    dX = x2 - x1
    dY = y2 - y1

    x = x1: y = y1
    IF dX >= dY THEN
        inc = dY \ dX
        DO WHILE x <> x2
            x = x + 4
            y = y + inc
            _MEMPUT m, m.OFFSET + y + x, clr
        LOOP
    ELSE
        inc = dX \ dY
        DO WHILE y <> y2
            x = x + inc
            y = y + w
            _MEMPUT m, m.OFFSET + y + x, clr
        LOOP
    END IF
    IF x1 = x2 THEN
        d = y1
        DO UNTIL d > y2
            _MEMPUT m, m.OFFSET + d + x1, clr
            d = d + w
        LOOP
    END IF
    IF y1 = y2 THEN
        d = x1
        DO UNTIL d > x2
            _MEMPUT m, m.OFFSET + y1 + d, clr
            d = d + 4
        LOOP
    END IF
    $CHECKING:ON
END SUB

The first change, as I mentioned above, was to change how we think of X/Y and calculate our offset.   It's no longer m.OFFSET + (w * y + x) * 4.  Now it's simply m.OFFSET + y + x....  This changed the speed from 3.4 seconds to 2.6.

The second change, I also did as mentioning above:  I replaced the real-precision division (/) with integer  division (\).  This further improved the speed from 2.6 to 1.68 seconds.

The final change, I noticed that the integer division never actually changes INSIDE the loop. dX and dY aren't changing values, so dX \ dY isn't going to ever generate any altered value.  I calculated the increment ONCE before each loop with inc = dX \ dY, and then used that value inside the loop itself.  Doing math ONCE is faster than doing it multiple times.   This increased the speed from 1.68 seconds to 1.47.

And, when you figure we started with a process that took over 10 seconds to begin with, optimizing it down to only taking 1.47 is quite a boost in overall performance!  It still doesn't compare to the speeds we see from CircleFill, which I plugged in for testing and took 0.32 seconds to do the same thing, but it's a heckuva change from what it was originally.  ;)

Re: Is this fast enough as general circle fill?
« Reply #49 on: June 27, 2018, 08:24:52 PM »
You're also losing a lot of 'cycles' calling the sub from within the circlefill inner loop.  The sub has a bunch of comparisons and such that could be worked into the circlefill algorithm.  Either way, I highly doubt memput is ever going to be faster than line bf. ;)
« Last Edit: June 27, 2018, 08:25:54 PM by v »

Offline SMcNeill

  • QB64 Developer
Re: Is this fast enough as general circle fill?
« Reply #50 on: June 27, 2018, 09:30:32 PM »
You're also losing a lot of 'cycles' calling the sub from within the circlefill inner loop.  The sub has a bunch of comparisons and such that could be worked into the circlefill algorithm.  Either way, I highly doubt memput is ever going to be faster than line bf. ;)

I doubt so either, but it sure has been a nice little routine to showcase a lot of the things which somebody can do to improve run speed inside their programs. 

Re: Is this fast enough as general circle fill?
« Reply #51 on: June 28, 2018, 12:31:05 AM »
As a circle clipping routine, this was a precursor. 42ms/fill@2.16GHz average for 512 random position, r=240 pixels (mars.png). Time is roughly 1/2 for monotone fill.

Re: Is this fast enough as general circle fill?
« Reply #52 on: June 28, 2018, 12:47:43 AM »
Minstep is meant to provide a precise stepping value to avoid missed raster lines. One optimization I did was to store the last radius%*sin(s!) and check if it was >= 1/2 versus current radius%*sin(s!). Part of how I reduced the rendering time for radius% = 240 to (42-45)ms. Also used POINT, using mars.png as the source.

Re: Is this fast enough as general circle fill?
« Reply #53 on: June 28, 2018, 08:15:09 PM »
Hi zigzag,

Yes! First thing I ever tried. Apparently the SQR function takes allot of time!

Also, it has been recently discussed, counter to our intuition that a line is faster with BF than without.



I think Steve's "Gold Standard" method comes from here:
https://en.wikipedia.org/wiki/Midpoint_circle_algorithm


Correction: It was not the SQR function that was taking all the time (although calling a function is slower than doing  integer math).

It was doing a quadrants' worth of calculations! The Gold Standard is only doing calculations for a half a quadrant, an octant, that is main reason it takes over twice as long. (See zigzag reply #27)
B = B + ...
QB64 x 64 v1.2 2018 0228/86 git b30af92
QB64 v1.2 20180228/86 git 6fde149
QB64 v1.2 [dev build]_d84bb00

Re: Is this fast enough as general circle fill?
« Reply #54 on: June 29, 2018, 06:51:59 PM »
Another correction: in reply 20 Petr said I did not need CLS

I don't know what I was thinking when I agreed in reply #21.

Today I retested the code and do need the CLS to clear the disk the mouse is drawing over the "stuff" of random circles serving as background.

Here is screen shot as reminder:
B = B + ...
QB64 x 64 v1.2 2018 0228/86 git b30af92
QB64 v1.2 20180228/86 git 6fde149
QB64 v1.2 [dev build]_d84bb00

Re: Is this fast enough as general circle fill?
« Reply #55 on: June 29, 2018, 07:51:51 PM »
Oh it was Petr's mod of my code that CLS was not needed.

Still do need it in my original example.
B = B + ...
QB64 x 64 v1.2 2018 0228/86 git b30af92
QB64 v1.2 20180228/86 git 6fde149
QB64 v1.2 [dev build]_d84bb00

Offline Petr

  • I am instructed.
Re: Is this fast enough as general circle fill?
« Reply #56 on: June 30, 2018, 06:46:25 AM »
Bplus, You need NOT CLS IF YOU USE HARDWARE IMAGES (loadimage ,33).  Software screen is in every loop owerwrited using _PUTIMAGE.

Re: Is this fast enough as general circle fill?
« Reply #57 on: June 30, 2018, 09:29:35 AM »
Thanks Petr, I think I got it now, the use of a hardware image that is.
B = B + ...
QB64 x 64 v1.2 2018 0228/86 git b30af92
QB64 v1.2 20180228/86 git 6fde149
QB64 v1.2 [dev build]_d84bb00

Re: Is this fast enough as general circle fill?
« Reply #58 on: August 30, 2018, 09:41:47 AM »
Does anyone happen to have a filled ellipse routine?  Preferably something on the performance level of Steve's

Re: Is this fast enough as general circle fill?
« Reply #59 on: August 30, 2018, 10:18:34 AM »
Here is my ellipse and filled ellipse routines, no where near Steve's level of performance. The speed is cut in half at least because you probably have to do a whole quadrants worth of calculations (ellipse not as symmetric as circle).

But I am sure this code can be optimized more than it is:
Code: [Select]
_TITLE "Ellipse and arc tests 2017-10-29 bplus"
CONST xmax = 800
CONST ymax = 600

SCREEN _NEWIMAGE(xmax, ymax, 32)
_SCREENMOVE 360, 60

COLOR &HFFFF0000
fEllipse 400, 300, 350, 290
COLOR &HFF000000
lastr = 100
DO
    ellipse 400, 300, lastr, 290
    lastr = .5 * (350 - lastr) + lastr + 10
    IF 350 - lastr < 10 THEN EXIT DO
LOOP
SLEEP

SUB fEllipse (CX AS LONG, CY AS LONG, xRadius AS LONG, yRadius AS LONG)
    DIM scale AS SINGLE, x AS LONG, y AS LONG
    scale = yRadius / xRadius
    LINE (CX, CY - yRadius)-(CX, CY + yRadius), , BF
    FOR x = 1 TO xRadius
        y = scale * SQR(xRadius * xRadius - x * x)
        LINE (CX + x, CY - y)-(CX + x, CY + y), , BF
        LINE (CX - x, CY - y)-(CX - x, CY + y), , BF
    NEXT
END SUB

SUB ellipse (CX AS LONG, CY AS LONG, xRadius AS LONG, yRadius AS LONG)
    DIM scale AS SINGLE, xs AS LONG, x AS LONG, y AS LONG
    DIM lastx AS LONG, lasty AS LONG
    scale = yRadius / xRadius: xs = xRadius * xRadius
    PSET (CX, CY - yRadius): PSET (CX, CY + yRadius)
    lastx = 0: lasty = yRadius
    FOR x = 1 TO xRadius
        y = scale * SQR(xs - x * x)
        LINE (CX + lastx, CY - lasty)-(CX + x, CY - y)
        LINE (CX + lastx, CY + lasty)-(CX + x, CY + y)
        LINE (CX - lastx, CY - lasty)-(CX - x, CY - y)
        LINE (CX - lastx, CY + lasty)-(CX - x, CY + y)
        lastx = x: lasty = y
    NEXT
END SUB


Yeah, I recall Steve? saying line with BF was actually faster than plain old line. (Oh, I have that!)
« Last Edit: August 30, 2018, 10:46:45 AM by bplus »
B = B + ...
QB64 x 64 v1.2 2018 0228/86 git b30af92
QB64 v1.2 20180228/86 git 6fde149
QB64 v1.2 [dev build]_d84bb00