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

codeguy

Is this fast enough as general circle fill?
« 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
12. F!=TIMER(.001)
13. LOCATE 1,1
14. PRINT f!-st!;
15.

codeguy

Re: Is this fast enough as general circle fill?
« Reply #1 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
« Last Edit: June 25, 2018, 12:37:19 AM by codeguy »

johnno56

• Live long and prosper.
Re: Is this fast enough as general circle fill?
« Reply #2 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
Logic is the beginning of wisdom.

codeguy

Re: Is this fast enough as general circle fill?
« Reply #3 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.

codeguy

Re: Is this fast enough as general circle fill?
« Reply #4 on: June 25, 2018, 04:43:46 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
12. F!=TIMER(.001)
13. LOCATE 1,1
14. PRINT f!-st!;
15.
Corrected. Radians, not degrees.

SMcNeill

• QB64 Developer
Re: Is this fast enough as general circle fill?
« Reply #5 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.

codeguy

Re: Is this fast enough as general circle fill?
« Reply #6 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.

codeguy

Re: Is this fast enough as general circle fill?
« Reply #7 on: June 25, 2018, 05:07:22 AM »
Using bf, r=1000, 0ms. Not kidding. Over 16 runs each, see picture.

codeguy

Re: Is this fast enough as general circle fill?
« Reply #8 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.

SMcNeill

• QB64 Developer
Re: Is this fast enough as general circle fill?
« Reply #9 on: June 25, 2018, 05:20:05 AM »
So, in future reference, *always* use BF with LINE when possible.  ;)

johnno56

• Live long and prosper.
Re: Is this fast enough as general circle fill?
« Reply #10 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
Logic is the beginning of wisdom.

SMcNeill

• QB64 Developer
Re: Is this fast enough as general circle fill?
« Reply #11 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.).
« Last Edit: June 25, 2018, 05:45:18 AM by SMcNeill »

codeguy

Re: Is this fast enough as general circle fill?
« Reply #12 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!
13.

codeguy

Re: Is this fast enough as general circle fill?
« Reply #13 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.

SMcNeill

• QB64 Developer
Re: Is this fast enough as general circle fill?
« Reply #14 on: June 25, 2018, 09:19:03 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