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

[SMcNeill]

And quick question:  What am I missing here; it seems as if this would have to overlap at least one line in an even-lined ellipse height.

Code: QB64: [Select]

1.     LINE (ox - a, oy)-(ox + a, oy), col, BF
2.     DO WHILE y < b
3.         y = y + 1
4.         x = SQR((h2w2 - y * y * w2) \ h2)
5.         LINE (ox - x, oy + y)-(ox + x, oy + y), col, BF
6.         LINE (ox - x, oy - y)-(ox + x, oy - y), col, BF
7.     LOOP

Draw the center line (line 1)...  Then draw above and below it until finished.... (so a 3 line ellipse works, or a 5 line tall ellipse works..)

But when you have an ellipse with a height of 4 lines?  How the heck are we drawing them in odd numbered pairs and then not getting any overlap?

[Pete]

SQR vs loop method: There is a periodic difference of no more than 1 pixel at various heights of an ellipse. I would attribute that to the different methods, which both use a kind of rounding that is a bit different.

As far as the odd vs even question goes, that's a lot like the last line being a dot. It's the way it's set up to work. If you put in a height of one, if prints one line, but if you put in a height of 2, it prints 3 lines, etc. The good news is it always prints the ellipse on the selected x, y coordinates. If we allow for even lines, then the coordinates are a pixel off in each direction. 

As far as integer division, I tried that a while back, mostly thinking it might take longer as it should involve a rounding step, but when I tried it, I got neck and neck results, so I left it as i. Perhaps Bill and ark can speed check those differences and report back. I'm using QB64 64-bit on a 64-bit Windows 10 but it is a slow system. What Mark can test run in 15 seconds takes me a minute.


Here is a line by line demo...

Code: QB64: [Select]

1. SCREEN _NEWIMAGE(1000, 700, 32)
2. _SCREENMOVE 180, 0
3.  
4. FOR i = 2 TO 300 STEP 2
5.     CLS
6.     PRINT "Width = 300 Height ="; i
7.     FlatEllipseFill5 500, 350, 300, i, _RGBA32(0, 500, 0, 500)
8. NEXT
9.  
10. SUB FlatEllipseFill5 (ox AS INTEGER, oy AS INTEGER, a AS INTEGER, b AS INTEGER, col AS _UNSIGNED LONG)
11. IF a = 0 OR b = 0 THEN EXIT SUB
12. DIM h2 AS _INTEGER64
13. DIM w2 AS _INTEGER64
14. DIM h2w2 AS _INTEGER64
15. DIM x AS INTEGER
16. DIM y AS INTEGER
17. w2 = a * a
18. h2 = b * b
19. h2w2 = h2 * w2
20. LINE (ox - a, oy)-(ox + a, oy), col, BF
21. DO WHILE y < b
22.     y = y + 1
23.     x = SQR((h2w2 - y * y * w2) / h2)
24.     col = _RGBA32(y * 50, 100, 500 - y * 50, 300)
25.     SLEEP
26.     LINE (ox - x, oy + y)-(ox + x, oy + y), col, BF
27.     SLEEP
28.     LINE (ox - x, oy - y)-(ox + x, oy - y), col, BF
29.     SLEEP
30. LOOP
31. END SUB
32.  

I wish I knew more about colors to add better contrast. :(

Pete

[STxAxTIC]

Morning,

A quick comment on speed testing... We aren't doing clean experiments all the time. Running the same test multiple times gives varying results, which isn't news... But I'm also finding that the *order* of the tests seems to effect the result. For instance, if I speed test a function against an identical copy of itself, it's rarely a tie: sometimes the function ties itself, but often the function beats itself by a 5%-10% margin, with the second run always being faster than the first. Just pointing this out. Probably a property of doing other stuff with the computer during a test, but that's extremely hard to isolate when stuck in Windows.

Code: QB64: [Select]

1. SCREEN _NEWIMAGE(800, 600, 32)
2.  
3. tt1 = TIMER
4. FOR k = 1 TO 10000
5.     CALL FlatEllipseFill(200, 200, 150, 50, _RGBA(100, 100, 100, 100))
6. NEXT
7. tt2 = TIMER
8. PRINT tt2 - tt1
9.  
10. tt3 = TIMER
11. FOR k = 1 TO 10000
12.     CALL FlatEllipseFill(250, 250, 150, 50, _RGBA(100, 100, 100, 100))
13. NEXT
14. tt4 = TIMER
15. PRINT tt4 - tt3
16.  
17. SUB FlatEllipseFill (ox AS INTEGER, oy AS INTEGER, a AS INTEGER, b AS INTEGER, col AS _UNSIGNED LONG)
18.     IF a = 0 OR b = 0 THEN EXIT SUB
19.     DIM h2 AS _INTEGER64
20.     DIM w2 AS _INTEGER64
21.     DIM h2w2 AS _INTEGER64
22.     DIM x AS INTEGER
23.     DIM y AS INTEGER
24.     w2 = a * a
25.     h2 = b * b
26.     h2w2 = h2 * w2
27.     LINE (ox - a, oy)-(ox + a, oy), col, BF
28.     DO WHILE y < b
29.         y = y + 1
30.         x = SQR((h2w2 - y * y * w2) \ h2)
31.         LINE (ox - x, oy + y)-(ox + x, oy + y), col, BF
32.         LINE (ox - x, oy - y)-(ox + x, oy - y), col, BF
33.     LOOP
34. END SUB

... Despite that, I did find that integer division does seem to perform a little faster on the average than regular division. Everyone agree that the function above is our best contender? I'm itching to lay this one to rest!

[bplus]

I am cool with it. Integer division is nice touch Steve! (I say before I test, because I think integer division should be faster because no floating point math needed.)

Append: Oh this is very, very, very odd!
I have pasted the code for sub in reply above to test with Integer division with \ right?!
and after I run the code test, it is switched back to float division / !!! This has happened twice now! First time I thought I copied the wrong thing.

So I am not seeing much improvement on time.

Anyone else getting this?

Append2: never mind, I must have forgotten to save something, the \ is sticking.  But I am not seeing an improvement, maybe because x is already DIM'd as Integer.

[Pete]

Bill: As to speed testing, I noticed the same things you did. I would swap out tests to offset that. Stupid Windows was preparing an update yesterday, which was messing up things in the background, for instance.

Naming: I wonder how many will fail to realize this puppy makes circles, too? Sure, a circle is just an degenerate ellipse, every community has one, but what else do we have to call it, oval? Hey, how about OVAL FILL? Wait, The Oval Team sounds too much like a 1960s drink option. Oval is more for egg shaped drawings, anyway. Naming things is a real botch sometimes.I like the flatellipsefill name in the current sub calls, except for the possible confusion with... "Well, where's the round ellipse function?"

Other Features: If we threw in a SELECT CASE and an extra parameter, we could include Bill's tilt-a-swirl formula in the non-default case. Zero, the default goes to flat ellipse, while any degree passed goes to CASE ELSE and results in the tilt formula being used. I don't know how much adding SELECT CASE and passing an extra parameter would affect the speed.

Anyway, just some stuff to consider for anyone pressing on...

What I know for sure is after several tests, it doesn't matter how much we try an tweak the one we are concentrating on now, Bill's with modified variable types with loops replacing for/next, and Bill's modified with my SQR replacing the inner loop, both run about the same. That was also true when I added varying sized ellipses to Mark's test program. I thought varying the sizes might show one outperformed but no. The testing, did however, show that Mark's SQR (which he already deduced ran slower), Steve' find, and Vince's modified Steve's find always ran considerably slower. That would probably be even more evident on my machine, because it has a tiny cpu. Hey, it's how it uses it that counts!

I would be for using Bill's modified with or without the SQR modification. What do you guys think about that, the naming, and keeping this just as a "flat" ellipse fill or including a tilt option, if that's OK with Bill? Also, if anyone has any disagreement with my statements, let me have it! I like to provoke thought... my wife says I could leave the thought part off, but you know...

Pete

[SMcNeill]

An IF is just as efficient as an SELECT CASE , though personally, I’d prefer separate routines just so the need to pass parameters is minimized.

As for a CircleFill, just have it call the EllipseFill for you.

SUB CircleFill (x, y, r, c)
   EllipseFill x, y, r, r, c
END SUB

Doesn’t get any simpler than that!  ;)

[bplus]

I don't like the switch idea for circle or flat ellipse or tilt ellipse but maybe one for fill or no fill?

We do need to complete the set for ellipse for at least tilted ellipse no fill, but I'd like to see flat ellipse outline too, to match the fill version. Using Circle might not match same flat ellipse outline. Another thing to test?

I like Steve's solution for fill circle or fill flat ellipse "switch".

[Pete]

SUB CircleFill (x, y, r, c)
   EllipseFill x, y, r, r, c
END SUB

I lile that idea!

Now, to your other post awhile ago, concerning overlap. I can assure you Bill's routine never overlaps lines, but I'm thinking of omitting the last loop, because it always ends up having x = 0. That means it just places a dot at the top and bottom of the vertical axis, no matter what the width of the ellipse is. I don't think we need that. If eliminated, a value of 1 would yield a line the width of the ellipse, without two stupid 1-pixel dots on the top and the bottom. (Edited in): I had to up the color resolution, but I see there are two lateral dots, too. No Steve, dots, NOT BOOBS! :D I guess this is just inherent in the math but it seems like there should be one more calculation to smooth things out, but then there goes the elegance. The horizontal line could be trimmed by one on each end, no problem.

So as it stands now, a value of 1 yields 3 lines, middle, top, bottom with the formula for the overall height of the flat ellipse as: n * 2 + 1, but if we get rid of the top and bottom "dot" lines, we get one line for a value of one, three lines for a value of two, five lines for a value of 3, and so on.

We either need a way to convey how the sizing works, or change it so it draws the implicit number of lines entered by the user. Changing it would open up a can of worms in the math, that's for sure. :(

So where do we want to head from here? BTW, I can provide some example code, if you don't "see" what I'm talking about.

Pete

[bplus]

Ha! will it ever end?

Yep, I was expecting a flat ellipse with xRadius of n to be 2n pixels wide not 2n+1, likewise an ellipse with yRadius of m pixels to be 2m pixels high not 2m+1.

As I would expect a circle of r radius to be 2r wide and high.

Wouldn't a circle of radius 1 fill pixels (probably would have to round up) like this:
**
**
where is (x, y) origin? x+.5, y+.5?


not like this?
 *
***
 *
but x, y origin is obvious middle dot.


I think it would depend on how things round out, whether there is 1 dot at top and bottom or several.

[SMcNeill]

Ha! will it ever end?

Yep, I was expecting a flat ellipse with xRadius of n to be 2n pixels wide not 2n+1, likewise an ellipse with yRadius of m pixels to be 2m pixels high not 2m+1.

As I would expect a circle of r radius to be 2r wide and high.

Wouldn't a circle of radius 1 fill pixels (probably would have to round up) like this:
**
**
where is (x, y) origin? x+.5, y+.5?


not like this?
 *
***
 *
but x, y origin is obvious middle dot.


I think it would depend on how things round out, whether there is 1 dot at top and bottom or several.

Isn’t a 1-radius circle just a point?

*

Or would you call that 0-radius with 1-radius being:

  *
***
  *

Enquiring minds want to know!

Personally, I’d think a radius of 2 should give a Diameter of 4, not 5, as these calculations are doing.

[Pete]

In the current models, Mark has an EXIT SUB, which prevents 0 from making any line or dot. Remove that, and a zero passed to the sub would result in a single line or dot, depending on the width measurement. In other words, 0, 0 would result in a dot, if Mark's EXIT SUB was removed.

Pete

[bplus]

Ha! will it ever end?

Yep, I was expecting a flat ellipse with xRadius of n to be 2n pixels wide not 2n+1, likewise an ellipse with yRadius of m pixels to be 2m pixels high not 2m+1.

As I would expect a circle of r radius to be 2r wide and high.

Wouldn't a circle of radius 1 fill pixels (probably would have to round up) like this:
**
**
where is (x, y) origin? x+.5, y+.5?


not like this?
 *
***
 *
but x, y origin is obvious middle dot.


I think it would depend on how things round out, whether there is 1 dot at top and bottom or several.

Isn’t a 1-radius circle just a point?

*

Or would you call that 0-radius with 1-radius being:

  *
***
  *

Enquiring minds want to know!

Personally, I’d think a radius of 2 should give a Diameter of 4, not 5, as these calculations are doing.

I pick the latter, you can count the radius in pixels up, down, left and right PLUS that seems the convention.

So we are stuck in +1 land, if a radius is n then the pixel count across or up/down is 2n+1.

So Pete should be getting only one dot at top or bottom AND left and right if any partial fractions are always rounded down.

If rounded up when >.5 should occasionally get flat tops and sides of several pixels.

In the current models, Mark has an EXIT SUB, which prevents 0 from making any line or dot. Remove that, and a zero passed to the sub would result in a single line or dot, depending on the width measurement. In other words, 0, 0 would result in a dot, if Mark's EXIT SUB was removed.

Pete

Pete,  OK draw the pixel or line then.

[bplus]

Try this:

Code: QB64: [Select]

1.     LINE (ox - a, oy)-(ox + a, oy), col, BF
2.     DO WHILE y < b
3.         y = y + 1
4.         x = SQR((h2w2 - y * y * w2) \ h2 + .5)  '<<<<<<<<<<<<< add .5 for rounding up once and awhile
5.         LINE (ox - x, oy + y)-(ox + x, oy + y), col, BF
6.         LINE (ox - x, oy - y)-(ox + x, oy - y), col, BF
7.     LOOP
8.  

[SMcNeill]

Or try:

X = _ROUND(SQR(....

[Pete]

If we don't want the dot on top and bottom, we also need to shorten the initial center line. Top and bottom dots go away be just a -1 in the LOOP. We'd have to play around a bit to see if it is as easy to trim that center line.

I don't think I would have noticed this, except I replaced lines with numbers to compare SQR with the loop method, and I noticed the final value for x was always zero. The I increased the brightness of the fill and saw the dots. Bill needs to see if he can live with them, since he worked out the original formula. I'm OK what ever is decided, because no drawings in pixels ever look perfect.

Oh, and I was writing this while you were posting. As for the rounding, I looked into that when I noticed SQR was a bit off by one once in awhile with the loop model, but the drawings were still sound. It was never off by more than one and I think because one is an approximation by trial and error and the other is a math function, it would be pretty hard to match them up all the time, but maybe you got it right there. I'll have to see if I can recover the program I put together to test those values. Stupid Windows updated last night, even though my system was on sleep. It shut down and rebooted, with my permission. That's a "feature" according to assholes (AKA Microsoft developers.)

Pete