1 //----------------------------------------------------------------------------
2 // Anti-Grain Geometry - Version 2.3
3 // Copyright (C) 2002-2005 Maxim Shemanarev (http://www.antigrain.com)
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.
10 //----------------------------------------------------------------------------
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.
16 //----------------------------------------------------------------------------
17 // Contact: mcseem@antigrain.com
18 // mcseemagg@yahoo.com
19 // http://www.antigrain.com
20 //----------------------------------------------------------------------------
22 // Adaptation for 32-bit screen coordinates has been sponsored by
23 // Liberty Technology Systems, Inc., visit http://lib-sys.com
25 // Liberty Technology Systems, Inc. is the provider of
26 // PostScript and PDF technology for software developers.
28 //----------------------------------------------------------------------------
29 #ifndef AGG_RASTERIZER_COMPOUND_AA_INCLUDED
30 #define AGG_RASTERIZER_COMPOUND_AA_INCLUDED
32 #include "agg_rasterizer_cells_aa.h"
33 #include "agg_rasterizer_sl_clip.h"
38 //-----------------------------------------------------------cell_style_aa
39 // A pixel cell. There're no constructors defined and it was done
40 // intentionally in order to avoid extra overhead when allocating an
60 void style(const cell_style_aa
& c
)
66 int not_equal(int ex
, int ey
, const cell_style_aa
& c
) const
68 return (ex
- x
) | (ey
- y
) | (left
- c
.left
) | (right
- c
.right
);
73 //==================================================rasterizer_compound_aa
74 template<class Clip
=rasterizer_sl_clip_int
> class rasterizer_compound_aa
89 typedef Clip clip_type
;
90 typedef typename
Clip::conv_type conv_type
;
91 typedef typename
Clip::coord_type coord_type
;
96 aa_scale
= 1 << aa_shift
,
97 aa_mask
= aa_scale
- 1,
98 aa_scale2
= aa_scale
* 2,
99 aa_mask2
= aa_scale2
- 1
102 //--------------------------------------------------------------------
103 rasterizer_compound_aa() :
106 m_filling_rule(fill_non_zero
),
107 m_styles(), // Active Styles
108 m_ast(), // Active Style Table (unique values)
109 m_asm(), // Active Style Mask
113 m_min_style(0x7FFFFFFF),
114 m_max_style(-0x7FFFFFFF),
117 m_scan_y(0x7FFFFFFF),
122 //--------------------------------------------------------------------
124 void reset_clipping();
125 void clip_box(double x1
, double y1
, double x2
, double y2
);
126 void filling_rule(filling_rule_e filling_rule
);
127 void master_alpha(int style
, double alpha
);
129 //--------------------------------------------------------------------
130 void styles(int left
, int right
);
131 void move_to(int x
, int y
);
132 void line_to(int x
, int y
);
133 void move_to_d(double x
, double y
);
134 void line_to_d(double x
, double y
);
135 void add_vertex(double x
, double y
, unsigned cmd
);
137 void edge(int x1
, int y1
, int x2
, int y2
);
138 void edge_d(double x1
, double y1
, double x2
, double y2
);
140 //-------------------------------------------------------------------
141 template<class VertexSource
>
142 void add_path(VertexSource
& vs
, unsigned path_id
=0)
149 if(m_outline
.sorted()) reset();
150 while(!is_stop(cmd
= vs
.vertex(&x
, &y
)))
152 add_vertex(x
, y
, cmd
);
157 //--------------------------------------------------------------------
158 int min_x() const { return m_outline
.min_x(); }
159 int min_y() const { return m_outline
.min_y(); }
160 int max_x() const { return m_outline
.max_x(); }
161 int max_y() const { return m_outline
.max_y(); }
162 int min_style() const { return m_min_style
; }
163 int max_style() const { return m_max_style
; }
165 //--------------------------------------------------------------------
167 bool rewind_scanlines();
168 unsigned sweep_styles();
169 int scanline_start() const { return m_sl_start
; }
170 unsigned scanline_length() const { return m_sl_len
; }
171 unsigned style(unsigned style_idx
) const;
173 cover_type
* allocate_cover_buffer(unsigned len
);
175 //--------------------------------------------------------------------
176 bool navigate_scanline(int y
);
177 bool hit_test(int tx
, int ty
);
179 //--------------------------------------------------------------------
180 AGG_INLINE
unsigned calculate_alpha(int area
, unsigned master_alpha
) const
182 int cover
= area
>> (poly_subpixel_shift
*2 + 1 - aa_shift
);
183 if(cover
< 0) cover
= -cover
;
184 if(m_filling_rule
== fill_even_odd
)
189 cover
= aa_scale2
- cover
;
192 if(cover
> aa_mask
) cover
= aa_mask
;
193 return (cover
* master_alpha
+ aa_mask
) >> aa_shift
;
196 //--------------------------------------------------------------------
197 // Sweeps one scanline with one style index. The style ID can be
198 // determined by calling style().
199 template<class Scanline
> bool sweep_scanline(Scanline
& sl
, int style_idx
)
201 int scan_y
= m_scan_y
- 1;
202 if(scan_y
> m_outline
.max_y()) return false;
206 unsigned master_alpha
= aa_mask
;
215 master_alpha
= m_master_alpha
[m_ast
[style_idx
] + m_min_style
- 1];
218 const style_info
& st
= m_styles
[m_ast
[style_idx
]];
220 unsigned num_cells
= st
.num_cells
;
221 cell_info
* cell
= &m_cells
[st
.start_cell
];
228 int area
= cell
->area
;
230 cover
+= cell
->cover
;
236 alpha
= calculate_alpha((cover
<< (poly_subpixel_shift
+ 1)) - area
,
238 sl
.add_cell(x
, alpha
);
242 if(num_cells
&& cell
->x
> x
)
244 alpha
= calculate_alpha(cover
<< (poly_subpixel_shift
+ 1),
248 sl
.add_span(x
, cell
->x
- x
, alpha
);
253 if(sl
.num_spans() == 0) return false;
259 void add_style(int style_id
);
260 void allocate_master_alpha();
262 //--------------------------------------------------------------------
264 rasterizer_compound_aa(const rasterizer_compound_aa
<Clip
>&);
265 const rasterizer_compound_aa
<Clip
>&
266 operator = (const rasterizer_compound_aa
<Clip
>&);
269 rasterizer_cells_aa
<cell_style_aa
> m_outline
;
271 filling_rule_e m_filling_rule
;
272 pod_vector
<style_info
> m_styles
; // Active Styles
273 pod_vector
<unsigned> m_ast
; // Active Style Table (unique values)
274 pod_vector
<int8u
> m_asm
; // Active Style Mask
275 pod_vector
<cell_info
> m_cells
;
276 pod_vector
<cover_type
> m_cover_buf
;
277 pod_bvector
<unsigned> m_master_alpha
;
281 coord_type m_start_x
;
282 coord_type m_start_y
;
297 //------------------------------------------------------------------------
299 void rasterizer_compound_aa
<Clip
>::reset()
302 m_min_style
= 0x7FFFFFFF;
303 m_max_style
= -0x7FFFFFFF;
304 m_scan_y
= 0x7FFFFFFF;
309 //------------------------------------------------------------------------
311 void rasterizer_compound_aa
<Clip
>::filling_rule(filling_rule_e filling_rule
)
313 m_filling_rule
= filling_rule
;
316 //------------------------------------------------------------------------
318 void rasterizer_compound_aa
<Clip
>::clip_box(double x1
, double y1
,
319 double x2
, double y2
)
322 m_clipper
.clip_box(conv_type::upscale(x1
), conv_type::upscale(y1
),
323 conv_type::upscale(x2
), conv_type::upscale(y2
));
326 //------------------------------------------------------------------------
328 void rasterizer_compound_aa
<Clip
>::reset_clipping()
331 m_clipper
.reset_clipping();
334 //------------------------------------------------------------------------
336 void rasterizer_compound_aa
<Clip
>::styles(int left
, int right
)
340 cell
.left
= (int16
)left
;
341 cell
.right
= (int16
)right
;
342 m_outline
.style(cell
);
343 if(left
>= 0 && left
< m_min_style
) m_min_style
= left
;
344 if(left
>= 0 && left
> m_max_style
) m_max_style
= left
;
345 if(right
>= 0 && right
< m_min_style
) m_min_style
= right
;
346 if(right
>= 0 && right
> m_max_style
) m_max_style
= right
;
349 //------------------------------------------------------------------------
351 void rasterizer_compound_aa
<Clip
>::move_to(int x
, int y
)
353 if(m_outline
.sorted()) reset();
354 m_clipper
.move_to(m_start_x
= conv_type::downscale(x
),
355 m_start_y
= conv_type::downscale(y
));
358 //------------------------------------------------------------------------
360 void rasterizer_compound_aa
<Clip
>::line_to(int x
, int y
)
362 m_clipper
.line_to(m_outline
,
363 conv_type::downscale(x
),
364 conv_type::downscale(y
));
367 //------------------------------------------------------------------------
369 void rasterizer_compound_aa
<Clip
>::move_to_d(double x
, double y
)
371 if(m_outline
.sorted()) reset();
372 m_clipper
.move_to(m_start_x
= conv_type::upscale(x
),
373 m_start_y
= conv_type::upscale(y
));
376 //------------------------------------------------------------------------
378 void rasterizer_compound_aa
<Clip
>::line_to_d(double x
, double y
)
380 m_clipper
.line_to(m_outline
,
381 conv_type::upscale(x
),
382 conv_type::upscale(y
));
385 //------------------------------------------------------------------------
387 void rasterizer_compound_aa
<Clip
>::add_vertex(double x
, double y
, unsigned cmd
)
401 m_clipper
.line_to(m_outline
, m_start_x
, m_start_y
);
405 //------------------------------------------------------------------------
407 void rasterizer_compound_aa
<Clip
>::edge(int x1
, int y1
, int x2
, int y2
)
409 if(m_outline
.sorted()) reset();
410 m_clipper
.move_to(conv_type::downscale(x1
), conv_type::downscale(y1
));
411 m_clipper
.line_to(m_outline
,
412 conv_type::downscale(x2
),
413 conv_type::downscale(y2
));
416 //------------------------------------------------------------------------
418 void rasterizer_compound_aa
<Clip
>::edge_d(double x1
, double y1
,
419 double x2
, double y2
)
421 if(m_outline
.sorted()) reset();
422 m_clipper
.move_to(conv_type::upscale(x1
), conv_type::upscale(y1
));
423 m_clipper
.line_to(m_outline
,
424 conv_type::upscale(x2
),
425 conv_type::upscale(y2
));
428 //------------------------------------------------------------------------
430 AGG_INLINE
void rasterizer_compound_aa
<Clip
>::sort()
432 m_outline
.sort_cells();
435 //------------------------------------------------------------------------
437 AGG_INLINE
bool rasterizer_compound_aa
<Clip
>::rewind_scanlines()
439 m_outline
.sort_cells();
440 if(m_outline
.total_cells() == 0)
444 if(m_max_style
< m_min_style
)
448 m_scan_y
= m_outline
.min_y();
449 m_styles
.allocate(m_max_style
- m_min_style
+ 2, 128);
450 allocate_master_alpha();
454 //------------------------------------------------------------------------
456 AGG_INLINE
void rasterizer_compound_aa
<Clip
>::add_style(int style_id
)
458 if(style_id
< 0) style_id
= 0;
459 else style_id
-= m_min_style
- 1;
461 unsigned nbyte
= style_id
>> 3;
462 unsigned mask
= 1 << (style_id
& 7);
464 style_info
* style
= &m_styles
[style_id
];
465 if((m_asm
[nbyte
] & mask
) == 0)
468 m_asm
[nbyte
] |= mask
;
469 style
->start_cell
= 0;
470 style
->num_cells
= 0;
471 style
->last_x
= -0x7FFFFFFF;
476 //------------------------------------------------------------------------
477 // Returns the number of styles
479 unsigned rasterizer_compound_aa
<Clip
>::sweep_styles()
483 if(m_scan_y
> m_outline
.max_y()) return 0;
484 unsigned num_cells
= m_outline
.scanline_num_cells(m_scan_y
);
485 const cell_style_aa
* const* cells
= m_outline
.scanline_cells(m_scan_y
);
486 unsigned num_styles
= m_max_style
- m_min_style
+ 2;
487 const cell_style_aa
* curr_cell
;
492 m_cells
.allocate(num_cells
* 2, 256); // Each cell can have two styles
493 m_ast
.capacity(num_styles
, 64);
494 m_asm
.allocate((num_styles
+ 7) >> 3, 8);
499 // Pre-add zero (for no-fill style, that is, -1).
500 // We need that to ensure that the "-1 style" would go first.
503 style
= &m_styles
[0];
504 style
->start_cell
= 0;
505 style
->num_cells
= 0;
506 style
->last_x
= -0x7FFFFFFF;
508 m_sl_start
= cells
[0]->x
;
509 m_sl_len
= cells
[num_cells
-1]->x
- m_sl_start
+ 1;
512 curr_cell
= *cells
++;
513 add_style(curr_cell
->left
);
514 add_style(curr_cell
->right
);
517 // Convert the Y-histogram into the array of starting indexes
519 unsigned start_cell
= 0;
520 for(i
= 0; i
< m_ast
.size(); i
++)
522 style_info
& st
= m_styles
[m_ast
[i
]];
523 unsigned v
= st
.start_cell
;
524 st
.start_cell
= start_cell
;
528 cells
= m_outline
.scanline_cells(m_scan_y
);
529 num_cells
= m_outline
.scanline_num_cells(m_scan_y
);
533 curr_cell
= *cells
++;
534 style_id
= (curr_cell
->left
< 0) ? 0 :
535 curr_cell
->left
- m_min_style
+ 1;
537 style
= &m_styles
[style_id
];
538 if(curr_cell
->x
== style
->last_x
)
540 cell
= &m_cells
[style
->start_cell
+ style
->num_cells
- 1];
541 cell
->area
+= curr_cell
->area
;
542 cell
->cover
+= curr_cell
->cover
;
546 cell
= &m_cells
[style
->start_cell
+ style
->num_cells
];
547 cell
->x
= curr_cell
->x
;
548 cell
->area
= curr_cell
->area
;
549 cell
->cover
= curr_cell
->cover
;
550 style
->last_x
= curr_cell
->x
;
554 style_id
= (curr_cell
->right
< 0) ? 0 :
555 curr_cell
->right
- m_min_style
+ 1;
557 style
= &m_styles
[style_id
];
558 if(curr_cell
->x
== style
->last_x
)
560 cell
= &m_cells
[style
->start_cell
+ style
->num_cells
- 1];
561 cell
->area
-= curr_cell
->area
;
562 cell
->cover
-= curr_cell
->cover
;
566 cell
= &m_cells
[style
->start_cell
+ style
->num_cells
];
567 cell
->x
= curr_cell
->x
;
568 cell
->area
= -curr_cell
->area
;
569 cell
->cover
= -curr_cell
->cover
;
570 style
->last_x
= curr_cell
->x
;
575 if(m_ast
.size() > 1) break;
580 range_adaptor
<pod_vector
<unsigned> > ra(m_ast
, 1, m_ast
.size() - 1);
581 quick_sort(ra
, unsigned_greater
);
583 return m_ast
.size() - 1;
586 //------------------------------------------------------------------------
587 // Returns style ID depending of the existing style index
590 unsigned rasterizer_compound_aa
<Clip
>::style(unsigned style_idx
) const
592 return m_ast
[style_idx
+ 1] + m_min_style
- 1;
595 //------------------------------------------------------------------------
597 AGG_INLINE
bool rasterizer_compound_aa
<Clip
>::navigate_scanline(int y
)
599 m_outline
.sort_cells();
600 if(m_outline
.total_cells() == 0)
604 if(m_max_style
< m_min_style
)
608 if(y
< m_outline
.min_y() || y
> m_outline
.max_y())
613 m_styles
.allocate(m_max_style
- m_min_style
+ 2, 128);
614 allocate_master_alpha();
618 //------------------------------------------------------------------------
620 bool rasterizer_compound_aa
<Clip
>::hit_test(int tx
, int ty
)
622 if(!navigate_scanline(ty
))
627 unsigned num_styles
= sweep_styles();
633 scanline_hit_test
sl(tx
);
634 sweep_scanline(sl
, -1);
638 //------------------------------------------------------------------------
640 cover_type
* rasterizer_compound_aa
<Clip
>::allocate_cover_buffer(unsigned len
)
642 m_cover_buf
.allocate(len
, 256);
643 return &m_cover_buf
[0];
646 //------------------------------------------------------------------------
648 void rasterizer_compound_aa
<Clip
>::allocate_master_alpha()
650 while((int)m_master_alpha
.size() <= m_max_style
)
652 m_master_alpha
.add(aa_mask
);
656 //------------------------------------------------------------------------
658 void rasterizer_compound_aa
<Clip
>::master_alpha(int style
, double alpha
)
662 while((int)m_master_alpha
.size() <= style
)
664 m_master_alpha
.add(aa_mask
);
666 m_master_alpha
[style
] = uround(alpha
* aa_mask
);