cairo lite

Work on the cairo library has taught Carl Worth and I a huge amount about computational geometry and the general requirements for 2D drawing. Taking the smallest parts of the cairo architecture, I've constructed a minimal drawing API using paths consisting of lines and splines.

The fundemental primitive is a polygon fill operation. There is no explicit stroke operation. Instead, you construct a separate pen using the regular path operators, then the path of the stroke is 'convolved' with the pen and the resulting closed polygon is added to another path. This means that the application is in control over the shape of the pen, so it can use circles, triangles or any other convex polygon.

The convolution algorithm that Carl and I developed for cairo requires a convex pen, so the convolution operation uses the Graham scan algorithm to compute the convex hull of whatever pen is provided. I have some ideas on how to permit an arbitrary polygon to be used as the pen; perhaps I'll have a chance to try those out.

Because the expected target display devices are all very small (<256 pixels in the largest dimension), and because the target CPUs are relatively modest in power, I'm using a 16-bit fixed point representation for the pixel coordinates with 12 integer and 4 fractional bits. This appears to provide sufficient subpixel precision to avoid obvious warts in tests that I've done.

Still to do is the addition of affine transformations from a user coordinate space of 32-bit fixed point numbers in 16.16 format. I had initially thought this wouldn't be necessary, and that it would be expensive. However, the most expensive part is the sine computation needed for angular rotations. I already had to add a table of sine values to construct regular circular pens, so at least that part won't impose any additional cost.