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