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