1 //---------------------------------------------------------------------------- 2 // Anti-Grain Geometry - Version 2.4 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_CELLS_AA_INCLUDED 30 #define AGG_RASTERIZER_CELLS_AA_INCLUDED 31 32 #include <string.h> 33 #include <math.h> 34 #include "agg_math.h" 35 #include "agg_array.h" 36 37 38 namespace agg 39 { 40 41 //-----------------------------------------------------rasterizer_cells_aa 42 // An internal class that implements the main rasterization algorithm. 43 // Used in the rasterizer. Should not be used direcly. 44 template<class Cell> class rasterizer_cells_aa 45 { 46 enum cell_block_scale_e 47 { 48 cell_block_shift = 12, 49 cell_block_size = 1 << cell_block_shift, 50 cell_block_mask = cell_block_size - 1, 51 cell_block_pool = 256, 52 cell_block_limit = 1024 53 }; 54 55 struct sorted_y 56 { 57 unsigned start; 58 unsigned num; 59 }; 60 61 public: 62 typedef Cell cell_type; 63 typedef rasterizer_cells_aa<Cell> self_type; 64 65 ~rasterizer_cells_aa(); 66 rasterizer_cells_aa(); 67 68 void reset(); 69 void style(const cell_type& style_cell); 70 void line(int x1, int y1, int x2, int y2); 71 72 int min_x() const { return m_min_x; } 73 int min_y() const { return m_min_y; } 74 int max_x() const { return m_max_x; } 75 int max_y() const { return m_max_y; } 76 77 void sort_cells(); 78 79 unsigned total_cells() const 80 { 81 return m_num_cells; 82 } 83 84 unsigned scanline_num_cells(unsigned y) const 85 { 86 return m_sorted_y[y - m_min_y].num; 87 } 88 89 const cell_type* const* scanline_cells(unsigned y) const 90 { 91 return m_sorted_cells.data() + m_sorted_y[y - m_min_y].start; 92 } 93 94 bool sorted() const { return m_sorted; } 95 96 private: 97 rasterizer_cells_aa(const self_type&); 98 const self_type& operator = (const self_type&); 99 100 void set_curr_cell(int x, int y); 101 void add_curr_cell(); 102 void render_hline(int ey, int x1, int y1, int x2, int y2); 103 void allocate_block(); 104 105 private: 106 unsigned m_num_blocks; 107 unsigned m_max_blocks; 108 unsigned m_curr_block; 109 unsigned m_num_cells; 110 cell_type** m_cells; 111 cell_type* m_curr_cell_ptr; 112 pod_vector<cell_type*> m_sorted_cells; 113 pod_vector<sorted_y> m_sorted_y; 114 cell_type m_curr_cell; 115 cell_type m_style_cell; 116 int m_min_x; 117 int m_min_y; 118 int m_max_x; 119 int m_max_y; 120 bool m_sorted; 121 }; 122 123 124 125 126 //------------------------------------------------------------------------ 127 template<class Cell> 128 rasterizer_cells_aa<Cell>::~rasterizer_cells_aa() 129 { 130 if(m_num_blocks) 131 { 132 cell_type** ptr = m_cells + m_num_blocks - 1; 133 while(m_num_blocks--) 134 { 135 pod_allocator<cell_type>::deallocate(*ptr, cell_block_size); 136 ptr--; 137 } 138 pod_allocator<cell_type*>::deallocate(m_cells, m_max_blocks); 139 } 140 } 141 142 //------------------------------------------------------------------------ 143 template<class Cell> 144 rasterizer_cells_aa<Cell>::rasterizer_cells_aa() : 145 m_num_blocks(0), 146 m_max_blocks(0), 147 m_curr_block(0), 148 m_num_cells(0), 149 m_cells(0), 150 m_curr_cell_ptr(0), 151 m_sorted_cells(), 152 m_sorted_y(), 153 m_min_x(0x7FFFFFFF), 154 m_min_y(0x7FFFFFFF), 155 m_max_x(-0x7FFFFFFF), 156 m_max_y(-0x7FFFFFFF), 157 m_sorted(false) 158 { 159 m_style_cell.initial(); 160 m_curr_cell.initial(); 161 } 162 163 //------------------------------------------------------------------------ 164 template<class Cell> 165 void rasterizer_cells_aa<Cell>::reset() 166 { 167 m_num_cells = 0; 168 m_curr_block = 0; 169 m_curr_cell.initial(); 170 m_style_cell.initial(); 171 m_sorted = false; 172 m_min_x = 0x7FFFFFFF; 173 m_min_y = 0x7FFFFFFF; 174 m_max_x = -0x7FFFFFFF; 175 m_max_y = -0x7FFFFFFF; 176 } 177 178 //------------------------------------------------------------------------ 179 template<class Cell> 180 AGG_INLINE void rasterizer_cells_aa<Cell>::add_curr_cell() 181 { 182 if(m_curr_cell.area | m_curr_cell.cover) 183 { 184 if((m_num_cells & cell_block_mask) == 0) 185 { 186 if(m_num_blocks >= cell_block_limit) return; 187 allocate_block(); 188 } 189 *m_curr_cell_ptr++ = m_curr_cell; 190 ++m_num_cells; 191 } 192 } 193 194 //------------------------------------------------------------------------ 195 template<class Cell> 196 AGG_INLINE void rasterizer_cells_aa<Cell>::set_curr_cell(int x, int y) 197 { 198 if(m_curr_cell.not_equal(x, y, m_style_cell)) 199 { 200 add_curr_cell(); 201 m_curr_cell.style(m_style_cell); 202 m_curr_cell.x = x; 203 m_curr_cell.y = y; 204 m_curr_cell.cover = 0; 205 m_curr_cell.area = 0; 206 } 207 } 208 209 //------------------------------------------------------------------------ 210 template<class Cell> 211 AGG_INLINE void rasterizer_cells_aa<Cell>::render_hline(int ey, 212 int x1, int y1, 213 int x2, int y2) 214 { 215 int ex1 = x1 >> poly_subpixel_shift; 216 int ex2 = x2 >> poly_subpixel_shift; 217 int fx1 = x1 & poly_subpixel_mask; 218 int fx2 = x2 & poly_subpixel_mask; 219 220 int delta, p, first, dx; 221 int incr, lift, mod, rem; 222 223 //trivial case. Happens often 224 if(y1 == y2) 225 { 226 set_curr_cell(ex2, ey); 227 return; 228 } 229 230 //everything is located in a single cell. That is easy! 231 if(ex1 == ex2) 232 { 233 delta = y2 - y1; 234 m_curr_cell.cover += delta; 235 m_curr_cell.area += (fx1 + fx2) * delta; 236 return; 237 } 238 239 //ok, we'll have to render a run of adjacent cells on the same 240 //hline... 241 p = (poly_subpixel_scale - fx1) * (y2 - y1); 242 first = poly_subpixel_scale; 243 incr = 1; 244 245 dx = x2 - x1; 246 247 if(dx < 0) 248 { 249 p = fx1 * (y2 - y1); 250 first = 0; 251 incr = -1; 252 dx = -dx; 253 } 254 255 delta = p / dx; 256 mod = p % dx; 257 258 if(mod < 0) 259 { 260 delta--; 261 mod += dx; 262 } 263 264 m_curr_cell.cover += delta; 265 m_curr_cell.area += (fx1 + first) * delta; 266 267 ex1 += incr; 268 set_curr_cell(ex1, ey); 269 y1 += delta; 270 271 if(ex1 != ex2) 272 { 273 p = poly_subpixel_scale * (y2 - y1 + delta); 274 lift = p / dx; 275 rem = p % dx; 276 277 if (rem < 0) 278 { 279 lift--; 280 rem += dx; 281 } 282 283 mod -= dx; 284 285 while (ex1 != ex2) 286 { 287 delta = lift; 288 mod += rem; 289 if(mod >= 0) 290 { 291 mod -= dx; 292 delta++; 293 } 294 295 m_curr_cell.cover += delta; 296 m_curr_cell.area += poly_subpixel_scale * delta; 297 y1 += delta; 298 ex1 += incr; 299 set_curr_cell(ex1, ey); 300 } 301 } 302 delta = y2 - y1; 303 m_curr_cell.cover += delta; 304 m_curr_cell.area += (fx2 + poly_subpixel_scale - first) * delta; 305 } 306 307 //------------------------------------------------------------------------ 308 template<class Cell> 309 AGG_INLINE void rasterizer_cells_aa<Cell>::style(const cell_type& style_cell) 310 { 311 m_style_cell.style(style_cell); 312 } 313 314 //------------------------------------------------------------------------ 315 template<class Cell> 316 void rasterizer_cells_aa<Cell>::line(int x1, int y1, int x2, int y2) 317 { 318 enum dx_limit_e { dx_limit = 16384 << poly_subpixel_shift }; 319 320 int dx = x2 - x1; 321 322 if(dx >= dx_limit || dx <= -dx_limit) 323 { 324 int cx = (x1 + x2) >> 1; 325 int cy = (y1 + y2) >> 1; 326 line(x1, y1, cx, cy); 327 line(cx, cy, x2, y2); 328 } 329 330 int dy = y2 - y1; 331 int ex1 = x1 >> poly_subpixel_shift; 332 int ex2 = x2 >> poly_subpixel_shift; 333 int ey1 = y1 >> poly_subpixel_shift; 334 int ey2 = y2 >> poly_subpixel_shift; 335 int fy1 = y1 & poly_subpixel_mask; 336 int fy2 = y2 & poly_subpixel_mask; 337 338 int x_from, x_to; 339 int p, rem, mod, lift, delta, first, incr; 340 341 if(ex1 < m_min_x) m_min_x = ex1; 342 if(ex1 > m_max_x) m_max_x = ex1; 343 if(ey1 < m_min_y) m_min_y = ey1; 344 if(ey1 > m_max_y) m_max_y = ey1; 345 if(ex2 < m_min_x) m_min_x = ex2; 346 if(ex2 > m_max_x) m_max_x = ex2; 347 if(ey2 < m_min_y) m_min_y = ey2; 348 if(ey2 > m_max_y) m_max_y = ey2; 349 350 set_curr_cell(ex1, ey1); 351 352 //everything is on a single hline 353 if(ey1 == ey2) 354 { 355 render_hline(ey1, x1, fy1, x2, fy2); 356 return; 357 } 358 359 //Vertical line - we have to calculate start and end cells, 360 //and then - the common values of the area and coverage for 361 //all cells of the line. We know exactly there's only one 362 //cell, so, we don't have to call render_hline(). 363 incr = 1; 364 if(dx == 0) 365 { 366 int ex = x1 >> poly_subpixel_shift; 367 int two_fx = (x1 - (ex << poly_subpixel_shift)) << 1; 368 int area; 369 370 first = poly_subpixel_scale; 371 if(dy < 0) 372 { 373 first = 0; 374 incr = -1; 375 } 376 377 x_from = x1; 378 379 //render_hline(ey1, x_from, fy1, x_from, first); 380 delta = first - fy1; 381 m_curr_cell.cover += delta; 382 m_curr_cell.area += two_fx * delta; 383 384 ey1 += incr; 385 set_curr_cell(ex, ey1); 386 387 delta = first + first - poly_subpixel_scale; 388 area = two_fx * delta; 389 while(ey1 != ey2) 390 { 391 //render_hline(ey1, x_from, poly_subpixel_scale - first, x_from, first); 392 m_curr_cell.cover = delta; 393 m_curr_cell.area = area; 394 ey1 += incr; 395 set_curr_cell(ex, ey1); 396 } 397 //render_hline(ey1, x_from, poly_subpixel_scale - first, x_from, fy2); 398 delta = fy2 - poly_subpixel_scale + first; 399 m_curr_cell.cover += delta; 400 m_curr_cell.area += two_fx * delta; 401 return; 402 } 403 404 //ok, we have to render several hlines 405 p = (poly_subpixel_scale - fy1) * dx; 406 first = poly_subpixel_scale; 407 408 if(dy < 0) 409 { 410 p = fy1 * dx; 411 first = 0; 412 incr = -1; 413 dy = -dy; 414 } 415 416 delta = p / dy; 417 mod = p % dy; 418 419 if(mod < 0) 420 { 421 delta--; 422 mod += dy; 423 } 424 425 x_from = x1 + delta; 426 render_hline(ey1, x1, fy1, x_from, first); 427 428 ey1 += incr; 429 set_curr_cell(x_from >> poly_subpixel_shift, ey1); 430 431 if(ey1 != ey2) 432 { 433 p = poly_subpixel_scale * dx; 434 lift = p / dy; 435 rem = p % dy; 436 437 if(rem < 0) 438 { 439 lift--; 440 rem += dy; 441 } 442 mod -= dy; 443 444 while(ey1 != ey2) 445 { 446 delta = lift; 447 mod += rem; 448 if (mod >= 0) 449 { 450 mod -= dy; 451 delta++; 452 } 453 454 x_to = x_from + delta; 455 render_hline(ey1, x_from, poly_subpixel_scale - first, x_to, first); 456 x_from = x_to; 457 458 ey1 += incr; 459 set_curr_cell(x_from >> poly_subpixel_shift, ey1); 460 } 461 } 462 render_hline(ey1, x_from, poly_subpixel_scale - first, x2, fy2); 463 } 464 465 //------------------------------------------------------------------------ 466 template<class Cell> 467 void rasterizer_cells_aa<Cell>::allocate_block() 468 { 469 if(m_curr_block >= m_num_blocks) 470 { 471 if(m_num_blocks >= m_max_blocks) 472 { 473 cell_type** new_cells = 474 pod_allocator<cell_type*>::allocate(m_max_blocks + 475 cell_block_pool); 476 477 if(m_cells) 478 { 479 memcpy(new_cells, m_cells, m_max_blocks * sizeof(cell_type*)); 480 pod_allocator<cell_type*>::deallocate(m_cells, m_max_blocks); 481 } 482 m_cells = new_cells; 483 m_max_blocks += cell_block_pool; 484 } 485 486 m_cells[m_num_blocks++] = 487 pod_allocator<cell_type>::allocate(cell_block_size); 488 489 } 490 m_curr_cell_ptr = m_cells[m_curr_block++]; 491 } 492 493 494 495 //------------------------------------------------------------------------ 496 template <class T> static AGG_INLINE void swap_cells(T* a, T* b) 497 { 498 T temp = *a; 499 *a = *b; 500 *b = temp; 501 } 502 503 504 //------------------------------------------------------------------------ 505 enum 506 { 507 qsort_threshold = 9 508 }; 509 510 511 //------------------------------------------------------------------------ 512 template<class Cell> 513 void qsort_cells(Cell** start, unsigned num) 514 { 515 Cell** stack[80]; 516 Cell*** top; 517 Cell** limit; 518 Cell** base; 519 520 limit = start + num; 521 base = start; 522 top = stack; 523 524 for (;;) 525 { 526 int len = int(limit - base); 527 528 Cell** i; 529 Cell** j; 530 Cell** pivot; 531 532 if(len > qsort_threshold) 533 { 534 // we use base + len/2 as the pivot 535 pivot = base + len / 2; 536 swap_cells(base, pivot); 537 538 i = base + 1; 539 j = limit - 1; 540 541 // now ensure that *i <= *base <= *j 542 if((*j)->x < (*i)->x) 543 { 544 swap_cells(i, j); 545 } 546 547 if((*base)->x < (*i)->x) 548 { 549 swap_cells(base, i); 550 } 551 552 if((*j)->x < (*base)->x) 553 { 554 swap_cells(base, j); 555 } 556 557 for(;;) 558 { 559 int x = (*base)->x; 560 do i++; while( (*i)->x < x ); 561 do j--; while( x < (*j)->x ); 562 563 if(i > j) 564 { 565 break; 566 } 567 568 swap_cells(i, j); 569 } 570 571 swap_cells(base, j); 572 573 // now, push the largest sub-array 574 if(j - base > limit - i) 575 { 576 top[0] = base; 577 top[1] = j; 578 base = i; 579 } 580 else 581 { 582 top[0] = i; 583 top[1] = limit; 584 limit = j; 585 } 586 top += 2; 587 } 588 else 589 { 590 // the sub-array is small, perform insertion sort 591 j = base; 592 i = j + 1; 593 594 for(; i < limit; j = i, i++) 595 { 596 for(; j[1]->x < (*j)->x; j--) 597 { 598 swap_cells(j + 1, j); 599 if (j == base) 600 { 601 break; 602 } 603 } 604 } 605 606 if(top > stack) 607 { 608 top -= 2; 609 base = top[0]; 610 limit = top[1]; 611 } 612 else 613 { 614 break; 615 } 616 } 617 } 618 } 619 620 621 //------------------------------------------------------------------------ 622 template<class Cell> 623 void rasterizer_cells_aa<Cell>::sort_cells() 624 { 625 if(m_sorted) return; //Perform sort only the first time. 626 627 add_curr_cell(); 628 m_curr_cell.x = 0x7FFFFFFF; 629 m_curr_cell.y = 0x7FFFFFFF; 630 m_curr_cell.cover = 0; 631 m_curr_cell.area = 0; 632 633 if(m_num_cells == 0) return; 634 635 // DBG: Check to see if min/max works well. 636 //for(unsigned nc = 0; nc < m_num_cells; nc++) 637 //{ 638 // cell_type* cell = m_cells[nc >> cell_block_shift] + (nc & cell_block_mask); 639 // if(cell->x < m_min_x || 640 // cell->y < m_min_y || 641 // cell->x > m_max_x || 642 // cell->y > m_max_y) 643 // { 644 // cell = cell; // Breakpoint here 645 // } 646 //} 647 648 // Allocate the array of cell pointers 649 m_sorted_cells.allocate(m_num_cells, 16); 650 651 // Allocate and zero the Y array 652 m_sorted_y.allocate(m_max_y - m_min_y + 1, 16); 653 m_sorted_y.zero(); 654 655 // Create the Y-histogram (count the numbers of cells for each Y) 656 cell_type** block_ptr = m_cells; 657 cell_type* cell_ptr; 658 unsigned nb = m_num_cells >> cell_block_shift; 659 unsigned i; 660 while(nb--) 661 { 662 cell_ptr = *block_ptr++; 663 i = cell_block_size; 664 while(i--) 665 { 666 m_sorted_y[cell_ptr->y - m_min_y].start++; 667 ++cell_ptr; 668 } 669 } 670 671 cell_ptr = *block_ptr++; 672 i = m_num_cells & cell_block_mask; 673 while(i--) 674 { 675 m_sorted_y[cell_ptr->y - m_min_y].start++; 676 ++cell_ptr; 677 } 678 679 // Convert the Y-histogram into the array of starting indexes 680 unsigned start = 0; 681 for(i = 0; i < m_sorted_y.size(); i++) 682 { 683 unsigned v = m_sorted_y[i].start; 684 m_sorted_y[i].start = start; 685 start += v; 686 } 687 688 // Fill the cell pointer array sorted by Y 689 block_ptr = m_cells; 690 nb = m_num_cells >> cell_block_shift; 691 while(nb--) 692 { 693 cell_ptr = *block_ptr++; 694 i = cell_block_size; 695 while(i--) 696 { 697 sorted_y& curr_y = m_sorted_y[cell_ptr->y - m_min_y]; 698 m_sorted_cells[curr_y.start + curr_y.num] = cell_ptr; 699 ++curr_y.num; 700 ++cell_ptr; 701 } 702 } 703 704 cell_ptr = *block_ptr++; 705 i = m_num_cells & cell_block_mask; 706 while(i--) 707 { 708 sorted_y& curr_y = m_sorted_y[cell_ptr->y - m_min_y]; 709 m_sorted_cells[curr_y.start + curr_y.num] = cell_ptr; 710 ++curr_y.num; 711 ++cell_ptr; 712 } 713 714 // Finally arrange the X-arrays 715 for(i = 0; i < m_sorted_y.size(); i++) 716 { 717 const sorted_y& curr_y = m_sorted_y[i]; 718 if(curr_y.num) 719 { 720 qsort_cells(m_sorted_cells.data() + curr_y.start, curr_y.num); 721 } 722 } 723 m_sorted = true; 724 } 725 726 727 728 //------------------------------------------------------scanline_hit_test 729 class scanline_hit_test 730 { 731 public: 732 scanline_hit_test(int x) : m_x(x), m_hit(false) {} 733 734 void reset_spans() {} 735 void finalize(int) {} 736 void add_cell(int x, int) 737 { 738 if(m_x == x) m_hit = true; 739 } 740 void add_span(int x, int len, int) 741 { 742 if(m_x >= x && m_x < x+len) m_hit = true; 743 } 744 unsigned num_spans() const { return 1; } 745 bool hit() const { return m_hit; } 746 747 private: 748 int m_x; 749 bool m_hit; 750 }; 751 752 753 } 754 755 #endif 756