[cairo-commit] cairo/src cairo-matrix.c, 1.30, 1.31 cairo-pen.c,
1.24, 1.25 cairoint.h, 1.202, 1.203
Bertram Felgenhauer
commit at pdx.freedesktop.org
Mon Aug 22 16:48:31 PDT 2005
Committed by: inte
Update of /cvs/cairo/cairo/src
In directory gabe:/tmp/cvs-serv13483/src
Modified Files:
cairo-matrix.c cairo-pen.c cairoint.h
Log Message:
2005-08-22 Bertram Felgenhauer <int-e at gmx.de>
* src/cairo-pen.c (_cairo_pen_vertices_needed): use new function.
strip comment of derivation for major axis length.
* src/cairo-matrix.c (_cairo_matrix_transformed_circle_major_axis):
use _cairo_matrix_get_affine to retrieve matrix entries.
* src/cairoint.h, src/cairo-matrix.c
(_cairo_matrix_transformed_circle_major_axis): new function split out
of cairo-pen.c. UTF8-ify the comment that explains the calculation.
Index: cairo-matrix.c
===================================================================
RCS file: /cvs/cairo/cairo/src/cairo-matrix.c,v
retrieving revision 1.30
retrieving revision 1.31
diff -u -d -r1.30 -r1.31
--- cairo-matrix.c 5 Aug 2005 17:05:29 -0000 1.30
+++ cairo-matrix.c 22 Aug 2005 23:48:28 -0000 1.31
@@ -587,3 +587,148 @@
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 at 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'(θ) = X(θ) * _R_ = (cos(θ), sin(θ)) * [a b]
+ [c d]
+ = (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: cairo-pen.c
===================================================================
RCS file: /cvs/cairo/cairo/src/cairo-pen.c,v
retrieving revision 1.24
retrieving revision 1.25
diff -u -d -r1.24 -r1.25
--- cairo-pen.c 22 Aug 2005 23:29:56 -0000 1.24
+++ cairo-pen.c 22 Aug 2005 23:48:28 -0000 1.25
@@ -173,132 +173,13 @@
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 at 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' = 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^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) = X(t) * _R_ = (cos(t), sin(t)) * [a b]
- [c d]
- = (a*cos(t) + c*sin(t), b*cos(t) + d*sin(t)).
-
-Define
-
- r(t) = |X'(t)|
-
-Thus
-
- r^2(t) = (a*cos(t) + c*sin(t))^2 + (b*cos(t) + d*sin(t))^2
- = (a^2 + b^2)*cos^2(t) + (c^2 + d^2)*sin^2(t)
- + 2*(a*c + b*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*c + b*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*c + b*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':
@@ -363,12 +244,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
@@ -376,29 +256,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 + 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;
-
/*
- * 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: cairoint.h
===================================================================
RCS file: /cvs/cairo/cairo/src/cairoint.h,v
retrieving revision 1.202
retrieving revision 1.203
diff -u -d -r1.202 -r1.203
--- cairoint.h 22 Aug 2005 04:04:52 -0000 1.202
+++ cairoint.h 22 Aug 2005 23:48:28 -0000 1.203
@@ -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);
More information about the cairo-commit
mailing list