1 //---------------------------------------------------------------------------- 2 // Anti-Grain Geometry - Version 2.2 3 // Copyright (C) 2002-2004 Maxim Shemanarev (http://www.antigrain.com) 4 // 5 // Permission to copy, use, modify, sell and distribute this software 6 // is granted provided this copyright notice appears in all copies. 7 // This software is provided "as is" without express or implied 8 // warranty, and with no claim as to its suitability for any purpose. 9 // 10 //---------------------------------------------------------------------------- 11 // Contact: mcseem@antigrain.com 12 // mcseemagg@yahoo.com 13 // http://www.antigrain.com 14 //---------------------------------------------------------------------------- 15 16 #ifndef AGG_SCANLINE_BOOLEAN_ALGEBRA_INCLUDED 17 #define AGG_SCANLINE_BOOLEAN_ALGEBRA_INCLUDED 18 19 #include <stdlib.h> 20 #include <math.h> 21 #include "agg_basics.h" 22 23 24 namespace agg 25 { 26 27 //-----------------------------------------------sbool_combine_spans_bin 28 // Functor. 29 // Combine two binary encoded spans, i.e., when we don't have any 30 // anti-aliasing information, but only X and Length. The function 31 // is compatible with any type of scanlines. 32 //---------------- 33 template<class Scanline1, 34 class Scanline2, 35 class Scanline> 36 struct sbool_combine_spans_bin 37 { 38 void operator () (const typename Scanline1::const_iterator&, 39 const typename Scanline2::const_iterator&, 40 int x, unsigned len, 41 Scanline& sl) const 42 { 43 sl.add_span(x, len, cover_full); 44 } 45 }; 46 47 48 49 //---------------------------------------------sbool_combine_spans_empty 50 // Functor. 51 // Combine two spans as empty ones. The functor does nothing 52 // and is used to XOR binary spans. 53 //---------------- 54 template<class Scanline1, 55 class Scanline2, 56 class Scanline> 57 struct sbool_combine_spans_empty 58 { 59 void operator () (const typename Scanline1::const_iterator&, 60 const typename Scanline2::const_iterator&, 61 int, unsigned, 62 Scanline&) const 63 {} 64 }; 65 66 67 68 //--------------------------------------------------sbool_add_span_empty 69 // Functor. 70 // Add nothing. Used in conbine_shapes_sub 71 //---------------- 72 template<class Scanline1, 73 class Scanline> 74 struct sbool_add_span_empty 75 { 76 void operator () (const typename Scanline1::const_iterator&, 77 int, unsigned, 78 Scanline&) const 79 {} 80 }; 81 82 83 //----------------------------------------------------sbool_add_span_bin 84 // Functor. 85 // Add a binary span 86 //---------------- 87 template<class Scanline1, 88 class Scanline> 89 struct sbool_add_span_bin 90 { 91 void operator () (const typename Scanline1::const_iterator&, 92 int x, unsigned len, 93 Scanline& sl) const 94 { 95 sl.add_span(x, len, cover_full); 96 } 97 }; 98 99 100 101 102 //-----------------------------------------------------sbool_add_span_aa 103 // Functor. 104 // Add an anti-aliased span 105 // anti-aliasing information, but only X and Length. The function 106 // is compatible with any type of scanlines. 107 //---------------- 108 template<class Scanline1, 109 class Scanline> 110 struct sbool_add_span_aa 111 { 112 void operator () (const typename Scanline1::const_iterator& span, 113 int x, unsigned len, 114 Scanline& sl) const 115 { 116 if(span->len < 0) 117 { 118 sl.add_span(x, len, *span->covers); 119 } 120 else 121 if(span->len > 0) 122 { 123 const typename Scanline1::cover_type* covers = span->covers; 124 if(span->x < x) covers += x - span->x; 125 sl.add_cells(x, len, covers); 126 } 127 } 128 }; 129 130 131 132 133 //----------------------------------------------sbool_intersect_spans_aa 134 // Functor. 135 // Intersect two spans preserving the anti-aliasing information. 136 // The result is added to the "sl" scanline. 137 //------------------ 138 template<class Scanline1, 139 class Scanline2, 140 class Scanline, 141 unsigned CoverShift = cover_shift> 142 struct sbool_intersect_spans_aa 143 { 144 enum 145 { 146 cover_shift = CoverShift, 147 cover_size = 1 << cover_shift, 148 cover_mask = cover_size - 1, 149 cover_full = cover_mask 150 }; 151 152 153 void operator () (const typename Scanline1::const_iterator& span1, 154 const typename Scanline2::const_iterator& span2, 155 int x, unsigned len, 156 Scanline& sl) const 157 { 158 unsigned cover; 159 const typename Scanline1::cover_type* covers1; 160 const typename Scanline2::cover_type* covers2; 161 162 // Calculate the operation code and choose the 163 // proper combination algorithm. 164 // 0 = Both spans are of AA type 165 // 1 = span1 is solid, span2 is AA 166 // 2 = span1 is AA, span2 is solid 167 // 3 = Both spans are of solid type 168 //----------------- 169 switch((span1->len < 0) | ((span2->len < 0) << 1)) 170 { 171 case 0: // Both are AA spans 172 covers1 = span1->covers; 173 covers2 = span2->covers; 174 if(span1->x < x) covers1 += x - span1->x; 175 if(span2->x < x) covers2 += x - span2->x; 176 do 177 { 178 cover = *covers1++ * *covers2++; 179 sl.add_cell(x++, 180 (cover == cover_full * cover_full) ? 181 cover_full : 182 (cover >> cover_shift)); 183 } 184 while(--len); 185 break; 186 187 case 1: // span1 is solid, span2 is AA 188 covers2 = span2->covers; 189 if(span2->x < x) covers2 += x - span2->x; 190 if(*(span1->covers) == cover_full) 191 { 192 sl.add_cells(x, len, covers2); 193 } 194 else 195 { 196 do 197 { 198 cover = *(span1->covers) * *covers2++; 199 sl.add_cell(x++, 200 (cover == cover_full * cover_full) ? 201 cover_full : 202 (cover >> cover_shift)); 203 } 204 while(--len); 205 } 206 break; 207 208 case 2: // span1 is AA, span2 is solid 209 covers1 = span1->covers; 210 if(span1->x < x) covers1 += x - span1->x; 211 if(*(span2->covers) == cover_full) 212 { 213 sl.add_cells(x, len, covers1); 214 } 215 else 216 { 217 do 218 { 219 cover = *covers1++ * *(span2->covers); 220 sl.add_cell(x++, 221 (cover == cover_full * cover_full) ? 222 cover_full : 223 (cover >> cover_shift)); 224 } 225 while(--len); 226 } 227 break; 228 229 case 3: // Both are solid spans 230 cover = *(span1->covers) * *(span2->covers); 231 sl.add_span(x, len, 232 (cover == cover_full * cover_full) ? 233 cover_full : 234 (cover >> cover_shift)); 235 break; 236 } 237 } 238 }; 239 240 241 242 243 244 245 //--------------------------------------------------sbool_unite_spans_aa 246 // Functor. 247 // Unite two spans preserving the anti-aliasing information. 248 // The result is added to the "sl" scanline. 249 //------------------ 250 template<class Scanline1, 251 class Scanline2, 252 class Scanline, 253 unsigned CoverShift = cover_shift> 254 struct sbool_unite_spans_aa 255 { 256 enum 257 { 258 cover_shift = CoverShift, 259 cover_size = 1 << cover_shift, 260 cover_mask = cover_size - 1, 261 cover_full = cover_mask 262 }; 263 264 265 void operator () (const typename Scanline1::const_iterator& span1, 266 const typename Scanline2::const_iterator& span2, 267 int x, unsigned len, 268 Scanline& sl) const 269 { 270 unsigned cover; 271 const typename Scanline1::cover_type* covers1; 272 const typename Scanline2::cover_type* covers2; 273 274 // Calculate the operation code and choose the 275 // proper combination algorithm. 276 // 0 = Both spans are of AA type 277 // 1 = span1 is solid, span2 is AA 278 // 2 = span1 is AA, span2 is solid 279 // 3 = Both spans are of solid type 280 //----------------- 281 switch((span1->len < 0) | ((span2->len < 0) << 1)) 282 { 283 case 0: // Both are AA spans 284 covers1 = span1->covers; 285 covers2 = span2->covers; 286 if(span1->x < x) covers1 += x - span1->x; 287 if(span2->x < x) covers2 += x - span2->x; 288 do 289 { 290 cover = cover_mask * cover_mask - 291 (cover_mask - *covers1++) * 292 (cover_mask - *covers2++); 293 sl.add_cell(x++, 294 (cover == cover_full * cover_full) ? 295 cover_full : 296 (cover >> cover_shift)); 297 } 298 while(--len); 299 break; 300 301 case 1: // span1 is solid, span2 is AA 302 covers2 = span2->covers; 303 if(span2->x < x) covers2 += x - span2->x; 304 if(*(span1->covers) == cover_full) 305 { 306 sl.add_span(x, len, cover_full); 307 } 308 else 309 { 310 do 311 { 312 cover = cover_mask * cover_mask - 313 (cover_mask - *(span1->covers)) * 314 (cover_mask - *covers2++); 315 sl.add_cell(x++, 316 (cover == cover_full * cover_full) ? 317 cover_full : 318 (cover >> cover_shift)); 319 } 320 while(--len); 321 } 322 break; 323 324 case 2: // span1 is AA, span2 is solid 325 covers1 = span1->covers; 326 if(span1->x < x) covers1 += x - span1->x; 327 if(*(span2->covers) == cover_full) 328 { 329 sl.add_span(x, len, cover_full); 330 } 331 else 332 { 333 do 334 { 335 cover = cover_mask * cover_mask - 336 (cover_mask - *covers1++) * 337 (cover_mask - *(span2->covers)); 338 sl.add_cell(x++, 339 (cover == cover_full * cover_full) ? 340 cover_full : 341 (cover >> cover_shift)); 342 } 343 while(--len); 344 } 345 break; 346 347 case 3: // Both are solid spans 348 cover = cover_mask * cover_mask - 349 (cover_mask - *(span1->covers)) * 350 (cover_mask - *(span2->covers)); 351 sl.add_span(x, len, 352 (cover == cover_full * cover_full) ? 353 cover_full : 354 (cover >> cover_shift)); 355 break; 356 } 357 } 358 }; 359 360 361 362 363 364 365 366 //---------------------------------------------sbool_xor_formula_saddle 367 template<unsigned CoverShift = cover_shift> 368 struct sbool_xor_formula_saddle 369 { 370 enum 371 { 372 cover_shift = CoverShift, 373 cover_size = 1 << cover_shift, 374 cover_mask = cover_size - 1 375 }; 376 377 static unsigned calculate(unsigned a, unsigned b) 378 { 379 unsigned k = a * b; 380 if(k == cover_mask * cover_mask) return 0; 381 382 a = (cover_mask * cover_mask - (a << cover_shift) + k) >> cover_shift; 383 b = (cover_mask * cover_mask - (b << cover_shift) + k) >> cover_shift; 384 return cover_mask - ((a * b) >> cover_shift); 385 } 386 }; 387 388 389 390 //--------------------------------------------sbool_xor_formula_linear 391 template<unsigned CoverShift = cover_shift> 392 struct sbool_xor_formula_linear 393 { 394 enum 395 { 396 cover_shift = CoverShift, 397 cover_size = 1 << cover_shift, 398 cover_mask = cover_size - 1 399 }; 400 401 static unsigned calculate(unsigned a, unsigned b) 402 { 403 unsigned cover = a + b; 404 if(cover > cover_mask) cover = cover_mask + cover_mask - cover; 405 return cover; 406 } 407 }; 408 409 410 411 //----------------------------------------------------sbool_xor_spans_aa 412 // Functor. 413 // XOR two spans preserving the anti-aliasing information. 414 // The result is added to the "sl" scanline. 415 //------------------ 416 template<class Scanline1, 417 class Scanline2, 418 class Scanline, 419 class XorFormula, 420 unsigned CoverShift = cover_shift> 421 struct sbool_xor_spans_aa 422 { 423 enum 424 { 425 cover_shift = CoverShift, 426 cover_size = 1 << cover_shift, 427 cover_mask = cover_size - 1, 428 cover_full = cover_mask 429 }; 430 431 432 void operator () (const typename Scanline1::const_iterator& span1, 433 const typename Scanline2::const_iterator& span2, 434 int x, unsigned len, 435 Scanline& sl) const 436 { 437 unsigned cover; 438 const typename Scanline1::cover_type* covers1; 439 const typename Scanline2::cover_type* covers2; 440 441 // Calculate the operation code and choose the 442 // proper combination algorithm. 443 // 0 = Both spans are of AA type 444 // 1 = span1 is solid, span2 is AA 445 // 2 = span1 is AA, span2 is solid 446 // 3 = Both spans are of solid type 447 //----------------- 448 switch((span1->len < 0) | ((span2->len < 0) << 1)) 449 { 450 case 0: // Both are AA spans 451 covers1 = span1->covers; 452 covers2 = span2->covers; 453 if(span1->x < x) covers1 += x - span1->x; 454 if(span2->x < x) covers2 += x - span2->x; 455 do 456 { 457 cover = XorFormula::calculate(*covers1++, *covers2++); 458 if(cover) sl.add_cell(x, cover); 459 ++x; 460 } 461 while(--len); 462 break; 463 464 case 1: // span1 is solid, span2 is AA 465 covers2 = span2->covers; 466 if(span2->x < x) covers2 += x - span2->x; 467 do 468 { 469 cover = XorFormula::calculate(*(span1->covers), *covers2++); 470 if(cover) sl.add_cell(x, cover); 471 ++x; 472 } 473 while(--len); 474 break; 475 476 case 2: // span1 is AA, span2 is solid 477 covers1 = span1->covers; 478 if(span1->x < x) covers1 += x - span1->x; 479 do 480 { 481 cover = XorFormula::calculate(*covers1++, *(span2->covers)); 482 if(cover) sl.add_cell(x, cover); 483 ++x; 484 } 485 while(--len); 486 break; 487 488 case 3: // Both are solid spans 489 cover = XorFormula::calculate(*(span1->covers), *(span2->covers)); 490 if(cover) sl.add_span(x, len, cover); 491 break; 492 493 } 494 } 495 }; 496 497 498 499 500 501 //-----------------------------------------------sbool_subtract_spans_aa 502 // Functor. 503 // Unite two spans preserving the anti-aliasing information. 504 // The result is added to the "sl" scanline. 505 //------------------ 506 template<class Scanline1, 507 class Scanline2, 508 class Scanline, 509 unsigned CoverShift = cover_shift> 510 struct sbool_subtract_spans_aa 511 { 512 enum 513 { 514 cover_shift = CoverShift, 515 cover_size = 1 << cover_shift, 516 cover_mask = cover_size - 1, 517 cover_full = cover_mask 518 }; 519 520 521 void operator () (const typename Scanline1::const_iterator& span1, 522 const typename Scanline2::const_iterator& span2, 523 int x, unsigned len, 524 Scanline& sl) const 525 { 526 unsigned cover; 527 const typename Scanline1::cover_type* covers1; 528 const typename Scanline2::cover_type* covers2; 529 530 // Calculate the operation code and choose the 531 // proper combination algorithm. 532 // 0 = Both spans are of AA type 533 // 1 = span1 is solid, span2 is AA 534 // 2 = span1 is AA, span2 is solid 535 // 3 = Both spans are of solid type 536 //----------------- 537 switch((span1->len < 0) | ((span2->len < 0) << 1)) 538 { 539 case 0: // Both are AA spans 540 covers1 = span1->covers; 541 covers2 = span2->covers; 542 if(span1->x < x) covers1 += x - span1->x; 543 if(span2->x < x) covers2 += x - span2->x; 544 do 545 { 546 cover = *covers1++ * (cover_mask - *covers2++); 547 if(cover) 548 { 549 sl.add_cell(x, 550 (cover == cover_full * cover_full) ? 551 cover_full : 552 (cover >> cover_shift)); 553 } 554 ++x; 555 } 556 while(--len); 557 break; 558 559 case 1: // span1 is solid, span2 is AA 560 covers2 = span2->covers; 561 if(span2->x < x) covers2 += x - span2->x; 562 do 563 { 564 cover = *(span1->covers) * (cover_mask - *covers2++); 565 if(cover) 566 { 567 sl.add_cell(x, 568 (cover == cover_full * cover_full) ? 569 cover_full : 570 (cover >> cover_shift)); 571 } 572 ++x; 573 } 574 while(--len); 575 break; 576 577 case 2: // span1 is AA, span2 is solid 578 covers1 = span1->covers; 579 if(span1->x < x) covers1 += x - span1->x; 580 if(*(span2->covers) != cover_full) 581 { 582 do 583 { 584 cover = *covers1++ * (cover_mask - *(span2->covers)); 585 if(cover) 586 { 587 sl.add_cell(x, 588 (cover == cover_full * cover_full) ? 589 cover_full : 590 (cover >> cover_shift)); 591 } 592 ++x; 593 } 594 while(--len); 595 } 596 break; 597 598 case 3: // Both are solid spans 599 cover = *(span1->covers) * (cover_mask - *(span2->covers)); 600 if(cover) 601 { 602 sl.add_span(x, len, 603 (cover == cover_full * cover_full) ? 604 cover_full : 605 (cover >> cover_shift)); 606 } 607 break; 608 } 609 } 610 }; 611 612 613 614 615 616 617 //--------------------------------------------sbool_add_spans_and_render 618 template<class Scanline1, 619 class Scanline, 620 class Renderer, 621 class AddSpanFunctor> 622 void sbool_add_spans_and_render(const Scanline1& sl1, 623 Scanline& sl, 624 Renderer& ren, 625 AddSpanFunctor add_span) 626 { 627 sl.reset_spans(); 628 typename Scanline::const_iterator span = sl1.begin(); 629 unsigned num_spans = sl1.num_spans(); 630 do 631 { 632 add_span(span, span->x, abs((int)span->len), sl); 633 ++span; 634 } 635 while(--num_spans); 636 sl.finalize(sl1.y()); 637 ren.render(sl); 638 } 639 640 641 642 643 644 645 646 //---------------------------------------------sbool_intersect_scanlines 647 // Intersect two scanlines, "sl1" and "sl2" and generate a new "sl" one. 648 // The combine_spans functor can be of type sbool_combine_spans_bin or 649 // sbool_intersect_spans_aa. First is a general functor to combine 650 // two spans without Anti-Aliasing, the second preserves the AA 651 // information, but works slower 652 // 653 template<class Scanline1, 654 class Scanline2, 655 class Scanline, 656 class CombineSpansFunctor> 657 void sbool_intersect_scanlines(const Scanline1& sl1, 658 const Scanline2& sl2, 659 Scanline& sl, 660 CombineSpansFunctor combine_spans) 661 { 662 sl.reset_spans(); 663 664 unsigned num1 = sl1.num_spans(); 665 if(num1 == 0) return; 666 667 unsigned num2 = sl2.num_spans(); 668 if(num2 == 0) return; 669 670 typename Scanline::const_iterator span1 = sl1.begin(); 671 typename Scanline::const_iterator span2 = sl2.begin(); 672 673 while(num1 && num2) 674 { 675 int xb1 = span1->x; 676 int xb2 = span2->x; 677 int xe1 = xb1 + abs((int)span1->len) - 1; 678 int xe2 = xb2 + abs((int)span2->len) - 1; 679 680 // Determine what spans we should advance in the next step 681 // The span with the least ending X should be advanced 682 // advance_both is just an optimization when we ending 683 // coordinates are the same and we can advance both 684 //-------------- 685 bool advance_span1 = xe1 < xe2; 686 bool advance_both = xe1 == xe2; 687 688 // Find the intersection of the spans 689 // and check if they intersect 690 //-------------- 691 if(xb1 < xb2) xb1 = xb2; 692 if(xe1 > xe2) xe1 = xe2; 693 if(xb1 <= xe1) 694 { 695 combine_spans(span1, span2, xb1, xe1 - xb1 + 1, sl); 696 } 697 698 // Advance the spans 699 //-------------- 700 if(advance_both) 701 { 702 --num1; 703 --num2; 704 ++span1; 705 ++span2; 706 } 707 else 708 { 709 if(advance_span1) 710 { 711 --num1; 712 ++span1; 713 } 714 else 715 { 716 --num2; 717 ++span2; 718 } 719 } 720 } 721 } 722 723 724 725 726 727 728 729 730 //------------------------------------------------sbool_intersect_shapes 731 // Intersect the scanline shapes. Here the "Scanline Generator" 732 // abstraction is used. ScanlineGen1 and ScanlineGen2 are 733 // the generators, and can be of type rasterizer_scanline_aa<>. 734 // There function requires three scanline containers that can be of 735 // different types. 736 // "sl1" and "sl2" are used to retrieve scanlines from the generators, 737 // "sl" is ised as the resulting scanline to render it. 738 // The external "sl1" and "sl2" are used only for the sake of 739 // optimization and reusing of the scanline objects. 740 // the function calls sbool_intersect_scanlines with CombineSpansFunctor 741 // as the last argument. See sbool_intersect_scanlines for details. 742 //---------- 743 template<class ScanlineGen1, 744 class ScanlineGen2, 745 class Scanline1, 746 class Scanline2, 747 class Scanline, 748 class Renderer, 749 class CombineSpansFunctor> 750 void sbool_intersect_shapes(ScanlineGen1& sg1, ScanlineGen2& sg2, 751 Scanline1& sl1, Scanline2& sl2, 752 Scanline& sl, Renderer& ren, 753 CombineSpansFunctor combine_spans) 754 { 755 // Prepare the scanline generators. 756 // If anyone of them doesn't contain 757 // any scanlines, then return. 758 //----------------- 759 if(!sg1.rewind_scanlines()) return; 760 if(!sg2.rewind_scanlines()) return; 761 762 // Get the bounding boxes 763 //---------------- 764 rect r1(sg1.min_x(), sg1.min_y(), sg1.max_x(), sg1.max_y()); 765 rect r2(sg2.min_x(), sg2.min_y(), sg2.max_x(), sg2.max_y()); 766 767 // Calculate the intersection of the bounding 768 // boxes and return if they don't intersect. 769 //----------------- 770 rect ir = intersect_rectangles(r1, r2); 771 if(!ir.is_valid()) return; 772 773 // Reset the scanlines and get two first ones 774 //----------------- 775 sl.reset(ir.x1, ir.x2); 776 sl1.reset(sg1.min_x(), sg1.max_x()); 777 sl2.reset(sg2.min_x(), sg2.max_x()); 778 if(!sg1.sweep_scanline(sl1)) return; 779 if(!sg2.sweep_scanline(sl2)) return; 780 781 ren.prepare(unsigned(ir.x2 - ir.x1 + 2)); 782 783 // The main loop 784 // Here we synchronize the scanlines with 785 // the same Y coordinate, ignoring all other ones. 786 // Only scanlines having the same Y-coordinate 787 // are to be combined. 788 //----------------- 789 for(;;) 790 { 791 while(sl1.y() < sl2.y()) 792 { 793 if(!sg1.sweep_scanline(sl1)) return; 794 } 795 while(sl2.y() < sl1.y()) 796 { 797 if(!sg2.sweep_scanline(sl2)) return; 798 } 799 800 if(sl1.y() == sl2.y()) 801 { 802 // The Y coordinates are the same. 803 // Combine the scanlines, render if they contain any spans, 804 // and advance both generators to the next scanlines 805 //---------------------- 806 sbool_intersect_scanlines(sl1, sl2, sl, combine_spans); 807 if(sl.num_spans()) 808 { 809 sl.finalize(sl1.y()); 810 ren.render(sl); 811 } 812 if(!sg1.sweep_scanline(sl1)) return; 813 if(!sg2.sweep_scanline(sl2)) return; 814 } 815 } 816 } 817 818 819 820 821 822 823 824 //-------------------------------------------------sbool_unite_scanlines 825 // Unite two scanlines, "sl1" and "sl2" and generate a new "sl" one. 826 // The combine_spans functor can be of type sbool_combine_spans_bin or 827 // sbool_intersect_spans_aa. First is a general functor to combine 828 // two spans without Anti-Aliasing, the second preserves the AA 829 // information, but works slower 830 // 831 template<class Scanline1, 832 class Scanline2, 833 class Scanline, 834 class AddSpanFunctor1, 835 class AddSpanFunctor2, 836 class CombineSpansFunctor> 837 void sbool_unite_scanlines(const Scanline1& sl1, 838 const Scanline2& sl2, 839 Scanline& sl, 840 AddSpanFunctor1 add_span1, 841 AddSpanFunctor2 add_span2, 842 CombineSpansFunctor combine_spans) 843 { 844 sl.reset_spans(); 845 846 unsigned num1 = sl1.num_spans(); 847 unsigned num2 = sl2.num_spans(); 848 849 typename Scanline::const_iterator span1; 850 typename Scanline::const_iterator span2; 851 852 enum { invalid_b = 0x7FFFFFFF, invalid_e = invalid_b - 1 }; 853 854 // Initialize the spans as invalid 855 //--------------- 856 int xb1 = invalid_b; 857 int xb2 = invalid_b; 858 int xe1 = invalid_e; 859 int xe2 = invalid_e; 860 861 // Initialize span1 if there are spans 862 //--------------- 863 if(num1) 864 { 865 span1 = sl1.begin(); 866 xb1 = span1->x; 867 xe1 = xb1 + abs((int)span1->len) - 1; 868 --num1; 869 } 870 871 // Initialize span2 if there are spans 872 //--------------- 873 if(num2) 874 { 875 span2 = sl2.begin(); 876 xb2 = span2->x; 877 xe2 = xb2 + abs((int)span2->len) - 1; 878 --num2; 879 } 880 881 882 for(;;) 883 { 884 // Retrieve a new span1 if it's invalid 885 //---------------- 886 if(num1 && xb1 > xe1) 887 { 888 --num1; 889 ++span1; 890 xb1 = span1->x; 891 xe1 = xb1 + abs((int)span1->len) - 1; 892 } 893 894 // Retrieve a new span2 if it's invalid 895 //---------------- 896 if(num2 && xb2 > xe2) 897 { 898 --num2; 899 ++span2; 900 xb2 = span2->x; 901 xe2 = xb2 + abs((int)span2->len) - 1; 902 } 903 904 if(xb1 > xe1 && xb2 > xe2) break; 905 906 // Calculate the intersection 907 //---------------- 908 int xb = xb1; 909 int xe = xe1; 910 if(xb < xb2) xb = xb2; 911 if(xe > xe2) xe = xe2; 912 int len = xe - xb + 1; // The length of the intersection 913 if(len > 0) 914 { 915 // The spans intersect, 916 // add the beginning of the span 917 //---------------- 918 if(xb1 < xb2) 919 { 920 add_span1(span1, xb1, xb2 - xb1, sl); 921 xb1 = xb2; 922 } 923 else 924 if(xb2 < xb1) 925 { 926 add_span2(span2, xb2, xb1 - xb2, sl); 927 xb2 = xb1; 928 } 929 930 // Add the combination part of the spans 931 //---------------- 932 combine_spans(span1, span2, xb, len, sl); 933 934 935 // Invalidate the fully processed span or both 936 //---------------- 937 if(xe1 < xe2) 938 { 939 // Invalidate span1 and eat 940 // the processed part of span2 941 //-------------- 942 xb1 = invalid_b; 943 xe1 = invalid_e; 944 xb2 += len; 945 } 946 else 947 if(xe2 < xe1) 948 { 949 // Invalidate span2 and eat 950 // the processed part of span1 951 //-------------- 952 xb2 = invalid_b; 953 xe2 = invalid_e; 954 xb1 += len; 955 } 956 else 957 { 958 xb1 = invalid_b; // Invalidate both 959 xb2 = invalid_b; 960 xe1 = invalid_e; 961 xe2 = invalid_e; 962 } 963 } 964 else 965 { 966 // The spans do not intersect 967 //-------------- 968 if(xb1 < xb2) 969 { 970 // Advance span1 971 //--------------- 972 if(xb1 <= xe1) 973 { 974 add_span1(span1, xb1, xe1 - xb1 + 1, sl); 975 } 976 xb1 = invalid_b; // Invalidate 977 xe1 = invalid_e; 978 } 979 else 980 { 981 // Advance span2 982 //--------------- 983 if(xb2 <= xe2) 984 { 985 add_span2(span2, xb2, xe2 - xb2 + 1, sl); 986 } 987 xb2 = invalid_b; // Invalidate 988 xe2 = invalid_e; 989 } 990 } 991 } 992 } 993 994 995 996 997 //----------------------------------------------------sbool_unite_shapes 998 // Unite the scanline shapes. Here the "Scanline Generator" 999 // abstraction is used. ScanlineGen1 and ScanlineGen2 are 1000 // the generators, and can be of type rasterizer_scanline_aa<>. 1001 // There function requires three scanline containers that can be 1002 // of different type. 1003 // "sl1" and "sl2" are used to retrieve scanlines from the generators, 1004 // "sl" is ised as the resulting scanline to render it. 1005 // The external "sl1" and "sl2" are used only for the sake of 1006 // optimization and reusing of the scanline objects. 1007 // the function calls sbool_unite_scanlines with CombineSpansFunctor 1008 // as the last argument. See sbool_unite_scanlines for details. 1009 //---------- 1010 template<class ScanlineGen1, 1011 class ScanlineGen2, 1012 class Scanline1, 1013 class Scanline2, 1014 class Scanline, 1015 class Renderer, 1016 class AddSpanFunctor1, 1017 class AddSpanFunctor2, 1018 class CombineSpansFunctor> 1019 void sbool_unite_shapes(ScanlineGen1& sg1, ScanlineGen2& sg2, 1020 Scanline1& sl1, Scanline2& sl2, 1021 Scanline& sl, Renderer& ren, 1022 AddSpanFunctor1 add_span1, 1023 AddSpanFunctor2 add_span2, 1024 CombineSpansFunctor combine_spans) 1025 { 1026 // Prepare the scanline generators. 1027 // If anyone of them doesn't contain 1028 // any scanlines, then return. 1029 //----------------- 1030 bool flag1 = sg1.rewind_scanlines(); 1031 bool flag2 = sg2.rewind_scanlines(); 1032 if(!flag1 && !flag2) return; 1033 1034 // Get the bounding boxes 1035 //---------------- 1036 rect r1(sg1.min_x(), sg1.min_y(), sg1.max_x(), sg1.max_y()); 1037 rect r2(sg2.min_x(), sg2.min_y(), sg2.max_x(), sg2.max_y()); 1038 1039 // Calculate the union of the bounding boxes 1040 //----------------- 1041 rect ur = unite_rectangles(r1, r2); 1042 if(!ur.is_valid()) return; 1043 1044 ren.prepare(unsigned(ur.x2 - ur.x2 + 2)); 1045 1046 // Reset the scanlines and get two first ones 1047 //----------------- 1048 sl.reset(ur.x1, ur.x2); 1049 if(flag1) 1050 { 1051 sl1.reset(sg1.min_x(), sg1.max_x()); 1052 flag1 = sg1.sweep_scanline(sl1); 1053 } 1054 1055 if(flag2) 1056 { 1057 sl2.reset(sg2.min_x(), sg2.max_x()); 1058 flag2 = sg2.sweep_scanline(sl2); 1059 } 1060 1061 // The main loop 1062 // Here we synchronize the scanlines with 1063 // the same Y coordinate. 1064 //----------------- 1065 while(flag1 || flag2) 1066 { 1067 if(flag1 && flag2) 1068 { 1069 if(sl1.y() == sl2.y()) 1070 { 1071 // The Y coordinates are the same. 1072 // Combine the scanlines, render if they contain any spans, 1073 // and advance both generators to the next scanlines 1074 //---------------------- 1075 sbool_unite_scanlines(sl1, sl2, sl, 1076 add_span1, add_span2, combine_spans); 1077 if(sl.num_spans()) 1078 { 1079 sl.finalize(sl1.y()); 1080 ren.render(sl); 1081 } 1082 flag1 = sg1.sweep_scanline(sl1); 1083 flag2 = sg2.sweep_scanline(sl2); 1084 } 1085 else 1086 { 1087 if(sl1.y() < sl2.y()) 1088 { 1089 sbool_add_spans_and_render(sl1, sl, ren, add_span1); 1090 flag1 = sg1.sweep_scanline(sl1); 1091 } 1092 else 1093 { 1094 sbool_add_spans_and_render(sl2, sl, ren, add_span2); 1095 flag2 = sg2.sweep_scanline(sl2); 1096 } 1097 } 1098 } 1099 else 1100 { 1101 if(flag1) 1102 { 1103 sbool_add_spans_and_render(sl1, sl, ren, add_span1); 1104 flag1 = sg1.sweep_scanline(sl1); 1105 } 1106 if(flag2) 1107 { 1108 sbool_add_spans_and_render(sl2, sl, ren, add_span2); 1109 flag2 = sg2.sweep_scanline(sl2); 1110 } 1111 } 1112 } 1113 } 1114 1115 1116 1117 1118 1119 1120 1121 1122 //-------------------------------------------------sbool_subtract_shapes 1123 // Subtract the scanline shapes, "sg1-sg2". Here the "Scanline Generator" 1124 // abstraction is used. ScanlineGen1 and ScanlineGen2 are 1125 // the generators, and can be of type rasterizer_scanline_aa<>. 1126 // There function requires three scanline containers that can be of 1127 // different types. 1128 // "sl1" and "sl2" are used to retrieve scanlines from the generators, 1129 // "sl" is ised as the resulting scanline to render it. 1130 // The external "sl1" and "sl2" are used only for the sake of 1131 // optimization and reusing of the scanline objects. 1132 // the function calls sbool_intersect_scanlines with CombineSpansFunctor 1133 // as the last argument. See combine_scanlines_sub for details. 1134 //---------- 1135 template<class ScanlineGen1, 1136 class ScanlineGen2, 1137 class Scanline1, 1138 class Scanline2, 1139 class Scanline, 1140 class Renderer, 1141 class AddSpanFunctor1, 1142 class CombineSpansFunctor> 1143 void sbool_subtract_shapes(ScanlineGen1& sg1, ScanlineGen2& sg2, 1144 Scanline1& sl1, Scanline2& sl2, 1145 Scanline& sl, Renderer& ren, 1146 AddSpanFunctor1 add_span1, 1147 CombineSpansFunctor combine_spans) 1148 { 1149 // Prepare the scanline generators. 1150 // Here "sg1" is master, "sg2" is slave. 1151 //----------------- 1152 if(!sg1.rewind_scanlines()) return; 1153 bool flag2 = sg2.rewind_scanlines(); 1154 1155 // Get the bounding box 1156 //---------------- 1157 rect r1(sg1.min_x(), sg1.min_y(), sg1.max_x(), sg1.max_y()); 1158 1159 // Reset the scanlines and get two first ones 1160 //----------------- 1161 sl.reset(sg1.min_x(), sg1.max_x()); 1162 sl1.reset(sg1.min_x(), sg1.max_x()); 1163 sl2.reset(sg2.min_x(), sg2.max_x()); 1164 if(!sg1.sweep_scanline(sl1)) return; 1165 1166 if(flag2) flag2 = sg2.sweep_scanline(sl2); 1167 1168 ren.prepare(unsigned(sg1.max_x() - sg1.min_x() + 2)); 1169 1170 // A fake span2 processor 1171 sbool_add_span_empty<Scanline1, Scanline> add_span2; 1172 1173 // The main loop 1174 // Here we synchronize the scanlines with 1175 // the same Y coordinate, ignoring all other ones. 1176 // Only scanlines having the same Y-coordinate 1177 // are to be combined. 1178 //----------------- 1179 bool flag1 = true; 1180 do 1181 { 1182 // Synchronize "slave" with "master" 1183 //----------------- 1184 while(flag2 && sl2.y() < sl1.y()) 1185 { 1186 flag2 = sg2.sweep_scanline(sl2); 1187 } 1188 1189 1190 if(flag2 && sl2.y() == sl1.y()) 1191 { 1192 // The Y coordinates are the same. 1193 // Combine the scanlines and render if they contain any spans. 1194 //---------------------- 1195 sbool_unite_scanlines(sl1, sl2, sl, add_span1, add_span2, combine_spans); 1196 if(sl.num_spans()) 1197 { 1198 sl.finalize(sl1.y()); 1199 ren.render(sl); 1200 } 1201 } 1202 else 1203 { 1204 sbool_add_spans_and_render(sl1, sl, ren, add_span1); 1205 } 1206 1207 // Advance the "master" 1208 flag1 = sg1.sweep_scanline(sl1); 1209 } 1210 while(flag1); 1211 } 1212 1213 1214 1215 1216 1217 1218 1219 //---------------------------------------------sbool_intersect_shapes_aa 1220 // Intersect two anti-aliased scanline shapes. 1221 // Here the "Scanline Generator" abstraction is used. 1222 // ScanlineGen1 and ScanlineGen2 are the generators, and can be of 1223 // type rasterizer_scanline_aa<>. There function requires three 1224 // scanline containers that can be of different types. 1225 // "sl1" and "sl2" are used to retrieve scanlines from the generators, 1226 // "sl" is ised as the resulting scanline to render it. 1227 // The external "sl1" and "sl2" are used only for the sake of 1228 // optimization and reusing of the scanline objects. 1229 //---------- 1230 template<class ScanlineGen1, 1231 class ScanlineGen2, 1232 class Scanline1, 1233 class Scanline2, 1234 class Scanline, 1235 class Renderer> 1236 void sbool_intersect_shapes_aa(ScanlineGen1& sg1, ScanlineGen2& sg2, 1237 Scanline1& sl1, Scanline2& sl2, 1238 Scanline& sl, Renderer& ren) 1239 { 1240 sbool_intersect_spans_aa<Scanline1, Scanline2, Scanline> combine_functor; 1241 sbool_intersect_shapes(sg1, sg2, sl1, sl2, sl, ren, combine_functor); 1242 } 1243 1244 1245 1246 1247 1248 //--------------------------------------------sbool_intersect_shapes_bin 1249 // Intersect two binary scanline shapes (without anti-aliasing). 1250 // See intersect_shapes_aa for more comments 1251 //---------- 1252 template<class ScanlineGen1, 1253 class ScanlineGen2, 1254 class Scanline1, 1255 class Scanline2, 1256 class Scanline, 1257 class Renderer> 1258 void sbool_intersect_shapes_bin(ScanlineGen1& sg1, ScanlineGen2& sg2, 1259 Scanline1& sl1, Scanline2& sl2, 1260 Scanline& sl, Renderer& ren) 1261 { 1262 sbool_combine_spans_bin<Scanline1, Scanline2, Scanline> combine_functor; 1263 sbool_intersect_shapes(sg1, sg2, sl1, sl2, sl, ren, combine_functor); 1264 } 1265 1266 1267 1268 1269 1270 //-------------------------------------------------sbool_unite_shapes_aa 1271 // Unite two anti-aliased scanline shapes 1272 // See intersect_shapes_aa for more comments 1273 //---------- 1274 template<class ScanlineGen1, 1275 class ScanlineGen2, 1276 class Scanline1, 1277 class Scanline2, 1278 class Scanline, 1279 class Renderer> 1280 void sbool_unite_shapes_aa(ScanlineGen1& sg1, ScanlineGen2& sg2, 1281 Scanline1& sl1, Scanline2& sl2, 1282 Scanline& sl, Renderer& ren) 1283 { 1284 sbool_add_span_aa<Scanline1, Scanline> add_functor1; 1285 sbool_add_span_aa<Scanline2, Scanline> add_functor2; 1286 sbool_unite_spans_aa<Scanline1, Scanline2, Scanline> combine_functor; 1287 sbool_unite_shapes(sg1, sg2, sl1, sl2, sl, ren, 1288 add_functor1, add_functor2, combine_functor); 1289 } 1290 1291 1292 1293 1294 1295 //------------------------------------------------sbool_unite_shapes_bin 1296 // Unite two binary scanline shapes (without anti-aliasing). 1297 // See intersect_shapes_aa for more comments 1298 //---------- 1299 template<class ScanlineGen1, 1300 class ScanlineGen2, 1301 class Scanline1, 1302 class Scanline2, 1303 class Scanline, 1304 class Renderer> 1305 void sbool_unite_shapes_bin(ScanlineGen1& sg1, ScanlineGen2& sg2, 1306 Scanline1& sl1, Scanline2& sl2, 1307 Scanline& sl, Renderer& ren) 1308 { 1309 sbool_add_span_bin<Scanline1, Scanline> add_functor1; 1310 sbool_add_span_bin<Scanline2, Scanline> add_functor2; 1311 sbool_combine_spans_bin<Scanline1, Scanline2, Scanline> combine_functor; 1312 sbool_unite_shapes(sg1, sg2, sl1, sl2, sl, ren, 1313 add_functor1, add_functor2, combine_functor); 1314 } 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 //---------------------------------------------------sbool_xor_shapes_aa 1325 // Apply eXclusive OR to two anti-aliased scanline shapes. There's 1326 // a modified "Linear" XOR used instead of classical "Saddle" one. 1327 // The reason is to have the result absolutely conststent with what 1328 // the scanline rasterizer produces. 1329 // See intersect_shapes_aa for more comments 1330 //---------- 1331 template<class ScanlineGen1, 1332 class ScanlineGen2, 1333 class Scanline1, 1334 class Scanline2, 1335 class Scanline, 1336 class Renderer> 1337 void sbool_xor_shapes_aa(ScanlineGen1& sg1, ScanlineGen2& sg2, 1338 Scanline1& sl1, Scanline2& sl2, 1339 Scanline& sl, Renderer& ren) 1340 { 1341 sbool_add_span_aa<Scanline1, Scanline> add_functor1; 1342 sbool_add_span_aa<Scanline2, Scanline> add_functor2; 1343 sbool_xor_spans_aa<Scanline1, Scanline2, Scanline, 1344 sbool_xor_formula_linear<> > combine_functor; 1345 sbool_unite_shapes(sg1, sg2, sl1, sl2, sl, ren, 1346 add_functor1, add_functor2, combine_functor); 1347 } 1348 1349 1350 1351 //------------------------------------------sbool_xor_shapes_saddle_aa 1352 // Apply eXclusive OR to two anti-aliased scanline shapes. 1353 // There's the classical "Saddle" used to calculate the 1354 // Anti-Aliasing values, that is: 1355 // a XOR b : 1-((1-a+a*b)*(1-b+a*b)) 1356 // See intersect_shapes_aa for more comments 1357 //---------- 1358 template<class ScanlineGen1, 1359 class ScanlineGen2, 1360 class Scanline1, 1361 class Scanline2, 1362 class Scanline, 1363 class Renderer> 1364 void sbool_xor_shapes_saddle_aa(ScanlineGen1& sg1, ScanlineGen2& sg2, 1365 Scanline1& sl1, Scanline2& sl2, 1366 Scanline& sl, Renderer& ren) 1367 { 1368 sbool_add_span_aa<Scanline1, Scanline> add_functor1; 1369 sbool_add_span_aa<Scanline2, Scanline> add_functor2; 1370 sbool_xor_spans_aa<Scanline1, 1371 Scanline2, 1372 Scanline, 1373 sbool_xor_formula_saddle<> > combine_functor; 1374 sbool_unite_shapes(sg1, sg2, sl1, sl2, sl, ren, 1375 add_functor1, add_functor2, combine_functor); 1376 } 1377 1378 1379 1380 //--------------------------------------------------sbool_xor_shapes_bin 1381 // Apply eXclusive OR to two binary scanline shapes (without anti-aliasing). 1382 // See intersect_shapes_aa for more comments 1383 //---------- 1384 template<class ScanlineGen1, 1385 class ScanlineGen2, 1386 class Scanline1, 1387 class Scanline2, 1388 class Scanline, 1389 class Renderer> 1390 void sbool_xor_shapes_bin(ScanlineGen1& sg1, ScanlineGen2& sg2, 1391 Scanline1& sl1, Scanline2& sl2, 1392 Scanline& sl, Renderer& ren) 1393 { 1394 sbool_add_span_bin<Scanline1, Scanline> add_functor1; 1395 sbool_add_span_bin<Scanline2, Scanline> add_functor2; 1396 sbool_combine_spans_empty<Scanline1, Scanline2, Scanline> combine_functor; 1397 sbool_unite_shapes(sg1, sg2, sl1, sl2, sl, ren, 1398 add_functor1, add_functor2, combine_functor); 1399 } 1400 1401 1402 1403 1404 1405 1406 //----------------------------------------------sbool_subtract_shapes_aa 1407 // Subtract shapes "sg1-sg2" with anti-aliasing 1408 // See intersect_shapes_aa for more comments 1409 //---------- 1410 template<class ScanlineGen1, 1411 class ScanlineGen2, 1412 class Scanline1, 1413 class Scanline2, 1414 class Scanline, 1415 class Renderer> 1416 void sbool_subtract_shapes_aa(ScanlineGen1& sg1, ScanlineGen2& sg2, 1417 Scanline1& sl1, Scanline2& sl2, 1418 Scanline& sl, Renderer& ren) 1419 { 1420 sbool_add_span_aa<Scanline1, Scanline> add_functor; 1421 sbool_subtract_spans_aa<Scanline1, Scanline2, Scanline> combine_functor; 1422 sbool_subtract_shapes(sg1, sg2, sl1, sl2, sl, ren, 1423 add_functor, combine_functor); 1424 } 1425 1426 1427 1428 1429 1430 //---------------------------------------------sbool_subtract_shapes_bin 1431 // Subtract binary shapes "sg1-sg2" without anti-aliasing 1432 // See intersect_shapes_aa for more comments 1433 //---------- 1434 template<class ScanlineGen1, 1435 class ScanlineGen2, 1436 class Scanline1, 1437 class Scanline2, 1438 class Scanline, 1439 class Renderer> 1440 void sbool_subtract_shapes_bin(ScanlineGen1& sg1, ScanlineGen2& sg2, 1441 Scanline1& sl1, Scanline2& sl2, 1442 Scanline& sl, Renderer& ren) 1443 { 1444 sbool_add_span_bin<Scanline1, Scanline> add_functor; 1445 sbool_combine_spans_empty<Scanline1, Scanline2, Scanline> combine_functor; 1446 sbool_subtract_shapes(sg1, sg2, sl1, sl2, sl, ren, 1447 add_functor, combine_functor); 1448 } 1449 1450 1451 1452 1453 1454 1455 //------------------------------------------------------------sbool_op_e 1456 enum sbool_op_e 1457 { 1458 sbool_or, //----sbool_or 1459 sbool_and, //----sbool_and 1460 sbool_xor, //----sbool_xor 1461 sbool_xor_saddle, //----sbool_xor_saddle 1462 sbool_a_minus_b, //----sbool_a_minus_b 1463 sbool_b_minus_a //----sbool_b_minus_a 1464 }; 1465 1466 1467 1468 1469 1470 1471 //----------------------------------------------sbool_combine_shapes_bin 1472 template<class ScanlineGen1, 1473 class ScanlineGen2, 1474 class Scanline1, 1475 class Scanline2, 1476 class Scanline, 1477 class Renderer> 1478 void sbool_combine_shapes_bin(sbool_op_e op, 1479 ScanlineGen1& sg1, ScanlineGen2& sg2, 1480 Scanline1& sl1, Scanline2& sl2, 1481 Scanline& sl, Renderer& ren) 1482 { 1483 switch(op) 1484 { 1485 case sbool_or : sbool_unite_shapes_bin (sg1, sg2, sl1, sl2, sl, ren); break; 1486 case sbool_and : sbool_intersect_shapes_bin(sg1, sg2, sl1, sl2, sl, ren); break; 1487 case sbool_xor : 1488 case sbool_xor_saddle: sbool_xor_shapes_bin (sg1, sg2, sl1, sl2, sl, ren); break; 1489 case sbool_a_minus_b : sbool_subtract_shapes_bin (sg1, sg2, sl1, sl2, sl, ren); break; 1490 case sbool_b_minus_a : sbool_subtract_shapes_bin (sg2, sg1, sl2, sl1, sl, ren); break; 1491 } 1492 } 1493 1494 1495 1496 1497 //-----------------------------------------------sbool_combine_shapes_aa 1498 template<class ScanlineGen1, 1499 class ScanlineGen2, 1500 class Scanline1, 1501 class Scanline2, 1502 class Scanline, 1503 class Renderer> 1504 void sbool_combine_shapes_aa(sbool_op_e op, 1505 ScanlineGen1& sg1, ScanlineGen2& sg2, 1506 Scanline1& sl1, Scanline2& sl2, 1507 Scanline& sl, Renderer& ren) 1508 { 1509 switch(op) 1510 { 1511 case sbool_or : sbool_unite_shapes_aa (sg1, sg2, sl1, sl2, sl, ren); break; 1512 case sbool_and : sbool_intersect_shapes_aa (sg1, sg2, sl1, sl2, sl, ren); break; 1513 case sbool_xor : sbool_xor_shapes_aa (sg1, sg2, sl1, sl2, sl, ren); break; 1514 case sbool_xor_saddle: sbool_xor_shapes_saddle_aa(sg1, sg2, sl1, sl2, sl, ren); break; 1515 case sbool_a_minus_b : sbool_subtract_shapes_aa (sg1, sg2, sl1, sl2, sl, ren); break; 1516 case sbool_b_minus_a : sbool_subtract_shapes_aa (sg2, sg1, sl2, sl1, sl, ren); break; 1517 } 1518 } 1519 1520 } 1521 1522 1523 #endif 1524 1525