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

[_vince]

further optimized version of steve's amazing algorithm ;-)
comment out the last line in the sub ;-)

Code: QB64: [Select]

1. sub ellipsef(x0, y0, rx, ry, c)
2.     a = 2*rx*rx
3.     b = 2*ry*ry
4.    
5.    
6.     x = 0
7.     y = ry
8.     dx = ry*ry
9.     dy = rx*rx*(1 - 2*ry)
10.     e = 0
11.     sx = 0
12.     sy = a*ry
13.    
14.     do while sx <= sy
15.         line (x0 - x, y0 + y)-step(2*x, 0),c,bf
16.         line (x0 - x, y0 - y)-step(2*x, 0),c,bf
17.        
18.         x = x + 1
19.         sx = sx + b
20.         e = e + dx
21.         dx = dx + b
22.        
23.         if 2*e + dy > 0 then
24.             y = y - 1
25.             sy = sy - a
26.             e = e + dy
27.             dy = dy + a
28.         end if
29.     loop
30.    
31.     x1 = x0 - x
32.     x2 = x0 + x
33.     y1 = y0 - y
34.    
35.     x = rx
36.     y = 0
37.     dx = ry*ry*(1 - 2*rx)
38.     dy = rx*rx
39.     e = 0
40.     sx = b*rx
41.     sy = 0
42.    
43.     x3 = x0 - x
44.    
45.     do while sx >= sy
46.         line (x0 - x, y0 + y)-(x1, y0 + y),c,bf
47.         line (x0 - x, y0 - y)-(x1, y0 - y),c,bf
48.         line (x0 + x, y0 + y)-(x2, y0 + y),c,bf
49.         line (x0 + x, y0 - y)-(x2, y0 - y),c,bf
50.        
51.         y = y + 1
52.         sy = sy + a
53.         e = e + dy
54.         dy = dy + a
55.        
56.         if 2*e + dx > 0 then
57.             x = x - 1    
58.             sx = sx - b
59.             e = e + dx
60.             dx = dx + b
61.         end if
62.     loop
63.    
64.     line (x1, y1)-(x2,y0 + y),c,bf  
65.    
66. end sub
67.  

[bplus]

Pete, you want to draw something even if a or b is 0?

Vince, does your version take care of the nipple problem?

[Pete]

I'll have to see what Vince posted in a minute, but right now this new one we are working on had me wondering why we need that inner loop at all. I mean why not just solve for x algebraically?

x = INT(SQR((h2w2 - yyw2) / h2))

I'll post back with an example, soon...

Pete

[Pete]

Well, it worked for one run. Now I have to test it with multiple sizes...

MODIFIED SINGLE LOOP ELLIPSE FILL SUB ROUTINE. (Solved algebraically.)

Code: QB64: [Select]

1. SCREEN _NEWIMAGE(1000, 700, 32)
2. _SCREENMOVE 180, 0
3.  
4. FlatEllipseFill 500, 350, 350, 200, _RGBA(255, 255, 255, 40)
5.  
6. SUB FlatEllipseFill (ox AS INTEGER, oy AS INTEGER, a AS INTEGER, b AS INTEGER, col AS _UNSIGNED LONG)
7. IF a = 0 OR b = 0 THEN EXIT SUB
8. DIM h2 AS _INTEGER64
9. DIM w2 AS _INTEGER64
10. DIM h2w2 AS _INTEGER64
11. DIM yyw2 AS _INTEGER64
12. DIM xi AS INTEGER
13. DIM x AS INTEGER
14. DIM y AS INTEGER
15. w2 = a * a
16. h2 = b * b
17. h2w2 = h2 * w2
18. x = a
19. y = 0
20. LINE (ox - a, oy)-(ox + a, oy), col, BF
21. 100
22. y = y + 1
23. yyw2 = y * y * w2
24. x = INT(SQR((h2w2 - yyw2) / h2))
25. LINE (ox - x, oy + y)-(ox + x, oy + y), col, BF
26. LINE (ox - x, oy - y)-(ox + x, oy - y), col, BF
27. IF y < b THEN 100
28. END SUB
29.  

So we also got rid of some lines by removing unnecessary loop variables. I just left the GOTO part in this one. It can easily be swapped out for DO/LOOP if GOTO isn't faster.

Pete

Edit: Yea! It works!

[bplus]

further optimized version of steve's amazing algorithm ;-)
comment out the last line in the sub ;-)

Code: QB64: [Select]

1. sub ellipsef(x0, y0, rx, ry, c)
2.     a = 2*rx*rx
3.     b = 2*ry*ry
4.    
5.    
6.     x = 0
7.     y = ry
8.     dx = ry*ry
9.     dy = rx*rx*(1 - 2*ry)
10.     e = 0
11.     sx = 0
12.     sy = a*ry
13.    
14.     do while sx <= sy
15.         line (x0 - x, y0 + y)-step(2*x, 0),c,bf
16.         line (x0 - x, y0 - y)-step(2*x, 0),c,bf
17.        
18.         x = x + 1
19.         sx = sx + b
20.         e = e + dx
21.         dx = dx + b
22.        
23.         if 2*e + dy > 0 then
24.             y = y - 1
25.             sy = sy - a
26.             e = e + dy
27.             dy = dy + a
28.         end if
29.     loop
30.    
31.     x1 = x0 - x
32.     x2 = x0 + x
33.     y1 = y0 - y
34.    
35.     x = rx
36.     y = 0
37.     dx = ry*ry*(1 - 2*rx)
38.     dy = rx*rx
39.     e = 0
40.     sx = b*rx
41.     sy = 0
42.    
43.     x3 = x0 - x
44.    
45.     do while sx >= sy
46.         line (x0 - x, y0 + y)-(x1, y0 + y),c,bf
47.         line (x0 - x, y0 - y)-(x1, y0 - y),c,bf
48.         line (x0 + x, y0 + y)-(x2, y0 + y),c,bf
49.         line (x0 + x, y0 - y)-(x2, y0 - y),c,bf
50.        
51.         y = y + 1
52.         sy = sy + a
53.         e = e + dy
54.         dy = dy + a
55.        
56.         if 2*e + dx > 0 then
57.             x = x - 1    
58.             sx = sx - b
59.             e = e + dx
60.             dx = dx + b
61.         end if
62.     loop
63.    
64.     line (x1, y1)-(x2,y0 + y),c,bf  
65.    
66. end sub
67.  

Yikes! Vince, here is my overlap test of your code (with last line in sub commented out)

[_vince]

The idea is there, a single LINE BF is going to be much faster than manually filling all of that in.  I'd need to review Steve's derivation notes to fix the overlap issue

[Pete]

Hi Mark,

Did you see the one I just posted? I think I figured out a way to optimize it so we lose that inner loop and a couple of variables and lines.

Oh, even in the earlier versions I posted, I did take into consideration your don't draw it if height and/or width is zero. This line exits the sub routine if that happens...

IF a = 0 OR b = 0 THEN EXIT SUB

So yes, that is handled.

What I'm looking at now is a way to bypass multiple DIM reads when more than one ellipse is built in a routine...

Pete

[bplus]

Hi Mark,

Did you see the one I just posted? I think I figured out a way to optimize it so we lose that inner loop and a couple of variables and lines.

Oh, even in the earlier versions I posted, I did take into consideration your don't draw it if height and/or width is zero. This line exits the sub routine if that happens...

IF a = 0 OR b = 0 THEN EXIT SUB

So yes, that is handled.

What I'm looking at now is a way to bypass multiple DIM reads when more than one ellipse is built in a routine...

Pete

Yes, I ran a timed test on it and was shocked! Even with BOTH the extra SQR AND INT functions it was comparable to the old Gold Standard Circle Fill. ;-)) Is the INT function needed?

Append:

Code: QB64: [Select]

1. IF a = 0 OR b = 0 THEN EXIT SUB

Oh! I see it now, the first line, sorry, I was expecting it after DIM statements.

[Pete]

I just edited (cleaned it up a bit) while you were posting. I'm still checking some things with the DIM statements to work around multiple calls. I'll post that version, soon.

This integral calculus stuff is fun. It takes me back to when I was a kid in school. Ah, to be 7 again! :D :D :D

Pete

OK, edited back to this thread to post the latest. A bit more cleaned up and it only goes through the DIM list once, so those statements won't be used again for multiple ellipse fills.

Code: QB64: [Select]

1. SCREEN _NEWIMAGE(1000, 700, 32)
2. _SCREENMOVE 180, 0
3.  
4. FOR i = 1 TO 350
5.     CLS
6.     PRINT "Width = 350 Height ="; i; " Press a key to expand height..."
7.     FlatEllipseFill 500, 350, 350, i, _RGBA(255, 255, 255, 40)
8.     _DISPLAY
9.     SLEEP
10. NEXT
11.  
12. SUB FlatEllipseFill (ox AS INTEGER, oy AS INTEGER, a AS INTEGER, b AS INTEGER, col AS _UNSIGNED LONG)
13. IF a = 0 OR b = 0 THEN EXIT SUB
14. STATIC pete
15. IF pete = 0 THEN
16.     pete = -1
17.     DIM h2 AS _INTEGER64
18.     DIM w2 AS _INTEGER64
19.     DIM h2w2 AS _INTEGER64
20.     DIM yyw2 AS _INTEGER64
21.     DIM x AS INTEGER
22.     DIM y AS INTEGER
23. END IF
24. w2 = a * a
25. h2 = b * b
26. h2w2 = h2 * w2
27. x = a
28. y = 0
29. LINE (ox - a, oy)-(ox + a, oy), col, BF
30. 100
31. y = y + 1
32. yyw2 = y * y * w2
33. x = SQR((h2w2 - yyw2) / h2)
34. LINE (ox - x, oy + y)-(ox + x, oy + y), col, BF
35. LINE (ox - x, oy - y)-(ox + x, oy - y), col, BF
36. IF y < b THEN 100
37. END SUB
38.  

I still think there might be some more equation optimization that could be achieved here, but maybe it is as cooked as it can get. Anyway, it is getting better!

[bplus]

Pete, at 1000 redraws of 300 radius circle the times are exactly the same but when I test 10000 then the CircleFilled routine consistently out paces the FlatEllipseFill routine. I did remove INT function and have yet to test overlap on all different sizes a, b.

[Pete]

Try the one in my last post. It bypasses reading DIMs after the first time, which should speed up results. If it still isn't faster, wow, could the progressive loops be faster than the square root calculation? That would be weird.

Pete

[SMcNeill]

Try the one in my last post. It bypasses reading DIMs after the first time, which should speed up results. If it still isn't faster, wow, could the progressive loops be faster than the square root calculation? That would be weird.

Pete

Reading DIMs aren’t an issue as they’re more QB64-side than C-translated side.  Your compiled program won’t really notice a difference.  ;)

[Pete]

Reading DIMs aren’t an issue as they’re more QB64-side than C-translated side.  Your compiled program won’t really notice a difference.  ;)

Well that bypass routine can be removed then. Now unless there is a way of changing the SQR calculation, I think I'm at an end point on this one. OMG, wait a minute, if we don't need the DIM bypass, that means we have to pitch the variable "pete" which is used to bypass the DIM statements. You ***tard! :D

DIM Pete as _PISSED_OFFSET

Anyway guys, which do you think will win out in a speed test, GOTO or DO/LOOP? I hope they are the same or DO/LOOP wins. GOTO is just too ugly to put in a function.

Final thought. You know the y = 0 is not needed, but I've kept it there for something we need to discuss if this or any of these submissions becomes part of the tool box, we need to come up with variable names unique to the function. The ones we are playing around with here could easily intefer with other coders global variables.

Pete

[bplus]

Reading DIMs aren’t an issue as they’re more QB64-side than C-translated side.  Your compiled program won’t really notice a difference.  ;)

Anyway, what do you guys think GOTO vs DO/LOOP will win out in a speed test?

I did test that one time and GOTO had no advantage and might have been slower.

Code: QB64: [Select]

1. DEFLNG A-Z
2. PRINT "Running 2 timed tests please wait..."
3.  
4. n = 1000000000
5.  
6. t! = TIMER
7. x = 0: i = 0
8. doloop:
9. i = i + 1
10. x = x + i
11. IF i < n THEN GOTO doloop
12. t2! = TIMER
13.  
14. x = 0: i = 0
15. WHILE i < n
16.     i = i + 1
17.     x = x + i
18. WEND
19. t3! = TIMER
20. PRINT n; " times adding in While... Wend time is "; t3! - t2!
21. PRINT n; "     times adding in GOTO loop time is "; t2! - t!
22.  
23.  

[SMcNeill]

Code: QB64: [Select]

1. STATIC pete
2. IF pete = 0 THEN
3.     pete = -1
4.     DIM h2 AS _INTEGER64
5.     DIM w2 AS _INTEGER64
6.     DIM h2w2 AS _INTEGER64
7.     DIM yyw2 AS _INTEGER64
8.     DIM x AS INTEGER
9.     DIM y AS INTEGER
10. END IF

The above may not be useful, but the concept behind it holds promise...

Perhaps the following can make a speed difference:

STATIC h2 AS _INTEGER64
STATIC w2 AS _INTEGER64

And so on...

The idea is to not initialize/free temp variables, speeding the overall process up as much as possible.  Just be careful not to reuse values between SUB calls.