QB64.org Forum

Active Forums => Programs => Topic started by: SMcNeill on November 03, 2018, 06:18:38 am

Title: EllipseFill
Post by: SMcNeill on November 03, 2018, 06:18:38 am

An ellipse filling routine, as fast as (or faster than) CircleFill:

Code: QB64: [Select]

1. SCREEN _NEWIMAGE(1000, 800, 32)
2.  
3.  
4. t# = TIMER
5. FOR i = 1 TO 1000
6.     CircleFill 500, 400, 400, -1
7. NEXT
8. t2# = TIMER
9. CLS
10. FOR i = 1 TO 1000
11.     EllipseFill 500, 400, 400, 400, -1
12. NEXT
13. t3# = TIMER
14.  
15.  
16. PRINT "Time for CircleFill:"; t2# - t#
17. PRINT "Time for EllipseFill:"; t3# - t2#
18.  
19. SLEEP
20.  
21. CLS
22. EllipseFill 500, 400, 400, 200, &HAFFF0000
23. CircleFill 500, 400, 180, &HFF000000
24. EllipseFill 500, 400, 20, 160, &HAFFF0000
25. SLEEP
26.  
27. CLS
28.  
29. EllipseFill 500, 400, 500, 400, &HAFFF0000
30. SLEEP
31. END
32.  
33. SUB CircleFill (CX AS LONG, CY AS LONG, R AS LONG, C AS LONG)
34.     DIM Radius AS LONG, RadiusError AS LONG
35.     DIM X AS LONG, Y AS LONG
36.  
37.     Radius = ABS(R)
38.     RadiusError = -Radius
39.     X = Radius
40.     Y = 0
41.  
42.     IF Radius = 0 THEN PSET (CX, CY), C: EXIT SUB
43.  
44.     ' Draw the middle span here so we don't draw it twice in the main loop,
45.     ' which would be a problem with blending turned on.
46.     LINE (CX - X, CY)-(CX + X, CY), C, BF
47.  
48.     WHILE X > Y
49.         RadiusError = RadiusError + Y * 2 + 1
50.         IF RadiusError >= 0 THEN
51.             IF X <> Y + 1 THEN
52.                 LINE (CX - Y, CY - X)-(CX + Y, CY - X), C, BF
53.                 LINE (CX - Y, CY + X)-(CX + Y, CY + X), C, BF
54.             END IF
55.             X = X - 1
56.             RadiusError = RadiusError - X * 2
57.         END IF
58.         Y = Y + 1
59.         LINE (CX - X, CY - Y)-(CX + X, CY - Y), C, BF
60.         LINE (CX - X, CY + Y)-(CX + X, CY + Y), C, BF
61.     WEND
62. END SUB
63.  
64. SUB EllipseFill (cx AS INTEGER, cy AS INTEGER, rx AS INTEGER, ry AS INTEGER, c AS LONG)
65.     DIM a AS LONG, b AS LONG
66.     DIM x AS LONG, y AS LONG
67.     DIM xx AS LONG, yy AS LONG
68.     DIM sx AS LONG, sy AS LONG
69.     DIM e AS LONG
70.  
71.     a = 2 * rx * rx
72.     b = 2 * ry * ry
73.     x = rx
74.     xx = ry * ry * (1 - rx - rx)
75.     yy = rx * rx
76.     sx = b * rx
77.  
78.     DO WHILE sx >= sy
79.         LINE (cx - x, cy - y)-(cx + x, cy - y), c, BF
80.         IF y <> 0 THEN LINE (cx - x, cy + y)-(cx + x, cy + y), c, BF
81.  
82.         y = y + 1
83.         sy = sy + a
84.         e = e + yy
85.         yy = yy + a
86.  
87.         IF (e + e + xx) > 0 THEN
88.             x = x - 1
89.             sx = sx - b
90.             e = e + xx
91.             xx = xx + b
92.         END IF
93.     LOOP
94.  
95.     x = 0
96.     y = ry
97.     xx = rx * ry
98.     yy = rx * rx * (1 - ry - ry)
99.     e = 0
100.     sx = 0
101.     sy = a * ry
102.  
103.     DO WHILE sx <= sy
104.         LINE (cx - x, cy - y)-(cx + x, cy - y), c, BF
105.         LINE (cx - x, cy + y)-(cx + x, cy + y), c, BF
106.  
107.         DO
108.             x = x + 1
109.             sx = sx + b
110.             e = e + xx
111.             xx = xx + b
112.         LOOP UNTIL (e + e + yy) > 0
113.  
114.         y = y - 1
115.         sy = sy - a
116.         e = e + yy
117.         yy = yy + a
118.  
119.     LOOP
120.  
121. END SUB
122.  

Note: I take no credit for this EllipseFill, as I found it on an old archive on my drive and then promptly lost it again while closing tabs and testing things.  I dunno who came up with this originally, but I'll see if I can find where the crap the source was hiding so I can give proper credit where credit is due later.

Edit: Original routine that I'd posted was created by unknown author.  Version up now has been modified to remove streaking (as described by bplus below) and improve performance slightly, by yours truly.  Enjoy!

Title: Re: EllipseFill
Post by: bplus on November 03, 2018, 12:57:30 pm

Steve, you are on a hot streak! One great post after another.

From another forum I learned that if you have code for an ellipse, you don't need to also carry code for a circle.

Oh, one more test...

Title: Re: EllipseFill
Post by: bplus on November 03, 2018, 01:03:17 pm

Fails! but sure does look neat.

Code: QB64: [Select]

1. SCREEN _NEWIMAGE(1000, 700, 32)
2.  
3.  
4. t# = TIMER
5. FOR i = 1 TO 1000
6.     CircleFill 500, 400, 400, -1
7. NEXT
8. CLS
9. t2# = TIMER
10. FOR i = 1 TO 1000
11.     EllipseFill 500, 400, 400, 400, -1
12. NEXT
13. t3# = TIMER
14.  
15.  
16. PRINT "Time for CircleFill:"; t2# - t#
17. PRINT "Time for EllipseFill:"; t3# - t2#
18.  
19. SLEEP
20.  
21. CLS
22. WHILE _KEYDOWN(27) = 0
23.     EllipseFill RND * 1000, RND * 700, RND * 100, RND * 100, _RGBA32(255 * RND, 255 * RND, 255 * RND, 100 * RND)
24.     _LIMIT 5
25. WEND
26.  
27. SUB CircleFill (CX AS LONG, CY AS LONG, R AS LONG, C AS LONG)
28.     DIM Radius AS LONG, RadiusError AS LONG
29.     DIM X AS LONG, Y AS LONG
30.  
31.     Radius = ABS(R)
32.     RadiusError = -Radius
33.     X = Radius
34.     Y = 0
35.  
36.     IF Radius = 0 THEN PSET (CX, CY), C: EXIT SUB
37.  
38.     ' Draw the middle span here so we don't draw it twice in the main loop,
39.     ' which would be a problem with blending turned on.
40.     LINE (CX - X, CY)-(CX + X, CY), C, BF
41.  
42.     WHILE X > Y
43.         RadiusError = RadiusError + Y * 2 + 1
44.         IF RadiusError >= 0 THEN
45.             IF X <> Y + 1 THEN
46.                 LINE (CX - Y, CY - X)-(CX + Y, CY - X), C, BF
47.                 LINE (CX - Y, CY + X)-(CX + Y, CY + X), C, BF
48.             END IF
49.             X = X - 1
50.             RadiusError = RadiusError - X * 2
51.         END IF
52.         Y = Y + 1
53.         LINE (CX - X, CY - Y)-(CX + X, CY - Y), C, BF
54.         LINE (CX - X, CY + Y)-(CX + X, CY + Y), C, BF
55.     WEND
56. END SUB
57.  
58. SUB EllipseFill (cx AS INTEGER, cy AS INTEGER, rx AS INTEGER, ry AS INTEGER, c AS _UNSIGNED LONG)
59.     DIM a AS LONG, b AS LONG
60.     DIM x AS LONG, y AS LONG
61.     DIM xx AS LONG, yy AS LONG
62.     DIM sx AS LONG, sy AS LONG
63.     DIM e AS LONG
64.  
65.     a = 2 * rx * rx
66.     b = 2 * ry * ry
67.     x = rx
68.     xx = ry * ry * (1 - rx - rx)
69.     yy = rx * rx
70.     sx = b * rx
71.  
72.     DO WHILE sx >= sy
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.  
76.         y = y + 1
77.         sy = sy + a
78.         e = e + yy
79.         yy = yy + a
80.  
81.         IF (e + e + xx) > 0 THEN
82.             x = x - 1
83.             sx = sx - b
84.             e = e + xx
85.             xx = xx + b
86.         END IF
87.     LOOP
88.  
89.     x = 0
90.     y = ry
91.     xx = rx * ry
92.     yy = rx * rx * (1 - ry - ry)
93.     e = 0
94.     sx = 0
95.     sy = a * ry
96.  
97.     DO WHILE sx <= sy
98.         LINE (cx - x, cy - y)-(cx + x, cy - y), c, BF
99.         LINE (cx - x, cy + y)-(cx + x, cy + y), c, BF
100.  
101.         x = x + 1
102.         sx = sx + b
103.         e = e + xx
104.         xx = xx + b
105.  
106.         IF (e + e + yy) > 0 THEN
107.             y = y - 1
108.             sy = sy - a
109.             e = e + yy
110.             yy = yy + a
111.         END IF
112.     LOOP
113.  
114. END SUB
115.  
116.  

Title: Re: EllipseFill
Post by: TerryRitchie on November 03, 2018, 01:50:31 pm

Quote from: bplus on November 03, 2018, 12:57:30 pm

Steve, you are on a hot streak! One great post after another.

My SMcNeill examples folder is getting quite large with code snippets :)

Title: Re: EllipseFill
Post by: SMcNeill on November 03, 2018, 02:45:52 pm

Quote from: bplus on November 03, 2018, 12:57:30 pm

Steve, you are on a hot streak! One great post after another.

From another forum I learned that if you have code for an ellipse, you don't need to also carry code for a circle.

Oh, one more test...

Exactly!  After all, a circle is nothing more than an ellipse whose Xradius is the same as the Yradius.  Think of it exactly as you would a square -- nothing more than a rectangle whose length is the same as its width.

If you can draw a rectangle, you can create a square.  If you can draw an ellipse, you can create a circle.

This is a little slower than CircleFill, but for the added flexibility, and the minor performance lost, I think it's more than acceptable as a "go to routine", in most instances.

Title: Re: EllipseFill
Post by: bplus on November 03, 2018, 02:52:34 pm

Well I would use it to replace circle fill because the time is so close but it is failing the alpha test, it's lines are overlapping and leaving streaks which I thought you might see in screen shot above.

Title: Re: EllipseFill
Post by: SMcNeill on November 03, 2018, 02:56:58 pm

I'm on my iPad right now; didn't zoom in that close to look good.  I'll play around with it later; it might be something easy enough to correct.  :)

Title: Re: EllipseFill
Post by: SMcNeill on November 03, 2018, 03:24:22 pm

Try this version, bplus, and see if it fixes the line issue for you:

Code: QB64: [Select]

1. SCREEN _NEWIMAGE(1000, 800, 32)
2.  
3.  
4. t# = TIMER
5. FOR i = 1 TO 1000
6.     CircleFill 500, 400, 400, -1
7. NEXT
8. t2# = TIMER
9. FOR i = 1 TO 1000
10.     EllipseFill 500, 400, 200, 400, -1
11. NEXT
12. t3# = TIMER
13.  
14.  
15. PRINT "Time for CircleFill:"; t2# - t#
16. PRINT "Time for EllipseFill:"; t3# - t2#
17.  
18. SLEEP
19.  
20. CLS
21. EllipseFill 500, 400, 400, 200, &H7FFFFF00
22. CircleFill 500, 400, 180, &HFF000000
23. EllipseFill 500, 400, 20, 160, &H7FF00FF0
24.  
25. END
26.  
27. SUB CircleFill (CX AS LONG, CY AS LONG, R AS LONG, C AS LONG)
28.     DIM Radius AS LONG, RadiusError AS LONG
29.     DIM X AS LONG, Y AS LONG
30.  
31.     Radius = ABS(R)
32.     RadiusError = -Radius
33.     X = Radius
34.     Y = 0
35.  
36.     IF Radius = 0 THEN PSET (CX, CY), C: EXIT SUB
37.  
38.     ' Draw the middle span here so we don't draw it twice in the main loop,
39.     ' which would be a problem with blending turned on.
40.     LINE (CX - X, CY)-(CX + X, CY), C, BF
41.  
42.     WHILE X > Y
43.         RadiusError = RadiusError + Y * 2 + 1
44.         IF RadiusError >= 0 THEN
45.             IF X <> Y + 1 THEN
46.                 LINE (CX - Y, CY - X)-(CX + Y, CY - X), C, BF
47.                 LINE (CX - Y, CY + X)-(CX + Y, CY + X), C, BF
48.             END IF
49.             X = X - 1
50.             RadiusError = RadiusError - X * 2
51.         END IF
52.         Y = Y + 1
53.         LINE (CX - X, CY - Y)-(CX + X, CY - Y), C, BF
54.         LINE (CX - X, CY + Y)-(CX + X, CY + Y), C, BF
55.     WEND
56. END SUB
57.  
58. SUB EllipseFill (cx AS INTEGER, cy AS INTEGER, rx AS INTEGER, ry AS INTEGER, c AS LONG)
59.     DIM a AS LONG, b AS LONG
60.     DIM x AS LONG, y AS LONG
61.     DIM xx AS LONG, yy AS LONG
62.     DIM sx AS LONG, sy AS LONG
63.     DIM e AS LONG
64.  
65.     a = 2 * rx * rx
66.     b = 2 * ry * ry
67.     x = rx
68.     xx = ry * ry * (1 - rx - rx)
69.     yy = rx * rx
70.     sx = b * rx
71.  
72.     DO WHILE sx >= sy
73.         LINE (cx - x, cy - y)-(cx + x, cy - y), c
74.         IF y <> -y THEN LINE (cx - x, cy + y)-(cx + x, cy + y), c, BF
75.         y = y + 1
76.         sy = sy + a
77.         e = e + yy
78.         yy = yy + a
79.  
80.         IF (e + e + xx) > 0 THEN
81.             x = x - 1
82.             sx = sx - b
83.             e = e + xx
84.             xx = xx + b
85.         END IF
86.     LOOP
87.  
88.     x = 0
89.     y = ry
90.     xx = rx * ry
91.     yy = rx * rx * (1 - ry - ry)
92.     e = 0
93.     sx = 1
94.     sy = a * ry
95.  
96.     DO WHILE sx <= sy
97.  
98.         LINE (cx - x, cy - y)-(cx + x, cy - y), c, BF
99.         LINE (cx - x, cy + y)-(cx + x, cy + y), c, BF
100.  
101.         DO
102.             x = x + 1
103.             sx = sx + b
104.             e = e + xx
105.             xx = xx + b
106.         LOOP UNTIL (e + e + yy) > 0
107.  
108.         y = y - 1
109.         sy = sy - a
110.         e = e + yy
111.         yy = yy + a
112.  
113.     LOOP
114.  
115. END SUB

Title: Re: EllipseFill
Post by: bplus on November 03, 2018, 03:33:33 pm

Thanks Steve,

Yes, overlap fixed but now time is 1.32 for circle and 2.47 for ellipse, so I will keep circle but use this for ellipse because I don't think I will find better.

Title: Re: EllipseFill
Post by: SMcNeill on November 03, 2018, 03:41:59 pm

Quote from: bplus on November 03, 2018, 03:33:33 pm

Thanks Steve,

Yes, overlap fixed but now time is 1.32 for circle and 2.47 for ellipse, so I will keep circle but use this for ellipse because I don't think I will find better.

I found better:

Code: QB64: [Select]

1. SCREEN _NEWIMAGE(1000, 800, 32)
2.  
3.  
4. t# = TIMER
5. FOR i = 1 TO 1000
6.     CircleFill 500, 400, 400, -1
7. NEXT
8. t2# = TIMER
9. CLS
10. FOR i = 1 TO 1000
11.     EllipseFill 500, 400, 400, 400, -1
12. NEXT
13. t3# = TIMER
14.  
15.  
16. PRINT "Time for CircleFill:"; t2# - t#
17. PRINT "Time for EllipseFill:"; t3# - t2#
18.  
19. SLEEP
20.  
21. CLS
22. EllipseFill 500, 400, 400, 200, &HAFFF0000
23. CircleFill 500, 400, 180, &HFF000000
24. EllipseFill 500, 400, 20, 160, &HAFFF0000
25. SLEEP
26.  
27. CLS
28.  
29. EllipseFill 500, 400, 500, 400, &HAFFF0000
30. SLEEP
31. END
32.  
33. SUB CircleFill (CX AS LONG, CY AS LONG, R AS LONG, C AS LONG)
34.     DIM Radius AS LONG, RadiusError AS LONG
35.     DIM X AS LONG, Y AS LONG
36.  
37.     Radius = ABS(R)
38.     RadiusError = -Radius
39.     X = Radius
40.     Y = 0
41.  
42.     IF Radius = 0 THEN PSET (CX, CY), C: EXIT SUB
43.  
44.     ' Draw the middle span here so we don't draw it twice in the main loop,
45.     ' which would be a problem with blending turned on.
46.     LINE (CX - X, CY)-(CX + X, CY), C, BF
47.  
48.     WHILE X > Y
49.         RadiusError = RadiusError + Y * 2 + 1
50.         IF RadiusError >= 0 THEN
51.             IF X <> Y + 1 THEN
52.                 LINE (CX - Y, CY - X)-(CX + Y, CY - X), C, BF
53.                 LINE (CX - Y, CY + X)-(CX + Y, CY + X), C, BF
54.             END IF
55.             X = X - 1
56.             RadiusError = RadiusError - X * 2
57.         END IF
58.         Y = Y + 1
59.         LINE (CX - X, CY - Y)-(CX + X, CY - Y), C, BF
60.         LINE (CX - X, CY + Y)-(CX + X, CY + Y), C, BF
61.     WEND
62. END SUB
63.  
64. SUB EllipseFill (cx AS INTEGER, cy AS INTEGER, rx AS INTEGER, ry AS INTEGER, c AS LONG)
65.     DIM a AS LONG, b AS LONG
66.     DIM x AS LONG, y AS LONG
67.     DIM xx AS LONG, yy AS LONG
68.     DIM sx AS LONG, sy AS LONG
69.     DIM e AS LONG
70.  
71.     a = 2 * rx * rx
72.     b = 2 * ry * ry
73.     x = rx
74.     xx = ry * ry * (1 - rx - rx)
75.     yy = rx * rx
76.     sx = b * rx
77.  
78.     DO WHILE sx >= sy
79.         LINE (cx - x, cy - y)-(cx + x, cy - y), c, BF
80.         IF y <> 0 THEN LINE (cx - x, cy + y)-(cx + x, cy + y), c, BF
81.  
82.         y = y + 1
83.         sy = sy + a
84.         e = e + yy
85.         yy = yy + a
86.  
87.         IF (e + e + xx) > 0 THEN
88.             x = x - 1
89.             sx = sx - b
90.             e = e + xx
91.             xx = xx + b
92.         END IF
93.     LOOP
94.  
95.     x = 0
96.     y = ry
97.     xx = rx * ry
98.     yy = rx * rx * (1 - ry - ry)
99.     e = 0
100.     sx = 0
101.     sy = a * ry
102.  
103.     DO WHILE sx <= sy
104.         LINE (cx - x, cy - y)-(cx + x, cy - y), c, BF
105.         LINE (cx - x, cy + y)-(cx + x, cy + y), c, BF
106.  
107.         DO
108.             x = x + 1
109.             sx = sx + b
110.             e = e + xx
111.             xx = xx + b
112.         LOOP UNTIL (e + e + yy) > 0
113.  
114.         y = y - 1
115.         sy = sy - a
116.         e = e + yy
117.         yy = yy + a
118.  
119.     LOOP
120.  
121. END SUB
122.  

This is now running AT THE EXACT SAME SPEED AS CIRCLEFILL on my machine.  And, I'm not seeing any lines in the output.   Try it out and see what you think.  :D

Title: Re: EllipseFill
Post by: Petr on November 03, 2018, 03:48:29 pm

Excellent! CircleFill: 1.8671875, EllipseFill: 1.59375

Title: Re: EllipseFill
Post by: SMcNeill on November 03, 2018, 03:52:05 pm

Quote from: Petr on November 03, 2018, 03:48:29 pm

Excellent! CircleFill: 1.8671875, EllipseFill: 1.59375

In QB64x64, I get EllipseFill running faster than CircleFill, as well.
In QB64x32, I get them running at almost the exact same speed.

I think I've found a nice little replacement for CircleFill with this routine.  :D

Title: Re: EllipseFill
Post by: bplus on November 03, 2018, 04:22:18 pm

Well if that don't beat all!

We couldn't find a faster way to do circles faster until started trying ellipse! I am getting faster circle fill with ellipse fill.

Nice one, Steve!

Title: Re: EllipseFill
Post by: SMcNeill on November 03, 2018, 05:22:42 pm

Quote from: bplus on November 03, 2018, 04:22:18 pm

Well if that don't beat all!

We couldn't find a faster way to do circles faster until started trying ellipse! I am getting faster circle fill with ellipse fill.

Nice one, Steve!

I think it's good enough now, it's earned itself a spot over in my forum as well: http://qb64.freeforums.net/thread/9/circlefill-ellipsefill

Title: Re: EllipseFill
Post by: SMcNeill on November 03, 2018, 07:22:59 pm

And, after playing around with EllipseFill, I also now have a second way to do CircleFill:

Code: QB64: [Select]

1. SCREEN _NEWIMAGE(1000, 800, 32)
2.  
3.  
4. t# = TIMER
5. FOR i = 1 TO 1000
6.     NewCircleFill 500, 400, 400, -1
7. NEXT
8. t2# = TIMER
9.  
10. CLS
11. FOR i = 1 TO 1000
12.     CircleFill 500, 400, 400, -1
13. NEXT
14. t3# = TIMER
15.  
16. CLS
17. FOR i = 1 TO 1000
18.     EllipseFill 500, 400, 400, 400, -1
19. NEXT
20. t4# = TIMER
21.  
22.  
23. PRINT "Time for NewCircleFill:"; t2# - t#
24. PRINT "Time for CircleFill:"; t3# - t2#
25. PRINT "Time for EllipseFill:"; t4# - t3#
26.  
27. SLEEP
28.  
29. CLS
30. EllipseFill 500, 400, 400, 200, &HAFFF0000
31. CircleFill 500, 400, 180, &HFF000000
32. EllipseFill 500, 400, 20, 160, &HAFFF0000
33. SLEEP
34.  
35. CLS
36.  
37. EllipseFill 500, 400, 500, 400, &HAFFF0000
38. SLEEP
39. END
40.  
41. SUB CircleFill (CX AS LONG, CY AS LONG, R AS LONG, C AS LONG)
42.     DIM Radius AS LONG, RadiusError AS LONG
43.     DIM X AS LONG, Y AS LONG
44.  
45.     Radius = ABS(R)
46.     RadiusError = -Radius
47.     X = Radius
48.     Y = 0
49.  
50.     IF Radius = 0 THEN PSET (CX, CY), C: EXIT SUB
51.  
52.     ' Draw the middle span here so we don't draw it twice in the main loop,
53.     ' which would be a problem with blending turned on.
54.     LINE (CX - X, CY)-(CX + X, CY), C, BF
55.  
56.     WHILE X > Y
57.         RadiusError = RadiusError + Y * 2 + 1
58.         IF RadiusError >= 0 THEN
59.             IF X <> Y + 1 THEN
60.                 LINE (CX - Y, CY - X)-(CX + Y, CY - X), C, BF
61.                 LINE (CX - Y, CY + X)-(CX + Y, CY + X), C, BF
62.             END IF
63.             X = X - 1
64.             RadiusError = RadiusError - X * 2
65.         END IF
66.         Y = Y + 1
67.         LINE (CX - X, CY - Y)-(CX + X, CY - Y), C, BF
68.         LINE (CX - X, CY + Y)-(CX + X, CY + Y), C, BF
69.     WEND
70. END SUB
71.  
72. SUB NewCircleFill (cx AS INTEGER, cy AS INTEGER, r AS INTEGER, c AS LONG)
73.     DIM x AS LONG
74.     DIM y AS LONG
75.     DIM e AS LONG
76.  
77.     x = r
78.     e = -x
79.  
80.     DO WHILE x >= y
81.         LINE (cx - x, cy - y)-(cx + x, cy - y), c, BF
82.         IF y <> 0 THEN LINE (cx - x, cy + y)-(cx + x, cy + y), c, BF
83.  
84.         y = y + 1
85.         e = e + y + y
86.         IF e > 0 THEN
87.             x = x - 1
88.             e = e - x - x
89.         END IF
90.     LOOP
91.     x = r
92.     e = -x
93.     y = 0
94.  
95.     DO WHILE x >= y
96.         LINE (cx - y, cy - x)-(cx + y, cy - x), c, BF
97.         LINE (cx - y, cy + x)-(cx + y, cy + x), c, BF
98.         DO
99.             y = y + 1
100.             e = e + y + y
101.         LOOP UNTIL e > 0
102.         x = x - 1
103.         e = e - x - x
104.     LOOP
105. END SUB
106.  
107.  
108.  
109. SUB EllipseFill (cx AS INTEGER, cy AS INTEGER, rx AS INTEGER, ry AS INTEGER, c AS LONG)
110.     DIM a AS LONG, b AS LONG
111.     DIM x AS LONG, y AS LONG
112.     DIM xx AS LONG, yy AS LONG
113.     DIM sx AS LONG, sy AS LONG
114.     DIM e AS LONG
115.  
116.     a = 2 * rx * rx
117.     b = 2 * ry * ry
118.     x = rx
119.     xx = ry * ry * (1 - rx - rx)
120.     yy = rx * rx
121.     sx = b * rx
122.  
123.     DO WHILE sx >= sy
124.         LINE (cx - x, cy - y)-(cx + x, cy - y), c, BF
125.         IF y <> 0 THEN LINE (cx - x, cy + y)-(cx + x, cy + y), c, BF
126.  
127.         y = y + 1
128.         sy = sy + a
129.         e = e + yy
130.         yy = yy + a
131.  
132.         IF (e + e + xx) > 0 THEN
133.             x = x - 1
134.             sx = sx - b
135.             e = e + xx
136.             xx = xx + b
137.         END IF
138.     LOOP
139.  
140.     x = 0
141.     y = ry
142.     xx = rx * ry
143.     yy = rx * rx * (1 - ry - ry)
144.     e = 0
145.     sx = 1
146.     sy = a * ry
147.  
148.     DO WHILE sx <= sy
149.         LINE (cx - x, cy - y)-(cx + x, cy - y), c, BF
150.         LINE (cx - x, cy + y)-(cx + x, cy + y), c, BF
151.  
152.         DO
153.             x = x + 1
154.             sx = sx + b
155.             e = e + xx
156.             xx = xx + b
157.         LOOP UNTIL (e + e + yy) > 0
158.  
159.         y = y - 1
160.         sy = sy - a
161.         e = e + yy
162.         yy = yy + a
163.  
164.     LOOP
165.  
166. END SUB

NewCircleFill is as fast as the old version, or faster, on my machine.  I'm curious how it'll perform for other folks, on different systems, so kindly share results, if you don't mind.  :)

Title: Re: EllipseFill
Post by: bplus on November 03, 2018, 08:50:27 pm

Hi Steve,

The New Circle method is failing the alpha test with 1 overlapping line in upper and lower halves and it is being edged out by the old circle method in the long loop time test.

Amazingly the Ellipse Fill method is edging out the old gold standard circle fill method and still passing the alpha test.

Here is my test code, comment and uncomment as needed in method block and time report line:

Code: QB64: [Select]

1. DEFINT A-Z
2. SCREEN _NEWIMAGE(1220, 620, 32)
3. _SCREENMOVE 100, 20
4. _DELAY 1
5. FOR i = 0 TO 1000
6.     t = t + i
7. NEXT
8. 'who goes first might be disadvantage in time
9.  
10. 'comment out the one not being tested against the old circle method
11. 'start## = TIMER
12. 'CIRCLE (915, 305), 300, _RGBA32(100, 100, 100, 100), , , 1
13. 'NewCircleFill 915, 305, 300, _RGBA32(0, 100, 0, 100)
14. 'FOR i = 1 TO 10000
15. '    NewCircleFill 915, 305, 300, _RGBA32(0, 100, 0, 100)
16. 'NEXT
17. 'NewCircleTime## = TIMER - start##
18.  
19. start## = TIMER
20. CIRCLE (915, 305), 300, _RGBA32(100, 100, 100, 100), , , 1
21. EllipseFill 915, 305, 300, 300, _RGBA32(0, 100, 0, 100)
22. FOR i = 1 TO 10000
23.     EllipseFill 915, 305, 300, 300, _RGBA32(0, 100, 0, 100)
24. NEXT
25. EllipseTime## = TIMER - start##
26.  
27. ' ==================================================== compare to the old gold standard
28. start## = TIMER
29. CIRCLE (305, 305), 300, _RGBA32(100, 100, 100, 100), , , 1
30. CircleFill 305, 305, 300, _RGBA32(0, 100, 0, 100)
31. FOR i = 1 TO 10000
32.     CircleFill 305, 305, 300, _RGBA32(0, 100, 0, 100)
33. NEXT
34. OldCircleTime## = TIMER - start##
35.  
36. 'Comment out one of next 2 below
37.  
38. 'PRINT "Old circle time:"; OldCircleTime##; ", New circle time:"; NewCircleTime##
39.  
40. PRINT "Old circle time:"; OldCircleTime##; ", Ellipse fill time:"; EllipseTime##
41.  
42.  
43. 'old circle fill
44. SUB CircleFill (CX AS INTEGER, CY AS INTEGER, R AS INTEGER, C AS _UNSIGNED LONG)
45.     DIM Radius AS INTEGER, RadiusError AS INTEGER
46.     DIM X AS INTEGER, Y AS INTEGER
47.  
48.     Radius = ABS(R)
49.     RadiusError = -Radius
50.     X = Radius
51.     Y = 0
52.  
53.     IF Radius = 0 THEN PSET (CX, CY), C: EXIT SUB
54.  
55.     ' Draw the middle span here so we don't draw it twice in the main loop,
56.     ' which would be a problem with blending turned on.
57.     LINE (CX - X, CY)-(CX + X, CY), C, BF
58.  
59.     WHILE X > Y
60.         RadiusError = RadiusError + Y * 2 + 1
61.         IF RadiusError >= 0 THEN
62.             IF X <> Y + 1 THEN
63.                 LINE (CX - Y, CY - X)-(CX + Y, CY - X), C, BF
64.                 LINE (CX - Y, CY + X)-(CX + Y, CY + X), C, BF
65.             END IF
66.             X = X - 1
67.             RadiusError = RadiusError - X * 2
68.         END IF
69.         Y = Y + 1
70.         LINE (CX - X, CY - Y)-(CX + X, CY - Y), C, BF
71.         LINE (CX - X, CY + Y)-(CX + X, CY + Y), C, BF
72.     WEND
73.  
74. END SUB
75.  
76. SUB NewCircleFill (cx AS INTEGER, cy AS INTEGER, r AS INTEGER, c AS _UNSIGNED LONG)
77.     DIM x AS INTEGER
78.     DIM y AS INTEGER
79.     DIM e AS INTEGER
80.  
81.     x = r
82.     e = -x
83.  
84.     DO WHILE x >= y
85.         LINE (cx - x, cy - y)-(cx + x, cy - y), c, BF
86.         IF y <> 0 THEN LINE (cx - x, cy + y)-(cx + x, cy + y), c, BF
87.  
88.         y = y + 1
89.         e = e + y + y
90.         IF e > 0 THEN
91.             x = x - 1
92.             e = e - x - x
93.         END IF
94.     LOOP
95.     x = r
96.     e = -x
97.     y = 0
98.  
99.     DO WHILE x >= y
100.         LINE (cx - y, cy - x)-(cx + y, cy - x), c, BF
101.         LINE (cx - y, cy + x)-(cx + y, cy + x), c, BF
102.         DO
103.             y = y + 1
104.             e = e + y + y
105.         LOOP UNTIL e > 0
106.         x = x - 1
107.         e = e - x - x
108.     LOOP
109. END SUB
110.  
111. SUB EllipseFill (cx AS INTEGER, cy AS INTEGER, rx AS INTEGER, ry AS INTEGER, c AS _UNSIGNED LONG)
112.     DIM a AS LONG, b AS LONG
113.     DIM x AS LONG, y AS LONG
114.     DIM xx AS LONG, yy AS LONG
115.     DIM sx AS LONG, sy AS LONG
116.     DIM e AS LONG
117.  
118.     a = 2 * rx * rx
119.     b = 2 * ry * ry
120.     x = rx
121.     xx = ry * ry * (1 - rx - rx)
122.     yy = rx * rx
123.     sx = b * rx
124.  
125.     DO WHILE sx >= sy
126.         LINE (cx - x, cy - y)-(cx + x, cy - y), c, BF
127.         IF y <> 0 THEN LINE (cx - x, cy + y)-(cx + x, cy + y), c, BF
128.  
129.         y = y + 1
130.         sy = sy + a
131.         e = e + yy
132.         yy = yy + a
133.  
134.         IF (e + e + xx) > 0 THEN
135.             x = x - 1
136.             sx = sx - b
137.             e = e + xx
138.             xx = xx + b
139.         END IF
140.     LOOP
141.  
142.     x = 0
143.     y = ry
144.     xx = rx * ry
145.     yy = rx * rx * (1 - ry - ry)
146.     e = 0
147.     sx = 1
148.     sy = a * ry
149.  
150.     DO WHILE sx <= sy
151.         LINE (cx - x, cy - y)-(cx + x, cy - y), c, BF
152.         LINE (cx - x, cy + y)-(cx + x, cy + y), c, BF
153.  
154.         DO
155.             x = x + 1
156.             sx = sx + b
157.             e = e + xx
158.             xx = xx + b
159.         LOOP UNTIL (e + e + yy) > 0
160.  
161.         y = y - 1
162.         sy = sy - a
163.         e = e + yy
164.         yy = yy + a
165.  
166.     LOOP
167.  
168. END SUB
169.  
170.  

I first test one drawing of each for alpha test, then I run them through long loops of redrawing for timed test.

BTW, the first CIRCLE just draws a circle to compare border edges to QB64's circle.

Text Only | Text with Attachments