agg::rasterizer_cells_aa< Cell > Class Template Reference

#include <src/agg/agg_rasterizer_cells_aa.h>

Inheritance diagram for agg::rasterizer_cells_aa< Cell >:

Collaboration diagram for agg::rasterizer_cells_aa< Cell >:

Classes
struct	sorted_y

Public Types
typedef Cell	cell_type
typedef rasterizer_cells_aa< Cell >	self_type

Public Member Functions
	~rasterizer_cells_aa ()
	rasterizer_cells_aa ()
void	reset ()
void	style (const cell_type &style_cell)
void	line (int x1, int y1, int x2, int y2)
int	min_x () const
int	min_y () const
int	max_x () const
int	max_y () const
void	sort_cells ()
unsigned	total_cells () const
unsigned	scanline_num_cells (unsigned y) const
const cell_type *const *	scanline_cells (unsigned y) const
bool	sorted () const

Private Types
enum	cell_block_scale_e {   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
	rasterizer_cells_aa (const self_type &)
const self_type &	operator= (const self_type &)
void	set_curr_cell (int x, int y)
void	add_curr_cell ()
void	render_hline (int ey, int x1, int y1, int x2, int y2)
void	allocate_block ()

Private Attributes
unsigned	m_num_blocks
unsigned	m_max_blocks
unsigned	m_curr_block
unsigned	m_num_cells
cell_type **	m_cells
cell_type *	m_curr_cell_ptr
pod_vector< cell_type * >	m_sorted_cells
pod_vector< sorted_y >	m_sorted_y
cell_type	m_curr_cell
cell_type	m_style_cell
int	m_min_x
int	m_min_y
int	m_max_x
int	m_max_y
bool	m_sorted

Detailed Description

template<class Cell>
class agg::rasterizer_cells_aa< Cell >

---

Class Documentation

agg::rasterizer_cells_aa::sorted_y

struct agg::rasterizer_cells_aa::sorted_y

template<class Cell>
struct agg::rasterizer_cells_aa< Cell >::sorted_y

Class Members
unsigned	num
unsigned	start

Member Typedef Documentation

cell_type

template<class Cell >

typedef Cell agg::rasterizer_cells_aa< Cell >::cell_type

self_type

template<class Cell >

typedef rasterizer_cells_aa<Cell> agg::rasterizer_cells_aa< Cell >::self_type

Member Enumeration Documentation

cell_block_scale_e

template<class Cell >

enum agg::rasterizer_cells_aa::cell_block_scale_e

private

Enumerator
cell_block_shift
cell_block_size
cell_block_mask
cell_block_pool
cell_block_limit

        {
            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
        };

Constructor & Destructor Documentation

~rasterizer_cells_aa()

template<class Cell >

agg::rasterizer_cells_aa< Cell >::~rasterizer_cells_aa

    {
        if(m_num_blocks)
        {
            cell_type** ptr = m_cells + m_num_blocks - 1;
            while(m_num_blocks--)
            {
                pod_allocator<cell_type>::deallocate(*ptr, cell_block_size);
                ptr--;
            }
            pod_allocator<cell_type*>::deallocate(m_cells, m_max_blocks);
        }
    }

References agg::pod_allocator< T >::deallocate().

Here is the call graph for this function:

rasterizer_cells_aa() [1/2]

template<class Cell >

agg::rasterizer_cells_aa< Cell >::rasterizer_cells_aa

                                                   :
        m_num_blocks(0),
        m_max_blocks(0),
        m_curr_block(0),
        m_num_cells(0),
        m_cells(0),
        m_curr_cell_ptr(0),
        m_sorted_cells(),
        m_sorted_y(),
        m_min_x(std::numeric_limits<int>::max()),
        m_min_y(std::numeric_limits<int>::max()),
        m_max_x(std::numeric_limits<int>::min()),
        m_max_y(std::numeric_limits<int>::min()),
        m_sorted(false)
    {
        m_style_cell.initial();
        m_curr_cell.initial();
    }

References agg::rasterizer_cells_aa< Cell >::m_curr_cell, and agg::rasterizer_cells_aa< Cell >::m_style_cell.

rasterizer_cells_aa() [2/2]

template<class Cell >

agg::rasterizer_cells_aa< Cell >::rasterizer_cells_aa ( const self_type &  )

private

Member Function Documentation

add_curr_cell()

template<class Cell >

AGG_INLINE void agg::rasterizer_cells_aa< Cell >::add_curr_cell

private

    {
        if(m_curr_cell.area | m_curr_cell.cover)
        {
            if((m_num_cells & cell_block_mask) == 0)
            {
                if(m_num_blocks >= cell_block_limit) return;
                allocate_block();
            }
            *m_curr_cell_ptr++ = m_curr_cell;
            ++m_num_cells;
        }
    }

allocate_block()

template<class Cell >

void agg::rasterizer_cells_aa< Cell >::allocate_block

private

    {
        if(m_curr_block >= m_num_blocks)
        {
            if(m_num_blocks >= m_max_blocks)
            {
                cell_type** new_cells = 
                    pod_allocator<cell_type*>::allocate(m_max_blocks + 
                                                        cell_block_pool);
 
                if(m_cells)
                {
                    memcpy(new_cells, m_cells, m_max_blocks * sizeof(cell_type*));
                    pod_allocator<cell_type*>::deallocate(m_cells, m_max_blocks);
                }
                m_cells = new_cells;
                m_max_blocks += cell_block_pool;
            }
 
            m_cells[m_num_blocks++] = 
                pod_allocator<cell_type>::allocate(cell_block_size);
 
        }
        m_curr_cell_ptr = m_cells[m_curr_block++];
    }

References agg::pod_allocator< T >::allocate(), and agg::pod_allocator< T >::deallocate().

Here is the call graph for this function:

line()

template<class Cell >

void agg::rasterizer_cells_aa< Cell >::line	(	int	x1,
		int	y1,
		int	x2,
		int	y2
	)

    {
        enum dx_limit_e { dx_limit = 16384 << poly_subpixel_shift };
 
        long long dx = (long long)x2 - (long long)x1;
 
        if(dx >= dx_limit || dx <= -dx_limit)
        {
            int cx = (int)(((long long)x1 + (long long)x2) >> 1);
            int cy = (int)(((long long)y1 + (long long)y2) >> 1);
            line(x1, y1, cx, cy);
            line(cx, cy, x2, y2);
        }
 
        long long dy = (long long)y2 - (long long)y1;
        int ex1 = x1 >> poly_subpixel_shift;
        int ex2 = x2 >> poly_subpixel_shift;
        int ey1 = y1 >> poly_subpixel_shift;
        int ey2 = y2 >> poly_subpixel_shift;
        int fy1 = y1 & poly_subpixel_mask;
        int fy2 = y2 & poly_subpixel_mask;
 
        int x_from, x_to;
        int rem, mod, lift, delta, first, incr;
        long long p;
 
        if(ex1 < m_min_x) m_min_x = ex1;
        if(ex1 > m_max_x) m_max_x = ex1;
        if(ey1 < m_min_y) m_min_y = ey1;
        if(ey1 > m_max_y) m_max_y = ey1;
        if(ex2 < m_min_x) m_min_x = ex2;
        if(ex2 > m_max_x) m_max_x = ex2;
        if(ey2 < m_min_y) m_min_y = ey2;
        if(ey2 > m_max_y) m_max_y = ey2;
 
        set_curr_cell(ex1, ey1);
 
        //everything is on a single hline
        if(ey1 == ey2)
        {
            render_hline(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_hline().
        incr  = 1;
        if(dx == 0)
        {
            int ex = x1 >> poly_subpixel_shift;
            int two_fx = (x1 - (ex << poly_subpixel_shift)) << 1;
            int area;
 
            first = poly_subpixel_scale;
            if(dy < 0)
            {
                first = 0;
                incr  = -1;
            }
 
            x_from = x1;
 
            //render_hline(ey1, x_from, fy1, x_from, first);
            delta = first - fy1;
            m_curr_cell.cover += delta;
            m_curr_cell.area  += two_fx * delta;
 
            ey1 += incr;
            set_curr_cell(ex, ey1);
 
            delta = first + first - poly_subpixel_scale;
            area = two_fx * delta;
            while(ey1 != ey2)
            {
                //render_hline(ey1, x_from, poly_subpixel_scale - first, x_from, first);
                m_curr_cell.cover = delta;
                m_curr_cell.area  = area;
                ey1 += incr;
                set_curr_cell(ex, ey1);
            }
            //render_hline(ey1, x_from, poly_subpixel_scale - first, x_from, fy2);
            delta = fy2 - poly_subpixel_scale + first;
            m_curr_cell.cover += delta;
            m_curr_cell.area  += two_fx * delta;
            return;
        }
 
        //ok, we have to render several hlines
        p     = (poly_subpixel_scale - fy1) * dx;
        first = poly_subpixel_scale;
 
        if(dy < 0)
        {
            p     = fy1 * dx;
            first = 0;
            incr  = -1;
            dy    = -dy;
        }
 
        delta = (int)(p / dy);
        mod   = (int)(p % dy);
 
        if(mod < 0)
        {
            delta--;
            mod += static_cast<int>(dy);
        }
 
        x_from = x1 + delta;
        render_hline(ey1, x1, fy1, x_from, first);
 
        ey1 += incr;
        set_curr_cell(x_from >> poly_subpixel_shift, ey1);
 
        if(ey1 != ey2)
        {
            p     = poly_subpixel_scale * dx;
            lift  = (int)(p / dy);
            rem   = (int)(p % dy);
 
            if(rem < 0)
            {
                lift--;
                rem += static_cast<int>(dy);
            }
            mod -= static_cast<int>(dy);
 
            while(ey1 != ey2)
            {
                delta = lift;
                mod  += rem;
                if (mod >= 0)
                {
                    mod -= static_cast<int>(dy);
                    delta++;
                }
 
                x_to = x_from + delta;
                render_hline(ey1, x_from, poly_subpixel_scale - first, x_to, first);
                x_from = x_to;
 
                ey1 += incr;
                set_curr_cell(x_from >> poly_subpixel_shift, ey1);
            }
        }
        render_hline(ey1, x_from, poly_subpixel_scale - first, x2, fy2);
    }

References long, agg::poly_subpixel_mask, agg::poly_subpixel_scale, and agg::poly_subpixel_shift.

max_x()

template<class Cell >

int agg::rasterizer_cells_aa< Cell >::max_x ( ) const

inline

{ return m_max_x; }

References agg::rasterizer_cells_aa< Cell >::m_max_x.

max_y()

template<class Cell >

int agg::rasterizer_cells_aa< Cell >::max_y ( ) const

inline

{ return m_max_y; }

References agg::rasterizer_cells_aa< Cell >::m_max_y.

min_x()

template<class Cell >

int agg::rasterizer_cells_aa< Cell >::min_x ( ) const

inline

{ return m_min_x; }

References agg::rasterizer_cells_aa< Cell >::m_min_x.

min_y()

template<class Cell >

int agg::rasterizer_cells_aa< Cell >::min_y ( ) const

inline

{ return m_min_y; }

References agg::rasterizer_cells_aa< Cell >::m_min_y.

operator=()

template<class Cell >

const self_type & agg::rasterizer_cells_aa< Cell >::operator= ( const self_type &  )

private

render_hline()

template<class Cell >

AGG_INLINE void agg::rasterizer_cells_aa< Cell >::render_hline ( int  ey, int  x1, int  y1, int  x2, int  y2  )

private

    {
        int ex1 = x1 >> poly_subpixel_shift;
        int ex2 = x2 >> poly_subpixel_shift;
        int fx1 = x1 & poly_subpixel_mask;
        int fx2 = x2 & poly_subpixel_mask;
 
        int delta, p, first;
        long long dx;
        int incr, lift, mod, rem;
 
        //trivial case. Happens often
        if(y1 == y2)
        {
            set_curr_cell(ex2, ey);
            return;
        }
 
        //everything is located in a single cell.  That is easy!
        if(ex1 == ex2)
        {
            delta = y2 - y1;
            m_curr_cell.cover += delta;
            m_curr_cell.area  += (fx1 + fx2) * delta;
            return;
        }
 
        //ok, we'll have to render a run of adjacent cells on the same
        //hline...
        p     = (poly_subpixel_scale - fx1) * (y2 - y1);
        first = poly_subpixel_scale;
        incr  = 1;
 
        dx = (long long)x2 - (long long)x1;
 
        if(dx < 0)
        {
            p     = fx1 * (y2 - y1);
            first = 0;
            incr  = -1;
            dx    = -dx;
        }
 
        delta = (int)(p / dx);
        mod   = (int)(p % dx);
 
        if(mod < 0)
        {
            delta--;
            mod += static_cast<int>(dx);
        }
 
        m_curr_cell.cover += delta;
        m_curr_cell.area  += (fx1 + first) * delta;
 
        ex1 += incr;
        set_curr_cell(ex1, ey);
        y1  += delta;
 
        if(ex1 != ex2)
        {
            p     = poly_subpixel_scale * (y2 - y1 + delta);
            lift  = (int)(p / dx);
            rem   = (int)(p % dx);
 
            if (rem < 0)
            {
                lift--;
                rem += static_cast<int>(dx);
            }
 
            mod -= static_cast<int>(dx);
 
            while (ex1 != ex2)
            {
                delta = lift;
                mod  += rem;
                if(mod >= 0)
                {
                    mod -= static_cast<int>(dx);
                    delta++;
                }
 
                m_curr_cell.cover += delta;
                m_curr_cell.area  += poly_subpixel_scale * delta;
                y1  += delta;
                ex1 += incr;
                set_curr_cell(ex1, ey);
            }
        }
        delta = y2 - y1;
        m_curr_cell.cover += delta;
        m_curr_cell.area  += (fx2 + poly_subpixel_scale - first) * delta;
    }

References long, agg::poly_subpixel_mask, agg::poly_subpixel_scale, and agg::poly_subpixel_shift.

reset()

template<class Cell >

void agg::rasterizer_cells_aa< Cell >::reset

    {
        m_num_cells = 0; 
        m_curr_block = 0;
        m_curr_cell.initial();
        m_style_cell.initial();
        m_sorted = false;
        m_min_x = std::numeric_limits<int>::max();
        m_min_y = std::numeric_limits<int>::max();
        m_max_x = std::numeric_limits<int>::min();
        m_max_y = std::numeric_limits<int>::min();
    }

scanline_cells()

template<class Cell >

const cell_type *const * agg::rasterizer_cells_aa< Cell >::scanline_cells ( unsigned  y ) const

inline

        { 
            return m_sorted_cells.data() + m_sorted_y[y - m_min_y].start; 
        }

References agg::pod_vector< T >::data(), agg::rasterizer_cells_aa< Cell >::m_min_y, agg::rasterizer_cells_aa< Cell >::m_sorted_cells, and agg::rasterizer_cells_aa< Cell >::m_sorted_y.

Here is the call graph for this function:

scanline_num_cells()

template<class Cell >

unsigned agg::rasterizer_cells_aa< Cell >::scanline_num_cells ( unsigned  y ) const

inline

        { 
            return m_sorted_y[y - m_min_y].num; 
        }

References agg::rasterizer_cells_aa< Cell >::m_min_y, and agg::rasterizer_cells_aa< Cell >::m_sorted_y.

set_curr_cell()

template<class Cell >

AGG_INLINE void agg::rasterizer_cells_aa< Cell >::set_curr_cell ( int  x, int  y  )

private

    {
        if(m_curr_cell.not_equal(x, y, m_style_cell))
        {
            add_curr_cell();
            m_curr_cell.style(m_style_cell);
            m_curr_cell.x     = x;
            m_curr_cell.y     = y;
            m_curr_cell.cover = 0;
            m_curr_cell.area  = 0;
        }
    }

sort_cells()

template<class Cell >

void agg::rasterizer_cells_aa< Cell >::sort_cells

    {
        if(m_sorted) return; //Perform sort only the first time.
 
        add_curr_cell();
        m_curr_cell.x     = std::numeric_limits<int>::max();
        m_curr_cell.y     = std::numeric_limits<int>::max();
        m_curr_cell.cover = 0;
        m_curr_cell.area  = 0;
 
        if(m_num_cells == 0) return;
 
// DBG: Check to see if min/max works well.
//for(unsigned nc = 0; nc < m_num_cells; nc++)
//{
//    cell_type* cell = m_cells[nc >> cell_block_shift] + (nc & cell_block_mask);
//    if(cell->x < m_min_x || 
//       cell->y < m_min_y || 
//       cell->x > m_max_x || 
//       cell->y > m_max_y)
//    {
//        cell = cell; // Breakpoint here
//    }
//}
        // Allocate the array of cell pointers
        m_sorted_cells.allocate(m_num_cells, 16);
 
        // Allocate and zero the Y array
        m_sorted_y.allocate(m_max_y - m_min_y + 1, 16);
        m_sorted_y.zero();
 
        // Create the Y-histogram (count the numbers of cells for each Y)
        cell_type** block_ptr = m_cells;
        cell_type*  cell_ptr;
        unsigned nb = m_num_cells;
        unsigned i;
        while(nb)
        {
            cell_ptr = *block_ptr++;
            i = (nb > cell_block_size) ? unsigned(cell_block_size) : nb;
            nb -= i;
            while(i--) 
            {
                m_sorted_y[cell_ptr->y - m_min_y].start++;
                ++cell_ptr;
            }
        }
 
        // Convert the Y-histogram into the array of starting indexes
        unsigned start = 0;
        for(i = 0; i < m_sorted_y.size(); i++)
        {
            unsigned v = m_sorted_y[i].start;
            m_sorted_y[i].start = start;
            start += v;
        }
 
        // Fill the cell pointer array sorted by Y
        block_ptr = m_cells;
        nb = m_num_cells;
        while(nb)
        {
            cell_ptr = *block_ptr++;
            i = (nb > cell_block_size) ? unsigned(cell_block_size) : nb;
            nb -= i;
            while(i--)
            {
                sorted_y& curr_y = m_sorted_y[cell_ptr->y - m_min_y];
                m_sorted_cells[curr_y.start + curr_y.num] = cell_ptr;
                ++curr_y.num;
                ++cell_ptr;
            }
        }
        
        // Finally arrange the X-arrays
        for(i = 0; i < m_sorted_y.size(); i++)
        {
            const sorted_y& curr_y = m_sorted_y[i];
            if(curr_y.num)
            {
                qsort_cells(m_sorted_cells.data() + curr_y.start, curr_y.num);
            }
        }
        m_sorted = true;
    }

References agg::rasterizer_cells_aa< Cell >::sorted_y::num, agg::qsort_cells(), and agg::rasterizer_cells_aa< Cell >::sorted_y::start.

Here is the call graph for this function:

sorted()

template<class Cell >

bool agg::rasterizer_cells_aa< Cell >::sorted ( ) const

inline

{ return m_sorted; }

References agg::rasterizer_cells_aa< Cell >::m_sorted.

style()

template<class Cell >

AGG_INLINE void agg::rasterizer_cells_aa< Cell >::style

(

const cell_type &

style_cell

)

    { 
        m_style_cell.style(style_cell); 
    }

total_cells()

template<class Cell >

unsigned agg::rasterizer_cells_aa< Cell >::total_cells ( ) const

inline

        {
            return m_num_cells;
        }

References agg::rasterizer_cells_aa< Cell >::m_num_cells.

Member Data Documentation

m_cells

template<class Cell >

cell_type** agg::rasterizer_cells_aa< Cell >::m_cells

private

m_curr_block

template<class Cell >

unsigned agg::rasterizer_cells_aa< Cell >::m_curr_block

private

m_curr_cell

template<class Cell >

cell_type agg::rasterizer_cells_aa< Cell >::m_curr_cell

private

Referenced by agg::rasterizer_cells_aa< Cell >::rasterizer_cells_aa().

m_curr_cell_ptr

template<class Cell >

cell_type* agg::rasterizer_cells_aa< Cell >::m_curr_cell_ptr

private

m_max_blocks

template<class Cell >

unsigned agg::rasterizer_cells_aa< Cell >::m_max_blocks

private

m_max_x

template<class Cell >

int agg::rasterizer_cells_aa< Cell >::m_max_x

private

Referenced by agg::rasterizer_cells_aa< Cell >::max_x().

m_max_y

template<class Cell >

int agg::rasterizer_cells_aa< Cell >::m_max_y

private

Referenced by agg::rasterizer_cells_aa< Cell >::max_y().

m_min_x

template<class Cell >

int agg::rasterizer_cells_aa< Cell >::m_min_x

private

Referenced by agg::rasterizer_cells_aa< Cell >::min_x().

m_min_y

template<class Cell >

int agg::rasterizer_cells_aa< Cell >::m_min_y

private

Referenced by agg::rasterizer_cells_aa< Cell >::min_y(), agg::rasterizer_cells_aa< Cell >::scanline_cells(), and agg::rasterizer_cells_aa< Cell >::scanline_num_cells().

m_num_blocks

template<class Cell >

unsigned agg::rasterizer_cells_aa< Cell >::m_num_blocks

private

m_num_cells

template<class Cell >

unsigned agg::rasterizer_cells_aa< Cell >::m_num_cells

private

Referenced by agg::rasterizer_cells_aa< Cell >::total_cells().

m_sorted

template<class Cell >

bool agg::rasterizer_cells_aa< Cell >::m_sorted

private

Referenced by agg::rasterizer_cells_aa< Cell >::sorted().

m_sorted_cells

template<class Cell >

pod_vector<cell_type*> agg::rasterizer_cells_aa< Cell >::m_sorted_cells

private

Referenced by agg::rasterizer_cells_aa< Cell >::scanline_cells().

m_sorted_y

template<class Cell >

pod_vector<sorted_y> agg::rasterizer_cells_aa< Cell >::m_sorted_y

private

Referenced by agg::rasterizer_cells_aa< Cell >::scanline_cells(), and agg::rasterizer_cells_aa< Cell >::scanline_num_cells().

m_style_cell

template<class Cell >

cell_type agg::rasterizer_cells_aa< Cell >::m_style_cell

private

Referenced by agg::rasterizer_cells_aa< Cell >::rasterizer_cells_aa().

---

The documentation for this class was generated from the following file:

• src/agg/agg_rasterizer_cells_aa.h