[A89] Re: filling ellipses

[Prev][Next][Index][Thread]

[A89] Re: filling ellipses


> Using the algebraic formula, I came up with a function to fill an ellipse.
Unfortunately, it's
> fairly slow (it scans until it hits the edge, draws a line across, then
scans again on the next
> row).  I went ahead and used clipped drawing functions.  If anyone has any
ideas for making it
> faster, that would be great.
> jeff

Not only is it slow, but, if I'm interpreting it correctly, it's wrong.

Try doing your ellipse with an XOR.  I would expect you to get what appears
to be concentric ellipses or a sort of checkered pattern.  It's really very
simple: if your algorithm will overlap some pixels, then it will not work
with XOR!  If you're going to test each pixel _individually_, then you must
set each pixel _individually_.  Changing those lines to single pixels would
solve the XOR problem, but still be fundamentally flawed.

Now, as for why the "formula" algorithm is a very, very poor (and very
slow!) solution:

1.) It tests each pixel individually.  Other algorithms have no need to do
this, and compared to them you're looping through an absurd number of times.
I see that you're taking advantage of the symmetry to only test 1/4 of the
pixels, but that's still excruciatingly slow.

2.) It relies heavily on multiplication and division.  Much of computer
science revolves around circumventing those operations, since they are two
of the slowest operations a computer needs to perform.  The beauty of the
Bresenham ellipse algorithm is that really only requires two
multiplications, total (the multiplications by powers of two will be
converted into bit shifts, and are therefore not multiplication after
compilation) and _no_ division.  I would assume that TI uses this algorithm
internally.

3.) It uses floating point operations.  Once again, the other algorithms do
not need this.

While the code you have written will work with a modification or two, it is
entirely the wrong approach and should be simply scratched.


Now, IF you were to get the Bresenham ellipse algorithm that Olle pointed
out to work -- you'd have to find another implementation, since the one Olle
pointed out seems to have not worked when you tested it -- and IF you
changed it to use lines, as was suggested, it STILL would not work with XOR!
That's because, as long as you could have two horizontally or vertically
adjacent pixels, then you're bound to have overlapping lines.  Once again,
XOR does not like overlap.

You are then left with one solution -- draw the a solid ellipse in a buffer,
then XOR it onto the screen, just as I suggested in the first place.  And as
long as you're doing that, you can the fast, working TIOS ellipse drawing
routine.

So, in the end, you're left with only one way to draw a reasonably fast,
filled ellipse using XOR -- exactly what I suggested yesterday.  I suggest
you overcome your virtual screen stigma, since it's certainly more than easy
enough to use them.

As for XORing a VS onto the actual screen, that should be relatively simple:

void xorScreens(void *VS)                    // I think this should work
{
    unsigned long *VSptr = (unsigned long *)VS;
    unsigned long *screenptr = (unsigned long *)LCD_MEM;
    int i;

    for (i=0; i < (240/8*128)/sizeof(unsigned long); ++i)
        *(VSptr++) ^= *(screenptr++);
}

    -Scott
Follow-Ups: