1bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 2bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant//---------------------------------------------------------------------------- 3f5256e16dfc425c1d466f6308d4026d529ce9e0bHoward Hinnant// XYQ: 2006-01-22 Copied from AGG project. 4bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// This file uses only integer data, so it's suitable for all platforms. 5b64f8b07c104c6cc986570ac8ee0ed16a9f23976Howard Hinnant//---------------------------------------------------------------------------- 6b64f8b07c104c6cc986570ac8ee0ed16a9f23976Howard Hinnant//---------------------------------------------------------------------------- 7bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// Anti-Grain Geometry - Version 2.3 8bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// Copyright (C) 2002-2005 Maxim Shemanarev (http://www.antigrain.com) 9bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// 10bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// Permission to copy, use, modify, sell and distribute this software 11bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// is granted provided this copyright notice appears in all copies. 12bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// This software is provided "as is" without express or implied 13bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// warranty, and with no claim as to its suitability for any purpose. 14212714f805dc3b00e351b1556395f18c5ae70c25Eric Fiselier// 15bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant//---------------------------------------------------------------------------- 16bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// 17bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// The author gratefully acknowleges the support of David Turner, 18bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// Robert Wilhelm, and Werner Lemberg - the authors of the FreeType 19bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// libray - in producing this work. See http://www.freetype.org for details. 20bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// 21bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant//---------------------------------------------------------------------------- 22bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// Contact: mcseem@antigrain.com 23bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// mcseemagg@yahoo.com 24bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// http://www.antigrain.com 25bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant//---------------------------------------------------------------------------- 26bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// 27bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// Adaptation for 32-bit screen coordinates has been sponsored by 28bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// Liberty Technology Systems, Inc., visit http://lib-sys.com 29bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// 30bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// Liberty Technology Systems, Inc. is the provider of 31bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// PostScript and PDF technology for software developers. 32bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// 33bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant//---------------------------------------------------------------------------- 34bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// 35bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// Class outline_aa - implementation. 36bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// 37bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// Initially the rendering algorithm was designed by David Turner and the 38bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// other authors of the FreeType library - see the above notice. I nearly 39bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// created a similar renderer, but still I was far from David's work. 40bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// I completely redesigned the original code and adapted it for Anti-Grain 41bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// ideas. Two functions - render_line and render_hline are the core of 42bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// the algorithm - they calculate the exact coverage of each pixel cell 43bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// of the polygon. I left these functions almost as is, because there's 44bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// no way to improve the perfection - hats off to David and his group! 45bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// 46bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// All other code is very different from the original. 47bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// 48bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant//---------------------------------------------------------------------------- 49bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant#include <limits.h> 50bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant#include "agg_rasterizer_scanline_aa.h" 51bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnantnamespace agg 52bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant{ 53bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard HinnantAGG_INLINE void cell_aa::set_cover(int c, int a) 54bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant{ 55bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant cover = c; 56bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant area = a; 57bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant} 58bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard HinnantAGG_INLINE void cell_aa::add_cover(int c, int a) 59bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant{ 60bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant cover += c; 61bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant area += a; 62bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant} 63bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard HinnantAGG_INLINE void cell_aa::set_coord(int cx, int cy) 64bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant{ 65bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant x = cx; 66bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant y = cy; 67bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant} 68bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard HinnantAGG_INLINE void cell_aa::set(int cx, int cy, int c, int a) 69bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant{ 70bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant x = cx; 71bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant y = cy; 72bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant cover = c; 73bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant area = a; 74bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant} 75bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnantoutline_aa::~outline_aa() 76bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant{ 77bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant if(m_num_blocks) { 78bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant cell_aa** ptr = m_cells + m_num_blocks - 1; 79bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant while(m_num_blocks--) { 80bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant FX_Free(*ptr); 81bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant ptr--; 82212714f805dc3b00e351b1556395f18c5ae70c25Eric Fiselier } 83212714f805dc3b00e351b1556395f18c5ae70c25Eric Fiselier FX_Free(m_cells); 84896baa2547b5e520c72cda5768d3af2d48f50285Howard Hinnant } 85bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant} 86bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnantoutline_aa::outline_aa() : 87bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant m_num_blocks(0), 88bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant m_max_blocks(0), 89212714f805dc3b00e351b1556395f18c5ae70c25Eric Fiselier m_cur_block(0), 90bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant m_num_cells(0), 91212714f805dc3b00e351b1556395f18c5ae70c25Eric Fiselier m_cells(0), 92bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant m_cur_cell_ptr(0), 93bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant m_cur_x(0), 94bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant m_cur_y(0), 95bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant m_min_x(0x7FFFFFFF), 96bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant m_min_y(0x7FFFFFFF), 97bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant m_max_x(-0x7FFFFFFF), 98bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant m_max_y(-0x7FFFFFFF), 99bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant m_sorted(false) 100bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant{ 101bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant m_cur_cell.set(0x7FFF, 0x7FFF, 0, 0); 102bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant} 1030a111118a60290ec0c650fbd0327403c4b118bddHoward Hinnantvoid outline_aa::reset() 104bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant{ 1050a111118a60290ec0c650fbd0327403c4b118bddHoward Hinnant m_num_cells = 0; 1060a111118a60290ec0c650fbd0327403c4b118bddHoward Hinnant m_cur_block = 0; 1070a111118a60290ec0c650fbd0327403c4b118bddHoward Hinnant m_cur_cell.set(0x7FFF, 0x7FFF, 0, 0); 1080a111118a60290ec0c650fbd0327403c4b118bddHoward Hinnant m_sorted = false; 109bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant m_min_x = 0x7FFFFFFF; 110bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant m_min_y = 0x7FFFFFFF; 111bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant m_max_x = -0x7FFFFFFF; 1120a111118a60290ec0c650fbd0327403c4b118bddHoward Hinnant m_max_y = -0x7FFFFFFF; 113bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant} 1140a111118a60290ec0c650fbd0327403c4b118bddHoward Hinnantvoid outline_aa::allocate_block() 1150a111118a60290ec0c650fbd0327403c4b118bddHoward Hinnant{ 116bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant if(m_cur_block >= m_num_blocks) { 117bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant if(m_num_blocks >= m_max_blocks) { 118bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant cell_aa** new_cells = FX_Alloc( cell_aa*, m_max_blocks + cell_block_pool); 119bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant if(m_cells) { 120bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant FXSYS_memcpy(new_cells, m_cells, m_max_blocks * sizeof(cell_aa*)); 121bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant FX_Free(m_cells); 122bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 123212714f805dc3b00e351b1556395f18c5ae70c25Eric Fiselier m_cells = new_cells; 124bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant m_max_blocks += cell_block_pool; 125e48b0c40ad37cb38282e3005cfe1992922768f70Eric Fiselier } 126bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant m_cells[m_num_blocks++] = FX_Alloc(cell_aa, cell_block_size); 127bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 128bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant m_cur_cell_ptr = m_cells[m_cur_block++]; 129bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant} 130bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard HinnantAGG_INLINE void outline_aa::add_cur_cell() 131212714f805dc3b00e351b1556395f18c5ae70c25Eric Fiselier{ 132bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant if(m_cur_cell.area | m_cur_cell.cover) { 133bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant if((m_num_cells & cell_block_mask) == 0) { 134bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant if(m_num_blocks >= cell_block_limit) { 135bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant return; 136bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 137bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant allocate_block(); 138bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 139bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant *m_cur_cell_ptr++ = m_cur_cell; 140bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant ++m_num_cells; 141bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 142} 143AGG_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} 162AGG_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} 224void 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} 314void 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} 323void 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} 330template <class T> static AGG_INLINE void swap_cells(T* a, T* b) 331{ 332 T temp = *a; 333 *a = *b; 334 *b = temp; 335} 336enum { 337 qsort_threshold = 9 338}; 339static 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} 412void 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