Author Topic: Seeking best ellipse fill function. (For everyone's sake.)  (Read 2163 times)

Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #60 on: February 11, 2019, 10:19:36 AM »
Current fill routine for reference.
Code: QB64 [Select]
  1. SUB FlatEllipseFill (ox AS INTEGER, oy AS INTEGER, a AS INTEGER, b AS INTEGER, col AS _UNSIGNED LONG)
  2. w2 = a * a
  3. h2 = b * b
  4. h2w2 = h2 * w2
  5. xi = a
  6. dx = 0
  7. LINE (ox - a, oy)-(ox + a, oy), col, BF
  8. FOR y = 1 TO b
  9.     FOR x = xi - dx + 1 TO 0 STEP -1
  10.         IF x * x * h2 + y * y * w2 <= h2w2 THEN EXIT FOR
  11.     NEXT
  12.     dx = xi - x
  13.     xi = x
  14.     LINE (ox - xi, oy + y)-(ox + xi, oy + y), col, BF
  15.     LINE (ox - xi, oy - y)-(ox + xi, oy - y), col, BF


IMO this is optimized for clarity:
Code: QB64 [Select]
  1. SUB fEllipse (CX AS LONG, CY AS LONG, xRadius AS LONG, yRadius AS LONG, c AS _UNSIGNED LONG)
  2.     DIM scale AS SINGLE, x AS LONG, y AS LONG
  3.     IF xRadius = 0 OR yRadius = 0 THEN EXIT SUB  '<<<<<<<<<<<<< really do need to skip out with 0
  4.     scale = yRadius / xRadius
  5.     LINE (CX, CY - yRadius)-(CX, CY + yRadius), c, BF
  6.     FOR x = 1 TO xRadius
  7.         y = scale * SQR(xRadius * xRadius - x * x)
  8.         LINE (CX + x, CY - y)-(CX + x, CY + y), c, BF
  9.         LINE (CX - x, CY - y)-(CX - x, CY + y), c, BF
  10.     NEXT

STxAxTIC begins to obscure but optimize for speed by going around using the sq root function with this substitution for SQR, reworking this line:
Code: QB64 [Select]
  1. y = scale * SQR(xRadius * xRadius - x * x)
  2.  
to this: (except he reworks for x not y)
Code: QB64 [Select]
  1.    
  2.     FOR x = xi - dx + 1 TO 0 STEP -1
  3.         IF x * x * h2 + y * y * w2 <= h2w2 THEN EXIT FOR
  4.     NEXT
  5.     dx = xi - x
  6.     xi = x
  7.  
Sorry, this would be clearer if I stuck to same variable names and now I see he is changing X's not Y's when drawing 2 lines.
All that to avoid using SQR, wow! That actually clears up that part of Steve's version for me, thanks.

And now, if he did it for octant instead of just quadrant, we would have something that looks like Steves code, after we also replaced the For loops with While loops since For loops are known to be slowest Loop structure.
« Last Edit: February 11, 2019, 10:35:27 AM by bplus »
B = B + ...

Offline Pete

  • Cuz I sez so, varmint!
Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #61 on: February 11, 2019, 10:57:38 AM »
Other C programmershave posted this avoid using SQR method online so there is probably some reason for it. My question would be since this project is based on time.... What limits performance the most; using SQR or going from LONG to DOUBLE variables?  In other words, would SQR with LONG be faster or slower than avoiding SQR and using LONG?

Now the one Steve dug up is interesting in that it draws the ellipse in two stages. The only way that could possibly be faster is if part of an ellipse (certain axis) can use fewer calculations; so you use a quicker formula to draw that part and finish it off with the more complex computations in the other part. The problem with that method, as posted, is the boob effect, as Bill puts it. That's some yet unidentified math problem, but seriously, unless that two stage method is faster by design, it should be pitched, rather than corrected, in favor of a single drawing algorithm.

Pete

Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #62 on: February 11, 2019, 11:19:08 AM »
bplus:
Quote
And now, if he did it for octant instead of just quadrant, we would have something that looks like Steves code, after we also replaced the For loops with While loops since For loops are known to be slowest Loop structure.

I was expecting FlatEllipseFill to run twice as long as CircleFill. Wrong! It is already running neck and neck with the proven CircleFill Routine!!!


I added the exit sub if either radius = 0 and I changed all the variables to LONG and I substituted the For loop with a While loop:
I am getting very nearly the same times, sometimes CircleFill faster, sometimes FlatEllipseFill:
Code: QB64 [Select]
  1. _TITLE "STATIC Ellipse Fill versus Steve Circle Fill"
  2. DEFINT A-Z
  3. SCREEN _NEWIMAGE(1220, 680, 32)
  4. _SCREENMOVE 100, 20
  5.  
  6. FlatEllipseFill 915, 305, 300, 300, _RGBA32(0, 100, 0, 40)
  7. FlatEllipseFill 915, 305, 300, 300, _RGBA32(0, 100, 0, 40)
  8. INPUT "EllipseFill (fel) overlap test, press enter to continue "; wate$
  9. LINE (0, 0)-(600, 20), _RGB32(0, 0, 0), BF
  10. start## = TIMER
  11. FOR i = 1 TO 10000
  12.     FlatEllipseFill 915, 305, 300, 300, _RGBA32(0, 100, 0, 100)
  13. EllipseTime## = TIMER - start##
  14. _PRINTSTRING (800, 615), "Time for 10000 EllipseFills:" + STR$(EllipseTime##)
  15.  
  16.  
  17. ' ==================================================== compare to the old gold standard
  18.  
  19. CircleFill 305, 305, 300, _RGBA32(0, 100, 0, 40)
  20. CircleFill 305, 305, 300, _RGBA32(0, 100, 0, 40)
  21. LOCATE 1, 1: INPUT "CircleFill overlap test, press enter to continue "; wate$
  22. LINE (0, 0)-(600, 20), _RGB32(0, 0, 0), BF
  23.  
  24. start## = TIMER
  25. FOR i = 1 TO 10000
  26.     CircleFill 305, 305, 300, _RGBA32(0, 100, 0, 100)
  27. OldCircleTime## = TIMER - start##
  28. _PRINTSTRING (200, 615), "Time for 10000 Circle Fills:" + STR$(OldCircleTime##)
  29.  
  30. 'old circle fill
  31. SUB CircleFill (CX AS INTEGER, CY AS INTEGER, R AS INTEGER, C AS _UNSIGNED LONG)
  32.     DIM Radius AS INTEGER, RadiusError AS INTEGER
  33.     DIM X AS INTEGER, Y AS INTEGER
  34.  
  35.     Radius = ABS(R)
  36.     RadiusError = -Radius
  37.     X = Radius
  38.     Y = 0
  39.  
  40.     IF Radius = 0 THEN PSET (CX, CY), C: EXIT SUB
  41.  
  42.     ' Draw the middle span here so we don't draw it twice in the main loop,
  43.     ' which would be a problem with blending turned on.
  44.     LINE (CX - X, CY)-(CX + X, CY), C, BF
  45.  
  46.     WHILE X > Y
  47.         RadiusError = RadiusError + Y * 2 + 1
  48.         IF RadiusError >= 0 THEN
  49.             IF X <> Y + 1 THEN
  50.                 LINE (CX - Y, CY - X)-(CX + Y, CY - X), C, BF
  51.                 LINE (CX - Y, CY + X)-(CX + Y, CY + X), C, BF
  52.             END IF
  53.             X = X - 1
  54.             RadiusError = RadiusError - X * 2
  55.         END IF
  56.         Y = Y + 1
  57.         LINE (CX - X, CY - Y)-(CX + X, CY - Y), C, BF
  58.         LINE (CX - X, CY + Y)-(CX + X, CY + Y), C, BF
  59.     WEND
  60.  
  61.  
  62. SUB FlatEllipseFill (ox AS LONG, oy AS LONG, a AS LONG, b AS LONG, col AS _UNSIGNED LONG)
  63.     DIM h2 AS LONG
  64.     DIM w2 AS LONG
  65.     DIM h2w2 AS LONG
  66.     DIM xi AS LONG
  67.     DIM dx AS LONG
  68.     DIM x AS LONG
  69.     DIM y AS LONG
  70.     IF a = 0 OR b = 0 THEN EXIT SUB ' B+ added this
  71.     w2 = a * a
  72.     h2 = b * b
  73.     h2w2 = h2 * w2
  74.     xi = a
  75.     dx = 0
  76.     LINE (ox - a, oy)-(ox + a, oy), col, BF
  77.     y = 0 ' B+ added this to eliminate FOR loop
  78.     WHILE y < b 'b+ no FOR loop
  79.         y = y + 1
  80.         FOR x = xi - dx + 1 TO 0 STEP -1
  81.             IF x * x * h2 + y * y * w2 <= h2w2 THEN EXIT FOR
  82.         NEXT
  83.         dx = xi - x
  84.         xi = x
  85.         LINE (ox - xi, oy + y)-(ox + xi, oy + y), col, BF
  86.         LINE (ox - xi, oy - y)-(ox + xi, oy - y), col, BF
  87.     WEND
  88.  
  89.  

So even CircleFill can be pitched as FlatEllipseFill could serve as both a Circle Fill and a Flat Ellipse Fill (as I was going to do with Steve's EllipseFill before the nipple problem was discovered).

Oh dang it, another For loop yet to go!
« Last Edit: February 11, 2019, 11:40:55 AM by bplus »
B = B + ...

Offline Pete

  • Cuz I sez so, varmint!
Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #63 on: February 11, 2019, 11:44:44 AM »
We already went over variable types that won't work. Just try this...

FlatEllipseFill 915, 305, 400, 200, _RGBA32(0, 100, 0, 40)

That's not an ellipse with variable types using LONG, but it becomes an ellipse if you use DOUBLE variable types. I haven't looked into the number results to see where the number results fail. I know Bill used LONG and INTEGER, which is too limited a type for this... but I just threw in DOUBLE everywhere, which is overkill. I decided to work on some of the numbers and post back...

Pete



« Last Edit: February 11, 2019, 12:21:49 PM by Pete »

Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #64 on: February 11, 2019, 12:04:40 PM »
We already went over LONG won't work. Just try this...

FlatEllipseFill 915, 305, 400, 200, _RGBA32(0, 100, 0, 40)

That's not an ellipse with LONG variable types, but it becomes an ellipse if you use DOUBLE variable types. I haven't looked into the number results to see where the number results fail. Hopefully, it's not some bug in QB64, but get this, 202, a larger number, works! I just don't have much patience when it comes to puzzles I guess, especially when I can skip right to a solution.

So if it is as fast using DOUBLE, great. If not, that's an issue. Maybe it can be fixed to use LONG by using SQR, or finding out what's wrong with LONG. I'll let you guys determine that, if you wish.

Pete

Sorry, missed that. It's probably the H2W2 number, squaring a square, say a = 400 b = 200 a^2 *b^2 = 6.4 x 10^9
but you say 202 works???
B = B + ...

Offline Pete

  • Cuz I sez so, varmint!
Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #65 on: February 11, 2019, 12:08:56 PM »
I just edited the post, because it was confusing.

I tried some work with the numbers and this seems to be working out so far...

DIM h2 AS DOUBLE
DIM w2 AS DOUBLE
DIM h2w2 AS DOUBLE
DIM xi AS INTEGER
DIM dx AS INTEGER
DIM x AS INTEGER
DIM y AS INTEGER

I don't need to use a variety of variable types in my work, so feel free to tear into this as needed. I may look into it a _bit more, too.

So far, so good. Running several simulations and it looks to be behaving. Apparently, only the right side of that equation needs to have DOUBLE as the variable type.

Pete
« Last Edit: February 11, 2019, 12:55:46 PM by Pete »

Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #66 on: February 11, 2019, 12:56:12 PM »
From experimenting with following, I think you have to type them all to cover the max value w2h2 can take:
Code: QB64 [Select]
  1. _TITLE "long type test"
  2. DIM test AS LONG, big AS _INTEGER64
  3. test = 100 'test olny made it to 215 ^ 4 !!!
  4. big = test * test * test * test
  5. WHILE big > 0 AND test < 1500
  6.     test = test + 1
  7.     big = test * test * test * test
  8. PRINT test, big, (test - 1) ^ 4
  9.  
  10.  
switch test from LONG type to _INTEGER64
« Last Edit: February 11, 2019, 12:57:25 PM by bplus »
B = B + ...

Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #67 on: February 11, 2019, 01:17:45 PM »
As Pete warned this code did pick up errors at certain a, b with everything LONG, but runs fine with everything at _INTEGER64:
Code: QB64 [Select]
  1. _TITLE "Flat Ellipse Fill (dimensions) test" 'edit: fix title
  2.  
  3. SCREEN _NEWIMAGE(1000, 700, 32)
  4. _SCREENMOVE 180, 20
  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 = 0 TO 350 'draw ellipse at various heights
  9.  
  10.     CLS
  11.     PRINT "b Radius"; i; "   press any to get to 400, <backspace> to go back one, <esc> for next test."
  12.  
  13.     FlatEllipseFill 500, 350, 400, i, _RGBA(255, 255, 255, 40)
  14.     'k$ = ""
  15.     'WHILE LEN(k$) = 0: k$ = INKEY$: WEND
  16.     'IF k$ = CHR$(8) THEN i = i - 2
  17.     'IF k$ = CHR$(27) THEN EXIT FOR
  18.     _DISPLAY
  19.     _LIMIT 5
  20.  
  21. FOR i = 0 TO 350 'draw ellipse at various heights
  22.  
  23.     CLS
  24.     PRINT "b Radius"; i; "   press any to get to 400, <backspace> to go back one, <esc> for next test."
  25.  
  26.     FlatEllipseFill 500, 350, i, 345, _RGBA(255, 255, 255, 40)
  27.     'k$ = ""
  28.     'WHILE LEN(k$) = 0: k$ = INKEY$: WEND
  29.     'IF k$ = CHR$(8) THEN i = i - 2
  30.     'IF k$ = CHR$(27) THEN EXIT FOR
  31.     _DISPLAY
  32.     _LIMIT 5
  33.  
  34.  
  35. WHILE _KEYDOWN(32) = 0 'check all sorts random stuff
  36.     FlatEllipseFill RND * 1000, RND * 700, RND * 100, RND * 100, _RGBA32(255 * RND, 255 * RND, 255 * RND, 100 * RND)
  37.     _DISPLAY
  38.     _LIMIT 1
  39.  
  40.  
  41. SUB FlatEllipseFill (ox AS _INTEGER64, oy AS _INTEGER64, a AS _INTEGER64, b AS _INTEGER64, col AS _UNSIGNED LONG)
  42.     DIM h2 AS _INTEGER64
  43.     DIM w2 AS _INTEGER64
  44.     DIM h2w2 AS _INTEGER64
  45.     DIM xi AS _INTEGER64
  46.     DIM dx AS _INTEGER64
  47.     DIM x AS _INTEGER64
  48.     DIM y AS _INTEGER64
  49.     IF a = 0 OR b = 0 THEN EXIT SUB ' B+ added this
  50.     w2 = a * a
  51.     h2 = b * b
  52.     h2w2 = h2 * w2
  53.     xi = a
  54.     dx = 0
  55.     LINE (ox - a, oy)-(ox + a, oy), col, BF
  56.     y = 0 ' B+ added this to eliminate FOR loop
  57.     WHILE y < b 'b+ no FOR loop
  58.         y = y + 1
  59.         x = xi - dx + 2
  60.         WHILE x >= 1
  61.             x = x - 1
  62.             IF x * x * h2 + y * y * w2 <= h2w2 THEN EXIT WHILE
  63.         WEND
  64.         dx = xi - x
  65.         xi = x
  66.         LINE (ox - xi, oy + y)-(ox + xi, oy + y), col, BF
  67.         LINE (ox - xi, oy - y)-(ox + xi, oy - y), col, BF
  68.     WEND
  69.  
  70.  

I confess a certain a bias to keeping everything out of float types.
« Last Edit: February 11, 2019, 01:20:12 PM by bplus »
B = B + ...

Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #68 on: February 11, 2019, 01:24:15 PM »
Flat Ellipse Fill with all variables at _INTEGER64 is still running neck and neck with Circle Fill, sometimes one or the other has the better time but Circle Fill has the lowest time that I've seen over many tests.

Code: QB64 [Select]
  1. _TITLE "STATIC Ellipse Fill versus Steve Circle Fill"
  2. DEFINT A-Z
  3. SCREEN _NEWIMAGE(1220, 680, 32)
  4. _SCREENMOVE 100, 20
  5.  
  6. FlatEllipseFill 915, 305, 300, 300, _RGBA32(0, 100, 0, 40)
  7. FlatEllipseFill 915, 305, 300, 300, _RGBA32(0, 100, 0, 40)
  8. INPUT "Flat EllipseFill overlap test, press enter to continue "; wate$
  9. LINE (0, 0)-(600, 20), _RGB32(0, 0, 0), BF
  10. start## = TIMER
  11. FOR i = 1 TO 10000
  12.     FlatEllipseFill 915, 305, 300, 300, _RGBA32(0, 100, 0, 100)
  13. EllipseTime## = TIMER - start##
  14. _PRINTSTRING (800, 615), "Time for 10000 Flat Ellipse Fills:" + STR$(EllipseTime##)
  15.  
  16.  
  17. ' ==================================================== compare to the old gold standard
  18.  
  19. CircleFill 305, 305, 300, _RGBA32(0, 100, 0, 40)
  20. CircleFill 305, 305, 300, _RGBA32(0, 100, 0, 40)
  21. LOCATE 1, 1: INPUT "CircleFill overlap test, press enter to continue "; wate$
  22. LINE (0, 0)-(600, 20), _RGB32(0, 0, 0), BF
  23.  
  24. start## = TIMER
  25. FOR i = 1 TO 10000
  26.     CircleFill 305, 305, 300, _RGBA32(0, 100, 0, 100)
  27. OldCircleTime## = TIMER - start##
  28. _PRINTSTRING (200, 615), "Time for 10000 Circle Fills:" + STR$(OldCircleTime##)
  29.  
  30. 'old circle fill
  31. SUB CircleFill (CX AS INTEGER, CY AS INTEGER, R AS INTEGER, C AS _UNSIGNED LONG)
  32.     DIM Radius AS INTEGER, RadiusError AS INTEGER
  33.     DIM X AS INTEGER, Y AS INTEGER
  34.  
  35.     Radius = ABS(R)
  36.     RadiusError = -Radius
  37.     X = Radius
  38.     Y = 0
  39.  
  40.     IF Radius = 0 THEN PSET (CX, CY), C: EXIT SUB
  41.  
  42.     ' Draw the middle span here so we don't draw it twice in the main loop,
  43.     ' which would be a problem with blending turned on.
  44.     LINE (CX - X, CY)-(CX + X, CY), C, BF
  45.  
  46.     WHILE X > Y
  47.         RadiusError = RadiusError + Y * 2 + 1
  48.         IF RadiusError >= 0 THEN
  49.             IF X <> Y + 1 THEN
  50.                 LINE (CX - Y, CY - X)-(CX + Y, CY - X), C, BF
  51.                 LINE (CX - Y, CY + X)-(CX + Y, CY + X), C, BF
  52.             END IF
  53.             X = X - 1
  54.             RadiusError = RadiusError - X * 2
  55.         END IF
  56.         Y = Y + 1
  57.         LINE (CX - X, CY - Y)-(CX + X, CY - Y), C, BF
  58.         LINE (CX - X, CY + Y)-(CX + X, CY + Y), C, BF
  59.     WEND
  60.  
  61.  
  62. SUB FlatEllipseFill (ox AS _INTEGER64, oy AS _INTEGER64, a AS _INTEGER64, b AS _INTEGER64, col AS _UNSIGNED LONG)
  63.     DIM h2 AS _INTEGER64
  64.     DIM w2 AS _INTEGER64
  65.     DIM h2w2 AS _INTEGER64
  66.     DIM xi AS _INTEGER64
  67.     DIM dx AS _INTEGER64
  68.     DIM x AS _INTEGER64
  69.     DIM y AS _INTEGER64
  70.     IF a = 0 OR b = 0 THEN EXIT SUB ' B+ added this
  71.     w2 = a * a
  72.     h2 = b * b
  73.     h2w2 = h2 * w2
  74.     xi = a
  75.     dx = 0
  76.     LINE (ox - a, oy)-(ox + a, oy), col, BF
  77.     y = 0 ' B+ added this to eliminate FOR loop
  78.     WHILE y < b 'b+ no FOR loop
  79.         y = y + 1
  80.         x = xi - dx + 2
  81.         WHILE x >= 1
  82.             x = x - 1
  83.             IF x * x * h2 + y * y * w2 <= h2w2 THEN EXIT WHILE
  84.         WEND
  85.         dx = xi - x
  86.         xi = x
  87.         LINE (ox - xi, oy + y)-(ox + xi, oy + y), col, BF
  88.         LINE (ox - xi, oy - y)-(ox + xi, oy - y), col, BF
  89.     WEND
  90.  
  91.  
B = B + ...

Offline Pete

  • Cuz I sez so, varmint!
Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #69 on: February 11, 2019, 01:47:32 PM »
Would using INTEGERS run any faster? My tests I've been running showed me that what I posted previously is true, that only the right side of that equation needed more range, so...

DIM xi AS _INTEGER64
DIM dx AS _INTEGER64
DIM x AS _INTEGER64
DIM y AS _INTEGER64

Could be changed to...

DIM xi AS INTEGER
DIM dx AS INTEGER
DIM x AS INTEGER
DIM y AS INTEGER

Yep, just tested some runs. So you could use...

DIM h2 AS _INTEGER64
DIM w2 AS _INTEGER64
DIM h2w2 AS _INTEGER64
DIM xi AS INTEGER
DIM dx AS INTEGER
DIM x AS INTEGER
DIM y AS INTEGER

In any event, it looks like we have something coming along that meets the requirements nicely. By we, I mean you guys. Sorry I can't be a bigger contributor here. This just isn't my area, but it's fun, and I managed to conjure up a couple of bug fixes.

Pete

Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #70 on: February 11, 2019, 06:22:51 PM »
Concerning optimizing Type Declarations, I think (or intuit) choosing the largest type needed to do and contain all calculations for all the variables involved and to specially avoid mixing float types with integer types.
B = B + ...

Offline STxAxTIC

  • Library Staff
  • Your mom would love me.
Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #71 on: February 11, 2019, 10:22:27 PM »
Ooookay where were we? First thought: a speed comparison between a raw circle fill versus an ellipse fill is somewhat of a foregone conclusion. Circles are the simplest shape in the universe, so they had better fill in quickly. Is there room for both functions in the new up-and-coming Toolbox? Hell yes, for two reasons: (i) the forum is empty right now and real estate over there is cheap, and (ii) people who still call them "ovals" probably never heard of ellipses, so those folks may be left wondering how to fill in their circles despite having glazed over a solution.

As an aside, it's lovely that the ellipse and circle-filling functions run at comparable speeds, so minimalists can just download an ellipse-filling routine and be done with the question.

After 5 forum pages I think we may have a few products. You guys are incredibly resilient for sticking to this.

Offline Pete

  • Cuz I sez so, varmint!
Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #72 on: February 12, 2019, 04:29:44 AM »
So here's what we have so far with two things I added/changed...

1) Added new variable to reduce equation steps: yyw2 = y * y * w2
2) Substituted DO/LOOP in place of FOR/LOOP for speed considerations.

Code: QB64 [Select]
  1. SCREEN _NEWIMAGE(1000, 700, 32)
  2.  
  3. FlatEllipseFill 500, 350, 350, 200, _RGBA(255, 255, 255, 40)
  4.  
  5. SUB FlatEllipseFill (ox AS INTEGER, oy AS INTEGER, a AS INTEGER, b AS INTEGER, col AS _UNSIGNED LONG)
  6. IF a = 0 OR b = 0 THEN EXIT SUB
  7. w2 = a * a
  8. h2 = b * b
  9. h2w2 = h2 * w2
  10. xi = a
  11. dx = 0
  12. y = 0
  13. LINE (ox - a, oy)-(ox + a, oy), col, BF
  14.     y = y + 1
  15.     yyw2 = y * y * w2
  16.     x = xi - dx + 1
  17.     DO
  18.         IF x * x * h2 + yyw2 <= h2w2 THEN EXIT DO
  19.         x = x - 1
  20.     LOOP
  21.     dx = xi - x
  22.     xi = x
  23.     LINE (ox - xi, oy + y)-(ox + xi, oy + y), col, BF
  24.     LINE (ox - xi, oy - y)-(ox + xi, oy - y), col, BF
  25. LOOP UNTIL y = b
  26.  

I don't think it is as elegant with these changes, but since speed is the goal, so be it.

A DO/LOOP actually requires one additional statement than a FOR/NEXT, but if you guys are sure it's still faster, it's all good this way. 

There might be some more optimization possible in these equations and this geometric progression looping approach. Maybe Steve could use his index approach to cut down the number of loops needed, but my guess would be the added conditional statements might add too much time and make it a push at best.

I posted a quick demo using this method at: https://www.tapatalk.com/groups/qbasic/viewtopic.php?f=648955&t=39432

Pete
« Last Edit: February 12, 2019, 05:09:53 AM by Pete »

Online SMcNeill

  • QB64 Developer
    • Steve’s QB64 Archive Forum
Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #73 on: February 12, 2019, 07:00:25 AM »
DO...LOOP is faster than FOR...NEXT just from the way they’re translated into C.  I’ll post a few simple examples in a different topic later, so as to not clutter up this one, but DO will always outperform FOR, from my experience.  (Only by a little, but when speed is the goal, each microsecond adds up.)
https://github.com/SteveMcNeill/Steve64 — A github collection of all things Steve!

Offline Pete

  • Cuz I sez so, varmint!
Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #74 on: February 12, 2019, 10:12:35 AM »
The thing Fell likes best about this thread is the KTMB Principle. (Keep the monkeys busy!)

Well, in terms of speed, should we be careful what we wish for, because if DO/LOOP is faster than FOR/NEXT, that's isn't so bad, but do you think GOTO could be faster, still?

Code: QB64 [Select]
  1. SCREEN _NEWIMAGE(1000, 700, 32)
  2.  
  3. FlatEllipseFill 500, 350, 350, 200, _RGBA(255, 255, 255, 40)
  4.  
  5. SUB FlatEllipseFill (ox AS INTEGER, oy AS INTEGER, a AS INTEGER, b AS INTEGER, col AS _UNSIGNED LONG)
  6. IF a = 0 OR b = 0 THEN EXIT SUB
  7. w2 = a * a
  8. h2 = b * b
  9. h2w2 = h2 * w2
  10. xi = a
  11. dx = 0
  12. y = 0
  13. LINE (ox - a, oy)-(ox + a, oy), col, BF
  14. 100
  15. y = y + 1
  16. yyw2 = y * y * w2
  17. x = xi - dx + 1
  18. 101
  19. IF x * x * h2 + yyw2 <= h2w2 THEN 102
  20. x = x - 1
  21. GOTO 101
  22. 102
  23. dx = xi - x
  24. xi = x
  25. LINE (ox - xi, oy + y)-(ox + xi, oy + y), col, BF
  26. LINE (ox - xi, oy - y)-(ox + xi, oy - y), col, BF
  27. IF y < b THEN 100
  28.