Is this fast enough as general circle fill?

[Petr]

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]

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]

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]

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: QB64: [Select]

1. DIM SHARED m AS _MEM
2. J& = _NEWIMAGE(800, 600, 32)
3. m = _MEMIMAGE(J&)
4. SCREEN J&
5.  
6. T = TIMER
7.  
8. FOR test = 1 TO 1000
9.     vinceCircleFill 400, 300, 200, _RGB32(0, 255, 0)
10. NEXT test
11.  
12. PRINT TIMER - T
13.  
14. SUB vinceCircleFill (x AS LONG, y AS LONG, R AS LONG, C AS _UNSIGNED LONG)
15.     x0 = R
16.     y0 = 0
17.     e = 0
18.     DO WHILE y0 < x0
19.         IF e <= 0 THEN
20.             y0 = y0 + 1
21.             MEM_LINE x - x0, y + y0, x + x0, y + y0, C
22.             MEM_LINE x - x0, y - y0, x + x0, y - y0, C
23.             e = e + 2 * y0
24.         ELSE
25.             MEM_LINE x - y0, y - x0, x + y0, y - x0, C
26.             MEM_LINE x - y0, y + x0, x + y0, y + x0, C
27.             x0 = x0 - 1
28.             e = e - 2 * x0
29.         END IF
30.     LOOP
31.     MEM_LINE x - R, y, x + R, y, C
32. END SUB
33.  
34. SUB MEM_LINE (x1t AS INTEGER, y1t AS INTEGER, x2t AS INTEGER, y2t AS INTEGER, clr AS LONG)
35.     DEFLNG A-Z
36.     $CHECKING:OFF
37.     w = _WIDTH
38.     x1 = x1t * 4: x2 = x2t * 4
39.     y1 = y1t * w * 4: y2 = y2t * w * 4
40.     dX = x2 - x1
41.     dY = y2 - y1
42.  
43.     x = x1: y = y1
44.     IF dX >= dY THEN
45.         inc = dY \ dX
46.         DO WHILE x <> x2
47.             x = x + 4
48.             y = y + inc
49.             _MEMPUT m, m.OFFSET + y + x, clr
50.         LOOP
51.     ELSE
52.         inc = dX \ dY
53.         DO WHILE y <> y2
54.             x = x + inc
55.             y = y + w
56.             _MEMPUT m, m.OFFSET + y + x, clr
57.         LOOP
58.     END IF
59.     IF x1 = x2 THEN
60.         d = y1
61.         DO UNTIL d > y2
62.             _MEMPUT m, m.OFFSET + d + x1, clr
63.             d = d + w
64.         LOOP
65.     END IF
66.     IF y1 = y2 THEN
67.         d = x1
68.         DO UNTIL d > x2
69.             _MEMPUT m, m.OFFSET + y1 + d, clr
70.             d = d + 4
71.         LOOP
72.     END IF
73.     $CHECKING:ON
74. END SUB
75.  

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]

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. ;)

[SMcNeill]

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]

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]

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]

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)

[bplus]

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:

[bplus]

Oh it was Petr's mod of my code that CLS was not needed.

Still do need it in my original example.

[Petr]

Bplus, You need NOT CLS IF YOU USE HARDWARE IMAGES (loadimage ,33).  Software screen is in every loop owerwrited using _PUTIMAGE.

[bplus]

Thanks Petr, I think I got it now, the use of a hardware image that is.

[_vince]

Does anyone happen to have a filled ellipse routine?  Preferably something on the performance level of Steve's

[bplus]

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: QB64: [Select]

1. _TITLE "Ellipse and arc tests 2017-10-29 bplus"
2. CONST xmax = 800
3. CONST ymax = 600
4.  
5. SCREEN _NEWIMAGE(xmax, ymax, 32)
6. _SCREENMOVE 360, 60
7.  
8. COLOR &HFFFF0000
9. fEllipse 400, 300, 350, 290
10. COLOR &HFF000000
11. lastr = 100
12. DO
13.     ellipse 400, 300, lastr, 290
14.     lastr = .5 * (350 - lastr) + lastr + 10
15.     IF 350 - lastr < 10 THEN EXIT DO
16. LOOP
17. SLEEP
18.  
19. SUB fEllipse (CX AS LONG, CY AS LONG, xRadius AS LONG, yRadius AS LONG)
20.     DIM scale AS SINGLE, x AS LONG, y AS LONG
21.     scale = yRadius / xRadius
22.     LINE (CX, CY - yRadius)-(CX, CY + yRadius), , BF
23.     FOR x = 1 TO xRadius
24.         y = scale * SQR(xRadius * xRadius - x * x)
25.         LINE (CX + x, CY - y)-(CX + x, CY + y), , BF
26.         LINE (CX - x, CY - y)-(CX - x, CY + y), , BF
27.     NEXT
28. END SUB
29.  
30. SUB ellipse (CX AS LONG, CY AS LONG, xRadius AS LONG, yRadius AS LONG)
31.     DIM scale AS SINGLE, xs AS LONG, x AS LONG, y AS LONG
32.     DIM lastx AS LONG, lasty AS LONG
33.     scale = yRadius / xRadius: xs = xRadius * xRadius
34.     PSET (CX, CY - yRadius): PSET (CX, CY + yRadius)
35.     lastx = 0: lasty = yRadius
36.     FOR x = 1 TO xRadius
37.         y = scale * SQR(xs - x * x)
38.         LINE (CX + lastx, CY - lasty)-(CX + x, CY - y)
39.         LINE (CX + lastx, CY + lasty)-(CX + x, CY + y)
40.         LINE (CX - lastx, CY - lasty)-(CX - x, CY - y)
41.         LINE (CX - lastx, CY + lasty)-(CX - x, CY + y)
42.         lastx = x: lasty = y
43.     NEXT
44. END SUB
45.  
46.  

Yeah, I recall Steve? saying line with BF was actually faster than plain old line. (Oh, I have that!)