1 //---------------------------------------------------------------------------- 2 // Anti-Grain Geometry - Version 2.3 3 // Copyright (C) 2002-2005 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 // 12 // The author gratefully acknowleges the support of David Turner, 13 // Robert Wilhelm, and Werner Lemberg - the authors of the FreeType 14 // libray - in producing this work. See http://www.freetype.org for details. 15 // 16 //---------------------------------------------------------------------------- 17 // Contact: mcseem@antigrain.com 18 // mcseemagg@yahoo.com 19 // http://www.antigrain.com 20 //---------------------------------------------------------------------------- 21 // 22 // Adaptation for 32-bit screen coordinates has been sponsored by 23 // Liberty Technology Systems, Inc., visit http://lib-sys.com 24 // 25 // Liberty Technology Systems, Inc. is the provider of 26 // PostScript and PDF technology for software developers. 27 // 28 //---------------------------------------------------------------------------- 29 #ifndef AGG_RASTERIZER_COMPOUND_AA_INCLUDED 30 #define AGG_RASTERIZER_COMPOUND_AA_INCLUDED 31 32 #include "agg_rasterizer_cells_aa.h" 33 #include "agg_rasterizer_sl_clip.h" 34 35 namespace agg 36 { 37 38 //-----------------------------------------------------------cell_style_aa 39 // A pixel cell. There're no constructors defined and it was done 40 // intentionally in order to avoid extra overhead when allocating an 41 // array of cells. 42 struct cell_style_aa 43 { 44 int x; 45 int y; 46 int cover; 47 int area; 48 int16 left, right; 49 initialcell_style_aa50 void initial() 51 { 52 x = 0x7FFFFFFF; 53 y = 0x7FFFFFFF; 54 cover = 0; 55 area = 0; 56 left = -1; 57 right = -1; 58 } 59 stylecell_style_aa60 void style(const cell_style_aa& c) 61 { 62 left = c.left; 63 right = c.right; 64 } 65 not_equalcell_style_aa66 int not_equal(int ex, int ey, const cell_style_aa& c) const 67 { 68 return (ex - x) | (ey - y) | (left - c.left) | (right - c.right); 69 } 70 }; 71 72 73 //===========================================================layer_order_e 74 enum layer_order_e 75 { 76 layer_unsorted, //------layer_unsorted 77 layer_direct, //------layer_direct 78 layer_inverse //------layer_inverse 79 }; 80 81 82 //==================================================rasterizer_compound_aa 83 template<class Clip=rasterizer_sl_clip_int> class rasterizer_compound_aa 84 { 85 struct style_info 86 { 87 unsigned start_cell; 88 unsigned num_cells; 89 int last_x; 90 }; 91 92 struct cell_info 93 { 94 int x, area, cover; 95 }; 96 97 public: 98 typedef Clip clip_type; 99 typedef typename Clip::conv_type conv_type; 100 typedef typename Clip::coord_type coord_type; 101 102 enum aa_scale_e 103 { 104 aa_shift = 8, 105 aa_scale = 1 << aa_shift, 106 aa_mask = aa_scale - 1, 107 aa_scale2 = aa_scale * 2, 108 aa_mask2 = aa_scale2 - 1 109 }; 110 111 //-------------------------------------------------------------------- rasterizer_compound_aa()112 rasterizer_compound_aa() : 113 m_outline(), 114 m_clipper(), 115 m_filling_rule(fill_non_zero), 116 m_layer_order(layer_direct), 117 m_styles(), // Active Styles 118 m_ast(), // Active Style Table (unique values) 119 m_asm(), // Active Style Mask 120 m_cells(), 121 m_cover_buf(), 122 m_master_alpha(), 123 m_min_style(0x7FFFFFFF), 124 m_max_style(-0x7FFFFFFF), 125 m_start_x(0), 126 m_start_y(0), 127 m_scan_y(0x7FFFFFFF), 128 m_sl_start(0), 129 m_sl_len(0) 130 {} 131 132 //-------------------------------------------------------------------- 133 void reset(); 134 void reset_clipping(); 135 void clip_box(double x1, double y1, double x2, double y2); 136 void filling_rule(filling_rule_e filling_rule); 137 void layer_order(layer_order_e order); 138 void master_alpha(int style, double alpha); 139 140 //-------------------------------------------------------------------- 141 void styles(int left, int right); 142 void move_to(int x, int y); 143 void line_to(int x, int y); 144 void move_to_d(double x, double y); 145 void line_to_d(double x, double y); 146 void add_vertex(double x, double y, unsigned cmd); 147 148 void edge(int x1, int y1, int x2, int y2); 149 void edge_d(double x1, double y1, double x2, double y2); 150 151 //------------------------------------------------------------------- 152 template<class VertexSource> 153 void add_path(VertexSource& vs, unsigned path_id=0) 154 { 155 double x; 156 double y; 157 158 unsigned cmd; 159 vs.rewind(path_id); 160 if(m_outline.sorted()) reset(); 161 while(!is_stop(cmd = vs.vertex(&x, &y))) 162 { 163 add_vertex(x, y, cmd); 164 } 165 } 166 167 168 //-------------------------------------------------------------------- min_x()169 int min_x() const { return m_outline.min_x(); } min_y()170 int min_y() const { return m_outline.min_y(); } max_x()171 int max_x() const { return m_outline.max_x(); } max_y()172 int max_y() const { return m_outline.max_y(); } min_style()173 int min_style() const { return m_min_style; } max_style()174 int max_style() const { return m_max_style; } 175 176 //-------------------------------------------------------------------- 177 void sort(); 178 bool rewind_scanlines(); 179 unsigned sweep_styles(); scanline_start()180 int scanline_start() const { return m_sl_start; } scanline_length()181 unsigned scanline_length() const { return m_sl_len; } 182 unsigned style(unsigned style_idx) const; 183 184 cover_type* allocate_cover_buffer(unsigned len); 185 186 //-------------------------------------------------------------------- 187 bool navigate_scanline(int y); 188 bool hit_test(int tx, int ty); 189 190 //-------------------------------------------------------------------- calculate_alpha(int area,unsigned master_alpha)191 AGG_INLINE unsigned calculate_alpha(int area, unsigned master_alpha) const 192 { 193 int cover = area >> (poly_subpixel_shift*2 + 1 - aa_shift); 194 if(cover < 0) cover = -cover; 195 if(m_filling_rule == fill_even_odd) 196 { 197 cover &= aa_mask2; 198 if(cover > aa_scale) 199 { 200 cover = aa_scale2 - cover; 201 } 202 } 203 if(cover > aa_mask) cover = aa_mask; 204 return (cover * master_alpha + aa_mask) >> aa_shift; 205 } 206 207 //-------------------------------------------------------------------- 208 // Sweeps one scanline with one style index. The style ID can be 209 // determined by calling style(). sweep_scanline(Scanline & sl,int style_idx)210 template<class Scanline> bool sweep_scanline(Scanline& sl, int style_idx) 211 { 212 int scan_y = m_scan_y - 1; 213 if(scan_y > m_outline.max_y()) return false; 214 215 sl.reset_spans(); 216 217 unsigned master_alpha = aa_mask; 218 219 if(style_idx < 0) 220 { 221 style_idx = 0; 222 } 223 else 224 { 225 style_idx++; 226 master_alpha = m_master_alpha[m_ast[style_idx] + m_min_style - 1]; 227 } 228 229 const style_info& st = m_styles[m_ast[style_idx]]; 230 231 unsigned num_cells = st.num_cells; 232 cell_info* cell = &m_cells[st.start_cell]; 233 234 int cover = 0; 235 while(num_cells--) 236 { 237 unsigned alpha; 238 int x = cell->x; 239 int area = cell->area; 240 241 cover += cell->cover; 242 243 ++cell; 244 245 if(area) 246 { 247 alpha = calculate_alpha((cover << (poly_subpixel_shift + 1)) - area, 248 master_alpha); 249 sl.add_cell(x, alpha); 250 x++; 251 } 252 253 if(num_cells && cell->x > x) 254 { 255 alpha = calculate_alpha(cover << (poly_subpixel_shift + 1), 256 master_alpha); 257 if(alpha) 258 { 259 sl.add_span(x, cell->x - x, alpha); 260 } 261 } 262 } 263 264 if(sl.num_spans() == 0) return false; 265 sl.finalize(scan_y); 266 return true; 267 } 268 269 private: 270 void add_style(int style_id); 271 void allocate_master_alpha(); 272 273 //-------------------------------------------------------------------- 274 // Disable copying 275 rasterizer_compound_aa(const rasterizer_compound_aa<Clip>&); 276 const rasterizer_compound_aa<Clip>& 277 operator = (const rasterizer_compound_aa<Clip>&); 278 279 private: 280 rasterizer_cells_aa<cell_style_aa> m_outline; 281 clip_type m_clipper; 282 filling_rule_e m_filling_rule; 283 layer_order_e m_layer_order; 284 pod_vector<style_info> m_styles; // Active Styles 285 pod_vector<unsigned> m_ast; // Active Style Table (unique values) 286 pod_vector<int8u> m_asm; // Active Style Mask 287 pod_vector<cell_info> m_cells; 288 pod_vector<cover_type> m_cover_buf; 289 pod_bvector<unsigned> m_master_alpha; 290 291 int m_min_style; 292 int m_max_style; 293 coord_type m_start_x; 294 coord_type m_start_y; 295 int m_scan_y; 296 int m_sl_start; 297 unsigned m_sl_len; 298 }; 299 300 301 302 303 304 305 306 307 308 309 //------------------------------------------------------------------------ 310 template<class Clip> reset()311 void rasterizer_compound_aa<Clip>::reset() 312 { 313 m_outline.reset(); 314 m_min_style = 0x7FFFFFFF; 315 m_max_style = -0x7FFFFFFF; 316 m_scan_y = 0x7FFFFFFF; 317 m_sl_start = 0; 318 m_sl_len = 0; 319 } 320 321 //------------------------------------------------------------------------ 322 template<class Clip> filling_rule(filling_rule_e filling_rule)323 void rasterizer_compound_aa<Clip>::filling_rule(filling_rule_e filling_rule) 324 { 325 m_filling_rule = filling_rule; 326 } 327 328 //------------------------------------------------------------------------ 329 template<class Clip> layer_order(layer_order_e order)330 void rasterizer_compound_aa<Clip>::layer_order(layer_order_e order) 331 { 332 m_layer_order = order; 333 } 334 335 //------------------------------------------------------------------------ 336 template<class Clip> clip_box(double x1,double y1,double x2,double y2)337 void rasterizer_compound_aa<Clip>::clip_box(double x1, double y1, 338 double x2, double y2) 339 { 340 reset(); 341 m_clipper.clip_box(conv_type::upscale(x1), conv_type::upscale(y1), 342 conv_type::upscale(x2), conv_type::upscale(y2)); 343 } 344 345 //------------------------------------------------------------------------ 346 template<class Clip> reset_clipping()347 void rasterizer_compound_aa<Clip>::reset_clipping() 348 { 349 reset(); 350 m_clipper.reset_clipping(); 351 } 352 353 //------------------------------------------------------------------------ 354 template<class Clip> styles(int left,int right)355 void rasterizer_compound_aa<Clip>::styles(int left, int right) 356 { 357 cell_style_aa cell; 358 cell.initial(); 359 cell.left = (int16)left; 360 cell.right = (int16)right; 361 m_outline.style(cell); 362 if(left >= 0 && left < m_min_style) m_min_style = left; 363 if(left >= 0 && left > m_max_style) m_max_style = left; 364 if(right >= 0 && right < m_min_style) m_min_style = right; 365 if(right >= 0 && right > m_max_style) m_max_style = right; 366 } 367 368 //------------------------------------------------------------------------ 369 template<class Clip> move_to(int x,int y)370 void rasterizer_compound_aa<Clip>::move_to(int x, int y) 371 { 372 if(m_outline.sorted()) reset(); 373 m_clipper.move_to(m_start_x = conv_type::downscale(x), 374 m_start_y = conv_type::downscale(y)); 375 } 376 377 //------------------------------------------------------------------------ 378 template<class Clip> line_to(int x,int y)379 void rasterizer_compound_aa<Clip>::line_to(int x, int y) 380 { 381 m_clipper.line_to(m_outline, 382 conv_type::downscale(x), 383 conv_type::downscale(y)); 384 } 385 386 //------------------------------------------------------------------------ 387 template<class Clip> move_to_d(double x,double y)388 void rasterizer_compound_aa<Clip>::move_to_d(double x, double y) 389 { 390 if(m_outline.sorted()) reset(); 391 m_clipper.move_to(m_start_x = conv_type::upscale(x), 392 m_start_y = conv_type::upscale(y)); 393 } 394 395 //------------------------------------------------------------------------ 396 template<class Clip> line_to_d(double x,double y)397 void rasterizer_compound_aa<Clip>::line_to_d(double x, double y) 398 { 399 m_clipper.line_to(m_outline, 400 conv_type::upscale(x), 401 conv_type::upscale(y)); 402 } 403 404 //------------------------------------------------------------------------ 405 template<class Clip> add_vertex(double x,double y,unsigned cmd)406 void rasterizer_compound_aa<Clip>::add_vertex(double x, double y, unsigned cmd) 407 { 408 if(is_move_to(cmd)) 409 { 410 move_to_d(x, y); 411 } 412 else 413 if(is_vertex(cmd)) 414 { 415 line_to_d(x, y); 416 } 417 else 418 if(is_close(cmd)) 419 { 420 m_clipper.line_to(m_outline, m_start_x, m_start_y); 421 } 422 } 423 424 //------------------------------------------------------------------------ 425 template<class Clip> edge(int x1,int y1,int x2,int y2)426 void rasterizer_compound_aa<Clip>::edge(int x1, int y1, int x2, int y2) 427 { 428 if(m_outline.sorted()) reset(); 429 m_clipper.move_to(conv_type::downscale(x1), conv_type::downscale(y1)); 430 m_clipper.line_to(m_outline, 431 conv_type::downscale(x2), 432 conv_type::downscale(y2)); 433 } 434 435 //------------------------------------------------------------------------ 436 template<class Clip> edge_d(double x1,double y1,double x2,double y2)437 void rasterizer_compound_aa<Clip>::edge_d(double x1, double y1, 438 double x2, double y2) 439 { 440 if(m_outline.sorted()) reset(); 441 m_clipper.move_to(conv_type::upscale(x1), conv_type::upscale(y1)); 442 m_clipper.line_to(m_outline, 443 conv_type::upscale(x2), 444 conv_type::upscale(y2)); 445 } 446 447 //------------------------------------------------------------------------ 448 template<class Clip> sort()449 AGG_INLINE void rasterizer_compound_aa<Clip>::sort() 450 { 451 m_outline.sort_cells(); 452 } 453 454 //------------------------------------------------------------------------ 455 template<class Clip> rewind_scanlines()456 AGG_INLINE bool rasterizer_compound_aa<Clip>::rewind_scanlines() 457 { 458 m_outline.sort_cells(); 459 if(m_outline.total_cells() == 0) 460 { 461 return false; 462 } 463 if(m_max_style < m_min_style) 464 { 465 return false; 466 } 467 m_scan_y = m_outline.min_y(); 468 m_styles.allocate(m_max_style - m_min_style + 2, 128); 469 allocate_master_alpha(); 470 return true; 471 } 472 473 //------------------------------------------------------------------------ 474 template<class Clip> add_style(int style_id)475 AGG_INLINE void rasterizer_compound_aa<Clip>::add_style(int style_id) 476 { 477 if(style_id < 0) style_id = 0; 478 else style_id -= m_min_style - 1; 479 480 unsigned nbyte = style_id >> 3; 481 unsigned mask = 1 << (style_id & 7); 482 483 style_info* style = &m_styles[style_id]; 484 if((m_asm[nbyte] & mask) == 0) 485 { 486 m_ast.add(style_id); 487 m_asm[nbyte] |= mask; 488 style->start_cell = 0; 489 style->num_cells = 0; 490 style->last_x = -0x7FFFFFFF; 491 } 492 ++style->start_cell; 493 } 494 495 //------------------------------------------------------------------------ 496 // Returns the number of styles 497 template<class Clip> sweep_styles()498 unsigned rasterizer_compound_aa<Clip>::sweep_styles() 499 { 500 for(;;) 501 { 502 if(m_scan_y > m_outline.max_y()) return 0; 503 unsigned num_cells = m_outline.scanline_num_cells(m_scan_y); 504 const cell_style_aa* const* cells = m_outline.scanline_cells(m_scan_y); 505 unsigned num_styles = m_max_style - m_min_style + 2; 506 const cell_style_aa* curr_cell; 507 unsigned style_id; 508 style_info* style; 509 cell_info* cell; 510 511 m_cells.allocate(num_cells * 2, 256); // Each cell can have two styles 512 m_ast.capacity(num_styles, 64); 513 m_asm.allocate((num_styles + 7) >> 3, 8); 514 m_asm.zero(); 515 516 if(num_cells) 517 { 518 // Pre-add zero (for no-fill style, that is, -1). 519 // We need that to ensure that the "-1 style" would go first. 520 m_asm[0] |= 1; 521 m_ast.add(0); 522 style = &m_styles[0]; 523 style->start_cell = 0; 524 style->num_cells = 0; 525 style->last_x = -0x7FFFFFFF; 526 527 m_sl_start = cells[0]->x; 528 m_sl_len = cells[num_cells-1]->x - m_sl_start + 1; 529 while(num_cells--) 530 { 531 curr_cell = *cells++; 532 add_style(curr_cell->left); 533 add_style(curr_cell->right); 534 } 535 536 // Convert the Y-histogram into the array of starting indexes 537 unsigned i; 538 unsigned start_cell = 0; 539 for(i = 0; i < m_ast.size(); i++) 540 { 541 style_info& st = m_styles[m_ast[i]]; 542 unsigned v = st.start_cell; 543 st.start_cell = start_cell; 544 start_cell += v; 545 } 546 547 cells = m_outline.scanline_cells(m_scan_y); 548 num_cells = m_outline.scanline_num_cells(m_scan_y); 549 550 while(num_cells--) 551 { 552 curr_cell = *cells++; 553 style_id = (curr_cell->left < 0) ? 0 : 554 curr_cell->left - m_min_style + 1; 555 556 style = &m_styles[style_id]; 557 if(curr_cell->x == style->last_x) 558 { 559 cell = &m_cells[style->start_cell + style->num_cells - 1]; 560 cell->area += curr_cell->area; 561 cell->cover += curr_cell->cover; 562 } 563 else 564 { 565 cell = &m_cells[style->start_cell + style->num_cells]; 566 cell->x = curr_cell->x; 567 cell->area = curr_cell->area; 568 cell->cover = curr_cell->cover; 569 style->last_x = curr_cell->x; 570 style->num_cells++; 571 } 572 573 style_id = (curr_cell->right < 0) ? 0 : 574 curr_cell->right - m_min_style + 1; 575 576 style = &m_styles[style_id]; 577 if(curr_cell->x == style->last_x) 578 { 579 cell = &m_cells[style->start_cell + style->num_cells - 1]; 580 cell->area -= curr_cell->area; 581 cell->cover -= curr_cell->cover; 582 } 583 else 584 { 585 cell = &m_cells[style->start_cell + style->num_cells]; 586 cell->x = curr_cell->x; 587 cell->area = -curr_cell->area; 588 cell->cover = -curr_cell->cover; 589 style->last_x = curr_cell->x; 590 style->num_cells++; 591 } 592 } 593 } 594 if(m_ast.size() > 1) break; 595 ++m_scan_y; 596 } 597 ++m_scan_y; 598 599 if(m_layer_order != layer_unsorted) 600 { 601 range_adaptor<pod_vector<unsigned> > ra(m_ast, 1, m_ast.size() - 1); 602 if(m_layer_order == layer_direct) quick_sort(ra, unsigned_greater); 603 else quick_sort(ra, unsigned_less); 604 } 605 606 return m_ast.size() - 1; 607 } 608 609 //------------------------------------------------------------------------ 610 // Returns style ID depending of the existing style index 611 template<class Clip> 612 AGG_INLINE style(unsigned style_idx)613 unsigned rasterizer_compound_aa<Clip>::style(unsigned style_idx) const 614 { 615 return m_ast[style_idx + 1] + m_min_style - 1; 616 } 617 618 //------------------------------------------------------------------------ 619 template<class Clip> navigate_scanline(int y)620 AGG_INLINE bool rasterizer_compound_aa<Clip>::navigate_scanline(int y) 621 { 622 m_outline.sort_cells(); 623 if(m_outline.total_cells() == 0) 624 { 625 return false; 626 } 627 if(m_max_style < m_min_style) 628 { 629 return false; 630 } 631 if(y < m_outline.min_y() || y > m_outline.max_y()) 632 { 633 return false; 634 } 635 m_scan_y = y; 636 m_styles.allocate(m_max_style - m_min_style + 2, 128); 637 allocate_master_alpha(); 638 return true; 639 } 640 641 //------------------------------------------------------------------------ 642 template<class Clip> hit_test(int tx,int ty)643 bool rasterizer_compound_aa<Clip>::hit_test(int tx, int ty) 644 { 645 if(!navigate_scanline(ty)) 646 { 647 return false; 648 } 649 650 unsigned num_styles = sweep_styles(); 651 if(num_styles <= 0) 652 { 653 return false; 654 } 655 656 scanline_hit_test sl(tx); 657 sweep_scanline(sl, -1); 658 return sl.hit(); 659 } 660 661 //------------------------------------------------------------------------ 662 template<class Clip> allocate_cover_buffer(unsigned len)663 cover_type* rasterizer_compound_aa<Clip>::allocate_cover_buffer(unsigned len) 664 { 665 m_cover_buf.allocate(len, 256); 666 return &m_cover_buf[0]; 667 } 668 669 //------------------------------------------------------------------------ 670 template<class Clip> allocate_master_alpha()671 void rasterizer_compound_aa<Clip>::allocate_master_alpha() 672 { 673 while((int)m_master_alpha.size() <= m_max_style) 674 { 675 m_master_alpha.add(aa_mask); 676 } 677 } 678 679 //------------------------------------------------------------------------ 680 template<class Clip> master_alpha(int style,double alpha)681 void rasterizer_compound_aa<Clip>::master_alpha(int style, double alpha) 682 { 683 if(style >= 0) 684 { 685 while((int)m_master_alpha.size() <= style) 686 { 687 m_master_alpha.add(aa_mask); 688 } 689 m_master_alpha[style] = uround(alpha * aa_mask); 690 } 691 } 692 693 } 694 695 696 697 #endif 698 699