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 (at) antigrain.com 23 // mcseemagg (at) 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 { 53 AGG_INLINE void cell_aa::set_cover(int c, int a) 54 { 55 cover = c; 56 area = a; 57 } 58 AGG_INLINE void cell_aa::add_cover(int c, int a) 59 { 60 cover += c; 61 area += a; 62 } 63 AGG_INLINE void cell_aa::set_coord(int cx, int cy) 64 { 65 x = cx; 66 y = cy; 67 } 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 } 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 } 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 } 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 } 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 } 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 } 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 } 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 } 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 } 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 } 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 } 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 }; 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 } 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
