2 * Copyright © 2008 Keith Packard
4 * Permission to use, copy, modify, distribute, and sell this software and its
5 * documentation for any purpose is hereby granted without fee, provided that
6 * the above copyright notice appear in all copies and that both that copyright
7 * notice and this permission notice appear in supporting documentation, and
8 * that the name of the copyright holders not be used in advertising or
9 * publicity pertaining to distribution of the software without specific,
10 * written prior permission. The copyright holders make no representations
11 * about the suitability of this software for any purpose. It is provided "as
12 * is" without express or implied warranty.
14 * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
15 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
16 * EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY SPECIAL, INDIRECT OR
17 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
18 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
19 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
33 #include "pixman-private.h"
35 #define F(x) pixman_int_to_fixed (x)
38 pixman_transform_init_identity (struct pixman_transform *matrix)
42 memset (matrix, '\0', sizeof (struct pixman_transform));
43 for (i = 0; i < 3; i++)
44 matrix->matrix[i][i] = F (1);
47 typedef pixman_fixed_32_32_t pixman_fixed_34_30_t;
49 PIXMAN_EXPORT pixman_bool_t
50 pixman_transform_point_3d (const struct pixman_transform *transform,
51 struct pixman_vector * vector)
53 struct pixman_vector result;
54 pixman_fixed_32_32_t partial;
55 pixman_fixed_48_16_t v;
58 for (j = 0; j < 3; j++)
61 for (i = 0; i < 3; i++)
63 partial = ((pixman_fixed_48_16_t) transform->matrix[j][i] *
64 (pixman_fixed_48_16_t) vector->vector[i]);
68 if (v > pixman_max_fixed_48_16 || v < pixman_min_fixed_48_16)
71 result.vector[j] = (pixman_fixed_t) v;
76 if (!result.vector[2])
82 PIXMAN_EXPORT pixman_bool_t
83 pixman_transform_point (const struct pixman_transform *transform,
84 struct pixman_vector * vector)
86 pixman_fixed_32_32_t partial;
87 pixman_fixed_34_30_t v[3];
88 pixman_fixed_48_16_t quo;
91 for (j = 0; j < 3; j++)
95 for (i = 0; i < 3; i++)
97 partial = ((pixman_fixed_32_32_t) transform->matrix[j][i] *
98 (pixman_fixed_32_32_t) vector->vector[i]);
106 for (j = 0; j < 2; j++)
108 quo = v[j] / (v[2] >> 16);
109 if (quo > pixman_max_fixed_48_16 || quo < pixman_min_fixed_48_16)
111 vector->vector[j] = (pixman_fixed_t) quo;
114 vector->vector[2] = pixman_fixed_1;
118 PIXMAN_EXPORT pixman_bool_t
119 pixman_transform_multiply (struct pixman_transform * dst,
120 const struct pixman_transform *l,
121 const struct pixman_transform *r)
123 struct pixman_transform d;
127 for (dy = 0; dy < 3; dy++)
129 for (dx = 0; dx < 3; dx++)
131 pixman_fixed_48_16_t v;
132 pixman_fixed_32_32_t partial;
135 for (o = 0; o < 3; o++)
138 (pixman_fixed_32_32_t) l->matrix[dy][o] *
139 (pixman_fixed_32_32_t) r->matrix[o][dx];
144 if (v > pixman_max_fixed_48_16 || v < pixman_min_fixed_48_16)
147 d.matrix[dy][dx] = (pixman_fixed_t) v;
156 pixman_transform_init_scale (struct pixman_transform *t,
160 memset (t, '\0', sizeof (struct pixman_transform));
162 t->matrix[0][0] = sx;
163 t->matrix[1][1] = sy;
164 t->matrix[2][2] = F (1);
167 static pixman_fixed_t
168 fixed_inverse (pixman_fixed_t x)
170 return (pixman_fixed_t) ((((pixman_fixed_48_16_t) F (1)) * F (1)) / x);
173 PIXMAN_EXPORT pixman_bool_t
174 pixman_transform_scale (struct pixman_transform *forward,
175 struct pixman_transform *reverse,
179 struct pixman_transform t;
181 if (sx == 0 || sy == 0)
186 pixman_transform_init_scale (&t, sx, sy);
187 if (!pixman_transform_multiply (forward, &t, forward))
193 pixman_transform_init_scale (&t, fixed_inverse (sx),
195 if (!pixman_transform_multiply (reverse, reverse, &t))
203 pixman_transform_init_rotate (struct pixman_transform *t,
207 memset (t, '\0', sizeof (struct pixman_transform));
210 t->matrix[0][1] = -s;
213 t->matrix[2][2] = F (1);
216 PIXMAN_EXPORT pixman_bool_t
217 pixman_transform_rotate (struct pixman_transform *forward,
218 struct pixman_transform *reverse,
222 struct pixman_transform t;
226 pixman_transform_init_rotate (&t, c, s);
227 if (!pixman_transform_multiply (forward, &t, forward))
233 pixman_transform_init_rotate (&t, c, -s);
234 if (!pixman_transform_multiply (reverse, reverse, &t))
242 pixman_transform_init_translate (struct pixman_transform *t,
246 memset (t, '\0', sizeof (struct pixman_transform));
248 t->matrix[0][0] = F (1);
249 t->matrix[0][2] = tx;
250 t->matrix[1][1] = F (1);
251 t->matrix[1][2] = ty;
252 t->matrix[2][2] = F (1);
255 PIXMAN_EXPORT pixman_bool_t
256 pixman_transform_translate (struct pixman_transform *forward,
257 struct pixman_transform *reverse,
261 struct pixman_transform t;
265 pixman_transform_init_translate (&t, tx, ty);
267 if (!pixman_transform_multiply (forward, &t, forward))
273 pixman_transform_init_translate (&t, -tx, -ty);
275 if (!pixman_transform_multiply (reverse, reverse, &t))
281 PIXMAN_EXPORT pixman_bool_t
282 pixman_transform_bounds (const struct pixman_transform *matrix,
283 struct pixman_box16 * b)
286 struct pixman_vector v[4];
290 v[0].vector[0] = F (b->x1);
291 v[0].vector[1] = F (b->y1);
292 v[0].vector[2] = F (1);
294 v[1].vector[0] = F (b->x2);
295 v[1].vector[1] = F (b->y1);
296 v[1].vector[2] = F (1);
298 v[2].vector[0] = F (b->x2);
299 v[2].vector[1] = F (b->y2);
300 v[2].vector[2] = F (1);
302 v[3].vector[0] = F (b->x1);
303 v[3].vector[1] = F (b->y2);
304 v[3].vector[2] = F (1);
306 for (i = 0; i < 4; i++)
308 if (!pixman_transform_point (matrix, &v[i]))
311 x1 = pixman_fixed_to_int (v[i].vector[0]);
312 y1 = pixman_fixed_to_int (v[i].vector[1]);
313 x2 = pixman_fixed_to_int (pixman_fixed_ceil (v[i].vector[0]));
314 y2 = pixman_fixed_to_int (pixman_fixed_ceil (v[i].vector[1]));
325 if (x1 < b->x1) b->x1 = x1;
326 if (y1 < b->y1) b->y1 = y1;
327 if (x2 > b->x2) b->x2 = x2;
328 if (y2 > b->y2) b->y2 = y2;
335 PIXMAN_EXPORT pixman_bool_t
336 pixman_transform_invert (struct pixman_transform * dst,
337 const struct pixman_transform *src)
339 struct pixman_f_transform m, r;
341 pixman_f_transform_from_pixman_transform (&m, src);
343 if (!pixman_f_transform_invert (&r, &m))
346 if (!pixman_transform_from_pixman_f_transform (dst, &r))
353 within_epsilon (pixman_fixed_t a,
355 pixman_fixed_t epsilon)
357 pixman_fixed_t t = a - b;
365 #define EPSILON (pixman_fixed_t) (2)
367 #define IS_SAME(a, b) (within_epsilon (a, b, EPSILON))
368 #define IS_ZERO(a) (within_epsilon (a, 0, EPSILON))
369 #define IS_ONE(a) (within_epsilon (a, F (1), EPSILON))
371 (within_epsilon (a, F (1), EPSILON) || \
372 within_epsilon (a, F (-1), EPSILON) || \
374 #define IS_INT(a) (IS_ZERO (pixman_fixed_frac (a)))
376 PIXMAN_EXPORT pixman_bool_t
377 pixman_transform_is_identity (const struct pixman_transform *t)
379 return (IS_SAME (t->matrix[0][0], t->matrix[1][1]) &&
380 IS_SAME (t->matrix[0][0], t->matrix[2][2]) &&
381 !IS_ZERO (t->matrix[0][0]) &&
382 IS_ZERO (t->matrix[0][1]) &&
383 IS_ZERO (t->matrix[0][2]) &&
384 IS_ZERO (t->matrix[1][0]) &&
385 IS_ZERO (t->matrix[1][2]) &&
386 IS_ZERO (t->matrix[2][0]) &&
387 IS_ZERO (t->matrix[2][1]));
390 PIXMAN_EXPORT pixman_bool_t
391 pixman_transform_is_scale (const struct pixman_transform *t)
393 return (!IS_ZERO (t->matrix[0][0]) &&
394 IS_ZERO (t->matrix[0][1]) &&
395 IS_ZERO (t->matrix[0][2]) &&
397 IS_ZERO (t->matrix[1][0]) &&
398 !IS_ZERO (t->matrix[1][1]) &&
399 IS_ZERO (t->matrix[1][2]) &&
401 IS_ZERO (t->matrix[2][0]) &&
402 IS_ZERO (t->matrix[2][1]) &&
403 !IS_ZERO (t->matrix[2][2]));
406 PIXMAN_EXPORT pixman_bool_t
407 pixman_transform_is_int_translate (const struct pixman_transform *t)
409 return (IS_ONE (t->matrix[0][0]) &&
410 IS_ZERO (t->matrix[0][1]) &&
411 IS_INT (t->matrix[0][2]) &&
413 IS_ZERO (t->matrix[1][0]) &&
414 IS_ONE (t->matrix[1][1]) &&
415 IS_INT (t->matrix[1][2]) &&
417 IS_ZERO (t->matrix[2][0]) &&
418 IS_ZERO (t->matrix[2][1]) &&
419 IS_ONE (t->matrix[2][2]));
422 PIXMAN_EXPORT pixman_bool_t
423 pixman_transform_is_inverse (const struct pixman_transform *a,
424 const struct pixman_transform *b)
426 struct pixman_transform t;
428 if (!pixman_transform_multiply (&t, a, b))
431 return pixman_transform_is_identity (&t);
435 pixman_f_transform_from_pixman_transform (struct pixman_f_transform * ft,
436 const struct pixman_transform *t)
440 for (j = 0; j < 3; j++)
442 for (i = 0; i < 3; i++)
443 ft->m[j][i] = pixman_fixed_to_double (t->matrix[j][i]);
447 PIXMAN_EXPORT pixman_bool_t
448 pixman_transform_from_pixman_f_transform (struct pixman_transform * t,
449 const struct pixman_f_transform *ft)
453 for (j = 0; j < 3; j++)
455 for (i = 0; i < 3; i++)
457 double d = ft->m[j][i];
458 if (d < -32767.0 || d > 32767.0)
460 d = d * 65536.0 + 0.5;
461 t->matrix[j][i] = (pixman_fixed_t) floor (d);
468 PIXMAN_EXPORT pixman_bool_t
469 pixman_f_transform_invert (struct pixman_f_transform * dst,
470 const struct pixman_f_transform *src)
474 static int a[3] = { 2, 2, 1 };
475 static int b[3] = { 1, 0, 0 };
478 for (i = 0; i < 3; i++)
483 p = src->m[i][0] * (src->m[ai][2] * src->m[bi][1] -
484 src->m[ai][1] * src->m[bi][2]);
494 for (j = 0; j < 3; j++)
496 for (i = 0; i < 3; i++)
504 p = (src->m[ai][aj] * src->m[bi][bj] -
505 src->m[ai][bj] * src->m[bi][aj]);
507 if (((i + j) & 1) != 0)
510 dst->m[j][i] = det * p;
517 PIXMAN_EXPORT pixman_bool_t
518 pixman_f_transform_point (const struct pixman_f_transform *t,
519 struct pixman_f_vector * v)
521 struct pixman_f_vector result;
525 for (j = 0; j < 3; j++)
528 for (i = 0; i < 3; i++)
529 a += t->m[j][i] * v->v[i];
536 for (j = 0; j < 2; j++)
537 v->v[j] = result.v[j] / result.v[2];
545 pixman_f_transform_point_3d (const struct pixman_f_transform *t,
546 struct pixman_f_vector * v)
548 struct pixman_f_vector result;
552 for (j = 0; j < 3; j++)
555 for (i = 0; i < 3; i++)
556 a += t->m[j][i] * v->v[i];
564 pixman_f_transform_multiply (struct pixman_f_transform * dst,
565 const struct pixman_f_transform *l,
566 const struct pixman_f_transform *r)
568 struct pixman_f_transform d;
572 for (dy = 0; dy < 3; dy++)
574 for (dx = 0; dx < 3; dx++)
577 for (o = 0; o < 3; o++)
578 v += l->m[dy][o] * r->m[o][dx];
587 pixman_f_transform_init_scale (struct pixman_f_transform *t,
602 PIXMAN_EXPORT pixman_bool_t
603 pixman_f_transform_scale (struct pixman_f_transform *forward,
604 struct pixman_f_transform *reverse,
608 struct pixman_f_transform t;
610 if (sx == 0 || sy == 0)
615 pixman_f_transform_init_scale (&t, sx, sy);
616 pixman_f_transform_multiply (forward, &t, forward);
621 pixman_f_transform_init_scale (&t, 1 / sx, 1 / sy);
622 pixman_f_transform_multiply (reverse, reverse, &t);
629 pixman_f_transform_init_rotate (struct pixman_f_transform *t,
644 PIXMAN_EXPORT pixman_bool_t
645 pixman_f_transform_rotate (struct pixman_f_transform *forward,
646 struct pixman_f_transform *reverse,
650 struct pixman_f_transform t;
654 pixman_f_transform_init_rotate (&t, c, s);
655 pixman_f_transform_multiply (forward, &t, forward);
660 pixman_f_transform_init_rotate (&t, c, -s);
661 pixman_f_transform_multiply (reverse, reverse, &t);
668 pixman_f_transform_init_translate (struct pixman_f_transform *t,
683 PIXMAN_EXPORT pixman_bool_t
684 pixman_f_transform_translate (struct pixman_f_transform *forward,
685 struct pixman_f_transform *reverse,
689 struct pixman_f_transform t;
693 pixman_f_transform_init_translate (&t, tx, ty);
694 pixman_f_transform_multiply (forward, &t, forward);
699 pixman_f_transform_init_translate (&t, -tx, -ty);
700 pixman_f_transform_multiply (reverse, reverse, &t);
706 PIXMAN_EXPORT pixman_bool_t
707 pixman_f_transform_bounds (const struct pixman_f_transform *t,
708 struct pixman_box16 * b)
710 struct pixman_f_vector v[4];
727 for (i = 0; i < 4; i++)
729 if (!pixman_f_transform_point (t, &v[i]))
732 x1 = floor (v[i].v[0]);
733 y1 = floor (v[i].v[1]);
734 x2 = ceil (v[i].v[0]);
735 y2 = ceil (v[i].v[1]);
746 if (x1 < b->x1) b->x1 = x1;
747 if (y1 < b->y1) b->y1 = y1;
748 if (x2 > b->x2) b->x2 = x2;
749 if (y2 > b->y2) b->y2 = y2;
757 pixman_f_transform_init_identity (struct pixman_f_transform *t)
761 for (j = 0; j < 3; j++)
763 for (i = 0; i < 3; i++)
764 t->m[j][i] = i == j ? 1 : 0;