Index: src/cairo-matrix.c =================================================================== RCS file: /cvs/cairo/cairo/src/cairo-matrix.c,v retrieving revision 1.30 diff -u -r1.30 cairo-matrix.c --- src/cairo-matrix.c 5 Aug 2005 17:05:29 -0000 1.30 +++ src/cairo-matrix.c 22 Aug 2005 17:58:42 -0000 @@ -587,3 +587,146 @@ return TRUE; } + +/* + A circle in user space is transformed into an ellipse in device space. + + The following is a derivation of a formula to calculate the length of the + major axis for this ellipse; this is useful for error bounds calculations. + + Thanks to Walter Brisken for this derivation: + + 1. First some notation: + + All capital letters represent vectors in two dimensions. A prime ' + represents a transformed coordinate. Matrices are written in underlined + form, ie _R_. Lowercase letters represent scalar real values. + + 2. The question has been posed: What is the maximum expansion factor + achieved by the linear transformation + + X' = X _R_ + + where _R_ is a real-valued 2x2 matrix with entries: + + _R_ = [a b] + [c d] . + + In other words, what is the maximum radius, MAX[ |X'| ], reached for any + X on the unit circle ( |X| = 1 ) ? + + + 3. Some useful formulae + + (A) through (C) below are standard double-angle formulae. (D) is a lesser + known result and is derived below: + + (A) sin²(θ) = (1 - cos(2*θ))/2 + (B) cos²(θ) = (1 + cos(2*θ))/2 + (C) sin(θ)*cos(θ) = sin(2*θ)/2 + (D) MAX[a*cos(θ) + b*sin(θ)] = sqrt(a² + b²) + + Proof of (D): + + find the maximum of the function by setting the derivative to zero: + + -a*sin(θ)+b*cos(θ) = 0 + + From this it follows that + + tan(θ) = b/a + + and hence + + sin(θ) = b/sqrt(a² + b²) + + and + + cos(θ) = a/sqrt(a² + b²) + + Thus the maximum value is + + MAX[a*cos(θ) + b*sin(θ)] = (a² + b²)/sqrt(a² + b²) + = sqrt(a² + b²) + + + 4. Derivation of maximum expansion + + To find MAX[ |X'| ] we search brute force method using calculus. The unit + circle on which X is constrained is to be parameterized by t: + + X(θ) = (cos(θ), sin(θ)) + + Thus + + X'(θ) = (a*cos(θ) + c*sin(θ), b*cos(θ) + d*sin(θ)) . + + Define + + r(θ) = |X'(θ)| + + Thus + + r²(θ) = (a*cos(θ) + c*sin(θ))² + (b*cos(θ) + d*sin(θ))² + = (a² + b²)*cos²(θ) + (c² + d²)*sin²(θ) + + 2*(a*c + b*d)*cos(θ)*sin(θ) + + Now apply the double angle formulae (A) to (C) from above: + + r²(θ) = (a² + b² + c² + d²)/2 + + (a² + b² - c² - d²)*cos(2*θ)/2 + + (a*c + b*d)*sin(2*θ) + = f + g*cos(φ) + h*sin(φ) + + Where + + f = (a² + b² + c² + d²)/2 + g = (a² + b² - c² - d²)/2 + h = (a*c + d*d) + φ = 2*θ + + It is clear that MAX[ |X'| ] = sqrt(MAX[ r² ]). Here we determine MAX[ r² ] + using (D) from above: + + MAX[ r² ] = f + sqrt(g² + h²) + + And finally + + MAX[ |X'| ] = sqrt( f + sqrt(g² + h²) ) + + Which is the solution to this problem. + + + Walter Brisken + 2004/10/08 + + (Note that the minor axis length is at the minimum of the above solution, + which is just sqrt ( f - sqrt(g² + h²) ) given the symmetry of (D)). +*/ + +/* determine the length of the major axis of a circle of the given radius + after applying the transformation matrix. */ +double +_cairo_matrix_transformed_circle_major_axis (cairo_matrix_t *matrix, double radius) +{ + double a, b, c, d; + + _cairo_matrix_get_affine (matrix, + &a, &b, + &c, &d, + NULL, NULL); + + double i = a*a + b*b; + double j = c*c + d*d; + + double f = 0.5 * (i + j); + double g = 0.5 * (i - j); + double h = a*c + b*d; + + return radius * sqrt (f + sqrt (g*g+h*h)); + + /* + * we don't need the minor axis length, which is + * double min = radius * sqrt (f - sqrt (g*g+h*h)); + */ +} Index: src/cairo-pen.c =================================================================== RCS file: /cvs/cairo/cairo/src/cairo-pen.c,v retrieving revision 1.23 diff -u -r1.23 cairo-pen.c --- src/cairo-pen.c 7 Apr 2005 17:01:49 -0000 1.23 +++ src/cairo-pen.c 22 Aug 2005 17:58:42 -0000 @@ -167,136 +167,18 @@ } /* -The circular pen in user space is transformed into an ellipse in -device space. +A cirtcle in user space is transformed into an ellipse in device space. We construct the pen by computing points along the circumference using equally spaced angles. -We show below that this approximation to the ellipse has -maximum error at the major axis of the ellipse. -So, we need to compute the length of the major axis and then -use that to compute the number of sides needed in our pen. - -Thanks to Walter Brisken for this -derivation: - -1. First some notation: - -All capital letters represent vectors in two dimensions. A prime ' -represents a transformed coordinate. Matrices are written in underlined -form, ie _R_. Lowercase letters represent scalar real values. - -The letter t is used to represent the greek letter theta. - -2. The question has been posed: What is the maximum expansion factor -achieved by the linear transformation - -X' = _R_ X - -where _R_ is a real-valued 2x2 matrix with entries: - -_R_ = [a b] - [c d] . - -In other words, what is the maximum radius, MAX[ |X'| ], reached for any -X on the unit circle ( |X| = 1 ) ? - - -3. Some useful formulae - -(A) through (C) below are standard double-angle formulae. (D) is a lesser -known result and is derived below: - -(A) sin^2(t) = (1 - cos(2*t))/2 -(B) cos^2(t) = (1 + cos(2*t))/2 -(C) sin(t)*cos(t) = sin(2*t)/2 -(D) MAX[a*cos(t) + b*sin(t)] = sqrt(a^2 + b^2) - -Proof of (D): - -find the maximum of the function by setting the derivative to zero: - - -a*sin(t)+b*cos(t) = 0 - -From this it follows that - - tan(t) = b/a - -and hence - - sin(t) = b/sqrt(a^2 + b^2) - -and - - cos(t) = a/sqrt(a^2 + b^2) - -Thus the maximum value is - - MAX[a*cos(t) + b*sin(t)] = (a^2 + b^2)/sqrt(a^2 + b^2) - = sqrt(a^2 + b^2) - - -4. Derivation of maximum expansion - -To find MAX[ |X'| ] we search brute force method using calculus. The unit -circle on which X is constrained is to be parameterized by t: - - X(t) = (cos(t), sin(t)) - -Thus - - X'(t) = (a*cos(t) + b*sin(t), c*cos(t) + d*sin(t)) . - -Define - - r(t) = |X'(t)| - -Thus - - r^2(t) = (a*cos(t) + b*sin(t))^2 + (c*cos(t) + d*sin(t))^2 - = (a^2 + c^2)*cos^2(t) + (b^2 + d^2)*sin^2(t) - + 2*(a*b + c*d)*cos(t)*sin(t) - -Now apply the double angle formulae (A) to (C) from above: - - r^2(t) = (a^2 + b^2 + c^2 + d^2)/2 - + (a^2 - b^2 + c^2 - d^2)*cos(2*t)/2 - + (a*b + c*d)*sin(2*t) - = f + g*cos(u) + h*sin(u) - -Where - - f = (a^2 + b^2 + c^2 + d^2)/2 - g = (a^2 - b^2 + c^2 - d^2)/2 - h = (a*b + c*d) - u = 2*t - -It is clear that MAX[ |X'| ] = sqrt(MAX[ r^2 ]). Here we determine MAX[ r^2 ] -using (D) from above: - - MAX[ r^2 ] = f + sqrt(g^2 + h^2) - -And finally - - MAX[ |X'| ] = sqrt( f + sqrt(g^2 + h^2) ) - -Which is the solution to this problem. - - -Walter Brisken -2004/10/08 - -(Note that the minor axis length is at the minimum of the above solution, -which is just sqrt (f - sqrt (g^2 + h^2)) given the symmetry of (D)). - -Now to compute how many sides to use for the pen formed by -a regular polygon. +We show that this approximation to the ellipse has maximum error at the +major axis of the ellipse. Set - M = major axis length (computed by above formula) - m = minor axis length (computed by above formula) + M = major axis length + m = minor axis length Align 'M' along the X axis and 'm' along the Y axis and draw an ellipse parameterized by angle 't': @@ -361,12 +243,11 @@ Remembering that ∆ is half of our angle between vertices, the number of vertices is then -vertices = ceil(2π/2∆). - = ceil(π/∆). + vertices = ceil(2π/2∆). + = ceil(π/∆). Note that this also equation works for M == m (a circle) as it doesn't matter where on the circle the error is computed. - */ static int @@ -374,29 +255,15 @@ double radius, cairo_matrix_t *matrix) { - double a = matrix->xx, b = matrix->yx; - double c = matrix->xy, d = matrix->yy; - - double i = a*a + c*c; - double j = b*b + d*d; - - double f = 0.5 * (i + j); - double g = 0.5 * (i - j); - double h = a*b + c*d; - /* - * compute major and minor axes lengths for - * a pen with the specified radius + * the pen is a circle that gets transformed to an ellipse by matrix. + * compute major axis length for a pen with the specified radius. + * we don't need the minor axis length. */ - double major_axis = radius * sqrt (f + sqrt (g*g+h*h)); + double major_axis = _cairo_matrix_transformed_circle_major_axis(matrix, radius); /* - * we don't need the minor axis length, which is - * double min = radius * sqrt (f - sqrt (g*g+h*h)); - */ - - /* * compute number of vertices needed */ int num_vertices; Index: src/cairoint.h =================================================================== RCS file: /cvs/cairo/cairo/src/cairoint.h,v retrieving revision 1.202 diff -u -r1.202 cairoint.h --- src/cairoint.h 22 Aug 2005 04:04:52 -0000 1.202 +++ src/cairoint.h 22 Aug 2005 17:58:43 -0000 @@ -1866,6 +1866,9 @@ _cairo_matrix_is_integer_translation(const cairo_matrix_t *matrix, int *itx, int *ity); +cairo_private double +_cairo_matrix_transformed_circle_major_axis(cairo_matrix_t *matrix, double radius); + /* cairo_traps.c */ cairo_private void _cairo_traps_init (cairo_traps_t *traps);