• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 <limits.h>
50 #include "agg_rasterizer_scanline_aa.h"
51 #include "third_party/base/numerics/safe_math.h"
52 namespace agg
53 {
set_cover(int c,int a)54 AGG_INLINE void cell_aa::set_cover(int c, int a)
55 {
56     cover = c;
57     area = a;
58 }
add_cover(int c,int a)59 AGG_INLINE void cell_aa::add_cover(int c, int a)
60 {
61     cover += c;
62     area += a;
63 }
set_coord(int cx,int cy)64 AGG_INLINE void cell_aa::set_coord(int cx, int cy)
65 {
66     x = cx;
67     y = cy;
68 }
set(int cx,int cy,int c,int a)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 }
~outline_aa()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 }
outline_aa()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 }
reset()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 }
allocate_block()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               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 }
add_cur_cell()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 }
set_cur_cell(int x,int y)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 }
render_hline(int ey,int x1,int y1,int x2,int y2)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 }
render_line(int x1,int y1,int x2,int y2)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 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     pdfium::base::CheckedNumeric<int> safeP = poly_base_size - fy1;
273     safeP *= dx;
274     if (!safeP.IsValid())
275       return;
276     first = poly_base_size;
277     if(dy < 0) {
278       safeP = fy1;
279       safeP *= dx;
280       if (!safeP.IsValid())
281         return;
282       first = 0;
283       incr = -1;
284       dy = -dy;
285     }
286     delta = (safeP / dy).ValueOrDie();
287     mod = (safeP % dy).ValueOrDie();
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       safeP = static_cast<int>(poly_base_size);
298       safeP *= dx;
299       if (!safeP.IsValid())
300         return;
301       lift = (safeP / dy).ValueOrDie();
302       rem = (safeP % dy).ValueOrDie();
303       if (rem < 0) {
304         lift--;
305         rem += dy;
306         }
307         mod -= dy;
308         while(ey1 != ey2) {
309             delta = lift;
310             mod  += rem;
311             if (mod >= 0) {
312                 mod -= dy;
313                 delta++;
314             }
315             x_to = x_from + delta;
316             render_hline(ey1, x_from, poly_base_size - first, x_to, first);
317             x_from = x_to;
318             ey1 += incr;
319             set_cur_cell(x_from >> poly_base_shift, ey1);
320         }
321     }
322     render_hline(ey1, x_from, poly_base_size - first, x2, fy2);
323 }
move_to(int x,int y)324 void outline_aa::move_to(int x, int y)
325 {
326     if(m_sorted) {
327         reset();
328     }
329     set_cur_cell(x >> poly_base_shift, y >> poly_base_shift);
330     m_cur_x = x;
331     m_cur_y = y;
332 }
line_to(int x,int y)333 void outline_aa::line_to(int x, int y)
334 {
335     render_line(m_cur_x, m_cur_y, x, y);
336     m_cur_x = x;
337     m_cur_y = y;
338     m_sorted = false;
339 }
swap_cells(T * a,T * b)340 template <class T> static AGG_INLINE void swap_cells(T* a, T* b)
341 {
342     T temp = *a;
343     *a = *b;
344     *b = temp;
345 }
346 enum {
347     qsort_threshold = 9
348 };
qsort_cells(cell_aa ** start,unsigned num)349 static void qsort_cells(cell_aa** start, unsigned num)
350 {
351     cell_aa**  stack[80];
352     cell_aa*** top;
353     cell_aa**  limit;
354     cell_aa**  base;
355     limit = start + num;
356     base  = start;
357     top   = stack;
358     for (;;) {
359         int len = int(limit - base);
360         cell_aa** i;
361         cell_aa** j;
362         cell_aa** pivot;
363         if(len > qsort_threshold) {
364             pivot = base + len / 2;
365             swap_cells(base, pivot);
366             i = base + 1;
367             j = limit - 1;
368             if((*j)->x < (*i)->x) {
369                 swap_cells(i, j);
370             }
371             if((*base)->x < (*i)->x) {
372                 swap_cells(base, i);
373             }
374             if((*j)->x < (*base)->x) {
375                 swap_cells(base, j);
376             }
377             for(;;) {
378                 int x = (*base)->x;
379                 do {
380                     i++;
381                 } while( (*i)->x < x );
382                 do {
383                     j--;
384                 } while( x < (*j)->x );
385                 if(i > j) {
386                     break;
387                 }
388                 swap_cells(i, j);
389             }
390             swap_cells(base, j);
391             if(j - base > limit - i) {
392                 top[0] = base;
393                 top[1] = j;
394                 base   = i;
395             } else {
396                 top[0] = i;
397                 top[1] = limit;
398                 limit  = j;
399             }
400             top += 2;
401         } else {
402             j = base;
403             i = j + 1;
404             for(; i < limit; j = i, i++) {
405                 for(; j[1]->x < (*j)->x; j--) {
406                     swap_cells(j + 1, j);
407                     if (j == base) {
408                         break;
409                     }
410                 }
411             }
412             if(top > stack) {
413                 top  -= 2;
414                 base  = top[0];
415                 limit = top[1];
416             } else {
417                 break;
418             }
419         }
420     }
421 }
sort_cells()422 void outline_aa::sort_cells()
423 {
424     if(m_sorted) {
425         return;
426     }
427     add_cur_cell();
428     if(m_num_cells == 0) {
429         return;
430     }
431     m_sorted_cells.allocate(m_num_cells, 16);
432     if (m_max_y > 0 && m_min_y < 0 && -m_min_y > INT_MAX - m_max_y) {
433         return;
434     }
435     unsigned size = m_max_y - m_min_y;
436     if (size + 1 < size) {
437         return;
438     }
439     size++;
440     m_sorted_y.allocate(size, 16);
441     m_sorted_y.zero();
442     cell_aa** block_ptr = m_cells;
443     cell_aa*  cell_ptr = NULL;
444     unsigned nb = m_num_cells >> cell_block_shift;
445     unsigned i;
446     while(nb--) {
447         cell_ptr = *block_ptr++;
448         i = cell_block_size;
449         while(i--) {
450             m_sorted_y[cell_ptr->y - m_min_y].start++;
451             ++cell_ptr;
452         }
453     }
454     i = m_num_cells & cell_block_mask;
455     if (i) {
456         cell_ptr = *block_ptr++;
457     }
458     while(i--) {
459         m_sorted_y[cell_ptr->y - m_min_y].start++;
460         ++cell_ptr;
461     }
462     unsigned start = 0;
463     for(i = 0; i < m_sorted_y.size(); i++) {
464         unsigned v = m_sorted_y[i].start;
465         m_sorted_y[i].start = start;
466         start += v;
467     }
468     block_ptr = m_cells;
469     nb = m_num_cells >> cell_block_shift;
470     while(nb--) {
471         cell_ptr = *block_ptr++;
472         i = cell_block_size;
473         while(i--) {
474             sorted_y& cur_y = m_sorted_y[cell_ptr->y - m_min_y];
475             m_sorted_cells[cur_y.start + cur_y.num] = cell_ptr;
476             ++cur_y.num;
477             ++cell_ptr;
478         }
479     }
480     i = m_num_cells & cell_block_mask;
481     if (i) {
482         cell_ptr = *block_ptr++;
483     }
484     while(i--) {
485         sorted_y& cur_y = m_sorted_y[cell_ptr->y - m_min_y];
486         m_sorted_cells[cur_y.start + cur_y.num] = cell_ptr;
487         ++cur_y.num;
488         ++cell_ptr;
489     }
490     for(i = 0; i < m_sorted_y.size(); i++) {
491         const sorted_y& cur_y = m_sorted_y[i];
492         if(cur_y.num) {
493             qsort_cells(m_sorted_cells.data() + cur_y.start, cur_y.num);
494         }
495     }
496     m_sorted = true;
497 }
498 }
499