Anti-Grain Geometry - AGG (libagg)
2.5
|
00001 //---------------------------------------------------------------------------- 00002 // Anti-Grain Geometry - Version 2.3 00003 // Copyright (C) 2002-2005 Maxim Shemanarev (http://www.antigrain.com) 00004 // 00005 // Permission to copy, use, modify, sell and distribute this software 00006 // is granted provided this copyright notice appears in all copies. 00007 // This software is provided "as is" without express or implied 00008 // warranty, and with no claim as to its suitability for any purpose. 00009 // 00010 //---------------------------------------------------------------------------- 00011 // 00012 // The author gratefully acknowleges the support of David Turner, 00013 // Robert Wilhelm, and Werner Lemberg - the authors of the FreeType 00014 // libray - in producing this work. See http://www.freetype.org for details. 00015 // 00016 //---------------------------------------------------------------------------- 00017 // Contact: mcseem@antigrain.com 00018 // mcseemagg@yahoo.com 00019 // http://www.antigrain.com 00020 //---------------------------------------------------------------------------- 00021 // 00022 // Adaptation for 32-bit screen coordinates has been sponsored by 00023 // Liberty Technology Systems, Inc., visit http://lib-sys.com 00024 // 00025 // Liberty Technology Systems, Inc. is the provider of 00026 // PostScript and PDF technology for software developers. 00027 // 00028 //---------------------------------------------------------------------------- 00029 #ifndef AGG_RASTERIZER_COMPOUND_AA_INCLUDED 00030 #define AGG_RASTERIZER_COMPOUND_AA_INCLUDED 00031 00032 #include "agg_rasterizer_cells_aa.h" 00033 #include "agg_rasterizer_sl_clip.h" 00034 00035 namespace agg 00036 { 00037 00038 //-----------------------------------------------------------cell_style_aa 00039 // A pixel cell. There're no constructors defined and it was done 00040 // intentionally in order to avoid extra overhead when allocating an 00041 // array of cells. 00042 struct cell_style_aa 00043 { 00044 int x; 00045 int y; 00046 int cover; 00047 int area; 00048 int16 left, right; 00049 00050 void initial() 00051 { 00052 x = 0x7FFFFFFF; 00053 y = 0x7FFFFFFF; 00054 cover = 0; 00055 area = 0; 00056 left = -1; 00057 right = -1; 00058 } 00059 00060 void style(const cell_style_aa& c) 00061 { 00062 left = c.left; 00063 right = c.right; 00064 } 00065 00066 int not_equal(int ex, int ey, const cell_style_aa& c) const 00067 { 00068 return (ex - x) | (ey - y) | (left - c.left) | (right - c.right); 00069 } 00070 }; 00071 00072 00073 //===========================================================layer_order_e 00074 enum layer_order_e 00075 { 00076 layer_unsorted, //------layer_unsorted 00077 layer_direct, //------layer_direct 00078 layer_inverse //------layer_inverse 00079 }; 00080 00081 00082 //==================================================rasterizer_compound_aa 00083 template<class Clip=rasterizer_sl_clip_int> class rasterizer_compound_aa 00084 { 00085 struct style_info 00086 { 00087 unsigned start_cell; 00088 unsigned num_cells; 00089 int last_x; 00090 }; 00091 00092 struct cell_info 00093 { 00094 int x, area, cover; 00095 }; 00096 00097 public: 00098 typedef Clip clip_type; 00099 typedef typename Clip::conv_type conv_type; 00100 typedef typename Clip::coord_type coord_type; 00101 00102 enum aa_scale_e 00103 { 00104 aa_shift = 8, 00105 aa_scale = 1 << aa_shift, 00106 aa_mask = aa_scale - 1, 00107 aa_scale2 = aa_scale * 2, 00108 aa_mask2 = aa_scale2 - 1 00109 }; 00110 00111 //-------------------------------------------------------------------- 00112 rasterizer_compound_aa() : 00113 m_outline(), 00114 m_clipper(), 00115 m_filling_rule(fill_non_zero), 00116 m_layer_order(layer_direct), 00117 m_styles(), // Active Styles 00118 m_ast(), // Active Style Table (unique values) 00119 m_asm(), // Active Style Mask 00120 m_cells(), 00121 m_cover_buf(), 00122 m_master_alpha(), 00123 m_min_style(0x7FFFFFFF), 00124 m_max_style(-0x7FFFFFFF), 00125 m_start_x(0), 00126 m_start_y(0), 00127 m_scan_y(0x7FFFFFFF), 00128 m_sl_start(0), 00129 m_sl_len(0) 00130 {} 00131 00132 //-------------------------------------------------------------------- 00133 void reset(); 00134 void reset_clipping(); 00135 void clip_box(double x1, double y1, double x2, double y2); 00136 void filling_rule(filling_rule_e filling_rule); 00137 void layer_order(layer_order_e order); 00138 void master_alpha(int style, double alpha); 00139 00140 //-------------------------------------------------------------------- 00141 void styles(int left, int right); 00142 void move_to(int x, int y); 00143 void line_to(int x, int y); 00144 void move_to_d(double x, double y); 00145 void line_to_d(double x, double y); 00146 void add_vertex(double x, double y, unsigned cmd); 00147 00148 void edge(int x1, int y1, int x2, int y2); 00149 void edge_d(double x1, double y1, double x2, double y2); 00150 00151 //------------------------------------------------------------------- 00152 template<class VertexSource> 00153 void add_path(VertexSource& vs, unsigned path_id=0) 00154 { 00155 double x; 00156 double y; 00157 00158 unsigned cmd; 00159 vs.rewind(path_id); 00160 if(m_outline.sorted()) reset(); 00161 while(!is_stop(cmd = vs.vertex(&x, &y))) 00162 { 00163 add_vertex(x, y, cmd); 00164 } 00165 } 00166 00167 00168 //-------------------------------------------------------------------- 00169 int min_x() const { return m_outline.min_x(); } 00170 int min_y() const { return m_outline.min_y(); } 00171 int max_x() const { return m_outline.max_x(); } 00172 int max_y() const { return m_outline.max_y(); } 00173 int min_style() const { return m_min_style; } 00174 int max_style() const { return m_max_style; } 00175 00176 //-------------------------------------------------------------------- 00177 void sort(); 00178 bool rewind_scanlines(); 00179 unsigned sweep_styles(); 00180 int scanline_start() const { return m_sl_start; } 00181 unsigned scanline_length() const { return m_sl_len; } 00182 unsigned style(unsigned style_idx) const; 00183 00184 cover_type* allocate_cover_buffer(unsigned len); 00185 00186 //-------------------------------------------------------------------- 00187 bool navigate_scanline(int y); 00188 bool hit_test(int tx, int ty); 00189 00190 //-------------------------------------------------------------------- 00191 AGG_INLINE unsigned calculate_alpha(int area, unsigned master_alpha) const 00192 { 00193 int cover = area >> (poly_subpixel_shift*2 + 1 - aa_shift); 00194 if(cover < 0) cover = -cover; 00195 if(m_filling_rule == fill_even_odd) 00196 { 00197 cover &= aa_mask2; 00198 if(cover > aa_scale) 00199 { 00200 cover = aa_scale2 - cover; 00201 } 00202 } 00203 if(cover > aa_mask) cover = aa_mask; 00204 return (cover * master_alpha + aa_mask) >> aa_shift; 00205 } 00206 00207 //-------------------------------------------------------------------- 00208 // Sweeps one scanline with one style index. The style ID can be 00209 // determined by calling style(). 00210 template<class Scanline> bool sweep_scanline(Scanline& sl, int style_idx) 00211 { 00212 int scan_y = m_scan_y - 1; 00213 if(scan_y > m_outline.max_y()) return false; 00214 00215 sl.reset_spans(); 00216 00217 unsigned master_alpha = aa_mask; 00218 00219 if(style_idx < 0) 00220 { 00221 style_idx = 0; 00222 } 00223 else 00224 { 00225 style_idx++; 00226 master_alpha = m_master_alpha[m_ast[style_idx] + m_min_style - 1]; 00227 } 00228 00229 const style_info& st = m_styles[m_ast[style_idx]]; 00230 00231 unsigned num_cells = st.num_cells; 00232 cell_info* cell = &m_cells[st.start_cell]; 00233 00234 int cover = 0; 00235 while(num_cells--) 00236 { 00237 unsigned alpha; 00238 int x = cell->x; 00239 int area = cell->area; 00240 00241 cover += cell->cover; 00242 00243 ++cell; 00244 00245 if(area) 00246 { 00247 alpha = calculate_alpha((cover << (poly_subpixel_shift + 1)) - area, 00248 master_alpha); 00249 sl.add_cell(x, alpha); 00250 x++; 00251 } 00252 00253 if(num_cells && cell->x > x) 00254 { 00255 alpha = calculate_alpha(cover << (poly_subpixel_shift + 1), 00256 master_alpha); 00257 if(alpha) 00258 { 00259 sl.add_span(x, cell->x - x, alpha); 00260 } 00261 } 00262 } 00263 00264 if(sl.num_spans() == 0) return false; 00265 sl.finalize(scan_y); 00266 return true; 00267 } 00268 00269 private: 00270 void add_style(int style_id); 00271 void allocate_master_alpha(); 00272 00273 //-------------------------------------------------------------------- 00274 // Disable copying 00275 rasterizer_compound_aa(const rasterizer_compound_aa<Clip>&); 00276 const rasterizer_compound_aa<Clip>& 00277 operator = (const rasterizer_compound_aa<Clip>&); 00278 00279 private: 00280 rasterizer_cells_aa<cell_style_aa> m_outline; 00281 clip_type m_clipper; 00282 filling_rule_e m_filling_rule; 00283 layer_order_e m_layer_order; 00284 pod_vector<style_info> m_styles; // Active Styles 00285 pod_vector<unsigned> m_ast; // Active Style Table (unique values) 00286 pod_vector<int8u> m_asm; // Active Style Mask 00287 pod_vector<cell_info> m_cells; 00288 pod_vector<cover_type> m_cover_buf; 00289 pod_bvector<unsigned> m_master_alpha; 00290 00291 int m_min_style; 00292 int m_max_style; 00293 coord_type m_start_x; 00294 coord_type m_start_y; 00295 int m_scan_y; 00296 int m_sl_start; 00297 unsigned m_sl_len; 00298 }; 00299 00300 00301 00302 00303 00304 00305 00306 00307 00308 00309 //------------------------------------------------------------------------ 00310 template<class Clip> 00311 void rasterizer_compound_aa<Clip>::reset() 00312 { 00313 m_outline.reset(); 00314 m_min_style = 0x7FFFFFFF; 00315 m_max_style = -0x7FFFFFFF; 00316 m_scan_y = 0x7FFFFFFF; 00317 m_sl_start = 0; 00318 m_sl_len = 0; 00319 } 00320 00321 //------------------------------------------------------------------------ 00322 template<class Clip> 00323 void rasterizer_compound_aa<Clip>::filling_rule(filling_rule_e filling_rule) 00324 { 00325 m_filling_rule = filling_rule; 00326 } 00327 00328 //------------------------------------------------------------------------ 00329 template<class Clip> 00330 void rasterizer_compound_aa<Clip>::layer_order(layer_order_e order) 00331 { 00332 m_layer_order = order; 00333 } 00334 00335 //------------------------------------------------------------------------ 00336 template<class Clip> 00337 void rasterizer_compound_aa<Clip>::clip_box(double x1, double y1, 00338 double x2, double y2) 00339 { 00340 reset(); 00341 m_clipper.clip_box(conv_type::upscale(x1), conv_type::upscale(y1), 00342 conv_type::upscale(x2), conv_type::upscale(y2)); 00343 } 00344 00345 //------------------------------------------------------------------------ 00346 template<class Clip> 00347 void rasterizer_compound_aa<Clip>::reset_clipping() 00348 { 00349 reset(); 00350 m_clipper.reset_clipping(); 00351 } 00352 00353 //------------------------------------------------------------------------ 00354 template<class Clip> 00355 void rasterizer_compound_aa<Clip>::styles(int left, int right) 00356 { 00357 cell_style_aa cell; 00358 cell.initial(); 00359 cell.left = (int16)left; 00360 cell.right = (int16)right; 00361 m_outline.style(cell); 00362 if(left >= 0 && left < m_min_style) m_min_style = left; 00363 if(left >= 0 && left > m_max_style) m_max_style = left; 00364 if(right >= 0 && right < m_min_style) m_min_style = right; 00365 if(right >= 0 && right > m_max_style) m_max_style = right; 00366 } 00367 00368 //------------------------------------------------------------------------ 00369 template<class Clip> 00370 void rasterizer_compound_aa<Clip>::move_to(int x, int y) 00371 { 00372 if(m_outline.sorted()) reset(); 00373 m_clipper.move_to(m_start_x = conv_type::downscale(x), 00374 m_start_y = conv_type::downscale(y)); 00375 } 00376 00377 //------------------------------------------------------------------------ 00378 template<class Clip> 00379 void rasterizer_compound_aa<Clip>::line_to(int x, int y) 00380 { 00381 m_clipper.line_to(m_outline, 00382 conv_type::downscale(x), 00383 conv_type::downscale(y)); 00384 } 00385 00386 //------------------------------------------------------------------------ 00387 template<class Clip> 00388 void rasterizer_compound_aa<Clip>::move_to_d(double x, double y) 00389 { 00390 if(m_outline.sorted()) reset(); 00391 m_clipper.move_to(m_start_x = conv_type::upscale(x), 00392 m_start_y = conv_type::upscale(y)); 00393 } 00394 00395 //------------------------------------------------------------------------ 00396 template<class Clip> 00397 void rasterizer_compound_aa<Clip>::line_to_d(double x, double y) 00398 { 00399 m_clipper.line_to(m_outline, 00400 conv_type::upscale(x), 00401 conv_type::upscale(y)); 00402 } 00403 00404 //------------------------------------------------------------------------ 00405 template<class Clip> 00406 void rasterizer_compound_aa<Clip>::add_vertex(double x, double y, unsigned cmd) 00407 { 00408 if(is_move_to(cmd)) 00409 { 00410 move_to_d(x, y); 00411 } 00412 else 00413 if(is_vertex(cmd)) 00414 { 00415 line_to_d(x, y); 00416 } 00417 else 00418 if(is_close(cmd)) 00419 { 00420 m_clipper.line_to(m_outline, m_start_x, m_start_y); 00421 } 00422 } 00423 00424 //------------------------------------------------------------------------ 00425 template<class Clip> 00426 void rasterizer_compound_aa<Clip>::edge(int x1, int y1, int x2, int y2) 00427 { 00428 if(m_outline.sorted()) reset(); 00429 m_clipper.move_to(conv_type::downscale(x1), conv_type::downscale(y1)); 00430 m_clipper.line_to(m_outline, 00431 conv_type::downscale(x2), 00432 conv_type::downscale(y2)); 00433 } 00434 00435 //------------------------------------------------------------------------ 00436 template<class Clip> 00437 void rasterizer_compound_aa<Clip>::edge_d(double x1, double y1, 00438 double x2, double y2) 00439 { 00440 if(m_outline.sorted()) reset(); 00441 m_clipper.move_to(conv_type::upscale(x1), conv_type::upscale(y1)); 00442 m_clipper.line_to(m_outline, 00443 conv_type::upscale(x2), 00444 conv_type::upscale(y2)); 00445 } 00446 00447 //------------------------------------------------------------------------ 00448 template<class Clip> 00449 AGG_INLINE void rasterizer_compound_aa<Clip>::sort() 00450 { 00451 m_outline.sort_cells(); 00452 } 00453 00454 //------------------------------------------------------------------------ 00455 template<class Clip> 00456 AGG_INLINE bool rasterizer_compound_aa<Clip>::rewind_scanlines() 00457 { 00458 m_outline.sort_cells(); 00459 if(m_outline.total_cells() == 0) 00460 { 00461 return false; 00462 } 00463 if(m_max_style < m_min_style) 00464 { 00465 return false; 00466 } 00467 m_scan_y = m_outline.min_y(); 00468 m_styles.allocate(m_max_style - m_min_style + 2, 128); 00469 allocate_master_alpha(); 00470 return true; 00471 } 00472 00473 //------------------------------------------------------------------------ 00474 template<class Clip> 00475 AGG_INLINE void rasterizer_compound_aa<Clip>::add_style(int style_id) 00476 { 00477 if(style_id < 0) style_id = 0; 00478 else style_id -= m_min_style - 1; 00479 00480 unsigned nbyte = style_id >> 3; 00481 unsigned mask = 1 << (style_id & 7); 00482 00483 style_info* style = &m_styles[style_id]; 00484 if((m_asm[nbyte] & mask) == 0) 00485 { 00486 m_ast.add(style_id); 00487 m_asm[nbyte] |= mask; 00488 style->start_cell = 0; 00489 style->num_cells = 0; 00490 style->last_x = -0x7FFFFFFF; 00491 } 00492 ++style->start_cell; 00493 } 00494 00495 //------------------------------------------------------------------------ 00496 // Returns the number of styles 00497 template<class Clip> 00498 unsigned rasterizer_compound_aa<Clip>::sweep_styles() 00499 { 00500 for(;;) 00501 { 00502 if(m_scan_y > m_outline.max_y()) return 0; 00503 unsigned num_cells = m_outline.scanline_num_cells(m_scan_y); 00504 const cell_style_aa* const* cells = m_outline.scanline_cells(m_scan_y); 00505 unsigned num_styles = m_max_style - m_min_style + 2; 00506 const cell_style_aa* curr_cell; 00507 unsigned style_id; 00508 style_info* style; 00509 cell_info* cell; 00510 00511 m_cells.allocate(num_cells * 2, 256); // Each cell can have two styles 00512 m_ast.capacity(num_styles, 64); 00513 m_asm.allocate((num_styles + 7) >> 3, 8); 00514 m_asm.zero(); 00515 00516 if(num_cells) 00517 { 00518 // Pre-add zero (for no-fill style, that is, -1). 00519 // We need that to ensure that the "-1 style" would go first. 00520 m_asm[0] |= 1; 00521 m_ast.add(0); 00522 style = &m_styles[0]; 00523 style->start_cell = 0; 00524 style->num_cells = 0; 00525 style->last_x = -0x7FFFFFFF; 00526 00527 m_sl_start = cells[0]->x; 00528 m_sl_len = cells[num_cells-1]->x - m_sl_start + 1; 00529 while(num_cells--) 00530 { 00531 curr_cell = *cells++; 00532 add_style(curr_cell->left); 00533 add_style(curr_cell->right); 00534 } 00535 00536 // Convert the Y-histogram into the array of starting indexes 00537 unsigned i; 00538 unsigned start_cell = 0; 00539 for(i = 0; i < m_ast.size(); i++) 00540 { 00541 style_info& st = m_styles[m_ast[i]]; 00542 unsigned v = st.start_cell; 00543 st.start_cell = start_cell; 00544 start_cell += v; 00545 } 00546 00547 cells = m_outline.scanline_cells(m_scan_y); 00548 num_cells = m_outline.scanline_num_cells(m_scan_y); 00549 00550 while(num_cells--) 00551 { 00552 curr_cell = *cells++; 00553 style_id = (curr_cell->left < 0) ? 0 : 00554 curr_cell->left - m_min_style + 1; 00555 00556 style = &m_styles[style_id]; 00557 if(curr_cell->x == style->last_x) 00558 { 00559 cell = &m_cells[style->start_cell + style->num_cells - 1]; 00560 cell->area += curr_cell->area; 00561 cell->cover += curr_cell->cover; 00562 } 00563 else 00564 { 00565 cell = &m_cells[style->start_cell + style->num_cells]; 00566 cell->x = curr_cell->x; 00567 cell->area = curr_cell->area; 00568 cell->cover = curr_cell->cover; 00569 style->last_x = curr_cell->x; 00570 style->num_cells++; 00571 } 00572 00573 style_id = (curr_cell->right < 0) ? 0 : 00574 curr_cell->right - m_min_style + 1; 00575 00576 style = &m_styles[style_id]; 00577 if(curr_cell->x == style->last_x) 00578 { 00579 cell = &m_cells[style->start_cell + style->num_cells - 1]; 00580 cell->area -= curr_cell->area; 00581 cell->cover -= curr_cell->cover; 00582 } 00583 else 00584 { 00585 cell = &m_cells[style->start_cell + style->num_cells]; 00586 cell->x = curr_cell->x; 00587 cell->area = -curr_cell->area; 00588 cell->cover = -curr_cell->cover; 00589 style->last_x = curr_cell->x; 00590 style->num_cells++; 00591 } 00592 } 00593 } 00594 if(m_ast.size() > 1) break; 00595 ++m_scan_y; 00596 } 00597 ++m_scan_y; 00598 00599 if(m_layer_order != layer_unsorted) 00600 { 00601 range_adaptor<pod_vector<unsigned> > ra(m_ast, 1, m_ast.size() - 1); 00602 if(m_layer_order == layer_direct) quick_sort(ra, unsigned_greater); 00603 else quick_sort(ra, unsigned_less); 00604 } 00605 00606 return m_ast.size() - 1; 00607 } 00608 00609 //------------------------------------------------------------------------ 00610 // Returns style ID depending of the existing style index 00611 template<class Clip> 00612 AGG_INLINE 00613 unsigned rasterizer_compound_aa<Clip>::style(unsigned style_idx) const 00614 { 00615 return m_ast[style_idx + 1] + m_min_style - 1; 00616 } 00617 00618 //------------------------------------------------------------------------ 00619 template<class Clip> 00620 AGG_INLINE bool rasterizer_compound_aa<Clip>::navigate_scanline(int y) 00621 { 00622 m_outline.sort_cells(); 00623 if(m_outline.total_cells() == 0) 00624 { 00625 return false; 00626 } 00627 if(m_max_style < m_min_style) 00628 { 00629 return false; 00630 } 00631 if(y < m_outline.min_y() || y > m_outline.max_y()) 00632 { 00633 return false; 00634 } 00635 m_scan_y = y; 00636 m_styles.allocate(m_max_style - m_min_style + 2, 128); 00637 allocate_master_alpha(); 00638 return true; 00639 } 00640 00641 //------------------------------------------------------------------------ 00642 template<class Clip> 00643 bool rasterizer_compound_aa<Clip>::hit_test(int tx, int ty) 00644 { 00645 if(!navigate_scanline(ty)) 00646 { 00647 return false; 00648 } 00649 00650 unsigned num_styles = sweep_styles(); 00651 if(num_styles <= 0) 00652 { 00653 return false; 00654 } 00655 00656 scanline_hit_test sl(tx); 00657 sweep_scanline(sl, -1); 00658 return sl.hit(); 00659 } 00660 00661 //------------------------------------------------------------------------ 00662 template<class Clip> 00663 cover_type* rasterizer_compound_aa<Clip>::allocate_cover_buffer(unsigned len) 00664 { 00665 m_cover_buf.allocate(len, 256); 00666 return &m_cover_buf[0]; 00667 } 00668 00669 //------------------------------------------------------------------------ 00670 template<class Clip> 00671 void rasterizer_compound_aa<Clip>::allocate_master_alpha() 00672 { 00673 while((int)m_master_alpha.size() <= m_max_style) 00674 { 00675 m_master_alpha.add(aa_mask); 00676 } 00677 } 00678 00679 //------------------------------------------------------------------------ 00680 template<class Clip> 00681 void rasterizer_compound_aa<Clip>::master_alpha(int style, double alpha) 00682 { 00683 if(style >= 0) 00684 { 00685 while((int)m_master_alpha.size() <= style) 00686 { 00687 m_master_alpha.add(aa_mask); 00688 } 00689 m_master_alpha[style] = uround(alpha * aa_mask); 00690 } 00691 } 00692 00693 } 00694 00695 00696 00697 #endif 00698