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