Post by: STxAxTIC on February 06, 2019, 06:46:38 pm
(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]
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...
Post by: bplus 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]
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]
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).
Post by: STxAxTIC on February 06, 2019, 09:21:25 pm
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.
Post by: bplus on February 06, 2019, 09:40:30 pm
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.
Post by: SMcNeill 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. ;)
Post by: bplus on February 06, 2019, 11:55:25 pm
Code: QB64: [Select]
- _TITLE "Steves EllipseFill (right) vrs gold standard CircleFill (left), 2 tests take about 17 secs each after you press enter."
- DEFINT A-Z
- _DELAY 1
- INPUT "EllipseFill (fel) overlap test, press enter to continue "; wate$
- start## = TIMER
- ' ==================================================== compare to the old gold standard
- start## = TIMER
- 'old circle fill
- RadiusError = -Radius
- X = Radius
- Y = 0
- ' Draw the middle span here so we don't draw it twice in the main loop,
- ' which would be a problem with blending turned on.
- WHILE X > Y
- RadiusError = RadiusError + Y * 2 + 1
- X = X - 1
- RadiusError = RadiusError - X * 2
- Y = Y + 1
- a = 2 * rx * rx
- b = 2 * ry * ry
- x = rx
- xx = ry * ry * (1 - rx - rx)
- yy = rx * rx
- sx = b * rx
- y = y + 1
- sy = sy + a
- e = e + yy
- yy = yy + a
- x = x - 1
- sx = sx - b
- e = e + xx
- xx = xx + b
- x = 0
- y = ry
- xx = rx * ry
- yy = rx * rx * (1 - ry - ry)
- e = 0
- sx = 1
- sy = a * ry
- x = x + 1
- sx = sx + b
- e = e + xx
- xx = xx + b
- y = y - 1
- sy = sy - a
- e = e + yy
- yy = yy + a
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?
Post by: STxAxTIC on February 07, 2019, 07:46:17 am
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.
Post by: _vince 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]
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?
Post by: SMcNeill 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]
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.
Post by: STxAxTIC on February 09, 2019, 06:39:23 pm
Code: QB64: [Select]
Post by: bplus on February 09, 2019, 07:25:28 pm
Kudos for being first with code for tilted ellipse.
Post by: STxAxTIC on February 09, 2019, 08:05:53 pm
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]
Post by: bplus on February 09, 2019, 08:16:33 pm
I still think we need a sub that is not dependent upon knowing where the center of the screen is.
Post by: STxAxTIC on February 09, 2019, 08:21:43 pm
Post by: bplus on February 09, 2019, 09:35:28 pm
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]
- _TITLE "Tilted Ellipse test"
- INPUT "Hopefully the ellipse radii fits in both circles, press enter..."; wate$
- _LIMIT 10
- _DEST tef&
- lasti = i: lastj = j
- _FREEIMAGE tef&
Post by: STxAxTIC on February 09, 2019, 09:50:36 pm
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.
Post by: STxAxTIC on February 09, 2019, 09:58:54 pm
(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?
Post by: bplus on February 09, 2019, 11:06:07 pm
Post by: bplus on February 09, 2019, 11:19:15 pm
Code: QB64: [Select]
Post by: Pete on February 09, 2019, 11:22:50 pm
Pete
Post by: STxAxTIC on February 09, 2019, 11:28:58 pm
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.)
Post by: SMcNeill on February 09, 2019, 11:49:52 pm
Post by: STxAxTIC on February 09, 2019, 11:55:01 pm
Code: QB64: [Select]
The small offset next to the factor of 2*pi should agree with the step size.
And more interestingly:
Code: QB64: [Select]
... 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.
Post by: STxAxTIC on February 10, 2019, 12:00:30 am
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...
Post by: bplus on February 10, 2019, 12:15:12 am
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]
- ' Thanks to STxAxTIC's formula's
- ' Oops! I forgot to take into account STxAxTIC's Cartisian Coordinate System: Angles
- TiltedEllipseFill 0, 400, 300, 300, 200, a, clr
- _LIMIT 10
- mx2 = max + max
- _DEST tef&
- _SOURCE tef& 'point wont read without this!
- lasti = i: lastj = j
- x = 0
- x = x + 1
- xleft(y) = x
- x = x + 1
- x = x + 1
- _DEST destHandle&
- _FREEIMAGE tef&
Post by: bplus on February 10, 2019, 12:23:36 am
It's timed tests time if Steve is correct.
Post by: STxAxTIC on February 10, 2019, 12:27:23 am
(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.)
Post by: bplus on February 10, 2019, 12:43:07 am
Steve may have solution?
Meanwhile a timed test with the alpha beauties.
Post by: bplus on February 10, 2019, 11:53:18 am
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]
- _TITLE "Ellipsefill from Steve"
- 'B+ 2019-02-10 resave this code to
- 'just test this code for proper filling without overlap, timed tests are else where
- k$ = ""
- _LIMIT 1
- ' with Steve's EllipseFill, who needs CircleFill? fix for 0 radii 2019-02-05
- ' Is this fast enough for general circle fill (June 2018): https://www.qb64.org/forum/index.php?topic=298.msg1942#msg1942
- ' EllipseFill SMcNeill (Nov 3, 2018) https://www.qb64.org/forum/index.php?topic=755.msg6506#msg6506
- a = 2 * rx * rx
- b = 2 * ry * ry
- x = rx
- xx = ry * ry * (1 - rx - rx)
- yy = rx * rx
- sx = b * rx
- y = y + 1
- sy = sy + a
- e = e + yy
- yy = yy + a
- x = x - 1
- sx = sx - b
- e = e + xx
- xx = xx + b
- x = 0
- y = ry
- xx = rx * ry
- yy = rx * rx * (1 - ry - ry)
- e = 0
- sx = 0
- sy = a * ry
- x = x + 1
- sx = sx + b
- e = e + xx
- xx = xx + b
- y = y - 1
- sy = sy - a
- e = e + yy
- yy = yy + a
Post by: STxAxTIC on February 10, 2019, 11:59:36 am
Post by: bplus on February 10, 2019, 12:01:16 pm
Your attention to detail is indispensible plus! I wonder it 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...
Probably I am starting to become PIA.
I am next going to submit CircleFill to same test.
Post by: Pete on February 10, 2019, 12:18:28 pm
I don't see an obvious pattern in the results you posted, which means something in the algorithm is crunching numbers with probably some decimal off in the wrong direction.
BTW- you probably meant PITA, instead of PIA, you PITA!
Pete :D
Post by: bplus on February 10, 2019, 12:22:22 pm
Post by: Pete on February 10, 2019, 03:26:53 pm
Anyway, if it works it works because it simply checks the boundaries set byt the fist line statements and doesn't let the second set of line statements overlap them, which was causing the initial problem at radius entries like 45, 67, etc.
Code: QB64: [Select]
- _TITLE "Ellipsefill from Steve"
- 'B+ 2019-02-10 resave this code to
- 'just test this code for proper filling without overlap, timed tests are else where
- k$ = ""
- _LIMIT 1
- ' with Steve's EllipseFill, who needs CircleFill? fix for 0 radii 2019-02-05
- ' Is this fast enough for general circle fill (June 2018): https://www.qb64.org/forum/index.php?topic=298.msg1942#msg1942
- ' EllipseFill SMcNeill (Nov 3, 2018) https://www.qb64.org/forum/index.php?topic=755.msg6506#msg6506
- a = 2 * rx * rx
- b = 2 * ry * ry
- x = rx
- xx = ry * ry * (1 - 2 * rx)
- yy = rx * rx
- sx = b * rx
- y = y + 1
- sy = sy + a
- e = e + yy
- yy = yy + a
- x = x - 1
- sx = sx - b
- e = e + xx
- xx = xx + b
- oldy = y ' Pete's fix
- x = 0
- y = ry
- xx = rx * ry
- yy = rx * rx * (1 - 2 * ry)
- e = 0
- sx = 0
- sy = a * ry
- x = x + 1
- sx = sx + b
- e = e + xx
- xx = xx + b
- y = y - 1
- sy = sy - a
- e = e + yy
- yy = yy + a
Post by: bplus on February 10, 2019, 03:53:06 pm
Post by: Pete on February 10, 2019, 03:58:18 pm
Pete
Post by: bplus on February 10, 2019, 04:47:51 pm
Post by: Pete on February 10, 2019, 04:51:55 pm
Pete
Post by: bplus on February 10, 2019, 04:53:37 pm
Did you check what I posted above about switching up some of the math calcs? I don't want such a change to impede the speed.
Pete
Yes, nothing with the math was changed that I could see.
Here is the test code for time:
Code: QB64: [Select]
- _TITLE "Steves EllipseFill (right) vrs gold standard CircleFill (left), 2 tests take about 17 secs each after you press enter."
- DEFINT A-Z
- _DELAY 1
- INPUT "EllipseFill (fel) overlap test, press enter to continue "; wate$
- start## = TIMER
- ' ==================================================== compare to the old gold standard
- start## = TIMER
- 'old circle fill
- RadiusError = -Radius
- X = Radius
- Y = 0
- ' Draw the middle span here so we don't draw it twice in the main loop,
- ' which would be a problem with blending turned on.
- WHILE X > Y
- RadiusError = RadiusError + Y * 2 + 1
- X = X - 1
- RadiusError = RadiusError - X * 2
- Y = Y + 1
- ' now with Pete's fix for overlap 2019-02-10
- ' with Steve's EllipseFill, who needs CircleFill? fix for 0 radii 2019-02-05
- ' Is this fast enough for general circle fill (June 2018): https://www.qb64.org/forum/index.php?topic=298.msg1942#msg1942
- ' EllipseFill SMcNeill (Nov 3, 2018) https://www.qb64.org/forum/index.php?topic=755.msg6506#msg6506
- a = 2 * rx * rx
- b = 2 * ry * ry
- x = rx
- xx = ry * ry * (1 - rx - rx)
- yy = rx * rx
- sx = b * rx
- y = y + 1
- sy = sy + a
- e = e + yy
- yy = yy + a
- x = x - 1
- sx = sx - b
- e = e + xx
- xx = xx + b
- oldy = y ' Pete's fix
- x = 0
- y = ry
- xx = rx * ry
- yy = rx * rx * (1 - ry - ry)
- e = 0
- sx = 0
- sy = a * ry
- DO ' Pete's fix eliminate > WHILE sx <= sy ' no = ? fixed once but mostly no fix
- x = x + 1
- sx = sx + b
- e = e + xx
- xx = xx + b
- y = y - 1
- sy = sy - a
- e = e + yy
- yy = yy + a
Post by: Pete on February 10, 2019, 05:16:27 pm
So here is one I completely converted, unless I missed something.
Code: QB64: [Select]
- _TITLE "Ellipsefill from Steve"
- ' Pete changed math operations so r * r is now R^2, r + r is 2 * r, etc.
- 'B+ 2019-02-10 resave this code to
- 'just test this code for proper filling without overlap, timed tests are else where
- k$ = ""
- _LIMIT 1
- ' with Steve's EllipseFill, who needs CircleFill? fix for 0 radii 2019-02-05
- ' Is this fast enough for general circle fill (June 2018): https://www.qb64.org/forum/index.php?topic=298.msg1942#msg1942
- ' EllipseFill SMcNeill (Nov 3, 2018) https://www.qb64.org/forum/index.php?topic=755.msg6506#msg6506
- a = 2 * rx ^ 2
- b = 2 * ry ^ 2
- x = rx
- xx = ry ^ 2 * (1 - 2 * rx)
- yy = rx ^ 2
- sx = b * rx
- y = y + 1
- sy = sy + a
- e = e + yy
- yy = yy + a
- x = x - 1
- sx = sx - b
- e = e + xx
- xx = xx + b
- oldy = y ' Pete's fix
- x = 0
- y = ry
- xx = rx * ry
- yy = rx ^ 2 * (1 - 2 * ry)
- e = 0
- sx = 0
- sy = a * ry
- x = x + 1
- sx = sx + b
- e = e + xx
- xx = xx + b
- y = y - 1
- sy = sy - a
- e = e + yy
- yy = yy + a
Post by: SMcNeill on February 10, 2019, 06:18:28 pm
R * R is faster than R ^ 2
Certain operations have more overhead than others. If you’re going to optimize for speed, choose the operator with the fastest performance. ;)
Post by: Pete on February 10, 2019, 06:25:40 pm
So, my fix applied with the fastest math method according to Steve would be...
Code: QB64: [Select]
- _TITLE "Ellipsefill from Steve"
- 'B+ 2019-02-10 resave this code to
- 'just test this code for proper filling without overlap, timed tests are else where
- k$ = ""
- _LIMIT 1
- ' with Steve's EllipseFill, who needs CircleFill? fix for 0 radii 2019-02-05
- ' Is this fast enough for general circle fill (June 2018): https://www.qb64.org/forum/index.php?topic=298.msg1942#msg1942
- ' EllipseFill SMcNeill (Nov 3, 2018) https://www.qb64.org/forum/index.php?topic=755.msg6506#msg6506
- a = 2 * rx * rx
- b = 2 * ry * ry
- x = rx
- xx = ry * ry * (1 - rx - rx)
- yy = rx * rx
- sx = b * rx
- y = y + 1
- sy = sy + a
- e = e + yy
- yy = yy + a
- x = x - 1
- sx = sx - b
- e = e + xx
- xx = xx + b
- oldy = y ' Pete's fix. Get the last fill position.
- x = 0
- y = ry
- xx = rx * ry
- yy = rx * rx * (1 - ry - ry)
- e = 0
- sx = 0
- sy = a * ry
- x = x + 1
- sx = sx + b
- e = e + xx
- xx = xx + b
- y = y - 1
- sy = sy - a
- e = e + yy
- yy = yy + a
Post by: bplus on February 10, 2019, 06:34:06 pm
That's what I wanted to know.
So, my fix applied with the fastest math method according to Steve would be...Code: QB64: [Select]
And that is what I had in my timed tests and that is why I said Pete made no math changes.
we could change:
a = 2 * rx * rx
b = 2 * ry * ry
to a = rx*rx + rx*rx
b = ry*ry + ry * ry
Post by: SMcNeill on February 10, 2019, 06:43:47 pm
Quote
a = 2 * rx * rx
to a = rx*rx + rx*rx
You’ll just be slower....
You’re going from 2 multiplication operations to 2 multiplication operations AND an addition operation.
Maybe: a1 = rx * rx: a = a1 + a1 (If lookup times are faster)
Post by: bplus on February 10, 2019, 06:48:18 pm
Post by: Pete on February 10, 2019, 06:55:35 pm
R + R is faster than 2 * R
R * R is faster than R ^ 2
so for example in the original code...
xx = ry * ry * (1 - rx - rx) ' Original code
is faster than changing it to...
xx = ry * ry * (1 - 2 * rx)
I see you just changed it back to the original code, which should match the last one I posted, where I changed it back as well. So we should now have the fastest way to move through the equations, plus my fix the periodic fill problem. All good to go?
Pete
Post by: bplus on February 10, 2019, 07:37:19 pm
Ha! go figure.
Post by: Pete on February 10, 2019, 07:46:51 pm
So 64-bit has too much memory allocated for more digits than needed, maybe, or just a fluke?
Pete
Post by: SMcNeill on February 10, 2019, 07:55:05 pm
I just ran the timed test in a 32 bit version of QB64 and saved almost 3 sec on both CircleFill and EllipseFill.
Ha! go figure.
And have fun playing with some of the math optimization flags. They can drastically change your test times.
Post by: STxAxTIC on February 10, 2019, 11:10:43 pm
100% regardless of this issue or any others, I think the situation demands a pencil-to-paper derivation of how that function works. I'll reinvent it all if I have to, but surely it's among Steve's notes somewhere?
Post by: SMcNeill on February 10, 2019, 11:21:53 pm
Aaaalrighty, didn't expect to be gone all day, so I'm trying to play catchup here. First thing I notice is Steve's function doesn't draw ellipses for large eccentricity (small b). There are boobs on each end - just a recent artifact or was that there all along?
100% regardless of this issue or any others, I think the situation demands a pencil-to-paper derivation of how that function works. I'll reinvent it all if I have to, but surely it's among Steve's notes somewhere?
Afraid not. I found it in an old QB45 program that was on an old drive of mine from ages ago. I have no idea where the heck I originally acquired/derived it, and I didn’t take any notes as I tweaked it to remove duplicate lines in the past. (And it seems I still missed a few, but I think Pete’s fix corrects those.)
I’ll see if I can pull the original back up later (I have to reinstall the old 40GB drive and an IDE card/cable to use it), and see if the “boob effect” is there from the original, or introduced via alterations.
Post by: Pete on February 10, 2019, 11:35:52 pm
Pete :D
Post by: STxAxTIC on February 10, 2019, 11:47:31 pm
XD
I should modify my Tilted ellipse to include a Titted ellipse version as well...
Post by: Pete on February 11, 2019, 12:42:11 am
Pete :D
Post by: STxAxTIC on February 11, 2019, 01:06:58 am
Code: QB64: [Select]
- w2 = a * a
- h2 = b * b
- h2w2 = h2 * w2
- xi = a
- dx = 0
- dx = xi - x
- xi = x
... just have to check it for bugs, boobs, or other artifacts.
Post by: Pete on February 11, 2019, 01:52:43 am
Code: QB64: [Select]
- w2 = a * a
- h2 = b * b
- h2w2 = h2 * w2
- xi = a
- dx = 0
- dx = xi - x
- xi = x
201 fails, too, but plug in 203 and it's fine.
Pete
Post by: Cobalt on February 11, 2019, 02:27:07 am
So what Steve is saying is that...
...
R * R is faster than R ^ 2
...
Pete
and _SHL\_SHR are even faster if dealing with powers of 2
so _SHL(R,1) should be faster than R^2 and R*R
only draw back is it has to be power of 2.
I like 2s, 2 eyes, 2 ears, 2 hands, 2 balls.., 2 teats.... life is full of 2s unless your a cow then its 4 teats(hey power of 2!) or pigs then its 8 teats (hey another power of 2!) not versed enough in animal biology does any animal have 16 teats?
Post by: Pete on February 11, 2019, 02:40:21 am
Post by: Pete on February 11, 2019, 02:45:10 am
Code: QB64: [Select]
- w2 = a * a
- h2 = b * b
- h2w2 = h2 * w2
- xi = a
- dx = 0
- dx = xi - x
- xi = x
So I tested it with this, and no glitches. It will make a circle at 300 and then start on a vertical ellipse. It's also a fun effect if you omit the CLS and sleep. Stop it at 300 and you get a full moon effect.
Anyway, maybe something less than DOUBLE can be used but that for/next loop spits out some very large figures.
Code: QB64: [Select]
- PRINT "300 x"; i
- w2 = a * a
- h2 = b * b
- h2w2 = h2 * w2
- xi = a
- dx = 0
- dx = xi - x
- xi = x
I was about half way through making one like this, after getting the formulas together to calculate the parts of an ellipse. Oh well, spoiler. Nice find, Bill...
Pete
Post by: STxAxTIC on February 11, 2019, 06:48:30 am
Post by: bplus on February 11, 2019, 10:19:36 am
Code: QB64: [Select]
- w2 = a * a
- h2 = b * b
- h2w2 = h2 * w2
- xi = a
- dx = 0
- dx = xi - x
- xi = x
IMO this is optimized for clarity:
Code: QB64: [Select]
- scale = yRadius / xRadius
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]
Code: QB64: [Select]
- dx = xi - x
- xi = x
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.
Post by: Pete on February 11, 2019, 10:57:38 am
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
Post by: bplus on February 11, 2019, 11:19:08 am
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]
- _TITLE "STATIC Ellipse Fill versus Steve Circle Fill"
- DEFINT A-Z
- _DELAY 1
- INPUT "EllipseFill (fel) overlap test, press enter to continue "; wate$
- start## = TIMER
- ' ==================================================== compare to the old gold standard
- start## = TIMER
- 'old circle fill
- RadiusError = -Radius
- X = Radius
- Y = 0
- ' Draw the middle span here so we don't draw it twice in the main loop,
- ' which would be a problem with blending turned on.
- WHILE X > Y
- RadiusError = RadiusError + Y * 2 + 1
- X = X - 1
- RadiusError = RadiusError - X * 2
- Y = Y + 1
- w2 = a * a
- h2 = b * b
- h2w2 = h2 * w2
- xi = a
- dx = 0
- y = 0 ' B+ added this to eliminate FOR loop
- y = y + 1
- dx = xi - x
- xi = x
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!
Post by: Pete on February 11, 2019, 11:44:44 am
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
Post by: bplus 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???
Post by: Pete on February 11, 2019, 12:08:56 pm
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
Post by: bplus on February 11, 2019, 12:56:12 pm
Code: QB64: [Select]
switch test from LONG type to _INTEGER64
Post by: bplus on February 11, 2019, 01:17:45 pm
Code: QB64: [Select]
- 'B+ 2019-02-10 resave this code to
- 'just test this code for proper filling without overlap, timed tests are else where
- 'k$ = ""
- 'WHILE LEN(k$) = 0: k$ = INKEY$: WEND
- 'IF k$ = CHR$(8) THEN i = i - 2
- 'IF k$ = CHR$(27) THEN EXIT FOR
- _LIMIT 5
- 'k$ = ""
- 'WHILE LEN(k$) = 0: k$ = INKEY$: WEND
- 'IF k$ = CHR$(8) THEN i = i - 2
- 'IF k$ = CHR$(27) THEN EXIT FOR
- _LIMIT 5
- _LIMIT 1
- SUB FlatEllipseFill (ox AS _INTEGER64, oy AS _INTEGER64, a AS _INTEGER64, b AS _INTEGER64, col AS _UNSIGNED LONG)
- w2 = a * a
- h2 = b * b
- h2w2 = h2 * w2
- xi = a
- dx = 0
- y = 0 ' B+ added this to eliminate FOR loop
- y = y + 1
- x = xi - dx + 2
- x = x - 1
- dx = xi - x
- xi = x
I confess a certain a bias to keeping everything out of float types.
Post by: bplus on February 11, 2019, 01:24:15 pm
Code: QB64: [Select]
- _TITLE "STATIC Ellipse Fill versus Steve Circle Fill"
- DEFINT A-Z
- _DELAY 1
- INPUT "Flat EllipseFill overlap test, press enter to continue "; wate$
- start## = TIMER
- ' ==================================================== compare to the old gold standard
- start## = TIMER
- 'old circle fill
- RadiusError = -Radius
- X = Radius
- Y = 0
- ' Draw the middle span here so we don't draw it twice in the main loop,
- ' which would be a problem with blending turned on.
- WHILE X > Y
- RadiusError = RadiusError + Y * 2 + 1
- X = X - 1
- RadiusError = RadiusError - X * 2
- Y = Y + 1
- SUB FlatEllipseFill (ox AS _INTEGER64, oy AS _INTEGER64, a AS _INTEGER64, b AS _INTEGER64, col AS _UNSIGNED LONG)
- w2 = a * a
- h2 = b * b
- h2w2 = h2 * w2
- xi = a
- dx = 0
- y = 0 ' B+ added this to eliminate FOR loop
- y = y + 1
- x = xi - dx + 2
- x = x - 1
- dx = xi - x
- xi = x
Post by: Pete on February 11, 2019, 01:47:32 pm
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
Post by: bplus on February 11, 2019, 06:22:51 pm
Post by: STxAxTIC on February 11, 2019, 10:22:27 pm
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.
Post by: Pete on February 12, 2019, 04:29:44 am
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]
- w2 = a * a
- h2 = b * b
- h2w2 = h2 * w2
- xi = a
- dx = 0
- y = 0
- y = y + 1
- yyw2 = y * y * w2
- x = xi - dx + 1
- x = x - 1
- dx = xi - x
- xi = x
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
Post by: SMcNeill on February 12, 2019, 07:00:25 am
Post by: Pete on February 12, 2019, 10:12:35 am
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]
- w2 = a * a
- h2 = b * b
- h2w2 = h2 * w2
- xi = a
- dx = 0
- y = 0
- 100
- y = y + 1
- yyw2 = y * y * w2
- x = xi - dx + 1
- 101
- x = x - 1
- GOTO 101
- 102
- dx = xi - x
- xi = x
Post by: _vince on February 12, 2019, 10:40:15 am
comment out the last line in the sub ;-)
Code: QB64: [Select]
- a = 2*rx*rx
- b = 2*ry*ry
- x = 0
- y = ry
- dx = ry*ry
- dy = rx*rx*(1 - 2*ry)
- e = 0
- sx = 0
- sy = a*ry
- x = x + 1
- sx = sx + b
- e = e + dx
- dx = dx + b
- y = y - 1
- sy = sy - a
- e = e + dy
- dy = dy + a
- x1 = x0 - x
- x2 = x0 + x
- y1 = y0 - y
- x = rx
- y = 0
- dx = ry*ry*(1 - 2*rx)
- dy = rx*rx
- e = 0
- sx = b*rx
- sy = 0
- x3 = x0 - x
- y = y + 1
- sy = sy + a
- e = e + dy
- dy = dy + a
- x = x - 1
- sx = sx - b
- e = e + dx
- dx = dx + b
Post by: bplus on February 12, 2019, 10:50:28 am
Vince, does your version take care of the nipple problem?
Post by: Pete on February 12, 2019, 10:57:01 am
x = INT(SQR((h2w2 - yyw2) / h2))
I'll post back with an example, soon...
Pete
Post by: Pete on February 12, 2019, 11:02:43 am
MODIFIED SINGLE LOOP ELLIPSE FILL SUB ROUTINE. (Solved algebraically.)
Code: QB64: [Select]
- w2 = a * a
- h2 = b * b
- h2w2 = h2 * w2
- x = a
- y = 0
- 100
- y = y + 1
- yyw2 = y * y * w2
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!
Post by: bplus on February 12, 2019, 11:08:00 am
further optimized version of steve's amazing algorithm ;-)
comment out the last line in the sub ;-)Code: QB64: [Select]
Yikes! Vince, here is my overlap test of your code (with last line in sub commented out)
Post by: _vince on February 12, 2019, 11:14:29 am
Post by: Pete on February 12, 2019, 11:15:21 am
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
Post by: bplus on February 12, 2019, 11:28:38 am
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]
Oh! I see it now, the first line, sorry, I was expecting it after DIM statements.
Post by: Pete on February 12, 2019, 11:34:20 am
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]
- STATIC pete
- pete = -1
- w2 = a * a
- h2 = b * b
- h2w2 = h2 * w2
- x = a
- y = 0
- 100
- y = y + 1
- yyw2 = y * y * w2
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!
Post by: bplus on February 12, 2019, 11:59:49 am
Post by: Pete on February 12, 2019, 12:15:43 pm
Pete
Post by: SMcNeill on February 12, 2019, 12:37:02 pm
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. ;)
Post by: Pete on February 12, 2019, 12:53:33 pm
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
Post by: bplus on February 12, 2019, 01:22:45 pm
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]
Post by: SMcNeill on February 12, 2019, 01:32:24 pm
Code: QB64: [Select]
- STATIC pete
- pete = -1
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.
Post by: Pete on February 12, 2019, 01:50:51 pm
Mark, I'll get rid of the GOTO. Thanks for testing that.
This looks like my finished modifications. I also removed the y = 0 part, as I presume if this gets put into the tool box forum we will talk about renaming the variables to less commonly used names, names unique to the sub.
Code: QB64: [Select]
- w2 = a * a
- h2 = b * b
- h2w2 = h2 * w2
- x = a
- y = y + 1
- yyw2 = y * y * w2
Pete
Post by: STxAxTIC on February 12, 2019, 02:43:02 pm
A deep bow for having the balls to try that out again!
As for variable names - scope should save us. As part of good design, we should avoid globals (DIM SHAREDs) whenever possible, and there should be no collision whatsoever between simple variables like "y" causing interference. If it's *other* functions/subs/elements in someone's program that cause a problem with variable names, we shouldn't be obligated to hold their hand on this. Then again, qb64 functions have a bug (I refuse to call this a feature, it's a genuine "bad part") where functions can edit variables passed to them. Just terrible, and I always code to avoid being bitten by this. If we need to muck around with variable names to save people from being confused, then so be it I suppose.
Post by: bplus on February 12, 2019, 02:53:40 pm
Code: QB64: [Select]
- _TITLE "STATIC Ellipse Fill versus Steve Circle Fill"
- DEFINT A-Z
- _DELAY 1
- INPUT "Flat EllipseFill overlap test, press enter to continue "; wate$
- start## = TIMER
- ' ==================================================== compare to the old gold standard
- start## = TIMER
- 'old circle fill
- RadiusError = -Radius
- X = Radius
- Y = 0
- ' Draw the middle span here so we don't draw it twice in the main loop,
- ' which would be a problem with blending turned on.
- WHILE X > Y
- RadiusError = RadiusError + Y * 2 + 1
- X = X - 1
- RadiusError = RadiusError - X * 2
- Y = Y + 1
- SUB FlatEllipseFill (ox AS _INTEGER64, oy AS _INTEGER64, a AS _INTEGER64, b AS _INTEGER64, col AS _UNSIGNED LONG)
- w2 = a * a
- h2 = b * b
- h2w2 = h2 * w2
- xi = a
- dx = 0
- ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' y = 0 ' B+ added this to eliminate FOR loop
- y = y + 1
- x = xi - dx + 2
- x = x - 1
- dx = xi - x
- xi = x
I commented out one line in above code and now it is consistently matching or beating the Gold Standard Circle fill AND matching Circle fill's lowest time.
Here is the code for test I am using:
Code: QB64: [Select]
- _TITLE "STATIC Ellipse Fill versus Steve Circle Fill"
- '2019-02-12 add Pete's variation
- _DELAY 1
- INPUT "Flat EllipseFill overlap test, press enter to continue "; wate$
- start## = TIMER
- ' ==================================================== compare to the old gold standard
- start## = TIMER
- 'old circle fill
- RadiusError = -Radius
- X = Radius
- Y = 0
- ' Draw the middle span here so we don't draw it twice in the main loop,
- ' which would be a problem with blending turned on.
- WHILE X > Y
- RadiusError = RadiusError + Y * 2 + 1
- X = X - 1
- RadiusError = RadiusError - X * 2
- Y = Y + 1
- SUB FlatEllipseFill (ox AS _INTEGER64, oy AS _INTEGER64, a AS _INTEGER64, b AS _INTEGER64, col AS _UNSIGNED LONG)
- w2 = a * a
- h2 = b * b
- h2w2 = h2 * w2
- xi = a
- dx = 0
- 'y = 0 ' B+ added this to eliminate FOR loop
- y = y + 1
- x = xi - dx + 2
- x = x - 1
- dx = xi - x
- xi = x
- 'pete's variation 2019-02-12
- w2 = a * a
- h2 = b * b
- h2w2 = h2 * w2
- xi = a
- dx = 0
- y = 0
- y = y + 1
- yyw2 = y * y * w2
- x = xi - dx + 1
- x = x - 1
- dx = xi - x
- xi = x
- 'vince variation on Steve 2019-02-12
- a = 2 * rx * rx
- b = 2 * ry * ry
- x = 0
- y = ry
- dx = ry * ry
- dy = rx * rx * (1 - 2 * ry)
- e = 0
- sx = 0
- sy = a * ry
- x = x + 1
- sx = sx + b
- e = e + dx
- dx = dx + b
- y = y - 1
- sy = sy - a
- e = e + dy
- dy = dy + a
- x1 = x0 - x
- x2 = x0 + x
- y1 = y0 - y
- x = rx
- y = 0
- dx = ry * ry * (1 - 2 * rx)
- dy = rx * rx
- e = 0
- sx = b * rx
- sy = 0
- x3 = x0 - x
- y = y + 1
- sy = sy + a
- e = e + dy
- dy = dy + a
- x = x - 1
- sx = sx - b
- e = e + dx
- dx = dx + b
- 'pete's reversion back to SQR WTH? it's fine time wise!
- 'pete's final? 2019-02-12 variation
- w2 = a * a
- h2 = b * b
- h2w2 = h2 * w2
- x = a
- y = y + 1
- yyw2 = y * y * w2
- 'bplus reversion back to SQR nope over twice the time!
- scale = yRadius / xRadius
- xr2 = xRadius * xRadius
HA! I see a Y = 0 in circle fill code, maybe we could apply what we have learned to optimize it more. Radius = ABS(R) ???
Post by: Pete on February 12, 2019, 03:15:48 pm
[ This attachment cannot be displayed inline in 'Print Page' view ]
Post by: bplus on February 12, 2019, 03:20:44 pm
I will try this in 32 bit QB64.
BTW, be sure to run tests with Browser OFF.
Post by: Pete on February 12, 2019, 03:25:09 pm
OK 3 more tests with browser off. 225 total seconds for 3 runs for mine, 227 total seconds for Circle Fill. Basically a tie of 75 seconds each. Funny that both were slower with the browser off, but with so many things in Windows running in the background, who knows?
Pete
Post by: bplus on February 12, 2019, 04:13:28 pm
Quote
My system is Windows 10 64 bit laptop, intel core i5
Running tests on QB64, 32 bit version
circle Fill Pete's Fill
14.3945 14.5039
14.3945 14.3984
14.2891 14.3945
14.2851 14.3984
14.3945 14.4039
circle Fill STATIC Fill mod B+
14.2305 14.4531
14.2891 14.4492
14.3945 14.4531
14.1758 14.3984
14.2305 14.3984
Running tests on QB64, 64 bit version
circle Fill Pete's Fill
16.8672 17.0313
16.9258 16.8672
16.8125 16.9219
16.8125 16.8125
16.8711 17.0352
circle Fill STATIC Fill mod B+
16.9219 16.9766
16.9258 16.9766
16.8164 16.8711
16.8125 16.8672
16.8125 16.8125
Post by: Pete on February 12, 2019, 05:04:24 pm
The double draw method Steve submitted is about 20% slower, and the changes Vince made slowed it down about 20% more. Oops. Feel free to challenge that, anyone.
I don't think I want to bother making a hash table form here, but that's where I'd go next to remove SQR from my modification. If we can establish that there is a limit for how wide an ellipse can be, then that's certainly possible. I'm only presuming it would be faster though, I don't know for certain.
I favor the SQR one I came up with, just because it is so simplistic. It would also piss off the C people who posted the other one Bill found, with the inner x loop. Pissing off C people with BASIC just makes me happy! Oh, if you guys think I'm the only one, check this out, it's hilarious... https://social.microsoft.com/Forums/en-US/ed0e97aa-ea86-49dd-b5b0-01fd41c82cf2/using-com-port-with-qb64
Although... who knows, maybe someone will post some other method that eats our collective lunch. Stay tuned!
Pete
Post by: STxAxTIC on February 12, 2019, 05:25:44 pm
Post by: Pete on February 12, 2019, 06:06:56 pm
That's why I like to use unique variables, like pete!
Well kudos for grinding it out on your own! I was about half way there, when you posted. After that, I looked around at some stuff on the net and determined I was just heading in the same direction, except that SQR thing was bugging me, so I went on with that after making some tests to see if Steve's find was out of the running. I couldn't see how working on the boob effect would be productive, if the routine ended up being slower, which it is. So on to this single draw system, which looks like the one we will wind up with, unless someone
This is fun stuff, and again kudos. What we need now is either a new method or a way to speed up that SQR calculation in my modification. I wonder how much the internal works grinds out the SQR calculations? It only needs to be rounded as an integer. I mean we could use a square root algorithm to do that, since a hash table is a bit of overkill. It's still a bit tricky to calculate square roots, and requires loops to approximate, even with the "trick" division.
Pete
Post by: STxAxTIC on February 12, 2019, 06:18:21 pm
The one with the ascii *-characters in the curved shape is a dead ringer for my method. They even use the same Leibnitz "dx" notation for the tiny increments because this is the same exact setup used to find the area of the ellipse. Calculus is a language after all, you say certain things the same way. Staring at it harder: yikes, do they not have a LINE statement?
I see someone even attempted to do the tilted case but chickened out before arriving at any code. I know exactly why this is, and is why I was so stubborn about solving that issue this week too. The reason? A tilted ellipse does not permit (that I could derive) a strict XY-equation for its position - there's always an extra parameter. After conceding to this, I unleashed the tilted function that takes the punch and uses an extra variable.
At this exact point, I'm not even sure which is the fastest anymore. As the dust settles on this, can anyone (namely Pete or bplus) paste the newest and the greatest below this? Are we going to need a separate function for just circles?
Post by: Pete on February 12, 2019, 11:22:21 pm
The two fastest routines are yours, as modified with different variable types and DO/LOOP replacing FOR/NEXT, and yours with my modifications to substitute SQR for the inner loop. The SQR one is just a tad faster in my tests.
Guys: Do you know in th e last loop x is always zero? That means this routine puts down a horizontal line and dots the top and bottom of any ellipse. I hope that's OK with everyone. Oh, to see what I'm yacking about, here are the numbers...
Code: QB64: [Select]
- w2 = a * a
- h2 = b * b
- h2w2 = h2 * w2
- y = y + 1
- yyw2 = y * y * w2
- PRINT "============================="
I got rid of one more line and a variable in my SQR code. I'll repost it here. What I want to do now is compare it with ellipses of varying size. I also want to make sure I'm getting the same x values as the one that avoids SQR with an inner loop.
Latest SQR code:
Code: QB64: [Select]
- w2 = a * a
- h2 = b * b
- h2w2 = h2 * w2
- y = y + 1
You have to admit, it's pretty freakin' optimized.
Edit: removed unnecessary x = a statement. Thanks Mark!
Pete
Post by: bplus on February 12, 2019, 11:33:30 pm
Post by: Pete on February 13, 2019, 12:02:29 am
Pete
Post by: SMcNeill on February 13, 2019, 12:25:05 am
Code: QB64: [Select]
- w2 = a * a
- h2 = b * b
- h2w2 = h2 * w2
- y = y + 1
Post by: SMcNeill on February 13, 2019, 12:31:05 am
Code: QB64: [Select]
- y = y + 1
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?
Post by: Pete on February 13, 2019, 01:23:32 am
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]
- PRINT "Width = 300 Height ="; i
- w2 = a * a
- h2 = b * b
- h2w2 = h2 * w2
- y = y + 1
I wish I knew more about colors to add better contrast. :(
Pete
Post by: STxAxTIC on February 13, 2019, 09:32:41 am
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]
... 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!
Post by: bplus on February 13, 2019, 10:03:28 am
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.
Post by: Pete on February 13, 2019, 11:56:16 am
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
Post by: SMcNeill on February 13, 2019, 12:15:58 pm
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! ;)
Post by: bplus on February 13, 2019, 01:24:09 pm
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".
Post by: Pete on February 13, 2019, 02:24:12 pm
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
Post by: bplus on February 13, 2019, 03:48:54 pm
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.
Post by: SMcNeill on February 13, 2019, 03:52:06 pm
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.
Post by: Pete on February 13, 2019, 04:02:17 pm
Pete
Post by: bplus on February 13, 2019, 04:08:37 pm
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, OK draw the pixel or line then.
Pete
Post by: bplus on February 13, 2019, 04:17:53 pm
Code: QB64: [Select]
Post by: SMcNeill on February 13, 2019, 04:23:21 pm
X = _ROUND(SQR(....
Post by: Pete on February 13, 2019, 04:24:15 pm
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
Post by: Pete on February 13, 2019, 04:29:36 pm
Pete
Post by: STxAxTIC on February 13, 2019, 06:20:34 pm
- I like the idea of having a CircleFill function being a special case of an EllipseFill function curried down to have a=b=r. Let's keep that idea fo sho.
- Since the tilted ellipse is a different beast than the flat one, I think a two-function dichotomy is the way to go on that issue. If one breaks in the future for some ungodly reason, someone won't be tempted to toss out both. Plus all that trig might intimidate some folks.
- As for the questions about individual pixels, dots on each end, and so on - there's a relatively simple way to settle this using the area equation. Namely, the area of an ellipse is precisely pi*a*b. So this means: Count the number of pixels put on screen for any given fill method, whether it be with or without those extra dots. Whichever one gets closest to pi*a*b is the one that best matches theory, so we keep that.
- Is an ellipse/circle of radius 1 just a point? Mathematics says no. A circle of radius zero is actually a point. Demonstrating this for a circle centered at the point (h,k), we would have:
(x-h)^2 + (y-k)^2 = 0^2
(x-h)^2 = -(y-k)^2
x = h + sqrt(-(y-k)^2)
... which only has real solutions at x=h, y=k. So again, a point on screen corresponds to zero radius, in fact.
If you want to fill a single pixel with a nonzero-radius-circle, your radius would need to be 0.5 in order to have a diameter of 1.
For a radius of 1, you're now talking about a diameter of 2. At single-pixel resolution, this is again troublesome, because the next symmetric shape would be four pixels:
**
**
which in fact has a radius of sqrt(2)=1.41... so we're simply fighting the properties of the computer screen at that point.
Post by: STxAxTIC on February 13, 2019, 07:52:33 pm
So we're probably straining at gnats at this point. I came up with a test setup for counting the number of pixels in the ellipse to run it by the expected value. In the code below, I tuned a "fudge factor" to give the correct answer to within 0.08 pixels or so, but this is no reason to get excited. If you simply swap the a- and b- axes (rotate the ellipse 90 degrees), the area should still be the same right? Nope, it's off by 16 pixels for the same exact shape. Right away this tells me that we'll never get the precision we want on a screen without infinite resolution.
Needless to mention, the fudge factor doesn't work for any ellipse besides the test case, so I think our level of pedantic-ness can stop right around here.
Here's my test setup for that:
Code: QB64: [Select]
- aaa = 75 ' SWAP THESE TO TEST
- bbb = 150
- area = 0
- w2 = a * a
- h2 = b * b
- h2w2 = h2 * w2
- y = y + 1
In conclusion, after fiddling with this for a second, we should just draw what looks good.
Post by: STxAxTIC on February 14, 2019, 09:34:47 am
One last question for bplus, about the modified tilted ellipse routine... Do we still need the first argument in this function? It's not referenced inside the SUB at all.
Code: QB64: [Select]
- mx2 = max + max
- _DEST tef&
- _SOURCE tef& 'point wont read without this!
- lasti = i: lastj = j
- x = 0
- x = x + 1
- xleft(y) = x
- x = x + 1
- x = x + 1
- _DEST destHandle&
- _FREEIMAGE tef&
Post by: bplus on February 14, 2019, 10:17:13 am
Going once, going twice... SOLD on regular ellipses and circles.
One last question for bplus, about the modified tilted ellipse routine... Do we still need the first argument in this function? It's not referenced inside the SUB at all.Code: QB64: [Select]
Sure it is, and it is vital. Just before drawing the lines this is set in code:
Code: QB64: [Select]
- _DEST destHandle&
It then draws those lines at the destination.
Here is a demo app:
Code: QB64: [Select]
- c = xmx / 2
- stepper = stepper + 30
- TiltedEllipseFill 0, x, y, 250 - stepper, stepper, a + offset, k
- _LIMIT 12
- mx2 = max + max
- _DEST tef&
- _SOURCE tef& 'point wont read without this!
- lasti = i: lastj = j
- x = 0
- x = x + 1
- xleft(y) = x
- x = x + 1
- x = x + 1
- _DEST destHandle&
- _FREEIMAGE tef&
After playing around trying to remove Dot at top and bottom, I have decided CircleFill draws a much more pleasing symmetric circle without dots and slightly faster than best FlatEllipseFill. If you try a CIRCLE overlap test over CircleFill you will see overlap all the way around the edge or mostly. If you do a CIRCLE overlap test for FlatEllipseFill, you will see a dotted border overlap all the way around the edge ie not such a good fit. Therefore, CircleFill is staying in my tool box.
You can do FlatEllipse with CIRCLE sub but I doubt the outline would fit our best FlatEllipseFill, therefore FlatEllipseFill will need a partner FlatEllipse sub or a switch to do just the outlines, I favor the latter, one sub with a switch for filling or not.
In my opinion QB64 should be doing these things with Circle as it does with LINE with an "F" switch, THEN all that would be needed is what we have for TiltedEllipse with an tfFill switch.
I wonder what the code for CIRCLE looks like from under-the-hood, how hard would it be to update that?
Post by: SMcNeill on February 14, 2019, 10:49:08 am
Code: QB64: [Select]
- mx2 = max + max
- _DEST tef&
- _SOURCE tef& 'point wont read without this!
- lasti = i: lastj = j
- x = 0
- x = x + 1
- xleft(y) = x
- x = x + 1
- x = x + 1
- _DEST destHandle&
- _FREEIMAGE tef&
These lines seem odd to me:
WHILE POINT(x, y) = prc AND x < mx2
x = x + 1
WEND
WHILE POINT(x, y) <> prc AND x < mx2
x = x + 1
WEND
Isn't this a case of WHILE x < mx 2 ??
If POINT(x,y) = prc then we increment x... If POINT(x,y) <> prc then we increment x... Is there even a need for those checks?
Post by: STxAxTIC on February 14, 2019, 11:05:59 am
EDIT
On second thought, the only shape not inherently "covered" (no pun) in QB64 is the un-filled, tilted ellipse. It covers all the rest.
Post by: bplus on February 14, 2019, 11:23:56 am
Steve:
Quote
These lines seem odd to me:
I am sure they may seem odd to anyone, who hasn't tried drawing the lines at angles = yuck!
In order to have a pretty filled titled ellipse without overlap nor holes, you have to draw either vertical or horizontal lines or if you are really good, draw non overlapping boxes (which I think Vince attempted at one point).
To do this I used STATIC's formula's to draw the ellipse in an isolated area.
Then I went from top to bottom down the y axis and with the help of POINT found the left and right edge of the ellipse along the flat line. This is why the ellipse had to be drawn in an isolated area, so POINT only finds the ellipse points.
With the edges detected along flat lines we can draw a clean,no hole, no overlapping Tilted Ellipse Fill, at the place designated at destHandle&.
This is the code block that is finding the left and right edges of the tilted ellipse drawn in the isolated area:
Code: QB64: [Select]
- x = 0
- x = x + 1
- xleft(y) = x
- x = x + 1
- x = x + 1
You have to find the edges on the same line and you have 3 cases:
1. no edge
2. the left and right edge are the same
3. the left and right edge are different
The added condition
AND x < mx2
keeps x inside the bounds of the isolated drawing area when one or no POINTs are found.
Finally, when you go to draw the actual lines, you must make sure xLeft(y) is not at the right boundry ie no point of the ellipse was found for that y value.
Post by: STxAxTIC on February 14, 2019, 11:38:44 am
bplus is right about the inherent CIRCLE command (with eccentricity) not perfectly agreeing without our results. The difference is SO minuscule that our algorithms should probably not change though. Check out this simple mod that lets you send two colors to the ellipse function, with one color being just for the outline. We won't be keeping this of course:
Code: QB64: [Select]
- ' Video settings, Global declarations:
- ' FUNCTIONs and/or SUBs:
- ' ox = center x coordinate
- ' oy = center y coordinate
- ' a = semimajor axis
- ' b = semiminor axis
- ' col1 = outline color
- ' col2 = fill color
- w2 = a * a
- h2 = b * b
- h2w2 = h2 * w2
- y = y + 1
I suppose the a possible best solution it to just draw the thing, PAINT the inside like I did a few pages ago, and let the user place that on screen using image handles
EDIT
This will work fastest for the tilted case, as its our only option.
For nontilted things, I guess the challenge is back out there? Oh god...
Post by: bplus on February 14, 2019, 11:51:01 am
Quote
I suppose the best solution it to just draw the thing, PAINT the inside like I did a few pages ago, and let the user place that on screen using image handles.
As I recall, we had discovered PAINT is slow and doesn't do alpha... I listed problems of PAINT way back in this thread. This is why the Tilted Ellipse Fill routine jumps through so many hoops to avoid it!
Again I say, can we do something with QB64 CIRCLE routine ie add fills to what it already does?
Post by: STxAxTIC on February 14, 2019, 12:00:27 pm
Quote
Again I say, can we do something with QB64 CIRCLE routine ie add fills to what it already does?
I defer you to [banned user] on that one...
Post by: bplus on February 14, 2019, 12:24:43 pm
In meantime, I am keeping CircleFill in my tool box and IMO it should go in the forum's as the number 1 entry!
When I need an ellipse fill (and really how often is that?), I will use Titled Ellipse Fill (and no Fill switch?) because that code automatically includes the ability to do Flat Ellipses. This is the one with Steve's S and D fix.
If I really need speedier Flat Ellipses then STATIC's fudge of Pete's variation will do fine!
But I am trying to imagine Titled Ellipse No Fill, it could be draw directly to source no fooling around with isolated drawing. So build a switch onto Tilted Ellipse Fill or a whole separate sub? This is the question that remains for me because the requirements are so different.
Post by: bplus on February 14, 2019, 12:57:54 pm
Code: QB64: [Select]
- 'compare to CIRCLE with aspect = a/b
- k$ = ""
- mx2 = max + max
- _DEST tef&
- _SOURCE tef& 'point wont read without this!
- lasti = i: lastj = j
- x = 0
- x = x + 1
- xleft(y) = x
- x = x + 1
- x = x + 1
- _DEST destHandle&
- _FREEIMAGE tef&
Post by: STxAxTIC on February 14, 2019, 01:09:49 pm
Quote
OK maybe one of these days I will dig into the Source Code...
Here's what you do. Find every instance of CIRCLE in the qb64 source code, and make a copy of it - CIRCLE2 or whatever. As soon as you can use CIRCLE2 to completely replace circle, you're ready to do the filling and rename CIRCLE2 to whatever. If successful, the result will be your occult object and not much more unfortunately, it was decided long ago that we won't add this kind of stuff to the language itself until someone clearly and intelligently defines when to stop. That has never occurred and I doubt it will.
Quote
In meantime, I am keeping CircleFill in my tool box...
Based on the outline/pixels issue, I agree with this. Do you mind posting your freshest copy of the function? Be sure to nerf it down to handle just circles, which I imagine render without boobs.
Quote
...and IMO it should go in the forum's as the number 1 entry!
If the Librarian can figure out how to arrange posts alphabetically instead of by date, you may have your wish on this until an A- or B- named function claims the #1 spot.
Quote
If I really need speedier Flat Ellipses then STATIC's fudge of Pete's variation will do fine!
Something tells me you swapped the names here, but who's keeping track? Authors/contributors/useful testers will be credited in alphabetical order in the Toolbox forum. Whoever wants to do the research can click the link to this thread any they can see who worked on what.
Quote
But I am trying to imagine Titled Ellipse No Fill, it could be draw directly to source no fooling around with isolated drawing. So build a switch onto Tilted Ellipse Fill or a whole separate sub? This is the question that remains for me because the requirements are so different.
That's a great issue. I prefer our tooling stay as pure as possible, i.e. avoiding anything that brings in complexity with underscore commands, image handles, and all that, so long as it does the best job. (Just a weird preference.) Since unfilled ellipses are just PSET and LINE, I'm all about having two functions, one for filled, one for unfilled.
Post by: STxAxTIC on February 14, 2019, 01:12:57 pm
Quote
For the record, Titled Ellipse Fill does not compare well with CIRCLE with same radius as a and aspect b/a. Look at what happens when b exceeds a! but I am supposed to switch radius for CIRCLE when b > a.
Are you knocking down straw men intentionally, or just need some coffee?
Post by: bplus on February 14, 2019, 02:06:42 pm
QuoteFor the record, Titled Ellipse Fill does not compare well with CIRCLE with same radius as a and aspect b/a. Look at what happens when b exceeds a! but I am supposed to switch radius for CIRCLE when b > a.
Are you knocking down straw men intentionally, or just need some coffee?
I could use some more sleep but I am seeing with the comparison code that CIRCLE must be drawing ellipse (using aspect) with an entirely different method than any discussed here ie pretty good overlap on left side, complete miss on right.
Post by: SMcNeill on February 14, 2019, 02:53:17 pm
From memory, first section of code is declarations, followed by boundary checks (make certain the circle is being drawn inside the viewports), followed by the actual plotting routine at the end.
One thing to keep in mind: Circle also plots arcs; not just circles. To adapt the existing code to a fill routine, you’d basically need to plot lines inside that arc routine.
Which, really, I wouldn’t mind seeing a fast arc fill routine to boot. ;)
Post by: bplus on February 14, 2019, 10:57:53 pm
Quote
In meantime, I am keeping CircleFill in my tool box...STATIC
Quote
Based on the outline/pixels issue, I agree with this. Do you mind posting your freshest copy of the function? Be sure to nerf it down to handle just circles, which I imagine render without boobs.
Code: QB64: [Select]
- 'from Steve Gold standard
- RadiusError = -Radius
- X = Radius
- Y = 0
- ' Draw the middle span here so we don't draw it twice in the main loop,
- ' which would be a problem with blending turned on.
- WHILE X > Y
- RadiusError = RadiusError + Y * 2 + 1
- X = X - 1
- RadiusError = RadiusError - X * 2
- Y = Y + 1
Here is consolidation of speed tests with other Circle Fills tried:
Code: QB64: [Select]
- _TITLE "Circle Fill speed tests"
- _DELAY 1
- ntests = 100000 'it takes a really long run to prove Gold Standard Speed 167.9 versus vince 168.1
- ntests = 1000 'fast elimination
- 'It has been noticed that the one going first has a disadvantage
- _PRINTSTRING (700, 615), "Time for" + STR$(ntests) + " Gold Standard Circle Fills:" + STR$(finish##)
- ' ==================================================== the contender on left of screen
- start## = TIMER
- 'from Steve Gold standard
- RadiusError = -Radius
- X = Radius
- Y = 0
- ' Draw the middle span here so we don't draw it twice in the main loop,
- ' which would be a problem with blending turned on.
- WHILE X > Y
- RadiusError = RadiusError + Y * 2 + 1
- X = X - 1
- RadiusError = RadiusError - X * 2
- Y = Y + 1
- 'vince's circle fill this one does not bother with types good almost identical to Steve's
- x0 = r
- y0 = 0
- e = -r
- y0 = y0 + 1
- e = e + 2 * y0
- x0 = x0 - 1
- e = e - 2 * x0
- 'this does not overlap with circle well 2.13 x's Gold Time
- r2 = r * r
- x = 1
- xstop = r + 1
- x = x + 1
- 'andy amaya's version from SB, way too much overlapping! Junk as is but 1.1 Gold Standard Time
- x = R
- y = 0
- Xchange = 1 - 2 * R
- yChange = 1
- RadiusError = 0
- WHILE x >= y
- y = y + 1
- RadiusError = RadiusError + yChange
- yChange = yChange + 2
- x = x - 1
- RadiusError = RadiusError + Xchange
- Xchange = Xchange + 2
- 'fCirc but doing octants until get to square, then just do square fill! 1.18 Gold Sdt
- 'this is closer to matching the Gold Standard
- r2 = r * r
- t = r 'r - 1 gets rid of nipples but...
- tstop = r * .707106781
- t = t - 1
- 'add a routine for sqr root 1,16 X's Gold Std
- r2 = r * r
- t = r 'r - 1 gets rid of nipples but...
- tstop = r * .707106781
- 'VVVVVVVVVVVVVVVVVVV this might now save a shade off SQR
- s = r2 - t * t
- dist = s / 10
- dist2 = dist * dist
- 'WHILE ABS(dist ^ 2 - s) >= 1 'no! avoid function calls!
- dist = .5 * (dist + s / dist)
- dist2 = dist * dist
- 'VVVVVVVVVVVVVVVVV faster to use this YES
- 'dist = SQR(r2 - t * t) ' + .5 for rounding down
- t = t - 1
- 'too slow, dest can't just be 0 Junk as is
- _DEST a&
- _DEST 0
- x1 = x2: y1 = y2
- _FREEIMAGE a& '<<< this is important!
Here is consolidation of size and overlap with circle tests (checking for nipples, or dots... BTW discovered from these tests, the CIRCLE sub overlaps itself at 0, 90, 180, 270 degrees!):
Code: QB64: [Select]
- _TITLE "CircleFill Overlap test"
- 'B+ 2019-02-10 resave this code to
- 'just test this code for proper filling without overlap, timed tests are else where
- PRINT "Radius"; i; " press any to add until get to 200, <backspace> to go back one, <esc> for next test."
- 'CIRCLE (500, 350), i, _RGBA(255, 255, 255, 40)
- k$ = ""
- 'from Steve Gold standard
- RadiusError = -Radius
- X = Radius
- Y = 0
- ' Draw the middle span here so we don't draw it twice in the main loop,
- ' which would be a problem with blending turned on.
- WHILE X > Y
- RadiusError = RadiusError + Y * 2 + 1
- X = X - 1
- RadiusError = RadiusError - X * 2
- Y = Y + 1
- 'vince's circle fill this one does not bother with types good almost identical to Steve's
- x0 = r
- y0 = 0
- e = -r
- y0 = y0 + 1
- e = e + 2 * y0
- x0 = x0 - 1
- e = e - 2 * x0
- 'this does not overlap with circle well
- r2 = r * r
- x = 1
- xstop = r + 1
- x = x + 1
- 'andy amaya's version from SB, way too much overlapping! Junk as is
- x = R
- y = 0
- Xchange = 1 - 2 * R
- yChange = 1
- RadiusError = 0
- WHILE x >= y
- y = y + 1
- RadiusError = RadiusError + yChange
- yChange = yChange + 2
- x = x - 1
- RadiusError = RadiusError + Xchange
- Xchange = Xchange + 2
- 'fCirc but doing octants until get to square, then just do square fill!
- 'this is closer to matching the Gold Standard
- r2 = r * r
- t = r 'r - 1 gets rid of nipples but...
- tstop = r * .707106781
- t = t - 1
- 'add a routine for sqr root
- r2 = r * r
- t = r 'r - 1 gets rid of nipples but...
- tstop = r * .707106781
- 'VVVVVVVVVVVVVVVVVVV this might now save a shade off SQR
- s = r2 - t * t
- dist = s / 10
- dist2 = dist * dist
- 'WHILE ABS(dist ^ 2 - s) >= 1 'no! avoid function calls!
- dist = .5 * (dist + s / dist)
- dist2 = dist * dist
- 'VVVVVVVVVVVVVVVVV faster to use this YES
- 'dist = SQR(r2 - t * t) ' + .5 for rounding down
- t = t - 1
- 'terrible overlap too slow, dest can't just be 0 Junk as is
- _DEST a&
- _DEST 0
- x1 = x2: y1 = y2
- _FREEIMAGE a& '<<< this is important!
Post by: STxAxTIC on February 15, 2019, 12:08:10 am
Post by: bplus on February 15, 2019, 10:12:34 am
I swear I wanted to lay this thing to rest like 5 pages ago... Are you saying the so-called gold standard function overlaps itself at the cardinal points 0, pi/2, pi, 3pi/2? Wouldn't that make it bronze or worse?
NO! I am saying THE QB64 CIRCLE function is overlapping itself at the named angles.
Here is a demo that makes it clear as a bell:
Code: QB64: [Select]
Quote
I swear I wanted to lay this thing to rest like 5 pages ago...
Voltaire — 'The secret of being a bore is to tell everything.'
The Gold Standard is even better than THE QB64 CIRCLE sub in this respect!
Code: QB64: [Select]
- 'from Steve Gold standard
- RadiusError = -Radius
- X = Radius
- Y = 0
- ' Draw the middle span here so we don't draw it twice in the main loop,
- ' which would be a problem with blending turned on.
- WHILE X > Y
- RadiusError = RadiusError + Y * 2 + 1
- X = X - 1
- RadiusError = RadiusError - X * 2
- Y = Y + 1
Post by: bplus on February 15, 2019, 10:46:17 am
Quote
Circle is easy to find, complicated to work on. Just open libqb.cpp and search “circle”— it’s the first result I found. (Sub__circle, or something similar, is the actual name.)
Thanks Steve, found it and see why no one wants to mess with it! Yeeou-sa! It seems it's main concern is handling the arcs, and yet we still have to fix the arcs if we want to PAINT pie slices with it.
Post by: _vince on February 15, 2019, 11:02:04 am
bplus is right about the inherent CIRCLE command (with eccentricity) not perfectly agreeing without our results. The difference is SO minuscule that our algorithms should probably not change though.
https://www.qb64.org/forum/index.php?topic=287.msg1806#msg1806 (https://www.qb64.org/forum/index.php?topic=287.msg1806#msg1806)
want to know why?
Post by: STxAxTIC on February 15, 2019, 11:34:05 am
Am I gonna be killed by assassin for depicting the prophet like that? (I'll be waiting for you.)
So this means CIRCLE has a bug. We should start a new thread for that where it belongs if nobody has yet.
Post by: bplus on February 15, 2019, 12:08:21 pm
bplus is right about the inherent CIRCLE command (with eccentricity) not perfectly agreeing without our results. The difference is SO minuscule that our algorithms should probably not change though.
https://www.qb64.org/forum/index.php?topic=287.msg1806#msg1806 (https://www.qb64.org/forum/index.php?topic=287.msg1806#msg1806)
want to know why?
My guess after peeking into the qblib.cpp file, circle sub, that they are using Double Precision and Gold Standard is using Integers and the LINE sub rounds things it's own way. :)
Post by: bplus on February 15, 2019, 12:14:01 pm
I ain't religious but "Dammit Allah", said Mohamed :-(
Am I gonna be killed by assassin for depicting the prophet like that? (I'll be waiting for you.)
So this means CIRCLE has a bug. We should start a new thread for that where it belongs if nobody has yet.
Don't think anyone is going to mess with CIRCLE to fix it, it is an extremely rare case where the overlap bug enters awareness. Look how long it took me to run across it. Just file it under weird things about CIRCLE like the problem with arcs and PAINTING pie slices.
Post by: FellippeHeitor on February 15, 2019, 01:02:31 pm
Don't think anyone is going to mess with CIRCLE to fix it, it is an extremely rare case where the overlap bug enters awareness. Look how long it took me to run across it. Just file it under weird things about CIRCLE like the problem with arcs and PAINTING pie slices.
One question I haven't seen asked here yet (I just skimmed, may have missed it) is: Did QB4.5 do the same? If the odd behavior was already there, then CIRCLE should remain "buggy" concerning those middle lines.
That wouldn't prevent a new circle implementation to be added.
Not adding a new _CIRCLE command - that would be ridiculous -, but adding a new switch to the old existing CIRCLE command sounds feasible - one for the filled version, maybe another for an anti-aliased alternative routine that doesn't contain the vice of yore, what have you.
Who's willing to get their hands dirty with c code?
Post by: FellippeHeitor on February 15, 2019, 01:06:52 pm
Post by: STxAxTIC on February 16, 2019, 01:41:18 am
I made an effort to unify the notation, so if you *do* have an edit to make, use what's posted below, or make sure the notation is maintained.
EDIT
Opps, didn't add the un-filled, yes-tilted ellipse yet. Luckily this is so easy even *I* can do that, as it won't be needing any newfangled underscore technology. Just my original post without the PAINT statement.
Code: QB64: [Select]
- ' CX = center x coordinate
- ' CY = center y coordinate
- ' R = radius
- ' C = fill color
- RadiusError = -Radius
- X = Radius
- Y = 0
- WHILE X > Y
- RadiusError = RadiusError + Y * 2 + 1
- X = X - 1
- RadiusError = RadiusError - X * 2
- Y = Y + 1
- ' CX = center x coordinate
- ' CY = center y coordinate
- ' a = semimajor axis
- ' b = semiminor axis
- ' C = fill color
- w2 = a * a
- h2 = b * b
- h2w2 = h2 * w2
- y = y + 1
- ' destHandle& = destination handle
- ' CX = center x coordinate
- ' CY = center y coordinate
- ' a = semimajor axis
- ' b = semiminor axis
- ' ang = clockwise orientation of semimajor axis in radians (0 default)
- ' C = fill color
- mx2 = max + max
- _DEST tef&
- _SOURCE tef&
- lasti = i: lastj = j
- x = 0
- x = x + 1
- xleft(y) = x
- x = x + 1
- x = x + 1
- _DEST destHandle&
- _FREEIMAGE tef&
Post by: Pete on February 16, 2019, 03:56:10 am
Wow, who'd ah thunk this project would have us going around in circles? I guess we all should have seen that one coming. Well now that's it's over, I'd have to say it's been a blast. It's the second group project I've taken part in over 25 years and amazingly enough, both times everybody got along really well from start to finish. You guys rock and thinks for letting me participate!
Pete
Post by: STxAxTIC on February 16, 2019, 09:40:27 am
https://www.qb64.org/forum/index.php?topic=1069.msg102619 (https://www.qb64.org/forum/index.php?topic=1069.msg102619)
Post by: bplus on February 16, 2019, 09:52:04 am
Alrighty, considering using this for the final submission. Super bare-bones as it should be (whoever wants some backstory will be able to click a link to this thread). The obvious contributors are, in ABC order, bplus, pete, smcneill, and yours truly. Anyone not in favor, speak now or forever hold your peace. (I'm interested in moving on to the next thing, as is probably everyone.)
I made an effort to unify the notation, so if you *do* have an edit to make, use what's posted below, or make sure the notation is maintained.
EDIT
Opps, didn't add the un-filled, yes-tilted ellipse yet. Luckily this is so easy even *I* can do that, as it won't be needing any newfangled underscore technology. Just my original post without the PAINT statement.Code: QB64: [Select]
A couple of things just from quick scan of Bill's 2nd final complete code post (above):
Bill:
Quote
Opps, didn't add the un-filled, yes-tilted ellipse yet. Luckily this is so easy even *I* can do that, as it won't be needing any newfangled underscore technology. Just my original post without the PAINT statement.
Bill that had problems using the Cartesian coordinate system with y-axis flipped and angles increasing in counter-clockwise direction. Build the Tilted Ellipse code from the TiltedEllipseFill code.
The a and b parameters represent NOT the major and minor axis respectively but the x and y axis respectively ie a is not always greater than or equal to b. And the angle of tilt when 0, would put the a radius parallel with the x-axis.
Post by: STxAxTIC on February 16, 2019, 09:54:03 am
ask Fell or luke for librarian creds
Post by: bplus on February 16, 2019, 10:00:26 am
OK tested EllipseTilt and Bill did not use the original one without the PAINT because the current one fits TiltedEllipseFill and is changing angle correctly to Basic system coordinates. I still object to descriptions of a and b parameters and offer an alternate wording closer to the actual facts.
Code: QB64: [Select]
- CX = 500
- CY = 350
- a = 100
- b = 340
- mx2 = max + max
- _DEST tef&
- _SOURCE tef& 'point wont read without this!
- lasti = i: lastj = j
- x = 0
- x = x + 1
- xleft(y) = x
- x = x + 1
- x = x + 1
- _DEST destHandle&
- _FREEIMAGE tef&
- ' CX = center x coordinate
- ' CY = center y coordinate
- ' a = Flat ellipse x-axis '<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< B+ changed comment
- ' b = Flat ellipse y-axis '<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< B+ changed comment
- ' ang = clockwise orientation of semimajor axis in radians (0 default)
- ' C = fill color
- i = i + CX
- j = -j + CY