26 January 2009

How to draw an ellipse

Pretty much every drawing tool and library comes with an ellipse-drawing function, so you never even need to think about how it's done. Until, one day, you're the one writing the drawing tool.

Formulae and sample code abound for calculating the outline of an ellipse. The problem is when you try to draw a nice-looking ellipse, the edge needs to be smooth, and this means half-colouring some of the pixels at the edge.

The first thing is to remember that a pixel doesn't represent a point, it represents a square. So there are two things to calculate: for any given ideal euclidean point, whether that point is inside the ellipse; and for any given square, its "insideness", ie how much of that square is covered by the ellipse. So a pixel is drawn 100% opaque if it is completely inside the ellipse, and 100% transparent if it is completely outside. Otherwise, it is drawn with a transparency proportional to its insideness.

So, if all four corners of a pixel are "inside" the ellipse, consider the pixel is 100% covered by the ellipse. If all four corners are not "inside", consider the pixel 0% covered. Otherwise, subdivide the pixel into four sub-pixels, and calculate the insideness of each sub-pixel, recursively. The percent coverage for any given pixel is the average coverage for all its sub-pixels. Below a certain threshold, don't recurse; just use the values for the corner points.

To calculate whether a single point is inside the ellipse, use this function:


/**
 * determines whether a point p,q is inside an ellipse
 * specified by (x,y,a,b)
 *
 * returns 1 if inside, 0 if outside
 *
 * @param x x-coordinate of centre of ellipse
 * @param y y-coordinate of centre of ellipse
 * @param a horizonatal radius
 * @param b vertical radius
 * @param p x-coordinate of point to consider
 * @param q y-coordinate of point to consider
 */
insideEllipse = function(x, y, a, b, p, q) {
  var dx = (p - x) / a;
  var dy = (q - y) / b;
  var distance = dx * dx + dy * dy;
  return (distance < 1.0) ? 1 : 0;
};

To calculate the insideness of a square area, use this:


/**
 * determines what proportion of a square (p,q) - (p+side, q+side) is covered by this
 * ellipse. If side < threshold, returns an approximate result.
 *
 * returns: a value in the range [0.0, 1.0]
 *
 * @param p x-coordinate of point to consider
 * @param q y-coordinate of point to consider
 * @param side the length of the edge of the square to sample
 * @param threshold do not recurse if side is less than this value
 */
insideness = function(x, y, a, b, p, q, side, threshold) {
  var i1 = insideEllipse(x, y, a, b, p, q);
  var i2 = insideEllipse(x, y, a, b, p + side, q);
  var i3 = insideEllipse(x, y, a, b, p + side, q + side);
  var i4 = insideEllipse(x, y, a, b, p, q + side);
  var total = i1 + i2 + i3 + i4;
  if (total == 4 || total == 0 || side < threshold) {
    return total / 4.0;
  }

  side = side / 2;
  var j1 = insideness(x, y, a, b, p, q, side, threshold);
  var j2 = insideness(x, y, a, b, p + side, q, side, threshold);
  var j3 = insideness(x, y, a, b, p + side, q + side, side, threshold);
  var j4 = insideness(x, y, a, b, p, q + side, side, threshold);
  return (j1 + j2 + j3 + j4) / 4.0;
};

Enjoy.

No comments:

Post a Comment