How to convert closed bezier curves to Bitmaps?

Question

I need an algorithm to convert a closed bezier curve (perhaps self-crossing) to a binary bitmap: 0 for inside pixels and 1 for outside. I'm writing a code that needs to implement some operations on bezier curves, could anybody give me some resources or tutorials about beziere? Wikipedia and others didn't say anything about optimization, subtracting, union, knot insertion and deletion and other operations :-)

Answer 1

This paper by Charles Loop and Jim Blinn goes into lots of detail on your question.

Another option is to tessellate the Bezier curve into line segments and then use your favorite polygon fill algorithm.

Answer 2

I'd like to add that the tessellation option is very efficient and gives excellent results. It sounds wrong to approximate a Bezier curve by line segments, because you think the output will look like a polygon. The trick is to make the line segments short enough so that the error is very small (say, less than 1/10 of a pixel).

Here is a formula that I have used to compute the step size, to ensure that the maximum error (i.e., deviation of line segments from true curve) is less than delta:

Let (x1,y1), (x2,y2), (x3,y3), (x4,y4) be the control points of the Bezier curve, in pixel coordinates.j

  dd0 = square(x1-2*x2+x3) + square(y1-2*y2+y3);
  dd1 = square(x2-2*x3+x4) + square(y2-2*y3+y4);
  dd = 6*sqrt(max(dd0, dd1));

Then dd is the maximal value of the 2nd derivative over the curve - because the 2nd derivative of a cubic is a linear function, this maximum must occur at an endpoint. Here I have used square(x) as an abbreviation for x*x.

  if (8*delta > dd) {
    epsilon = 1;
  } else {
    epsilon = sqrt(8*delta/dd);
  }

Then epsilon is your step size: if you choose the endpoints of your line segments at t=0, t=epsilon, t=2*epsilon, ..., (and the last endpoint at t=1), then the line segments will be within delta of the original curve.

Choose delta = 0.1 and you get bitmap output that is visually indistinguishable from the original curve.