1 /* 2 * Copyright 2002 Keith Packard, member of The XFree86 Project, Inc. 3 * Copyright 2004 Keith Packard 4 * 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. 14 * 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. 22 */ 23 24 #ifdef HAVE_CONFIG_H 25 #include <config.h> 26 #endif 27 28 #include <stdio.h> 29 #include <stdlib.h> 30 #include "pixman-private.h" 31 32 /* 33 * Compute the smallest value greater than or equal to y which is on a 34 * grid row. 35 */ 36 37 PIXMAN_EXPORT pixman_fixed_t 38 pixman_sample_ceil_y (pixman_fixed_t y, int n) 39 { 40 pixman_fixed_t f = pixman_fixed_frac (y); 41 pixman_fixed_t i = pixman_fixed_floor (y); 42 43 f = DIV (f - Y_FRAC_FIRST (n) + (STEP_Y_SMALL (n) - pixman_fixed_e), STEP_Y_SMALL (n)) * STEP_Y_SMALL (n) + 44 Y_FRAC_FIRST (n); 45 46 if (f > Y_FRAC_LAST (n)) 47 { 48 if (pixman_fixed_to_int (i) == 0x7fff) 49 { 50 f = 0xffff; /* saturate */ 51 } 52 else 53 { 54 f = Y_FRAC_FIRST (n); 55 i += pixman_fixed_1; 56 } 57 } 58 return (i | f); 59 } 60 61 /* 62 * Compute the largest value strictly less than y which is on a 63 * grid row. 64 */ 65 PIXMAN_EXPORT pixman_fixed_t 66 pixman_sample_floor_y (pixman_fixed_t y, 67 int n) 68 { 69 pixman_fixed_t f = pixman_fixed_frac (y); 70 pixman_fixed_t i = pixman_fixed_floor (y); 71 72 f = DIV (f - pixman_fixed_e - Y_FRAC_FIRST (n), STEP_Y_SMALL (n)) * STEP_Y_SMALL (n) + 73 Y_FRAC_FIRST (n); 74 75 if (f < Y_FRAC_FIRST (n)) 76 { 77 if (pixman_fixed_to_int (i) == 0x8000) 78 { 79 f = 0; /* saturate */ 80 } 81 else 82 { 83 f = Y_FRAC_LAST (n); 84 i -= pixman_fixed_1; 85 } 86 } 87 return (i | f); 88 } 89 90 /* 91 * Step an edge by any amount (including negative values) 92 */ 93 PIXMAN_EXPORT void 94 pixman_edge_step (pixman_edge_t *e, 95 int n) 96 { 97 pixman_fixed_48_16_t ne; 98 99 e->x += n * e->stepx; 100 101 ne = e->e + n * (pixman_fixed_48_16_t) e->dx; 102 103 if (n >= 0) 104 { 105 if (ne > 0) 106 { 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; 110 } 111 } 112 else 113 { 114 if (ne <= -e->dy) 115 { 116 int nx = (-ne) / e->dy; 117 e->e = ne + nx * (pixman_fixed_48_16_t) e->dy; 118 e->x -= nx * e->signdx; 119 } 120 } 121 } 122 123 /* 124 * A private routine to initialize the multi-step 125 * elements of an edge structure 126 */ 127 static void 128 _pixman_edge_multi_init (pixman_edge_t * e, 129 int n, 130 pixman_fixed_t *stepx_p, 131 pixman_fixed_t *dx_p) 132 { 133 pixman_fixed_t stepx; 134 pixman_fixed_48_16_t ne; 135 136 ne = n * (pixman_fixed_48_16_t) e->dx; 137 stepx = n * e->stepx; 138 139 if (ne > 0) 140 { 141 int nx = ne / e->dy; 142 ne -= nx * (pixman_fixed_48_16_t)e->dy; 143 stepx += nx * e->signdx; 144 } 145 146 *dx_p = ne; 147 *stepx_p = stepx; 148 } 149 150 /* 151 * Initialize one edge structure given the line endpoints and a 152 * starting y value 153 */ 154 PIXMAN_EXPORT void 155 pixman_edge_init (pixman_edge_t *e, 156 int n, 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) 162 { 163 pixman_fixed_t dx, dy; 164 165 e->x = x_top; 166 e->e = 0; 167 dx = x_bot - x_top; 168 dy = y_bot - y_top; 169 e->dy = dy; 170 e->dx = 0; 171 172 if (dy) 173 { 174 if (dx >= 0) 175 { 176 e->signdx = 1; 177 e->stepx = dx / dy; 178 e->dx = dx % dy; 179 e->e = -dy; 180 } 181 else 182 { 183 e->signdx = -1; 184 e->stepx = -(-dx / dy); 185 e->dx = -dx % dy; 186 e->e = 0; 187 } 188 189 _pixman_edge_multi_init (e, STEP_Y_SMALL (n), 190 &e->stepx_small, &e->dx_small); 191 192 _pixman_edge_multi_init (e, STEP_Y_BIG (n), 193 &e->stepx_big, &e->dx_big); 194 } 195 pixman_edge_step (e, y_start - y_top); 196 } 197 198 /* 199 * Initialize one edge structure given a line, starting y value 200 * and a pixel offset for the line 201 */ 202 PIXMAN_EXPORT void 203 pixman_line_fixed_edge_init (pixman_edge_t * e, 204 int n, 205 pixman_fixed_t y, 206 const pixman_line_fixed_t *line, 207 int x_off, 208 int y_off) 209 { 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; 213 214 if (line->p1.y <= line->p2.y) 215 { 216 top = &line->p1; 217 bot = &line->p2; 218 } 219 else 220 { 221 top = &line->p2; 222 bot = &line->p1; 223 } 224 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); 230 } 231 232 PIXMAN_EXPORT void 233 pixman_add_traps (pixman_image_t * image, 234 int16_t x_off, 235 int16_t y_off, 236 int ntrap, 237 const pixman_trap_t *traps) 238 { 239 int bpp; 240 int height; 241 242 pixman_fixed_t x_off_fixed; 243 pixman_fixed_t y_off_fixed; 244 pixman_edge_t l, r; 245 pixman_fixed_t t, b; 246 247 _pixman_image_validate (image); 248 249 height = image->bits.height; 250 bpp = PIXMAN_FORMAT_BPP (image->bits.format); 251 252 x_off_fixed = pixman_int_to_fixed (x_off); 253 y_off_fixed = pixman_int_to_fixed (y_off); 254 255 while (ntrap--) 256 { 257 t = traps->top.y + y_off_fixed; 258 if (t < 0) 259 t = 0; 260 t = pixman_sample_ceil_y (t, bpp); 261 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); 266 267 if (b >= t) 268 { 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); 275 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); 281 282 pixman_rasterize_edges (image, &l, &r, t, b); 283 } 284 285 traps++; 286 } 287 } 288 289 #if 0 290 static void 291 dump_image (pixman_image_t *image, 292 const char * title) 293 { 294 int i, j; 295 296 if (!image->type == BITS) 297 printf ("%s is not a regular image\n", title); 298 299 if (!image->bits.format == PIXMAN_a8) 300 printf ("%s is not an alpha mask\n", title); 301 302 printf ("\n\n\n%s: \n", title); 303 304 for (i = 0; i < image->bits.height; ++i) 305 { 306 uint8_t *line = 307 (uint8_t *)&(image->bits.bits[i * image->bits.rowstride]); 308 309 for (j = 0; j < image->bits.width; ++j) 310 printf ("%c", line[j] ? '#' : ' '); 311 312 printf ("\n"); 313 } 314 } 315 #endif 316 317 PIXMAN_EXPORT void 318 pixman_add_trapezoids (pixman_image_t * image, 319 int16_t x_off, 320 int y_off, 321 int ntraps, 322 const pixman_trapezoid_t *traps) 323 { 324 int i; 325 326 #if 0 327 dump_image (image, "before"); 328 #endif 329 330 for (i = 0; i < ntraps; ++i) 331 { 332 const pixman_trapezoid_t *trap = &(traps[i]); 333 334 if (!pixman_trapezoid_valid (trap)) 335 continue; 336 337 pixman_rasterize_trapezoid (image, trap, x_off, y_off); 338 } 339 340 #if 0 341 dump_image (image, "after"); 342 #endif 343 } 344 345 PIXMAN_EXPORT void 346 pixman_rasterize_trapezoid (pixman_image_t * image, 347 const pixman_trapezoid_t *trap, 348 int x_off, 349 int y_off) 350 { 351 int bpp; 352 int height; 353 354 pixman_fixed_t y_off_fixed; 355 pixman_edge_t l, r; 356 pixman_fixed_t t, b; 357 358 return_if_fail (image->type == BITS); 359 360 _pixman_image_validate (image); 361 362 if (!pixman_trapezoid_valid (trap)) 363 return; 364 365 height = image->bits.height; 366 bpp = PIXMAN_FORMAT_BPP (image->bits.format); 367 368 y_off_fixed = pixman_int_to_fixed (y_off); 369 370 t = trap->top + y_off_fixed; 371 if (t < 0) 372 t = 0; 373 t = pixman_sample_ceil_y (t, bpp); 374 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); 379 380 if (b >= t) 381 { 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); 385 386 pixman_rasterize_edges (image, &l, &r, t, b); 387 } 388 } 389 390 static const pixman_bool_t zero_src_has_no_effect[PIXMAN_N_OPERATORS] = 391 { 392 FALSE, /* Clear 0 0 */ 393 FALSE, /* Src 1 0 */ 394 TRUE, /* Dst 0 1 */ 395 TRUE, /* Over 1 1-Aa */ 396 TRUE, /* OverReverse 1-Ab 1 */ 397 FALSE, /* In Ab 0 */ 398 FALSE, /* InReverse 0 Aa */ 399 FALSE, /* Out 1-Ab 0 */ 400 TRUE, /* OutReverse 0 1-Aa */ 401 TRUE, /* Atop Ab 1-Aa */ 402 FALSE, /* AtopReverse 1-Ab Aa */ 403 TRUE, /* Xor 1-Ab 1-Aa */ 404 TRUE, /* Add 1 1 */ 405 }; 406 407 static pixman_bool_t 408 get_trap_extents (pixman_op_t op, pixman_image_t *dest, 409 const pixman_trapezoid_t *traps, int n_traps, 410 pixman_box32_t *box) 411 { 412 int i; 413 414 /* When the operator is such that a zero source has an 415 * effect on the underlying image, we have to 416 * composite across the entire destination 417 */ 418 if (!zero_src_has_no_effect [op]) 419 { 420 box->x1 = 0; 421 box->y1 = 0; 422 box->x2 = dest->bits.width; 423 box->y2 = dest->bits.height; 424 return TRUE; 425 } 426 427 box->x1 = INT32_MAX; 428 box->y1 = INT32_MAX; 429 box->x2 = INT32_MIN; 430 box->y2 = INT32_MIN; 431 432 for (i = 0; i < n_traps; ++i) 433 { 434 const pixman_trapezoid_t *trap = &(traps[i]); 435 int y1, y2; 436 437 if (!pixman_trapezoid_valid (trap)) 438 continue; 439 440 y1 = pixman_fixed_to_int (trap->top); 441 if (y1 < box->y1) 442 box->y1 = y1; 443 444 y2 = pixman_fixed_to_int (pixman_fixed_ceil (trap->bottom)); 445 if (y2 > box->y2) 446 box->y2 = y2; 447 448 #define EXTEND_MIN(x) \ 449 if (pixman_fixed_to_int ((x)) < box->x1) \ 450 box->x1 = pixman_fixed_to_int ((x)); 451 #define EXTEND_MAX(x) \ 452 if (pixman_fixed_to_int (pixman_fixed_ceil ((x))) > box->x2) \ 453 box->x2 = pixman_fixed_to_int (pixman_fixed_ceil ((x))); 454 455 #define EXTEND(x) \ 456 EXTEND_MIN(x); \ 457 EXTEND_MAX(x); 458 459 EXTEND(trap->left.p1.x); 460 EXTEND(trap->left.p2.x); 461 EXTEND(trap->right.p1.x); 462 EXTEND(trap->right.p2.x); 463 } 464 465 if (box->x1 >= box->x2 || box->y1 >= box->y2) 466 return FALSE; 467 468 return TRUE; 469 } 470 471 /* 472 * pixman_composite_trapezoids() 473 * 474 * All the trapezoids are conceptually rendered to an infinitely big image. 475 * The (0, 0) coordinates of this image are then aligned with the (x, y) 476 * coordinates of the source image, and then both images are aligned with 477 * the (x, y) coordinates of the destination. Then these three images are 478 * composited across the entire destination. 479 */ 480 PIXMAN_EXPORT void 481 pixman_composite_trapezoids (pixman_op_t op, 482 pixman_image_t * src, 483 pixman_image_t * dst, 484 pixman_format_code_t mask_format, 485 int x_src, 486 int y_src, 487 int x_dst, 488 int y_dst, 489 int n_traps, 490 const pixman_trapezoid_t * traps) 491 { 492 int i; 493 494 return_if_fail (PIXMAN_FORMAT_TYPE (mask_format) == PIXMAN_TYPE_A); 495 496 if (n_traps <= 0) 497 return; 498 499 _pixman_image_validate (src); 500 _pixman_image_validate (dst); 501 502 if (op == PIXMAN_OP_ADD && 503 (src->common.flags & FAST_PATH_IS_OPAQUE) && 504 (mask_format == dst->common.extended_format_code) && 505 !(dst->common.have_clip_region)) 506 { 507 for (i = 0; i < n_traps; ++i) 508 { 509 const pixman_trapezoid_t *trap = &(traps[i]); 510 511 if (!pixman_trapezoid_valid (trap)) 512 continue; 513 514 pixman_rasterize_trapezoid (dst, trap, x_dst, y_dst); 515 } 516 } 517 else 518 { 519 pixman_image_t *tmp; 520 pixman_box32_t box; 521 int i; 522 523 if (!get_trap_extents (op, dst, traps, n_traps, &box)) 524 return; 525 526 if (!(tmp = pixman_image_create_bits ( 527 mask_format, box.x2 - box.x1, box.y2 - box.y1, NULL, -1))) 528 return; 529 530 for (i = 0; i < n_traps; ++i) 531 { 532 const pixman_trapezoid_t *trap = &(traps[i]); 533 534 if (!pixman_trapezoid_valid (trap)) 535 continue; 536 537 pixman_rasterize_trapezoid (tmp, trap, - box.x1, - box.y1); 538 } 539 540 pixman_image_composite (op, src, tmp, dst, 541 x_src + box.x1, y_src + box.y1, 542 0, 0, 543 x_dst + box.x1, y_dst + box.y1, 544 box.x2 - box.x1, box.y2 - box.y1); 545 546 pixman_image_unref (tmp); 547 } 548 } 549 550 static int 551 greater_y (const pixman_point_fixed_t *a, const pixman_point_fixed_t *b) 552 { 553 if (a->y == b->y) 554 return a->x > b->x; 555 return a->y > b->y; 556 } 557 558 /* 559 * Note that the definition of this function is a bit odd because 560 * of the X coordinate space (y increasing downwards). 561 */ 562 static int 563 clockwise (const pixman_point_fixed_t *ref, 564 const pixman_point_fixed_t *a, 565 const pixman_point_fixed_t *b) 566 { 567 pixman_point_fixed_t ad, bd; 568 569 ad.x = a->x - ref->x; 570 ad.y = a->y - ref->y; 571 bd.x = b->x - ref->x; 572 bd.y = b->y - ref->y; 573 574 return ((pixman_fixed_32_32_t) bd.y * ad.x - 575 (pixman_fixed_32_32_t) ad.y * bd.x) < 0; 576 } 577 578 static void 579 triangle_to_trapezoids (const pixman_triangle_t *tri, pixman_trapezoid_t *traps) 580 { 581 const pixman_point_fixed_t *top, *left, *right, *tmp; 582 583 top = &tri->p1; 584 left = &tri->p2; 585 right = &tri->p3; 586 587 if (greater_y (top, left)) 588 { 589 tmp = left; 590 left = top; 591 top = tmp; 592 } 593 594 if (greater_y (top, right)) 595 { 596 tmp = right; 597 right = top; 598 top = tmp; 599 } 600 601 if (clockwise (top, right, left)) 602 { 603 tmp = right; 604 right = left; 605 left = tmp; 606 } 607 608 /* 609 * Two cases: 610 * 611 * + + 612 * / \ / \ 613 * / \ / \ 614 * / + + \ 615 * / -- -- \ 616 * / -- -- \ 617 * / --- --- \ 618 * +-- --+ 619 */ 620 621 traps->top = top->y; 622 traps->left.p1 = *top; 623 traps->left.p2 = *left; 624 traps->right.p1 = *top; 625 traps->right.p2 = *right; 626 627 if (right->y < left->y) 628 traps->bottom = right->y; 629 else 630 traps->bottom = left->y; 631 632 traps++; 633 634 *traps = *(traps - 1); 635 636 if (right->y < left->y) 637 { 638 traps->top = right->y; 639 traps->bottom = left->y; 640 traps->right.p1 = *right; 641 traps->right.p2 = *left; 642 } 643 else 644 { 645 traps->top = left->y; 646 traps->bottom = right->y; 647 traps->left.p1 = *left; 648 traps->left.p2 = *right; 649 } 650 } 651 652 static pixman_trapezoid_t * 653 convert_triangles (int n_tris, const pixman_triangle_t *tris) 654 { 655 pixman_trapezoid_t *traps; 656 int i; 657 658 if (n_tris <= 0) 659 return NULL; 660 661 traps = pixman_malloc_ab (n_tris, 2 * sizeof (pixman_trapezoid_t)); 662 if (!traps) 663 return NULL; 664 665 for (i = 0; i < n_tris; ++i) 666 triangle_to_trapezoids (&(tris[i]), traps + 2 * i); 667 668 return traps; 669 } 670 671 PIXMAN_EXPORT void 672 pixman_composite_triangles (pixman_op_t op, 673 pixman_image_t * src, 674 pixman_image_t * dst, 675 pixman_format_code_t mask_format, 676 int x_src, 677 int y_src, 678 int x_dst, 679 int y_dst, 680 int n_tris, 681 const pixman_triangle_t * tris) 682 { 683 pixman_trapezoid_t *traps; 684 685 if ((traps = convert_triangles (n_tris, tris))) 686 { 687 pixman_composite_trapezoids (op, src, dst, mask_format, 688 x_src, y_src, x_dst, y_dst, 689 n_tris * 2, traps); 690 691 free (traps); 692 } 693 } 694 695 PIXMAN_EXPORT void 696 pixman_add_triangles (pixman_image_t *image, 697 int32_t x_off, 698 int32_t y_off, 699 int n_tris, 700 const pixman_triangle_t *tris) 701 { 702 pixman_trapezoid_t *traps; 703 704 if ((traps = convert_triangles (n_tris, tris))) 705 { 706 pixman_add_trapezoids (image, x_off, y_off, 707 n_tris * 2, traps); 708 709 free (traps); 710 } 711 } 712
