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 // The author gratefully acknowleges the support of David Turner, 11 // Robert Wilhelm, and Werner Lemberg - the authors of the FreeType 12 // libray - in producing this work. See http://www.freetype.org for details. 13 // 14 //---------------------------------------------------------------------------- 15 // Contact: mcseem@antigrain.com 16 // mcseemagg@yahoo.com 17 // http://www.antigrain.com 18 //---------------------------------------------------------------------------- 19 // 20 // Class rasterizer_scanline_aa 21 // 22 // 23 //---------------------------------------------------------------------------- 24 #ifndef AGG_RASTERIZER_SCANLINE_AA_INCLUDED 25 #define AGG_RASTERIZER_SCANLINE_AA_INCLUDED 26 27 #include <string.h> 28 #include <math.h> 29 #include "agg_basics.h" 30 #include "agg_math.h" 31 #include "agg_gamma_functions.h" 32 #include "agg_clip_liang_barsky.h" 33 #include "agg_render_scanlines.h" 34 35 36 namespace agg 37 { 38 39 //------------------------------------------------------------------------ 40 // These constants determine the subpixel accuracy, to be more precise, 41 // the number of bits of the fractional part of the coordinates. 42 // The possible coordinate capacity in bits can be calculated by formula: 43 // sizeof(int) * 8 - poly_base_shift * 2, i.e, for 32-bit integers and 44 // 8-bits fractional part the capacity is 16 bits or [-32768...32767]. 45 enum 46 { 47 poly_base_shift = 8, //----poly_base_shift 48 poly_base_size = 1 << poly_base_shift, //----poly_base_size 49 poly_base_mask = poly_base_size - 1 //----poly_base_mask 50 }; 51 52 //--------------------------------------------------------------poly_coord 53 inline int poly_coord(double c) 54 { 55 return int(c * poly_base_size); 56 } 57 58 //-----------------------------------------------------------------cell_aa 59 // A pixel cell. There're no constructors defined and it was done 60 // intentionally in order to avoid extra overhead when allocating an 61 // array of cells. 62 struct cell_aa 63 { 64 int16 x; 65 int16 y; 66 int packed_coord; 67 int cover; 68 int area; 69 70 void set(int x, int y, int c, int a); 71 void set_coord(int x, int y); 72 void set_cover(int c, int a); 73 void add_cover(int c, int a); 74 }; 75 76 77 //--------------------------------------------------------------outline_aa 78 // An internal class that implements the main rasterization algorithm. 79 // Used in the rasterizer. Should not be used direcly. 80 class outline_aa 81 { 82 enum 83 { 84 cell_block_shift = 12, 85 cell_block_size = 1 << cell_block_shift, 86 cell_block_mask = cell_block_size - 1, 87 cell_block_pool = 256, 88 cell_block_limit = 1024 89 }; 90 91 public: 92 93 ~outline_aa(); 94 outline_aa(); 95 96 void reset(); 97 98 void move_to(int x, int y); 99 void line_to(int x, int y); 100 101 int min_x() const { return m_min_x; } 102 int min_y() const { return m_min_y; } 103 int max_x() const { return m_max_x; } 104 int max_y() const { return m_max_y; } 105 106 const cell_aa* const* cells(); 107 unsigned num_cells() { cells(); return m_num_cells; } 108 bool sorted() const { return m_sorted; } 109 110 private: 111 outline_aa(const outline_aa&); 112 const outline_aa& operator = (const outline_aa&); 113 114 void set_cur_cell(int x, int y); 115 void add_cur_cell(); 116 void sort_cells(); 117 void render_hline(int ey, int x1, int y1, int x2, int y2); 118 void render_line(int x1, int y1, int x2, int y2); 119 void allocate_block(); 120 121 static void qsort_cells(cell_aa** start, unsigned num); 122 123 private: 124 unsigned m_num_blocks; 125 unsigned m_max_blocks; 126 unsigned m_cur_block; 127 unsigned m_num_cells; 128 cell_aa** m_cells; 129 cell_aa* m_cur_cell_ptr; 130 cell_aa** m_sorted_cells; 131 unsigned m_sorted_size; 132 cell_aa m_cur_cell; 133 int m_cur_x; 134 int m_cur_y; 135 int m_min_x; 136 int m_min_y; 137 int m_max_x; 138 int m_max_y; 139 bool m_sorted; 140 }; 141 142 143 //----------------------------------------------------------filling_rule_e 144 enum filling_rule_e 145 { 146 fill_non_zero, 147 fill_even_odd 148 }; 149 150 151 //==================================================rasterizer_scanline_aa 152 // Polygon rasterizer that is used to render filled polygons with 153 // high-quality Anti-Aliasing. Internally, by default, the class uses 154 // integer coordinates in format 24.8, i.e. 24 bits for integer part 155 // and 8 bits for fractional - see poly_base_shift. This class can be 156 // used in the following way: 157 // 158 // 1. filling_rule(filling_rule_e ft) - optional. 159 // 160 // 2. gamma() - optional. 161 // 162 // 3. reset() 163 // 164 // 4. move_to(x, y) / line_to(x, y) - make the polygon. One can create 165 // more than one contour, but each contour must consist of at least 3 166 // vertices, i.e. move_to(x1, y1); line_to(x2, y2); line_to(x3, y3); 167 // is the absolute minimum of vertices that define a triangle. 168 // The algorithm does not check either the number of vertices nor 169 // coincidence of their coordinates, but in the worst case it just 170 // won't draw anything. 171 // The orger of the vertices (clockwise or counterclockwise) 172 // is important when using the non-zero filling rule (fill_non_zero). 173 // In this case the vertex order of all the contours must be the same 174 // if you want your intersecting polygons to be without "holes". 175 // You actually can use different vertices order. If the contours do not 176 // intersect each other the order is not important anyway. If they do, 177 // contours with the same vertex order will be rendered without "holes" 178 // while the intersecting contours with different orders will have "holes". 179 // 180 // filling_rule() and gamma() can be called anytime before "sweeping". 181 //------------------------------------------------------------------------ 182 template<unsigned XScale=1, unsigned AA_Shift=8> class rasterizer_scanline_aa 183 { 184 enum status 185 { 186 status_initial, 187 status_line_to, 188 status_closed 189 }; 190 191 struct iterator 192 { 193 const cell_aa* const* cells; 194 int cover; 195 int last_y; 196 }; 197 198 public: 199 enum 200 { 201 aa_shift = AA_Shift, 202 aa_num = 1 << aa_shift, 203 aa_mask = aa_num - 1, 204 aa_2num = aa_num * 2, 205 aa_2mask = aa_2num - 1 206 }; 207 208 //-------------------------------------------------------------------- 209 rasterizer_scanline_aa() : 210 m_filling_rule(fill_non_zero), 211 m_clipped_start_x(0), 212 m_clipped_start_y(0), 213 m_start_x(0), 214 m_start_y(0), 215 m_prev_x(0), 216 m_prev_y(0), 217 m_prev_flags(0), 218 m_status(status_initial), 219 m_clipping(false) 220 { 221 int i; 222 for(i = 0; i < aa_num; i++) m_gamma[i] = i; 223 } 224 225 //-------------------------------------------------------------------- 226 template<class GammaF> 227 rasterizer_scanline_aa(const GammaF& gamma_function) : 228 m_filling_rule(fill_non_zero), 229 m_clipped_start_x(0), 230 m_clipped_start_y(0), 231 m_start_x(0), 232 m_start_y(0), 233 m_prev_x(0), 234 m_prev_y(0), 235 m_prev_flags(0), 236 m_status(status_initial), 237 m_clipping(false) 238 { 239 gamma(gamma_function); 240 } 241 242 //-------------------------------------------------------------------- 243 void reset(); 244 void filling_rule(filling_rule_e filling_rule); 245 void clip_box(double x1, double y1, double x2, double y2); 246 void reset_clipping(); 247 248 //-------------------------------------------------------------------- 249 template<class GammaF> void gamma(const GammaF& gamma_function) 250 { 251 int i; 252 for(i = 0; i < aa_num; i++) 253 { 254 m_gamma[i] = int(floor(gamma_function(double(i) / aa_mask) * aa_mask + 0.5)); 255 } 256 } 257 258 //-------------------------------------------------------------------- 259 unsigned apply_gamma(unsigned cover) const 260 { 261 return m_gamma[cover]; 262 } 263 264 //-------------------------------------------------------------------- 265 void add_vertex(double x, double y, unsigned cmd); 266 void move_to(int x, int y); 267 void line_to(int x, int y); 268 void close_polygon(); 269 void move_to_d(double x, double y); 270 void line_to_d(double x, double y); 271 272 //-------------------------------------------------------------------- 273 int min_x() const { return m_outline.min_x(); } 274 int min_y() const { return m_outline.min_y(); } 275 int max_x() const { return m_outline.max_x(); } 276 int max_y() const { return m_outline.max_y(); } 277 278 //-------------------------------------------------------------------- 279 unsigned calculate_alpha(int area) const 280 { 281 int cover = area >> (poly_base_shift*2 + 1 - aa_shift); 282 283 if(cover < 0) cover = -cover; 284 if(m_filling_rule == fill_even_odd) 285 { 286 cover &= aa_2mask; 287 if(cover > aa_num) 288 { 289 cover = aa_2num - cover; 290 } 291 } 292 if(cover > aa_mask) cover = aa_mask; 293 return m_gamma[cover]; 294 } 295 296 //-------------------------------------------------------------------- 297 void sort() 298 { 299 m_outline.cells(); 300 } 301 302 303 //-------------------------------------------------------------------- 304 bool rewind_scanlines() 305 { 306 close_polygon(); 307 m_iterator.cells = m_outline.cells(); 308 if(m_outline.num_cells() == 0) 309 { 310 return false; 311 } 312 m_iterator.cover = 0; 313 m_iterator.last_y = (*m_iterator.cells)->y; 314 return true; 315 } 316 317 318 //-------------------------------------------------------------------- 319 template<class Scanline> bool sweep_scanline(Scanline& sl) 320 { 321 sl.reset_spans(); 322 for(;;) 323 { 324 const cell_aa* cur_cell = *m_iterator.cells; 325 if(cur_cell == 0) return false; 326 ++m_iterator.cells; 327 m_iterator.last_y = cur_cell->y; 328 329 for(;;) 330 { 331 int coord = cur_cell->packed_coord; 332 int area = cur_cell->area; 333 int last_x = cur_cell->x; 334 335 m_iterator.cover += cur_cell->cover; 336 337 //accumulate all cells with the same coordinates 338 for(; (cur_cell = *m_iterator.cells) != 0; ++m_iterator.cells) 339 { 340 if(cur_cell->packed_coord != coord) break; 341 area += cur_cell->area; 342 m_iterator.cover += cur_cell->cover; 343 } 344 345 int alpha; 346 if(cur_cell == 0 || cur_cell->y != m_iterator.last_y) 347 { 348 349 if(area) 350 { 351 alpha = calculate_alpha((m_iterator.cover << (poly_base_shift + 1)) - area); 352 if(alpha) 353 { 354 sl.add_cell(last_x, alpha); 355 } 356 ++last_x; 357 } 358 break; 359 } 360 361 ++m_iterator.cells; 362 363 if(area) 364 { 365 alpha = calculate_alpha((m_iterator.cover << (poly_base_shift + 1)) - area); 366 if(alpha) 367 { 368 sl.add_cell(last_x, alpha); 369 } 370 ++last_x; 371 } 372 373 if(cur_cell->x > last_x) 374 { 375 alpha = calculate_alpha(m_iterator.cover << (poly_base_shift + 1)); 376 if(alpha) 377 { 378 sl.add_span(last_x, cur_cell->x - last_x, alpha); 379 } 380 } 381 } 382 if(sl.num_spans()) 383 { 384 sl.finalize(m_iterator.last_y); 385 break; 386 } 387 } 388 return true; 389 } 390 391 392 //-------------------------------------------------------------------- 393 bool hit_test(int tx, int ty); 394 395 396 //-------------------------------------------------------------------- 397 void add_xy(const double* x, const double* y, unsigned n) 398 { 399 if(n > 2) 400 { 401 move_to_d(*x++, *y++); 402 --n; 403 do 404 { 405 line_to_d(*x++, *y++); 406 } 407 while(--n); 408 } 409 } 410 411 //------------------------------------------------------------------- 412 template<class VertexSource> 413 void add_path(VertexSource& vs, unsigned id=0) 414 { 415 double x; 416 double y; 417 418 unsigned cmd; 419 vs.rewind(id); 420 while(!is_stop(cmd = vs.vertex(&x, &y))) 421 { 422 add_vertex(x, y, cmd); 423 } 424 } 425 426 427 private: 428 //-------------------------------------------------------------------- 429 // Disable copying 430 rasterizer_scanline_aa(const rasterizer_scanline_aa<XScale, AA_Shift>&); 431 const rasterizer_scanline_aa<XScale, AA_Shift>& 432 operator = (const rasterizer_scanline_aa<XScale, AA_Shift>&); 433 434 //-------------------------------------------------------------------- 435 void move_to_no_clip(int x, int y); 436 void line_to_no_clip(int x, int y); 437 void close_polygon_no_clip(); 438 void clip_segment(int x, int y); 439 440 private: 441 outline_aa m_outline; 442 int m_gamma[aa_num]; 443 filling_rule_e m_filling_rule; 444 int m_clipped_start_x; 445 int m_clipped_start_y; 446 int m_start_x; 447 int m_start_y; 448 int m_prev_x; 449 int m_prev_y; 450 unsigned m_prev_flags; 451 unsigned m_status; 452 rect m_clip_box; 453 bool m_clipping; 454 iterator m_iterator; 455 }; 456 457 458 459 460 461 462 463 464 465 466 //------------------------------------------------------------------------ 467 template<unsigned XScale, unsigned AA_Shift> 468 void rasterizer_scanline_aa<XScale, AA_Shift>::reset() 469 { 470 m_outline.reset(); 471 m_status = status_initial; 472 } 473 474 //------------------------------------------------------------------------ 475 template<unsigned XScale, unsigned AA_Shift> 476 void rasterizer_scanline_aa<XScale, AA_Shift>::filling_rule(filling_rule_e filling_rule) 477 { 478 m_filling_rule = filling_rule; 479 } 480 481 //------------------------------------------------------------------------ 482 template<unsigned XScale, unsigned AA_Shift> 483 void rasterizer_scanline_aa<XScale, AA_Shift>::clip_box(double x1, double y1, double x2, double y2) 484 { 485 reset(); 486 m_clip_box = rect(poly_coord(x1), poly_coord(y1), 487 poly_coord(x2), poly_coord(y2)); 488 m_clip_box.normalize(); 489 m_clipping = true; 490 } 491 492 //------------------------------------------------------------------------ 493 template<unsigned XScale, unsigned AA_Shift> 494 void rasterizer_scanline_aa<XScale, AA_Shift>::reset_clipping() 495 { 496 reset(); 497 m_clipping = false; 498 } 499 500 501 502 //------------------------------------------------------------------------ 503 template<unsigned XScale, unsigned AA_Shift> 504 void rasterizer_scanline_aa<XScale, AA_Shift>::move_to_no_clip(int x, int y) 505 { 506 if(m_status == status_line_to) 507 { 508 close_polygon_no_clip(); 509 } 510 m_outline.move_to(x * XScale, y); 511 m_clipped_start_x = x; 512 m_clipped_start_y = y; 513 m_status = status_line_to; 514 } 515 516 517 //------------------------------------------------------------------------ 518 template<unsigned XScale, unsigned AA_Shift> 519 void rasterizer_scanline_aa<XScale, AA_Shift>::line_to_no_clip(int x, int y) 520 { 521 if(m_status != status_initial) 522 { 523 m_outline.line_to(x * XScale, y); 524 m_status = status_line_to; 525 } 526 } 527 528 529 //------------------------------------------------------------------------ 530 template<unsigned XScale, unsigned AA_Shift> 531 void rasterizer_scanline_aa<XScale, AA_Shift>::close_polygon_no_clip() 532 { 533 if(m_status == status_line_to) 534 { 535 m_outline.line_to(m_clipped_start_x * XScale, m_clipped_start_y); 536 m_status = status_closed; 537 } 538 } 539 540 541 //------------------------------------------------------------------------ 542 template<unsigned XScale, unsigned AA_Shift> 543 void rasterizer_scanline_aa<XScale, AA_Shift>::clip_segment(int x, int y) 544 { 545 unsigned flags = clipping_flags(x, y, m_clip_box); 546 if(m_prev_flags == flags) 547 { 548 if(flags == 0) 549 { 550 if(m_status == status_initial) 551 { 552 move_to_no_clip(x, y); 553 } 554 else 555 { 556 line_to_no_clip(x, y); 557 } 558 } 559 } 560 else 561 { 562 int cx[4]; 563 int cy[4]; 564 unsigned n = clip_liang_barsky(m_prev_x, m_prev_y, 565 x, y, 566 m_clip_box, 567 cx, cy); 568 const int* px = cx; 569 const int* py = cy; 570 while(n--) 571 { 572 if(m_status == status_initial) 573 { 574 move_to_no_clip(*px++, *py++); 575 } 576 else 577 { 578 line_to_no_clip(*px++, *py++); 579 } 580 } 581 } 582 m_prev_flags = flags; 583 m_prev_x = x; 584 m_prev_y = y; 585 } 586 587 588 589 //------------------------------------------------------------------------ 590 template<unsigned XScale, unsigned AA_Shift> 591 void rasterizer_scanline_aa<XScale, AA_Shift>::add_vertex(double x, double y, unsigned cmd) 592 { 593 if(is_close(cmd)) 594 { 595 close_polygon(); 596 } 597 else 598 { 599 if(is_move_to(cmd)) 600 { 601 move_to(poly_coord(x), poly_coord(y)); 602 } 603 else 604 { 605 if(is_vertex(cmd)) 606 { 607 line_to(poly_coord(x), poly_coord(y)); 608 } 609 } 610 } 611 } 612 613 614 615 //------------------------------------------------------------------------ 616 template<unsigned XScale, unsigned AA_Shift> 617 void rasterizer_scanline_aa<XScale, AA_Shift>::move_to(int x, int y) 618 { 619 if(m_clipping) 620 { 621 if(m_outline.sorted()) 622 { 623 reset(); 624 } 625 if(m_status == status_line_to) 626 { 627 close_polygon(); 628 } 629 m_prev_x = m_start_x = x; 630 m_prev_y = m_start_y = y; 631 m_status = status_initial; 632 m_prev_flags = clipping_flags(x, y, m_clip_box); 633 if(m_prev_flags == 0) 634 { 635 move_to_no_clip(x, y); 636 } 637 } 638 else 639 { 640 move_to_no_clip(x, y); 641 } 642 } 643 644 //------------------------------------------------------------------------ 645 template<unsigned XScale, unsigned AA_Shift> 646 void rasterizer_scanline_aa<XScale, AA_Shift>::line_to(int x, int y) 647 { 648 if(m_clipping) 649 { 650 clip_segment(x, y); 651 } 652 else 653 { 654 line_to_no_clip(x, y); 655 } 656 } 657 658 //------------------------------------------------------------------------ 659 template<unsigned XScale, unsigned AA_Shift> 660 void rasterizer_scanline_aa<XScale, AA_Shift>::close_polygon() 661 { 662 if(m_clipping) 663 { 664 clip_segment(m_start_x, m_start_y); 665 } 666 close_polygon_no_clip(); 667 } 668 669 //------------------------------------------------------------------------ 670 template<unsigned XScale, unsigned AA_Shift> 671 void rasterizer_scanline_aa<XScale, AA_Shift>::move_to_d(double x, double y) 672 { 673 move_to(poly_coord(x), poly_coord(y)); 674 } 675 676 //------------------------------------------------------------------------ 677 template<unsigned XScale, unsigned AA_Shift> 678 void rasterizer_scanline_aa<XScale, AA_Shift>::line_to_d(double x, double y) 679 { 680 line_to(poly_coord(x), poly_coord(y)); 681 } 682 683 684 //------------------------------------------------------------------------ 685 template<unsigned XScale, unsigned AA_Shift> 686 bool rasterizer_scanline_aa<XScale, AA_Shift>::hit_test(int tx, int ty) 687 { 688 close_polygon(); 689 const cell_aa* const* cells = m_outline.cells(); 690 if(m_outline.num_cells() == 0) return false; 691 692 int cover = 0; 693 694 const cell_aa* cur_cell = *cells++; 695 for(;;) 696 { 697 int alpha; 698 int coord = cur_cell->packed_coord; 699 int x = cur_cell->x; 700 int y = cur_cell->y; 701 702 if(y > ty) return false; 703 704 int area = cur_cell->area; 705 cover += cur_cell->cover; 706 707 while((cur_cell = *cells++) != 0) 708 { 709 if(cur_cell->packed_coord != coord) break; 710 area += cur_cell->area; 711 cover += cur_cell->cover; 712 } 713 714 if(area) 715 { 716 alpha = calculate_alpha((cover << (poly_base_shift + 1)) - area); 717 if(alpha) 718 { 719 if(tx == x && ty == y) return true; 720 } 721 x++; 722 } 723 724 if(!cur_cell) break; 725 726 if(cur_cell->x > x) 727 { 728 alpha = calculate_alpha(cover << (poly_base_shift + 1)); 729 if(alpha) 730 { 731 if(ty == y && tx >= x && tx <= cur_cell->x) return true; 732 } 733 } 734 } 735 return false; 736 } 737 738 } 739 740 741 742 #endif 743 744