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_BIN_INCLUDED 17 #define AGG_SCANLINE_STORAGE_BIN_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_storage_bin 30 class scanline_storage_bin 31 { 32 public: 33 //--------------------------------------------------------------- 34 struct span_data 35 { 36 int16 x; 37 int16 len; 38 }; 39 40 //--------------------------------------------------------------- 41 struct scanline_data 42 { 43 int y; 44 unsigned num_spans; 45 unsigned start_span; 46 }; 47 48 49 //--------------------------------------------------------------- 50 class embedded_scanline 51 { 52 public: 53 54 //----------------------------------------------------------- 55 class const_iterator 56 { 57 public: 58 const_iterator(const embedded_scanline& sl) : 59 m_storage(sl.m_storage), 60 m_span_idx(sl.m_scanline.start_span) 61 { 62 m_span = m_storage->span_by_index(m_span_idx); 63 } 64 65 const span_data& operator*() const { return m_span; } 66 const span_data* operator->() const { return &m_span; } 67 68 void operator ++ () 69 { 70 ++m_span_idx; 71 m_span = m_storage->span_by_index(m_span_idx); 72 } 73 74 private: 75 const scanline_storage_bin* m_storage; 76 unsigned m_span_idx; 77 span_data m_span; 78 }; 79 80 friend class const_iterator; 81 82 83 //----------------------------------------------------------- 84 embedded_scanline(const scanline_storage_bin& storage) : 85 m_storage(&storage) 86 { 87 setup(0); 88 } 89 90 //----------------------------------------------------------- 91 void reset(int, int) {} 92 unsigned num_spans() const { return m_scanline.num_spans; } 93 int y() const { return m_scanline.y; } 94 const_iterator begin() const { return const_iterator(*this); } 95 96 //----------------------------------------------------------- 97 void setup(unsigned scanline_idx) 98 { 99 m_scanline_idx = scanline_idx; 100 m_scanline = m_storage->scanline_by_index(m_scanline_idx); 101 } 102 103 private: 104 const scanline_storage_bin* m_storage; 105 scanline_data m_scanline; 106 unsigned m_scanline_idx; 107 }; 108 109 110 //--------------------------------------------------------------- 111 scanline_storage_bin() : 112 m_spans(256-2), // Block increment size 113 m_scanlines(), 114 m_min_x( 0x7FFFFFFF), 115 m_min_y( 0x7FFFFFFF), 116 m_max_x(-0x7FFFFFFF), 117 m_max_y(-0x7FFFFFFF), 118 m_cur_scanline(0) 119 { 120 m_fake_scanline.y = 0; 121 m_fake_scanline.num_spans = 0; 122 m_fake_scanline.start_span = 0; 123 m_fake_span.x = 0; 124 m_fake_span.len = 0; 125 } 126 127 // Renderer Interface 128 //--------------------------------------------------------------- 129 void prepare(unsigned) 130 { 131 m_scanlines.remove_all(); 132 m_spans.remove_all(); 133 m_min_x = 0x7FFFFFFF; 134 m_min_y = 0x7FFFFFFF; 135 m_max_x = -0x7FFFFFFF; 136 m_max_y = -0x7FFFFFFF; 137 m_cur_scanline = 0; 138 } 139 140 //--------------------------------------------------------------- 141 template<class Scanline> void render(const Scanline& sl) 142 { 143 scanline_data sl_this; 144 145 int y = sl.y(); 146 if(y < m_min_y) m_min_y = y; 147 if(y > m_max_y) m_max_y = y; 148 149 sl_this.y = y; 150 sl_this.num_spans = sl.num_spans(); 151 sl_this.start_span = m_spans.size(); 152 typename Scanline::const_iterator span_iterator = sl.begin(); 153 154 unsigned num_spans = sl_this.num_spans; 155 do 156 { 157 span_data sp; 158 sp.x = span_iterator->x; 159 sp.len = (int16)abs((int)(span_iterator->len)); 160 m_spans.add(sp); 161 int x1 = sp.x; 162 int x2 = sp.x + sp.len - 1; 163 if(x1 < m_min_x) m_min_x = x1; 164 if(x2 > m_max_x) m_max_x = x2; 165 ++span_iterator; 166 } 167 while(--num_spans); 168 m_scanlines.add(sl_this); 169 } 170 171 172 //--------------------------------------------------------------- 173 // Iterate scanlines interface 174 int min_x() const { return m_min_x; } 175 int min_y() const { return m_min_y; } 176 int max_x() const { return m_max_x; } 177 int max_y() const { return m_max_y; } 178 179 //--------------------------------------------------------------- 180 bool rewind_scanlines() 181 { 182 m_cur_scanline = 0; 183 return m_scanlines.size() > 0; 184 } 185 186 187 //--------------------------------------------------------------- 188 template<class Scanline> bool sweep_scanline(Scanline& sl) 189 { 190 sl.reset_spans(); 191 for(;;) 192 { 193 if(m_cur_scanline >= m_scanlines.size()) return false; 194 const scanline_data& sl_this = m_scanlines[m_cur_scanline]; 195 196 unsigned num_spans = sl_this.num_spans; 197 unsigned span_idx = sl_this.start_span; 198 do 199 { 200 const span_data& sp = m_spans[span_idx++]; 201 sl.add_span(sp.x, sp.len, cover_full); 202 } 203 while(--num_spans); 204 205 ++m_cur_scanline; 206 if(sl.num_spans()) 207 { 208 sl.finalize(sl_this.y); 209 break; 210 } 211 } 212 return true; 213 } 214 215 216 //--------------------------------------------------------------- 217 // Specialization for embedded_scanline 218 bool sweep_scanline(embedded_scanline& sl) 219 { 220 do 221 { 222 if(m_cur_scanline >= m_scanlines.size()) return false; 223 sl.setup(m_cur_scanline); 224 ++m_cur_scanline; 225 } 226 while(sl.num_spans() == 0); 227 return true; 228 } 229 230 231 //--------------------------------------------------------------- 232 unsigned byte_size() const 233 { 234 unsigned i; 235 unsigned size = sizeof(int16) * 4; // min_x, min_y, max_x, max_y 236 237 for(i = 0; i < m_scanlines.size(); ++i) 238 { 239 size += sizeof(int16) * 2; // Y, num_spans 240 241 const scanline_data& sl_this = m_scanlines[i]; 242 243 unsigned num_spans = sl_this.num_spans; 244 unsigned span_idx = sl_this.start_span; 245 do 246 { 247 const span_data& sp = m_spans[span_idx++]; 248 size += sizeof(int16) * 2; // X, span_len 249 } 250 while(--num_spans); 251 } 252 return size; 253 } 254 255 256 //--------------------------------------------------------------- 257 static void write_int16(int8u* dst, int16 val) 258 { 259 dst[0] = ((const int8u*)&val)[0]; 260 dst[1] = ((const int8u*)&val)[1]; 261 } 262 263 264 //--------------------------------------------------------------- 265 void serialize(int8u* data) const 266 { 267 unsigned i; 268 269 write_int16(data, int16u(min_x())); // min_x 270 data += sizeof(int16u); 271 write_int16(data, int16u(min_y())); // min_y 272 data += sizeof(int16u); 273 write_int16(data, int16u(max_x())); // max_x 274 data += sizeof(int16u); 275 write_int16(data, int16u(max_y())); // max_y 276 data += sizeof(int16u); 277 278 for(i = 0; i < m_scanlines.size(); ++i) 279 { 280 const scanline_data& sl_this = m_scanlines[i]; 281 282 write_int16(data, int16(sl_this.y)); // Y 283 data += sizeof(int16); 284 285 write_int16(data, int16(sl_this.num_spans)); // num_spans 286 data += sizeof(int16); 287 288 unsigned num_spans = sl_this.num_spans; 289 unsigned span_idx = sl_this.start_span; 290 do 291 { 292 const span_data& sp = m_spans[span_idx++]; 293 294 write_int16(data, int16(sp.x)); // X 295 data += sizeof(int16); 296 297 write_int16(data, int16(sp.len)); // len 298 data += sizeof(int16); 299 } 300 while(--num_spans); 301 } 302 } 303 304 305 //--------------------------------------------------------------- 306 const scanline_data& scanline_by_index(unsigned i) const 307 { 308 return (i < m_scanlines.size()) ? m_scanlines[i] : m_fake_scanline; 309 } 310 311 //--------------------------------------------------------------- 312 const span_data& span_by_index(unsigned i) const 313 { 314 return (i < m_spans.size()) ? m_spans[i] : m_fake_span; 315 } 316 317 318 private: 319 pod_deque<span_data, 10> m_spans; 320 pod_deque<scanline_data, 8> m_scanlines; 321 span_data m_fake_span; 322 scanline_data m_fake_scanline; 323 int m_min_x; 324 int m_min_y; 325 int m_max_x; 326 int m_max_y; 327 unsigned m_cur_scanline; 328 }; 329 330 331 332 333 334 335 336 337 338 339 340 341 342 //---------------------------------------serialized_scanlines_adaptor_bin 343 class serialized_scanlines_adaptor_bin 344 { 345 public: 346 typedef bool cover_type; 347 348 //-------------------------------------------------------------------- 349 class embedded_scanline 350 { 351 public: 352 353 //---------------------------------------------------------------- 354 class const_iterator 355 { 356 public: 357 struct span 358 { 359 int16 x; 360 int16 len; 361 }; 362 363 const_iterator(const embedded_scanline& sl) : 364 m_ptr(sl.m_ptr), 365 m_dx(sl.m_dx) 366 { 367 m_span.x = read_int16() + m_dx; 368 m_span.len = read_int16(); 369 } 370 371 const span& operator*() const { return m_span; } 372 const span* operator->() const { return &m_span; } 373 374 void operator ++ () 375 { 376 m_span.x = read_int16() + m_dx; 377 m_span.len = read_int16(); 378 } 379 380 private: 381 int read_int16() 382 { 383 int16 val; 384 ((int8u*)&val)[0] = *m_ptr++; 385 ((int8u*)&val)[1] = *m_ptr++; 386 return val; 387 } 388 389 const int8u* m_ptr; 390 span m_span; 391 int m_dx; 392 }; 393 394 friend class const_iterator; 395 396 397 //---------------------------------------------------------------- 398 embedded_scanline() : m_ptr(0), m_y(0), m_num_spans(0) {} 399 400 //---------------------------------------------------------------- 401 void reset(int, int) {} 402 unsigned num_spans() const { return m_num_spans; } 403 int y() const { return m_y; } 404 const_iterator begin() const { return const_iterator(*this); } 405 406 407 private: 408 //---------------------------------------------------------------- 409 int read_int16() 410 { 411 int16 val; 412 ((int8u*)&val)[0] = *m_ptr++; 413 ((int8u*)&val)[1] = *m_ptr++; 414 return val; 415 } 416 417 public: 418 //---------------------------------------------------------------- 419 void init(const int8u* ptr, int dx, int dy) 420 { 421 m_ptr = ptr; 422 m_y = read_int16() + dy; 423 m_num_spans = unsigned(read_int16()); 424 m_dx = dx; 425 } 426 427 private: 428 const int8u* m_ptr; 429 int m_y; 430 unsigned m_num_spans; 431 int m_dx; 432 }; 433 434 435 436 public: 437 //-------------------------------------------------------------------- 438 serialized_scanlines_adaptor_bin() : 439 m_data(0), 440 m_end(0), 441 m_ptr(0), 442 m_dx(0), 443 m_dy(0), 444 m_min_x(0x7FFFFFFF), 445 m_min_y(0x7FFFFFFF), 446 m_max_x(-0x7FFFFFFF), 447 m_max_y(-0x7FFFFFFF) 448 {} 449 450 //-------------------------------------------------------------------- 451 serialized_scanlines_adaptor_bin(const int8u* data, unsigned size, 452 double dx, double dy) : 453 m_data(data), 454 m_end(data + size), 455 m_ptr(data), 456 m_dx(int(floor(dx + 0.5))), 457 m_dy(int(floor(dy + 0.5))), 458 m_min_x(0x7FFFFFFF), 459 m_min_y(0x7FFFFFFF), 460 m_max_x(-0x7FFFFFFF), 461 m_max_y(-0x7FFFFFFF) 462 {} 463 464 //-------------------------------------------------------------------- 465 void init(const int8u* data, unsigned size, double dx, double dy) 466 { 467 m_data = data; 468 m_end = data + size; 469 m_ptr = data; 470 m_dx = int(floor(dx + 0.5)); 471 m_dy = int(floor(dy + 0.5)); 472 m_min_x = 0x7FFFFFFF; 473 m_min_y = 0x7FFFFFFF; 474 m_max_x = -0x7FFFFFFF; 475 m_max_y = -0x7FFFFFFF; 476 } 477 478 private: 479 //-------------------------------------------------------------------- 480 int read_int16() 481 { 482 int16 val; 483 ((int8u*)&val)[0] = *m_ptr++; 484 ((int8u*)&val)[1] = *m_ptr++; 485 return val; 486 } 487 488 public: 489 // Iterate scanlines interface 490 //-------------------------------------------------------------------- 491 bool rewind_scanlines() 492 { 493 m_ptr = m_data; 494 if(m_ptr < m_end) 495 { 496 m_min_x = read_int16() + m_dx; 497 m_min_y = read_int16() + m_dy; 498 m_max_x = read_int16() + m_dx; 499 m_max_y = read_int16() + m_dy; 500 return true; 501 } 502 return false; 503 } 504 505 //-------------------------------------------------------------------- 506 int min_x() const { return m_min_x; } 507 int min_y() const { return m_min_y; } 508 int max_x() const { return m_max_x; } 509 int max_y() const { return m_max_y; } 510 511 //-------------------------------------------------------------------- 512 template<class Scanline> bool sweep_scanline(Scanline& sl) 513 { 514 sl.reset_spans(); 515 for(;;) 516 { 517 if(m_ptr >= m_end) return false; 518 519 int y = read_int16() + m_dy; 520 unsigned num_spans = read_int16(); 521 522 do 523 { 524 int x = read_int16() + m_dx; 525 int len = read_int16(); 526 527 if(len < 0) len = -len; 528 sl.add_span(x, unsigned(len), cover_full); 529 } 530 while(--num_spans); 531 532 if(sl.num_spans()) 533 { 534 sl.finalize(y); 535 break; 536 } 537 } 538 return true; 539 } 540 541 542 //-------------------------------------------------------------------- 543 // Specialization for embedded_scanline 544 bool sweep_scanline(embedded_scanline& sl) 545 { 546 do 547 { 548 if(m_ptr >= m_end) return false; 549 550 sl.init(m_ptr, m_dx, m_dy); 551 552 // Jump to the next scanline 553 //-------------------------- 554 read_int16(); // Y 555 int num_spans = read_int16(); // num_spans 556 m_ptr += num_spans * sizeof(int16) * 2; 557 } 558 while(sl.num_spans() == 0); 559 return true; 560 } 561 562 private: 563 const int8u* m_data; 564 const int8u* m_end; 565 const int8u* m_ptr; 566 int m_dx; 567 int m_dy; 568 int m_min_x; 569 int m_min_y; 570 int m_max_x; 571 int m_max_y; 572 }; 573 574 575 576 } 577 578 #endif 579 580