| /* |
| * Copyright © 2002 Keith Packard, member of The XFree86 Project, Inc. |
| * Copyright © 2004 Keith Packard |
| * |
| * Permission to use, copy, modify, distribute, and sell this software and its |
| * documentation for any purpose is hereby granted without fee, provided that |
| * the above copyright notice appear in all copies and that both that |
| * copyright notice and this permission notice appear in supporting |
| * documentation, and that the name of Keith Packard not be used in |
| * advertising or publicity pertaining to distribution of the software without |
| * specific, written prior permission. Keith Packard makes no |
| * representations about the suitability of this software for any purpose. It |
| * is provided "as is" without express or implied warranty. |
| * |
| * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, |
| * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO |
| * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR |
| * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, |
| * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER |
| * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR |
| * PERFORMANCE OF THIS SOFTWARE. |
| */ |
| |
| #ifdef HAVE_CONFIG_H |
| #include <config.h> |
| #endif |
| |
| #include <stdio.h> |
| #include <stdlib.h> |
| #include "pixman-private.h" |
| |
| /* |
| * Compute the smallest value greater than or equal to y which is on a |
| * grid row. |
| */ |
| |
| PIXMAN_EXPORT pixman_fixed_t |
| pixman_sample_ceil_y (pixman_fixed_t y, int n) |
| { |
| pixman_fixed_t f = pixman_fixed_frac (y); |
| pixman_fixed_t i = pixman_fixed_floor (y); |
| |
| f = DIV (f - Y_FRAC_FIRST (n) + (STEP_Y_SMALL (n) - pixman_fixed_e), STEP_Y_SMALL (n)) * STEP_Y_SMALL (n) + |
| Y_FRAC_FIRST (n); |
| |
| if (f > Y_FRAC_LAST (n)) |
| { |
| if (pixman_fixed_to_int (i) == 0x7fff) |
| { |
| f = 0xffff; /* saturate */ |
| } |
| else |
| { |
| f = Y_FRAC_FIRST (n); |
| i += pixman_fixed_1; |
| } |
| } |
| return (i | f); |
| } |
| |
| /* |
| * Compute the largest value strictly less than y which is on a |
| * grid row. |
| */ |
| PIXMAN_EXPORT pixman_fixed_t |
| pixman_sample_floor_y (pixman_fixed_t y, |
| int n) |
| { |
| pixman_fixed_t f = pixman_fixed_frac (y); |
| pixman_fixed_t i = pixman_fixed_floor (y); |
| |
| f = DIV (f - pixman_fixed_e - Y_FRAC_FIRST (n), STEP_Y_SMALL (n)) * STEP_Y_SMALL (n) + |
| Y_FRAC_FIRST (n); |
| |
| if (f < Y_FRAC_FIRST (n)) |
| { |
| if (pixman_fixed_to_int (i) == 0x8000) |
| { |
| f = 0; /* saturate */ |
| } |
| else |
| { |
| f = Y_FRAC_LAST (n); |
| i -= pixman_fixed_1; |
| } |
| } |
| return (i | f); |
| } |
| |
| /* |
| * Step an edge by any amount (including negative values) |
| */ |
| PIXMAN_EXPORT void |
| pixman_edge_step (pixman_edge_t *e, |
| int n) |
| { |
| pixman_fixed_48_16_t ne; |
| |
| e->x += n * e->stepx; |
| |
| ne = e->e + n * (pixman_fixed_48_16_t) e->dx; |
| |
| if (n >= 0) |
| { |
| if (ne > 0) |
| { |
| int nx = (ne + e->dy - 1) / e->dy; |
| e->e = ne - nx * (pixman_fixed_48_16_t) e->dy; |
| e->x += nx * e->signdx; |
| } |
| } |
| else |
| { |
| if (ne <= -e->dy) |
| { |
| int nx = (-ne) / e->dy; |
| e->e = ne + nx * (pixman_fixed_48_16_t) e->dy; |
| e->x -= nx * e->signdx; |
| } |
| } |
| } |
| |
| /* |
| * A private routine to initialize the multi-step |
| * elements of an edge structure |
| */ |
| static void |
| _pixman_edge_multi_init (pixman_edge_t * e, |
| int n, |
| pixman_fixed_t *stepx_p, |
| pixman_fixed_t *dx_p) |
| { |
| pixman_fixed_t stepx; |
| pixman_fixed_48_16_t ne; |
| |
| ne = n * (pixman_fixed_48_16_t) e->dx; |
| stepx = n * e->stepx; |
| |
| if (ne > 0) |
| { |
| int nx = ne / e->dy; |
| ne -= nx * (pixman_fixed_48_16_t)e->dy; |
| stepx += nx * e->signdx; |
| } |
| |
| *dx_p = ne; |
| *stepx_p = stepx; |
| } |
| |
| /* |
| * Initialize one edge structure given the line endpoints and a |
| * starting y value |
| */ |
| PIXMAN_EXPORT void |
| pixman_edge_init (pixman_edge_t *e, |
| int n, |
| pixman_fixed_t y_start, |
| pixman_fixed_t x_top, |
| pixman_fixed_t y_top, |
| pixman_fixed_t x_bot, |
| pixman_fixed_t y_bot) |
| { |
| pixman_fixed_t dx, dy; |
| |
| e->x = x_top; |
| e->e = 0; |
| dx = x_bot - x_top; |
| dy = y_bot - y_top; |
| e->dy = dy; |
| e->dx = 0; |
| |
| if (dy) |
| { |
| if (dx >= 0) |
| { |
| e->signdx = 1; |
| e->stepx = dx / dy; |
| e->dx = dx % dy; |
| e->e = -dy; |
| } |
| else |
| { |
| e->signdx = -1; |
| e->stepx = -(-dx / dy); |
| e->dx = -dx % dy; |
| e->e = 0; |
| } |
| |
| _pixman_edge_multi_init (e, STEP_Y_SMALL (n), |
| &e->stepx_small, &e->dx_small); |
| |
| _pixman_edge_multi_init (e, STEP_Y_BIG (n), |
| &e->stepx_big, &e->dx_big); |
| } |
| pixman_edge_step (e, y_start - y_top); |
| } |
| |
| /* |
| * Initialize one edge structure given a line, starting y value |
| * and a pixel offset for the line |
| */ |
| PIXMAN_EXPORT void |
| pixman_line_fixed_edge_init (pixman_edge_t * e, |
| int n, |
| pixman_fixed_t y, |
| const pixman_line_fixed_t *line, |
| int x_off, |
| int y_off) |
| { |
| pixman_fixed_t x_off_fixed = pixman_int_to_fixed (x_off); |
| pixman_fixed_t y_off_fixed = pixman_int_to_fixed (y_off); |
| const pixman_point_fixed_t *top, *bot; |
| |
| if (line->p1.y <= line->p2.y) |
| { |
| top = &line->p1; |
| bot = &line->p2; |
| } |
| else |
| { |
| top = &line->p2; |
| bot = &line->p1; |
| } |
| |
| pixman_edge_init (e, n, y, |
| top->x + x_off_fixed, |
| top->y + y_off_fixed, |
| bot->x + x_off_fixed, |
| bot->y + y_off_fixed); |
| } |
| |
| PIXMAN_EXPORT void |
| pixman_add_traps (pixman_image_t * image, |
| int16_t x_off, |
| int16_t y_off, |
| int ntrap, |
| const pixman_trap_t *traps) |
| { |
| int bpp; |
| int height; |
| |
| pixman_fixed_t x_off_fixed; |
| pixman_fixed_t y_off_fixed; |
| pixman_edge_t l, r; |
| pixman_fixed_t t, b; |
| |
| _pixman_image_validate (image); |
| |
| height = image->bits.height; |
| bpp = PIXMAN_FORMAT_BPP (image->bits.format); |
| |
| x_off_fixed = pixman_int_to_fixed (x_off); |
| y_off_fixed = pixman_int_to_fixed (y_off); |
| |
| while (ntrap--) |
| { |
| t = traps->top.y + y_off_fixed; |
| if (t < 0) |
| t = 0; |
| t = pixman_sample_ceil_y (t, bpp); |
| |
| b = traps->bot.y + y_off_fixed; |
| if (pixman_fixed_to_int (b) >= height) |
| b = pixman_int_to_fixed (height) - 1; |
| b = pixman_sample_floor_y (b, bpp); |
| |
| if (b >= t) |
| { |
| /* initialize edge walkers */ |
| pixman_edge_init (&l, bpp, t, |
| traps->top.l + x_off_fixed, |
| traps->top.y + y_off_fixed, |
| traps->bot.l + x_off_fixed, |
| traps->bot.y + y_off_fixed); |
| |
| pixman_edge_init (&r, bpp, t, |
| traps->top.r + x_off_fixed, |
| traps->top.y + y_off_fixed, |
| traps->bot.r + x_off_fixed, |
| traps->bot.y + y_off_fixed); |
| |
| pixman_rasterize_edges (image, &l, &r, t, b); |
| } |
| |
| traps++; |
| } |
| } |
| |
| #if 0 |
| static void |
| dump_image (pixman_image_t *image, |
| const char * title) |
| { |
| int i, j; |
| |
| if (!image->type == BITS) |
| printf ("%s is not a regular image\n", title); |
| |
| if (!image->bits.format == PIXMAN_a8) |
| printf ("%s is not an alpha mask\n", title); |
| |
| printf ("\n\n\n%s: \n", title); |
| |
| for (i = 0; i < image->bits.height; ++i) |
| { |
| uint8_t *line = |
| (uint8_t *)&(image->bits.bits[i * image->bits.rowstride]); |
| |
| for (j = 0; j < image->bits.width; ++j) |
| printf ("%c", line[j] ? '#' : ' '); |
| |
| printf ("\n"); |
| } |
| } |
| #endif |
| |
| PIXMAN_EXPORT void |
| pixman_add_trapezoids (pixman_image_t * image, |
| int16_t x_off, |
| int y_off, |
| int ntraps, |
| const pixman_trapezoid_t *traps) |
| { |
| int i; |
| |
| #if 0 |
| dump_image (image, "before"); |
| #endif |
| |
| for (i = 0; i < ntraps; ++i) |
| { |
| const pixman_trapezoid_t *trap = &(traps[i]); |
| |
| if (!pixman_trapezoid_valid (trap)) |
| continue; |
| |
| pixman_rasterize_trapezoid (image, trap, x_off, y_off); |
| } |
| |
| #if 0 |
| dump_image (image, "after"); |
| #endif |
| } |
| |
| PIXMAN_EXPORT void |
| pixman_rasterize_trapezoid (pixman_image_t * image, |
| const pixman_trapezoid_t *trap, |
| int x_off, |
| int y_off) |
| { |
| int bpp; |
| int height; |
| |
| pixman_fixed_t y_off_fixed; |
| pixman_edge_t l, r; |
| pixman_fixed_t t, b; |
| |
| return_if_fail (image->type == BITS); |
| |
| _pixman_image_validate (image); |
| |
| if (!pixman_trapezoid_valid (trap)) |
| return; |
| |
| height = image->bits.height; |
| bpp = PIXMAN_FORMAT_BPP (image->bits.format); |
| |
| y_off_fixed = pixman_int_to_fixed (y_off); |
| |
| t = trap->top + y_off_fixed; |
| if (t < 0) |
| t = 0; |
| t = pixman_sample_ceil_y (t, bpp); |
| |
| b = trap->bottom + y_off_fixed; |
| if (pixman_fixed_to_int (b) >= height) |
| b = pixman_int_to_fixed (height) - 1; |
| b = pixman_sample_floor_y (b, bpp); |
| |
| if (b >= t) |
| { |
| /* initialize edge walkers */ |
| pixman_line_fixed_edge_init (&l, bpp, t, &trap->left, x_off, y_off); |
| pixman_line_fixed_edge_init (&r, bpp, t, &trap->right, x_off, y_off); |
| |
| pixman_rasterize_edges (image, &l, &r, t, b); |
| } |
| } |
| |
| static const pixman_bool_t zero_src_has_no_effect[PIXMAN_N_OPERATORS] = |
| { |
| FALSE, /* Clear 0 0 */ |
| FALSE, /* Src 1 0 */ |
| TRUE, /* Dst 0 1 */ |
| TRUE, /* Over 1 1-Aa */ |
| TRUE, /* OverReverse 1-Ab 1 */ |
| FALSE, /* In Ab 0 */ |
| FALSE, /* InReverse 0 Aa */ |
| FALSE, /* Out 1-Ab 0 */ |
| TRUE, /* OutReverse 0 1-Aa */ |
| TRUE, /* Atop Ab 1-Aa */ |
| FALSE, /* AtopReverse 1-Ab Aa */ |
| TRUE, /* Xor 1-Ab 1-Aa */ |
| TRUE, /* Add 1 1 */ |
| }; |
| |
| static pixman_bool_t |
| get_trap_extents (pixman_op_t op, pixman_image_t *dest, |
| const pixman_trapezoid_t *traps, int n_traps, |
| pixman_box32_t *box) |
| { |
| int i; |
| |
| /* When the operator is such that a zero source has an |
| * effect on the underlying image, we have to |
| * composite across the entire destination |
| */ |
| if (!zero_src_has_no_effect [op]) |
| { |
| box->x1 = 0; |
| box->y1 = 0; |
| box->x2 = dest->bits.width; |
| box->y2 = dest->bits.height; |
| return TRUE; |
| } |
| |
| box->x1 = INT32_MAX; |
| box->y1 = INT32_MAX; |
| box->x2 = INT32_MIN; |
| box->y2 = INT32_MIN; |
| |
| for (i = 0; i < n_traps; ++i) |
| { |
| const pixman_trapezoid_t *trap = &(traps[i]); |
| int y1, y2; |
| |
| if (!pixman_trapezoid_valid (trap)) |
| continue; |
| |
| y1 = pixman_fixed_to_int (trap->top); |
| if (y1 < box->y1) |
| box->y1 = y1; |
| |
| y2 = pixman_fixed_to_int (pixman_fixed_ceil (trap->bottom)); |
| if (y2 > box->y2) |
| box->y2 = y2; |
| |
| #define EXTEND_MIN(x) \ |
| if (pixman_fixed_to_int ((x)) < box->x1) \ |
| box->x1 = pixman_fixed_to_int ((x)); |
| #define EXTEND_MAX(x) \ |
| if (pixman_fixed_to_int (pixman_fixed_ceil ((x))) > box->x2) \ |
| box->x2 = pixman_fixed_to_int (pixman_fixed_ceil ((x))); |
| |
| #define EXTEND(x) \ |
| EXTEND_MIN(x); \ |
| EXTEND_MAX(x); |
| |
| EXTEND(trap->left.p1.x); |
| EXTEND(trap->left.p2.x); |
| EXTEND(trap->right.p1.x); |
| EXTEND(trap->right.p2.x); |
| } |
| |
| if (box->x1 >= box->x2 || box->y1 >= box->y2) |
| return FALSE; |
| |
| return TRUE; |
| } |
| |
| /* |
| * pixman_composite_trapezoids() |
| * |
| * All the trapezoids are conceptually rendered to an infinitely big image. |
| * The (0, 0) coordinates of this image are then aligned with the (x, y) |
| * coordinates of the source image, and then both images are aligned with |
| * the (x, y) coordinates of the destination. Then these three images are |
| * composited across the entire destination. |
| */ |
| PIXMAN_EXPORT void |
| pixman_composite_trapezoids (pixman_op_t op, |
| pixman_image_t * src, |
| pixman_image_t * dst, |
| pixman_format_code_t mask_format, |
| int x_src, |
| int y_src, |
| int x_dst, |
| int y_dst, |
| int n_traps, |
| const pixman_trapezoid_t * traps) |
| { |
| int i; |
| |
| return_if_fail (PIXMAN_FORMAT_TYPE (mask_format) == PIXMAN_TYPE_A); |
| |
| if (n_traps <= 0) |
| return; |
| |
| _pixman_image_validate (src); |
| _pixman_image_validate (dst); |
| |
| if (op == PIXMAN_OP_ADD && |
| (src->common.flags & FAST_PATH_IS_OPAQUE) && |
| (mask_format == dst->common.extended_format_code) && |
| !(dst->common.have_clip_region)) |
| { |
| for (i = 0; i < n_traps; ++i) |
| { |
| const pixman_trapezoid_t *trap = &(traps[i]); |
| |
| if (!pixman_trapezoid_valid (trap)) |
| continue; |
| |
| pixman_rasterize_trapezoid (dst, trap, x_dst, y_dst); |
| } |
| } |
| else |
| { |
| pixman_image_t *tmp; |
| pixman_box32_t box; |
| int i; |
| |
| if (!get_trap_extents (op, dst, traps, n_traps, &box)) |
| return; |
| |
| if (!(tmp = pixman_image_create_bits ( |
| mask_format, box.x2 - box.x1, box.y2 - box.y1, NULL, -1))) |
| return; |
| |
| for (i = 0; i < n_traps; ++i) |
| { |
| const pixman_trapezoid_t *trap = &(traps[i]); |
| |
| if (!pixman_trapezoid_valid (trap)) |
| continue; |
| |
| pixman_rasterize_trapezoid (tmp, trap, - box.x1, - box.y1); |
| } |
| |
| pixman_image_composite (op, src, tmp, dst, |
| x_src + box.x1, y_src + box.y1, |
| 0, 0, |
| x_dst + box.x1, y_dst + box.y1, |
| box.x2 - box.x1, box.y2 - box.y1); |
| |
| pixman_image_unref (tmp); |
| } |
| } |
| |
| static int |
| greater_y (const pixman_point_fixed_t *a, const pixman_point_fixed_t *b) |
| { |
| if (a->y == b->y) |
| return a->x > b->x; |
| return a->y > b->y; |
| } |
| |
| /* |
| * Note that the definition of this function is a bit odd because |
| * of the X coordinate space (y increasing downwards). |
| */ |
| static int |
| clockwise (const pixman_point_fixed_t *ref, |
| const pixman_point_fixed_t *a, |
| const pixman_point_fixed_t *b) |
| { |
| pixman_point_fixed_t ad, bd; |
| |
| ad.x = a->x - ref->x; |
| ad.y = a->y - ref->y; |
| bd.x = b->x - ref->x; |
| bd.y = b->y - ref->y; |
| |
| return ((pixman_fixed_32_32_t) bd.y * ad.x - |
| (pixman_fixed_32_32_t) ad.y * bd.x) < 0; |
| } |
| |
| static void |
| triangle_to_trapezoids (const pixman_triangle_t *tri, pixman_trapezoid_t *traps) |
| { |
| const pixman_point_fixed_t *top, *left, *right, *tmp; |
| |
| top = &tri->p1; |
| left = &tri->p2; |
| right = &tri->p3; |
| |
| if (greater_y (top, left)) |
| { |
| tmp = left; |
| left = top; |
| top = tmp; |
| } |
| |
| if (greater_y (top, right)) |
| { |
| tmp = right; |
| right = top; |
| top = tmp; |
| } |
| |
| if (clockwise (top, right, left)) |
| { |
| tmp = right; |
| right = left; |
| left = tmp; |
| } |
| |
| /* |
| * Two cases: |
| * |
| * + + |
| * / \ / \ |
| * / \ / \ |
| * / + + \ |
| * / -- -- \ |
| * / -- -- \ |
| * / --- --- \ |
| * +-- --+ |
| */ |
| |
| traps->top = top->y; |
| traps->left.p1 = *top; |
| traps->left.p2 = *left; |
| traps->right.p1 = *top; |
| traps->right.p2 = *right; |
| |
| if (right->y < left->y) |
| traps->bottom = right->y; |
| else |
| traps->bottom = left->y; |
| |
| traps++; |
| |
| *traps = *(traps - 1); |
| |
| if (right->y < left->y) |
| { |
| traps->top = right->y; |
| traps->bottom = left->y; |
| traps->right.p1 = *right; |
| traps->right.p2 = *left; |
| } |
| else |
| { |
| traps->top = left->y; |
| traps->bottom = right->y; |
| traps->left.p1 = *left; |
| traps->left.p2 = *right; |
| } |
| } |
| |
| static pixman_trapezoid_t * |
| convert_triangles (int n_tris, const pixman_triangle_t *tris) |
| { |
| pixman_trapezoid_t *traps; |
| int i; |
| |
| if (n_tris <= 0) |
| return NULL; |
| |
| traps = pixman_malloc_ab (n_tris, 2 * sizeof (pixman_trapezoid_t)); |
| if (!traps) |
| return NULL; |
| |
| for (i = 0; i < n_tris; ++i) |
| triangle_to_trapezoids (&(tris[i]), traps + 2 * i); |
| |
| return traps; |
| } |
| |
| PIXMAN_EXPORT void |
| pixman_composite_triangles (pixman_op_t op, |
| pixman_image_t * src, |
| pixman_image_t * dst, |
| pixman_format_code_t mask_format, |
| int x_src, |
| int y_src, |
| int x_dst, |
| int y_dst, |
| int n_tris, |
| const pixman_triangle_t * tris) |
| { |
| pixman_trapezoid_t *traps; |
| |
| if ((traps = convert_triangles (n_tris, tris))) |
| { |
| pixman_composite_trapezoids (op, src, dst, mask_format, |
| x_src, y_src, x_dst, y_dst, |
| n_tris * 2, traps); |
| |
| free (traps); |
| } |
| } |
| |
| PIXMAN_EXPORT void |
| pixman_add_triangles (pixman_image_t *image, |
| int32_t x_off, |
| int32_t y_off, |
| int n_tris, |
| const pixman_triangle_t *tris) |
| { |
| pixman_trapezoid_t *traps; |
| |
| if ((traps = convert_triangles (n_tris, tris))) |
| { |
| pixman_add_trapezoids (image, x_off, y_off, |
| n_tris * 2, traps); |
| |
| free (traps); |
| } |
| } |