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_SCANLINE_AA_INCLUDED 30 #define AGG_RASTERIZER_SCANLINE_AA_INCLUDED 31 32 #include "agg_rasterizer_cells_aa.h" 33 #include "agg_rasterizer_sl_clip.h" 34 #include "agg_gamma_functions.h" 35 36 37 namespace mapserver 38 { 39 40 41 //-----------------------------------------------------------------cell_aa 42 // A pixel cell. There're no constructors defined and it was done 43 // intentionally in order to avoid extra overhead when allocating an 44 // array of cells. 45 struct cell_aa 46 { 47 int x; 48 int y; 49 int cover; 50 int area; 51 initialcell_aa52 void initial() 53 { 54 x = 0x7FFFFFFF; 55 y = 0x7FFFFFFF; 56 cover = 0; 57 area = 0; 58 } 59 stylecell_aa60 void style(const cell_aa&) {} 61 not_equalcell_aa62 int not_equal(int ex, int ey, const cell_aa&) const 63 { 64 return (ex - x) | (ey - y); 65 } 66 }; 67 68 69 //==================================================rasterizer_scanline_aa 70 // Polygon rasterizer that is used to render filled polygons with 71 // high-quality Anti-Aliasing. Internally, by default, the class uses 72 // integer coordinates in format 24.8, i.e. 24 bits for integer part 73 // and 8 bits for fractional - see poly_subpixel_shift. This class can be 74 // used in the following way: 75 // 76 // 1. filling_rule(filling_rule_e ft) - optional. 77 // 78 // 2. gamma() - optional. 79 // 80 // 3. reset() 81 // 82 // 4. move_to(x, y) / line_to(x, y) - make the polygon. One can create 83 // more than one contour, but each contour must consist of at least 3 84 // vertices, i.e. move_to(x1, y1); line_to(x2, y2); line_to(x3, y3); 85 // is the absolute minimum of vertices that define a triangle. 86 // The algorithm does not check either the number of vertices nor 87 // coincidence of their coordinates, but in the worst case it just 88 // won't draw anything. 89 // The orger of the vertices (clockwise or counterclockwise) 90 // is important when using the non-zero filling rule (fill_non_zero). 91 // In this case the vertex order of all the contours must be the same 92 // if you want your intersecting polygons to be without "holes". 93 // You actually can use different vertices order. If the contours do not 94 // intersect each other the order is not important anyway. If they do, 95 // contours with the same vertex order will be rendered without "holes" 96 // while the intersecting contours with different orders will have "holes". 97 // 98 // filling_rule() and gamma() can be called anytime before "sweeping". 99 //------------------------------------------------------------------------ 100 template<class Clip=rasterizer_sl_clip_int> class rasterizer_scanline_aa 101 { 102 enum status 103 { 104 status_initial, 105 status_move_to, 106 status_line_to, 107 status_closed 108 }; 109 110 public: 111 typedef Clip clip_type; 112 typedef typename Clip::conv_type conv_type; 113 typedef typename Clip::coord_type coord_type; 114 115 enum aa_scale_e 116 { 117 aa_shift = 8, 118 aa_scale = 1 << aa_shift, 119 aa_mask = aa_scale - 1, 120 aa_scale2 = aa_scale * 2, 121 aa_mask2 = aa_scale2 - 1 122 }; 123 124 //-------------------------------------------------------------------- rasterizer_scanline_aa()125 rasterizer_scanline_aa() : 126 m_outline(), 127 m_clipper(), 128 m_filling_rule(fill_non_zero), 129 m_auto_close(true), 130 m_start_x(0), 131 m_start_y(0), 132 m_status(status_initial) 133 { 134 int i; 135 for(i = 0; i < aa_scale; i++) m_gamma[i] = i; 136 } 137 138 //-------------------------------------------------------------------- 139 template<class GammaF> rasterizer_scanline_aa(const GammaF & gamma_function)140 rasterizer_scanline_aa(const GammaF& gamma_function) : 141 m_outline(), 142 m_clipper(m_outline), 143 m_filling_rule(fill_non_zero), 144 m_auto_close(true), 145 m_start_x(0), 146 m_start_y(0), 147 m_status(status_initial) 148 { 149 gamma(gamma_function); 150 } 151 152 //-------------------------------------------------------------------- 153 void reset(); 154 void reset_clipping(); 155 void clip_box(double x1, double y1, double x2, double y2); 156 void filling_rule(filling_rule_e filling_rule); auto_close(bool flag)157 void auto_close(bool flag) { m_auto_close = flag; } 158 159 //-------------------------------------------------------------------- gamma(const GammaF & gamma_function)160 template<class GammaF> void gamma(const GammaF& gamma_function) 161 { 162 int i; 163 for(i = 0; i < aa_scale; i++) 164 { 165 m_gamma[i] = uround(gamma_function(double(i) / aa_mask) * aa_mask); 166 } 167 } 168 169 //-------------------------------------------------------------------- apply_gamma(unsigned cover)170 unsigned apply_gamma(unsigned cover) const 171 { 172 return m_gamma[cover]; 173 } 174 175 //-------------------------------------------------------------------- 176 void move_to(int x, int y); 177 void line_to(int x, int y); 178 void move_to_d(double x, double y); 179 void line_to_d(double x, double y); 180 void close_polygon(); 181 void add_vertex(double x, double y, unsigned cmd); 182 183 void edge(int x1, int y1, int x2, int y2); 184 void edge_d(double x1, double y1, double x2, double y2); 185 186 //------------------------------------------------------------------- 187 template<class VertexSource> 188 void add_path(VertexSource& vs, unsigned path_id=0) 189 { 190 double x; 191 double y; 192 193 unsigned cmd; 194 vs.rewind(path_id); 195 if(m_outline.sorted()) reset(); 196 while(!is_stop(cmd = vs.vertex(&x, &y))) 197 { 198 add_vertex(x, y, cmd); 199 } 200 } 201 202 //-------------------------------------------------------------------- min_x()203 int min_x() const { return m_outline.min_x(); } min_y()204 int min_y() const { return m_outline.min_y(); } max_x()205 int max_x() const { return m_outline.max_x(); } max_y()206 int max_y() const { return m_outline.max_y(); } 207 208 //-------------------------------------------------------------------- 209 void sort(); 210 bool rewind_scanlines(); 211 bool navigate_scanline(int y); 212 213 //-------------------------------------------------------------------- calculate_alpha(int area)214 AGG_INLINE unsigned calculate_alpha(int area) const 215 { 216 int cover = area >> (poly_subpixel_shift*2 + 1 - aa_shift); 217 218 if(cover < 0) cover = -cover; 219 if(m_filling_rule == fill_even_odd) 220 { 221 cover &= aa_mask2; 222 if(cover > aa_scale) 223 { 224 cover = aa_scale2 - cover; 225 } 226 } 227 if(cover > aa_mask) cover = aa_mask; 228 return m_gamma[cover]; 229 } 230 231 //-------------------------------------------------------------------- sweep_scanline(Scanline & sl)232 template<class Scanline> bool sweep_scanline(Scanline& sl) 233 { 234 for(;;) 235 { 236 if(m_scan_y > m_outline.max_y()) return false; 237 sl.reset_spans(); 238 unsigned num_cells = m_outline.scanline_num_cells(m_scan_y); 239 const cell_aa* const* cells = m_outline.scanline_cells(m_scan_y); 240 int cover = 0; 241 242 while(num_cells) 243 { 244 const cell_aa* cur_cell = *cells; 245 int x = cur_cell->x; 246 int area = cur_cell->area; 247 unsigned alpha; 248 249 cover += cur_cell->cover; 250 251 //accumulate all cells with the same X 252 while(--num_cells) 253 { 254 cur_cell = *++cells; 255 if(cur_cell->x != x) break; 256 area += cur_cell->area; 257 cover += cur_cell->cover; 258 } 259 260 if(area) 261 { 262 alpha = calculate_alpha((cover << (poly_subpixel_shift + 1)) - area); 263 if(alpha) 264 { 265 sl.add_cell(x, alpha); 266 } 267 x++; 268 } 269 270 if(num_cells && cur_cell->x > x) 271 { 272 alpha = calculate_alpha(cover << (poly_subpixel_shift + 1)); 273 if(alpha) 274 { 275 sl.add_span(x, cur_cell->x - x, alpha); 276 } 277 } 278 } 279 280 if(sl.num_spans()) break; 281 ++m_scan_y; 282 } 283 284 sl.finalize(m_scan_y); 285 ++m_scan_y; 286 return true; 287 } 288 289 //-------------------------------------------------------------------- 290 bool hit_test(int tx, int ty); 291 292 293 private: 294 //-------------------------------------------------------------------- 295 // Disable copying 296 rasterizer_scanline_aa(const rasterizer_scanline_aa<Clip>&); 297 const rasterizer_scanline_aa<Clip>& 298 operator = (const rasterizer_scanline_aa<Clip>&); 299 300 private: 301 rasterizer_cells_aa<cell_aa> m_outline; 302 clip_type m_clipper; 303 int m_gamma[aa_scale]; 304 filling_rule_e m_filling_rule; 305 bool m_auto_close; 306 coord_type m_start_x; 307 coord_type m_start_y; 308 unsigned m_status; 309 int m_scan_y; 310 }; 311 312 313 314 315 316 317 318 319 320 321 322 323 //------------------------------------------------------------------------ 324 template<class Clip> reset()325 void rasterizer_scanline_aa<Clip>::reset() 326 { 327 m_outline.reset(); 328 m_status = status_initial; 329 } 330 331 //------------------------------------------------------------------------ 332 template<class Clip> filling_rule(filling_rule_e filling_rule)333 void rasterizer_scanline_aa<Clip>::filling_rule(filling_rule_e filling_rule) 334 { 335 m_filling_rule = filling_rule; 336 } 337 338 //------------------------------------------------------------------------ 339 template<class Clip> clip_box(double x1,double y1,double x2,double y2)340 void rasterizer_scanline_aa<Clip>::clip_box(double x1, double y1, 341 double x2, double y2) 342 { 343 reset(); 344 m_clipper.clip_box(conv_type::upscale(x1), conv_type::upscale(y1), 345 conv_type::upscale(x2), conv_type::upscale(y2)); 346 } 347 348 //------------------------------------------------------------------------ 349 template<class Clip> reset_clipping()350 void rasterizer_scanline_aa<Clip>::reset_clipping() 351 { 352 reset(); 353 m_clipper.reset_clipping(); 354 } 355 356 //------------------------------------------------------------------------ 357 template<class Clip> close_polygon()358 void rasterizer_scanline_aa<Clip>::close_polygon() 359 { 360 if(m_status == status_line_to) 361 { 362 m_clipper.line_to(m_outline, m_start_x, m_start_y); 363 m_status = status_closed; 364 } 365 } 366 367 //------------------------------------------------------------------------ 368 template<class Clip> move_to(int x,int y)369 void rasterizer_scanline_aa<Clip>::move_to(int x, int y) 370 { 371 if(m_outline.sorted()) reset(); 372 if(m_auto_close) close_polygon(); 373 m_clipper.move_to(m_start_x = conv_type::downscale(x), 374 m_start_y = conv_type::downscale(y)); 375 m_status = status_move_to; 376 } 377 378 //------------------------------------------------------------------------ 379 template<class Clip> line_to(int x,int y)380 void rasterizer_scanline_aa<Clip>::line_to(int x, int y) 381 { 382 m_clipper.line_to(m_outline, 383 conv_type::downscale(x), 384 conv_type::downscale(y)); 385 m_status = status_line_to; 386 } 387 388 //------------------------------------------------------------------------ 389 template<class Clip> move_to_d(double x,double y)390 void rasterizer_scanline_aa<Clip>::move_to_d(double x, double y) 391 { 392 if(m_outline.sorted()) reset(); 393 if(m_auto_close) close_polygon(); 394 m_clipper.move_to(m_start_x = conv_type::upscale(x), 395 m_start_y = conv_type::upscale(y)); 396 m_status = status_move_to; 397 } 398 399 //------------------------------------------------------------------------ 400 template<class Clip> line_to_d(double x,double y)401 void rasterizer_scanline_aa<Clip>::line_to_d(double x, double y) 402 { 403 m_clipper.line_to(m_outline, 404 conv_type::upscale(x), 405 conv_type::upscale(y)); 406 m_status = status_line_to; 407 } 408 409 //------------------------------------------------------------------------ 410 template<class Clip> add_vertex(double x,double y,unsigned cmd)411 void rasterizer_scanline_aa<Clip>::add_vertex(double x, double y, unsigned cmd) 412 { 413 if(is_move_to(cmd)) 414 { 415 move_to_d(x, y); 416 } 417 else 418 if(is_vertex(cmd)) 419 { 420 line_to_d(x, y); 421 } 422 else 423 if(is_close(cmd)) 424 { 425 close_polygon(); 426 } 427 } 428 429 //------------------------------------------------------------------------ 430 template<class Clip> edge(int x1,int y1,int x2,int y2)431 void rasterizer_scanline_aa<Clip>::edge(int x1, int y1, int x2, int y2) 432 { 433 if(m_outline.sorted()) reset(); 434 m_clipper.move_to(conv_type::downscale(x1), conv_type::downscale(y1)); 435 m_clipper.line_to(m_outline, 436 conv_type::downscale(x2), 437 conv_type::downscale(y2)); 438 m_status = status_move_to; 439 } 440 441 //------------------------------------------------------------------------ 442 template<class Clip> edge_d(double x1,double y1,double x2,double y2)443 void rasterizer_scanline_aa<Clip>::edge_d(double x1, double y1, 444 double x2, double y2) 445 { 446 if(m_outline.sorted()) reset(); 447 m_clipper.move_to(conv_type::upscale(x1), conv_type::upscale(y1)); 448 m_clipper.line_to(m_outline, 449 conv_type::upscale(x2), 450 conv_type::upscale(y2)); 451 m_status = status_move_to; 452 } 453 454 //------------------------------------------------------------------------ 455 template<class Clip> sort()456 void rasterizer_scanline_aa<Clip>::sort() 457 { 458 if(m_auto_close) close_polygon(); 459 m_outline.sort_cells(); 460 } 461 462 //------------------------------------------------------------------------ 463 template<class Clip> rewind_scanlines()464 AGG_INLINE bool rasterizer_scanline_aa<Clip>::rewind_scanlines() 465 { 466 if(m_auto_close) close_polygon(); 467 m_outline.sort_cells(); 468 if(m_outline.total_cells() == 0) 469 { 470 return false; 471 } 472 m_scan_y = m_outline.min_y(); 473 return true; 474 } 475 476 477 //------------------------------------------------------------------------ 478 template<class Clip> navigate_scanline(int y)479 AGG_INLINE bool rasterizer_scanline_aa<Clip>::navigate_scanline(int y) 480 { 481 if(m_auto_close) close_polygon(); 482 m_outline.sort_cells(); 483 if(m_outline.total_cells() == 0 || 484 y < m_outline.min_y() || 485 y > m_outline.max_y()) 486 { 487 return false; 488 } 489 m_scan_y = y; 490 return true; 491 } 492 493 //------------------------------------------------------------------------ 494 template<class Clip> hit_test(int tx,int ty)495 bool rasterizer_scanline_aa<Clip>::hit_test(int tx, int ty) 496 { 497 if(!navigate_scanline(ty)) return false; 498 scanline_hit_test sl(tx); 499 sweep_scanline(sl); 500 return sl.hit(); 501 } 502 503 504 505 } 506 507 508 509 #endif 510 511