osgEarth 2.1.1
|
#include <AGG.h>
Public Member Functions | |
~outline () | |
outline () | |
void | reset () |
void | move_to (int x, int y) |
void | line_to (int x, int y) |
int | min_x () const |
int | min_y () const |
int | max_x () const |
int | max_y () const |
unsigned | num_cells () const |
const cell *const | cells () |
Private Types | |
enum | { cell_block_shift = 12, cell_block_size = 1 << cell_block_shift, cell_block_mask = cell_block_size - 1, cell_block_pool = 256, cell_block_limit = 1024 } |
Private Member Functions | |
outline (const outline &) | |
const outline & | operator= (const outline &) |
void | set_cur_cell (int x, int y) |
void | add_cur_cell () |
void | sort_cells () |
void | render_scanline (int ey, int x1, int y1, int x2, int y2) |
void | render_line (int x1, int y1, int x2, int y2) |
void | allocate_block () |
Static Private Member Functions | |
static void | qsort_cells (cell **start, unsigned num) |
Private Attributes | |
unsigned | m_num_blocks |
unsigned | m_max_blocks |
unsigned | m_cur_block |
unsigned | m_num_cells |
cell ** | m_cells |
cell * | m_cur_cell_ptr |
cell ** | m_sorted_cells |
unsigned | m_sorted_size |
cell | m_cur_cell |
int | m_cur_x |
int | m_cur_y |
int | m_close_x |
int | m_close_y |
int | m_min_x |
int | m_min_y |
int | m_max_x |
int | m_max_y |
unsigned | m_flags |
anonymous enum [private] |
Definition at line 530 of file AGG.h.
{ cell_block_shift = 12, cell_block_size = 1 << cell_block_shift, cell_block_mask = cell_block_size - 1, cell_block_pool = 256, cell_block_limit = 1024 };
agg::outline::~outline | ( | ) |
Definition at line 1470 of file AGG.h.
{ delete [] m_sorted_cells; if(m_num_blocks) { cell** ptr = m_cells + m_num_blocks - 1; while(m_num_blocks--) { delete [] *ptr; ptr--; } delete [] m_cells; } }
agg::outline::outline | ( | ) |
Definition at line 1487 of file AGG.h.
: m_num_blocks(0), m_max_blocks(0), m_cur_block(0), m_num_cells(0), m_cells(0), m_cur_cell_ptr(0), m_sorted_cells(0), m_sorted_size(0), m_cur_x(0), m_cur_y(0), m_close_x(0), m_close_y(0), m_min_x(0x7FFFFFFF), m_min_y(0x7FFFFFFF), m_max_x(-0x7FFFFFFF), m_max_y(-0x7FFFFFFF), m_flags(sort_required) { m_cur_cell.set(0x7FFF, 0x7FFF, 0, 0); }
agg::outline::outline | ( | const outline & | ) | [private] |
void agg::outline::add_cur_cell | ( | ) | [inline, private] |
Definition at line 1549 of file AGG.h.
{ if(m_cur_cell.area | m_cur_cell.cover) { if((m_num_cells & cell_block_mask) == 0) { if(m_num_blocks >= cell_block_limit) return; allocate_block(); } *m_cur_cell_ptr++ = m_cur_cell; m_num_cells++; } }
void agg::outline::allocate_block | ( | ) | [private] |
Definition at line 1527 of file AGG.h.
{ if(m_cur_block >= m_num_blocks) { if(m_num_blocks >= m_max_blocks) { cell** new_cells = new cell* [m_max_blocks + cell_block_pool]; if(m_cells) { memcpy(new_cells, m_cells, m_max_blocks * sizeof(cell*)); delete [] m_cells; } m_cells = new_cells; m_max_blocks += cell_block_pool; } m_cells[m_num_blocks++] = new cell [unsigned(cell_block_size)]; } m_cur_cell_ptr = m_cells[m_cur_block++]; }
const cell *const agg::outline::cells | ( | ) |
Definition at line 2014 of file AGG.h.
{ if(m_flags & not_closed) { line_to(m_close_x, m_close_y); m_flags &= ~not_closed; } //Perform sort only the first time. if(m_flags & sort_required) { add_cur_cell(); if(m_num_cells == 0) return 0; sort_cells(); m_flags &= ~sort_required; } return m_sorted_cells; }
void agg::outline::line_to | ( | int | x, |
int | y | ||
) |
Definition at line 1816 of file AGG.h.
{ if((m_flags & sort_required) && ((m_cur_x ^ x) | (m_cur_y ^ y))) { int c; c = m_cur_x >> poly_base_shift; if(c < m_min_x) m_min_x = c; ++c; if(c > m_max_x) m_max_x = c; c = x >> poly_base_shift; if(c < m_min_x) m_min_x = c; ++c; if(c > m_max_x) m_max_x = c; render_line(m_cur_x, m_cur_y, x, y); m_cur_x = x; m_cur_y = y; m_flags |= not_closed; } }
int agg::outline::max_x | ( | ) | const [inline] |
int agg::outline::max_y | ( | ) | const [inline] |
int agg::outline::min_x | ( | ) | const [inline] |
int agg::outline::min_y | ( | ) | const [inline] |
void agg::outline::move_to | ( | int | x, |
int | y | ||
) |
Definition at line 1804 of file AGG.h.
{ if((m_flags & sort_required) == 0) reset(); if(m_flags & not_closed) line_to(m_close_x, m_close_y); set_cur_cell(x >> poly_base_shift, y >> poly_base_shift); m_close_x = m_cur_x = x; m_close_y = m_cur_y = y; }
unsigned agg::outline::num_cells | ( | ) | const [inline] |
Definition at line 554 of file AGG.h.
{return m_num_cells; }
void agg::outline::qsort_cells | ( | cell ** | start, |
unsigned | num | ||
) | [static, private] |
Definition at line 1863 of file AGG.h.
{ cell** stack[80]; cell*** top; cell** limit; cell** base; limit = start + num; base = start; top = stack; for (;;) { int len = int(limit - base); cell** i; cell** j; cell** pivot; if(len > qsort_threshold) { // we use base + len/2 as the pivot pivot = base + len / 2; swap_cells(base, pivot); i = base + 1; j = limit - 1; // now ensure that *i <= *base <= *j if(less_than(j, i)) { swap_cells(i, j); } if(less_than(base, i)) { swap_cells(base, i); } if(less_than(j, base)) { swap_cells(base, j); } for(;;) { do i++; while( less_than(i, base) ); do j--; while( less_than(base, j) ); if ( i > j ) { break; } swap_cells(i, j); } swap_cells(base, j); // now, push the largest sub-array if(j - base > limit - i) { top[0] = base; top[1] = j; base = i; } else { top[0] = i; top[1] = limit; limit = j; } top += 2; } else { // the sub-array is small, perform insertion sort j = base; i = j + 1; for(; i < limit; j = i, i++) { for(; less_than(j + 1, j); j--) { swap_cells(j + 1, j); if (j == base) { break; } } } if(top > stack) { top -= 2; base = top[0]; limit = top[1]; } else { break; } } } }
void agg::outline::render_line | ( | int | x1, |
int | y1, | ||
int | x2, | ||
int | y2 | ||
) | [private] |
Definition at line 1674 of file AGG.h.
{ int ey1 = y1 >> poly_base_shift; int ey2 = y2 >> poly_base_shift; int fy1 = y1 & poly_base_mask; int fy2 = y2 & poly_base_mask; int dx, dy, x_from, x_to; int p, rem, mod, lift, delta, first, incr; if(ey1 < m_min_y) m_min_y = ey1; if(ey1+1 > m_max_y) m_max_y = ey1+1; if(ey2 < m_min_y) m_min_y = ey2; if(ey2+1 > m_max_y) m_max_y = ey2+1; dx = x2 - x1; dy = y2 - y1; //everything is on a single scanline if(ey1 == ey2) { render_scanline(ey1, x1, fy1, x2, fy2); return; } //Vertical line - we have to calculate start and end cells, //and then - the common values of the area and coverage for //all cells of the line. We know exactly there's only one //cell, so, we don't have to call render_scanline(). incr = 1; if(dx == 0) { int ex = x1 >> poly_base_shift; int two_fx = (x1 - (ex << poly_base_shift)) << 1; int area; first = poly_base_size; if(dy < 0) { first = 0; incr = -1; } x_from = x1; //render_scanline(ey1, x_from, fy1, x_from, first); delta = first - fy1; m_cur_cell.add_cover(delta, two_fx * delta); ey1 += incr; set_cur_cell(ex, ey1); delta = first + first - poly_base_size; area = two_fx * delta; while(ey1 != ey2) { //render_scanline(ey1, x_from, poly_base_size - first, x_from, first); m_cur_cell.set_cover(delta, area); ey1 += incr; set_cur_cell(ex, ey1); } //render_scanline(ey1, x_from, poly_base_size - first, x_from, fy2); delta = fy2 - poly_base_size + first; m_cur_cell.add_cover(delta, two_fx * delta); return; } //ok, we have to render several scanlines p = (poly_base_size - fy1) * dx; first = poly_base_size; if(dy < 0) { p = fy1 * dx; first = 0; incr = -1; dy = -dy; } delta = p / dy; mod = p % dy; if(mod < 0) { delta--; mod += dy; } x_from = x1 + delta; render_scanline(ey1, x1, fy1, x_from, first); ey1 += incr; set_cur_cell(x_from >> poly_base_shift, ey1); if(ey1 != ey2) { p = poly_base_size * dx; lift = p / dy; rem = p % dy; if(rem < 0) { lift--; rem += dy; } mod -= dy; while(ey1 != ey2) { delta = lift; mod += rem; if (mod >= 0) { mod -= dy; delta++; } x_to = x_from + delta; render_scanline(ey1, x_from, poly_base_size - first, x_to, first); x_from = x_to; ey1 += incr; set_cur_cell(x_from >> poly_base_shift, ey1); } } render_scanline(ey1, x_from, poly_base_size - first, x2, fy2); }
void agg::outline::render_scanline | ( | int | ey, |
int | x1, | ||
int | y1, | ||
int | x2, | ||
int | y2 | ||
) | [inline, private] |
Definition at line 1578 of file AGG.h.
{ int ex1 = x1 >> poly_base_shift; int ex2 = x2 >> poly_base_shift; int fx1 = x1 & poly_base_mask; int fx2 = x2 & poly_base_mask; int delta, p, first, dx; int incr, lift, mod, rem; //trivial case. Happens often if(y1 == y2) { set_cur_cell(ex2, ey); return; } //everything is located in a single cell. That is easy! if(ex1 == ex2) { delta = y2 - y1; m_cur_cell.add_cover(delta, (fx1 + fx2) * delta); return; } //ok, we'll have to render a run of adjacent cells on the same //scanline... p = (poly_base_size - fx1) * (y2 - y1); first = poly_base_size; incr = 1; dx = x2 - x1; if(dx < 0) { p = fx1 * (y2 - y1); first = 0; incr = -1; dx = -dx; } delta = p / dx; mod = p % dx; if(mod < 0) { delta--; mod += dx; } m_cur_cell.add_cover(delta, (fx1 + first) * delta); ex1 += incr; set_cur_cell(ex1, ey); y1 += delta; if(ex1 != ex2) { p = poly_base_size * (y2 - y1 + delta); lift = p / dx; rem = p % dx; if (rem < 0) { lift--; rem += dx; } mod -= dx; while (ex1 != ex2) { delta = lift; mod += rem; if(mod >= 0) { mod -= dx; delta++; } m_cur_cell.add_cover(delta, (poly_base_size) * delta); y1 += delta; ex1 += incr; set_cur_cell(ex1, ey); } } delta = y2 - y1; m_cur_cell.add_cover(delta, (fx2 + poly_base_size - first) * delta); }
void agg::outline::reset | ( | ) |
Definition at line 1511 of file AGG.h.
{ m_num_cells = 0; m_cur_block = 0; m_cur_cell.set(0x7FFF, 0x7FFF, 0, 0); m_flags |= sort_required; m_flags &= ~not_closed; m_min_x = 0x7FFFFFFF; m_min_y = 0x7FFFFFFF; m_max_x = -0x7FFFFFFF; m_max_y = -0x7FFFFFFF; }
void agg::outline::set_cur_cell | ( | int | x, |
int | y | ||
) | [inline, private] |
Definition at line 1566 of file AGG.h.
{ if(m_cur_cell.packed_coord != (y << 16) + x) { add_cur_cell(); m_cur_cell.set(x, y, 0, 0); } }
void agg::outline::sort_cells | ( | ) | [private] |
Definition at line 1973 of file AGG.h.
{ if(m_num_cells == 0) return; if(m_num_cells > m_sorted_size) { delete [] m_sorted_cells; m_sorted_size = m_num_cells; m_sorted_cells = new cell* [m_num_cells + 1]; } cell** sorted_ptr = m_sorted_cells; cell** block_ptr = m_cells; cell* cell_ptr; unsigned nb = m_num_cells >> cell_block_shift; unsigned i; while(nb--) { cell_ptr = *block_ptr++; i = cell_block_size; while(i--) { *sorted_ptr++ = cell_ptr++; } } cell_ptr = *block_ptr++; i = m_num_cells & cell_block_mask; while(i--) { *sorted_ptr++ = cell_ptr++; } m_sorted_cells[m_num_cells] = 0; qsort_cells(m_sorted_cells, m_num_cells); }
cell** agg::outline::m_cells [private] |
int agg::outline::m_close_x [private] |
int agg::outline::m_close_y [private] |
unsigned agg::outline::m_cur_block [private] |
cell agg::outline::m_cur_cell [private] |
cell* agg::outline::m_cur_cell_ptr [private] |
int agg::outline::m_cur_x [private] |
int agg::outline::m_cur_y [private] |
unsigned agg::outline::m_flags [private] |
unsigned agg::outline::m_max_blocks [private] |
int agg::outline::m_max_x [private] |
int agg::outline::m_max_y [private] |
int agg::outline::m_min_x [private] |
int agg::outline::m_min_y [private] |
unsigned agg::outline::m_num_blocks [private] |
unsigned agg::outline::m_num_cells [private] |
cell** agg::outline::m_sorted_cells [private] |
unsigned agg::outline::m_sorted_size [private] |