Attachment 2983 Details for Bug 4188 – pull out cairo_matrix_transformed_circle_major_axis

[patch] pull out cairo_matrix_transformed_circle_major_axis

cairo-pull-out-cairo-matrix-transformed-circle-major-axis.diff (text/plain), 9.89 KB, created by Bertram Felgenhauer on 2005-08-22 11:21:11 UTC

(hide)

Description:

Filename:

MIME Type:

Creator: Bertram Felgenhauer

Created: 2005-08-22 11:21:11 UTC

Size: 9.89 KB

patch

obsolete

>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 <wbrisken@aoc.nrao.edu> 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 <wbrisken@aoc.nrao.edu> 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);

Actions: View | Splinter Review

Attachments on bug 4188: 2983 | 2984 | 2985 | 2996

Use of freedesktop.org services, including Bugzilla, is subject to our Code of Conduct. How we collect and use information is described in our Privacy Policy.