Is this fast enough as general circle fill?

[codeguy]

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. Next
13. F!=timer(.001)
14. Locate 1,1
15. Print f!-st!;
16. _delay 10
17. Screen 0
18. _freeimage demo&
19.  

[codeguy]

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

[johnno56]

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

[codeguy]

Haven't compared it to steve's circle fill but I don't think even that would beat this.

[codeguy]

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. Next
13. F!=timer(.001)
14. Locate 1,1
15. Print f!-st!;
16. _delay 10
17. Screen 0
18. _freeimage demo&
19.  

Corrected. Radians, not degrees.

[SMcNeill]

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]

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]

Using bf, r=1000, 0ms. Not kidding. Over 16 runs each, see picture.

[codeguy]

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]

So, in future reference, *always* use BF with LINE when possible.  ;)

[johnno56]

Wow. SO much faster. many times the 1000 radius was instantaneous. I did't both testing the smaller sizes. Cool.  :D

[SMcNeill]

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

[codeguy]

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. End if
14. Next
15.  

[codeguy]

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]

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