Subversion Repositories Scribus

Rev

Go to most recent revision | Details | Last modification | View Log | RSS feed

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