2008-05-03

Ellipses

The SuperBitmap class now has a drawEllipse() function. Another one off the SourceForge list.

I “borrowed” the function from this site:

http://enchantia.com/software/graphapp/doc/tech/ellipses.html

I’m not entirely sure what the licence for this is. It’s an implementation of Doug McIlroy’s (Bell Labs?) ellipse function written as part of an academic paper by someone else. The program it relates to is a graphing program with a BSD-like licence, so as Woopsi follows a similar licence I don’t imagine including it will be a problem. I’ve included an attribution comment anyway.

That site also includes a function for creating filled ellipses using filled rectangles which are, of course, Woopsi’s forte. However, the code is written in my least favourite way - short, meaningless variables. Here’s a snippet:


long t = -a2*y;
long dxt = 2*b2*x, dyt = -2*a2*y;
long d2xt = 2*b2, d2yt = 2*a2;

I bet the guys he works with love picking up his projects when he moves on to something else…

The code doesn’t compile because of signed/unsigned comparisons, and the obvious quick-fix doesn’t work. I’ll have to read the whole paper and re-write the function so that I can understand everything it’s doing and fix the problems.

If you’re trying to illustrate a point with code, use descriptive variable names. Honestly. In fact, always use descriptive variable names.

The most interesting thing about the ellipse problem is that McIlroy’s original missive, “Getting Raster Ellipses Right”, doesn’t seem to be available on the internet anywhere, despite being referenced just about every time rasterised ellipse functions are mentioned.

Comments

ant on 2008-05-03 at 22:21 said:

Yeah, I got the dx/dy bits (I vaguely remember derivation from school). But “t”? What’s t? Time? Makes no sense. “a” and “b”, which I probably didn’t post, are the horizontal and vertical radii of the ellipse, whilst “a2” and “b2” are the pre-calculated squares of “a” and “b”.

I really, really hate abbreviated variable names. I’m of the opinion that code should be self-commenting. Not that it should preclude actual comments, though, as they’re hugely important, but I think that code should try to make itself obvious. Calling the vertical radius “b” really doesn’t help anyone.

My theory of naming conventions is that everything should be painfully obvious. Imagine that you’re writing code that’s going to be picked up by a junior developer who has barely written any code before. If your code is obvious and well-commented, he’s going to bug you a lot less than if you’ve called all of your variables “a” and “b”.

My other scenario is that I’m picking up a project I worked on two years ago because someone’s just discovered a horrendous bug that desperately needs fixing. If I’m trawling through 10MB of sourcecode in which every variable has a single-character name, I’m going to be cursing past-me for weeks whilst I try to remember how it all works.

To be honest, I imagine that the author was working at an entirely different level to me. He just bashed the code out, assumed that it worked, and carried on with the important stuff (the rest of the paper).

Jeff on 2008-05-03 at 23:05 said:

Its a matter of context. dxt and dyt, when written with subscripts are pretty obviously first derivatives of t with respect to x (and y). Ditto d2xt is the second derivative. If you were talking about motion, you’d use words like velocity and acceleration but the maths purists tend to consider those things less clear. Its unfortunate that he also seems to use a2 for a

Donald Knuth would say “This is why I invented TeX”

Its pretty clearly buggy in that it passes both height and -height to fill_rect, in a position that only takes an unsigned int. I’d say that he’s expect it to draw from y to y+h and handle the case where h<0 means to draw from y-h to y.

Jeff on 2008-05-04 at 01:35 said:

But a2 is as close to ‘a-squared’ as you can get with identifier names, from a mathematicians perspective. (I know, we had a German mathematician in the office who did this stuff all the time).

dxt is not “delta x”, its “delta t with repect to x”. ie, if x advances by 1, how far should t advance. By hand, its normally written as “dt”

Lots of computer graphics type track ’t’ when they are walking along a curve, specifically because it maps back onto animation and extrapolation. At time t, your cursor should be at position (x,y). At some later time, t+d, your x will have advanced by some dx and your y will have advanced by dy, but its not a given that theres a simple linear relationship between t and dx (or t and dy) - in fact, its almost guaranteed that its not. However, you can usually express the position in terms of a single variable ’t’.

eg, if you were tracking around the special case of a circle, ’t’ tends to be angular displacement, and (x,y) = (r.cos(t), r.sin(t))

The trick, when doing animation, is to decide what interval you want between t values to get the best output. In the algorithm you are looking at, delta-t is not constant - instead, its computed through the bresenham algorithm; it computes which value, x or y, will change the most, then looks at how much it has to advance t to effect that change. That way, you don’t get gaps between your pixels.

As to ‘a & b’ as axis dimensions, sorry thats standard maths as well. The standard high-school definition of an ellipse is (AX)^2 + (BY)^2 = R^2 where A and B are related to the major and minor axis dimensions. And they really do use A and B.

http://www.analyzemath.com/EllipseEq/EllipseEq.html shows a different form of the equation, that deals with the origin not being (0,0)

http://en.wikipedia.org/wiki/Ellipse uses a & b as the axis sizes - though they do use slightly better variable names, but there code is nowhere near as good because it will leave gaps between pixels for large values of (a & b) since they use a discrete number of steps.

To a mathematician, it really was so self-evident what A and B represent that he didn’t notice.

Having said all that, you have a valid complaint - the problem will be coming up with more descriptive names that don’t end up obscuring what the underlying maths actually is.

Jeff on 2008-05-04 at 01:36 said:

Argh, html. When I said “its written as dt”, I meant to say “d<subscriptx>t”

ant on 2008-05-04 at 08:10 said:

Heh, a multitude of good points. I need to brush up on my maths…