2 * Copyright © 2002 Keith Packard, member of The XFree86 Project, Inc.
3 * Copyright © 2004 Keith Packard
5 * Permission to use, copy, modify, distribute, and sell this software and its
6 * documentation for any purpose is hereby granted without fee, provided that
7 * the above copyright notice appear in all copies and that both that
8 * copyright notice and this permission notice appear in supporting
9 * documentation, and that the name of Keith Packard not be used in
10 * advertising or publicity pertaining to distribution of the software without
11 * specific, written prior permission. Keith Packard makes no
12 * representations about the suitability of this software for any purpose. It
13 * is provided "as is" without express or implied warranty.
15 * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
16 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
17 * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
18 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
19 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
20 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
21 * PERFORMANCE OF THIS SOFTWARE.
30 #include "pixman-private.h"
33 * Compute the smallest value greater than or equal to y which is on a
37 PIXMAN_EXPORT pixman_fixed_t
38 pixman_sample_ceil_y (pixman_fixed_t y, int n)
40 pixman_fixed_t f = pixman_fixed_frac (y);
41 pixman_fixed_t i = pixman_fixed_floor (y);
43 f = DIV (f - Y_FRAC_FIRST (n) + (STEP_Y_SMALL (n) - pixman_fixed_e), STEP_Y_SMALL (n)) * STEP_Y_SMALL (n) +
46 if (f > Y_FRAC_LAST (n))
48 if (pixman_fixed_to_int (i) == 0x7fff)
50 f = 0xffff; /* saturate */
62 * Compute the largest value strictly less than y which is on a
65 PIXMAN_EXPORT pixman_fixed_t
66 pixman_sample_floor_y (pixman_fixed_t y,
69 pixman_fixed_t f = pixman_fixed_frac (y);
70 pixman_fixed_t i = pixman_fixed_floor (y);
72 f = DIV (f - pixman_fixed_e - Y_FRAC_FIRST (n), STEP_Y_SMALL (n)) * STEP_Y_SMALL (n) +
75 if (f < Y_FRAC_FIRST (n))
77 if (pixman_fixed_to_int (i) == 0x8000)
91 * Step an edge by any amount (including negative values)
94 pixman_edge_step (pixman_edge_t *e,
97 pixman_fixed_48_16_t ne;
101 ne = e->e + n * (pixman_fixed_48_16_t) e->dx;
107 int nx = (ne + e->dy - 1) / e->dy;
108 e->e = ne - nx * (pixman_fixed_48_16_t) e->dy;
109 e->x += nx * e->signdx;
116 int nx = (-ne) / e->dy;
117 e->e = ne + nx * (pixman_fixed_48_16_t) e->dy;
118 e->x -= nx * e->signdx;
124 * A private routine to initialize the multi-step
125 * elements of an edge structure
128 _pixman_edge_multi_init (pixman_edge_t * e,
130 pixman_fixed_t *stepx_p,
131 pixman_fixed_t *dx_p)
133 pixman_fixed_t stepx;
134 pixman_fixed_48_16_t ne;
136 ne = n * (pixman_fixed_48_16_t) e->dx;
137 stepx = n * e->stepx;
143 stepx += nx * e->signdx;
151 * Initialize one edge structure given the line endpoints and a
155 pixman_edge_init (pixman_edge_t *e,
157 pixman_fixed_t y_start,
158 pixman_fixed_t x_top,
159 pixman_fixed_t y_top,
160 pixman_fixed_t x_bot,
161 pixman_fixed_t y_bot)
163 pixman_fixed_t dx, dy;
184 e->stepx = -(-dx / dy);
189 _pixman_edge_multi_init (e, STEP_Y_SMALL (n),
190 &e->stepx_small, &e->dx_small);
192 _pixman_edge_multi_init (e, STEP_Y_BIG (n),
193 &e->stepx_big, &e->dx_big);
195 pixman_edge_step (e, y_start - y_top);
199 * Initialize one edge structure given a line, starting y value
200 * and a pixel offset for the line
203 pixman_line_fixed_edge_init (pixman_edge_t * e,
206 const pixman_line_fixed_t *line,
210 pixman_fixed_t x_off_fixed = pixman_int_to_fixed (x_off);
211 pixman_fixed_t y_off_fixed = pixman_int_to_fixed (y_off);
212 const pixman_point_fixed_t *top, *bot;
214 if (line->p1.y <= line->p2.y)
225 pixman_edge_init (e, n, y,
226 top->x + x_off_fixed,
227 top->y + y_off_fixed,
228 bot->x + x_off_fixed,
229 bot->y + y_off_fixed);
233 pixman_add_traps (pixman_image_t * image,
237 pixman_trap_t * traps)
242 pixman_fixed_t x_off_fixed;
243 pixman_fixed_t y_off_fixed;
247 _pixman_image_validate (image);
249 height = image->bits.height;
250 bpp = PIXMAN_FORMAT_BPP (image->bits.format);
252 x_off_fixed = pixman_int_to_fixed (x_off);
253 y_off_fixed = pixman_int_to_fixed (y_off);
257 t = traps->top.y + y_off_fixed;
260 t = pixman_sample_ceil_y (t, bpp);
262 b = traps->bot.y + y_off_fixed;
263 if (pixman_fixed_to_int (b) >= height)
264 b = pixman_int_to_fixed (height) - 1;
265 b = pixman_sample_floor_y (b, bpp);
269 /* initialize edge walkers */
270 pixman_edge_init (&l, bpp, t,
271 traps->top.l + x_off_fixed,
272 traps->top.y + y_off_fixed,
273 traps->bot.l + x_off_fixed,
274 traps->bot.y + y_off_fixed);
276 pixman_edge_init (&r, bpp, t,
277 traps->top.r + x_off_fixed,
278 traps->top.y + y_off_fixed,
279 traps->bot.r + x_off_fixed,
280 traps->bot.y + y_off_fixed);
282 pixman_rasterize_edges (image, &l, &r, t, b);
291 dump_image (pixman_image_t *image,
296 if (!image->type == BITS)
297 printf ("%s is not a regular image\n", title);
299 if (!image->bits.format == PIXMAN_a8)
300 printf ("%s is not an alpha mask\n", title);
302 printf ("\n\n\n%s: \n", title);
304 for (i = 0; i < image->bits.height; ++i)
307 (uint8_t *)&(image->bits.bits[i * image->bits.rowstride]);
309 for (j = 0; j < image->bits.width; ++j)
310 printf ("%c", line[j] ? '#' : ' ');
318 pixman_add_trapezoids (pixman_image_t * image,
322 const pixman_trapezoid_t *traps)
327 dump_image (image, "before");
330 for (i = 0; i < ntraps; ++i)
332 const pixman_trapezoid_t *trap = &(traps[i]);
334 if (!pixman_trapezoid_valid (trap))
337 pixman_rasterize_trapezoid (image, trap, x_off, y_off);
341 dump_image (image, "after");
346 pixman_rasterize_trapezoid (pixman_image_t * image,
347 const pixman_trapezoid_t *trap,
354 pixman_fixed_t y_off_fixed;
358 return_if_fail (image->type == BITS);
360 _pixman_image_validate (image);
362 if (!pixman_trapezoid_valid (trap))
365 height = image->bits.height;
366 bpp = PIXMAN_FORMAT_BPP (image->bits.format);
368 y_off_fixed = pixman_int_to_fixed (y_off);
370 t = trap->top + y_off_fixed;
373 t = pixman_sample_ceil_y (t, bpp);
375 b = trap->bottom + y_off_fixed;
376 if (pixman_fixed_to_int (b) >= height)
377 b = pixman_int_to_fixed (height) - 1;
378 b = pixman_sample_floor_y (b, bpp);
382 /* initialize edge walkers */
383 pixman_line_fixed_edge_init (&l, bpp, t, &trap->left, x_off, y_off);
384 pixman_line_fixed_edge_init (&r, bpp, t, &trap->right, x_off, y_off);
386 pixman_rasterize_edges (image, &l, &r, t, b);
391 * pixman_composite_trapezoids()
393 * All the trapezoids are conceptually rendered to an infinitely big image.
394 * The (0, 0) coordinates of this image are then aligned with the (x, y)
395 * coordinates of the source image, and then both images are aligned with
396 * the (x, y) coordinates of the destination. Then, in principle, compositing
397 * of these three images takes place across the entire destination.
399 * FIXME: However, there is currently a bug, where we restrict this compositing
400 * to the bounding box of the trapezoids. This is incorrect for operators such
401 * as SRC and IN where blank source pixels do have an effect on the destination.
404 pixman_composite_trapezoids (pixman_op_t op,
405 pixman_image_t * src,
406 pixman_image_t * dst,
407 pixman_format_code_t mask_format,
413 const pixman_trapezoid_t * traps)
420 _pixman_image_validate (src);
421 _pixman_image_validate (dst);
423 if (op == PIXMAN_OP_ADD &&
424 (src->common.flags & FAST_PATH_IS_OPAQUE) &&
425 (mask_format == dst->common.extended_format_code) &&
426 !(dst->common.have_clip_region))
428 for (i = 0; i < n_traps; ++i)
430 const pixman_trapezoid_t *trap = &(traps[i]);
432 if (!pixman_trapezoid_valid (trap))
435 pixman_rasterize_trapezoid (dst, trap, x_dst, y_dst);
448 for (i = 0; i < n_traps; ++i)
450 const pixman_trapezoid_t *trap = &(traps[i]);
453 if (!pixman_trapezoid_valid (trap))
456 y1 = pixman_fixed_to_int (trap->top);
460 y2 = pixman_fixed_to_int (pixman_fixed_ceil (trap->bottom));
464 #define EXTEND_MIN(x) \
465 if (pixman_fixed_to_int ((x)) < box.x1) \
466 box.x1 = pixman_fixed_to_int ((x));
467 #define EXTEND_MAX(x) \
468 if (pixman_fixed_to_int (pixman_fixed_ceil ((x))) > box.x2) \
469 box.x2 = pixman_fixed_to_int (pixman_fixed_ceil ((x)));
475 EXTEND(trap->left.p1.x);
476 EXTEND(trap->left.p2.x);
477 EXTEND(trap->right.p1.x);
478 EXTEND(trap->right.p2.x);
481 if (box.x1 >= box.x2 || box.y1 >= box.y2)
484 tmp = pixman_image_create_bits (
485 mask_format, box.x2 - box.x1, box.y2 - box.y1, NULL, -1);
487 for (i = 0; i < n_traps; ++i)
489 const pixman_trapezoid_t *trap = &(traps[i]);
491 if (!pixman_trapezoid_valid (trap))
494 pixman_rasterize_trapezoid (tmp, trap, - box.x1, - box.y1);
497 pixman_image_composite (op, src, tmp, dst,
498 x_src + box.x1, y_src + box.y1,
500 x_dst + box.x1, y_dst + box.y1,
501 box.x2 - box.x1, box.y2 - box.y1);
503 pixman_image_unref (tmp);
508 greater_y (const pixman_point_fixed_t *a, const pixman_point_fixed_t *b)
516 * Note that the definition of this function is a bit odd because
517 * of the X coordinate space (y increasing downwards).
520 clockwise (const pixman_point_fixed_t *ref,
521 const pixman_point_fixed_t *a,
522 const pixman_point_fixed_t *b)
524 pixman_point_fixed_t ad, bd;
526 ad.x = a->x - ref->x;
527 ad.y = a->y - ref->y;
528 bd.x = b->x - ref->x;
529 bd.y = b->y - ref->y;
531 return ((pixman_fixed_32_32_t) bd.y * ad.x -
532 (pixman_fixed_32_32_t) ad.y * bd.x) < 0;
536 triangle_to_trapezoids (const pixman_triangle_t *tri, pixman_trapezoid_t *traps)
538 const pixman_point_fixed_t *top, *left, *right, *tmp;
544 if (greater_y (top, left))
551 if (greater_y (top, right))
558 if (clockwise (top, right, left))
579 traps->left.p1 = *top;
580 traps->left.p2 = *left;
581 traps->right.p1 = *top;
582 traps->right.p2 = *right;
584 if (right->y < left->y)
585 traps->bottom = right->y;
587 traps->bottom = left->y;
591 *traps = *(traps - 1);
593 if (right->y < left->y)
595 traps->top = right->y;
596 traps->bottom = left->y;
597 traps->right.p1 = *right;
598 traps->right.p2 = *left;
602 traps->top = left->y;
603 traps->bottom = right->y;
604 traps->left.p1 = *left;
605 traps->left.p2 = *right;
609 static pixman_trapezoid_t *
610 convert_triangles (int n_tris, const pixman_triangle_t *tris)
612 pixman_trapezoid_t *traps;
618 traps = pixman_malloc_ab (n_tris, 2 * sizeof (pixman_trapezoid_t));
622 for (i = 0; i < n_tris; ++i)
623 triangle_to_trapezoids (&(tris[i]), traps + 2 * i);
629 pixman_composite_triangles (pixman_op_t op,
630 pixman_image_t * src,
631 pixman_image_t * dst,
632 pixman_format_code_t mask_format,
638 const pixman_triangle_t * tris)
640 pixman_trapezoid_t *traps;
642 if ((traps = convert_triangles (n_tris, tris)))
644 pixman_composite_trapezoids (op, src, dst, mask_format,
645 x_src, y_src, x_dst, y_dst,
653 pixman_add_triangles (pixman_image_t *image,
657 const pixman_triangle_t *tris)
659 pixman_trapezoid_t *traps;
661 if ((traps = convert_triangles (n_tris, tris)))
663 pixman_add_trapezoids (image, x_off, y_off,