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

0 Members and 1 Guest are viewing this topic.

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1091
  • he lives
    • View Profile
Seeking best ellipse fill function. (For everyone's sake.)
« on: February 06, 2019, 06:46:38 pm »
Because I started the thread I'll set the standard. Criteria: Must be an ellipse, must not overdraw pixels so as to not confound transparency. The best function will do the same thing faster. Here I used some LINEs and a nice fat LINE ()-(), , BF to get the job done, but on another thread I used only one LINE in repetition. Not even sure if this is better yet...

(If you're wondering where the SQR2(2) factors come from, it's from calculus of variations. It turns out that the biggest rectangle that fits in a quarter-ellipse has dimensions a/sqr(2) by b/sqr(2), making my choice of LINE ()-(), , BF ideal if you're going to consider patching a rectangle in first...)

This makes me think wonder if the size of the ellipse you draw might have a bearing on which function fills it fastest, regarding line the BF method vs lots of skinny lines. Make sure any test you do accounts for this. (Test lots of sizes)

Code: QB64: [Select]
  1. SCREEN _NEWIMAGE(800, 600, 32)
  2.  
  3. CALL efill(50, 150, 80, 40, _RGBA(100, 200, 0, 100))
  4. CALL efill(70, 130, 80, 40, _RGBA(200, 100, 0, 100))
  5.  
  6. SUB efill (x0, y0, a, b, c AS LONG)
  7.     a2 = a / SQR(2)
  8.     b2 = b / SQR(2)
  9.     LINE (-a2 + _WIDTH / 2 + x0, -b2 + _HEIGHT / 2 - y0)-(a2 + _WIDTH / 2 + x0, b2 + _HEIGHT / 2 - y0), c, BF
  10.     LINE (0 + _WIDTH / 2 + x0, -b + _HEIGHT / 2 - y0)-(0 + _WIDTH / 2 + x0, -b2 - 1 + _HEIGHT / 2 - y0), c
  11.     LINE (0 + _WIDTH / 2 + x0, b + _HEIGHT / 2 - y0)-(0 + _WIDTH / 2 + x0, b2 + 1 + _HEIGHT / 2 - y0), c
  12.     LINE (-a + _WIDTH / 2 + x0, 0 + _HEIGHT / 2 - y0)-(-a2 - 1 + _WIDTH / 2 + x0, 0 + _HEIGHT / 2 - y0), c
  13.     LINE (a + _WIDTH / 2 + x0, 0 + _HEIGHT / 2 - y0)-(a2 + 1 + _WIDTH / 2 + x0, 0 + _HEIGHT / 2 - y0), c
  14.     FOR i = 1 TO a2
  15.         y1 = b * SQR(1 - i ^ 2 / a ^ 2)
  16.         LINE (i + _WIDTH / 2 + x0, -y1 + _HEIGHT / 2 - y0)-(i + _WIDTH / 2 + x0, -b2 - 1 + _HEIGHT / 2 - y0), c
  17.         LINE (-i + _WIDTH / 2 + x0, -y1 + _HEIGHT / 2 - y0)-(-i + _WIDTH / 2 + x0, -b2 - 1 + _HEIGHT / 2 - y0), c
  18.         LINE (i + _WIDTH / 2 + x0, b2 + 1 + _HEIGHT / 2 - y0)-(i + _WIDTH / 2 + x0, y1 + _HEIGHT / 2 - y0), c
  19.         LINE (-i + _WIDTH / 2 + x0, b2 + 1 + _HEIGHT / 2 - y0)-(-i + _WIDTH / 2 + x0, y1 + _HEIGHT / 2 - y0), c
  20.     NEXT
  21.     FOR j = 1 TO b2
  22.         x1 = a * SQR(1 - j ^ 2 / b ^ 2)
  23.         LINE (-x1 + _WIDTH / 2 + x0, j + _HEIGHT / 2 - y0)-(-a2 - 1 + _WIDTH / 2 + x0, j + _HEIGHT / 2 - y0), c
  24.         LINE (-x1 + _WIDTH / 2 + x0, -j + _HEIGHT / 2 - y0)-(-a2 - 1 + _WIDTH / 2 + x0, -j + _HEIGHT / 2 - y0), c
  25.         LINE (x1 + _WIDTH / 2 + x0, j + _HEIGHT / 2 - y0)-(a2 + 1 + _WIDTH / 2 + x0, j + _HEIGHT / 2 - y0), c
  26.         LINE (x1 + _WIDTH / 2 + x0, -j + _HEIGHT / 2 - y0)-(a2 + 1 + _WIDTH / 2 + x0, -j + _HEIGHT / 2 - y0), c
  27.     NEXT

EDIT

Out of the box, Steve's version (that either he or bplus will inevitably post) is twice as fast. I'm trying to figure if it has something to do with calls to SQR...
ellipse.png
* ellipse.png (Filesize: 1.08 KB, Dimensions: 260x140, Views: 688)
« Last Edit: February 06, 2019, 07:10:32 pm by STxAxTIC »
You're not done when it works, you're done when it's right.

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #1 on: February 06, 2019, 08:43:39 pm »
Because I started the thread I'll set the standard. Criteria: Must be an ellipse, must not overdraw pixels so as to not confound transparency. The best function will do the same thing faster. Here I used some LINEs and a nice fat LINE ()-(), , BF to get the job done, but on another thread I used only one LINE in repetition. Not even sure if this is better yet...

(If you're wondering where the SQR2(2) factors come from, it's from calculus of variations. It turns out that the biggest rectangle that fits in a quarter-ellipse has dimensions a/sqr(2) by b/sqr(2), making my choice of LINE ()-(), , BF ideal if you're going to consider patching a rectangle in first...)

This makes me think wonder if the size of the ellipse you draw might have a bearing on which function fills it fastest, regarding line the BF method vs lots of skinny lines. Make sure any test you do accounts for this. (Test lots of sizes)

Code: QB64: [Select]
  1. SCREEN _NEWIMAGE(800, 600, 32)
  2.  
  3. CALL efill(50, 150, 80, 40, _RGBA(100, 200, 0, 100))
  4. CALL efill(70, 130, 80, 40, _RGBA(200, 100, 0, 100))
  5.  
  6. SUB efill (x0, y0, a, b, c AS LONG)
  7.     a2 = a / SQR(2)
  8.     b2 = b / SQR(2)
  9.     LINE (-a2 + _WIDTH / 2 + x0, -b2 + _HEIGHT / 2 - y0)-(a2 + _WIDTH / 2 + x0, b2 + _HEIGHT / 2 - y0), c, BF
  10.     LINE (0 + _WIDTH / 2 + x0, -b + _HEIGHT / 2 - y0)-(0 + _WIDTH / 2 + x0, -b2 - 1 + _HEIGHT / 2 - y0), c
  11.     LINE (0 + _WIDTH / 2 + x0, b + _HEIGHT / 2 - y0)-(0 + _WIDTH / 2 + x0, b2 + 1 + _HEIGHT / 2 - y0), c
  12.     LINE (-a + _WIDTH / 2 + x0, 0 + _HEIGHT / 2 - y0)-(-a2 - 1 + _WIDTH / 2 + x0, 0 + _HEIGHT / 2 - y0), c
  13.     LINE (a + _WIDTH / 2 + x0, 0 + _HEIGHT / 2 - y0)-(a2 + 1 + _WIDTH / 2 + x0, 0 + _HEIGHT / 2 - y0), c
  14.     FOR i = 1 TO a2
  15.         y1 = b * SQR(1 - i ^ 2 / a ^ 2)
  16.         LINE (i + _WIDTH / 2 + x0, -y1 + _HEIGHT / 2 - y0)-(i + _WIDTH / 2 + x0, -b2 - 1 + _HEIGHT / 2 - y0), c
  17.         LINE (-i + _WIDTH / 2 + x0, -y1 + _HEIGHT / 2 - y0)-(-i + _WIDTH / 2 + x0, -b2 - 1 + _HEIGHT / 2 - y0), c
  18.         LINE (i + _WIDTH / 2 + x0, b2 + 1 + _HEIGHT / 2 - y0)-(i + _WIDTH / 2 + x0, y1 + _HEIGHT / 2 - y0), c
  19.         LINE (-i + _WIDTH / 2 + x0, b2 + 1 + _HEIGHT / 2 - y0)-(-i + _WIDTH / 2 + x0, y1 + _HEIGHT / 2 - y0), c
  20.     NEXT
  21.     FOR j = 1 TO b2
  22.         x1 = a * SQR(1 - j ^ 2 / b ^ 2)
  23.         LINE (-x1 + _WIDTH / 2 + x0, j + _HEIGHT / 2 - y0)-(-a2 - 1 + _WIDTH / 2 + x0, j + _HEIGHT / 2 - y0), c
  24.         LINE (-x1 + _WIDTH / 2 + x0, -j + _HEIGHT / 2 - y0)-(-a2 - 1 + _WIDTH / 2 + x0, -j + _HEIGHT / 2 - y0), c
  25.         LINE (x1 + _WIDTH / 2 + x0, j + _HEIGHT / 2 - y0)-(a2 + 1 + _WIDTH / 2 + x0, j + _HEIGHT / 2 - y0), c
  26.         LINE (x1 + _WIDTH / 2 + x0, -j + _HEIGHT / 2 - y0)-(a2 + 1 + _WIDTH / 2 + x0, -j + _HEIGHT / 2 - y0), c
  27.     NEXT

EDIT

Out of the box, Steve's version (that either he or bplus will inevitably post) is twice as fast. I'm trying to figure if it has something to do with calls to SQR...

Preliminary test question because the ellipse is not drawing where I think it should:
Why isn't your ellipse origin at x0, y0?
What are all the _WIDTH and _HEIGHT functions (constants?) doing in the code?
Can I assume a is the x radius and b the y radius?
Code: QB64: [Select]
  1. SCREEN _NEWIMAGE(800, 600, 32)
  2.  
  3.  
  4. CALL efill(50, 150, 80, 40, _RGBA(100, 200, 0, 100))
  5. CALL efill(70, 130, 80, 40, _RGBA(200, 100, 0, 100))
  6. CIRCLE (50, 150), 80, _RGB(255, 255, 255)
  7.  
  8. SUB efill (x0, y0, a, b, c AS LONG)
  9.     a2 = a / SQR(2)
  10.     b2 = b / SQR(2)
  11.     LINE (-a2 + _WIDTH / 2 + x0, -b2 + _HEIGHT / 2 - y0)-(a2 + _WIDTH / 2 + x0, b2 + _HEIGHT / 2 - y0), c, BF
  12.     LINE (0 + _WIDTH / 2 + x0, -b + _HEIGHT / 2 - y0)-(0 + _WIDTH / 2 + x0, -b2 - 1 + _HEIGHT / 2 - y0), c
  13.     LINE (0 + _WIDTH / 2 + x0, b + _HEIGHT / 2 - y0)-(0 + _WIDTH / 2 + x0, b2 + 1 + _HEIGHT / 2 - y0), c
  14.     LINE (-a + _WIDTH / 2 + x0, 0 + _HEIGHT / 2 - y0)-(-a2 - 1 + _WIDTH / 2 + x0, 0 + _HEIGHT / 2 - y0), c
  15.     LINE (a + _WIDTH / 2 + x0, 0 + _HEIGHT / 2 - y0)-(a2 + 1 + _WIDTH / 2 + x0, 0 + _HEIGHT / 2 - y0), c
  16.     FOR i = 1 TO a2
  17.         y1 = b * SQR(1 - i ^ 2 / a ^ 2)
  18.         LINE (i + _WIDTH / 2 + x0, -y1 + _HEIGHT / 2 - y0)-(i + _WIDTH / 2 + x0, -b2 - 1 + _HEIGHT / 2 - y0), c
  19.         LINE (-i + _WIDTH / 2 + x0, -y1 + _HEIGHT / 2 - y0)-(-i + _WIDTH / 2 + x0, -b2 - 1 + _HEIGHT / 2 - y0), c
  20.         LINE (i + _WIDTH / 2 + x0, b2 + 1 + _HEIGHT / 2 - y0)-(i + _WIDTH / 2 + x0, y1 + _HEIGHT / 2 - y0), c
  21.         LINE (-i + _WIDTH / 2 + x0, b2 + 1 + _HEIGHT / 2 - y0)-(-i + _WIDTH / 2 + x0, y1 + _HEIGHT / 2 - y0), c
  22.     NEXT
  23.     FOR j = 1 TO b2
  24.         x1 = a * SQR(1 - j ^ 2 / b ^ 2)
  25.         LINE (-x1 + _WIDTH / 2 + x0, j + _HEIGHT / 2 - y0)-(-a2 - 1 + _WIDTH / 2 + x0, j + _HEIGHT / 2 - y0), c
  26.         LINE (-x1 + _WIDTH / 2 + x0, -j + _HEIGHT / 2 - y0)-(-a2 - 1 + _WIDTH / 2 + x0, -j + _HEIGHT / 2 - y0), c
  27.         LINE (x1 + _WIDTH / 2 + x0, j + _HEIGHT / 2 - y0)-(a2 + 1 + _WIDTH / 2 + x0, j + _HEIGHT / 2 - y0), c
  28.         LINE (x1 + _WIDTH / 2 + x0, -j + _HEIGHT / 2 - y0)-(a2 + 1 + _WIDTH / 2 + x0, -j + _HEIGHT / 2 - y0), c
  29.     NEXT
  30.  
  31.  

As it stands I can not compare because it's not drawing where it should. Also I am seeing a line overlap in the EllipseFill test (Steve's).
wth(qm).PNG
* wth(qm).PNG (Filesize: 5.41 KB, Dimensions: 811x332, Views: 753)
« Last Edit: February 06, 2019, 08:57:56 pm by bplus »

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1091
  • he lives
    • View Profile
Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #2 on: February 06, 2019, 09:21:25 pm »
I put the origin in the center of screen and use normal Cartesian coordinates. The conversion does probably confound a speed test, so you have a point.

Steve's is gonna be faster - I finally did a web search on this and found what I sortof expected. You need to avoid square roots and trig when doing this stuff. Not sure where the inspiration where his code came from, but it likely won't be beat.
You're not done when it works, you're done when it's right.

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #3 on: February 06, 2019, 09:40:30 pm »
Did you find Bresenham?

This might or might not be Steve's?

My understanding is that instead of doing a Quadrant's worth of calculations, it only does an Octant's worth (at least for the Circle Fill version) and yes, avoid ^, trig and SQR functions helps too.
* Ellipse.pdf (Filesize: 172.33 KB, Downloads: 574)
« Last Edit: February 06, 2019, 09:45:58 pm by bplus »

Offline SMcNeill

  • QB64 Developer
  • Forum Resident
  • Posts: 3972
    • View Profile
    • Steve’s QB64 Archive Forum
Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #4 on: February 06, 2019, 11:25:10 pm »
Did you find Bresenham?

This might or might not be Steve's?

My understanding is that instead of doing a Quadrant's worth of calculations, it only does an Octant's worth (at least for the Circle Fill version) and yes, avoid ^, trig and SQR functions helps too.

As I mentioned when I shared it, I’m not 100% certain where my EllipseFill came from.  It was in an old untitled.bas file on my drive from SDL days, with a date-stamp years old.  I honestly don’t remember if I derived it from the CircleFill, or if it came from somewhere else.

I’m thinking it was probably inspired/derived from McIlroy's Ellipse Algorithm, or L. Patrick‘s work, but I won’t swear to anything.  Link here to read up on it a bit:  http://enchantia.com/graphapp/doc/tech/ellipses.html  The medication the quacks have me on for my heart fuddle my long-term memory and make it rather difficult for me to remember all the finer points of things, and I truly can’t say where EllipseFill floated into my possession from now.

It magically was on my drive, so the original author is unknown to me.  (It may have even been me; I don’t know.)  After I dug it up, I played around with it, noticed the similarities to CircleFill, and identified a few glitches.  Optimizing those out was entirely my own work, back in November, and it became as you see it now — a routine which can draw ellipses just as fast as we used to be able to draw circles.  ;)
https://github.com/SteveMcNeill/Steve64 — A github collection of all things Steve!

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #5 on: February 06, 2019, 11:55:25 pm »
Here is an update of EllipseFill versus CircleFill, they run neck and neck on 10000 large fills.
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.  
  7. EllipseFill 915, 305, 300, 300, _RGBA32(0, 100, 0, 40)
  8. EllipseFill 915, 305, 300, 300, _RGBA32(0, 100, 0, 40)
  9. INPUT "EllipseFill (fel) overlap test, press enter to continue "; wate$
  10. LINE (0, 0)-(600, 20), _RGB32(0, 0, 0), BF
  11. start## = TIMER
  12. FOR i = 1 TO 10000
  13.     EllipseFill 915, 305, 300, 300, _RGBA32(0, 100, 0, 100)
  14. EllipseTime## = TIMER - start##
  15. _PRINTSTRING (800, 615), "Time for 10000 EllipseFills:" + STR$(EllipseTime##)
  16.  
  17.  
  18. ' ==================================================== compare to the old gold standard
  19.  
  20. CircleFill 305, 305, 300, _RGBA32(0, 100, 0, 40)
  21. CircleFill 305, 305, 300, _RGBA32(0, 100, 0, 40)
  22. LOCATE 1, 1: INPUT "CircleFill overlap test, press enter to continue "; wate$
  23. LINE (0, 0)-(600, 20), _RGB32(0, 0, 0), BF
  24.  
  25. start## = TIMER
  26. FOR i = 1 TO 10000
  27.     CircleFill 305, 305, 300, _RGBA32(0, 100, 0, 100)
  28. OldCircleTime## = TIMER - start##
  29. _PRINTSTRING (200, 615), "Time for 10000 Circle Fills:" + STR$(OldCircleTime##)
  30.  
  31. 'old circle fill
  32. SUB CircleFill (CX AS INTEGER, CY AS INTEGER, R AS INTEGER, C AS _UNSIGNED LONG)
  33.     DIM Radius AS INTEGER, RadiusError AS INTEGER
  34.     DIM X AS INTEGER, Y AS INTEGER
  35.  
  36.     Radius = ABS(R)
  37.     RadiusError = -Radius
  38.     X = Radius
  39.     Y = 0
  40.  
  41.     IF Radius = 0 THEN PSET (CX, CY), C: EXIT SUB
  42.  
  43.     ' Draw the middle span here so we don't draw it twice in the main loop,
  44.     ' which would be a problem with blending turned on.
  45.     LINE (CX - X, CY)-(CX + X, CY), C, BF
  46.  
  47.     WHILE X > Y
  48.         RadiusError = RadiusError + Y * 2 + 1
  49.         IF RadiusError >= 0 THEN
  50.             IF X <> Y + 1 THEN
  51.                 LINE (CX - Y, CY - X)-(CX + Y, CY - X), C, BF
  52.                 LINE (CX - Y, CY + X)-(CX + Y, CY + X), C, BF
  53.             END IF
  54.             X = X - 1
  55.             RadiusError = RadiusError - X * 2
  56.         END IF
  57.         Y = Y + 1
  58.         LINE (CX - X, CY - Y)-(CX + X, CY - Y), C, BF
  59.         LINE (CX - X, CY + Y)-(CX + X, CY + Y), C, BF
  60.     WEND
  61.  
  62.  
  63. SUB EllipseFill (cx AS INTEGER, cy AS INTEGER, rx AS INTEGER, ry AS INTEGER, c AS _UNSIGNED LONG)
  64.     DIM a AS LONG, b AS LONG
  65.     DIM x AS LONG, y AS LONG
  66.     DIM xx AS LONG, yy AS LONG
  67.     DIM sx AS LONG, sy AS LONG
  68.     DIM e AS LONG
  69.  
  70.     a = 2 * rx * rx
  71.     b = 2 * ry * ry
  72.     x = rx
  73.     xx = ry * ry * (1 - rx - rx)
  74.     yy = rx * rx
  75.     sx = b * rx
  76.  
  77.     DO WHILE sx >= sy
  78.         LINE (cx - x, cy - y)-(cx + x, cy - y), c, BF
  79.         IF y <> 0 THEN LINE (cx - x, cy + y)-(cx + x, cy + y), c, BF
  80.  
  81.         y = y + 1
  82.         sy = sy + a
  83.         e = e + yy
  84.         yy = yy + a
  85.  
  86.         IF (e + e + xx) > 0 THEN
  87.             x = x - 1
  88.             sx = sx - b
  89.             e = e + xx
  90.             xx = xx + b
  91.         END IF
  92.     LOOP
  93.  
  94.     x = 0
  95.     y = ry
  96.     xx = rx * ry
  97.     yy = rx * rx * (1 - ry - ry)
  98.     e = 0
  99.     sx = 1
  100.     sy = a * ry
  101.  
  102.     DO WHILE sx <= sy
  103.         LINE (cx - x, cy - y)-(cx + x, cy - y), c, BF
  104.         LINE (cx - x, cy + y)-(cx + x, cy + y), c, BF
  105.  
  106.         DO
  107.             x = x + 1
  108.             sx = sx + b
  109.             e = e + xx
  110.             xx = xx + b
  111.         LOOP UNTIL (e + e + yy) > 0
  112.  
  113.         y = y - 1
  114.         sy = sy - a
  115.         e = e + yy
  116.         yy = yy + a
  117.  
  118.     LOOP
  119.  
  120.  
  121.  

Oddly Static's code was NOT doing that badly, I am not sure why, I just couldn't draw the darn thing where I wanted to really check if I had it setup correctly. If you draw half a 300 radius circle off screen would that cut the time in half?

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1091
  • he lives
    • View Profile
Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #6 on: February 07, 2019, 07:46:17 am »
Cool bplus, thanks for doing the legwork on this. Really appreciate it.

The reason I opened this thread in this way was to harvest our first bit of content for an upcoming new section on these forums. (This will be formally "announced" later.) The new section will be like Samples Lite: not quite full-fledged demos, but instead we will collect functions and libraries that do one thing extremely well without the user having to learn anything about the code. A pure collection of black boxes, if possible.
« Last Edit: February 07, 2019, 07:48:10 am by STxAxTIC »
You're not done when it works, you're done when it's right.

Offline _vince

  • Seasoned Forum Regular
  • Posts: 422
    • View Profile
Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #7 on: February 08, 2019, 01:24:09 pm »
It magically was on my drive, so the original author is unknown to me.  (It may have even been me; I don’t know.)  After I dug it up, I played around with it, noticed the similarities to CircleFill, and identified a few glitches.  Optimizing those out was entirely my own work, back in November, and it became as you see it now — a routine which can draw ellipses just as fast as we used to be able to draw circles.  ;)

maybe this will jog your memory:
Code: QB64: [Select]
  1.         IF (e + e + xx) > 0 THEN
  2.     yy = rx * rx * (1 - ry - ry)
  3.  

why are you using e + e instead of 2*e or -ry - ry instead of -2*ry? Can we learn more about these advanced optimization techniques?

Offline SMcNeill

  • QB64 Developer
  • Forum Resident
  • Posts: 3972
    • View Profile
    • Steve’s QB64 Archive Forum
Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #8 on: February 08, 2019, 03:20:10 pm »
It magically was on my drive, so the original author is unknown to me.  (It may have even been me; I don’t know.)  After I dug it up, I played around with it, noticed the similarities to CircleFill, and identified a few glitches.  Optimizing those out was entirely my own work, back in November, and it became as you see it now — a routine which can draw ellipses just as fast as we used to be able to draw circles.  ;)

maybe this will jog your memory:
Code: QB64: [Select]
  1.         IF (e + e + xx) > 0 THEN
  2.     yy = rx * rx * (1 - ry - ry)
  3.  

why are you using e + e instead of 2*e or -ry - ry instead of -2*ry? Can we learn more about these advanced optimization techniques?

Run a speed test sometime and compare speed of operations.

x * x is faster than x ^ 2.
x + x is faster than 2 * x.
-x is MUCH faster than -1 * x.  (Negation vs negative multiplication)

UnseenMachine and I used to have a topic over at [abandoned, outdated and now likely malicious qb64 dot net website - don’t go there] which discussed operational optimization techniques, but unfortunately, .net seems to be forever lost to time now.

A few other pointers, off the top of my head: 
DO.. LOOP is faster than FOR...NEXT.

Assignment to an integer variable is faster than INT.   (DIM x AS INTEGER: x = 3.2 is faster than x! = INT(3.2)

Try to limit REDIM _PRESERVE calls as much as possible.

Instead of:
DO
   count = count + 1
   REDIM _PRESERVE Array(UBOUND(Array) + 1)
   ‘do stuff
LOOP

Do:
REDIM _PRESERVE Array(UBOUND(Array) + 10000)
DO
    count = count + 1
    IF count > UBOUND(Array) THEN REDIM _PRESERVE Array(UBOUND(Array) + 10000)
    ‘Do stuff
LOOP
   REDIM _PRESERVE ARRAY(count) ‘remove unneeded Array space..



Just lots of little things like these throughout years of time testing and experience, are what I use to optimize performance.
https://github.com/SteveMcNeill/Steve64 — A github collection of all things Steve!

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1091
  • he lives
    • View Profile
Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #9 on: February 09, 2019, 06:39:23 pm »
Alright, here are two functions that draw filled tilted ellipses. One suffers from a serious aliasing problem due to drawing diagonal lines. I wonder if (i) all languages would do this, or (ii) it's something in opengl, (iii) it's not opengl inherently, but Galleon's effort to make graphics modes compatible with old behavior (this is prolly it). The second function cheats using PAINT. Anyway, have a ball.

Code: QB64: [Select]
  1.  
  2. DIM SHARED CenterX
  3. DIM SHARED CenterY
  4. CenterX = _WIDTH / 2
  5. CenterY = _HEIGHT / 2
  6.  
  7. FOR k = 0 TO 3.14 * 2 + .01 STEP .01
  8.     CLS
  9.     CALL TiltedEllipseFill1(100, 100, 100, 60, k)
  10.     CALL TiltedEllipseFill2(-100, -100, 100, 60, k)
  11.     _LIMIT 20
  12.     _DISPLAY
  13.  
  14.  
  15. SUB TiltedEllipseFill1 (x0, y0, a, b, ang)
  16.     FOR i = -a TO a
  17.         yy = b * SQR(1 - i ^ 2 / a ^ 2)
  18.         x1 = i
  19.         x2 = i
  20.         y1 = yy
  21.         y2 = -yy
  22.         x1i = x1
  23.         x2i = x2
  24.         y1i = y1
  25.         y2i = y2
  26.         x1 = (x1i) * COS(ang) - (y1i) * SIN(ang)
  27.         y1 = (x1i) * SIN(ang) + (y1i) * COS(ang)
  28.         x2 = (x2i) * COS(ang) - (y2i) * SIN(ang)
  29.         y2 = (x2i) * SIN(ang) + (y2i) * COS(ang)
  30.         x1 = x1 + x0 + CenterX
  31.         x2 = x2 + x0 + CenterX
  32.         y1 = -y1 - y0 + CenterY
  33.         y2 = -y2 - y0 + CenterY
  34.         LINE (x1, y1)-(x2, y2), 4
  35.     NEXT
  36.  
  37. SUB TiltedEllipseFill2 (x0, y0, a, b, ang)
  38.     FOR k = 0 TO 2 * 3.14 + .1 STEP .1
  39.         i = a * COS(k) * COS(ang) + b * SIN(k) * SIN(ang)
  40.         j = -a * COS(k) * SIN(ang) + b * SIN(k) * COS(ang)
  41.         i = i + x0 + CenterX
  42.         j = -j - y0 + CenterY
  43.         IF k <> 0 THEN
  44.             LINE -(i, j), 5
  45.         ELSE
  46.             PSET (i, j), 5
  47.         END IF
  48.     NEXT
  49.     PAINT (x0 + CenterX, -y0 + CenterY), 5, 5
  50.  
« Last Edit: February 09, 2019, 06:42:20 pm by STxAxTIC »
You're not done when it works, you're done when it's right.

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #10 on: February 09, 2019, 07:25:28 pm »
Hey STATIC,

Kudos for being first with code for tilted ellipse.

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1091
  • he lives
    • View Profile
Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #11 on: February 09, 2019, 08:05:53 pm »
Thanks bplus!

I think in practice, the second function (Without the alias problem) will be the keeper. Since it relies on PAINT for filling, it has to be its own image or whatever if we want to place it over other shapes, of course.

Just so it's all in one place, here is the derivation of the equations in the second function. Vectors are in bold.

(1)
Recall that an un-tilted ellipse with major and minor axes a, b, respectively, centered at the point (0, 0) can be represented by a vector r0 and an angular parameter q, namely

r0 = i a cos(q) + j b sin (q) ,

where unit vectors i = (1, 0) and j = (0, 1) align with the horizontal and vertical directions, respectively.

(As a quick aside, it's trivial to eliminate the parameter q in the above to arrive at (x/a)^2 + (y/b)^2 = 1.)

(2)
It must follow that a tilted ellipse aligns with a different pair of unit vectors u and v in place of i and j. Whatever u and v are, the tilted ellipse obeys:

r = u a cos(q) + v b sin (q)

(3)
The next task is to determine u and v in terms of i and j. For i and j to "swing into" u and v across angle w, we apply a rotation matrix as follows:

u = i cos(w) - j sin(w)
v = i sin(w) + j cos(w)

(4)
Plugging the new equations for u and v into r, we find:

r = (i cos(w) - j sin(w)) a cos(q) + (i sin(w) + j cos(w)) b sin(q)

r = i (a cos(q) cos(w) + b sin (q) sin(w)) + j (-a cos(q)sin(w) + b sin(q) sin(w))

(5)
Isolate the i and j components to finally land at equations for x and y

x = a cos(q) cos(w) + b sin (q) sin(w)
y = -a cos(q)sin(w) + b sin(q) sin(w)


... and these are precisely what are implemented in the code (which uses slightly different notation)

Code: QB64: [Select]
  1. ... = a * COS(k) * COS(ang) + b * SIN(k) * SIN(ang)
  2. ... = -a * COS(k) * SIN(ang) + b * SIN(k) * COS(ang)
  3.  
« Last Edit: February 09, 2019, 08:16:38 pm by STxAxTIC »
You're not done when it works, you're done when it's right.

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #12 on: February 09, 2019, 08:16:33 pm »
And as I learned early on in QB64 forum, you can draw your ellipse in an isolated _DEST and transfer the image to wherever needed without concern of PAINT running into other objects. (Yeah, you said that ;-)) ) Problem is, PAINT is slow for circle filling.

I still think we need a sub that is not dependent upon knowing where the center of the screen is.
« Last Edit: February 09, 2019, 08:27:45 pm by bplus »

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1091
  • he lives
    • View Profile
Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #13 on: February 09, 2019, 08:21:43 pm »
I figured PAINT would be slow... but then again it needs four trig calls, so it was never destined to be lightning. One possible avenue that remains is to do a similar analysis that led to Steve's code, and then generalize it for tilted shapes. I see this going nowhere unfortunately, simply because (i) you might have to draw diagonals and suffer the same alias problem as my first method, and then (ii) I haven't been able to attain a parameter-free expression for the ellipse that is strictly an XY equation. Not that it's *required*, but would be very hand for making a fast function. I truly doubt such an equation exists after a few hours of mucking around in equation-land.
« Last Edit: February 09, 2019, 08:32:12 pm by STxAxTIC »
You're not done when it works, you're done when it's right.

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Seeking best ellipse fill function. (For everyone's sake.)
« Reply #14 on: February 09, 2019, 09:35:28 pm »
I have modified the tiltedEllispeFill2 sub to be used without needing the center of screen and setup in a separate destination and transferred to destHandle& with _PUTIMAGE.

Another problem with PAINT is that it does not do Alpha (at least as a boundry).
Another problem with PAINT is very narrow ellipse:
Code: QB64: [Select]
  1. _TITLE "Tilted Ellipse test"
  2. SCREEN _NEWIMAGE(800, 600, 32)
  3. clr = _RGB32(255, 128, 64)
  4. TiltedEllipseFill2 0, 400, 300, 300, 200, _PI(1 / 4), clr
  5. CIRCLE (400, 300), 300
  6. CIRCLE (400, 300), 200
  7. INPUT "Hopefully the ellipse radii fits in both circles, press enter..."; wate$
  8. WHILE _KEYDOWN(27) = 0
  9.     TiltedEllipseFill2 0, RND * 600 + 100, RND * 400 + 100, RND * 100 + 1, RND * 100 + 1, _PI(RND * 2), _RGB32(RND * 255, RND * 255, RND * 255)
  10.     _DISPLAY
  11.     _LIMIT 10
  12.  
  13. SUB TiltedEllipseFill2 (destHandle&, x0, y0, a, b, ang, c AS _UNSIGNED LONG)
  14.     IF a > b THEN max = a + 1 ELSE max = b + 1
  15.     tef& = _NEWIMAGE(2 * max, 2 * max)
  16.     _DEST tef&
  17.     FOR k = 0 TO 2 * 3.14 + .1 STEP .1
  18.         i = max + a * COS(k) * COS(ang) + b * SIN(k) * SIN(ang)
  19.         j = max - a * COS(k) * SIN(ang) + b * SIN(k) * COS(ang)
  20.         IF k <> 0 THEN
  21.             LINE (lasti, lastj)-(i, j), c
  22.         ELSE
  23.             PSET (i, j), c
  24.         END IF
  25.         lasti = i: lastj = j
  26.     NEXT
  27.     PAINT (max, max), c
  28.     _PUTIMAGE (x0 - max, y0 - max)-STEP(2 * max, 2 * max), tef&, destHamdle&
  29.     _FREEIMAGE tef&
  30.  
test ellipse code 1.PNG

 
Test ellipse code 2.PNG
« Last Edit: February 09, 2019, 09:46:59 pm by bplus »