Back to index

lightning-sunbird  0.9+nobinonly
cairo-matrix.c
Go to the documentation of this file.
00001 /* cairo - a vector graphics library with display and print output
00002  *
00003  * Copyright © 2002 University of Southern California
00004  *
00005  * This library is free software; you can redistribute it and/or
00006  * modify it either under the terms of the GNU Lesser General Public
00007  * License version 2.1 as published by the Free Software Foundation
00008  * (the "LGPL") or, at your option, under the terms of the Mozilla
00009  * Public License Version 1.1 (the "MPL"). If you do not alter this
00010  * notice, a recipient may use your version of this file under either
00011  * the MPL or the LGPL.
00012  *
00013  * You should have received a copy of the LGPL along with this library
00014  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
00015  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
00016  * You should have received a copy of the MPL along with this library
00017  * in the file COPYING-MPL-1.1
00018  *
00019  * The contents of this file are subject to the Mozilla Public License
00020  * Version 1.1 (the "License"); you may not use this file except in
00021  * compliance with the License. You may obtain a copy of the License at
00022  * http://www.mozilla.org/MPL/
00023  *
00024  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
00025  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
00026  * the specific language governing rights and limitations.
00027  *
00028  * The Original Code is the cairo graphics library.
00029  *
00030  * The Initial Developer of the Original Code is University of Southern
00031  * California.
00032  *
00033  * Contributor(s):
00034  *     Carl D. Worth <cworth@cworth.org>
00035  */
00036 
00037 #define _GNU_SOURCE
00038 #include <stdlib.h>
00039 
00040 #include "cairoint.h"
00041 
00042 static void
00043 _cairo_matrix_scalar_multiply (cairo_matrix_t *matrix, double scalar);
00044 
00045 static void
00046 _cairo_matrix_compute_adjoint (cairo_matrix_t *matrix);
00047 
00054 void
00055 cairo_matrix_init_identity (cairo_matrix_t *matrix)
00056 {
00057     cairo_matrix_init (matrix,
00058                      1, 0,
00059                      0, 1,
00060                      0, 0);
00061 }
00062 slim_hidden_def(cairo_matrix_init_identity);
00063 
00082 void
00083 cairo_matrix_init (cairo_matrix_t *matrix,
00084                  double xx, double yx,
00085 
00086                  double xy, double yy,
00087                  double x0, double y0)
00088 {
00089     matrix->xx = xx; matrix->yx = yx;
00090     matrix->xy = xy; matrix->yy = yy;
00091     matrix->x0 = x0; matrix->y0 = y0;
00092 }
00093 slim_hidden_def(cairo_matrix_init);
00094 
00115 void
00116 _cairo_matrix_get_affine (const cairo_matrix_t *matrix,
00117                        double *xx, double *yx,
00118                        double *xy, double *yy,
00119                        double *x0, double *y0)
00120 {
00121     *xx  = matrix->xx;
00122     *yx  = matrix->yx;
00123 
00124     *xy  = matrix->xy;
00125     *yy  = matrix->yy;
00126 
00127     if (x0)
00128        *x0 = matrix->x0;
00129     if (y0)
00130        *y0 = matrix->y0;
00131 }
00132 
00142 void
00143 cairo_matrix_init_translate (cairo_matrix_t *matrix,
00144                           double tx, double ty)
00145 {
00146     cairo_matrix_init (matrix,
00147                      1, 0,
00148                      0, 1,
00149                      tx, ty);
00150 }
00151 slim_hidden_def(cairo_matrix_init_translate);
00152 
00164 void
00165 cairo_matrix_translate (cairo_matrix_t *matrix, double tx, double ty)
00166 {
00167     cairo_matrix_t tmp;
00168 
00169     cairo_matrix_init_translate (&tmp, tx, ty);
00170 
00171     cairo_matrix_multiply (matrix, &tmp, matrix);
00172 }
00173 
00183 void
00184 cairo_matrix_init_scale (cairo_matrix_t *matrix,
00185                       double sx, double sy)
00186 {
00187     cairo_matrix_init (matrix,
00188                      sx,  0,
00189                      0, sy,
00190                      0, 0);
00191 }
00192 slim_hidden_def(cairo_matrix_init_scale);
00193 
00204 void
00205 cairo_matrix_scale (cairo_matrix_t *matrix, double sx, double sy)
00206 {
00207     cairo_matrix_t tmp;
00208 
00209     cairo_matrix_init_scale (&tmp, sx, sy);
00210 
00211     cairo_matrix_multiply (matrix, &tmp, matrix);
00212 }
00213 slim_hidden_def(cairo_matrix_scale);
00214 
00226 void
00227 cairo_matrix_init_rotate (cairo_matrix_t *matrix,
00228                        double radians)
00229 {
00230     double  s;
00231     double  c;
00232 
00233     s = sin (radians);
00234     c = cos (radians);
00235 
00236     cairo_matrix_init (matrix,
00237                      c, s,
00238                      -s, c,
00239                      0, 0);
00240 }
00241 slim_hidden_def(cairo_matrix_init_rotate);
00242 
00257 void
00258 cairo_matrix_rotate (cairo_matrix_t *matrix, double radians)
00259 {
00260     cairo_matrix_t tmp;
00261 
00262     cairo_matrix_init_rotate (&tmp, radians);
00263 
00264     cairo_matrix_multiply (matrix, &tmp, matrix);
00265 }
00266 
00281 /*
00282  * XXX: The ordering of the arguments to this function corresponds
00283  *      to [row_vector]*A*B. If we want to use column vectors instead,
00284  *      then we need to switch the two arguments and fix up all
00285  *      uses.
00286  */
00287 void
00288 cairo_matrix_multiply (cairo_matrix_t *result, const cairo_matrix_t *a, const cairo_matrix_t *b)
00289 {
00290     cairo_matrix_t r;
00291 
00292     r.xx = a->xx * b->xx + a->yx * b->xy;
00293     r.yx = a->xx * b->yx + a->yx * b->yy;
00294 
00295     r.xy = a->xy * b->xx + a->yy * b->xy;
00296     r.yy = a->xy * b->yx + a->yy * b->yy;
00297 
00298     r.x0 = a->x0 * b->xx + a->y0 * b->xy + b->x0;
00299     r.y0 = a->x0 * b->yx + a->y0 * b->yy + b->y0;
00300 
00301     *result = r;
00302 }
00303 slim_hidden_def(cairo_matrix_multiply);
00304 
00326 void
00327 cairo_matrix_transform_distance (const cairo_matrix_t *matrix, double *dx, double *dy)
00328 {
00329     double new_x, new_y;
00330 
00331     new_x = (matrix->xx * *dx + matrix->xy * *dy);
00332     new_y = (matrix->yx * *dx + matrix->yy * *dy);
00333 
00334     *dx = new_x;
00335     *dy = new_y;
00336 }
00337 slim_hidden_def(cairo_matrix_transform_distance);
00338 
00347 void
00348 cairo_matrix_transform_point (const cairo_matrix_t *matrix, double *x, double *y)
00349 {
00350     cairo_matrix_transform_distance (matrix, x, y);
00351 
00352     *x += matrix->x0;
00353     *y += matrix->y0;
00354 }
00355 slim_hidden_def(cairo_matrix_transform_point);
00356 
00357 void
00358 _cairo_matrix_transform_bounding_box (const cairo_matrix_t *matrix,
00359                                   double *x, double *y,
00360                                   double *width, double *height)
00361 {
00362     int i;
00363     double quad_x[4], quad_y[4];
00364     double dx1, dy1;
00365     double dx2, dy2;
00366     double min_x, max_x;
00367     double min_y, max_y;
00368 
00369     quad_x[0] = *x;
00370     quad_y[0] = *y;
00371     cairo_matrix_transform_point (matrix, &quad_x[0], &quad_y[0]);
00372 
00373     dx1 = *width;
00374     dy1 = 0;
00375     cairo_matrix_transform_distance (matrix, &dx1, &dy1);
00376     quad_x[1] = quad_x[0] + dx1;
00377     quad_y[1] = quad_y[0] + dy1;
00378 
00379     dx2 = 0;
00380     dy2 = *height;
00381     cairo_matrix_transform_distance (matrix, &dx2, &dy2);
00382     quad_x[2] = quad_x[0] + dx2;
00383     quad_y[2] = quad_y[0] + dy2;
00384 
00385     quad_x[3] = quad_x[0] + dx1 + dx2;
00386     quad_y[3] = quad_y[0] + dy1 + dy2;
00387 
00388     min_x = max_x = quad_x[0];
00389     min_y = max_y = quad_y[0];
00390 
00391     for (i=1; i < 4; i++) {
00392        if (quad_x[i] < min_x)
00393            min_x = quad_x[i];
00394        if (quad_x[i] > max_x)
00395            max_x = quad_x[i];
00396 
00397        if (quad_y[i] < min_y)
00398            min_y = quad_y[i];
00399        if (quad_y[i] > max_y)
00400            max_y = quad_y[i];
00401     }
00402 
00403     *x = min_x;
00404     *y = min_y;
00405     *width = max_x - min_x;
00406     *height = max_y - min_y;
00407 }
00408 
00409 static void
00410 _cairo_matrix_scalar_multiply (cairo_matrix_t *matrix, double scalar)
00411 {
00412     matrix->xx *= scalar;
00413     matrix->yx *= scalar;
00414 
00415     matrix->xy *= scalar;
00416     matrix->yy *= scalar;
00417 
00418     matrix->x0 *= scalar;
00419     matrix->y0 *= scalar;
00420 }
00421 
00422 /* This function isn't a correct adjoint in that the implicit 1 in the
00423    homogeneous result should actually be ad-bc instead. But, since this
00424    adjoint is only used in the computation of the inverse, which
00425    divides by det (A)=ad-bc anyway, everything works out in the end. */
00426 static void
00427 _cairo_matrix_compute_adjoint (cairo_matrix_t *matrix)
00428 {
00429     /* adj (A) = transpose (C:cofactor (A,i,j)) */
00430     double a, b, c, d, tx, ty;
00431 
00432     _cairo_matrix_get_affine (matrix,
00433                            &a,  &b,
00434                            &c,  &d,
00435                            &tx, &ty);
00436 
00437     cairo_matrix_init (matrix,
00438                      d, -b,
00439                      -c, a,
00440                      c*ty - d*tx, b*tx - a*ty);
00441 }
00442 
00456 cairo_status_t
00457 cairo_matrix_invert (cairo_matrix_t *matrix)
00458 {
00459     /* inv (A) = 1/det (A) * adj (A) */
00460     double det;
00461 
00462     _cairo_matrix_compute_determinant (matrix, &det);
00463     
00464     if (det == 0)
00465        return CAIRO_STATUS_INVALID_MATRIX;
00466 
00467     _cairo_matrix_compute_adjoint (matrix);
00468     _cairo_matrix_scalar_multiply (matrix, 1 / det);
00469 
00470     return CAIRO_STATUS_SUCCESS;
00471 }
00472 slim_hidden_def(cairo_matrix_invert);
00473 
00474 void
00475 _cairo_matrix_compute_determinant (const cairo_matrix_t *matrix,
00476                                double            *det)
00477 {
00478     double a, b, c, d;
00479 
00480     a = matrix->xx; b = matrix->yx;
00481     c = matrix->xy; d = matrix->yy;
00482 
00483     *det = a*d - b*c;
00484 }
00485 
00486 /* Compute the amount that each basis vector is scaled by. */
00487 cairo_status_t
00488 _cairo_matrix_compute_scale_factors (const cairo_matrix_t *matrix,
00489                                  double *sx, double *sy, int x_major)
00490 {
00491     double det;
00492 
00493     _cairo_matrix_compute_determinant (matrix, &det);
00494 
00495     if (det == 0)
00496     {
00497        *sx = *sy = 0;
00498     }
00499     else
00500     {
00501        double x = x_major != 0;
00502        double y = x == 0;
00503        double major, minor;
00504        
00505        cairo_matrix_transform_distance (matrix, &x, &y);
00506        major = sqrt(x*x + y*y);
00507        /*
00508         * ignore mirroring
00509         */
00510        if (det < 0)
00511            det = -det;
00512        if (major)
00513            minor = det / major;
00514        else 
00515            minor = 0.0;
00516        if (x_major)
00517        {
00518            *sx = major;
00519            *sy = minor;
00520        }
00521        else
00522        {
00523            *sx = minor;
00524            *sy = major;
00525        }
00526     }
00527 
00528     return CAIRO_STATUS_SUCCESS;
00529 }
00530 
00531 cairo_bool_t 
00532 _cairo_matrix_is_integer_translation(const cairo_matrix_t *m,
00533                                  int *itx, int *ity)
00534 {
00535     cairo_bool_t is_integer_translation;
00536     cairo_fixed_t x0_fixed, y0_fixed;
00537 
00538     x0_fixed = _cairo_fixed_from_double (m->x0);
00539     y0_fixed = _cairo_fixed_from_double (m->y0);
00540 
00541     is_integer_translation = ((m->xx == 1.0) &&
00542                            (m->yx == 0.0) &&
00543                            (m->xy == 0.0) &&
00544                            (m->yy == 1.0) &&
00545                            (_cairo_fixed_is_integer(x0_fixed)) &&
00546                            (_cairo_fixed_is_integer(y0_fixed)));
00547 
00548     if (! is_integer_translation)
00549        return FALSE;
00550 
00551     if (itx)
00552        *itx = _cairo_fixed_integer_part(x0_fixed);
00553     if (ity)
00554        *ity = _cairo_fixed_integer_part(y0_fixed);
00555 
00556     return TRUE;
00557 }
00558 
00559 /*
00560   A circle in user space is transformed into an ellipse in device space.
00561 
00562   The following is a derivation of a formula to calculate the length of the
00563   major axis for this ellipse; this is useful for error bounds calculations.
00564   
00565   Thanks to Walter Brisken <wbrisken@aoc.nrao.edu> for this derivation:
00566   
00567   1.  First some notation:
00568   
00569   All capital letters represent vectors in two dimensions.  A prime ' 
00570   represents a transformed coordinate.  Matrices are written in underlined
00571   form, ie _R_.  Lowercase letters represent scalar real values.
00572   
00573   2.  The question has been posed:  What is the maximum expansion factor 
00574   achieved by the linear transformation
00575   
00576   X' = X _R_
00577   
00578   where _R_ is a real-valued 2x2 matrix with entries:
00579   
00580   _R_ = [a b]
00581         [c d]  .
00582   
00583   In other words, what is the maximum radius, MAX[ |X'| ], reached for any 
00584   X on the unit circle ( |X| = 1 ) ?
00585   
00586   
00587   3.  Some useful formulae
00588   
00589   (A) through (C) below are standard double-angle formulae.  (D) is a lesser
00590   known result and is derived below:
00591   
00592   (A)  sin²(θ) = (1 - cos(2*θ))/2
00593   (B)  cos²(θ) = (1 + cos(2*θ))/2
00594   (C)  sin(θ)*cos(θ) = sin(2*θ)/2
00595   (D)  MAX[a*cos(θ) + b*sin(θ)] = sqrt(a² + b²)
00596   
00597   Proof of (D):
00598   
00599   find the maximum of the function by setting the derivative to zero:
00600   
00601        -a*sin(θ)+b*cos(θ) = 0
00602   
00603   From this it follows that 
00604   
00605        tan(θ) = b/a 
00606   
00607   and hence 
00608   
00609        sin(θ) = b/sqrt(a² + b²)
00610   
00611   and 
00612   
00613        cos(θ) = a/sqrt(a² + b²)
00614   
00615   Thus the maximum value is
00616   
00617        MAX[a*cos(θ) + b*sin(θ)] = (a² + b²)/sqrt(a² + b²)
00618                                    = sqrt(a² + b²)
00619   
00620   
00621   4.  Derivation of maximum expansion
00622   
00623   To find MAX[ |X'| ] we search brute force method using calculus.  The unit
00624   circle on which X is constrained is to be parameterized by t:
00625   
00626        X(θ) = (cos(θ), sin(θ))
00627   
00628   Thus 
00629   
00630        X'(θ) = X(θ) * _R_ = (cos(θ), sin(θ)) * [a b]
00631                                                [c d]
00632              = (a*cos(θ) + c*sin(θ), b*cos(θ) + d*sin(θ)).
00633   
00634   Define 
00635   
00636        r(θ) = |X'(θ)|
00637   
00638   Thus
00639   
00640        r²(θ) = (a*cos(θ) + c*sin(θ))² + (b*cos(θ) + d*sin(θ))²
00641              = (a² + b²)*cos²(θ) + (c² + d²)*sin²(θ) 
00642                  + 2*(a*c + b*d)*cos(θ)*sin(θ) 
00643   
00644   Now apply the double angle formulae (A) to (C) from above:
00645   
00646        r²(θ) = (a² + b² + c² + d²)/2 
00647             + (a² + b² - c² - d²)*cos(2*θ)/2
00648             + (a*c + b*d)*sin(2*θ)
00649              = f + g*cos(φ) + h*sin(φ)
00650   
00651   Where
00652   
00653        f = (a² + b² + c² + d²)/2
00654        g = (a² + b² - c² - d²)/2
00655        h = (a*c + d*d)
00656        φ = 2*θ
00657   
00658   It is clear that MAX[ |X'| ] = sqrt(MAX[ r² ]).  Here we determine MAX[ r² ]
00659   using (D) from above:
00660   
00661        MAX[ r² ] = f + sqrt(g² + h²)
00662   
00663   And finally
00664 
00665        MAX[ |X'| ] = sqrt( f + sqrt(g² + h²) )
00666 
00667   Which is the solution to this problem.
00668 
00669 
00670   Walter Brisken
00671   2004/10/08
00672 
00673   (Note that the minor axis length is at the minimum of the above solution,
00674   which is just sqrt ( f - sqrt(g² + h²) ) given the symmetry of (D)).
00675 */
00676 
00677 /* determine the length of the major axis of a circle of the given radius
00678    after applying the transformation matrix. */
00679 double
00680 _cairo_matrix_transformed_circle_major_axis (cairo_matrix_t *matrix, double radius)
00681 {
00682     double  a, b, c, d, f, g, h, i, j;
00683 
00684     _cairo_matrix_get_affine (matrix,
00685                               &a, &b,
00686                               &c, &d,
00687                               NULL, NULL);
00688 
00689     i = a*a + b*b;
00690     j = c*c + d*d;
00691 
00692     f = 0.5 * (i + j);
00693     g = 0.5 * (i - j);
00694     h = a*c + b*d;
00695 
00696     return radius * sqrt (f + sqrt (g*g+h*h));
00697 
00698     /*
00699      * we don't need the minor axis length, which is
00700      * double min = radius * sqrt (f - sqrt (g*g+h*h));
00701      */
00702 }