[cairo] Pen vertex estimation

[Keith Packard]

In constructing pens, the hardest part is estimating the number of 
vertices needed to satisfy the tolerance.

Under the transformation matrix, the circular user-space pen will be
transformed to some ellipse; given the pixel-dimension of the major axis of
that ellipse, it's straightforward to compute the number of vertices 
needed to construct a polygon within the specified tolerance.

So, the hard piece of problem actually devolves to a computation of the 
major axis length of an ellipse given the transformation matrix.

The current code computes the determinant of the matrix, which represents 
the area expansion factor for the matrix.  Assuming that the matrix scales 
in only one direction, this expansion factor will also represent the 
scaling of the major axis dimension.  We don't exactly restrict matrices 
to this form though.  

For matrices scaling the same amount in both directions, this equation over
computes the major axis length by an exponent of two, which is a waste of
CPU.  For matrices which scale up in one direction and down in another,
this can actually *under* estimate the number of vertices needed by an 
arbitrary amount.

So, we clearly need a different function.

Consider our user-space pen as a circle of radius 1 with a square
circumscribing it.  Under the transformation, the circle becomes an ellipse
and the square a parallelogram.  Because the transform is affine, the
circle remains inscribed within the square.  Hence, the major axis must
therefore be less than the distance from the origin to the furthest corner
of the parallelogram.  Again using the fact that the transform is affine, that
furthest is either the transformation of the point [1,1] or [-1,1] (or 
their mirrors through the origin)

Given the matrix

	| a b |
 	| c d |

[1,1]	-> [a + c, b + d]
[-1,1]	-> [-a + c, -b + d]
[1,-1]	-> [a - c, b - d]
[-1,-1]	-> [-a - c, -b - d]

The maximum over all four values is [|a| + |b|, |c| + |d|].

The distance from the origin to this point represents a bound on the major 
axis length for the ellipse.  We can either compute this exactly, or use 
the manhatten distance as an approximation, in which case our ellipse is 
bounded by |a| + |b| + |c| + |d|.  I'm using the latter for twin where the 
sqrt operation is expensive.

-keith


-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 228 bytes
Desc: not available
Url : http://lists.freedesktop.org/archives/cairo/attachments/20041001/b06cae35/attachment.pgp