Anti-Grain Geometry - AGG (libagg)
2.5
|
00001 //---------------------------------------------------------------------------- 00002 // Anti-Grain Geometry (AGG) - Version 2.5 00003 // A high quality rendering engine for C++ 00004 // Copyright (C) 2002-2006 Maxim Shemanarev 00005 // Contact: mcseem@antigrain.com 00006 // mcseemagg@yahoo.com 00007 // http://antigrain.com 00008 // 00009 // AGG is free software; you can redistribute it and/or 00010 // modify it under the terms of the GNU General Public License 00011 // as published by the Free Software Foundation; either version 2 00012 // of the License, or (at your option) any later version. 00013 // 00014 // AGG is distributed in the hope that it will be useful, 00015 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00016 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00017 // GNU General Public License for more details. 00018 // 00019 // You should have received a copy of the GNU General Public License 00020 // along with AGG; if not, write to the Free Software 00021 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, 00022 // MA 02110-1301, USA. 00023 //---------------------------------------------------------------------------- 00024 // 00025 // The author gratefully acknowleges the support of David Turner, 00026 // Robert Wilhelm, and Werner Lemberg - the authors of the FreeType 00027 // libray - in producing this work. See http://www.freetype.org for details. 00028 // 00029 //---------------------------------------------------------------------------- 00030 // 00031 // Adaptation for 32-bit screen coordinates has been sponsored by 00032 // Liberty Technology Systems, Inc., visit http://lib-sys.com 00033 // 00034 // Liberty Technology Systems, Inc. is the provider of 00035 // PostScript and PDF technology for software developers. 00036 // 00037 //---------------------------------------------------------------------------- 00038 00039 #ifndef AGG_RASTERIZER_CELLS_AA_INCLUDED 00040 #define AGG_RASTERIZER_CELLS_AA_INCLUDED 00041 00042 #include <string.h> 00043 #include <math.h> 00044 #include "agg_math.h" 00045 #include "agg_array.h" 00046 00047 00048 namespace agg 00049 { 00050 00051 //-----------------------------------------------------rasterizer_cells_aa 00052 // An internal class that implements the main rasterization algorithm. 00053 // Used in the rasterizer. Should not be used direcly. 00054 template<class Cell> class rasterizer_cells_aa 00055 { 00056 enum cell_block_scale_e 00057 { 00058 cell_block_shift = 12, 00059 cell_block_size = 1 << cell_block_shift, 00060 cell_block_mask = cell_block_size - 1, 00061 cell_block_pool = 256, 00062 cell_block_limit = 1024 00063 }; 00064 00065 struct sorted_y 00066 { 00067 unsigned start; 00068 unsigned num; 00069 }; 00070 00071 public: 00072 typedef Cell cell_type; 00073 typedef rasterizer_cells_aa<Cell> self_type; 00074 00075 ~rasterizer_cells_aa(); 00076 rasterizer_cells_aa(); 00077 00078 void reset(); 00079 void style(const cell_type& style_cell); 00080 void line(int x1, int y1, int x2, int y2); 00081 00082 int min_x() const { return m_min_x; } 00083 int min_y() const { return m_min_y; } 00084 int max_x() const { return m_max_x; } 00085 int max_y() const { return m_max_y; } 00086 00087 void sort_cells(); 00088 00089 unsigned total_cells() const 00090 { 00091 return m_num_cells; 00092 } 00093 00094 unsigned scanline_num_cells(unsigned y) const 00095 { 00096 return m_sorted_y[y - m_min_y].num; 00097 } 00098 00099 const cell_type* const* scanline_cells(unsigned y) const 00100 { 00101 return m_sorted_cells.data() + m_sorted_y[y - m_min_y].start; 00102 } 00103 00104 bool sorted() const { return m_sorted; } 00105 00106 private: 00107 rasterizer_cells_aa(const self_type&); 00108 const self_type& operator = (const self_type&); 00109 00110 void set_curr_cell(int x, int y); 00111 void add_curr_cell(); 00112 void render_hline(int ey, int x1, int y1, int x2, int y2); 00113 void allocate_block(); 00114 00115 private: 00116 unsigned m_num_blocks; 00117 unsigned m_max_blocks; 00118 unsigned m_curr_block; 00119 unsigned m_num_cells; 00120 cell_type** m_cells; 00121 cell_type* m_curr_cell_ptr; 00122 pod_vector<cell_type*> m_sorted_cells; 00123 pod_vector<sorted_y> m_sorted_y; 00124 cell_type m_curr_cell; 00125 cell_type m_style_cell; 00126 int m_min_x; 00127 int m_min_y; 00128 int m_max_x; 00129 int m_max_y; 00130 bool m_sorted; 00131 }; 00132 00133 00134 00135 00136 //------------------------------------------------------------------------ 00137 template<class Cell> 00138 rasterizer_cells_aa<Cell>::~rasterizer_cells_aa() 00139 { 00140 if(m_num_blocks) 00141 { 00142 cell_type** ptr = m_cells + m_num_blocks - 1; 00143 while(m_num_blocks--) 00144 { 00145 pod_allocator<cell_type>::deallocate(*ptr, cell_block_size); 00146 ptr--; 00147 } 00148 pod_allocator<cell_type*>::deallocate(m_cells, m_max_blocks); 00149 } 00150 } 00151 00152 //------------------------------------------------------------------------ 00153 template<class Cell> 00154 rasterizer_cells_aa<Cell>::rasterizer_cells_aa() : 00155 m_num_blocks(0), 00156 m_max_blocks(0), 00157 m_curr_block(0), 00158 m_num_cells(0), 00159 m_cells(0), 00160 m_curr_cell_ptr(0), 00161 m_sorted_cells(), 00162 m_sorted_y(), 00163 m_min_x(0x7FFFFFFF), 00164 m_min_y(0x7FFFFFFF), 00165 m_max_x(-0x7FFFFFFF), 00166 m_max_y(-0x7FFFFFFF), 00167 m_sorted(false) 00168 { 00169 m_style_cell.initial(); 00170 m_curr_cell.initial(); 00171 } 00172 00173 //------------------------------------------------------------------------ 00174 template<class Cell> 00175 void rasterizer_cells_aa<Cell>::reset() 00176 { 00177 m_num_cells = 0; 00178 m_curr_block = 0; 00179 m_curr_cell.initial(); 00180 m_style_cell.initial(); 00181 m_sorted = false; 00182 m_min_x = 0x7FFFFFFF; 00183 m_min_y = 0x7FFFFFFF; 00184 m_max_x = -0x7FFFFFFF; 00185 m_max_y = -0x7FFFFFFF; 00186 } 00187 00188 //------------------------------------------------------------------------ 00189 template<class Cell> 00190 AGG_INLINE void rasterizer_cells_aa<Cell>::add_curr_cell() 00191 { 00192 if(m_curr_cell.area | m_curr_cell.cover) 00193 { 00194 if((m_num_cells & cell_block_mask) == 0) 00195 { 00196 if(m_num_blocks >= cell_block_limit) return; 00197 allocate_block(); 00198 } 00199 *m_curr_cell_ptr++ = m_curr_cell; 00200 ++m_num_cells; 00201 } 00202 } 00203 00204 //------------------------------------------------------------------------ 00205 template<class Cell> 00206 AGG_INLINE void rasterizer_cells_aa<Cell>::set_curr_cell(int x, int y) 00207 { 00208 if(m_curr_cell.not_equal(x, y, m_style_cell)) 00209 { 00210 add_curr_cell(); 00211 m_curr_cell.style(m_style_cell); 00212 m_curr_cell.x = x; 00213 m_curr_cell.y = y; 00214 m_curr_cell.cover = 0; 00215 m_curr_cell.area = 0; 00216 } 00217 } 00218 00219 //------------------------------------------------------------------------ 00220 template<class Cell> 00221 AGG_INLINE void rasterizer_cells_aa<Cell>::render_hline(int ey, 00222 int x1, int y1, 00223 int x2, int y2) 00224 { 00225 int ex1 = x1 >> poly_subpixel_shift; 00226 int ex2 = x2 >> poly_subpixel_shift; 00227 int fx1 = x1 & poly_subpixel_mask; 00228 int fx2 = x2 & poly_subpixel_mask; 00229 00230 int delta, p, first, dx; 00231 int incr, lift, mod, rem; 00232 00233 //trivial case. Happens often 00234 if(y1 == y2) 00235 { 00236 set_curr_cell(ex2, ey); 00237 return; 00238 } 00239 00240 //everything is located in a single cell. That is easy! 00241 if(ex1 == ex2) 00242 { 00243 delta = y2 - y1; 00244 m_curr_cell.cover += delta; 00245 m_curr_cell.area += (fx1 + fx2) * delta; 00246 return; 00247 } 00248 00249 //ok, we'll have to render a run of adjacent cells on the same 00250 //hline... 00251 p = (poly_subpixel_scale - fx1) * (y2 - y1); 00252 first = poly_subpixel_scale; 00253 incr = 1; 00254 00255 dx = x2 - x1; 00256 00257 if(dx < 0) 00258 { 00259 p = fx1 * (y2 - y1); 00260 first = 0; 00261 incr = -1; 00262 dx = -dx; 00263 } 00264 00265 delta = p / dx; 00266 mod = p % dx; 00267 00268 if(mod < 0) 00269 { 00270 delta--; 00271 mod += dx; 00272 } 00273 00274 m_curr_cell.cover += delta; 00275 m_curr_cell.area += (fx1 + first) * delta; 00276 00277 ex1 += incr; 00278 set_curr_cell(ex1, ey); 00279 y1 += delta; 00280 00281 if(ex1 != ex2) 00282 { 00283 p = poly_subpixel_scale * (y2 - y1 + delta); 00284 lift = p / dx; 00285 rem = p % dx; 00286 00287 if (rem < 0) 00288 { 00289 lift--; 00290 rem += dx; 00291 } 00292 00293 mod -= dx; 00294 00295 while (ex1 != ex2) 00296 { 00297 delta = lift; 00298 mod += rem; 00299 if(mod >= 0) 00300 { 00301 mod -= dx; 00302 delta++; 00303 } 00304 00305 m_curr_cell.cover += delta; 00306 m_curr_cell.area += poly_subpixel_scale * delta; 00307 y1 += delta; 00308 ex1 += incr; 00309 set_curr_cell(ex1, ey); 00310 } 00311 } 00312 delta = y2 - y1; 00313 m_curr_cell.cover += delta; 00314 m_curr_cell.area += (fx2 + poly_subpixel_scale - first) * delta; 00315 } 00316 00317 //------------------------------------------------------------------------ 00318 template<class Cell> 00319 AGG_INLINE void rasterizer_cells_aa<Cell>::style(const cell_type& style_cell) 00320 { 00321 m_style_cell.style(style_cell); 00322 } 00323 00324 //------------------------------------------------------------------------ 00325 template<class Cell> 00326 void rasterizer_cells_aa<Cell>::line(int x1, int y1, int x2, int y2) 00327 { 00328 enum dx_limit_e { dx_limit = 16384 << poly_subpixel_shift }; 00329 00330 int dx = x2 - x1; 00331 00332 if(dx >= dx_limit || dx <= -dx_limit) 00333 { 00334 int cx = (x1 + x2) >> 1; 00335 int cy = (y1 + y2) >> 1; 00336 line(x1, y1, cx, cy); 00337 line(cx, cy, x2, y2); 00338 } 00339 00340 int dy = y2 - y1; 00341 int ex1 = x1 >> poly_subpixel_shift; 00342 int ex2 = x2 >> poly_subpixel_shift; 00343 int ey1 = y1 >> poly_subpixel_shift; 00344 int ey2 = y2 >> poly_subpixel_shift; 00345 int fy1 = y1 & poly_subpixel_mask; 00346 int fy2 = y2 & poly_subpixel_mask; 00347 00348 int x_from, x_to; 00349 int p, rem, mod, lift, delta, first, incr; 00350 00351 if(ex1 < m_min_x) m_min_x = ex1; 00352 if(ex1 > m_max_x) m_max_x = ex1; 00353 if(ey1 < m_min_y) m_min_y = ey1; 00354 if(ey1 > m_max_y) m_max_y = ey1; 00355 if(ex2 < m_min_x) m_min_x = ex2; 00356 if(ex2 > m_max_x) m_max_x = ex2; 00357 if(ey2 < m_min_y) m_min_y = ey2; 00358 if(ey2 > m_max_y) m_max_y = ey2; 00359 00360 set_curr_cell(ex1, ey1); 00361 00362 //everything is on a single hline 00363 if(ey1 == ey2) 00364 { 00365 render_hline(ey1, x1, fy1, x2, fy2); 00366 return; 00367 } 00368 00369 //Vertical line - we have to calculate start and end cells, 00370 //and then - the common values of the area and coverage for 00371 //all cells of the line. We know exactly there's only one 00372 //cell, so, we don't have to call render_hline(). 00373 incr = 1; 00374 if(dx == 0) 00375 { 00376 int ex = x1 >> poly_subpixel_shift; 00377 int two_fx = (x1 - (ex << poly_subpixel_shift)) << 1; 00378 int area; 00379 00380 first = poly_subpixel_scale; 00381 if(dy < 0) 00382 { 00383 first = 0; 00384 incr = -1; 00385 } 00386 00387 x_from = x1; 00388 00389 //render_hline(ey1, x_from, fy1, x_from, first); 00390 delta = first - fy1; 00391 m_curr_cell.cover += delta; 00392 m_curr_cell.area += two_fx * delta; 00393 00394 ey1 += incr; 00395 set_curr_cell(ex, ey1); 00396 00397 delta = first + first - poly_subpixel_scale; 00398 area = two_fx * delta; 00399 while(ey1 != ey2) 00400 { 00401 //render_hline(ey1, x_from, poly_subpixel_scale - first, x_from, first); 00402 m_curr_cell.cover = delta; 00403 m_curr_cell.area = area; 00404 ey1 += incr; 00405 set_curr_cell(ex, ey1); 00406 } 00407 //render_hline(ey1, x_from, poly_subpixel_scale - first, x_from, fy2); 00408 delta = fy2 - poly_subpixel_scale + first; 00409 m_curr_cell.cover += delta; 00410 m_curr_cell.area += two_fx * delta; 00411 return; 00412 } 00413 00414 //ok, we have to render several hlines 00415 p = (poly_subpixel_scale - fy1) * dx; 00416 first = poly_subpixel_scale; 00417 00418 if(dy < 0) 00419 { 00420 p = fy1 * dx; 00421 first = 0; 00422 incr = -1; 00423 dy = -dy; 00424 } 00425 00426 delta = p / dy; 00427 mod = p % dy; 00428 00429 if(mod < 0) 00430 { 00431 delta--; 00432 mod += dy; 00433 } 00434 00435 x_from = x1 + delta; 00436 render_hline(ey1, x1, fy1, x_from, first); 00437 00438 ey1 += incr; 00439 set_curr_cell(x_from >> poly_subpixel_shift, ey1); 00440 00441 if(ey1 != ey2) 00442 { 00443 p = poly_subpixel_scale * dx; 00444 lift = p / dy; 00445 rem = p % dy; 00446 00447 if(rem < 0) 00448 { 00449 lift--; 00450 rem += dy; 00451 } 00452 mod -= dy; 00453 00454 while(ey1 != ey2) 00455 { 00456 delta = lift; 00457 mod += rem; 00458 if (mod >= 0) 00459 { 00460 mod -= dy; 00461 delta++; 00462 } 00463 00464 x_to = x_from + delta; 00465 render_hline(ey1, x_from, poly_subpixel_scale - first, x_to, first); 00466 x_from = x_to; 00467 00468 ey1 += incr; 00469 set_curr_cell(x_from >> poly_subpixel_shift, ey1); 00470 } 00471 } 00472 render_hline(ey1, x_from, poly_subpixel_scale - first, x2, fy2); 00473 } 00474 00475 //------------------------------------------------------------------------ 00476 template<class Cell> 00477 void rasterizer_cells_aa<Cell>::allocate_block() 00478 { 00479 if(m_curr_block >= m_num_blocks) 00480 { 00481 if(m_num_blocks >= m_max_blocks) 00482 { 00483 cell_type** new_cells = 00484 pod_allocator<cell_type*>::allocate(m_max_blocks + 00485 cell_block_pool); 00486 00487 if(m_cells) 00488 { 00489 memcpy(new_cells, m_cells, m_max_blocks * sizeof(cell_type*)); 00490 pod_allocator<cell_type*>::deallocate(m_cells, m_max_blocks); 00491 } 00492 m_cells = new_cells; 00493 m_max_blocks += cell_block_pool; 00494 } 00495 00496 m_cells[m_num_blocks++] = 00497 pod_allocator<cell_type>::allocate(cell_block_size); 00498 00499 } 00500 m_curr_cell_ptr = m_cells[m_curr_block++]; 00501 } 00502 00503 00504 00505 //------------------------------------------------------------------------ 00506 template <class T> static AGG_INLINE void swap_cells(T* a, T* b) 00507 { 00508 T temp = *a; 00509 *a = *b; 00510 *b = temp; 00511 } 00512 00513 00514 //------------------------------------------------------------------------ 00515 enum 00516 { 00517 qsort_threshold = 9 00518 }; 00519 00520 00521 //------------------------------------------------------------------------ 00522 template<class Cell> 00523 void qsort_cells(Cell** start, unsigned num) 00524 { 00525 Cell** stack[80]; 00526 Cell*** top; 00527 Cell** limit; 00528 Cell** base; 00529 00530 limit = start + num; 00531 base = start; 00532 top = stack; 00533 00534 for (;;) 00535 { 00536 int len = int(limit - base); 00537 00538 Cell** i; 00539 Cell** j; 00540 Cell** pivot; 00541 00542 if(len > qsort_threshold) 00543 { 00544 // we use base + len/2 as the pivot 00545 pivot = base + len / 2; 00546 swap_cells(base, pivot); 00547 00548 i = base + 1; 00549 j = limit - 1; 00550 00551 // now ensure that *i <= *base <= *j 00552 if((*j)->x < (*i)->x) 00553 { 00554 swap_cells(i, j); 00555 } 00556 00557 if((*base)->x < (*i)->x) 00558 { 00559 swap_cells(base, i); 00560 } 00561 00562 if((*j)->x < (*base)->x) 00563 { 00564 swap_cells(base, j); 00565 } 00566 00567 for(;;) 00568 { 00569 int x = (*base)->x; 00570 do i++; while( (*i)->x < x ); 00571 do j--; while( x < (*j)->x ); 00572 00573 if(i > j) 00574 { 00575 break; 00576 } 00577 00578 swap_cells(i, j); 00579 } 00580 00581 swap_cells(base, j); 00582 00583 // now, push the largest sub-array 00584 if(j - base > limit - i) 00585 { 00586 top[0] = base; 00587 top[1] = j; 00588 base = i; 00589 } 00590 else 00591 { 00592 top[0] = i; 00593 top[1] = limit; 00594 limit = j; 00595 } 00596 top += 2; 00597 } 00598 else 00599 { 00600 // the sub-array is small, perform insertion sort 00601 j = base; 00602 i = j + 1; 00603 00604 for(; i < limit; j = i, i++) 00605 { 00606 for(; j[1]->x < (*j)->x; j--) 00607 { 00608 swap_cells(j + 1, j); 00609 if (j == base) 00610 { 00611 break; 00612 } 00613 } 00614 } 00615 00616 if(top > stack) 00617 { 00618 top -= 2; 00619 base = top[0]; 00620 limit = top[1]; 00621 } 00622 else 00623 { 00624 break; 00625 } 00626 } 00627 } 00628 } 00629 00630 00631 //------------------------------------------------------------------------ 00632 template<class Cell> 00633 void rasterizer_cells_aa<Cell>::sort_cells() 00634 { 00635 if(m_sorted) return; //Perform sort only the first time. 00636 00637 add_curr_cell(); 00638 m_curr_cell.x = 0x7FFFFFFF; 00639 m_curr_cell.y = 0x7FFFFFFF; 00640 m_curr_cell.cover = 0; 00641 m_curr_cell.area = 0; 00642 00643 if(m_num_cells == 0) return; 00644 00645 // DBG: Check to see if min/max works well. 00646 //for(unsigned nc = 0; nc < m_num_cells; nc++) 00647 //{ 00648 // cell_type* cell = m_cells[nc >> cell_block_shift] + (nc & cell_block_mask); 00649 // if(cell->x < m_min_x || 00650 // cell->y < m_min_y || 00651 // cell->x > m_max_x || 00652 // cell->y > m_max_y) 00653 // { 00654 // cell = cell; // Breakpoint here 00655 // } 00656 //} 00657 // Allocate the array of cell pointers 00658 m_sorted_cells.allocate(m_num_cells, 16); 00659 00660 // Allocate and zero the Y array 00661 m_sorted_y.allocate(m_max_y - m_min_y + 1, 16); 00662 m_sorted_y.zero(); 00663 00664 // Create the Y-histogram (count the numbers of cells for each Y) 00665 cell_type** block_ptr = m_cells; 00666 cell_type* cell_ptr; 00667 unsigned nb = m_num_cells >> cell_block_shift; 00668 unsigned i; 00669 while(nb--) 00670 { 00671 cell_ptr = *block_ptr++; 00672 i = cell_block_size; 00673 while(i--) 00674 { 00675 m_sorted_y[cell_ptr->y - m_min_y].start++; 00676 ++cell_ptr; 00677 } 00678 } 00679 00680 cell_ptr = *block_ptr++; 00681 i = m_num_cells & cell_block_mask; 00682 while(i--) 00683 { 00684 m_sorted_y[cell_ptr->y - m_min_y].start++; 00685 ++cell_ptr; 00686 } 00687 00688 // Convert the Y-histogram into the array of starting indexes 00689 unsigned start = 0; 00690 for(i = 0; i < m_sorted_y.size(); i++) 00691 { 00692 unsigned v = m_sorted_y[i].start; 00693 m_sorted_y[i].start = start; 00694 start += v; 00695 } 00696 00697 // Fill the cell pointer array sorted by Y 00698 block_ptr = m_cells; 00699 nb = m_num_cells >> cell_block_shift; 00700 while(nb--) 00701 { 00702 cell_ptr = *block_ptr++; 00703 i = cell_block_size; 00704 while(i--) 00705 { 00706 sorted_y& curr_y = m_sorted_y[cell_ptr->y - m_min_y]; 00707 m_sorted_cells[curr_y.start + curr_y.num] = cell_ptr; 00708 ++curr_y.num; 00709 ++cell_ptr; 00710 } 00711 } 00712 00713 cell_ptr = *block_ptr++; 00714 i = m_num_cells & cell_block_mask; 00715 while(i--) 00716 { 00717 sorted_y& curr_y = m_sorted_y[cell_ptr->y - m_min_y]; 00718 m_sorted_cells[curr_y.start + curr_y.num] = cell_ptr; 00719 ++curr_y.num; 00720 ++cell_ptr; 00721 } 00722 00723 // Finally arrange the X-arrays 00724 for(i = 0; i < m_sorted_y.size(); i++) 00725 { 00726 const sorted_y& curr_y = m_sorted_y[i]; 00727 if(curr_y.num) 00728 { 00729 qsort_cells(m_sorted_cells.data() + curr_y.start, curr_y.num); 00730 } 00731 } 00732 m_sorted = true; 00733 } 00734 00735 00736 00737 //------------------------------------------------------scanline_hit_test 00738 class scanline_hit_test 00739 { 00740 public: 00741 scanline_hit_test(int x) : m_x(x), m_hit(false) {} 00742 00743 void reset_spans() {} 00744 void finalize(int) {} 00745 void add_cell(int x, int) 00746 { 00747 if(m_x == x) m_hit = true; 00748 } 00749 void add_span(int x, int len, int) 00750 { 00751 if(m_x >= x && m_x < x+len) m_hit = true; 00752 } 00753 unsigned num_spans() const { return 1; } 00754 bool hit() const { return m_hit; } 00755 00756 private: 00757 int m_x; 00758 bool m_hit; 00759 }; 00760 00761 00762 } 00763 00764 #endif