1 /* cairo - a vector graphics library with display and print output
3 * Copyright © 2002 University of Southern California
5 * This library is free software; you can redistribute it and/or
6 * modify it either under the terms of the GNU Lesser General Public
7 * License version 2.1 as published by the Free Software Foundation
8 * (the "LGPL") or, at your option, under the terms of the Mozilla
9 * Public License Version 1.1 (the "MPL"). If you do not alter this
10 * notice, a recipient may use your version of this file under either
11 * the MPL or the LGPL.
13 * You should have received a copy of the LGPL along with this library
14 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
15 * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
16 * You should have received a copy of the MPL along with this library
17 * in the file COPYING-MPL-1.1
19 * The contents of this file are subject to the Mozilla Public License
20 * Version 1.1 (the "License"); you may not use this file except in
21 * compliance with the License. You may obtain a copy of the License at
22 * http://www.mozilla.org/MPL/
24 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
25 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
26 * the specific language governing rights and limitations.
28 * The Original Code is the cairo graphics library.
30 * The Initial Developer of the Original Code is University of Southern
34 * Carl D. Worth <cworth@cworth.org>
38 #include "cairo-error-private.h"
41 #define PIXMAN_MAX_INT ((pixman_fixed_1 >> 1) - pixman_fixed_e) /* need to ensure deltas also fit */
43 #if _XOPEN_SOURCE >= 600 || defined (_ISOC99_SOURCE)
44 #define ISFINITE(x) isfinite (x)
46 #define ISFINITE(x) ((x) * (x) >= 0.) /* check for NaNs */
50 * SECTION:cairo-matrix
51 * @Title: cairo_matrix_t
52 * @Short_Description: Generic matrix operations
55 * #cairo_matrix_t is used throughout cairo to convert between different
56 * coordinate spaces. A #cairo_matrix_t holds an affine transformation,
57 * such as a scale, rotation, shear, or a combination of these.
58 * The transformation of a point (<literal>x</literal>,<literal>y</literal>)
62 * x_new = xx * x + xy * y + x0;
63 * y_new = yx * x + yy * y + y0;
66 * The current transformation matrix of a #cairo_t, represented as a
67 * #cairo_matrix_t, defines the transformation from user-space
68 * coordinates to device-space coordinates. See cairo_get_matrix() and
73 _cairo_matrix_scalar_multiply (cairo_matrix_t
*matrix
, double scalar
);
76 _cairo_matrix_compute_adjoint (cairo_matrix_t
*matrix
);
79 * cairo_matrix_init_identity:
80 * @matrix: a #cairo_matrix_t
82 * Modifies @matrix to be an identity transformation.
87 cairo_matrix_init_identity (cairo_matrix_t
*matrix
)
89 cairo_matrix_init (matrix
,
94 slim_hidden_def(cairo_matrix_init_identity
);
98 * @matrix: a #cairo_matrix_t
99 * @xx: xx component of the affine transformation
100 * @yx: yx component of the affine transformation
101 * @xy: xy component of the affine transformation
102 * @yy: yy component of the affine transformation
103 * @x0: X translation component of the affine transformation
104 * @y0: Y translation component of the affine transformation
106 * Sets @matrix to be the affine transformation given by
107 * @xx, @yx, @xy, @yy, @x0, @y0. The transformation is given
110 * x_new = xx * x + xy * y + x0;
111 * y_new = yx * x + yy * y + y0;
117 cairo_matrix_init (cairo_matrix_t
*matrix
,
118 double xx
, double yx
,
120 double xy
, double yy
,
121 double x0
, double y0
)
123 matrix
->xx
= xx
; matrix
->yx
= yx
;
124 matrix
->xy
= xy
; matrix
->yy
= yy
;
125 matrix
->x0
= x0
; matrix
->y0
= y0
;
127 slim_hidden_def(cairo_matrix_init
);
130 * _cairo_matrix_get_affine:
131 * @matrix: a #cairo_matrix_t
132 * @xx: location to store xx component of matrix
133 * @yx: location to store yx component of matrix
134 * @xy: location to store xy component of matrix
135 * @yy: location to store yy component of matrix
136 * @x0: location to store x0 (X-translation component) of matrix, or %NULL
137 * @y0: location to store y0 (Y-translation component) of matrix, or %NULL
139 * Gets the matrix values for the affine transformation that @matrix represents.
140 * See cairo_matrix_init().
143 * This function is a leftover from the old public API, but is still
144 * mildly useful as an internal means for getting at the matrix
145 * members in a positional way. For example, when reassigning to some
146 * external matrix type, or when renaming members to more meaningful
147 * names (such as a,b,c,d,e,f) for particular manipulations.
150 _cairo_matrix_get_affine (const cairo_matrix_t
*matrix
,
151 double *xx
, double *yx
,
152 double *xy
, double *yy
,
153 double *x0
, double *y0
)
168 * cairo_matrix_init_translate:
169 * @matrix: a #cairo_matrix_t
170 * @tx: amount to translate in the X direction
171 * @ty: amount to translate in the Y direction
173 * Initializes @matrix to a transformation that translates by @tx and
174 * @ty in the X and Y dimensions, respectively.
179 cairo_matrix_init_translate (cairo_matrix_t
*matrix
,
180 double tx
, double ty
)
182 cairo_matrix_init (matrix
,
187 slim_hidden_def(cairo_matrix_init_translate
);
190 * cairo_matrix_translate:
191 * @matrix: a #cairo_matrix_t
192 * @tx: amount to translate in the X direction
193 * @ty: amount to translate in the Y direction
195 * Applies a translation by @tx, @ty to the transformation in
196 * @matrix. The effect of the new transformation is to first translate
197 * the coordinates by @tx and @ty, then apply the original transformation
198 * to the coordinates.
203 cairo_matrix_translate (cairo_matrix_t
*matrix
, double tx
, double ty
)
207 cairo_matrix_init_translate (&tmp
, tx
, ty
);
209 cairo_matrix_multiply (matrix
, &tmp
, matrix
);
211 slim_hidden_def (cairo_matrix_translate
);
214 * cairo_matrix_init_scale:
215 * @matrix: a #cairo_matrix_t
216 * @sx: scale factor in the X direction
217 * @sy: scale factor in the Y direction
219 * Initializes @matrix to a transformation that scales by @sx and @sy
220 * in the X and Y dimensions, respectively.
225 cairo_matrix_init_scale (cairo_matrix_t
*matrix
,
226 double sx
, double sy
)
228 cairo_matrix_init (matrix
,
233 slim_hidden_def(cairo_matrix_init_scale
);
236 * cairo_matrix_scale:
237 * @matrix: a #cairo_matrix_t
238 * @sx: scale factor in the X direction
239 * @sy: scale factor in the Y direction
241 * Applies scaling by @sx, @sy to the transformation in @matrix. The
242 * effect of the new transformation is to first scale the coordinates
243 * by @sx and @sy, then apply the original transformation to the coordinates.
248 cairo_matrix_scale (cairo_matrix_t
*matrix
, double sx
, double sy
)
252 cairo_matrix_init_scale (&tmp
, sx
, sy
);
254 cairo_matrix_multiply (matrix
, &tmp
, matrix
);
256 slim_hidden_def(cairo_matrix_scale
);
259 * cairo_matrix_init_rotate:
260 * @matrix: a #cairo_matrix_t
261 * @radians: angle of rotation, in radians. The direction of rotation
262 * is defined such that positive angles rotate in the direction from
263 * the positive X axis toward the positive Y axis. With the default
264 * axis orientation of cairo, positive angles rotate in a clockwise
267 * Initialized @matrix to a transformation that rotates by @radians.
272 cairo_matrix_init_rotate (cairo_matrix_t
*matrix
,
281 cairo_matrix_init (matrix
,
286 slim_hidden_def(cairo_matrix_init_rotate
);
289 * cairo_matrix_rotate:
290 * @matrix: a #cairo_matrix_t
291 * @radians: angle of rotation, in radians. The direction of rotation
292 * is defined such that positive angles rotate in the direction from
293 * the positive X axis toward the positive Y axis. With the default
294 * axis orientation of cairo, positive angles rotate in a clockwise
297 * Applies rotation by @radians to the transformation in
298 * @matrix. The effect of the new transformation is to first rotate the
299 * coordinates by @radians, then apply the original transformation
300 * to the coordinates.
305 cairo_matrix_rotate (cairo_matrix_t
*matrix
, double radians
)
309 cairo_matrix_init_rotate (&tmp
, radians
);
311 cairo_matrix_multiply (matrix
, &tmp
, matrix
);
315 * cairo_matrix_multiply:
316 * @result: a #cairo_matrix_t in which to store the result
317 * @a: a #cairo_matrix_t
318 * @b: a #cairo_matrix_t
320 * Multiplies the affine transformations in @a and @b together
321 * and stores the result in @result. The effect of the resulting
322 * transformation is to first apply the transformation in @a to the
323 * coordinates and then apply the transformation in @b to the
326 * It is allowable for @result to be identical to either @a or @b.
331 * XXX: The ordering of the arguments to this function corresponds
332 * to [row_vector]*A*B. If we want to use column vectors instead,
333 * then we need to switch the two arguments and fix up all
337 cairo_matrix_multiply (cairo_matrix_t
*result
, const cairo_matrix_t
*a
, const cairo_matrix_t
*b
)
341 r
.xx
= a
->xx
* b
->xx
+ a
->yx
* b
->xy
;
342 r
.yx
= a
->xx
* b
->yx
+ a
->yx
* b
->yy
;
344 r
.xy
= a
->xy
* b
->xx
+ a
->yy
* b
->xy
;
345 r
.yy
= a
->xy
* b
->yx
+ a
->yy
* b
->yy
;
347 r
.x0
= a
->x0
* b
->xx
+ a
->y0
* b
->xy
+ b
->x0
;
348 r
.y0
= a
->x0
* b
->yx
+ a
->y0
* b
->yy
+ b
->y0
;
352 slim_hidden_def(cairo_matrix_multiply
);
355 _cairo_matrix_multiply (cairo_matrix_t
*r
,
356 const cairo_matrix_t
*a
,
357 const cairo_matrix_t
*b
)
359 r
->xx
= a
->xx
* b
->xx
+ a
->yx
* b
->xy
;
360 r
->yx
= a
->xx
* b
->yx
+ a
->yx
* b
->yy
;
362 r
->xy
= a
->xy
* b
->xx
+ a
->yy
* b
->xy
;
363 r
->yy
= a
->xy
* b
->yx
+ a
->yy
* b
->yy
;
365 r
->x0
= a
->x0
* b
->xx
+ a
->y0
* b
->xy
+ b
->x0
;
366 r
->y0
= a
->x0
* b
->yx
+ a
->y0
* b
->yy
+ b
->y0
;
370 * cairo_matrix_transform_distance:
371 * @matrix: a #cairo_matrix_t
372 * @dx: X component of a distance vector. An in/out parameter
373 * @dy: Y component of a distance vector. An in/out parameter
375 * Transforms the distance vector (@dx,@dy) by @matrix. This is
376 * similar to cairo_matrix_transform_point() except that the translation
377 * components of the transformation are ignored. The calculation of
378 * the returned vector is as follows:
381 * dx2 = dx1 * a + dy1 * c;
382 * dy2 = dx1 * b + dy1 * d;
385 * Affine transformations are position invariant, so the same vector
386 * always transforms to the same vector. If (@x1,@y1) transforms
387 * to (@x2,@y2) then (@x1+@dx1,@y1+@dy1) will transform to
388 * (@x1+@dx2,@y1+@dy2) for all values of @x1 and @x2.
393 cairo_matrix_transform_distance (const cairo_matrix_t
*matrix
, double *dx
, double *dy
)
397 new_x
= (matrix
->xx
* *dx
+ matrix
->xy
* *dy
);
398 new_y
= (matrix
->yx
* *dx
+ matrix
->yy
* *dy
);
403 slim_hidden_def(cairo_matrix_transform_distance
);
406 * cairo_matrix_transform_point:
407 * @matrix: a #cairo_matrix_t
408 * @x: X position. An in/out parameter
409 * @y: Y position. An in/out parameter
411 * Transforms the point (@x, @y) by @matrix.
416 cairo_matrix_transform_point (const cairo_matrix_t
*matrix
, double *x
, double *y
)
418 cairo_matrix_transform_distance (matrix
, x
, y
);
423 slim_hidden_def(cairo_matrix_transform_point
);
426 _cairo_matrix_transform_bounding_box (const cairo_matrix_t
*matrix
,
427 double *x1
, double *y1
,
428 double *x2
, double *y2
,
429 cairo_bool_t
*is_tight
)
432 double quad_x
[4], quad_y
[4];
436 if (matrix
->xy
== 0. && matrix
->yx
== 0.) {
437 /* non-rotation/skew matrix, just map the two extreme points */
439 if (matrix
->xx
!= 1.) {
440 quad_x
[0] = *x1
* matrix
->xx
;
441 quad_x
[1] = *x2
* matrix
->xx
;
442 if (quad_x
[0] < quad_x
[1]) {
450 if (matrix
->x0
!= 0.) {
455 if (matrix
->yy
!= 1.) {
456 quad_y
[0] = *y1
* matrix
->yy
;
457 quad_y
[1] = *y2
* matrix
->yy
;
458 if (quad_y
[0] < quad_y
[1]) {
466 if (matrix
->y0
!= 0.) {
480 cairo_matrix_transform_point (matrix
, &quad_x
[0], &quad_y
[0]);
484 cairo_matrix_transform_point (matrix
, &quad_x
[1], &quad_y
[1]);
488 cairo_matrix_transform_point (matrix
, &quad_x
[2], &quad_y
[2]);
492 cairo_matrix_transform_point (matrix
, &quad_x
[3], &quad_y
[3]);
494 min_x
= max_x
= quad_x
[0];
495 min_y
= max_y
= quad_y
[0];
497 for (i
=1; i
< 4; i
++) {
498 if (quad_x
[i
] < min_x
)
500 if (quad_x
[i
] > max_x
)
503 if (quad_y
[i
] < min_y
)
505 if (quad_y
[i
] > max_y
)
515 /* it's tight if and only if the four corner points form an axis-aligned
517 And that's true if and only if we can derive corners 0 and 3 from
518 corners 1 and 2 in one of two straightforward ways...
519 We could use a tolerance here but for now we'll fall back to FALSE in the case
520 of floating point error.
523 (quad_x
[1] == quad_x
[0] && quad_y
[1] == quad_y
[3] &&
524 quad_x
[2] == quad_x
[3] && quad_y
[2] == quad_y
[0]) ||
525 (quad_x
[1] == quad_x
[3] && quad_y
[1] == quad_y
[0] &&
526 quad_x
[2] == quad_x
[0] && quad_y
[2] == quad_y
[3]);
531 _cairo_matrix_transform_bounding_box_fixed (const cairo_matrix_t
*matrix
,
533 cairo_bool_t
*is_tight
)
535 double x1
, y1
, x2
, y2
;
537 _cairo_box_to_doubles (bbox
, &x1
, &y1
, &x2
, &y2
);
538 _cairo_matrix_transform_bounding_box (matrix
, &x1
, &y1
, &x2
, &y2
, is_tight
);
539 _cairo_box_from_doubles (bbox
, &x1
, &y1
, &x2
, &y2
);
543 _cairo_matrix_scalar_multiply (cairo_matrix_t
*matrix
, double scalar
)
545 matrix
->xx
*= scalar
;
546 matrix
->yx
*= scalar
;
548 matrix
->xy
*= scalar
;
549 matrix
->yy
*= scalar
;
551 matrix
->x0
*= scalar
;
552 matrix
->y0
*= scalar
;
555 /* This function isn't a correct adjoint in that the implicit 1 in the
556 homogeneous result should actually be ad-bc instead. But, since this
557 adjoint is only used in the computation of the inverse, which
558 divides by det (A)=ad-bc anyway, everything works out in the end. */
560 _cairo_matrix_compute_adjoint (cairo_matrix_t
*matrix
)
562 /* adj (A) = transpose (C:cofactor (A,i,j)) */
563 double a
, b
, c
, d
, tx
, ty
;
565 _cairo_matrix_get_affine (matrix
,
570 cairo_matrix_init (matrix
,
573 c
*ty
- d
*tx
, b
*tx
- a
*ty
);
577 * cairo_matrix_invert:
578 * @matrix: a #cairo_matrix_t
580 * Changes @matrix to be the inverse of its original value. Not
581 * all transformation matrices have inverses; if the matrix
582 * collapses points together (it is <firstterm>degenerate</firstterm>),
583 * then it has no inverse and this function will fail.
585 * Returns: If @matrix has an inverse, modifies @matrix to
586 * be the inverse matrix and returns %CAIRO_STATUS_SUCCESS. Otherwise,
587 * returns %CAIRO_STATUS_INVALID_MATRIX.
592 cairo_matrix_invert (cairo_matrix_t
*matrix
)
596 /* Simple scaling|translation matrices are quite common... */
597 if (matrix
->xy
== 0. && matrix
->yx
== 0.) {
598 matrix
->x0
= -matrix
->x0
;
599 matrix
->y0
= -matrix
->y0
;
601 if (matrix
->xx
!= 1.) {
602 if (matrix
->xx
== 0.)
603 return _cairo_error (CAIRO_STATUS_INVALID_MATRIX
);
605 matrix
->xx
= 1. / matrix
->xx
;
606 matrix
->x0
*= matrix
->xx
;
609 if (matrix
->yy
!= 1.) {
610 if (matrix
->yy
== 0.)
611 return _cairo_error (CAIRO_STATUS_INVALID_MATRIX
);
613 matrix
->yy
= 1. / matrix
->yy
;
614 matrix
->y0
*= matrix
->yy
;
617 return CAIRO_STATUS_SUCCESS
;
620 /* inv (A) = 1/det (A) * adj (A) */
621 det
= _cairo_matrix_compute_determinant (matrix
);
623 if (! ISFINITE (det
))
624 return _cairo_error (CAIRO_STATUS_INVALID_MATRIX
);
627 return _cairo_error (CAIRO_STATUS_INVALID_MATRIX
);
629 _cairo_matrix_compute_adjoint (matrix
);
630 _cairo_matrix_scalar_multiply (matrix
, 1 / det
);
632 return CAIRO_STATUS_SUCCESS
;
634 slim_hidden_def(cairo_matrix_invert
);
637 _cairo_matrix_is_invertible (const cairo_matrix_t
*matrix
)
641 det
= _cairo_matrix_compute_determinant (matrix
);
643 return ISFINITE (det
) && det
!= 0.;
647 _cairo_matrix_is_scale_0 (const cairo_matrix_t
*matrix
)
649 return matrix
->xx
== 0. &&
656 _cairo_matrix_compute_determinant (const cairo_matrix_t
*matrix
)
660 a
= matrix
->xx
; b
= matrix
->yx
;
661 c
= matrix
->xy
; d
= matrix
->yy
;
667 * _cairo_matrix_compute_basis_scale_factors:
669 * @basis_scale: the scale factor in the direction of basis
670 * @normal_scale: the scale factor in the direction normal to the basis
671 * @x_basis: basis to use. X basis if true, Y basis otherwise.
673 * Computes |Mv| and det(M)/|Mv| for v=[1,0] if x_basis is true, and v=[0,1]
674 * otherwise, and M is @matrix.
676 * Return value: the scale factor of @matrix on the height of the font,
677 * or 1.0 if @matrix is %NULL.
680 _cairo_matrix_compute_basis_scale_factors (const cairo_matrix_t
*matrix
,
681 double *basis_scale
, double *normal_scale
,
682 cairo_bool_t x_basis
)
686 det
= _cairo_matrix_compute_determinant (matrix
);
688 if (! ISFINITE (det
))
689 return _cairo_error (CAIRO_STATUS_INVALID_MATRIX
);
693 *basis_scale
= *normal_scale
= 0;
697 double x
= x_basis
!= 0;
701 cairo_matrix_transform_distance (matrix
, &x
, &y
);
702 major
= hypot (x
, y
);
714 *basis_scale
= major
;
715 *normal_scale
= minor
;
719 *basis_scale
= minor
;
720 *normal_scale
= major
;
724 return CAIRO_STATUS_SUCCESS
;
728 _cairo_matrix_is_integer_translation (const cairo_matrix_t
*matrix
,
731 if (_cairo_matrix_is_translation (matrix
))
733 cairo_fixed_t x0_fixed
= _cairo_fixed_from_double (matrix
->x0
);
734 cairo_fixed_t y0_fixed
= _cairo_fixed_from_double (matrix
->y0
);
736 if (_cairo_fixed_is_integer (x0_fixed
) &&
737 _cairo_fixed_is_integer (y0_fixed
))
740 *itx
= _cairo_fixed_integer_part (x0_fixed
);
742 *ity
= _cairo_fixed_integer_part (y0_fixed
);
751 #define SCALING_EPSILON _cairo_fixed_to_double(1)
753 /* This only returns true if the matrix is 90 degree rotations or
754 * flips. It appears calling code is relying on this. It will return
755 * false for other rotations even if the scale is one. Approximations
756 * are allowed to handle matricies filled in using trig functions
757 * such as sin(M_PI_2).
760 _cairo_matrix_has_unity_scale (const cairo_matrix_t
*matrix
)
762 /* check that the determinant is near +/-1 */
763 double det
= _cairo_matrix_compute_determinant (matrix
);
764 if (fabs (det
* det
- 1.0) < SCALING_EPSILON
) {
765 /* check that one axis is close to zero */
766 if (fabs (matrix
->xy
) < SCALING_EPSILON
&&
767 fabs (matrix
->yx
) < SCALING_EPSILON
)
769 if (fabs (matrix
->xx
) < SCALING_EPSILON
&&
770 fabs (matrix
->yy
) < SCALING_EPSILON
)
772 /* If rotations are allowed then it must instead test for
773 * orthogonality. This is xx*xy+yx*yy ~= 0.
779 /* By pixel exact here, we mean a matrix that is composed only of
780 * 90 degree rotations, flips, and integer translations and produces a 1:1
781 * mapping between source and destination pixels. If we transform an image
782 * with a pixel-exact matrix, filtering is not useful.
785 _cairo_matrix_is_pixel_exact (const cairo_matrix_t
*matrix
)
787 cairo_fixed_t x0_fixed
, y0_fixed
;
789 if (! _cairo_matrix_has_unity_scale (matrix
))
792 x0_fixed
= _cairo_fixed_from_double (matrix
->x0
);
793 y0_fixed
= _cairo_fixed_from_double (matrix
->y0
);
795 return _cairo_fixed_is_integer (x0_fixed
) && _cairo_fixed_is_integer (y0_fixed
);
799 A circle in user space is transformed into an ellipse in device space.
801 The following is a derivation of a formula to calculate the length of the
802 major axis for this ellipse; this is useful for error bounds calculations.
804 Thanks to Walter Brisken <wbrisken@aoc.nrao.edu> for this derivation:
806 1. First some notation:
808 All capital letters represent vectors in two dimensions. A prime '
809 represents a transformed coordinate. Matrices are written in underlined
810 form, ie _R_. Lowercase letters represent scalar real values.
812 2. The question has been posed: What is the maximum expansion factor
813 achieved by the linear transformation
817 where _R_ is a real-valued 2x2 matrix with entries:
822 In other words, what is the maximum radius, MAX[ |X'| ], reached for any
823 X on the unit circle ( |X| = 1 ) ?
825 3. Some useful formulae
827 (A) through (C) below are standard double-angle formulae. (D) is a lesser
828 known result and is derived below:
830 (A) sin²(θ) = (1 - cos(2*θ))/2
831 (B) cos²(θ) = (1 + cos(2*θ))/2
832 (C) sin(θ)*cos(θ) = sin(2*θ)/2
833 (D) MAX[a*cos(θ) + b*sin(θ)] = sqrt(a² + b²)
837 find the maximum of the function by setting the derivative to zero:
839 -a*sin(θ)+b*cos(θ) = 0
841 From this it follows that
847 sin(θ) = b/sqrt(a² + b²)
851 cos(θ) = a/sqrt(a² + b²)
853 Thus the maximum value is
855 MAX[a*cos(θ) + b*sin(θ)] = (a² + b²)/sqrt(a² + b²)
858 4. Derivation of maximum expansion
860 To find MAX[ |X'| ] we search brute force method using calculus. The unit
861 circle on which X is constrained is to be parameterized by t:
863 X(θ) = (cos(θ), sin(θ))
867 X'(θ) = X(θ) * _R_ = (cos(θ), sin(θ)) * [a b]
869 = (a*cos(θ) + c*sin(θ), b*cos(θ) + d*sin(θ)).
877 r²(θ) = (a*cos(θ) + c*sin(θ))² + (b*cos(θ) + d*sin(θ))²
878 = (a² + b²)*cos²(θ) + (c² + d²)*sin²(θ)
879 + 2*(a*c + b*d)*cos(θ)*sin(θ)
881 Now apply the double angle formulae (A) to (C) from above:
883 r²(θ) = (a² + b² + c² + d²)/2
884 + (a² + b² - c² - d²)*cos(2*θ)/2
885 + (a*c + b*d)*sin(2*θ)
886 = f + g*cos(φ) + h*sin(φ)
890 f = (a² + b² + c² + d²)/2
891 g = (a² + b² - c² - d²)/2
895 It is clear that MAX[ |X'| ] = sqrt(MAX[ r² ]). Here we determine MAX[ r² ]
896 using (D) from above:
898 MAX[ r² ] = f + sqrt(g² + h²)
902 MAX[ |X'| ] = sqrt( f + sqrt(g² + h²) )
904 Which is the solution to this problem.
909 (Note that the minor axis length is at the minimum of the above solution,
910 which is just sqrt ( f - sqrt(g² + h²) ) given the symmetry of (D)).
913 For another derivation of the same result, using Singular Value Decomposition,
914 see doc/tutorial/src/singular.c.
917 /* determine the length of the major axis of a circle of the given radius
918 after applying the transformation matrix. */
920 _cairo_matrix_transformed_circle_major_axis (const cairo_matrix_t
*matrix
,
923 double a
, b
, c
, d
, f
, g
, h
, i
, j
;
925 if (_cairo_matrix_has_unity_scale (matrix
))
928 _cairo_matrix_get_affine (matrix
,
940 return radius
* sqrt (f
+ hypot (g
, h
));
943 * we don't need the minor axis length, which is
944 * double min = radius * sqrt (f - sqrt (g*g+h*h));
948 static const pixman_transform_t pixman_identity_transform
= {{
954 static cairo_status_t
955 _cairo_matrix_to_pixman_matrix (const cairo_matrix_t
*matrix
,
956 pixman_transform_t
*pixman_transform
,
961 unsigned max_iterations
;
963 pixman_transform
->matrix
[0][0] = _cairo_fixed_16_16_from_double (matrix
->xx
);
964 pixman_transform
->matrix
[0][1] = _cairo_fixed_16_16_from_double (matrix
->xy
);
965 pixman_transform
->matrix
[0][2] = _cairo_fixed_16_16_from_double (matrix
->x0
);
967 pixman_transform
->matrix
[1][0] = _cairo_fixed_16_16_from_double (matrix
->yx
);
968 pixman_transform
->matrix
[1][1] = _cairo_fixed_16_16_from_double (matrix
->yy
);
969 pixman_transform
->matrix
[1][2] = _cairo_fixed_16_16_from_double (matrix
->y0
);
971 pixman_transform
->matrix
[2][0] = 0;
972 pixman_transform
->matrix
[2][1] = 0;
973 pixman_transform
->matrix
[2][2] = 1 << 16;
975 /* The conversion above breaks cairo's translation invariance:
976 * a translation of (a, b) in device space translates to
977 * a translation of (xx * a + xy * b, yx * a + yy * b)
978 * for cairo, while pixman uses rounded versions of xx ... yy.
979 * This error increases as a and b get larger.
981 * To compensate for this, we fix the point (xc, yc) in pattern
982 * space and adjust pixman's transform to agree with cairo's at
986 if (_cairo_matrix_has_unity_scale (matrix
))
987 return CAIRO_STATUS_SUCCESS
;
989 if (unlikely (fabs (matrix
->xx
) > PIXMAN_MAX_INT
||
990 fabs (matrix
->xy
) > PIXMAN_MAX_INT
||
991 fabs (matrix
->x0
) > PIXMAN_MAX_INT
||
992 fabs (matrix
->yx
) > PIXMAN_MAX_INT
||
993 fabs (matrix
->yy
) > PIXMAN_MAX_INT
||
994 fabs (matrix
->y0
) > PIXMAN_MAX_INT
))
996 return _cairo_error (CAIRO_STATUS_INVALID_MATRIX
);
999 /* Note: If we can't invert the transformation, skip the adjustment. */
1001 if (cairo_matrix_invert (&inv
) != CAIRO_STATUS_SUCCESS
)
1002 return CAIRO_STATUS_SUCCESS
;
1004 /* find the pattern space coordinate that maps to (xc, yc) */
1008 pixman_vector_t vector
;
1009 cairo_fixed_16_16_t dx
, dy
;
1011 vector
.vector
[0] = _cairo_fixed_16_16_from_double (xc
);
1012 vector
.vector
[1] = _cairo_fixed_16_16_from_double (yc
);
1013 vector
.vector
[2] = 1 << 16;
1015 /* If we can't transform the reference point, skip the adjustment. */
1016 if (! pixman_transform_point_3d (pixman_transform
, &vector
))
1017 return CAIRO_STATUS_SUCCESS
;
1019 x
= pixman_fixed_to_double (vector
.vector
[0]);
1020 y
= pixman_fixed_to_double (vector
.vector
[1]);
1021 cairo_matrix_transform_point (&inv
, &x
, &y
);
1023 /* Ideally, the vector should now be (xc, yc).
1024 * We can now compensate for the resulting error.
1028 cairo_matrix_transform_distance (matrix
, &x
, &y
);
1029 dx
= _cairo_fixed_16_16_from_double (x
);
1030 dy
= _cairo_fixed_16_16_from_double (y
);
1031 pixman_transform
->matrix
[0][2] -= dx
;
1032 pixman_transform
->matrix
[1][2] -= dy
;
1034 if (dx
== 0 && dy
== 0)
1035 return CAIRO_STATUS_SUCCESS
;
1036 } while (--max_iterations
);
1038 /* We didn't find an exact match between cairo and pixman, but
1039 * the matrix should be mostly correct */
1040 return CAIRO_STATUS_SUCCESS
;
1043 static inline double
1044 _pixman_nearest_sample (double d
)
1046 return ceil (d
- .5);
1050 * _cairo_matrix_is_pixman_translation:
1052 * @filter: the filter to be used on the pattern transformed by @matrix
1053 * @x_offset: the translation in the X direction
1054 * @y_offset: the translation in the Y direction
1056 * Checks if @matrix translated by (x_offset, y_offset) can be
1057 * represented using just an offset (within the range pixman can
1058 * accept) and an identity matrix.
1060 * Passing a non-zero value in x_offset/y_offset has the same effect
1061 * as applying cairo_matrix_translate(matrix, x_offset, y_offset) and
1062 * setting x_offset and y_offset to 0.
1064 * Upon return x_offset and y_offset contain the translation vector if
1065 * the return value is %TRUE. If the return value is %FALSE, they will
1068 * Return value: %TRUE if @matrix can be represented as a pixman
1069 * translation, %FALSE otherwise.
1072 _cairo_matrix_is_pixman_translation (const cairo_matrix_t
*matrix
,
1073 cairo_filter_t filter
,
1079 if (!_cairo_matrix_is_translation (matrix
))
1082 if (matrix
->x0
== 0. && matrix
->y0
== 0.)
1085 tx
= matrix
->x0
+ *x_offset
;
1086 ty
= matrix
->y0
+ *y_offset
;
1088 if (filter
== CAIRO_FILTER_FAST
|| filter
== CAIRO_FILTER_NEAREST
) {
1089 tx
= _pixman_nearest_sample (tx
);
1090 ty
= _pixman_nearest_sample (ty
);
1091 } else if (tx
!= floor (tx
) || ty
!= floor (ty
)) {
1095 if (fabs (tx
) > PIXMAN_MAX_INT
|| fabs (ty
) > PIXMAN_MAX_INT
)
1098 *x_offset
= _cairo_lround (tx
);
1099 *y_offset
= _cairo_lround (ty
);
1104 * _cairo_matrix_to_pixman_matrix_offset:
1106 * @filter: the filter to be used on the pattern transformed by @matrix
1107 * @xc: the X coordinate of the point to fix in pattern space
1108 * @yc: the Y coordinate of the point to fix in pattern space
1109 * @out_transform: the transformation which best approximates @matrix
1110 * @x_offset: the translation in the X direction
1111 * @y_offset: the translation in the Y direction
1113 * This function tries to represent @matrix translated by (x_offset,
1114 * y_offset) as a %pixman_transform_t and an translation.
1116 * Passing a non-zero value in x_offset/y_offset has the same effect
1117 * as applying cairo_matrix_translate(matrix, x_offset, y_offset) and
1118 * setting x_offset and y_offset to 0.
1120 * If it is possible to represent the matrix with an identity
1121 * %pixman_transform_t and a translation within the valid range for
1122 * pixman, this function will set @out_transform to be the identity,
1123 * @x_offset and @y_offset to be the translation vector and will
1124 * return %CAIRO_INT_STATUS_NOTHING_TO_DO. Otherwise it will try to
1125 * evenly divide the translational component of @matrix between
1126 * @out_transform and (@x_offset, @y_offset).
1128 * Upon return x_offset and y_offset contain the translation vector.
1130 * Return value: %CAIRO_INT_STATUS_NOTHING_TO_DO if the out_transform
1131 * is the identity, %CAIRO_STATUS_INVALID_MATRIX if it was not
1132 * possible to represent @matrix as a pixman_transform_t without
1133 * overflows, %CAIRO_STATUS_SUCCESS otherwise.
1136 _cairo_matrix_to_pixman_matrix_offset (const cairo_matrix_t
*matrix
,
1137 cairo_filter_t filter
,
1140 pixman_transform_t
*out_transform
,
1144 cairo_bool_t is_pixman_translation
;
1146 is_pixman_translation
= _cairo_matrix_is_pixman_translation (matrix
,
1151 if (is_pixman_translation
) {
1152 *out_transform
= pixman_identity_transform
;
1153 return CAIRO_INT_STATUS_NOTHING_TO_DO
;
1158 cairo_matrix_translate (&m
, *x_offset
, *y_offset
);
1159 if (m
.x0
!= 0.0 || m
.y0
!= 0.0) {
1160 double tx
, ty
, norm
;
1163 /* pixman also limits the [xy]_offset to 16 bits so evenly
1164 * spread the bits between the two.
1166 * To do this, find the solutions of:
1167 * |x| = |x*m.xx + y*m.xy + m.x0|
1168 * |y| = |x*m.yx + y*m.yy + m.y0|
1170 * and select the one whose maximum norm is smallest.
1174 norm
= MAX (fabs (tx
), fabs (ty
));
1176 for (i
= -1; i
< 2; i
+=2) {
1177 for (j
= -1; j
< 2; j
+=2) {
1178 double x
, y
, den
, new_norm
;
1180 den
= (m
.xx
+ i
) * (m
.yy
+ j
) - m
.xy
* m
.yx
;
1181 if (fabs (den
) < DBL_EPSILON
)
1184 x
= m
.y0
* m
.xy
- m
.x0
* (m
.yy
+ j
);
1185 y
= m
.x0
* m
.yx
- m
.y0
* (m
.xx
+ i
);
1191 new_norm
= MAX (fabs (x
), fabs (y
));
1192 if (norm
> new_norm
) {
1204 cairo_matrix_translate (&m
, tx
, ty
);
1210 return _cairo_matrix_to_pixman_matrix (&m
, out_transform
, xc
, yc
);