btrfs: [] on the end of a struct field is a variable length array.
[haiku.git] / headers / libs / agg / agg_rasterizer_compound_aa.h
blob8547747c885e77ca7635d924735e367bd07d0a20
1 //----------------------------------------------------------------------------
2 // Anti-Grain Geometry - Version 2.3
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 //----------------------------------------------------------------------------
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.
27 //
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"
35 namespace agg
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
41 // array of cells.
42 struct cell_style_aa
44 int x;
45 int y;
46 int cover;
47 int area;
48 int16 left, right;
50 void initial()
52 x = 0x7FFFFFFF;
53 y = 0x7FFFFFFF;
54 cover = 0;
55 area = 0;
56 left = -1;
57 right = -1;
60 void style(const cell_style_aa& c)
62 left = c.left;
63 right = c.right;
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
76 struct style_info
78 unsigned start_cell;
79 unsigned num_cells;
80 int last_x;
83 struct cell_info
85 int x, area, cover;
88 public:
89 typedef Clip clip_type;
90 typedef typename Clip::conv_type conv_type;
91 typedef typename Clip::coord_type coord_type;
93 enum aa_scale_e
95 aa_shift = 8,
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() :
104 m_outline(),
105 m_clipper(),
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
110 m_cells(),
111 m_cover_buf(),
112 m_master_alpha(),
113 m_min_style(0x7FFFFFFF),
114 m_max_style(-0x7FFFFFFF),
115 m_start_x(0),
116 m_start_y(0),
117 m_scan_y(0x7FFFFFFF),
118 m_sl_start(0),
119 m_sl_len(0)
122 //--------------------------------------------------------------------
123 void reset();
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)
144 double x;
145 double y;
147 unsigned cmd;
148 vs.rewind(path_id);
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 //--------------------------------------------------------------------
166 void sort();
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)
186 cover &= aa_mask2;
187 if(cover > aa_scale)
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;
204 sl.reset_spans();
206 unsigned master_alpha = aa_mask;
208 if(style_idx < 0)
210 style_idx = 0;
212 else
214 style_idx++;
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];
223 int cover = 0;
224 while(num_cells--)
226 unsigned alpha;
227 int x = cell->x;
228 int area = cell->area;
230 cover += cell->cover;
232 ++cell;
234 if(area)
236 alpha = calculate_alpha((cover << (poly_subpixel_shift + 1)) - area,
237 master_alpha);
238 sl.add_cell(x, alpha);
239 x++;
242 if(num_cells && cell->x > x)
244 alpha = calculate_alpha(cover << (poly_subpixel_shift + 1),
245 master_alpha);
246 if(alpha)
248 sl.add_span(x, cell->x - x, alpha);
253 if(sl.num_spans() == 0) return false;
254 sl.finalize(scan_y);
255 return true;
258 private:
259 void add_style(int style_id);
260 void allocate_master_alpha();
262 //--------------------------------------------------------------------
263 // Disable copying
264 rasterizer_compound_aa(const rasterizer_compound_aa<Clip>&);
265 const rasterizer_compound_aa<Clip>&
266 operator = (const rasterizer_compound_aa<Clip>&);
268 private:
269 rasterizer_cells_aa<cell_style_aa> m_outline;
270 clip_type m_clipper;
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;
279 int m_min_style;
280 int m_max_style;
281 coord_type m_start_x;
282 coord_type m_start_y;
283 int m_scan_y;
284 int m_sl_start;
285 unsigned m_sl_len;
297 //------------------------------------------------------------------------
298 template<class Clip>
299 void rasterizer_compound_aa<Clip>::reset()
301 m_outline.reset();
302 m_min_style = 0x7FFFFFFF;
303 m_max_style = -0x7FFFFFFF;
304 m_scan_y = 0x7FFFFFFF;
305 m_sl_start = 0;
306 m_sl_len = 0;
309 //------------------------------------------------------------------------
310 template<class Clip>
311 void rasterizer_compound_aa<Clip>::filling_rule(filling_rule_e filling_rule)
313 m_filling_rule = filling_rule;
316 //------------------------------------------------------------------------
317 template<class Clip>
318 void rasterizer_compound_aa<Clip>::clip_box(double x1, double y1,
319 double x2, double y2)
321 reset();
322 m_clipper.clip_box(conv_type::upscale(x1), conv_type::upscale(y1),
323 conv_type::upscale(x2), conv_type::upscale(y2));
326 //------------------------------------------------------------------------
327 template<class Clip>
328 void rasterizer_compound_aa<Clip>::reset_clipping()
330 reset();
331 m_clipper.reset_clipping();
334 //------------------------------------------------------------------------
335 template<class Clip>
336 void rasterizer_compound_aa<Clip>::styles(int left, int right)
338 cell_style_aa cell;
339 cell.initial();
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 //------------------------------------------------------------------------
350 template<class Clip>
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 //------------------------------------------------------------------------
359 template<class Clip>
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 //------------------------------------------------------------------------
368 template<class Clip>
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 //------------------------------------------------------------------------
377 template<class Clip>
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 //------------------------------------------------------------------------
386 template<class Clip>
387 void rasterizer_compound_aa<Clip>::add_vertex(double x, double y, unsigned cmd)
389 if(is_move_to(cmd))
391 move_to_d(x, y);
393 else
394 if(is_vertex(cmd))
396 line_to_d(x, y);
398 else
399 if(is_close(cmd))
401 m_clipper.line_to(m_outline, m_start_x, m_start_y);
405 //------------------------------------------------------------------------
406 template<class Clip>
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 //------------------------------------------------------------------------
417 template<class Clip>
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 //------------------------------------------------------------------------
429 template<class Clip>
430 AGG_INLINE void rasterizer_compound_aa<Clip>::sort()
432 m_outline.sort_cells();
435 //------------------------------------------------------------------------
436 template<class Clip>
437 AGG_INLINE bool rasterizer_compound_aa<Clip>::rewind_scanlines()
439 m_outline.sort_cells();
440 if(m_outline.total_cells() == 0)
442 return false;
444 if(m_max_style < m_min_style)
446 return false;
448 m_scan_y = m_outline.min_y();
449 m_styles.allocate(m_max_style - m_min_style + 2, 128);
450 allocate_master_alpha();
451 return true;
454 //------------------------------------------------------------------------
455 template<class Clip>
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)
467 m_ast.add(style_id);
468 m_asm[nbyte] |= mask;
469 style->start_cell = 0;
470 style->num_cells = 0;
471 style->last_x = -0x7FFFFFFF;
473 ++style->start_cell;
476 //------------------------------------------------------------------------
477 // Returns the number of styles
478 template<class Clip>
479 unsigned rasterizer_compound_aa<Clip>::sweep_styles()
481 for(;;)
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;
488 unsigned style_id;
489 style_info* style;
490 cell_info* 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);
495 m_asm.zero();
497 if(num_cells)
499 // Pre-add zero (for no-fill style, that is, -1).
500 // We need that to ensure that the "-1 style" would go first.
501 m_asm[0] |= 1;
502 m_ast.add(0);
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;
510 while(num_cells--)
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
518 unsigned i;
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;
525 start_cell += v;
528 cells = m_outline.scanline_cells(m_scan_y);
529 num_cells = m_outline.scanline_num_cells(m_scan_y);
531 while(num_cells--)
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;
544 else
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;
551 style->num_cells++;
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;
564 else
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;
571 style->num_cells++;
575 if(m_ast.size() > 1) break;
576 ++m_scan_y;
578 ++m_scan_y;
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
588 template<class Clip>
589 AGG_INLINE
590 unsigned rasterizer_compound_aa<Clip>::style(unsigned style_idx) const
592 return m_ast[style_idx + 1] + m_min_style - 1;
595 //------------------------------------------------------------------------
596 template<class Clip>
597 AGG_INLINE bool rasterizer_compound_aa<Clip>::navigate_scanline(int y)
599 m_outline.sort_cells();
600 if(m_outline.total_cells() == 0)
602 return false;
604 if(m_max_style < m_min_style)
606 return false;
608 if(y < m_outline.min_y() || y > m_outline.max_y())
610 return false;
612 m_scan_y = y;
613 m_styles.allocate(m_max_style - m_min_style + 2, 128);
614 allocate_master_alpha();
615 return true;
618 //------------------------------------------------------------------------
619 template<class Clip>
620 bool rasterizer_compound_aa<Clip>::hit_test(int tx, int ty)
622 if(!navigate_scanline(ty))
624 return false;
627 unsigned num_styles = sweep_styles();
628 if(num_styles <= 0)
630 return false;
633 scanline_hit_test sl(tx);
634 sweep_scanline(sl, -1);
635 return sl.hit();
638 //------------------------------------------------------------------------
639 template<class Clip>
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 //------------------------------------------------------------------------
647 template<class Clip>
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 //------------------------------------------------------------------------
657 template<class Clip>
658 void rasterizer_compound_aa<Clip>::master_alpha(int style, double alpha)
660 if(style >= 0)
662 while((int)m_master_alpha.size() <= style)
664 m_master_alpha.add(aa_mask);
666 m_master_alpha[style] = uround(alpha * aa_mask);
674 #endif