634d10a3bef2d32542b71b572ec50a133593eac7
[pdfium.git] / core / src / fxge / agg / agg23 / fx_agg_rasterizer_scanline_aa.cpp
1
2 //----------------------------------------------------------------------------
3 // XYQ: 2006-01-22 Copied from AGG project.
4 // This file uses only integer data, so it's suitable for all platforms.
5 //----------------------------------------------------------------------------
6 //----------------------------------------------------------------------------
7 // Anti-Grain Geometry - Version 2.3
8 // Copyright (C) 2002-2005 Maxim Shemanarev (http://www.antigrain.com)
9 //
10 // Permission to copy, use, modify, sell and distribute this software
11 // is granted provided this copyright notice appears in all copies.
12 // This software is provided "as is" without express or implied
13 // warranty, and with no claim as to its suitability for any purpose.
14 //
15 //----------------------------------------------------------------------------
16 //
17 // The author gratefully acknowleges the support of David Turner,
18 // Robert Wilhelm, and Werner Lemberg - the authors of the FreeType
19 // libray - in producing this work. See http://www.freetype.org for details.
20 //
21 //----------------------------------------------------------------------------
22 // Contact: mcseem@antigrain.com
23 //          mcseemagg@yahoo.com
24 //          http://www.antigrain.com
25 //----------------------------------------------------------------------------
26 //
27 // Adaptation for 32-bit screen coordinates has been sponsored by
28 // Liberty Technology Systems, Inc., visit http://lib-sys.com
29 //
30 // Liberty Technology Systems, Inc. is the provider of
31 // PostScript and PDF technology for software developers.
32 //
33 //----------------------------------------------------------------------------
34 //
35 // Class outline_aa - implementation.
36 //
37 // Initially the rendering algorithm was designed by David Turner and the
38 // other authors of the FreeType library - see the above notice. I nearly
39 // created a similar renderer, but still I was far from David's work.
40 // I completely redesigned the original code and adapted it for Anti-Grain
41 // ideas. Two functions - render_line and render_hline are the core of
42 // the algorithm - they calculate the exact coverage of each pixel cell
43 // of the polygon. I left these functions almost as is, because there's
44 // no way to improve the perfection - hats off to David and his group!
45 //
46 // All other code is very different from the original.
47 //
48 //----------------------------------------------------------------------------
49 #include "../../../../include/fxcrt/fx_ext.h"
50 #include <limits.h>
51 #include "agg_rasterizer_scanline_aa.h"
52 namespace agg
53 {
54 AGG_INLINE void cell_aa::set_cover(int c, int a)
55 {
56     cover = c;
57     area = a;
58 }
59 AGG_INLINE void cell_aa::add_cover(int c, int a)
60 {
61     cover += c;
62     area += a;
63 }
64 AGG_INLINE void cell_aa::set_coord(int cx, int cy)
65 {
66     x = cx;
67     y = cy;
68 }
69 AGG_INLINE void cell_aa::set(int cx, int cy, int c, int a)
70 {
71     x = cx;
72     y = cy;
73     cover = c;
74     area = a;
75 }
76 outline_aa::~outline_aa()
77 {
78     if(m_num_blocks) {
79         cell_aa** ptr = m_cells + m_num_blocks - 1;
80         while(m_num_blocks--) {
81             FX_Free(*ptr);
82             ptr--;
83         }
84         FX_Free(m_cells);
85     }
86 }
87 outline_aa::outline_aa() :
88     m_num_blocks(0),
89     m_max_blocks(0),
90     m_cur_block(0),
91     m_num_cells(0),
92     m_cells(0),
93     m_cur_cell_ptr(0),
94     m_cur_x(0),
95     m_cur_y(0),
96     m_min_x(0x7FFFFFFF),
97     m_min_y(0x7FFFFFFF),
98     m_max_x(-0x7FFFFFFF),
99     m_max_y(-0x7FFFFFFF),
100     m_sorted(false)
101 {
102     m_cur_cell.set(0x7FFF, 0x7FFF, 0, 0);
103 }
104 void outline_aa::reset()
105 {
106     m_num_cells = 0;
107     m_cur_block = 0;
108     m_cur_cell.set(0x7FFF, 0x7FFF, 0, 0);
109     m_sorted = false;
110     m_min_x =  0x7FFFFFFF;
111     m_min_y =  0x7FFFFFFF;
112     m_max_x = -0x7FFFFFFF;
113     m_max_y = -0x7FFFFFFF;
114 }
115 void outline_aa::allocate_block()
116 {
117     if(m_cur_block >= m_num_blocks) {
118         if(m_num_blocks >= m_max_blocks) {
119             cell_aa** new_cells = FX_Alloc( cell_aa*, m_max_blocks + cell_block_pool);
120             if (!new_cells) {
121                 return;
122             }
123             if(m_cells) {
124                 FXSYS_memcpy32(new_cells, m_cells, m_max_blocks * sizeof(cell_aa*));
125                 FX_Free(m_cells);
126             }
127             m_cells = new_cells;
128             m_max_blocks += cell_block_pool;
129         }
130         m_cells[m_num_blocks++] = FX_Alloc(cell_aa, cell_block_size);
131         if (!m_cells[m_num_blocks - 1]) {
132             return;
133         }
134     }
135     m_cur_cell_ptr = m_cells[m_cur_block++];
136 }
137 AGG_INLINE void outline_aa::add_cur_cell()
138 {
139     if(m_cur_cell.area | m_cur_cell.cover) {
140         if((m_num_cells & cell_block_mask) == 0) {
141             if(m_num_blocks >= cell_block_limit) {
142                 return;
143             }
144             allocate_block();
145         }
146         *m_cur_cell_ptr++ = m_cur_cell;
147         ++m_num_cells;
148     }
149 }
150 AGG_INLINE void outline_aa::set_cur_cell(int x, int y)
151 {
152     if(m_cur_cell.x != x || m_cur_cell.y != y) {
153         add_cur_cell();
154         m_cur_cell.set(x, y, 0, 0);
155         if(x < m_min_x) {
156             m_min_x = x;
157         }
158         if(x > m_max_x) {
159             m_max_x = x;
160         }
161         if(y < m_min_y) {
162             m_min_y = y;
163         }
164         if(y > m_max_y) {
165             m_max_y = y;
166         }
167     }
168 }
169 AGG_INLINE void outline_aa::render_hline(int ey, int x1, int y1, int x2, int y2)
170 {
171     int ex1 = x1 >> poly_base_shift;
172     int ex2 = x2 >> poly_base_shift;
173     int fx1 = x1 & poly_base_mask;
174     int fx2 = x2 & poly_base_mask;
175     int delta, p, first, dx;
176     int incr, lift, mod, rem;
177     if(y1 == y2) {
178         set_cur_cell(ex2, ey);
179         return;
180     }
181     if(ex1 == ex2) {
182         delta = y2 - y1;
183         m_cur_cell.add_cover(delta, (fx1 + fx2) * delta);
184         return;
185     }
186     p     = (poly_base_size - fx1) * (y2 - y1);
187     first = poly_base_size;
188     incr  = 1;
189     dx = x2 - x1;
190     if(dx < 0) {
191         p     = fx1 * (y2 - y1);
192         first = 0;
193         incr  = -1;
194         dx    = -dx;
195     }
196     delta = p / dx;
197     mod   = p % dx;
198     if(mod < 0) {
199         delta--;
200         mod += dx;
201     }
202     m_cur_cell.add_cover(delta, (fx1 + first) * delta);
203     ex1 += incr;
204     set_cur_cell(ex1, ey);
205     y1  += delta;
206     if(ex1 != ex2) {
207         p     = poly_base_size * (y2 - y1 + delta);
208         lift  = p / dx;
209         rem   = p % dx;
210         if (rem < 0) {
211             lift--;
212             rem += dx;
213         }
214         mod -= dx;
215         while (ex1 != ex2) {
216             delta = lift;
217             mod  += rem;
218             if(mod >= 0) {
219                 mod -= dx;
220                 delta++;
221             }
222             m_cur_cell.add_cover(delta, (poly_base_size) * delta);
223             y1  += delta;
224             ex1 += incr;
225             set_cur_cell(ex1, ey);
226         }
227     }
228     delta = y2 - y1;
229     m_cur_cell.add_cover(delta, (fx2 + poly_base_size - first) * delta);
230 }
231 void outline_aa::render_line(int x1, int y1, int x2, int y2)
232 {
233     enum dx_limit_e { dx_limit = 16384 << poly_base_shift };
234     int dx = x2 - x1;
235     if(dx >= dx_limit || dx <= -dx_limit) {
236         int cx = (x1 + x2) >> 1;
237         int cy = (y1 + y2) >> 1;
238         render_line(x1, y1, cx, cy);
239         render_line(cx, cy, x2, y2);
240     }
241     int dy = y2 - y1;
242     int ey1 = y1 >> poly_base_shift;
243     int ey2 = y2 >> poly_base_shift;
244     int fy1 = y1 & poly_base_mask;
245     int fy2 = y2 & poly_base_mask;
246     int x_from, x_to;
247     int p, rem, mod, lift, delta, first, incr;
248     if(ey1 == ey2) {
249         render_hline(ey1, x1, fy1, x2, fy2);
250         return;
251     }
252     incr  = 1;
253     if(dx == 0) {
254         int ex = x1 >> poly_base_shift;
255         int two_fx = (x1 - (ex << poly_base_shift)) << 1;
256         int area;
257         first = poly_base_size;
258         if(dy < 0) {
259             first = 0;
260             incr  = -1;
261         }
262         x_from = x1;
263         delta = first - fy1;
264         m_cur_cell.add_cover(delta, two_fx * delta);
265         ey1 += incr;
266         set_cur_cell(ex, ey1);
267         delta = first + first - poly_base_size;
268         area = two_fx * delta;
269         while(ey1 != ey2) {
270             m_cur_cell.set_cover(delta, area);
271             ey1 += incr;
272             set_cur_cell(ex, ey1);
273         }
274         delta = fy2 - poly_base_size + first;
275         m_cur_cell.add_cover(delta, two_fx * delta);
276         return;
277     }
278     p     = (poly_base_size - fy1) * dx;
279     first = poly_base_size;
280     if(dy < 0) {
281         p     = fy1 * dx;
282         first = 0;
283         incr  = -1;
284         dy    = -dy;
285     }
286     delta = p / dy;
287     mod   = p % dy;
288     if(mod < 0) {
289         delta--;
290         mod += dy;
291     }
292     x_from = x1 + delta;
293     render_hline(ey1, x1, fy1, x_from, first);
294     ey1 += incr;
295     set_cur_cell(x_from >> poly_base_shift, ey1);
296     if(ey1 != ey2) {
297         p     = poly_base_size * dx;
298         lift  = p / dy;
299         rem   = p % dy;
300         if(rem < 0) {
301             lift--;
302             rem += dy;
303         }
304         mod -= dy;
305         while(ey1 != ey2) {
306             delta = lift;
307             mod  += rem;
308             if (mod >= 0) {
309                 mod -= dy;
310                 delta++;
311             }
312             x_to = x_from + delta;
313             render_hline(ey1, x_from, poly_base_size - first, x_to, first);
314             x_from = x_to;
315             ey1 += incr;
316             set_cur_cell(x_from >> poly_base_shift, ey1);
317         }
318     }
319     render_hline(ey1, x_from, poly_base_size - first, x2, fy2);
320 }
321 void outline_aa::move_to(int x, int y)
322 {
323     if(m_sorted) {
324         reset();
325     }
326     set_cur_cell(x >> poly_base_shift, y >> poly_base_shift);
327     m_cur_x = x;
328     m_cur_y = y;
329 }
330 void outline_aa::line_to(int x, int y)
331 {
332     render_line(m_cur_x, m_cur_y, x, y);
333     m_cur_x = x;
334     m_cur_y = y;
335     m_sorted = false;
336 }
337 template <class T> static AGG_INLINE void swap_cells(T* a, T* b)
338 {
339     T temp = *a;
340     *a = *b;
341     *b = temp;
342 }
343 enum {
344     qsort_threshold = 9
345 };
346 static void qsort_cells(cell_aa** start, unsigned num)
347 {
348     cell_aa**  stack[80];
349     cell_aa*** top;
350     cell_aa**  limit;
351     cell_aa**  base;
352     limit = start + num;
353     base  = start;
354     top   = stack;
355     for (;;) {
356         int len = int(limit - base);
357         cell_aa** i;
358         cell_aa** j;
359         cell_aa** pivot;
360         if(len > qsort_threshold) {
361             pivot = base + len / 2;
362             swap_cells(base, pivot);
363             i = base + 1;
364             j = limit - 1;
365             if((*j)->x < (*i)->x) {
366                 swap_cells(i, j);
367             }
368             if((*base)->x < (*i)->x) {
369                 swap_cells(base, i);
370             }
371             if((*j)->x < (*base)->x) {
372                 swap_cells(base, j);
373             }
374             for(;;) {
375                 int x = (*base)->x;
376                 do {
377                     i++;
378                 } while( (*i)->x < x );
379                 do {
380                     j--;
381                 } while( x < (*j)->x );
382                 if(i > j) {
383                     break;
384                 }
385                 swap_cells(i, j);
386             }
387             swap_cells(base, j);
388             if(j - base > limit - i) {
389                 top[0] = base;
390                 top[1] = j;
391                 base   = i;
392             } else {
393                 top[0] = i;
394                 top[1] = limit;
395                 limit  = j;
396             }
397             top += 2;
398         } else {
399             j = base;
400             i = j + 1;
401             for(; i < limit; j = i, i++) {
402                 for(; j[1]->x < (*j)->x; j--) {
403                     swap_cells(j + 1, j);
404                     if (j == base) {
405                         break;
406                     }
407                 }
408             }
409             if(top > stack) {
410                 top  -= 2;
411                 base  = top[0];
412                 limit = top[1];
413             } else {
414                 break;
415             }
416         }
417     }
418 }
419 void outline_aa::sort_cells()
420 {
421     if(m_sorted) {
422         return;
423     }
424     add_cur_cell();
425     if(m_num_cells == 0) {
426         return;
427     }
428     m_sorted_cells.allocate(m_num_cells, 16);
429     if (m_max_y > 0 && m_min_y < 0 && -m_min_y > INT_MAX - m_max_y) {
430         return;
431     }
432     unsigned size = m_max_y - m_min_y;
433     if (size + 1 < size) {
434         return;
435     }
436     size++;
437     m_sorted_y.allocate(size, 16);
438     m_sorted_y.zero();
439     cell_aa** block_ptr = m_cells;
440     cell_aa*  cell_ptr = NULL;
441     unsigned nb = m_num_cells >> cell_block_shift;
442     unsigned i;
443     while(nb--) {
444         cell_ptr = *block_ptr++;
445         i = cell_block_size;
446         while(i--) {
447             m_sorted_y[cell_ptr->y - m_min_y].start++;
448             ++cell_ptr;
449         }
450     }
451     i = m_num_cells & cell_block_mask;
452     if (i) {
453         cell_ptr = *block_ptr++;
454     }
455     while(i--) {
456         m_sorted_y[cell_ptr->y - m_min_y].start++;
457         ++cell_ptr;
458     }
459     unsigned start = 0;
460     for(i = 0; i < m_sorted_y.size(); i++) {
461         unsigned v = m_sorted_y[i].start;
462         m_sorted_y[i].start = start;
463         start += v;
464     }
465     block_ptr = m_cells;
466     nb = m_num_cells >> cell_block_shift;
467     while(nb--) {
468         cell_ptr = *block_ptr++;
469         i = cell_block_size;
470         while(i--) {
471             sorted_y& cur_y = m_sorted_y[cell_ptr->y - m_min_y];
472             m_sorted_cells[cur_y.start + cur_y.num] = cell_ptr;
473             ++cur_y.num;
474             ++cell_ptr;
475         }
476     }
477     i = m_num_cells & cell_block_mask;
478     if (i) {
479         cell_ptr = *block_ptr++;
480     }
481     while(i--) {
482         sorted_y& cur_y = m_sorted_y[cell_ptr->y - m_min_y];
483         m_sorted_cells[cur_y.start + cur_y.num] = cell_ptr;
484         ++cur_y.num;
485         ++cell_ptr;
486     }
487     for(i = 0; i < m_sorted_y.size(); i++) {
488         const sorted_y& cur_y = m_sorted_y[i];
489         if(cur_y.num) {
490             qsort_cells(m_sorted_cells.data() + cur_y.start, cur_y.num);
491         }
492     }
493     m_sorted = true;
494 }
495 }