Rasterizing an ellipse

Question

Is there a efficient algorithm out there to find the indicies of pixels in a general ellipse?

Essentially, what I want to do is to find the indicies in a two dimensional array that corresponds to a parameterized ellipse that spans over the "2-D surface" of possible array indicies. This problem can, as in my first Q above, be compared to the rasterization of an ellipse.

I have found some Scan Line algorithms that do what I want for axis-aligned ellipses, but now I wonder if there are any similar ones for ellipses that are skewed and rotated. There must be since vector graphics SW out there manage to fill ellipses that are skewed and/or rotated.

To clearify what I mean, I recently had one similar question to this resolved here: Special polygonial for loop in two dimensional array

/Nick

Answer 1

You can take the algorithms that you've found for rasterizing an ellipse and simply apply a rotation or skew transform to the coordinates before testing whether they're inside or outside the ellipse. For example, if you want to test for an ellipse rotated 45 degrees, you could do something like this:

for (x = 0; x < maxX; x++)
{
    for (y = 0; y < maxY; y++)
    {
        double newX, newY;
        Transform (x, y, rotationMatrix, &newX, &newY);
        if (PointInEllipse (newX, newY, ellipse))
        {
            ...do whatever here....
        }
    }
}

Where Transform simply applies a 2x2 rotation matrix to x and y and puts the result in newX, newY.

Answer 2

I would recommend triangulating your ellipse and using the standard triangle fill routines, odds are good that is how it is done by most graphics APIs, as OpenGL and DirectX tend to only be able to draw triangles at the end of the day.

A simple triangulation of an ellipse looks like a pizza except scaled outwards. If you need higher quality, you just up the number of slices in the pizza.