[cairocommit] cairo/src cairo_pen.c,1.17,1.18
Keith Packard
commit at pdx.freedesktop.org
Tue Oct 12 12:29:32 PDT 2004
Committed by: keithp
Update of /cvs/cairo/cairo/src
In directory gabe:/tmp/cvsserv7546/src
Modified Files:
cairo_pen.c
Log Message:
20041012 Keith Packard <keithp at keithp.com>
reviewed by: Carl Worth <cworth at cworth.org>
* src/cairo_pen.c: (_cairo_pen_init), (_cairo_pen_vertices_needed):
Adapt function from Walter Brisken to compute pen ellipse major
axis length and use that to compute the required number of pen
vertices.
Index: cairo_pen.c
===================================================================
RCS file: /cvs/cairo/cairo/src/cairo_pen.c,v
retrieving revision 1.17
retrieving revision 1.18
diff C2 d r1.17 r1.18
*** cairo_pen.c 4 Sep 2004 13:38:35 0000 1.17
 cairo_pen.c 12 Oct 2004 19:29:30 0000 1.18
***************
*** 38,42 ****
static int
! _cairo_pen_vertices_needed (double radius, double tolerance, double expansion);
static void
 38,42 
static int
! _cairo_pen_vertices_needed (double tolerance, double radius, cairo_matrix_t *matrix);
static void
***************
*** 62,66 ****
int i;
int reflect;
! double det, expansion;
if (pen>num_vertices) {
 62,66 
int i;
int reflect;
! double det;
if (pen>num_vertices) {
***************
*** 77,98 ****
pen>tolerance = gstate>tolerance;
 /* The determinant represents the area expansion factor of the
 transform. In the worst case, this is entirely in one
 dimension, which is what we assume here. */

_cairo_matrix_compute_determinant (&gstate>ctm, &det);
if (det >= 0) {
reflect = 0;
 expansion = det;
} else {
reflect = 1;
 expansion = det;
}

 pen>num_vertices = _cairo_pen_vertices_needed (radius, gstate>tolerance, expansion);
 /* number of vertices must be even */
 if (pen>num_vertices % 2)
 pen>num_vertices++;
pen>vertices = malloc (pen>num_vertices * sizeof (cairo_pen_vertex_t));
if (pen>vertices == NULL) {
 77,91 
pen>tolerance = gstate>tolerance;
_cairo_matrix_compute_determinant (&gstate>ctm, &det);
if (det >= 0) {
reflect = 0;
} else {
reflect = 1;
}
+ pen>num_vertices = _cairo_pen_vertices_needed (gstate>tolerance,
+ radius,
+ &gstate>ctm);
+
pen>vertices = malloc (pen>num_vertices * sizeof (cairo_pen_vertex_t));
if (pen>vertices == NULL) {
***************
*** 172,186 ****
}
static int
! _cairo_pen_vertices_needed (double radius, double tolerance, double expansion)
{
! double theta;
! if (tolerance > expansion*radius) {
! return 4;
! }
! theta = acos (1  tolerance/(expansion * radius));
! return ceil (M_PI / theta);
}
 165,415 
}
+ /*
+ The circular pen 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 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' = _R_ X
+
+ 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*a + b*b)/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(t) + (b^2 + d^2)*sin(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.
+
+ Set
+
+ M = major axis length (computed by above formula)
+ m = minor axis length (computed by above formula)
+
+ Align 'M' along the X axis and 'm' along the Y axis and draw
+ an ellipse parameterized by angle 't':
+
+ x = M cos t y = m sin t
+
+ Perturb t by Â± d and compute two new points (x+,y+), (x,y).
+ The distance from the average of these two points to (x,y) represents
+ the maximum error in approximating the ellipse with a polygon formed
+ from vertices 2âˆ† radians apart.
+
+ x+ = M cos (t+âˆ†) y+ = m sin (t+âˆ†)
+ x = M cos (tâˆ†) y = m sin (tâˆ†)
+
+ Now compute the approximation error, E:
+
+ Ex = (x  (x+ + x) / 2)
+ Ex = (M cos(t)  (Mcos(t+âˆ†) + Mcos(tâˆ†))/2)
+ = M (cos(t)  (cos(t)cos(âˆ†) + sin(t)sin(âˆ†) +
+ cos(t)cos(âˆ†)  sin(t)sin(âˆ†))/2)
+ = M(cos(t)  cos(t)cos(âˆ†))
+ = M cos(t) (1  cos(âˆ†))
+
+ Ey = y  (y+  y) / 2
+ = m sin (t)  (m sin(t+âˆ†) + m sin(tâˆ†)) / 2
+ = m (sin(t)  (sin(t)cos(âˆ†) + cos(t)sin(âˆ†) +
+ sin(t)cos(âˆ†)  cos(t)sin(âˆ†))/2)
+ = m (sin(t)  sin(t)cos(âˆ†))
+ = m sin(t) (1  cos(âˆ†))
+
+ EÂ² = ExÂ² + EyÂ²
+ = (M cos(t) (1  cos (âˆ†)))Â² + (m sin(t) (1cos(âˆ†)))Â²
+ = (1  cos(âˆ†))Â² (MÂ² cosÂ²(t) + mÂ² sinÂ²(t))
+ = (1  cos(âˆ†))Â² ((mÂ² + MÂ²  mÂ²) cosÂ² (t) + mÂ² sinÂ²(t))
+ = (1  cos(âˆ†))Â² (MÂ²  mÂ²) cosÂ² (t) + (1  cos(âˆ†))Â² mÂ²
+
+ Find the extremum by differentiation wrt t and setting that to zero
+
+ âˆ‚(EÂ²)/âˆ‚(t) = (1cos(d))Â² (MÂ²  mÂ²) (2 cos(t) sin(t))
+
+ 0 = 2 cos (t) sin (t)
+ 0 = sin (2t)
+ t = nÏ€
+
+ Which is to say that the maximum and minimum errors occur on the
+ axes of the ellipse at 0 and Ï€ radians:
+
+ EÂ²(0) = (1cos(âˆ†))Â² (MÂ²  mÂ²) + (1cos(âˆ†))Â² mÂ²
+ = (1cos(âˆ†))Â² MÂ²
+ EÂ²(Ï€) = (1cos(âˆ†))Â² mÂ²
+
+ maximum error = M (1cos(âˆ†))
+ minimum error = m (1cos(âˆ†))
+
+ We must make maximum error â‰¤ tolerance, so compute the âˆ† needed:
+
+ tolerance = M (1cos(âˆ†))
+ tolerance / M = 1  cos (âˆ†)
+ cos(âˆ†) = 1  tolerance/M
+ âˆ† = acos (1  tolerance / M);
+
+ Remembering that âˆ† is half of our angle between vertices,
+ the number of vertices is then
+
+ 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
! _cairo_pen_vertices_needed (double tolerance,
! double radius,
! cairo_matrix_t *matrix)
{
! double a = matrix>m[0][0], c = matrix>m[0][1];
! double b = matrix>m[1][0], d = matrix>m[1][1];
! 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
! */
!
! double major_axis = 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));
! */
!
! /*
! * compute number of vertices needed
! */
! int num_vertices;
!
! /* Where tolerance / M is > 1, we use 4 points */
! if (tolerance >= major_axis) {
! num_vertices = 4;
! } else {
! double delta = acos (1  tolerance / major_axis);
! num_vertices = ceil (M_PI / delta);
!
! /* number of vertices must be even */
! if (num_vertices % 2)
! num_vertices++;
! }
! return num_vertices;
}
***************
*** 202,207 ****
}
}
!
! /* Find active pen vertex for clockwise edge of stroke at the given slope.
*
* NOTE: The behavior of this function is sensitive to the sense of
 431,436 
}
}
! /*
! * Find active pen vertex for clockwise edge of stroke at the given slope.
*
* NOTE: The behavior of this function is sensitive to the sense of
More information about the cairocommit
mailing list