Merge to XFA: Separate agg-authored code from fx-authored code.
[pdfium.git] / third_party / agg23 / 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 "../../core/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(m_cells) {
121                 FXSYS_memcpy(new_cells, m_cells, m_max_blocks * sizeof(cell_aa*));
122                 FX_Free(m_cells);
123             }
124             m_cells = new_cells;
125             m_max_blocks += cell_block_pool;
126         }
127         m_cells[m_num_blocks++] = FX_Alloc(cell_aa, cell_block_size);
128     }
129     m_cur_cell_ptr = m_cells[m_cur_block++];
130 }
131 AGG_INLINE void outline_aa::add_cur_cell()
132 {
133     if(m_cur_cell.area | m_cur_cell.cover) {
134         if((m_num_cells & cell_block_mask) == 0) {
135             if(m_num_blocks >= cell_block_limit) {
136                 return;
137             }
138             allocate_block();
139         }
140         *m_cur_cell_ptr++ = m_cur_cell;
141         ++m_num_cells;
142     }
143 }
144 AGG_INLINE void outline_aa::set_cur_cell(int x, int y)
145 {
146     if(m_cur_cell.x != x || m_cur_cell.y != y) {
147         add_cur_cell();
148         m_cur_cell.set(x, y, 0, 0);
149         if(x < m_min_x) {
150             m_min_x = x;
151         }
152         if(x > m_max_x) {
153             m_max_x = x;
154         }
155         if(y < m_min_y) {
156             m_min_y = y;
157         }
158         if(y > m_max_y) {
159             m_max_y = y;
160         }
161     }
162 }
163 AGG_INLINE void outline_aa::render_hline(int ey, int x1, int y1, int x2, int y2)
164 {
165     int ex1 = x1 >> poly_base_shift;
166     int ex2 = x2 >> poly_base_shift;
167     int fx1 = x1 & poly_base_mask;
168     int fx2 = x2 & poly_base_mask;
169     int delta, p, first, dx;
170     int incr, lift, mod, rem;
171     if(y1 == y2) {
172         set_cur_cell(ex2, ey);
173         return;
174     }
175     if(ex1 == ex2) {
176         delta = y2 - y1;
177         m_cur_cell.add_cover(delta, (fx1 + fx2) * delta);
178         return;
179     }
180     p     = (poly_base_size - fx1) * (y2 - y1);
181     first = poly_base_size;
182     incr  = 1;
183     dx = x2 - x1;
184     if(dx < 0) {
185         p     = fx1 * (y2 - y1);
186         first = 0;
187         incr  = -1;
188         dx    = -dx;
189     }
190     delta = p / dx;
191     mod   = p % dx;
192     if(mod < 0) {
193         delta--;
194         mod += dx;
195     }
196     m_cur_cell.add_cover(delta, (fx1 + first) * delta);
197     ex1 += incr;
198     set_cur_cell(ex1, ey);
199     y1  += delta;
200     if(ex1 != ex2) {
201         p     = poly_base_size * (y2 - y1 + delta);
202         lift  = p / dx;
203         rem   = p % dx;
204         if (rem < 0) {
205             lift--;
206             rem += dx;
207         }
208         mod -= dx;
209         while (ex1 != ex2) {
210             delta = lift;
211             mod  += rem;
212             if(mod >= 0) {
213                 mod -= dx;
214                 delta++;
215             }
216             m_cur_cell.add_cover(delta, (poly_base_size) * delta);
217             y1  += delta;
218             ex1 += incr;
219             set_cur_cell(ex1, ey);
220         }
221     }
222     delta = y2 - y1;
223     m_cur_cell.add_cover(delta, (fx2 + poly_base_size - first) * delta);
224 }
225 void outline_aa::render_line(int x1, int y1, int x2, int y2)
226 {
227     enum dx_limit_e { dx_limit = 16384 << poly_base_shift };
228     int dx = x2 - x1;
229     if(dx >= dx_limit || dx <= -dx_limit) {
230         int cx = (x1 + x2) >> 1;
231         int cy = (y1 + y2) >> 1;
232         render_line(x1, y1, cx, cy);
233         render_line(cx, cy, x2, y2);
234     }
235     int dy = y2 - y1;
236     int ey1 = y1 >> poly_base_shift;
237     int ey2 = y2 >> poly_base_shift;
238     int fy1 = y1 & poly_base_mask;
239     int fy2 = y2 & poly_base_mask;
240     int x_from, x_to;
241     int p, rem, mod, lift, delta, first, incr;
242     if(ey1 == ey2) {
243         render_hline(ey1, x1, fy1, x2, fy2);
244         return;
245     }
246     incr  = 1;
247     if(dx == 0) {
248         int ex = x1 >> poly_base_shift;
249         int two_fx = (x1 - (ex << poly_base_shift)) << 1;
250         int area;
251         first = poly_base_size;
252         if(dy < 0) {
253             first = 0;
254             incr  = -1;
255         }
256         x_from = x1;
257         delta = first - fy1;
258         m_cur_cell.add_cover(delta, two_fx * delta);
259         ey1 += incr;
260         set_cur_cell(ex, ey1);
261         delta = first + first - poly_base_size;
262         area = two_fx * delta;
263         while(ey1 != ey2) {
264             m_cur_cell.set_cover(delta, area);
265             ey1 += incr;
266             set_cur_cell(ex, ey1);
267         }
268         delta = fy2 - poly_base_size + first;
269         m_cur_cell.add_cover(delta, two_fx * delta);
270         return;
271     }
272     p     = (poly_base_size - fy1) * dx;
273     first = poly_base_size;
274     if(dy < 0) {
275         p     = fy1 * dx;
276         first = 0;
277         incr  = -1;
278         dy    = -dy;
279     }
280     delta = p / dy;
281     mod   = p % dy;
282     if(mod < 0) {
283         delta--;
284         mod += dy;
285     }
286     x_from = x1 + delta;
287     render_hline(ey1, x1, fy1, x_from, first);
288     ey1 += incr;
289     set_cur_cell(x_from >> poly_base_shift, ey1);
290     if(ey1 != ey2) {
291         p     = poly_base_size * dx;
292         lift  = p / dy;
293         rem   = p % dy;
294         if(rem < 0) {
295             lift--;
296             rem += dy;
297         }
298         mod -= dy;
299         while(ey1 != ey2) {
300             delta = lift;
301             mod  += rem;
302             if (mod >= 0) {
303                 mod -= dy;
304                 delta++;
305             }
306             x_to = x_from + delta;
307             render_hline(ey1, x_from, poly_base_size - first, x_to, first);
308             x_from = x_to;
309             ey1 += incr;
310             set_cur_cell(x_from >> poly_base_shift, ey1);
311         }
312     }
313     render_hline(ey1, x_from, poly_base_size - first, x2, fy2);
314 }
315 void outline_aa::move_to(int x, int y)
316 {
317     if(m_sorted) {
318         reset();
319     }
320     set_cur_cell(x >> poly_base_shift, y >> poly_base_shift);
321     m_cur_x = x;
322     m_cur_y = y;
323 }
324 void outline_aa::line_to(int x, int y)
325 {
326     render_line(m_cur_x, m_cur_y, x, y);
327     m_cur_x = x;
328     m_cur_y = y;
329     m_sorted = false;
330 }
331 template <class T> static AGG_INLINE void swap_cells(T* a, T* b)
332 {
333     T temp = *a;
334     *a = *b;
335     *b = temp;
336 }
337 enum {
338     qsort_threshold = 9
339 };
340 static void qsort_cells(cell_aa** start, unsigned num)
341 {
342     cell_aa**  stack[80];
343     cell_aa*** top;
344     cell_aa**  limit;
345     cell_aa**  base;
346     limit = start + num;
347     base  = start;
348     top   = stack;
349     for (;;) {
350         int len = int(limit - base);
351         cell_aa** i;
352         cell_aa** j;
353         cell_aa** pivot;
354         if(len > qsort_threshold) {
355             pivot = base + len / 2;
356             swap_cells(base, pivot);
357             i = base + 1;
358             j = limit - 1;
359             if((*j)->x < (*i)->x) {
360                 swap_cells(i, j);
361             }
362             if((*base)->x < (*i)->x) {
363                 swap_cells(base, i);
364             }
365             if((*j)->x < (*base)->x) {
366                 swap_cells(base, j);
367             }
368             for(;;) {
369                 int x = (*base)->x;
370                 do {
371                     i++;
372                 } while( (*i)->x < x );
373                 do {
374                     j--;
375                 } while( x < (*j)->x );
376                 if(i > j) {
377                     break;
378                 }
379                 swap_cells(i, j);
380             }
381             swap_cells(base, j);
382             if(j - base > limit - i) {
383                 top[0] = base;
384                 top[1] = j;
385                 base   = i;
386             } else {
387                 top[0] = i;
388                 top[1] = limit;
389                 limit  = j;
390             }
391             top += 2;
392         } else {
393             j = base;
394             i = j + 1;
395             for(; i < limit; j = i, i++) {
396                 for(; j[1]->x < (*j)->x; j--) {
397                     swap_cells(j + 1, j);
398                     if (j == base) {
399                         break;
400                     }
401                 }
402             }
403             if(top > stack) {
404                 top  -= 2;
405                 base  = top[0];
406                 limit = top[1];
407             } else {
408                 break;
409             }
410         }
411     }
412 }
413 void outline_aa::sort_cells()
414 {
415     if(m_sorted) {
416         return;
417     }
418     add_cur_cell();
419     if(m_num_cells == 0) {
420         return;
421     }
422     m_sorted_cells.allocate(m_num_cells, 16);
423     if (m_max_y > 0 && m_min_y < 0 && -m_min_y > INT_MAX - m_max_y) {
424         return;
425     }
426     unsigned size = m_max_y - m_min_y;
427     if (size + 1 < size) {
428         return;
429     }
430     size++;
431     m_sorted_y.allocate(size, 16);
432     m_sorted_y.zero();
433     cell_aa** block_ptr = m_cells;
434     cell_aa*  cell_ptr = NULL;
435     unsigned nb = m_num_cells >> cell_block_shift;
436     unsigned i;
437     while(nb--) {
438         cell_ptr = *block_ptr++;
439         i = cell_block_size;
440         while(i--) {
441             m_sorted_y[cell_ptr->y - m_min_y].start++;
442             ++cell_ptr;
443         }
444     }
445     i = m_num_cells & cell_block_mask;
446     if (i) {
447         cell_ptr = *block_ptr++;
448     }
449     while(i--) {
450         m_sorted_y[cell_ptr->y - m_min_y].start++;
451         ++cell_ptr;
452     }
453     unsigned start = 0;
454     for(i = 0; i < m_sorted_y.size(); i++) {
455         unsigned v = m_sorted_y[i].start;
456         m_sorted_y[i].start = start;
457         start += v;
458     }
459     block_ptr = m_cells;
460     nb = m_num_cells >> cell_block_shift;
461     while(nb--) {
462         cell_ptr = *block_ptr++;
463         i = cell_block_size;
464         while(i--) {
465             sorted_y& cur_y = m_sorted_y[cell_ptr->y - m_min_y];
466             m_sorted_cells[cur_y.start + cur_y.num] = cell_ptr;
467             ++cur_y.num;
468             ++cell_ptr;
469         }
470     }
471     i = m_num_cells & cell_block_mask;
472     if (i) {
473         cell_ptr = *block_ptr++;
474     }
475     while(i--) {
476         sorted_y& cur_y = m_sorted_y[cell_ptr->y - m_min_y];
477         m_sorted_cells[cur_y.start + cur_y.num] = cell_ptr;
478         ++cur_y.num;
479         ++cell_ptr;
480     }
481     for(i = 0; i < m_sorted_y.size(); i++) {
482         const sorted_y& cur_y = m_sorted_y[i];
483         if(cur_y.num) {
484             qsort_cells(m_sorted_cells.data() + cur_y.start, cur_y.num);
485         }
486     }
487     m_sorted = true;
488 }
489 }