[cairocommit] cairo/src cairomatrix.c, 1.30, 1.31 cairopen.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/cvsserv13483/src
Modified Files:
cairomatrix.c cairopen.c cairoint.h
Log Message:
20050822 Bertram Felgenhauer <inte at gmx.de>
* src/cairopen.c (_cairo_pen_vertices_needed): use new function.
strip comment of derivation for major axis length.
* src/cairomatrix.c (_cairo_matrix_transformed_circle_major_axis):
use _cairo_matrix_get_affine to retrieve matrix entries.
* src/cairoint.h, src/cairomatrix.c
(_cairo_matrix_transformed_circle_major_axis): new function split out
of cairopen.c. UTF8ify the comment that explains the calculation.
Index: cairomatrix.c
===================================================================
RCS file: /cvs/cairo/cairo/src/cairomatrix.c,v
retrieving revision 1.30
retrieving revision 1.31
diff u d r1.30 r1.31
 cairomatrix.c 5 Aug 2005 17:05:29 0000 1.30
+++ cairomatrix.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 realvalued 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 doubleangle 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: cairopen.c
===================================================================
RCS file: /cvs/cairo/cairo/src/cairopen.c,v
retrieving revision 1.24
retrieving revision 1.25
diff u d r1.24 r1.25
 cairopen.c 22 Aug 2005 23:29:56 0000 1.24
+++ cairopen.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 realvalued 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 doubleangle 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 cairocommit
mailing list