Line data Source code
1 : /* cairo - a vector graphics library with display and print output
2 : *
3 : * Copyright © 2002 University of Southern California
4 : *
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.
12 : *
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
18 : *
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/
23 : *
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.
27 : *
28 : * The Original Code is the cairo graphics library.
29 : *
30 : * The Initial Developer of the Original Code is University of Southern
31 : * California.
32 : *
33 : * Contributor(s):
34 : * Carl D. Worth <cworth@cworth.org>
35 : */
36 :
37 : #include "cairoint.h"
38 : #include "cairo-error-private.h"
39 :
40 : #if _XOPEN_SOURCE >= 600 || defined (_ISOC99_SOURCE)
41 : #define ISFINITE(x) isfinite (x)
42 : #else
43 : #define ISFINITE(x) ((x) * (x) >= 0.) /* check for NaNs */
44 : #endif
45 :
46 : /**
47 : * SECTION:cairo-matrix
48 : * @Title: cairo_matrix_t
49 : * @Short_Description: Generic matrix operations
50 : * @See_Also: #cairo_t
51 : *
52 : * #cairo_matrix_t is used throughout cairo to convert between different
53 : * coordinate spaces. A #cairo_matrix_t holds an affine transformation,
54 : * such as a scale, rotation, shear, or a combination of these.
55 : * The transformation of a point (<literal>x</literal>,<literal>y</literal>)
56 : * is given by:
57 : *
58 : * <programlisting>
59 : * x_new = xx * x + xy * y + x0;
60 : * y_new = yx * x + yy * y + y0;
61 : * </programlisting>
62 : *
63 : * The current transformation matrix of a #cairo_t, represented as a
64 : * #cairo_matrix_t, defines the transformation from user-space
65 : * coordinates to device-space coordinates. See cairo_get_matrix() and
66 : * cairo_set_matrix().
67 : */
68 :
69 : static void
70 : _cairo_matrix_scalar_multiply (cairo_matrix_t *matrix, double scalar);
71 :
72 : static void
73 : _cairo_matrix_compute_adjoint (cairo_matrix_t *matrix);
74 :
75 : /**
76 : * cairo_matrix_init_identity:
77 : * @matrix: a #cairo_matrix_t
78 : *
79 : * Modifies @matrix to be an identity transformation.
80 : **/
81 : void
82 18 : cairo_matrix_init_identity (cairo_matrix_t *matrix)
83 : {
84 18 : cairo_matrix_init (matrix,
85 : 1, 0,
86 : 0, 1,
87 : 0, 0);
88 18 : }
89 : slim_hidden_def(cairo_matrix_init_identity);
90 :
91 : /**
92 : * cairo_matrix_init:
93 : * @matrix: a #cairo_matrix_t
94 : * @xx: xx component of the affine transformation
95 : * @yx: yx component of the affine transformation
96 : * @xy: xy component of the affine transformation
97 : * @yy: yy component of the affine transformation
98 : * @x0: X translation component of the affine transformation
99 : * @y0: Y translation component of the affine transformation
100 : *
101 : * Sets @matrix to be the affine transformation given by
102 : * @xx, @yx, @xy, @yy, @x0, @y0. The transformation is given
103 : * by:
104 : * <programlisting>
105 : * x_new = xx * x + xy * y + x0;
106 : * y_new = yx * x + yy * y + y0;
107 : * </programlisting>
108 : **/
109 : void
110 58 : cairo_matrix_init (cairo_matrix_t *matrix,
111 : double xx, double yx,
112 :
113 : double xy, double yy,
114 : double x0, double y0)
115 : {
116 58 : matrix->xx = xx; matrix->yx = yx;
117 58 : matrix->xy = xy; matrix->yy = yy;
118 58 : matrix->x0 = x0; matrix->y0 = y0;
119 58 : }
120 : slim_hidden_def(cairo_matrix_init);
121 :
122 : /**
123 : * _cairo_matrix_get_affine:
124 : * @matrix: a #cairo_matrix_t
125 : * @xx: location to store xx component of matrix
126 : * @yx: location to store yx component of matrix
127 : * @xy: location to store xy component of matrix
128 : * @yy: location to store yy component of matrix
129 : * @x0: location to store x0 (X-translation component) of matrix, or %NULL
130 : * @y0: location to store y0 (Y-translation component) of matrix, or %NULL
131 : *
132 : * Gets the matrix values for the affine transformation that @matrix represents.
133 : * See cairo_matrix_init().
134 : *
135 : *
136 : * This function is a leftover from the old public API, but is still
137 : * mildly useful as an internal means for getting at the matrix
138 : * members in a positional way. For example, when reassigning to some
139 : * external matrix type, or when renaming members to more meaningful
140 : * names (such as a,b,c,d,e,f) for particular manipulations.
141 : **/
142 : void
143 14 : _cairo_matrix_get_affine (const cairo_matrix_t *matrix,
144 : double *xx, double *yx,
145 : double *xy, double *yy,
146 : double *x0, double *y0)
147 : {
148 14 : *xx = matrix->xx;
149 14 : *yx = matrix->yx;
150 :
151 14 : *xy = matrix->xy;
152 14 : *yy = matrix->yy;
153 :
154 14 : if (x0)
155 0 : *x0 = matrix->x0;
156 14 : if (y0)
157 0 : *y0 = matrix->y0;
158 14 : }
159 :
160 : /**
161 : * cairo_matrix_init_translate:
162 : * @matrix: a #cairo_matrix_t
163 : * @tx: amount to translate in the X direction
164 : * @ty: amount to translate in the Y direction
165 : *
166 : * Initializes @matrix to a transformation that translates by @tx and
167 : * @ty in the X and Y dimensions, respectively.
168 : **/
169 : void
170 0 : cairo_matrix_init_translate (cairo_matrix_t *matrix,
171 : double tx, double ty)
172 : {
173 0 : cairo_matrix_init (matrix,
174 : 1, 0,
175 : 0, 1,
176 : tx, ty);
177 0 : }
178 : slim_hidden_def(cairo_matrix_init_translate);
179 :
180 : /**
181 : * cairo_matrix_translate:
182 : * @matrix: a #cairo_matrix_t
183 : * @tx: amount to translate in the X direction
184 : * @ty: amount to translate in the Y direction
185 : *
186 : * Applies a translation by @tx, @ty to the transformation in
187 : * @matrix. The effect of the new transformation is to first translate
188 : * the coordinates by @tx and @ty, then apply the original transformation
189 : * to the coordinates.
190 : **/
191 : void
192 0 : cairo_matrix_translate (cairo_matrix_t *matrix, double tx, double ty)
193 : {
194 : cairo_matrix_t tmp;
195 :
196 0 : cairo_matrix_init_translate (&tmp, tx, ty);
197 :
198 0 : cairo_matrix_multiply (matrix, &tmp, matrix);
199 0 : }
200 : slim_hidden_def (cairo_matrix_translate);
201 :
202 : /**
203 : * cairo_matrix_init_scale:
204 : * @matrix: a #cairo_matrix_t
205 : * @sx: scale factor in the X direction
206 : * @sy: scale factor in the Y direction
207 : *
208 : * Initializes @matrix to a transformation that scales by @sx and @sy
209 : * in the X and Y dimensions, respectively.
210 : **/
211 : void
212 24 : cairo_matrix_init_scale (cairo_matrix_t *matrix,
213 : double sx, double sy)
214 : {
215 24 : cairo_matrix_init (matrix,
216 : sx, 0,
217 : 0, sy,
218 : 0, 0);
219 24 : }
220 : slim_hidden_def(cairo_matrix_init_scale);
221 :
222 : /**
223 : * cairo_matrix_scale:
224 : * @matrix: a #cairo_matrix_t
225 : * @sx: scale factor in the X direction
226 : * @sy: scale factor in the Y direction
227 : *
228 : * Applies scaling by @sx, @sy to the transformation in @matrix. The
229 : * effect of the new transformation is to first scale the coordinates
230 : * by @sx and @sy, then apply the original transformation to the coordinates.
231 : **/
232 : void
233 14 : cairo_matrix_scale (cairo_matrix_t *matrix, double sx, double sy)
234 : {
235 : cairo_matrix_t tmp;
236 :
237 14 : cairo_matrix_init_scale (&tmp, sx, sy);
238 :
239 14 : cairo_matrix_multiply (matrix, &tmp, matrix);
240 14 : }
241 : slim_hidden_def(cairo_matrix_scale);
242 :
243 : /**
244 : * cairo_matrix_init_rotate:
245 : * @matrix: a #cairo_matrix_t
246 : * @radians: angle of rotation, in radians. The direction of rotation
247 : * is defined such that positive angles rotate in the direction from
248 : * the positive X axis toward the positive Y axis. With the default
249 : * axis orientation of cairo, positive angles rotate in a clockwise
250 : * direction.
251 : *
252 : * Initialized @matrix to a transformation that rotates by @radians.
253 : **/
254 : void
255 0 : cairo_matrix_init_rotate (cairo_matrix_t *matrix,
256 : double radians)
257 : {
258 : double s;
259 : double c;
260 :
261 0 : s = sin (radians);
262 0 : c = cos (radians);
263 :
264 0 : cairo_matrix_init (matrix,
265 : c, s,
266 : -s, c,
267 : 0, 0);
268 0 : }
269 : slim_hidden_def(cairo_matrix_init_rotate);
270 :
271 : /**
272 : * cairo_matrix_rotate:
273 : * @matrix: a #cairo_matrix_t
274 : * @radians: angle of rotation, in radians. The direction of rotation
275 : * is defined such that positive angles rotate in the direction from
276 : * the positive X axis toward the positive Y axis. With the default
277 : * axis orientation of cairo, positive angles rotate in a clockwise
278 : * direction.
279 : *
280 : * Applies rotation by @radians to the transformation in
281 : * @matrix. The effect of the new transformation is to first rotate the
282 : * coordinates by @radians, then apply the original transformation
283 : * to the coordinates.
284 : **/
285 : void
286 0 : cairo_matrix_rotate (cairo_matrix_t *matrix, double radians)
287 : {
288 : cairo_matrix_t tmp;
289 :
290 0 : cairo_matrix_init_rotate (&tmp, radians);
291 :
292 0 : cairo_matrix_multiply (matrix, &tmp, matrix);
293 0 : }
294 :
295 : /**
296 : * cairo_matrix_multiply:
297 : * @result: a #cairo_matrix_t in which to store the result
298 : * @a: a #cairo_matrix_t
299 : * @b: a #cairo_matrix_t
300 : *
301 : * Multiplies the affine transformations in @a and @b together
302 : * and stores the result in @result. The effect of the resulting
303 : * transformation is to first apply the transformation in @a to the
304 : * coordinates and then apply the transformation in @b to the
305 : * coordinates.
306 : *
307 : * It is allowable for @result to be identical to either @a or @b.
308 : **/
309 : /*
310 : * XXX: The ordering of the arguments to this function corresponds
311 : * to [row_vector]*A*B. If we want to use column vectors instead,
312 : * then we need to switch the two arguments and fix up all
313 : * uses.
314 : */
315 : void
316 25 : cairo_matrix_multiply (cairo_matrix_t *result, const cairo_matrix_t *a, const cairo_matrix_t *b)
317 : {
318 : cairo_matrix_t r;
319 :
320 25 : r.xx = a->xx * b->xx + a->yx * b->xy;
321 25 : r.yx = a->xx * b->yx + a->yx * b->yy;
322 :
323 25 : r.xy = a->xy * b->xx + a->yy * b->xy;
324 25 : r.yy = a->xy * b->yx + a->yy * b->yy;
325 :
326 25 : r.x0 = a->x0 * b->xx + a->y0 * b->xy + b->x0;
327 25 : r.y0 = a->x0 * b->yx + a->y0 * b->yy + b->y0;
328 :
329 25 : *result = r;
330 25 : }
331 : slim_hidden_def(cairo_matrix_multiply);
332 :
333 : /**
334 : * cairo_matrix_transform_distance:
335 : * @matrix: a #cairo_matrix_t
336 : * @dx: X component of a distance vector. An in/out parameter
337 : * @dy: Y component of a distance vector. An in/out parameter
338 : *
339 : * Transforms the distance vector (@dx,@dy) by @matrix. This is
340 : * similar to cairo_matrix_transform_point() except that the translation
341 : * components of the transformation are ignored. The calculation of
342 : * the returned vector is as follows:
343 : *
344 : * <programlisting>
345 : * dx2 = dx1 * a + dy1 * c;
346 : * dy2 = dx1 * b + dy1 * d;
347 : * </programlisting>
348 : *
349 : * Affine transformations are position invariant, so the same vector
350 : * always transforms to the same vector. If (@x1,@y1) transforms
351 : * to (@x2,@y2) then (@x1+@dx1,@y1+@dy1) will transform to
352 : * (@x1+@dx2,@y1+@dy2) for all values of @x1 and @x2.
353 : **/
354 : void
355 1345 : cairo_matrix_transform_distance (const cairo_matrix_t *matrix, double *dx, double *dy)
356 : {
357 : double new_x, new_y;
358 :
359 1345 : new_x = (matrix->xx * *dx + matrix->xy * *dy);
360 1345 : new_y = (matrix->yx * *dx + matrix->yy * *dy);
361 :
362 1345 : *dx = new_x;
363 1345 : *dy = new_y;
364 1345 : }
365 : slim_hidden_def(cairo_matrix_transform_distance);
366 :
367 : /**
368 : * cairo_matrix_transform_point:
369 : * @matrix: a #cairo_matrix_t
370 : * @x: X position. An in/out parameter
371 : * @y: Y position. An in/out parameter
372 : *
373 : * Transforms the point (@x, @y) by @matrix.
374 : **/
375 : void
376 528 : cairo_matrix_transform_point (const cairo_matrix_t *matrix, double *x, double *y)
377 : {
378 528 : cairo_matrix_transform_distance (matrix, x, y);
379 :
380 528 : *x += matrix->x0;
381 528 : *y += matrix->y0;
382 528 : }
383 : slim_hidden_def(cairo_matrix_transform_point);
384 :
385 : void
386 0 : _cairo_matrix_transform_bounding_box (const cairo_matrix_t *matrix,
387 : double *x1, double *y1,
388 : double *x2, double *y2,
389 : cairo_bool_t *is_tight)
390 : {
391 : int i;
392 : double quad_x[4], quad_y[4];
393 : double min_x, max_x;
394 : double min_y, max_y;
395 :
396 0 : if (matrix->xy == 0. && matrix->yx == 0.) {
397 : /* non-rotation/skew matrix, just map the two extreme points */
398 :
399 0 : if (matrix->xx != 1.) {
400 0 : quad_x[0] = *x1 * matrix->xx;
401 0 : quad_x[1] = *x2 * matrix->xx;
402 0 : if (quad_x[0] < quad_x[1]) {
403 0 : *x1 = quad_x[0];
404 0 : *x2 = quad_x[1];
405 : } else {
406 0 : *x1 = quad_x[1];
407 0 : *x2 = quad_x[0];
408 : }
409 : }
410 0 : if (matrix->x0 != 0.) {
411 0 : *x1 += matrix->x0;
412 0 : *x2 += matrix->x0;
413 : }
414 :
415 0 : if (matrix->yy != 1.) {
416 0 : quad_y[0] = *y1 * matrix->yy;
417 0 : quad_y[1] = *y2 * matrix->yy;
418 0 : if (quad_y[0] < quad_y[1]) {
419 0 : *y1 = quad_y[0];
420 0 : *y2 = quad_y[1];
421 : } else {
422 0 : *y1 = quad_y[1];
423 0 : *y2 = quad_y[0];
424 : }
425 : }
426 0 : if (matrix->y0 != 0.) {
427 0 : *y1 += matrix->y0;
428 0 : *y2 += matrix->y0;
429 : }
430 :
431 0 : if (is_tight)
432 0 : *is_tight = TRUE;
433 :
434 0 : return;
435 : }
436 :
437 : /* general matrix */
438 0 : quad_x[0] = *x1;
439 0 : quad_y[0] = *y1;
440 0 : cairo_matrix_transform_point (matrix, &quad_x[0], &quad_y[0]);
441 :
442 0 : quad_x[1] = *x2;
443 0 : quad_y[1] = *y1;
444 0 : cairo_matrix_transform_point (matrix, &quad_x[1], &quad_y[1]);
445 :
446 0 : quad_x[2] = *x1;
447 0 : quad_y[2] = *y2;
448 0 : cairo_matrix_transform_point (matrix, &quad_x[2], &quad_y[2]);
449 :
450 0 : quad_x[3] = *x2;
451 0 : quad_y[3] = *y2;
452 0 : cairo_matrix_transform_point (matrix, &quad_x[3], &quad_y[3]);
453 :
454 0 : min_x = max_x = quad_x[0];
455 0 : min_y = max_y = quad_y[0];
456 :
457 0 : for (i=1; i < 4; i++) {
458 0 : if (quad_x[i] < min_x)
459 0 : min_x = quad_x[i];
460 0 : if (quad_x[i] > max_x)
461 0 : max_x = quad_x[i];
462 :
463 0 : if (quad_y[i] < min_y)
464 0 : min_y = quad_y[i];
465 0 : if (quad_y[i] > max_y)
466 0 : max_y = quad_y[i];
467 : }
468 :
469 0 : *x1 = min_x;
470 0 : *y1 = min_y;
471 0 : *x2 = max_x;
472 0 : *y2 = max_y;
473 :
474 0 : if (is_tight) {
475 : /* it's tight if and only if the four corner points form an axis-aligned
476 : rectangle.
477 : And that's true if and only if we can derive corners 0 and 3 from
478 : corners 1 and 2 in one of two straightforward ways...
479 : We could use a tolerance here but for now we'll fall back to FALSE in the case
480 : of floating point error.
481 : */
482 0 : *is_tight =
483 0 : (quad_x[1] == quad_x[0] && quad_y[1] == quad_y[3] &&
484 0 : quad_x[2] == quad_x[3] && quad_y[2] == quad_y[0]) ||
485 0 : (quad_x[1] == quad_x[3] && quad_y[1] == quad_y[0] &&
486 0 : quad_x[2] == quad_x[0] && quad_y[2] == quad_y[3]);
487 : }
488 : }
489 :
490 : cairo_private void
491 0 : _cairo_matrix_transform_bounding_box_fixed (const cairo_matrix_t *matrix,
492 : cairo_box_t *bbox,
493 : cairo_bool_t *is_tight)
494 : {
495 : double x1, y1, x2, y2;
496 :
497 0 : _cairo_box_to_doubles (bbox, &x1, &y1, &x2, &y2);
498 0 : _cairo_matrix_transform_bounding_box (matrix, &x1, &y1, &x2, &y2, is_tight);
499 0 : _cairo_box_from_doubles (bbox, &x1, &y1, &x2, &y2);
500 0 : }
501 :
502 : static void
503 0 : _cairo_matrix_scalar_multiply (cairo_matrix_t *matrix, double scalar)
504 : {
505 0 : matrix->xx *= scalar;
506 0 : matrix->yx *= scalar;
507 :
508 0 : matrix->xy *= scalar;
509 0 : matrix->yy *= scalar;
510 :
511 0 : matrix->x0 *= scalar;
512 0 : matrix->y0 *= scalar;
513 0 : }
514 :
515 : /* This function isn't a correct adjoint in that the implicit 1 in the
516 : homogeneous result should actually be ad-bc instead. But, since this
517 : adjoint is only used in the computation of the inverse, which
518 : divides by det (A)=ad-bc anyway, everything works out in the end. */
519 : static void
520 0 : _cairo_matrix_compute_adjoint (cairo_matrix_t *matrix)
521 : {
522 : /* adj (A) = transpose (C:cofactor (A,i,j)) */
523 : double a, b, c, d, tx, ty;
524 :
525 0 : _cairo_matrix_get_affine (matrix,
526 : &a, &b,
527 : &c, &d,
528 : &tx, &ty);
529 :
530 0 : cairo_matrix_init (matrix,
531 : d, -b,
532 : -c, a,
533 0 : c*ty - d*tx, b*tx - a*ty);
534 0 : }
535 :
536 : /**
537 : * cairo_matrix_invert:
538 : * @matrix: a #cairo_matrix_t
539 : *
540 : * Changes @matrix to be the inverse of its original value. Not
541 : * all transformation matrices have inverses; if the matrix
542 : * collapses points together (it is <firstterm>degenerate</firstterm>),
543 : * then it has no inverse and this function will fail.
544 : *
545 : * Returns: If @matrix has an inverse, modifies @matrix to
546 : * be the inverse matrix and returns %CAIRO_STATUS_SUCCESS. Otherwise,
547 : * returns %CAIRO_STATUS_INVALID_MATRIX.
548 : **/
549 : cairo_status_t
550 11 : cairo_matrix_invert (cairo_matrix_t *matrix)
551 : {
552 : double det;
553 :
554 : /* Simple scaling|translation matrices are quite common... */
555 11 : if (matrix->xy == 0. && matrix->yx == 0.) {
556 11 : matrix->x0 = -matrix->x0;
557 11 : matrix->y0 = -matrix->y0;
558 :
559 11 : if (matrix->xx != 1.) {
560 11 : if (matrix->xx == 0.)
561 0 : return _cairo_error (CAIRO_STATUS_INVALID_MATRIX);
562 :
563 11 : matrix->xx = 1. / matrix->xx;
564 11 : matrix->x0 *= matrix->xx;
565 : }
566 :
567 11 : if (matrix->yy != 1.) {
568 11 : if (matrix->yy == 0.)
569 0 : return _cairo_error (CAIRO_STATUS_INVALID_MATRIX);
570 :
571 11 : matrix->yy = 1. / matrix->yy;
572 11 : matrix->y0 *= matrix->yy;
573 : }
574 :
575 11 : return CAIRO_STATUS_SUCCESS;
576 : }
577 :
578 : /* inv (A) = 1/det (A) * adj (A) */
579 0 : det = _cairo_matrix_compute_determinant (matrix);
580 :
581 0 : if (! ISFINITE (det))
582 0 : return _cairo_error (CAIRO_STATUS_INVALID_MATRIX);
583 :
584 0 : if (det == 0)
585 0 : return _cairo_error (CAIRO_STATUS_INVALID_MATRIX);
586 :
587 0 : _cairo_matrix_compute_adjoint (matrix);
588 0 : _cairo_matrix_scalar_multiply (matrix, 1 / det);
589 :
590 0 : return CAIRO_STATUS_SUCCESS;
591 : }
592 : slim_hidden_def(cairo_matrix_invert);
593 :
594 : cairo_bool_t
595 2 : _cairo_matrix_is_invertible (const cairo_matrix_t *matrix)
596 : {
597 : double det;
598 :
599 2 : det = _cairo_matrix_compute_determinant (matrix);
600 :
601 2 : return ISFINITE (det) && det != 0.;
602 : }
603 :
604 : cairo_bool_t
605 0 : _cairo_matrix_is_scale_0 (const cairo_matrix_t *matrix)
606 : {
607 0 : return matrix->xx == 0. &&
608 0 : matrix->xy == 0. &&
609 0 : matrix->yx == 0. &&
610 0 : matrix->yy == 0.;
611 : }
612 :
613 : double
614 51 : _cairo_matrix_compute_determinant (const cairo_matrix_t *matrix)
615 : {
616 : double a, b, c, d;
617 :
618 51 : a = matrix->xx; b = matrix->yx;
619 51 : c = matrix->xy; d = matrix->yy;
620 :
621 51 : return a*d - b*c;
622 : }
623 :
624 : /**
625 : * _cairo_matrix_compute_basis_scale_factors:
626 : * @matrix: a matrix
627 : * @basis_scale: the scale factor in the direction of basis
628 : * @normal_scale: the scale factor in the direction normal to the basis
629 : * @x_basis: basis to use. X basis if true, Y basis otherwise.
630 : *
631 : * Computes |Mv| and det(M)/|Mv| for v=[1,0] if x_basis is true, and v=[0,1]
632 : * otherwise, and M is @matrix.
633 : *
634 : * Return value: the scale factor of @matrix on the height of the font,
635 : * or 1.0 if @matrix is %NULL.
636 : **/
637 : cairo_status_t
638 25 : _cairo_matrix_compute_basis_scale_factors (const cairo_matrix_t *matrix,
639 : double *basis_scale, double *normal_scale,
640 : cairo_bool_t x_basis)
641 : {
642 : double det;
643 :
644 25 : det = _cairo_matrix_compute_determinant (matrix);
645 :
646 25 : if (! ISFINITE (det))
647 0 : return _cairo_error (CAIRO_STATUS_INVALID_MATRIX);
648 :
649 25 : if (det == 0)
650 : {
651 0 : *basis_scale = *normal_scale = 0;
652 : }
653 : else
654 : {
655 25 : double x = x_basis != 0;
656 25 : double y = x == 0;
657 : double major, minor;
658 :
659 25 : cairo_matrix_transform_distance (matrix, &x, &y);
660 25 : major = hypot (x, y);
661 : /*
662 : * ignore mirroring
663 : */
664 25 : if (det < 0)
665 0 : det = -det;
666 25 : if (major)
667 25 : minor = det / major;
668 : else
669 0 : minor = 0.0;
670 25 : if (x_basis)
671 : {
672 25 : *basis_scale = major;
673 25 : *normal_scale = minor;
674 : }
675 : else
676 : {
677 0 : *basis_scale = minor;
678 0 : *normal_scale = major;
679 : }
680 : }
681 :
682 25 : return CAIRO_STATUS_SUCCESS;
683 : }
684 :
685 : cairo_bool_t
686 2 : _cairo_matrix_is_identity (const cairo_matrix_t *matrix)
687 : {
688 6 : return (matrix->xx == 1.0 && matrix->yx == 0.0 &&
689 6 : matrix->xy == 0.0 && matrix->yy == 1.0 &&
690 6 : matrix->x0 == 0.0 && matrix->y0 == 0.0);
691 : }
692 :
693 : cairo_bool_t
694 0 : _cairo_matrix_is_translation (const cairo_matrix_t *matrix)
695 : {
696 0 : return (matrix->xx == 1.0 && matrix->yx == 0.0 &&
697 0 : matrix->xy == 0.0 && matrix->yy == 1.0);
698 : }
699 :
700 : cairo_bool_t
701 0 : _cairo_matrix_is_integer_translation (const cairo_matrix_t *matrix,
702 : int *itx, int *ity)
703 : {
704 0 : if (_cairo_matrix_is_translation (matrix))
705 : {
706 0 : cairo_fixed_t x0_fixed = _cairo_fixed_from_double (matrix->x0);
707 0 : cairo_fixed_t y0_fixed = _cairo_fixed_from_double (matrix->y0);
708 :
709 0 : if (_cairo_fixed_is_integer (x0_fixed) &&
710 0 : _cairo_fixed_is_integer (y0_fixed))
711 : {
712 0 : if (itx)
713 0 : *itx = _cairo_fixed_integer_part (x0_fixed);
714 0 : if (ity)
715 0 : *ity = _cairo_fixed_integer_part (y0_fixed);
716 :
717 0 : return TRUE;
718 : }
719 : }
720 :
721 0 : return FALSE;
722 : }
723 :
724 : cairo_bool_t
725 0 : _cairo_matrix_has_unity_scale (const cairo_matrix_t *matrix)
726 : {
727 0 : if (matrix->xy == 0.0 && matrix->yx == 0.0) {
728 0 : if (! (matrix->xx == 1.0 || matrix->xx == -1.0))
729 0 : return FALSE;
730 0 : if (! (matrix->yy == 1.0 || matrix->yy == -1.0))
731 0 : return FALSE;
732 0 : } else if (matrix->xx == 0.0 && matrix->yy == 0.0) {
733 0 : if (! (matrix->xy == 1.0 || matrix->xy == -1.0))
734 0 : return FALSE;
735 0 : if (! (matrix->yx == 1.0 || matrix->yx == -1.0))
736 0 : return FALSE;
737 : } else
738 0 : return FALSE;
739 :
740 0 : return TRUE;
741 : }
742 :
743 : /* By pixel exact here, we mean a matrix that is composed only of
744 : * 90 degree rotations, flips, and integer translations and produces a 1:1
745 : * mapping between source and destination pixels. If we transform an image
746 : * with a pixel-exact matrix, filtering is not useful.
747 : */
748 : cairo_bool_t
749 0 : _cairo_matrix_is_pixel_exact (const cairo_matrix_t *matrix)
750 : {
751 : cairo_fixed_t x0_fixed, y0_fixed;
752 :
753 0 : if (! _cairo_matrix_has_unity_scale (matrix))
754 0 : return FALSE;
755 :
756 0 : x0_fixed = _cairo_fixed_from_double (matrix->x0);
757 0 : y0_fixed = _cairo_fixed_from_double (matrix->y0);
758 :
759 0 : return _cairo_fixed_is_integer (x0_fixed) && _cairo_fixed_is_integer (y0_fixed);
760 : }
761 :
762 : /*
763 : A circle in user space is transformed into an ellipse in device space.
764 :
765 : The following is a derivation of a formula to calculate the length of the
766 : major axis for this ellipse; this is useful for error bounds calculations.
767 :
768 : Thanks to Walter Brisken <wbrisken@aoc.nrao.edu> for this derivation:
769 :
770 : 1. First some notation:
771 :
772 : All capital letters represent vectors in two dimensions. A prime '
773 : represents a transformed coordinate. Matrices are written in underlined
774 : form, ie _R_. Lowercase letters represent scalar real values.
775 :
776 : 2. The question has been posed: What is the maximum expansion factor
777 : achieved by the linear transformation
778 :
779 : X' = X _R_
780 :
781 : where _R_ is a real-valued 2x2 matrix with entries:
782 :
783 : _R_ = [a b]
784 : [c d] .
785 :
786 : In other words, what is the maximum radius, MAX[ |X'| ], reached for any
787 : X on the unit circle ( |X| = 1 ) ?
788 :
789 : 3. Some useful formulae
790 :
791 : (A) through (C) below are standard double-angle formulae. (D) is a lesser
792 : known result and is derived below:
793 :
794 : (A) sin²(θ) = (1 - cos(2*θ))/2
795 : (B) cos²(θ) = (1 + cos(2*θ))/2
796 : (C) sin(θ)*cos(θ) = sin(2*θ)/2
797 : (D) MAX[a*cos(θ) + b*sin(θ)] = sqrt(a² + b²)
798 :
799 : Proof of (D):
800 :
801 : find the maximum of the function by setting the derivative to zero:
802 :
803 : -a*sin(θ)+b*cos(θ) = 0
804 :
805 : From this it follows that
806 :
807 : tan(θ) = b/a
808 :
809 : and hence
810 :
811 : sin(θ) = b/sqrt(a² + b²)
812 :
813 : and
814 :
815 : cos(θ) = a/sqrt(a² + b²)
816 :
817 : Thus the maximum value is
818 :
819 : MAX[a*cos(θ) + b*sin(θ)] = (a² + b²)/sqrt(a² + b²)
820 : = sqrt(a² + b²)
821 :
822 : 4. Derivation of maximum expansion
823 :
824 : To find MAX[ |X'| ] we search brute force method using calculus. The unit
825 : circle on which X is constrained is to be parameterized by t:
826 :
827 : X(θ) = (cos(θ), sin(θ))
828 :
829 : Thus
830 :
831 : X'(θ) = X(θ) * _R_ = (cos(θ), sin(θ)) * [a b]
832 : [c d]
833 : = (a*cos(θ) + c*sin(θ), b*cos(θ) + d*sin(θ)).
834 :
835 : Define
836 :
837 : r(θ) = |X'(θ)|
838 :
839 : Thus
840 :
841 : r²(θ) = (a*cos(θ) + c*sin(θ))² + (b*cos(θ) + d*sin(θ))²
842 : = (a² + b²)*cos²(θ) + (c² + d²)*sin²(θ)
843 : + 2*(a*c + b*d)*cos(θ)*sin(θ)
844 :
845 : Now apply the double angle formulae (A) to (C) from above:
846 :
847 : r²(θ) = (a² + b² + c² + d²)/2
848 : + (a² + b² - c² - d²)*cos(2*θ)/2
849 : + (a*c + b*d)*sin(2*θ)
850 : = f + g*cos(φ) + h*sin(φ)
851 :
852 : Where
853 :
854 : f = (a² + b² + c² + d²)/2
855 : g = (a² + b² - c² - d²)/2
856 : h = (a*c + d*d)
857 : φ = 2*θ
858 :
859 : It is clear that MAX[ |X'| ] = sqrt(MAX[ r² ]). Here we determine MAX[ r² ]
860 : using (D) from above:
861 :
862 : MAX[ r² ] = f + sqrt(g² + h²)
863 :
864 : And finally
865 :
866 : MAX[ |X'| ] = sqrt( f + sqrt(g² + h²) )
867 :
868 : Which is the solution to this problem.
869 :
870 : Walter Brisken
871 : 2004/10/08
872 :
873 : (Note that the minor axis length is at the minimum of the above solution,
874 : which is just sqrt ( f - sqrt(g² + h²) ) given the symmetry of (D)).
875 :
876 :
877 : For another derivation of the same result, using Singular Value Decomposition,
878 : see doc/tutorial/src/singular.c.
879 : */
880 :
881 : /* determine the length of the major and minor axes of a circle of the given
882 : radius after applying the transformation matrix. */
883 : void
884 0 : _cairo_matrix_transformed_circle_axes (const cairo_matrix_t *matrix,
885 : double radius,
886 : double *major,
887 : double *minor)
888 : {
889 : double a, b, c, d, f, g, h, i, j, k;
890 :
891 0 : _cairo_matrix_get_affine (matrix,
892 : &a, &b,
893 : &c, &d,
894 : NULL, NULL);
895 :
896 0 : i = a*a + b*b;
897 0 : j = c*c + d*d;
898 0 : k = a*c + b*d;
899 :
900 0 : f = 0.5 * (i + j);
901 0 : g = 0.5 * (i - j);
902 0 : h = hypot (g, k);
903 :
904 0 : if (major)
905 0 : *major = radius * sqrt (f + h);
906 0 : if (minor)
907 0 : *minor = radius * sqrt (f - h);
908 0 : }
909 :
910 : /* determine the length of the major axis of a circle of the given radius
911 : after applying the transformation matrix. */
912 : double
913 0 : _cairo_matrix_transformed_circle_major_axis (const cairo_matrix_t *matrix,
914 : double radius)
915 : {
916 : double major;
917 :
918 0 : _cairo_matrix_transformed_circle_axes (matrix, radius, &major, NULL);
919 :
920 0 : return major;
921 : }
922 :
923 : void
924 0 : _cairo_matrix_to_pixman_matrix (const cairo_matrix_t *matrix,
925 : pixman_transform_t *pixman_transform,
926 : double xc,
927 : double yc)
928 : {
929 : static const pixman_transform_t pixman_identity_transform = {{
930 : {1 << 16, 0, 0},
931 : { 0, 1 << 16, 0},
932 : { 0, 0, 1 << 16}
933 : }};
934 :
935 0 : if (_cairo_matrix_is_identity (matrix)) {
936 0 : *pixman_transform = pixman_identity_transform;
937 : } else {
938 : cairo_matrix_t inv;
939 : unsigned max_iterations;
940 :
941 0 : pixman_transform->matrix[0][0] = _cairo_fixed_16_16_from_double (matrix->xx);
942 0 : pixman_transform->matrix[0][1] = _cairo_fixed_16_16_from_double (matrix->xy);
943 0 : pixman_transform->matrix[0][2] = _cairo_fixed_16_16_from_double (matrix->x0);
944 :
945 0 : pixman_transform->matrix[1][0] = _cairo_fixed_16_16_from_double (matrix->yx);
946 0 : pixman_transform->matrix[1][1] = _cairo_fixed_16_16_from_double (matrix->yy);
947 0 : pixman_transform->matrix[1][2] = _cairo_fixed_16_16_from_double (matrix->y0);
948 :
949 0 : pixman_transform->matrix[2][0] = 0;
950 0 : pixman_transform->matrix[2][1] = 0;
951 0 : pixman_transform->matrix[2][2] = 1 << 16;
952 :
953 : /* The conversion above breaks cairo's translation invariance:
954 : * a translation of (a, b) in device space translates to
955 : * a translation of (xx * a + xy * b, yx * a + yy * b)
956 : * for cairo, while pixman uses rounded versions of xx ... yy.
957 : * This error increases as a and b get larger.
958 : *
959 : * To compensate for this, we fix the point (xc, yc) in pattern
960 : * space and adjust pixman's transform to agree with cairo's at
961 : * that point.
962 : */
963 :
964 0 : if (_cairo_matrix_has_unity_scale (matrix))
965 0 : return;
966 :
967 : /* Note: If we can't invert the transformation, skip the adjustment. */
968 0 : inv = *matrix;
969 0 : if (cairo_matrix_invert (&inv) != CAIRO_STATUS_SUCCESS)
970 0 : return;
971 :
972 : /* find the pattern space coordinate that maps to (xc, yc) */
973 0 : xc += .5; yc += .5; /* offset for the pixel centre */
974 0 : max_iterations = 5;
975 : do {
976 : double x,y;
977 : pixman_vector_t vector;
978 : cairo_fixed_16_16_t dx, dy;
979 :
980 0 : vector.vector[0] = _cairo_fixed_16_16_from_double (xc);
981 0 : vector.vector[1] = _cairo_fixed_16_16_from_double (yc);
982 0 : vector.vector[2] = 1 << 16;
983 :
984 0 : if (! pixman_transform_point_3d (pixman_transform, &vector))
985 0 : return;
986 :
987 0 : x = pixman_fixed_to_double (vector.vector[0]);
988 0 : y = pixman_fixed_to_double (vector.vector[1]);
989 0 : cairo_matrix_transform_point (&inv, &x, &y);
990 :
991 : /* Ideally, the vector should now be (xc, yc).
992 : * We can now compensate for the resulting error.
993 : */
994 0 : x -= xc;
995 0 : y -= yc;
996 0 : cairo_matrix_transform_distance (matrix, &x, &y);
997 0 : dx = _cairo_fixed_16_16_from_double (x);
998 0 : dy = _cairo_fixed_16_16_from_double (y);
999 0 : pixman_transform->matrix[0][2] -= dx;
1000 0 : pixman_transform->matrix[1][2] -= dy;
1001 :
1002 0 : if (dx == 0 && dy == 0)
1003 0 : break;
1004 0 : } while (--max_iterations);
1005 : }
1006 : }
|
