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

[STxAxTIC]

There's always an edge case I guess.

Welp, it turns out that the off-circle-ness is called the eccentricity, given by e=sqrt(1-b^2/a^2), where circles have e=0. In practice with this function, the programmer should rethink what he's doing if looking to apply this function to very eccentric shapes that are fussy down to the pixel.

[STxAxTIC]

... With all of the above said, do we all agree that:

(i) The code Steve brought to the table is the best flat ellipse fill
(ii) Bplus's mod to my tilted ellipse thing is basically ready to ship.

If that's true, then we have the first trickle of entries for a new subforum. Any last minute thoughts on these?

[bplus]

Hold on, I am not ready to ship, I found a solution to alpha, still checking results.

[bplus]

No PAINT, no _PUTIMAGE, using rectilinear lines with BF! Now have alpha AND perfect narrow ellipse fills.

Code: QB64: [Select]

1. _TITLE "Tilted Ellipse test" ' B+ 2019-02-09 Thanks to STxAxTIC's formula's
2. SCREEN _NEWIMAGE(800, 600, 32)
3. _SCREENMOVE 200, 40
4. DIM clr AS _UNSIGNED LONG
5. clr = _RGBA32(255, 128, 30, 50)
6. TiltedEllipseFill 0, 400, 300, 300, 200, _PI(1 / 4), clr
7. CIRCLE (400, 300), 300
8. CIRCLE (400, 300), 200
9. INPUT "Hopefully the ellipse radii fits in both circles, press enter..."; wate$
10. CLS
11. WHILE _KEYDOWN(27) = 0
12.     TiltedEllipseFill 0, RND * 600 + 100, RND * 400 + 100, RND * 100 + 1, RND * 100 + 1, _PI(RND * 2), _RGBA32(RND * 255, RND * 255, RND * 255, RND * 255)
13.     _DISPLAY
14.     _LIMIT 10
15. WEND
16.  
17. SUB TiltedEllipseFill (destHandle&, x0, y0, a, b, ang, c AS _UNSIGNED LONG)
18.     DIM max AS INTEGER, mx2 AS INTEGER, i AS INTEGER, j AS INTEGER
19.     DIM prc AS _UNSIGNED LONG
20.     prc = _RGB32(255, 255, 255, 255)  ' prc for Paint Readable Color
21.     IF a > b THEN max = a + 1 ELSE max = b + 1
22.     mx2 = max + max
23.     tef& = _NEWIMAGE(mx2, mx2)
24.     _DEST tef&
25.     _SOURCE tef& 'point wont read without this!
26.     FOR k = 0 TO 6.2832 + .05 STEP .1
27.         i = max + a * COS(k) * COS(ang) + b * SIN(k) * SIN(ang)
28.         j = max - a * COS(k) * SIN(ang) + b * SIN(k) * COS(ang)
29.         IF k <> 0 THEN
30.             LINE (lasti, lastj)-(i, j), prc
31.         ELSE
32.             PSET (i, j), prc
33.         END IF
34.         lasti = i: lastj = j
35.     NEXT
36.     DIM xleft(mx2) AS INTEGER, xright(mx2) AS INTEGER, x AS INTEGER, y AS INTEGER
37.     FOR y = 0 TO mx2
38.         x = 0
39.         WHILE POINT(x, y) <> prc AND x < mx2
40.             x = x + 1
41.         WEND
42.         xleft(y) = x
43.         WHILE POINT(x, y) = prc AND x < mx2
44.             x = x + 1
45.         WEND
46.         WHILE POINT(x, y) <> prc AND x < mx2
47.             x = x + 1
48.         WEND
49.         IF x = mx2 THEN xright(y) = xleft(y) ELSE xright(y) = x
50.     NEXT
51.     _DEST destHandle&
52.     FOR y = 0 TO mx2
53.         IF xleft(y) <> mx2 THEN LINE (xleft(y) + x0 - max, y + y0 - max)-(xright(y) + x0 - max, y + y0 - max), c, BF
54.     NEXT
55.     _FREEIMAGE tef&
56. END SUB
57.  

 

[Pete]

Nice work guys! For non-SCREEN 0 stuff, that is. ;)

Pete

[STxAxTIC]

Hehe, leave it to Pete to beat me to the first comment. Thanks for following this!

Absolutely lovely work bplus. I'm shocked the whole thing came together so quickly.

As everyone probably noticed, these efforts will wind up in a place of their own, so that anytime these questions come up again, we have the answer in a nice section without a flame war occurring underneath. (My own fault usually.)

[SMcNeill]

Paint can handle alpha if _DONTBLEND is in use.  If you’re blending alpha, draw to a separate image first, then _PUTIMAGE the finished ellipseto the main screen.

[STxAxTIC]

Found two small things that only help:

Code: QB64: [Select]

1. FOR k = 0 TO 6.2832 + .05 STEP .05

The small offset next to the factor of 2*pi should agree with the step size.

And more interestingly:

Code: QB64: [Select]

1. IF xleft(y) <> mx2 THEN LINE (xleft(y) + x0 - max, y + y0 - max)-(xright(y) + x0 - max, y + y0 - max), c

... doesn't need BF or even B. Every line is strictly horizontal as y + y0 - max is the only y-argument in the LINE statement above.

[STxAxTIC]

And since the function has broken the underscore barrier, so to speak - what about what Steve just said? Can that make the whole thing smaller and faster?

Damn, while I love my armchair over here in the Science department, I should mingle more with the engineers who use QB64 commands a little more often...

[bplus]

Well I found another correction, the angle and equations work for a Cartesian coordinate system but unfortunately Basic angles start 0 due east and rotate clockwise, so I adjusted equations to follow Basic Angle system.

BF used for lines because according to Steve it is faster than drawing a line. It was a part of the optimizations for CircleFill.

I rounded pi * 2 up so .05 would have worked with .1 STEP (it was) but I did forget I changed back to .1 with STEP. That, BTW is another place that could be optimized for best size to step depending on big or small ellipse circumference.

Here is TiltedEllipseFill with QB64 Basic System of Angle designations:

Code: QB64: [Select]

1. _TITLE "Tilted Ellipse Oops" ' B+ 2019-02-10 oops we have a problem with Angle designation
2. ' Thanks to STxAxTIC's formula's
3.  
4. ' Oops! I forgot to take into account STxAxTIC's Cartisian Coordinate System: Angles
5.  
6. SCREEN _NEWIMAGE(800, 600, 32)
7. _SCREENMOVE 200, 40
8. DIM clr AS _UNSIGNED LONG
9. clr = _RGBA32(255, 128, 30, 50)
10. WHILE _KEYDOWN(27) = 0
11.     CLS
12.     a = a + _PI(1 / 180)
13.     PRINT "Angle:"; INT(_R2D(a))
14.     TiltedEllipseFill 0, 400, 300, 300, 200, a, clr
15.     LINE (400, 300)-(400 + 300 * COS(a), 300 + 300 * SIN(a))
16.     _DISPLAY
17.     _LIMIT 10
18. WEND
19.  
20. SUB TiltedEllipseFill (destHandle&, x0, y0, a, b, ang, c AS _UNSIGNED LONG)
21.     DIM max AS INTEGER, mx2 AS INTEGER, i AS INTEGER, j AS INTEGER
22.     DIM prc AS _UNSIGNED LONG
23.     prc = _RGB32(255, 255, 255, 255)
24.     IF a > b THEN max = a + 1 ELSE max = b + 1
25.     mx2 = max + max
26.     tef& = _NEWIMAGE(mx2, mx2)
27.     _DEST tef&
28.     _SOURCE tef& 'point wont read without this!
29.     FOR k = 0 TO 6.2832 + .05 STEP .1
30.         i = max + a * COS(k) * COS(ang) + b * SIN(k) * SIN(ang)
31.         j = max + a * COS(k) * SIN(ang) - b * SIN(k) * COS(ang)
32.         IF k <> 0 THEN
33.             LINE (lasti, lastj)-(i, j), prc
34.         ELSE
35.             PSET (i, j), prc
36.         END IF
37.         lasti = i: lastj = j
38.     NEXT
39.     DIM xleft(mx2) AS INTEGER, xright(mx2) AS INTEGER, x AS INTEGER, y AS INTEGER
40.     FOR y = 0 TO mx2
41.         x = 0
42.         WHILE POINT(x, y) <> prc AND x < mx2
43.             x = x + 1
44.         WEND
45.         xleft(y) = x
46.         WHILE POINT(x, y) = prc AND x < mx2
47.             x = x + 1
48.         WEND
49.         WHILE POINT(x, y) <> prc AND x < mx2
50.             x = x + 1
51.         WEND
52.         IF x = mx2 THEN xright(y) = xleft(y) ELSE xright(y) = x
53.     NEXT
54.     _DEST destHandle&
55.     FOR y = 0 TO mx2
56.         IF xleft(y) <> mx2 THEN LINE (xleft(y) + x0 - max, y + y0 - max)-(xright(y) + x0 - max, y + y0 - max), c, BF
57.     NEXT
58.     _FREEIMAGE tef&
59. END SUB
60.  

[bplus]

The _DONTBLEND might fix the paint issue but not the poor painting job done with narrow ellipsii.

It's timed tests time if Steve is correct.

[STxAxTIC]

Again your thoroughness is appreciated. Once this thread cools down we'll crystallize the results in the new section. In the meantime, anyone with works that may fit there - sorting routines and the like - are welcome to post that stuff to Programs, or bump it to resurrect the thread.

(That reminds me - Steve, is your screen capture stuff hanging around? We could use a bump on that one, plus a handful of your other things that I'll try to name if they don't surface naturally soon.)

[bplus]

For me, _DONTBLEND makes everything Opaque so whole image rectangle (yuck!!), black and all, is transferred over with _PUTIMAGE, with no alpha transparencies.

Steve may have solution?

Meanwhile a timed test with the alpha beauties.

[bplus]

Problem!

While doing speed tests, I found Steve's EllipseFill was drawing overlapping lines at regular intervals with a held at 400 and b increased from 0 to 400.

Overlaps at b=45, 57, 67, 81, 86, 93... that is just the first few found.

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

[STxAxTIC]

Your attention to detail is indispensable plus! I wonder if 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...