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_STORAGE_AA_INCLUDED 17 #define AGG_SCANLINE_STORAGE_AA_INCLUDED 18 19 #include <string.h> 20 #include <stdlib.h> 21 #include <math.h> 22 #include "agg_array.h" 23 #include "agg_render_scanlines.h" 24 25 26 namespace agg 27 { 28 29 //----------------------------------------------scanline_cell_storage 30 template<class T> class scanline_cell_storage 31 { 32 struct extra_span 33 { 34 unsigned len; 35 T* ptr; 36 }; 37 38 public: 39 typedef T value_type; 40 41 //--------------------------------------------------------------- 42 ~scanline_cell_storage() 43 { 44 remove_all(); 45 } 46 47 //--------------------------------------------------------------- 48 scanline_cell_storage() : 49 m_cells(128-2), 50 m_extra_storage() 51 {} 52 53 54 // Copying 55 //--------------------------------------------------------------- 56 scanline_cell_storage(const scanline_cell_storage<T>& v) : 57 m_cells(v.m_cells), 58 m_extra_storage() 59 { 60 copy_extra_storage(v); 61 } 62 63 //--------------------------------------------------------------- 64 const scanline_cell_storage<T>& 65 operator = (const scanline_cell_storage<T>& v) 66 { 67 remove_all(); 68 m_cells = v.m_cells; 69 copy_extra_storage(v); 70 return *this; 71 } 72 73 //--------------------------------------------------------------- 74 void remove_all() 75 { 76 int i; 77 for(i = m_extra_storage.size()-1; i >= 0; --i) 78 { 79 delete [] m_extra_storage[(unsigned)i].ptr; 80 } 81 m_extra_storage.remove_all(); 82 m_cells.remove_all(); 83 } 84 85 //--------------------------------------------------------------- 86 int add_cells(const T* cells, unsigned num_cells) 87 { 88 int idx = m_cells.allocate_continuous_block(num_cells); 89 if(idx >= 0) 90 { 91 T* ptr = &m_cells[idx]; 92 memcpy(ptr, cells, sizeof(T) * num_cells); 93 return idx; 94 } 95 extra_span s; 96 s.len = num_cells; 97 s.ptr = new T [num_cells]; 98 memcpy(s.ptr, cells, sizeof(T) * num_cells); 99 m_extra_storage.add(s); 100 return -int(m_extra_storage.size()); 101 } 102 103 //--------------------------------------------------------------- 104 const T* operator [] (int idx) const 105 { 106 if(idx >= 0) 107 { 108 if((unsigned)idx >= m_cells.size()) return 0; 109 return &m_cells[(unsigned)idx]; 110 } 111 unsigned i = unsigned(-idx - 1); 112 if(i >= m_extra_storage.size()) return 0; 113 return m_extra_storage[i].ptr; 114 } 115 116 //--------------------------------------------------------------- 117 T* operator [] (int idx) 118 { 119 if(idx >= 0) 120 { 121 if((unsigned)idx >= m_cells.size()) return 0; 122 return &m_cells[(unsigned)idx]; 123 } 124 unsigned i = unsigned(-idx - 1); 125 if(i >= m_extra_storage.size()) return 0; 126 return m_extra_storage[i].ptr; 127 } 128 129 private: 130 void copy_extra_storage(const scanline_cell_storage<T>& v) 131 { 132 unsigned i; 133 for(i = 0; i < v.m_extra_storage.size(); ++i) 134 { 135 const extra_span& src = v.m_extra_storage[i]; 136 extra_span dst; 137 dst.len = src.len; 138 dst.ptr = new T [dst.len]; 139 memcpy(dst.ptr, src.ptr, dst.len * sizeof(T)); 140 m_extra_storage.add(dst); 141 } 142 } 143 144 pod_deque<T, 12> m_cells; 145 pod_deque<extra_span, 6> m_extra_storage; 146 }; 147 148 149 150 151 152 153 //-----------------------------------------------scanline_storage_aa 154 template<class T> class scanline_storage_aa 155 { 156 public: 157 typedef T cover_type; 158 159 //--------------------------------------------------------------- 160 struct span_data 161 { 162 int16 x; 163 int16 len; // If negative, it's a solid span, covers is valid 164 int covers_id; // The index of the cells in the scanline_cell_storage 165 }; 166 167 //--------------------------------------------------------------- 168 struct scanline_data 169 { 170 int y; 171 unsigned num_spans; 172 unsigned start_span; 173 }; 174 175 176 //--------------------------------------------------------------- 177 class embedded_scanline 178 { 179 public: 180 181 //----------------------------------------------------------- 182 class const_iterator 183 { 184 public: 185 struct span 186 { 187 int16 x; 188 int16 len; // If negative, it's a solid span, covers is valid 189 const T* covers; 190 }; 191 192 const_iterator(const embedded_scanline& sl) : 193 m_storage(sl.m_storage), 194 m_span_idx(sl.m_scanline.start_span) 195 { 196 init_span(); 197 } 198 199 const span& operator*() const { return m_span; } 200 const span* operator->() const { return &m_span; } 201 202 void operator ++ () 203 { 204 ++m_span_idx; 205 init_span(); 206 } 207 208 private: 209 void init_span() 210 { 211 const span_data& s = m_storage->span_by_index(m_span_idx); 212 m_span.x = s.x; 213 m_span.len = s.len; 214 m_span.covers = m_storage->covers_by_index(s.covers_id); 215 } 216 217 const scanline_storage_aa* m_storage; 218 unsigned m_span_idx; 219 span m_span; 220 }; 221 222 friend class const_iterator; 223 224 225 //----------------------------------------------------------- 226 embedded_scanline(const scanline_storage_aa& storage) : 227 m_storage(&storage) 228 { 229 init(0); 230 } 231 232 //----------------------------------------------------------- 233 void reset(int, int) {} 234 unsigned num_spans() const { return m_scanline.num_spans; } 235 int y() const { return m_scanline.y; } 236 const_iterator begin() const { return const_iterator(*this); } 237 238 //----------------------------------------------------------- 239 void init(unsigned scanline_idx) 240 { 241 m_scanline_idx = scanline_idx; 242 m_scanline = m_storage->scanline_by_index(m_scanline_idx); 243 } 244 245 private: 246 const scanline_storage_aa* m_storage; 247 scanline_data m_scanline; 248 unsigned m_scanline_idx; 249 }; 250 251 252 //--------------------------------------------------------------- 253 scanline_storage_aa() : 254 m_covers(), 255 m_spans(256-2), // Block increment size 256 m_scanlines(), 257 m_min_x( 0x7FFFFFFF), 258 m_min_y( 0x7FFFFFFF), 259 m_max_x(-0x7FFFFFFF), 260 m_max_y(-0x7FFFFFFF), 261 m_cur_scanline(0) 262 { 263 m_fake_scanline.y = 0; 264 m_fake_scanline.num_spans = 0; 265 m_fake_scanline.start_span = 0; 266 m_fake_span.x = 0; 267 m_fake_span.len = 0; 268 m_fake_span.covers_id = 0; 269 } 270 271 // Renderer Interface 272 //--------------------------------------------------------------- 273 void prepare(unsigned) 274 { 275 m_covers.remove_all(); 276 m_scanlines.remove_all(); 277 m_spans.remove_all(); 278 m_min_x = 0x7FFFFFFF; 279 m_min_y = 0x7FFFFFFF; 280 m_max_x = -0x7FFFFFFF; 281 m_max_y = -0x7FFFFFFF; 282 m_cur_scanline = 0; 283 } 284 285 //--------------------------------------------------------------- 286 template<class Scanline> void render(const Scanline& sl) 287 { 288 scanline_data sl_this; 289 290 int y = sl.y(); 291 if(y < m_min_y) m_min_y = y; 292 if(y > m_max_y) m_max_y = y; 293 294 sl_this.y = y; 295 sl_this.num_spans = sl.num_spans(); 296 sl_this.start_span = m_spans.size(); 297 typename Scanline::const_iterator span_iterator = sl.begin(); 298 299 unsigned num_spans = sl_this.num_spans; 300 do 301 { 302 span_data sp; 303 304 sp.x = span_iterator->x; 305 sp.len = span_iterator->len; 306 int len = abs(int(sp.len)); 307 sp.covers_id = 308 m_covers.add_cells(span_iterator->covers, 309 unsigned(len)); 310 m_spans.add(sp); 311 int x1 = sp.x; 312 int x2 = sp.x + len - 1; 313 if(x1 < m_min_x) m_min_x = x1; 314 if(x2 > m_max_x) m_max_x = x2; 315 ++span_iterator; 316 } 317 while(--num_spans); 318 m_scanlines.add(sl_this); 319 } 320 321 322 //--------------------------------------------------------------- 323 // Iterate scanlines interface 324 int min_x() const { return m_min_x; } 325 int min_y() const { return m_min_y; } 326 int max_x() const { return m_max_x; } 327 int max_y() const { return m_max_y; } 328 329 //--------------------------------------------------------------- 330 bool rewind_scanlines() 331 { 332 m_cur_scanline = 0; 333 return m_scanlines.size() > 0; 334 } 335 336 337 //--------------------------------------------------------------- 338 template<class Scanline> bool sweep_scanline(Scanline& sl) 339 { 340 sl.reset_spans(); 341 for(;;) 342 { 343 if(m_cur_scanline >= m_scanlines.size()) return false; 344 const scanline_data& sl_this = m_scanlines[m_cur_scanline]; 345 346 unsigned num_spans = sl_this.num_spans; 347 unsigned span_idx = sl_this.start_span; 348 do 349 { 350 const span_data& sp = m_spans[span_idx++]; 351 const T* covers = covers_by_index(sp.covers_id); 352 if(sp.len < 0) 353 { 354 sl.add_span(sp.x, unsigned(-sp.len), *covers); 355 } 356 else 357 { 358 sl.add_cells(sp.x, sp.len, covers); 359 } 360 } 361 while(--num_spans); 362 ++m_cur_scanline; 363 if(sl.num_spans()) 364 { 365 sl.finalize(sl_this.y); 366 break; 367 } 368 } 369 return true; 370 } 371 372 373 //--------------------------------------------------------------- 374 // Specialization for embedded_scanline 375 bool sweep_scanline(embedded_scanline& sl) 376 { 377 do 378 { 379 if(m_cur_scanline >= m_scanlines.size()) return false; 380 sl.init(m_cur_scanline); 381 ++m_cur_scanline; 382 } 383 while(sl.num_spans() == 0); 384 return true; 385 } 386 387 //--------------------------------------------------------------- 388 unsigned byte_size() const 389 { 390 unsigned i; 391 unsigned size = sizeof(int16) * 4; // min_x, min_y, max_x, max_y 392 393 for(i = 0; i < m_scanlines.size(); ++i) 394 { 395 size += sizeof(int16) * 3; // scanline size in bytes, Y, num_spans 396 397 const scanline_data& sl_this = m_scanlines[i]; 398 399 unsigned num_spans = sl_this.num_spans; 400 unsigned span_idx = sl_this.start_span; 401 do 402 { 403 const span_data& sp = m_spans[span_idx++]; 404 405 size += sizeof(int16) * 2; // X, span_len 406 if(sp.len < 0) 407 { 408 size += sizeof(T); // cover 409 } 410 else 411 { 412 size += sizeof(T) * unsigned(sp.len); // covers 413 } 414 } 415 while(--num_spans); 416 } 417 return size; 418 } 419 420 421 //--------------------------------------------------------------- 422 static void write_int16(int8u* dst, int16 val) 423 { 424 dst[0] = ((const int8u*)&val)[0]; 425 dst[1] = ((const int8u*)&val)[1]; 426 } 427 428 429 //--------------------------------------------------------------- 430 void serialize(int8u* data) const 431 { 432 unsigned i; 433 434 write_int16(data, int16u(min_x())); // min_x 435 data += sizeof(int16u); 436 write_int16(data, int16u(min_y())); // min_y 437 data += sizeof(int16u); 438 write_int16(data, int16u(max_x())); // max_x 439 data += sizeof(int16u); 440 write_int16(data, int16u(max_y())); // max_y 441 data += sizeof(int16u); 442 443 for(i = 0; i < m_scanlines.size(); ++i) 444 { 445 const scanline_data& sl_this = m_scanlines[i]; 446 447 int8u* size_ptr = data; 448 data += sizeof(int16); // Reserve space for scanline size in bytes 449 450 write_int16(data, int16(sl_this.y)); // Y 451 data += sizeof(int16); 452 453 write_int16(data, int16(sl_this.num_spans)); // num_spans 454 data += sizeof(int16); 455 456 unsigned num_spans = sl_this.num_spans; 457 unsigned span_idx = sl_this.start_span; 458 do 459 { 460 const span_data& sp = m_spans[span_idx++]; 461 const T* covers = covers_by_index(sp.covers_id); 462 463 write_int16(data, int16(sp.x)); // X 464 data += sizeof(int16); 465 466 write_int16(data, int16(sp.len)); // span_len 467 data += sizeof(int16); 468 469 if(sp.len < 0) 470 { 471 memcpy(data, covers, sizeof(T)); 472 data += sizeof(T); 473 } 474 else 475 { 476 memcpy(data, covers, unsigned(sp.len) * sizeof(T)); 477 data += sizeof(T) * unsigned(sp.len); 478 } 479 } 480 while(--num_spans); 481 write_int16(size_ptr, int16(unsigned(data - size_ptr))); 482 } 483 } 484 485 486 //--------------------------------------------------------------- 487 const scanline_data& scanline_by_index(unsigned i) const 488 { 489 return (i < m_scanlines.size()) ? m_scanlines[i] : m_fake_scanline; 490 } 491 492 //--------------------------------------------------------------- 493 const span_data& span_by_index(unsigned i) const 494 { 495 return (i < m_spans.size()) ? m_spans[i] : m_fake_span; 496 } 497 498 //--------------------------------------------------------------- 499 const T* covers_by_index(int i) const 500 { 501 return m_covers[i]; 502 } 503 504 private: 505 scanline_cell_storage<T> m_covers; 506 pod_deque<span_data, 10> m_spans; 507 pod_deque<scanline_data, 8> m_scanlines; 508 span_data m_fake_span; 509 scanline_data m_fake_scanline; 510 int m_min_x; 511 int m_min_y; 512 int m_max_x; 513 int m_max_y; 514 unsigned m_cur_scanline; 515 }; 516 517 518 typedef scanline_storage_aa<int8u> scanline_storage_aa8; //--------scanline_storage_aa8 519 typedef scanline_storage_aa<int16u> scanline_storage_aa16; //--------scanline_storage_aa16 520 typedef scanline_storage_aa<int32u> scanline_storage_aa32; //--------scanline_storage_aa32 521 522 523 524 525 //------------------------------------------serialized_scanlines_adaptor_aa 526 template<class T> class serialized_scanlines_adaptor_aa 527 { 528 public: 529 typedef T cover_type; 530 531 //--------------------------------------------------------------------- 532 class embedded_scanline 533 { 534 public: 535 typedef T cover_type; 536 537 //----------------------------------------------------------------- 538 class const_iterator 539 { 540 public: 541 struct span 542 { 543 int16 x; 544 int16 len; // If negative, it's a solid span, "covers" is valid 545 const T* covers; 546 }; 547 548 const_iterator(const embedded_scanline& sl) : 549 m_ptr(sl.m_ptr), 550 m_dx(sl.m_dx) 551 { 552 init_span(); 553 } 554 555 const span& operator*() const { return m_span; } 556 const span* operator->() const { return &m_span; } 557 558 void operator ++ () 559 { 560 if(m_span.len < 0) 561 { 562 m_ptr += sizeof(T); 563 } 564 else 565 { 566 m_ptr += m_span.len * sizeof(T); 567 } 568 init_span(); 569 } 570 571 private: 572 int read_int16() 573 { 574 int16 val; 575 ((int8u*)&val)[0] = *m_ptr++; 576 ((int8u*)&val)[1] = *m_ptr++; 577 return val; 578 } 579 580 void init_span() 581 { 582 m_span.x = read_int16() + m_dx; 583 m_span.len = read_int16(); 584 m_span.covers = m_ptr; 585 } 586 587 const int8u* m_ptr; 588 span m_span; 589 int m_dx; 590 }; 591 592 friend class const_iterator; 593 594 595 //----------------------------------------------------------------- 596 embedded_scanline() : m_ptr(0), m_y(0), m_num_spans(0) {} 597 598 //----------------------------------------------------------------- 599 void reset(int, int) {} 600 unsigned num_spans() const { return m_num_spans; } 601 int y() const { return m_y; } 602 const_iterator begin() const { return const_iterator(*this); } 603 604 605 private: 606 //----------------------------------------------------------------- 607 int read_int16() 608 { 609 int16 val; 610 ((int8u*)&val)[0] = *m_ptr++; 611 ((int8u*)&val)[1] = *m_ptr++; 612 return val; 613 } 614 615 public: 616 //----------------------------------------------------------------- 617 void init(const int8u* ptr, int dx, int dy) 618 { 619 m_ptr = ptr; 620 m_y = read_int16() + dy; 621 m_num_spans = unsigned(read_int16()); 622 m_dx = dx; 623 } 624 625 private: 626 const int8u* m_ptr; 627 int m_y; 628 unsigned m_num_spans; 629 int m_dx; 630 }; 631 632 633 634 public: 635 //-------------------------------------------------------------------- 636 serialized_scanlines_adaptor_aa() : 637 m_data(0), 638 m_end(0), 639 m_ptr(0), 640 m_dx(0), 641 m_dy(0), 642 m_min_x(0x7FFFFFFF), 643 m_min_y(0x7FFFFFFF), 644 m_max_x(-0x7FFFFFFF), 645 m_max_y(-0x7FFFFFFF) 646 {} 647 648 //-------------------------------------------------------------------- 649 serialized_scanlines_adaptor_aa(const int8u* data, unsigned size, 650 double dx, double dy) : 651 m_data(data), 652 m_end(data + size), 653 m_ptr(data), 654 m_dx(int(floor(dx + 0.5))), 655 m_dy(int(floor(dy + 0.5))), 656 m_min_x(0x7FFFFFFF), 657 m_min_y(0x7FFFFFFF), 658 m_max_x(-0x7FFFFFFF), 659 m_max_y(-0x7FFFFFFF) 660 {} 661 662 //-------------------------------------------------------------------- 663 void init(const int8u* data, unsigned size, double dx, double dy) 664 { 665 m_data = data; 666 m_end = data + size; 667 m_ptr = data; 668 m_dx = int(floor(dx + 0.5)); 669 m_dy = int(floor(dy + 0.5)); 670 m_min_x = 0x7FFFFFFF; 671 m_min_y = 0x7FFFFFFF; 672 m_max_x = -0x7FFFFFFF; 673 m_max_y = -0x7FFFFFFF; 674 } 675 676 private: 677 //-------------------------------------------------------------------- 678 int read_int16() 679 { 680 int16 val; 681 ((int8u*)&val)[0] = *m_ptr++; 682 ((int8u*)&val)[1] = *m_ptr++; 683 return val; 684 } 685 686 //-------------------------------------------------------------------- 687 unsigned read_int16u() 688 { 689 int16u val; 690 ((int8u*)&val)[0] = *m_ptr++; 691 ((int8u*)&val)[1] = *m_ptr++; 692 return val; 693 } 694 695 public: 696 // Iterate scanlines interface 697 //-------------------------------------------------------------------- 698 bool rewind_scanlines() 699 { 700 m_ptr = m_data; 701 if(m_ptr < m_end) 702 { 703 m_min_x = read_int16() + m_dx; 704 m_min_y = read_int16() + m_dy; 705 m_max_x = read_int16() + m_dx; 706 m_max_y = read_int16() + m_dy; 707 return true; 708 } 709 return false; 710 } 711 712 //-------------------------------------------------------------------- 713 int min_x() const { return m_min_x; } 714 int min_y() const { return m_min_y; } 715 int max_x() const { return m_max_x; } 716 int max_y() const { return m_max_y; } 717 718 //-------------------------------------------------------------------- 719 template<class Scanline> bool sweep_scanline(Scanline& sl) 720 { 721 sl.reset_spans(); 722 for(;;) 723 { 724 if(m_ptr >= m_end) return false; 725 726 read_int16(); // Skip scanline size in bytes 727 int y = read_int16() + m_dy; 728 unsigned num_spans = read_int16(); 729 730 do 731 { 732 int x = read_int16() + m_dx; 733 int len = read_int16(); 734 735 if(len < 0) 736 { 737 sl.add_span(x, unsigned(-len), *m_ptr); 738 m_ptr += sizeof(T); 739 } 740 else 741 { 742 sl.add_cells(x, len, m_ptr); 743 m_ptr += len * sizeof(T); 744 } 745 } 746 while(--num_spans); 747 748 if(sl.num_spans()) 749 { 750 sl.finalize(y); 751 break; 752 } 753 } 754 return true; 755 } 756 757 758 //-------------------------------------------------------------------- 759 // Specialization for embedded_scanline 760 bool sweep_scanline(embedded_scanline& sl) 761 { 762 do 763 { 764 if(m_ptr >= m_end) return false; 765 766 unsigned byte_size = read_int16u(); 767 sl.init(m_ptr, m_dx, m_dy); 768 m_ptr += byte_size - sizeof(int16); 769 } 770 while(sl.num_spans() == 0); 771 return true; 772 } 773 774 private: 775 const int8u* m_data; 776 const int8u* m_end; 777 const int8u* m_ptr; 778 int m_dx; 779 int m_dy; 780 int m_min_x; 781 int m_min_y; 782 int m_max_x; 783 int m_max_y; 784 }; 785 786 787 788 typedef serialized_scanlines_adaptor_aa<int8u> serialized_scanlines_adaptor_aa8; //----serialized_scanlines_adaptor_aa8 789 typedef serialized_scanlines_adaptor_aa<int16u> serialized_scanlines_adaptor_aa16; //----serialized_scanlines_adaptor_aa16 790 typedef serialized_scanlines_adaptor_aa<int32u> serialized_scanlines_adaptor_aa32; //----serialized_scanlines_adaptor_aa32 791 792 } 793 794 795 #endif 796 797