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 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 }
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