Seeking best ellipse fill function. (For everyone's sake.)

[bplus]

Your attention to detail is indispensible plus! I wonder it the algorithm can be torn apart to find out why that happens... The thing seems to be *so* optimized that it became fragile. As soon as I get near a PC I will join your efforts...

Probably I am starting to become PIA.

I am next going to submit CircleFill to same test.

[Pete]

Don't give up. I don't know a single person who gets a program to run correctly from the first time out of the gate, unless it's that Hello World guru.

I don't see an obvious pattern in the results you posted, which means something in the algorithm is crunching numbers with probably some decimal off in the wrong direction.

BTW- you probably meant PITA, instead of PIA, you PITA!

Pete :D

[bplus]

Well hurray, CircleFill still holds up!

[Pete]

Here's my fix to the 1 to 400 problem. Hey, check it carefully, as I flipped through it fast. No patience for this crap, sorry.

Anyway, if it works it works because it simply checks the boundaries set byt the fist line statements and doesn't let the second set of line statements overlap them, which was causing the initial problem at radius entries like 45, 67, etc.

Code: QB64: [Select]

1. _TITLE "Ellipsefill from Steve"
2. SCREEN _NEWIMAGE(1000, 700, 32)
3. _SCREENMOVE 180, 20
4. 'B+ 2019-02-10 resave this code to
5. 'just test this code for proper filling without overlap, timed tests are else where
6.  
7. FOR i = 1 TO 400 'draw ellipse at various heights
8.     CLS
9.     PRINT "b Radius"; i; " Press any to get to 400, <backspace> to go back one, <esc> for next test."
10.     EllipseFill 500, 350, 400, i, _RGBA(255, 255, 255, 40)
11.     k$ = ""
12.     WHILE LEN(k$) = 0: k$ = INKEY$: WEND
13.     IF k$ = CHR$(8) THEN i = i - 2
14.     IF k$ = CHR$(27) THEN EXIT FOR
15. NEXT
16.  
17. CLS
18. WHILE _KEYDOWN(32) = 0 'check all sorts random stuff
19.     EllipseFill RND * 1000, RND * 700, RND * 100, RND * 100, _RGBA32(255 * RND, 255 * RND, 255 * RND, 100 * RND)
20.     _LIMIT 1
21. WEND
22.  
23. ' with Steve's EllipseFill, who needs CircleFill? fix for 0 radii 2019-02-05
24. ' Is this fast enough for general circle fill (June 2018):  https://www.qb64.org/forum/index.php?topic=298.msg1942#msg1942
25. '  EllipseFill SMcNeill (Nov 3, 2018) https://www.qb64.org/forum/index.php?topic=755.msg6506#msg6506
26. SUB EllipseFill (cx AS INTEGER, cy AS INTEGER, rx AS INTEGER, ry AS INTEGER, c AS _UNSIGNED LONG)
27. DIM a AS LONG, b AS LONG
28. DIM x AS LONG, y AS LONG
29.  
30. DIM yy AS LONG
31. DIM sx AS LONG, sy AS LONG
32. DIM e AS LONG
33.  
34. IF rx = 0 OR ry = 0 THEN EXIT SUB 'nothing to draw, B+ added this to avoid errors when b was 0
35.  
36. a = 2 * rx * rx
37. b = 2 * ry * ry
38. x = rx
39. xx = ry * ry * (1 - 2 * rx)
40. yy = rx * rx
41. sx = b * rx
42.  
43. DO WHILE sx >= sy 'no = ? , nope that didn't help
44.     LINE (cx - x, cy - y)-(cx + x, cy - y), c, BF
45.     IF y <> 0 THEN LINE (cx - x, cy + y)-(cx + x, cy + y), c, BF
46.     y = y + 1
47.     sy = sy + a
48.     e = e + yy
49.     yy = yy + a
50.  
51.     IF (e + e + xx) > 0 THEN 'add = ? nope no fix
52.         x = x - 1
53.         sx = sx - b
54.         e = e + xx
55.         xx = xx + b
56.     END IF
57. LOOP
58. oldy = y ' Pete's fix
59. x = 0
60. y = ry
61. xx = rx * ry
62.  
63. yy = rx * rx * (1 - 2 * ry)
64. e = 0
65. sx = 0
66. sy = a * ry
67.  
68. DO
69.     LINE (cx - x, cy - y)-(cx + x, cy - y), c, BF
70.     LINE (cx - x, cy + y)-(cx + x, cy + y), c, BF
71.     DO
72.         x = x + 1
73.         sx = sx + b
74.         e = e + xx
75.         xx = xx + b
76.     LOOP UNTIL (e + e + yy) > 0 'add = ? nope no fix
77.     y = y - 1
78.     sy = sy - a
79.     e = e + yy
80.     yy = yy + a
81. LOOP UNTIL y < oldy
82.  
83. END SUB
84.  
85.  

[bplus]

Nice Pete! I will run time tests on this fix.

[Pete]

Hey did you guys find out that different ways of expressing equations are calculated faster? Case in point, I tend to own code, and I started changing things like - r + r to - 2 * r. I was about to change things like ry * ry to ry ^2, but then I thought I'd ask here first. If - r + r, or whatever it was, would run faster than the 2 * r I changed it to, then by all means, change it back before you do the speed tests. That way, you have apples to apples, should it make a difference.

Pete

[bplus]

OK they are still running neck and neck, the gold standard running a very large radius circle 10000 time versus EllipseFill now with latest fix from Pete in a timed test. So the Ellipse fill can be used both for CircleFill and EllipseFill when ellipse needed has axis parallel to x, y axis, otherwise use TiltedEllipseFill for angular Ellipse fills.

[Pete]

Did you check what I posted above about switching up some of the math calcs? I don't want such a change to impede the speed.

Pete

[bplus]

Did you check what I posted above about switching up some of the math calcs? I don't want such a change to impede the speed.

Pete

Yes, nothing with the math was changed that I could see.
Here is the test code for time:

Code: QB64: [Select]

1. _TITLE "Steves EllipseFill (right) vrs gold standard CircleFill (left), 2 tests take about 17 secs each after you press enter."
2.  
3. DEFINT A-Z
4. SCREEN _NEWIMAGE(1220, 680, 32)
5. _SCREENMOVE 100, 20
6. _DELAY 1
7.  
8. EllipseFill 915, 305, 300, 300, _RGBA32(0, 100, 0, 40)
9. EllipseFill 915, 305, 300, 300, _RGBA32(0, 100, 0, 40)
10. INPUT "EllipseFill (fel) overlap test, press enter to continue "; wate$
11. LINE (0, 0)-(600, 20), _RGB32(0, 0, 0), BF
12. start## = TIMER
13. FOR i = 1 TO 10000
14.     EllipseFill 915, 305, 300, 300, _RGBA32(0, 100, 0, 100)
15. NEXT
16. EllipseTime## = TIMER - start##
17. _PRINTSTRING (800, 615), "Time for 10000 EllipseFills:" + STR$(EllipseTime##)
18.  
19.  
20. ' ==================================================== compare to the old gold standard
21.  
22. CircleFill 305, 305, 300, _RGBA32(0, 100, 0, 40)
23. CircleFill 305, 305, 300, _RGBA32(0, 100, 0, 40)
24. LOCATE 1, 1: INPUT "CircleFill overlap test, press enter to continue "; wate$
25. LINE (0, 0)-(600, 20), _RGB32(0, 0, 0), BF
26.  
27. start## = TIMER
28. FOR i = 1 TO 10000
29.     CircleFill 305, 305, 300, _RGBA32(0, 100, 0, 100)
30. NEXT
31. OldCircleTime## = TIMER - start##
32. _PRINTSTRING (200, 615), "Time for 10000 Circle Fills:" + STR$(OldCircleTime##)
33.  
34. 'old circle fill
35. SUB CircleFill (CX AS INTEGER, CY AS INTEGER, R AS INTEGER, C AS _UNSIGNED LONG)
36.     DIM Radius AS INTEGER, RadiusError AS INTEGER
37.     DIM X AS INTEGER, Y AS INTEGER
38.  
39.     Radius = ABS(R)
40.     RadiusError = -Radius
41.     X = Radius
42.     Y = 0
43.  
44.     IF Radius = 0 THEN PSET (CX, CY), C: EXIT SUB
45.  
46.     ' Draw the middle span here so we don't draw it twice in the main loop,
47.     ' which would be a problem with blending turned on.
48.     LINE (CX - X, CY)-(CX + X, CY), C, BF
49.  
50.     WHILE X > Y
51.         RadiusError = RadiusError + Y * 2 + 1
52.         IF RadiusError >= 0 THEN
53.             IF X <> Y + 1 THEN
54.                 LINE (CX - Y, CY - X)-(CX + Y, CY - X), C, BF
55.                 LINE (CX - Y, CY + X)-(CX + Y, CY + X), C, BF
56.             END IF
57.             X = X - 1
58.             RadiusError = RadiusError - X * 2
59.         END IF
60.         Y = Y + 1
61.         LINE (CX - X, CY - Y)-(CX + X, CY - Y), C, BF
62.         LINE (CX - X, CY + Y)-(CX + X, CY + Y), C, BF
63.     WEND
64.  
65. END SUB
66.  
67. ' now with Pete's fix for overlap 2019-02-10
68. ' with Steve's EllipseFill, who needs CircleFill? fix for 0 radii 2019-02-05
69. ' Is this fast enough for general circle fill (June 2018):  https://www.qb64.org/forum/index.php?topic=298.msg1942#msg1942
70. '  EllipseFill SMcNeill (Nov 3, 2018) https://www.qb64.org/forum/index.php?topic=755.msg6506#msg6506
71. SUB EllipseFill (cx AS INTEGER, cy AS INTEGER, rx AS INTEGER, ry AS INTEGER, c AS _UNSIGNED LONG)
72.     DIM a AS LONG, b AS LONG
73.     DIM x AS LONG, y AS LONG
74.     DIM xx AS LONG, yy AS LONG
75.     DIM sx AS LONG, sy AS LONG
76.     DIM e AS LONG
77.  
78.     IF rx = 0 OR ry = 0 THEN EXIT SUB 'nothing to draw, B+ added this to avoid errors when b was 0
79.  
80.     a = 2 * rx * rx
81.     b = 2 * ry * ry
82.     x = rx
83.     xx = ry * ry * (1 - rx - rx)
84.     yy = rx * rx
85.     sx = b * rx
86.  
87.     DO WHILE sx >= sy 'no = ? , nope that didn't help
88.         LINE (cx - x, cy - y)-(cx + x, cy - y), c, BF
89.         IF y <> 0 THEN LINE (cx - x, cy + y)-(cx + x, cy + y), c, BF
90.  
91.         y = y + 1
92.         sy = sy + a
93.         e = e + yy
94.         yy = yy + a
95.  
96.         IF (e + e + xx) > 0 THEN 'add = ? nope no fix
97.             x = x - 1
98.             sx = sx - b
99.             e = e + xx
100.             xx = xx + b
101.         END IF
102.     LOOP
103.     oldy = y ' Pete's fix
104.     x = 0
105.     y = ry
106.     xx = rx * ry
107.     yy = rx * rx * (1 - ry - ry)
108.     e = 0
109.     sx = 0
110.     sy = a * ry
111.  
112.     DO '   Pete's fix eliminate >   WHILE sx <= sy ' no  =  ? fixed once but mostly no fix
113.         LINE (cx - x, cy - y)-(cx + x, cy - y), c, BF
114.         LINE (cx - x, cy + y)-(cx + x, cy + y), c, BF
115.  
116.         DO
117.             x = x + 1
118.             sx = sx + b
119.             e = e + xx
120.             xx = xx + b
121.         LOOP UNTIL (e + e + yy) > 0 'add = ? nope no fix
122.  
123.         y = y - 1
124.         sy = sy - a
125.         e = e + yy
126.         yy = yy + a
127.  
128.     LOOP UNTIL y < oldy ' pete's fix
129.  
130. END SUB
131.  
132.  

[Pete]

No, reread it. I mean I changed a couple of lines from r + r to 2 * r. I'll post this one with all of the changes I can find to condense the math using powers, * 2, etc. Maybe it runs faster one way or the other, but I just like the math better with 2*, ^2, etc. If it makes no speed difference, it doesn't matter how you want to go about posting the finished product. Just know I changed 2 lines in the one you tested and you can change them back, for conformity sake, if you wish. Either way, yes, it produces the exact same math results.

So here is one I completely converted, unless I missed something.

Code: QB64: [Select]

1. _TITLE "Ellipsefill from Steve"
2. SCREEN _NEWIMAGE(1000, 700, 32)
3. _SCREENMOVE 180, 20
4. ' Pete changed math operations so r * r is now R^2, r + r is 2 * r, etc.
5. 'B+ 2019-02-10 resave this code to
6. 'just test this code for proper filling without overlap, timed tests are else where
7.  
8. FOR i = 1 TO 400 'draw ellipse at various heights
9.     CLS
10.     PRINT "b Radius"; i; " Press any to get to 400, <backspace> to go back one, <esc> for next test."
11.     EllipseFill 500, 350, 400, i, _RGBA(255, 255, 255, 40)
12.     k$ = ""
13.     WHILE LEN(k$) = 0: k$ = INKEY$: WEND
14.     IF k$ = CHR$(8) THEN i = i - 2
15.     IF k$ = CHR$(27) THEN EXIT FOR
16. NEXT
17.  
18. CLS
19. WHILE _KEYDOWN(32) = 0 'check all sorts random stuff
20.     EllipseFill RND * 1000, RND * 700, RND * 100, RND * 100, _RGBA32(255 * RND, 255 * RND, 255 * RND, 100 * RND)
21.     _LIMIT 1
22. WEND
23.  
24. ' with Steve's EllipseFill, who needs CircleFill? fix for 0 radii 2019-02-05
25. ' Is this fast enough for general circle fill (June 2018):  https://www.qb64.org/forum/index.php?topic=298.msg1942#msg1942
26. '  EllipseFill SMcNeill (Nov 3, 2018) https://www.qb64.org/forum/index.php?topic=755.msg6506#msg6506
27. SUB EllipseFill (cx AS INTEGER, cy AS INTEGER, rx AS INTEGER, ry AS INTEGER, c AS _UNSIGNED LONG)
28. DIM a AS LONG, b AS LONG
29. DIM x AS LONG, y AS LONG
30.  
31. DIM yy AS LONG
32. DIM sx AS LONG, sy AS LONG
33. DIM e AS LONG
34.  
35. IF rx = 0 OR ry = 0 THEN EXIT SUB 'nothing to draw, B+ added this to avoid errors when b was 0
36.  
37. a = 2 * rx ^ 2
38. b = 2 * ry ^ 2
39. x = rx
40. xx = ry ^ 2 * (1 - 2 * rx)
41. yy = rx ^ 2
42. sx = b * rx
43.  
44. DO WHILE sx >= sy 'no = ? , nope that didn't help
45.     LINE (cx - x, cy - y)-(cx + x, cy - y), c, BF
46.     IF y <> 0 THEN LINE (cx - x, cy + y)-(cx + x, cy + y), c, BF
47.     y = y + 1
48.     sy = sy + a
49.     e = e + yy
50.     yy = yy + a
51.  
52.     IF (2 * e + xx) > 0 THEN 'add = ? nope no fix
53.         x = x - 1
54.         sx = sx - b
55.         e = e + xx
56.         xx = xx + b
57.     END IF
58. LOOP
59.  
60. oldy = y ' Pete's fix
61. x = 0
62. y = ry
63. xx = rx * ry
64.  
65. yy = rx ^ 2 * (1 - 2 * ry)
66. e = 0
67. sx = 0
68. sy = a * ry
69.  
70. DO
71.     LINE (cx - x, cy - y)-(cx + x, cy - y), c, BF
72.     LINE (cx - x, cy + y)-(cx + x, cy + y), c, BF
73.     DO
74.         x = x + 1
75.         sx = sx + b
76.         e = e + xx
77.         xx = xx + b
78.     LOOP UNTIL (2 * e + yy) > 0 'add = ? nope no fix
79.     y = y - 1
80.     sy = sy - a
81.     e = e + yy
82.     yy = yy + a
83. LOOP UNTIL y < oldy ' Pete's fix applied here.
84.  
85. END SUB
86.  

[SMcNeill]

R + R is faster than 2 * R
R * R is faster than R ^ 2

Certain operations have more overhead than others.  If you’re going to optimize for speed, choose the operator with the fastest performance.  ;)

[Pete]

That's what I wanted to know.

So, my fix applied with the fastest math method according to Steve would be...

Code: QB64: [Select]

1. _TITLE "Ellipsefill from Steve"
2. SCREEN _NEWIMAGE(1000, 700, 32)
3. _SCREENMOVE 180, 20
4. 'B+ 2019-02-10 resave this code to
5. 'just test this code for proper filling without overlap, timed tests are else where
6.  
7. FOR i = 1 TO 400 'draw ellipse at various heights
8.     CLS
9.     PRINT "b Radius"; i; " Press any to get to 400, <backspace> to go back one, <esc> for next test."
10.     EllipseFill 500, 350, 400, i, _RGBA(255, 255, 255, 40)
11.     k$ = ""
12.     WHILE LEN(k$) = 0: k$ = INKEY$: WEND
13.     IF k$ = CHR$(8) THEN i = i - 2
14.     IF k$ = CHR$(27) THEN EXIT FOR
15. NEXT
16.  
17. CLS
18. WHILE _KEYDOWN(32) = 0 'check all sorts random stuff
19.     EllipseFill RND * 1000, RND * 700, RND * 100, RND * 100, _RGBA32(255 * RND, 255 * RND, 255 * RND, 100 * RND)
20.     _LIMIT 1
21. WEND
22.  
23. ' with Steve's EllipseFill, who needs CircleFill? fix for 0 radii 2019-02-05
24. ' Is this fast enough for general circle fill (June 2018):  https://www.qb64.org/forum/index.php?topic=298.msg1942#msg1942
25. '  EllipseFill SMcNeill (Nov 3, 2018) https://www.qb64.org/forum/index.php?topic=755.msg6506#msg6506
26. SUB EllipseFill (cx AS INTEGER, cy AS INTEGER, rx AS INTEGER, ry AS INTEGER, c AS _UNSIGNED LONG)
27. DIM a AS LONG, b AS LONG
28. DIM x AS LONG, y AS LONG
29.  
30. DIM yy AS LONG
31. DIM sx AS LONG, sy AS LONG
32. DIM e AS LONG
33.  
34. IF rx = 0 OR ry = 0 THEN EXIT SUB 'nothing to draw, B+ added this to avoid errors when b was 0
35.  
36. a = 2 * rx * rx
37. b = 2 * ry * ry
38. x = rx
39. xx = ry * ry * (1 - rx - rx)
40. yy = rx * rx
41. sx = b * rx
42.  
43. DO WHILE sx >= sy
44.     LINE (cx - x, cy - y)-(cx + x, cy - y), c, BF
45.     IF y <> 0 THEN LINE (cx - x, cy + y)-(cx + x, cy + y), c, BF
46.     y = y + 1
47.     sy = sy + a
48.     e = e + yy
49.     yy = yy + a
50.  
51.     IF (e + e + xx) > 0 THEN
52.         x = x - 1
53.         sx = sx - b
54.         e = e + xx
55.         xx = xx + b
56.     END IF
57. LOOP
58. oldy = y ' Pete's fix. Get the last fill position.
59. x = 0
60. y = ry
61. xx = rx * ry
62.  
63. yy = rx * rx * (1 - ry - ry)
64. e = 0
65. sx = 0
66. sy = a * ry
67.  
68. DO
69.     LINE (cx - x, cy - y)-(cx + x, cy - y), c, BF
70.     LINE (cx - x, cy + y)-(cx + x, cy + y), c, BF
71.     DO
72.         x = x + 1
73.         sx = sx + b
74.         e = e + xx
75.         xx = xx + b
76.     LOOP UNTIL (e + e + yy) > 0
77.     y = y - 1
78.     sy = sy - a
79.     e = e + yy
80.     yy = yy + a
81. LOOP UNTIL y < oldy ' Pete's fix applied here.
82.  
83. END SUB
84.  

[bplus]

That's what I wanted to know.

So, my fix applied with the fastest math method according to Steve would be...

Code: QB64: [Select]

1. _TITLE "Ellipsefill from Steve"
2. SCREEN _NEWIMAGE(1000, 700, 32)
3. _SCREENMOVE 180, 20
4. 'B+ 2019-02-10 resave this code to
5. 'just test this code for proper filling without overlap, timed tests are else where
6.  
7. FOR i = 1 TO 400 'draw ellipse at various heights
8.     CLS
9.     PRINT "b Radius"; i; " Press any to get to 400, <backspace> to go back one, <esc> for next test."
10.     EllipseFill 500, 350, 400, i, _RGBA(255, 255, 255, 40)
11.     k$ = ""
12.     WHILE LEN(k$) = 0: k$ = INKEY$: WEND
13.     IF k$ = CHR$(8) THEN i = i - 2
14.     IF k$ = CHR$(27) THEN EXIT FOR
15. NEXT
16.  
17. CLS
18. WHILE _KEYDOWN(32) = 0 'check all sorts random stuff
19.     EllipseFill RND * 1000, RND * 700, RND * 100, RND * 100, _RGBA32(255 * RND, 255 * RND, 255 * RND, 100 * RND)
20.     _LIMIT 1
21. WEND
22.  
23. ' with Steve's EllipseFill, who needs CircleFill? fix for 0 radii 2019-02-05
24. ' Is this fast enough for general circle fill (June 2018):  https://www.qb64.org/forum/index.php?topic=298.msg1942#msg1942
25. '  EllipseFill SMcNeill (Nov 3, 2018) https://www.qb64.org/forum/index.php?topic=755.msg6506#msg6506
26. SUB EllipseFill (cx AS INTEGER, cy AS INTEGER, rx AS INTEGER, ry AS INTEGER, c AS _UNSIGNED LONG)
27. DIM a AS LONG, b AS LONG
28. DIM x AS LONG, y AS LONG
29.  
30. DIM yy AS LONG
31. DIM sx AS LONG, sy AS LONG
32. DIM e AS LONG
33.  
34. IF rx = 0 OR ry = 0 THEN EXIT SUB 'nothing to draw, B+ added this to avoid errors when b was 0
35.  
36. a = 2 * rx * rx
37. b = 2 * ry * ry
38. x = rx
39. xx = ry * ry * (1 - rx - rx)
40. yy = rx * rx
41. sx = b * rx
42.  
43. DO WHILE sx >= sy
44.     LINE (cx - x, cy - y)-(cx + x, cy - y), c, BF
45.     IF y <> 0 THEN LINE (cx - x, cy + y)-(cx + x, cy + y), c, BF
46.     y = y + 1
47.     sy = sy + a
48.     e = e + yy
49.     yy = yy + a
50.  
51.     IF (e + e + xx) > 0 THEN
52.         x = x - 1
53.         sx = sx - b
54.         e = e + xx
55.         xx = xx + b
56.     END IF
57. LOOP
58. oldy = y ' Pete's fix. Get the last fill position.
59. x = 0
60. y = ry
61. xx = rx * ry
62.  
63. yy = rx * rx * (1 - ry - ry)
64. e = 0
65. sx = 0
66. sy = a * ry
67.  
68. DO
69.     LINE (cx - x, cy - y)-(cx + x, cy - y), c, BF
70.     LINE (cx - x, cy + y)-(cx + x, cy + y), c, BF
71.     DO
72.         x = x + 1
73.         sx = sx + b
74.         e = e + xx
75.         xx = xx + b
76.     LOOP UNTIL (e + e + yy) > 0
77.     y = y - 1
78.     sy = sy - a
79.     e = e + yy
80.     yy = yy + a
81. LOOP UNTIL y < oldy ' Pete's fix applied here.
82.  
83. END SUB
84.  

And that is what I had in my timed tests and that is why I said Pete made no math changes.

we could change:
    a = 2 * rx * rx
    b = 2 * ry * ry

to a = rx*rx + rx*rx
    b = ry*ry + ry * ry

[SMcNeill]

    a = 2 * rx * rx

to a = rx*rx + rx*rx

You’ll just be slower....

You’re going from 2 multiplication operations to 2 multiplication operations AND an addition operation.

Maybe:  a1 = rx * rx: a = a1 + a1  (If lookup times are faster)

[bplus]

Yep! Confirmed I changed it back.