Text Only | Text with Attachments

QB64.org Forum

Active Forums => QB64 Discussion => Topic started by: codeguy on June 25, 2018, 12:10:00 am

Title: Is this fast enough as general circle fill?
Post by: codeguy on June 25, 2018, 12:10:00 am
Code: QB64: [Select]
  1. Demo&=_newimage(1366,768,256)
  2. Screen demo&
  3. St!=timer(.001)
  4. Radius=1000
  5. Cx=radius
  6. Cy=radius
  7. Minstep!=1/(2*_pi*radius)
  8. For s=0 to 90 step minstep!
  9. Px%=radius*cos(s!)
  10. Py%=radius*sin(s!)
  11. Line(cx%-px%,cy%+py%)-(cx%+px%,cy%+py%),127
  13. F!=timer(.001)
  14. Locate 1,1
  15. Print f!-st!;
  19.  
Title: Re: Is this fast enough as general circle fill?
Post by: codeguy on June 25, 2018, 12:32:03 am
With a small circle, the difference isn't that huge. For a circle of radius = 1000, successive fill by circle lags my algorithm by more than 100 times. 8.2ms versus 9130ms. Successive circle fill at this diameter leaves unfilled sections. My algorithm provides a perfect fill. Feel free to use my code for _CodeGuyQB64PerfectlyFilledCircle
Title: Re: Is this fast enough as general circle fill?
Post by: johnno56 on June 25, 2018, 01:41:53 am
That is one BIG circle!

Any way I got 1.210938 for a radius of 1000.
0.0234375 for a radius of 100.
3.90625e-03 for a radius of 10. (sometimes it was zero)

Hope this helps.

J
Title: Re: Is this fast enough as general circle fill?
Post by: codeguy on June 25, 2018, 03:05:11 am
Haven't compared it to steve's circle fill but I don't think even that would beat this.
Title: Re: Is this fast enough as general circle fill?
Post by: codeguy on June 25, 2018, 04:43:46 am
Quote from: codeguy on June 25, 2018, 12:10:00 am
Code: QB64: [Select]
  1. Demo&=_newimage(1366,768,256)
  2. Screen demo&
  3. St!=timer(.001)
  4. Radius=1000
  5. Cx=radius
  6. Cy=radius
  7. Minstep!=1/(2*_pi*radius)
  8. For s=0 to _pi/2 step minstep!
  9. Px%=radius*cos(s!)
  10. Py%=radius*sin(s!)
  11. Line(cx%-px%,cy%+py%)-(cx%+px%,cy%+py%),127
  13. F!=timer(.001)
  14. Locate 1,1
  15. Print f!-st!;
  19.  
Corrected. Radians, not degrees.
Title: Re: Is this fast enough as general circle fill?
Post by: SMcNeill on June 25, 2018, 04:48:21 am
Here's an experiment for you:  Change the LINE statement to include the BF after the end of it.

Instead of:   LINE (X,y)-(x2,y), color

Use:  LINE (X,y)-(x2,y), color, BF

QB64's C-code has been heavily optimized for the box fill routine, and you'll find it's usually much faster to include the BF for straight lines, than it is to exclude it.

I predict you'll see a considerable improvement in run speeds.
Title: Re: Is this fast enough as general circle fill?
Post by: codeguy on June 25, 2018, 04:54:21 am
And that's 97.6ms. Still 30 times slower than steve's, BUT no artifacts. Steve's algo seems to leave some pixels untouched along radius when overlaid successive reduced radius circle fill or mine. Steve's algo seems to be 30 times faster though.
Title: Re: Is this fast enough as general circle fill?
Post by: codeguy on June 25, 2018, 05:07:22 am
Using bf, r=1000, 0ms. Not kidding. Over 16 runs each, see picture.
Title: Re: Is this fast enough as general circle fill?
Post by: codeguy on June 25, 2018, 05:16:23 am
For 64 iterations of yours and mine, slightly modified, but exact same results: the modification checks if py >= previous py+.5 (one-half vertical pixel difference) and now px and py are single-precision.
Title: Re: Is this fast enough as general circle fill?
Post by: SMcNeill on June 25, 2018, 05:20:05 am
So, in future reference, *always* use BF with LINE when possible.  ;)
Title: Re: Is this fast enough as general circle fill?
Post by: johnno56 on June 25, 2018, 05:37:37 am
Wow. SO much faster. many times the 1000 radius was instantaneous. I did't both testing the smaller sizes. Cool.  :D
Title: Re: Is this fast enough as general circle fill?
Post by: SMcNeill on June 25, 2018, 05:41:13 am
And a few quick points here:

1) Cx, Cy should include the percent % symbol so they work in your equation, without being 0 always.
2) This only makes HALF the circle.  Change radius to 250 and center  it at 250,250 (the Cx,Cy change will allow that easily enough), and you'll easily see you only have half the circle.

Make the full circle and then compare times, if you want to see which runs faster for you.  ;)

(A simple addition of a second line statement to draw from top to bottom (X, Cy% -py%) instead of (X, Cy% + py%) will do it for you.). 
Title: Re: Is this fast enough as general circle fill?
Post by: codeguy on June 25, 2018, 05:41:26 am
My algorithm in picture. Seems about 10 times faster than yours. Might wanna check it out.
Code: QB64: [Select]
  1. Radius%=1000
  2. Cx%=radius%
  3. Cy%=radius%
  4. Ir!=1/radius%
  5. Fc!=_pi/2
  6. Ly!=radius%*sin(0)
  7. For s!=0 to fc!-ir! Step ir!
  8. Py!=radius%*sin(s!)
  9. If py!-ly!>=.5 then
  10. Px!=radius%*cos(s!)
  11. Line(cx%-px!,cy%-py!)-(cx%+px!,cy%-py!),63,bf
  12. Ly!=py!
  15.  
Title: Re: Is this fast enough as general circle fill?
Post by: codeguy on June 25, 2018, 06:53:58 am
Corrected, mine is about 50% slower. Adapted mine to circle clip and it clips to circle equal to the lesser of height or width of an image. On mars.png, it's roughly 46.875ms. Good for that. Circle fill for same size is 19-24ms. You win, but maybe my circle clip will prevail somewhere.
Title: Re: Is this fast enough as general circle fill?
Post by: SMcNeill on June 25, 2018, 09:19:03 am
Quote from: codeguy on June 25, 2018, 06:53:58 am
Corrected, mine is about 50% slower. Adapted mine to circle clip and it clips to circle equal to the lesser of height or width of an image. On mars.png, it's roughly 46.875ms. Good for that. Circle fill for same size is 19-24ms. You win, but maybe my circle clip will prevail somewhere.

Corrected, yours basically IS mine; you've just taken the time to reinvent it for yourself to understand how/why it works.  The only real difference in this and my CircleFill is a few minor optimization tweaks.  DO loops instead of FOR.  A few pre calculated values such as _PI /2.  Nothing major really; just little differences which added together create a minor speed difference. 

Compare the two closely, side-by-side, and you'll see how similar they actually are.  ;D
Title: Re: Is this fast enough as general circle fill?
Post by: bplus on June 25, 2018, 09:30:55 am
Slower than Steve's but this fills a regular polygon that approaches a circle as increase the number of sides. It fills the circle with an image and the image is based according to location of mouse (or where ever you want a circular part of image).

This is a circle fill method based on _MAPTRIANGLE, I think it is fast enough to impress!

Code: QB64: [Select]
  1. 'Poly Image Demo 2
  2. 'by bplus started 2018-06-22
  3.  
  4. CONST xmax = 800
  5. CONST ymax = 600
  6. SCREEN _NEWIMAGE(xmax, ymax, 32)
  7. _SCREENMOVE 100, 20
  8.  
  9. stars& = _LOADIMAGE("stars.png")
  10. stuff& = _NEWIMAGE(xmax, ymax, 32)
  11. _DEST stuff&
  12. FOR i = 1 TO 100
  13.     CIRCLE (RND * xmax, RND * ymax), RND * 100, _RGB32(RND * 255, RND * 255, RND * 255)
  17.     CLS
  18.     _SOURCE stuff&
  19.     _PUTIMAGE
  21.     polygonImage stars&, _MOUSEX, _MOUSEY, 250, 50
  22.     _DISPLAY
  23.     _LIMIT 30
  25.  
  26.  
  27. SUB polygonImage (ImageHandle&, xOrigin, yOrigin, radius, nVertex)
  28.     polyAngle = _PI(2) / nVertex
  29.     x1 = xOrigin + radius * COS(polyAngle)
  30.     y1 = yOrigin + radius * SIN(polyAngle)
  31.     FOR i = 2 TO nVertex + 1
  32.         x2 = xOrigin + radius * COS(i * polyAngle)
  33.         y2 = yOrigin + radius * SIN(i * polyAngle)
  34.         _MAPTRIANGLE (xOrigin, yOrigin)-(x1, y1)-(x2, y2), ImageHandle& TO(xOrigin, yOrigin)-(x1, y1)-(x2, y2), 0
  35.         x1 = x2: y1 = y2
  36.     NEXT
  38.  

Attached is code with Stars.png for testing with image file.
Title: Re: Is this fast enough as general circle fill?
Post by: SMcNeill on June 25, 2018, 09:43:40 am
For the absolute FASTEST filled circle routine, what one could do is simply pre-calculate the start and end points for each line of a circle of X size, and then save that data into an array.  Then, instead of the program having to do any math, it'd just lookup the plot points directly from memory, and insta-draw the circle.

Take all the math out ahead of time, utilize a lookup table, and it'd be much quicker than anything anybody has shared previously.  Only drawback would be the memory required to store the lookup table, which, in regards to modern OS memory limits, really shouldn't be that big an issue at all, honestly. 
Title: Re: Is this fast enough as general circle fill?
Post by: bplus on June 25, 2018, 09:47:54 am
Here is my test code comparing the 2 Methods with just one color. Over 2 times slower but not 10 or 1000 times...

Code: QB64: [Select]
  1. _TITLE "Circle fill: Steve's method versus MapTriangle by bplus started 2018-06-22"
  2. 'QB64 version 2017 1106/82 (the day before they switched to version 1.2)
  3.  
  4. 'steve's method wins easily
  5.  
  6. CONST xmax = 800
  7. CONST ymax = 600
  8. SCREEN _NEWIMAGE(xmax, ymax, 32)
  9. _SCREENMOVE 360, 60
  10. start## = TIMER
  11. 'this is 10 X 10 X 10 runs on circle with different colors
  12. FOR r = 246 TO 255
  13.     FOR g = 246 TO 255
  14.         FOR b = 1 TO 10
  15.             'fpcir xmax / 2, ymax / 2, 300, _RGB32(r, g, b)
  16.             fcirc xmax / 2, ymax / 2, 300, _RGB32(r, g, b)
  17.         NEXT
  18.     NEXT
  20. COLOR _RGB32(255, 255, 255)
  21. PRINT TIMER - start##
  22.  
  23. SUB fpcir (xOrigin AS LONG, yOrigin AS LONG, radius AS LONG, K AS _UNSIGNED LONG)
  24.     a& = _NEWIMAGE(1, 1, 32)
  25.     _DEST a&
  26.     PSET (0, 0), K
  27.     _DEST 0
  28.     DIM x1 AS LONG, y1 AS LONG, x2 AS LONG, y2 AS LONG, i AS INTEGER
  29.     DIM polyAngle AS SINGLE
  30.     polyAngle = _PI(2) / 60
  31.     x1 = xOrigin + radius * COS(polyAngle)
  32.     y1 = yOrigin + radius * SIN(polyAngle)
  33.     FOR i = 2 TO 61
  34.         x2 = xOrigin + radius * COS(i * polyAngle)
  35.         y2 = yOrigin + radius * SIN(i * polyAngle)
  36.         _MAPTRIANGLE (0, 0)-(0, 0)-(0, 0), a& TO(xOrigin, yOrigin)-(x1, y1)-(x2, y2), 0
  37.         x1 = x2: y1 = y2
  38.     NEXT
  39.     _FREEIMAGE a& '<<< this is important!
  41.  
  42. SUB fcirc (CX AS LONG, CY AS LONG, R AS LONG, K AS _UNSIGNED LONG)
  43.     DIM subRadius AS LONG, RadiusError AS LONG
  44.     DIM X AS LONG, Y AS LONG
  45.  
  46.     subRadius = ABS(R)
  47.     RadiusError = -subRadius
  48.     X = subRadius
  49.     Y = 0
  50.  
  51.     IF subRadius = 0 THEN PSET (CX, CY): EXIT SUB
  52.  
  53.     ' Draw the middle span here so we don't draw it twice in the main loop,
  54.     ' which would be a problem with blending turned on.
  55.     LINE (CX - X, CY)-(CX + X, CY), K, BF
  56.  
  57.     WHILE X > Y
  58.         RadiusError = RadiusError + Y * 2 + 1
  59.         IF RadiusError >= 0 THEN
  60.             IF X <> Y + 1 THEN
  61.                 LINE (CX - Y, CY - X)-(CX + Y, CY - X), K, BF
  62.                 LINE (CX - Y, CY + X)-(CX + Y, CY + X), K, BF
  63.             END IF
  64.             X = X - 1
  65.             RadiusError = RadiusError - X * 2
  66.         END IF
  67.         Y = Y + 1
  68.         LINE (CX - X, CY - Y)-(CX + X, CY - Y), K, BF
  69.         LINE (CX - X, CY + Y)-(CX + X, CY + Y), K, BF
  70.     WEND
  72.  
  73.  

Might use codeguy's "mini step" to adjust number of triangles to take according to size of (near) circle. Here I just tested a large "circle" polygon with 60 sides for speed.
Title: Re: Is this fast enough as general circle fill?
Post by: Petr on June 25, 2018, 10:23:13 am
Hi Codeguy. I was watching your program, there are two brakes. The first big brake is Minstep !, it's really low for large diameters and that's why it's so slow. Another - but smaller brake is the call of the sinus and cosine functions during rendering. It is far more advantageous to save these values in a field and then to use them directly for drawing. I made some attempts, the LINE command with the parameter, BF is 50 percent faster than without it, and 40 percent slower with the B parameter than without it. Your turn-around solution with only a quarter rotation is very nice, it saves a lot of extra time.

Code: QB64: [Select]
  1.  
  2. '0.105 original
  3. REDIM Px(0) AS SINGLE, Py(0) AS SINGLE
  4. Demo& = _NEWIMAGE(1366, 768, 256)
  5. SCREEN Demo&
  6. St! = TIMER(.001)
  7. Radius = 1000
  8. Cx = Radius
  9. Cy = Radius
  10.  
  11. ' Minstep: When someone rewrite it to function, I would leave this as an optional parameter, letting everyone decide by themselves how much smooth circle wants ...
  12. 'Minstep! = 1 / (2 * _PI * Radius) 'why so? For circle R = 250: 1 / (6.28 * 250) = 0.0006. This is very small step...
  13. Minstep! = 1 / _PI / (Radius / 10) ' for Circle R = 250: 1 / 3.14 / 25 = 0.01, it is enought...or not?
  14.  
  15. FOR s = 0 TO _PI / 2 STEP Minstep!
  16.     Px(i) = Radius * COS(s!)
  17.     Py(i) = Radius * SIN(s!)
  18.     i = i + 1
  19.     REDIM _PRESERVE Px(i) AS SINGLE
  20.     REDIM _PRESERVE Py(i) AS SINGLE
  22.  
  23.  
  24. FOR s = 0 TO UBOUND(Px)
  25.     LINE (Cx - Px(s), Cy - Py(s))-(Cx + Px(s), Cy + Py(s)), 127, BF
  27.  
  28. F! = TIMER(.001)
  29. LOCATE 1, 1
  30. PRINT F! - St!;
  34.  
  35.  
Title: Re: Is this fast enough as general circle fill?
Post by: Petr on June 25, 2018, 10:41:16 am
For some reason, I can not edit the previous post, so here is the Minstep! fixed so that it also works on small radius.

Code: QB64: [Select]
  1.  
  2.  
  3.  
  4. '0.105 original
  5. REDIM Px(0) AS SINGLE, Py(0) AS SINGLE, s AS SINGLE, st AS SINGLE, radius AS INTEGER, Cx AS INTEGER, Cy AS INTEGER
  6. Demo& = _NEWIMAGE(1366, 768, 256)
  7. SCREEN Demo&
  8. st! = TIMER(.001)
  9. radius = 555
  10. Cx = 250 'radius
  11. Cy = 400 'radius
  12.  
  13. ' Minstep: When someone rewrite it to function, I would leave this as an optional parameter, letting everyone decide by themselves how much smooth circle wants ...
  14. 'Minstep! = 1 / (2 * _PI * Radius) 'why so? For circle R = 250: 1 / (6.28 * 250) = 0.0006. This is very small step...
  15. Minstep! = 1 / (_PI / 2 * radius)
  16.  
  17. FOR s = 0 TO _PI / 2 STEP Minstep!
  18.     Px(i) = radius * COS(s!)
  19.     Py(i) = radius * SIN(s!)
  20.     i = i + 1
  21.     REDIM _PRESERVE Px(i) AS SINGLE
  22.     REDIM _PRESERVE Py(i) AS SINGLE
  24.  
  25.  
  26. FOR s = 0 TO UBOUND(Px)
  27.     LINE (Cx - Px(s), Cy - Py(s))-(Cx + Px(s), Cy + Py(s)), 127, BF
  29.  
  30. F! = TIMER(.001)
  31. LOCATE 1, 1
  32. PRINT F! - st!;
  36.  
  37.  
Title: Re: Is this fast enough as general circle fill?
Post by: Petr on June 25, 2018, 10:55:32 am
Quote from: bplus on June 25, 2018, 09:30:55 am
Slower than Steve's but this fills a regular polygon that approaches a circle as increase the number of sides. It fills the circle with an image and the image is based according to location of mouse (or where ever you want a circular part of image).

This is a circle fill method based on _MAPTRIANGLE, I think it is fast enough to impress!

Code: QB64: [Select]
  1. 'Poly Image Demo 2
  2. 'by bplus started 2018-06-22
  3.  
  4. CONST xmax = 800
  5. CONST ymax = 600
  6. SCREEN _NEWIMAGE(xmax, ymax, 32)
  7. _SCREENMOVE 100, 20
  8.  
  9. stars& = _LOADIMAGE("stars.png")
  10. stuff& = _NEWIMAGE(xmax, ymax, 32)
  11. _DEST stuff&
  12. FOR i = 1 TO 100
  13.     CIRCLE (RND * xmax, RND * ymax), RND * 100, _RGB32(RND * 255, RND * 255, RND * 255)
  17.     CLS
  18.     _SOURCE stuff&
  19.     _PUTIMAGE
  21.     polygonImage stars&, _MOUSEX, _MOUSEY, 250, 50
  22.     _DISPLAY
  23.     _LIMIT 30
  25.  
  26.  
  27. SUB polygonImage (ImageHandle&, xOrigin, yOrigin, radius, nVertex)
  28.     polyAngle = _PI(2) / nVertex
  29.     x1 = xOrigin + radius * COS(polyAngle)
  30.     y1 = yOrigin + radius * SIN(polyAngle)
  31.     FOR i = 2 TO nVertex + 1
  32.         x2 = xOrigin + radius * COS(i * polyAngle)
  33.         y2 = yOrigin + radius * SIN(i * polyAngle)
  34.         _MAPTRIANGLE (xOrigin, yOrigin)-(x1, y1)-(x2, y2), ImageHandle& TO(xOrigin, yOrigin)-(x1, y1)-(x2, y2), 0
  35.         x1 = x2: y1 = y2
  36.     NEXT
  38.  

Attached is code with Stars.png for testing with image file.


Hi Bplus, You can use hardware images for really fast output:

Code: QB64: [Select]
  1. 'Poly Image Demo 2
  2. 'by bplus started 2018-06-22
  3.  
  4. CONST xmax = 800
  5. CONST ymax = 600
  6. SCREEN _NEWIMAGE(xmax, ymax, 32)
  7. _SCREENMOVE 100, 20
  8.  
  9. star& = _LOADIMAGE("stars.png")
  10. stars& = _COPYIMAGE(star&, 33)
  12. stuff& = _NEWIMAGE(xmax, ymax, 32)
  13. _DEST stuff&
  14. FOR i = 1 TO 100
  15.     CIRCLE (RND * xmax, RND * ymax), RND * 100, _RGB32(RND * 255, RND * 255, RND * 255)
  19.     '    CLS not need for hardware images and in this case also not, _PUTIMAGE in this case rewrite screen.
  20.     _SOURCE stuff&
  21.     _PUTIMAGE
  23.     polygonImage stars&, _MOUSEX, _MOUSEY, 250, 50
  24.     _DISPLAY
  25.     _LIMIT 30
  27.  
  28.  
  29. SUB polygonImage (ImageHandle&, xOrigin, yOrigin, radius, nVertex) 'Where I just saw it.... :-D
  30.     polyAngle = _PI(2) / nVertex
  31.     x1 = xOrigin + radius * COS(polyAngle)
  32.     y1 = yOrigin + radius * SIN(polyAngle)
  33.     FOR i = 2 TO nVertex + 1
  34.         x2 = xOrigin + radius * COS(i * polyAngle)
  35.         y2 = yOrigin + radius * SIN(i * polyAngle)
  36.         _MAPTRIANGLE (xOrigin, yOrigin)-(x1, y1)-(x2, y2), ImageHandle& TO(xOrigin, yOrigin)-(x1, y1)-(x2, y2), 0
  37.         x1 = x2: y1 = y2
  38.     NEXT
  40.  
  41.  
Title: Re: Is this fast enough as general circle fill?
Post by: bplus on June 25, 2018, 11:16:13 am
Code: QB64: [Select]
  1. stars& = _COPYIMAGE(star&, 33)

Petr, Using this line is causing a line of distortion on y axis right down the 270 to 90 degree line from center??? for my system when I move the mouse around. Using the image as I had directly was better (for my system anyway).

Does anyone else see it? It's seems about 2-4 (maybe more) pixels wide.



PS Petr: Right! CLS was not needed, leftover from before drawing "stuff".
Title: Re: Is this fast enough as general circle fill?
Post by: Petr on June 25, 2018, 12:44:00 pm
Quote
Petr, Using this line is causing a line of distortion on y axis right down the 270 to 90 degree line from center??? for my system when I move the mouse around. Using the image as I had directly was better (for my system anyway).

Does anyone else see it? It's seems about 2-4 (maybe more) pixels wide.

Yes, right under the mouse. It is interesting. It is best see in bright places. And it does with a hardware image only. So I have it not seen this yet.
Title: Re: Is this fast enough as general circle fill?
Post by: SkyCharger001 on June 25, 2018, 02:55:44 pm
about the LINE BF,
Code: QB64: [Select]
  1. LINE(cx%-px!,cy%-py!)-(cx%+px!,cy%+py!),63,bf
instead of
Code: QB64: [Select]
  1. LINE(cx%-px!,cy%-py!)-(cx%+px!,cy%-py!),63,bf
should save you half of the LINE calls
Title: Re: Is this fast enough as general circle fill?
Post by: bplus on June 25, 2018, 04:28:03 pm
Quote from: SkyCharger001 on June 25, 2018, 02:55:44 pm
about the LINE BF,
Code: QB64: [Select]
  1. LINE(cx%-px!,cy%-py!)-(cx%+px!,cy%+py!),63,bf
instead of
Code: QB64: [Select]
  1. LINE(cx%-px!,cy%-py!)-(cx%+px!,cy%-py!),63,bf
should save you half of the LINE calls

Yes, but if you are using alpha coloring, the overlapping boxes might NOT give you an even shade.
Title: Re: Is this fast enough as general circle fill?
Post by: _vince on June 25, 2018, 06:45:58 pm
These claims I strongly refuse to believe that anything's faster than that by Steve.
Title: Re: Is this fast enough as general circle fill?
Post by: SkyCharger001 on June 26, 2018, 04:44:11 am
Quote from: bplus on June 25, 2018, 04:28:03 pm
Quote from: SkyCharger001 on June 25, 2018, 02:55:44 pm
about the LINE BF,
Code: QB64: [Select]
  1. LINE(cx%-px!,cy%-py!)-(cx%+px!,cy%+py!),63,bf
instead of
Code: QB64: [Select]
  1. LINE(cx%-px!,cy%-py!)-(cx%+px!,cy%-py!),63,bf
should save you half of the LINE calls

Yes, but if you are using alpha coloring, the overlapping boxes might NOT give you an even shade.
Ah, didn't think about that.
one solution (that might ruin the speed-gain) would be to draw the filled circle on a temporary indexed image with color 0 set to RGBA(0,0,0,0) for masking and color 1 set to whatever RGBA color you want, and _PUTIMAGEing it onto the target image.
Title: Re: Is this fast enough as general circle fill?
Post by: zigzag on June 26, 2018, 07:01:16 am
Hasn't anyone considered using this method?

Code: QB64: [Select]
  1. Radius% = 1000
  2. Cx% = Radius%
  3. Cy% = Radius%
  4.  
  5. FOR X% = 0 TO Radius%
  6.   Y% = SQR(Radius% * Radius% - X% * X%)
  7.   LINE (Cx% + X%, Cy% - Y%)-(Cx% + X%, Cy% + Y%)
  8.   LINE (Cx% - X%, Cy% - Y%)-(Cx% - X%, Cy% + Y%)
Title: Re: Is this fast enough as general circle fill?
Post by: Ashish on June 26, 2018, 09:06:53 am
+Zigzag
I guess you are using circle equation (x^2+y^2=r^2) inside the loop and it works. Good to see this code as I've only use these equation on paper graphs.
Title: Re: Is this fast enough as general circle fill?
Post by: bplus on June 26, 2018, 09:09:36 am
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

Title: Re: Is this fast enough as general circle fill?
Post by: SMcNeill on June 26, 2018, 03:34:18 pm
Sometimes, computers do things that are completely counter-intuitive to us, and we find ourselves having to step back as programmers and simply say, "WOW!!"   Here's a perfect example of that:

Code: QB64: [Select]
  1. DIM SHARED Radius AS INTEGER: Radius = 1000
  2. DIM SHARED CP(Radius, Radius) AS INTEGER 'CirclePoints
  3.  
  4.  
  5. SCREEN _NEWIMAGE(800, 600, 256)
  7.  
  8.  
  9. PreCalcCircles
  10.  
  11. x = _WIDTH / 2
  12. y = _HEIGHT / 2
  13. k = 15
  14. TestLoopLimit = 10000
  15.  
  16. t1 = TIMER(0.001)
  17. FOR i = 1 TO TestLoopLimit
  18.     CircleFillFast x, y, 300, k
  20.  
  21. t2 = TIMER(0.001)
  22. FOR i = 1 TO TestLoopLimit
  23.     CircleFill x, y, 300, k
  25. t3 = TIMER(0.001)
  26.  
  27. PRINT USING "##.#### seconds with CircleFillFast"; t2 - t1
  28. PRINT USING "##.#### seconds with CircleFill"; t3 - t2
  29.  
  30.  
  31. SUB PreCalcCircles
  32.     FOR i = 0 TO Radius 'each circle, for all radius sizes from 1 to limit
  33.         FOR j = 0 TO i 'get the points for each line of those circles
  34.             CP(i, j) = SQR(i * i - j * j)
  35.         NEXT
  36.     NEXT
  38.  
  39.  
  40. SUB CircleFillFast (x, y, Radius, k)
  41.     FOR j = 0 TO Radius 'get the points for each line of those circles
  42.         LINE (x - CP(Radius, j), y + j)-(x + CP(Radius, j), y + j), k, BF
  43.         LINE (x - CP(Radius, j), y - j)-(x + CP(Radius, j), y - j), k, BF
  44.     NEXT
  46.  
  47. SUB CircleFill (CX AS LONG, CY AS LONG, R AS LONG, C AS LONG)
  48.     DIM Radius AS LONG, RadiusError AS LONG
  49.     DIM X AS LONG, Y AS LONG
  50.  
  51.     Radius = ABS(R)
  52.     RadiusError = -Radius
  53.     X = Radius
  54.     Y = 0
  55.  
  56.     IF Radius = 0 THEN PSET (CX, CY), C: EXIT SUB
  57.  
  58.     ' Draw the middle span here so we don't draw it twice in the main loop,
  59.     ' which would be a problem with blending turned on.
  60.     LINE (CX - X, CY)-(CX + X, CY), C, BF
  61.  
  62.     WHILE X > Y
  63.         RadiusError = RadiusError + Y * 2 + 1
  64.         IF RadiusError >= 0 THEN
  65.             IF X <> Y + 1 THEN
  66.                 LINE (CX - Y, CY - X)-(CX + Y, CY - X), C, BF
  67.                 LINE (CX - Y, CY + X)-(CX + Y, CY + X), C, BF
  68.             END IF
  69.             X = X - 1
  70.             RadiusError = RadiusError - X * 2
  71.         END IF
  72.         Y = Y + 1
  73.         LINE (CX - X, CY - Y)-(CX + X, CY - Y), C, BF
  74.         LINE (CX - X, CY + Y)-(CX + X, CY + Y), C, BF
  75.     WEND
  77.  

Here we look at two different circle fill routines -- one, which I'd assume to be faster, which precalculates the offset needed to find the endpoints for each line which composes a circle, and another, which is the same old CircleFill program which I've shared countless times over the years with people on various QB64 forums.

When all is said and done though, CircleFill is STILL even faster than CircleFillFast, which pregenerates those end-points for us!

I've got to admit, I find these results rather shocking!  (Thus the name I chose when naming the CircleFill-NotSoFastAfterall routine.)  Apparently, in this case, the integer math used in CircleFill is faster than the time it takes for QB64 to look up those internal values from a preset array.

Who woulda thunk it?!!

Anywho, I thought I'd share, just so others could look over the two routines and compare.  Maybe there's a way to improve the CircleFillFast so that it'd be faster than CircleFill, but if it is, I'm not seeing it at the moment.

It looks like CircleFill is still the fastest routine to use to rapidly fill a circle for us.  :D
Title: Re: Is this fast enough as general circle fill?
Post by: SMcNeill on June 26, 2018, 03:39:20 pm
Code: QB64: [Select]
  1. DIM SHARED Radius AS INTEGER: Radius = 1000
  2. DIM SHARED CP(Radius, Radius) AS INTEGER 'CirclePoints
  3.  
  4.  
  5. SCREEN _NEWIMAGE(800, 600, 256)
  7.  
  8.  
  9. PreCalcCircles
  10.  
  11. x = _WIDTH / 2
  12. y = _HEIGHT / 2
  13. k = 15
  14. TestLoopLimit = 10000
  15.  
  16. t1 = TIMER(0.001)
  17. FOR i = 1 TO TestLoopLimit
  18.     CircleFillFast x, y, 300, k
  21.  
  22. t2 = TIMER(0.001)
  23. FOR i = 1 TO TestLoopLimit
  24.     CircleFill x, y, 300, k
  26.  
  27. t3 = TIMER(0.001)
  28.  
  29. PRINT USING "##.#### seconds with CircleFillFast"; t2 - t1
  30. PRINT USING "##.#### seconds with CircleFill"; t3 - t2
  31.  
  32.  
  33. SUB PreCalcCircles
  34.     FOR i = 0 TO Radius 'each circle, for all radius sizes from 1 to limit
  35.         FOR j = 0 TO i 'get the points for each line of those circles
  36.             CP(i, j) = SQR(i * i - j * j)
  37.         NEXT
  38.     NEXT
  40.  
  41.  
  42. SUB CircleFillFast (x, y, r, k)
  43.     DO UNTIL j > r
  44.         t = CP(r, j)
  45.         LINE (x - t, y + j)-(x + t, y + j), k, BF
  46.         LINE (x - t, y - j)-(x + t, y - j), k, BF
  47.         j = j + 1
  48.     LOOP
  50.  
  51. SUB CircleFill (CX AS LONG, CY AS LONG, R AS LONG, C AS LONG)
  52.     DIM Radius AS LONG, RadiusError AS LONG
  53.     DIM X AS LONG, Y AS LONG
  54.  
  55.     Radius = ABS(R)
  56.     RadiusError = -Radius
  57.     X = Radius
  58.     Y = 0
  59.  
  60.     IF Radius = 0 THEN PSET (CX, CY), C: EXIT SUB
  61.  
  62.     ' Draw the middle span here so we don't draw it twice in the main loop,
  63.     ' which would be a problem with blending turned on.
  64.     LINE (CX - X, CY)-(CX + X, CY), C, BF
  65.  
  66.     WHILE X > Y
  67.         RadiusError = RadiusError + Y * 2 + 1
  68.         IF RadiusError >= 0 THEN
  69.             IF X <> Y + 1 THEN
  70.                 LINE (CX - Y, CY - X)-(CX + Y, CY - X), C, BF
  71.                 LINE (CX - Y, CY + X)-(CX + Y, CY + X), C, BF
  72.             END IF
  73.             X = X - 1
  74.             RadiusError = RadiusError - X * 2
  75.         END IF
  76.         Y = Y + 1
  77.         LINE (CX - X, CY - Y)-(CX + X, CY - Y), C, BF
  78.         LINE (CX - X, CY + Y)-(CX + X, CY + Y), C, BF
  79.     WEND
  80.  
  82.  

And this version is quite a bit faster than the previous one -- but still slower than the original CircleFill routine.  The only real change here for performance?  Using         t = CP(r, j)     and using t in our circle drawing routines instead of CP(r,j).  Referencing arrays are slower than referencing single variables, and we see the change in performance here, noticeably.

Title: Re: Is this fast enough as general circle fill?
Post by: SMcNeill on June 26, 2018, 03:45:50 pm
*Remove the SLEEP statement in the above routine, which I was using to test things, or else you'll just sit there and not do much of anything while waiting for the program to complete.  I'd placed it there while testing changes and can't go back and edit the above post to remove it.  :P
Title: Re: Is this fast enough as general circle fill?
Post by: Petr on June 26, 2018, 04:05:11 pm
Hi Steve. NUMERIC TYPES!

Try it now:

Code: QB64: [Select]
  1. DIM SHARED Radius AS INTEGER: Radius = 1000
  2. DIM SHARED CP(Radius, Radius) AS INTEGER 'CirclePoints
  3.  
  4.  
  5. SCREEN _NEWIMAGE(800, 600, 256)
  7.  
  8.  
  9. PreCalcCircles
  10.  
  11. x = _WIDTH / 2
  12. y = _HEIGHT / 2
  13. k = 15
  14. TestLoopLimit = 10000
  15.  
  16. t1 = TIMER(0.001)
  17. FOR i = 1 TO TestLoopLimit
  18.     CircleFillFast x#, y#, 300, k#
  20.  
  21.  
  22. t2 = TIMER(0.001)
  23. FOR i = 1 TO TestLoopLimit
  24.     CircleFill x, y, 300, k
  26.  
  27. t3 = TIMER(0.001)
  28.  
  29. PRINT USING "##.#### seconds with CircleFillFast"; t2 - t1
  30. PRINT USING "##.#### seconds with CircleFill"; t3 - t2
  31.  
  32.  
  33. SUB PreCalcCircles
  34.     DIM i AS INTEGER, j AS INTEGER
  35.     FOR i = 0 TO Radius 'each circle, for all radius sizes from 1 to limit
  36.         FOR j = 0 TO i 'get the points for each line of those circles
  37.             CP(i, j) = SQR(i * i - j * j)
  38.         NEXT
  39.     NEXT
  41.  
  42.  
  43. SUB CircleFillFast (x AS INTEGER, y AS INTEGER, r AS INTEGER, k AS INTEGER)
  45.     DO UNTIL j > r
  46.         t = CP(r, j)
  47.         LINE (x - t, y + j)-(x + t, y + j), k, BF
  48.         LINE (x - t, y - j)-(x + t, y - j), k, BF
  49.         j = j + 1
  50.     LOOP
  52.  
  53. SUB CircleFill (CX AS LONG, CY AS LONG, R AS LONG, C AS LONG)
  54.     DIM Radius AS LONG, RadiusError AS LONG
  55.     DIM X AS LONG, Y AS LONG
  56.  
  57.     Radius = ABS(R)
  58.     RadiusError = -Radius
  59.     X = Radius
  60.     Y = 0
  61.  
  62.     IF Radius = 0 THEN PSET (CX, CY), C: EXIT SUB
  63.  
  64.     ' Draw the middle span here so we don't draw it twice in the main loop,
  65.     ' which would be a problem with blending turned on.
  66.     LINE (CX - X, CY)-(CX + X, CY), C, BF
  67.  
  68.     WHILE X > Y
  69.         RadiusError = RadiusError + Y * 2 + 1
  70.         IF RadiusError >= 0 THEN
  71.             IF X <> Y + 1 THEN
  72.                 LINE (CX - Y, CY - X)-(CX + Y, CY - X), C, BF
  73.                 LINE (CX - Y, CY + X)-(CX + Y, CY + X), C, BF
  74.             END IF
  75.             X = X - 1
  76.             RadiusError = RadiusError - X * 2
  77.         END IF
  78.         Y = Y + 1
  79.         LINE (CX - X, CY - Y)-(CX + X, CY - Y), C, BF
  80.         LINE (CX - X, CY + Y)-(CX + X, CY + Y), C, BF
  81.     WEND
  82.  
  84.  
  85.  
Title: Re: Is this fast enough as general circle fill?
Post by: SMcNeill on June 26, 2018, 04:12:18 pm
Just changing the types for     CircleFillFast x#, y#, 300, k# , breaks the program.  There is no x# or y# in use anywhere, so you're placing the circle at 0,0 with color 0....  75% of it is drawn off the screen, and that's going to make it appear to run faster than it actually is.

You can't compare speeds of drawing 1/4 of a circle, against speeds of drawing a whole circle.  ;)

You'd need to change all instances of X/Y to become single precision values, and then you end up with similar speed results as before.

Code: QB64: [Select]
  1. DIM SHARED Radius AS INTEGER: Radius = 1000
  2. DIM SHARED CP(Radius, Radius) AS INTEGER 'CirclePoints
  3.  
  4.  
  5. SCREEN _NEWIMAGE(800, 600, 256)
  7.  
  8.  
  9. PreCalcCircles
  10.  
  11. x# = _WIDTH / 2
  12. y# = _HEIGHT / 2
  13. k# = 15
  14. TestLoopLimit = 10000
  15.  
  16. t1 = TIMER(0.001)
  17. FOR i = 1 TO TestLoopLimit
  18.     CircleFillFast x#, y#, 300, k#
  20.  
  21.  
  22. t2 = TIMER(0.001)
  23. FOR i = 1 TO TestLoopLimit
  24.     CircleFill x#, y#, 300, k#
  26.  
  27. t3 = TIMER(0.001)
  28.  
  29. PRINT USING "##.#### seconds with CircleFillFast"; t2 - t1
  30. PRINT USING "##.#### seconds with CircleFill"; t3 - t2
  31.  
  32.  
  33. SUB PreCalcCircles
  34.     DIM i AS INTEGER, j AS INTEGER
  35.     FOR i = 0 TO Radius 'each circle, for all radius sizes from 1 to limit
  36.         FOR j = 0 TO i 'get the points for each line of those circles
  37.             CP(i, j) = SQR(i * i - j * j)
  38.         NEXT
  39.     NEXT
  41.  
  42.  
  43. SUB CircleFillFast (x AS INTEGER, y AS INTEGER, r AS INTEGER, k AS INTEGER)
  45.     DO UNTIL j > r
  46.         t = CP(r, j)
  47.         LINE (x - t, y + j)-(x + t, y + j), k, BF
  48.         LINE (x - t, y - j)-(x + t, y - j), k, BF
  49.         j = j + 1
  50.     LOOP
  52.  
  53. SUB CircleFill (CX AS LONG, CY AS LONG, R AS LONG, C AS LONG)
  54.     DIM Radius AS LONG, RadiusError AS LONG
  55.     DIM X AS LONG, Y AS LONG
  56.  
  57.     Radius = ABS(R)
  58.     RadiusError = -Radius
  59.     X = Radius
  60.     Y = 0
  61.  
  62.     IF Radius = 0 THEN PSET (CX, CY), C: EXIT SUB
  63.  
  64.     ' Draw the middle span here so we don't draw it twice in the main loop,
  65.     ' which would be a problem with blending turned on.
  66.     LINE (CX - X, CY)-(CX + X, CY), C, BF
  67.  
  68.     WHILE X > Y
  69.         RadiusError = RadiusError + Y * 2 + 1
  70.         IF RadiusError >= 0 THEN
  71.             IF X <> Y + 1 THEN
  72.                 LINE (CX - Y, CY - X)-(CX + Y, CY - X), C, BF
  73.                 LINE (CX - Y, CY + X)-(CX + Y, CY + X), C, BF
  74.             END IF
  75.             X = X - 1
  76.             RadiusError = RadiusError - X * 2
  77.         END IF
  78.         Y = Y + 1
  79.         LINE (CX - X, CY - Y)-(CX + X, CY - Y), C, BF
  80.         LINE (CX - X, CY + Y)-(CX + X, CY + Y), C, BF
  81.     WEND
  82.  
Title: Re: Is this fast enough as general circle fill?
Post by: SMcNeill on June 26, 2018, 04:26:52 pm
The best speed I can tend to generate with tweaking things is this (so far): 

Code: QB64: [Select]
  2. DIM SHARED Radius AS INTEGER: Radius = 1000
  3. DIM SHARED CP(Radius, Radius) AS INTEGER 'CirclePoints
  4.  
  5.  
  6. SCREEN _NEWIMAGE(800, 600, 256)
  8.  
  9.  
  10. PreCalcCircles
  11.  
  12. x = _WIDTH / 2
  13. y = _HEIGHT / 2
  14. k = 15
  15. TestLoopLimit = 10000
  16.  
  17. t1# = TIMER(0.001)
  18. FOR i = 1 TO TestLoopLimit
  19.     CircleFillFast x, y, 300, k
  21.  
  22.  
  23. t2# = TIMER(0.001)
  24. FOR i = 1 TO TestLoopLimit
  25.     CircleFill x, y, 300, k
  27.  
  28. t3# = TIMER(0.001)
  29.  
  30. PRINT USING "##.#### seconds with CircleFillFast"; t2# - t1#
  31. PRINT USING "##.#### seconds with CircleFill"; t3# - t2#
  32.  
  33.  
  34. SUB PreCalcCircles
  35.     FOR i = 0 TO Radius 'each circle, for all radius sizes from 1 to limit
  36.         FOR j = 0 TO i 'get the points for each line of those circles
  37.             CP(i, j) = SQR(i * i - j * j)
  38.         NEXT
  39.     NEXT
  41.  
  42.  
  43. SUB CircleFillFast (x, y, r, k)
  44.     dc = _DEFAULTCOLOR
  45.     COLOR k
  46.     DO UNTIL j > r
  47.         t = CP(r, j)
  48.         LINE (x - t, y + j)-STEP(t + t, 0), , BF
  49.         LINE (x - t, y - j)-STEP(t + t, 0), , BF
  50.         j = j + 1
  51.     LOOP
  52.     COLOR dc
  54.  
  55. SUB CircleFill (CX AS LONG, CY AS LONG, R AS LONG, C AS LONG)
  56.     DIM Radius AS LONG, RadiusError AS LONG
  57.     DIM X AS LONG, Y AS LONG
  58.  
  59.     Radius = ABS(R)
  60.     RadiusError = -Radius
  61.     X = Radius
  62.     Y = 0
  63.  
  64.     IF Radius = 0 THEN PSET (CX, CY), C: EXIT SUB
  65.     ' Draw the middle span here so we don't draw it twice in the main loop,
  66.     ' which would be a problem with blending turned on.
  67.     LINE (CX - X, CY)-(CX + X, CY), C, BF
  68.  
  69.     WHILE X > Y
  70.         RadiusError = RadiusError + Y * 2 + 1
  71.         IF RadiusError >= 0 THEN
  72.             IF X <> Y + 1 THEN
  73.                 LINE (CX - Y, CY - X)-(CX + Y, CY - X), C, BF
  74.                 LINE (CX - Y, CY + X)-(CX + Y, CY + X), C, BF
  75.             END IF
  76.             X = X - 1
  77.             RadiusError = RadiusError - X * 2
  78.         END IF
  79.         Y = Y + 1
  80.         LINE (CX - X, CY - Y)-(CX + X, CY - Y), C, BF
  81.         LINE (CX - X, CY + Y)-(CX + X, CY + Y), C, BF
  82.     WEND
  83.  

Speeds on my machine are 0.55 seconds versus 0.50 seconds, so both of them are plenty fast for most instances.  (After all, this is drawing a filled circle the whole size of my screen 10,000 times.)

Maybe if someone wanted/needed the endpoints for collision detection or some other use, then the precalculated values in CircleFillFast would be useful.  As it is though, I suppose I'm still going to have to call CircleFill the quickest routine I've personally seen so far. 
Title: Re: Is this fast enough as general circle fill?
Post by: Petr on June 26, 2018, 04:47:47 pm
You're right. I did not realize that. Whatever I'm trying to do, it's not better.
Title: Re: Is this fast enough as general circle fill?
Post by: Petr on June 26, 2018, 04:54:19 pm
Steve, can you please look to this source, why it is so slow? https://www.qb64.org/forum/index.php?topic=287.msg1756#msg1756
Title: Re: Is this fast enough as general circle fill?
Post by: SMcNeill on June 26, 2018, 05:06:03 pm
Quote from: Petr on June 26, 2018, 04:54:19 pm
Steve, can you please look to this source, why it is so slow? https://www.qb64.org/forum/index.php?topic=287.msg1756#msg1756

Try it with $CHECKING:OFF.

I'll give it a better looking over later tonight, but the wife has me heading out for supper here in a few moments.  $CHECKING might make a noticeable boost in performance for you though. 
Title: Re: Is this fast enough as general circle fill?
Post by: Petr on June 26, 2018, 05:09:53 pm
I'll try it. Thank you. I'm going to sleep, it's almost midnight here. I'll see it tomorrow.
Title: Re: Is this fast enough as general circle fill?
Post by: SMcNeill on June 26, 2018, 05:16:02 pm
Advice 2:

Remove:

FUNCTION IN& (x AS INTEGER, y AS INTEGER)
    IN& = (_WIDTH * y + x) * 4
END FUNCTION


Function calls are slow.  Do the math directly, and don't call on _WIDTH.

Early in the routine, use w = _WIDTH, then:

  _MEMPUT m, m.OFFSET + (w * y1 + x) * 4, clr&
Title: Re: Is this fast enough as general circle fill?
Post by: SMcNeill on June 26, 2018, 06:24:58 pm
Quote from: Petr on June 21, 2018, 02:29:57 pm
Fellippe, when you started with comparing time, which is very beneficial to all, I give this code here. I made the analogy of the LINE command via MEMPUT. Even though I expected great speed, but  the result is to cry. It's a terrible lemur lazy. Could you tell me what I was doing here bad again? Thank you.

Code: QB64: [Select]
  1.  
  3. J& = _NEWIMAGE(800, 600, 32)
  4. m = _MEMIMAGE(J&)
  6.  
  7. T = TIMER
  8.  
  9. FOR test = 1 TO 1000
  10.     vinceCircleFill 400, 300, 200, _RGB32(0, 255, 0)
  11. NEXT test
  12.  
  14.  
  15. SUB vinceCircleFill (x AS LONG, y AS LONG, R AS LONG, C AS _UNSIGNED LONG)
  16.     x0 = R
  17.     y0 = 0
  18.     e = 0
  19.     DO WHILE y0 < x0
  20.         IF e <= 0 THEN
  21.             y0 = y0 + 1
  22.             MEM_LINE x - x0, y + y0, x + x0, y + y0, C
  23.             MEM_LINE x - x0, y - y0, x + x0, y - y0, C
  24.             e = e + 2 * y0
  25.         ELSE
  26.             MEM_LINE x - y0, y - x0, x + y0, y - x0, C
  27.             MEM_LINE x - y0, y + x0, x + y0, y + x0, C
  28.             x0 = x0 - 1
  29.             e = e - 2 * x0
  30.         END IF
  31.     LOOP
  32.     MEM_LINE x - R, y, x + R, y, C
  34.  
  35. SUB MEM_LINE (x1 AS INTEGER, y1 AS INTEGER, x2 AS INTEGER, y2 AS INTEGER, clr AS LONG)
  36.     DEFLNG A-Z
  37.     dX = x2 - x1
  38.     dY = y2 - y1
  39.     IF dX > dY OR dX = dY THEN
  40.         x = x1: y = y1
  41.         DO WHILE x <> x2
  42.             x = x + 1
  43.             y = y + (dY / dX)
  44.             _MEMPUT m, m.OFFSET + IN&(x, y), clr&
  45.         LOOP
  46.     END IF
  47.     IF dY > dX THEN
  48.         x = x1: y = y1
  49.         DO WHILE y <> y2
  50.             x = x + (dX / dY)
  51.             y = y + 1
  52.             _MEMPUT m, m.OFFSET + IN&(x, y), clr&
  53.         LOOP
  54.     END IF
  55.     IF x1 = x2 THEN
  56.         FOR d = y1 TO y2
  57.             _MEMPUT m, m.OFFSET + IN&(x1, d), clr&
  58.         NEXT d
  59.     END IF
  60.     IF y1 = y2 THEN
  61.         FOR d = x1 TO x2
  62.             _MEMPUT m, m.OFFSET + IN&(d, y1), clr&
  63.         NEXT d
  64.     END IF
  66.  
  68.     IN& = (_WIDTH * y + x) * 4
  70.  
  71.  

A few tweaks to the above code, and you'll see a slight improvement on run time:
Code: QB64: [Select]
  2. J& = _NEWIMAGE(800, 600, 32)
  3. m = _MEMIMAGE(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.  
  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
  33.  
  34. SUB MEM_LINE (x1 AS INTEGER, y1 AS INTEGER, x2 AS INTEGER, y2 AS INTEGER, clr AS LONG)
  35.     DEFLNG A-Z
  37.     dX = x2 - x1
  38.     dY = y2 - y1
  39.     w = _WIDTH
  40.     x = x1: y = y1
  41.     IF dX >= dY THEN
  42.         DO WHILE x <> x2
  43.             x = x + 1
  44.             y = y + (dY / dX)
  45.             _MEMPUT m, m.OFFSET + (w * y + x) * 4, clr
  46.         LOOP
  47.     ELSE
  48.         DO WHILE y <> y2
  49.             x = x + (dX / dY)
  50.             y = y + 1
  51.             _MEMPUT m, m.OFFSET + (w * y + x) * 4, clr
  52.         LOOP
  53.     END IF
  54.     IF x1 = x2 THEN
  55.         d = y1
  56.         DO UNTIL d > y2
  57.             _MEMPUT m, m.OFFSET + (w * d + x1) * 4, clr
  58.             d = d + 1
  59.         LOOP
  60.     END IF
  61.     IF y1 = y2 THEN
  62.         d = x1
  63.         DO UNTIL d > x2
  64.             _MEMPUT m, m.OFFSET + (w * y1 + d) * 4, clr
  65.             d = d + 1
  66.         LOOP
  67.     END IF

As it was, it took 10.3 seconds to draw 1000 times on my machine.  (I changed the limit from 10,000 to 1,000 so I wouldn't have to wait all night for results.)  The modified version does the same thing in 3.4 seconds.

$CHECKING makes a small change, with 4.3 seconds vs 3.4 seconds for run time, but the greatest change comes from dropping the multiple FUNCTION calls.  They're SLOOOOOOW in relation to other things in QB64 and should generally be avoided as much as possible in situations where speed might be a critical consideration for your program.  Changing the FOR-NEXT loops to DO-LOOP saves a little time as well, though it's mainly one of those things where you'd worry about altering and using AFTER you're certain the code runs right the first time around for you. 

Still, I don't think it'll compare to the times of LINE (x1,y1)-(x2,y2), kolor, BF, since LINE BF has been extensively optimized at the C-level by Galleon, but it's still a nice improvement overall for us.  :)
Title: Re: Is this fast enough as general circle fill?
Post by: Petr on June 27, 2018, 10:40:52 am
Steve, thank you for your pretty detailed analysis of the problem. Never thought me to try the reaction time of the functions. It's a shame that such a useful thing as the functions have such a reaction time.
Title: Re: Is this fast enough as general circle fill?
Post by: SMcNeill on June 27, 2018, 11:36:50 am
Looking at it fresh this morning, I see another way you could speed it up even more, with the use of some creative math.

        DO WHILE y <> y2
            x = x + (dX / dY)
            y = y + 1
            _MEMPUT m, m.OFFSET + (w * y + x) * 4, clr
        LOOP

If you make y1 and y2 in relation to w to begin with, you could reduce a few math operations in the DO LOOPS...

Y1 = Y1 * w: Y2 = Y2 * w     <---- first line at the start of the SUB

Y = Y + w   <----  in the DO LOOP
_MEMPUT m, m.offset + (y + x) *4, clr    <----  internally in the routine now, Y increments by _WIDTH amount naturally, and we remove a multiplication step of operations.


*************

Since X and Y are interger values, you can probably change the math to be a little more efficient elsewhere as well:

Instead of X = X + (DX / DY), make it X = X + (DX \ DY)

Integer division (\) is considerably faster than real division (/), so if you can use it and need a program to optimize speed, do so. 

****************

Lots of little tricks and tweaks which can be used to optimize speed.  The main thing you have to be *really* careful of is not to obfuscate the code beyond the point of being able to understand it in the future.  Just because you *can* make it faster, it doesn't mean you always *should* -- especially if you alter it so much you can't figure it out and debug it or alter it, at a later date.

Fast is good, but understanding is better.  ;D
Title: Re: Is this fast enough as general circle fill?
Post by: SMcNeill on June 27, 2018, 11:45:28 am
In fact, you may be able to remove that * 4 operation completely, if you multiple the X/Y/W values by 4 at the beginning of the program as well.

Then it'd just be a case of _MEMPUT m, m.offset + y + x, clr, which would save several math operations for each DO..LOOP.
Title: Re: Is this fast enough as general circle fill?
Post by: Petr 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!
Title: Re: Is this fast enough as general circle fill?
Post by: SkyCharger001 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)
Title: Re: Is this fast enough as general circle fill?
Post by: _vince on June 27, 2018, 06:39:21 pm
Quote from: SkyCharger001 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)

Any line can be drawn without any floating point math using the this algorithm:
https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm (https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm)
Title: Re: Is this fast enough as general circle fill?
Post by: SMcNeill 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: QB64: [Select]
  2. J& = _NEWIMAGE(800, 600, 32)
  3. m = _MEMIMAGE(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.  
  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
  33.  
  34. SUB MEM_LINE (x1t AS INTEGER, y1t AS INTEGER, x2t AS INTEGER, y2t AS INTEGER, clr AS LONG)
  35.     DEFLNG A-Z
  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
  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.  ;)
Title: Re: Is this fast enough as general circle fill?
Post by: _vince 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. ;)
Title: Re: Is this fast enough as general circle fill?
Post by: SMcNeill on June 27, 2018, 08:30:32 pm
Quote from: v 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. ;)

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. 
Title: Re: Is this fast enough as general circle fill?
Post by: codeguy 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.
Title: Re: Is this fast enough as general circle fill?
Post by: codeguy 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.
Title: Re: Is this fast enough as general circle fill?
Post by: bplus on June 28, 2018, 07:15:09 pm
Quote from: bplus on June 26, 2018, 09:09:36 am
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)
Title: Re: Is this fast enough as general circle fill?
Post by: bplus 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:
Title: Re: Is this fast enough as general circle fill?
Post by: bplus 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.
Title: Re: Is this fast enough as general circle fill?
Post by: Petr 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.
Title: Re: Is this fast enough as general circle fill?
Post by: bplus on June 30, 2018, 08:29:35 am
Thanks Petr, I think I got it now, the use of a hardware image that is.
Title: Re: Is this fast enough as general circle fill?
Post by: _vince 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
Title: Re: Is this fast enough as general circle fill?
Post by: bplus 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: 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
  13.     ellipse 400, 300, lastr, 290
  14.     lastr = .5 * (350 - lastr) + lastr + 10
  15.     IF 350 - lastr < 10 THEN EXIT DO
  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
  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
  45.  
  46.  

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