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

#### Petr

• I am instructed.
##### Re: Is this fast enough as general circle fill?
« Reply #45 on: June 27, 2018, 02: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!

#### SkyCharger001

##### Re: Is this fast enough as general circle fill?
« Reply #46 on: June 27, 2018, 05: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)

#### _vince

##### Re: Is this fast enough as general circle fill?
« Reply #47 on: June 27, 2018, 06: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

#### SMcNeill

• QB64 Developer
##### Re: Is this fast enough as general circle fill?
« Reply #48 on: June 27, 2018, 06: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 _MEMJ& = _NEWIMAGE(800, 600, 32)m = _MEMIMAGE(J&)SCREEN J&T = TIMERFOR test = 1 TO 1000    vinceCircleFill 400, 300, 200, _RGB32(0, 255, 0)NEXT testPRINT TIMER - TSUB 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, CEND SUBSUB 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:ONEND 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.  ;)

#### _vince

##### Re: Is this fast enough as general circle fill?
« Reply #49 on: June 27, 2018, 07: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, 07:25:54 PM by v »

#### SMcNeill

• QB64 Developer
##### Re: Is this fast enough as general circle fill?
« Reply #50 on: June 27, 2018, 08: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.

#### codeguy

##### Re: Is this fast enough as general circle fill?
« Reply #51 on: June 27, 2018, 11:31:05 PM »
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.

#### codeguy

##### Re: Is this fast enough as general circle fill?
« Reply #52 on: June 27, 2018, 11:47:43 PM »
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.

#### bplus

##### Re: Is this fast enough as general circle fill?
« Reply #53 on: June 28, 2018, 07: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 + ...

#### bplus

##### Re: Is this fast enough as general circle fill?
« Reply #54 on: June 29, 2018, 05: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 + ...

#### bplus

##### Re: Is this fast enough as general circle fill?
« Reply #55 on: June 29, 2018, 06: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 + ...

#### Petr

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

#### bplus

##### Re: Is this fast enough as general circle fill?
« Reply #57 on: June 30, 2018, 08:29:35 AM »
Thanks Petr, I think I got it now, the use of a hardware image that is.
B = B + ...

#### _vince

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

#### bplus

##### Re: Is this fast enough as general circle fill?
« Reply #59 on: August 30, 2018, 09: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 = 800CONST ymax = 600SCREEN _NEWIMAGE(xmax, ymax, 32)_SCREENMOVE 360, 60COLOR &HFFFF0000fEllipse 400, 300, 350, 290COLOR &HFF000000lastr = 100DO    ellipse 400, 300, lastr, 290    lastr = .5 * (350 - lastr) + lastr + 10    IF 350 - lastr < 10 THEN EXIT DOLOOPSLEEPSUB 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    NEXTEND SUBSUB 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    NEXTEND 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, 09:46:45 AM by bplus »
B = B + ...