1e39da397SStephan Aßmus//----------------------------------------------------------------------------
2e39da397SStephan Aßmus// Anti-Grain Geometry - Version 2.4
3e39da397SStephan Aßmus// Copyright (C) 2002-2005 Maxim Shemanarev (http://www.antigrain.com)
4e39da397SStephan Aßmus//
5e39da397SStephan Aßmus// Permission to copy, use, modify, sell and distribute this software
6e39da397SStephan Aßmus// is granted provided this copyright notice appears in all copies.
7e39da397SStephan Aßmus// This software is provided "as is" without express or implied
8e39da397SStephan Aßmus// warranty, and with no claim as to its suitability for any purpose.
9e39da397SStephan Aßmus//
10e39da397SStephan Aßmus//----------------------------------------------------------------------------
11e39da397SStephan Aßmus//
12e39da397SStephan Aßmus// The author gratefully acknowleges the support of David Turner,
13e39da397SStephan Aßmus// Robert Wilhelm, and Werner Lemberg - the authors of the FreeType
14e39da397SStephan Aßmus// libray - in producing this work. See http://www.freetype.org for details.
15e39da397SStephan Aßmus//
16e39da397SStephan Aßmus//----------------------------------------------------------------------------
17e39da397SStephan Aßmus// Contact: mcseem@antigrain.com
18e39da397SStephan Aßmus//          mcseemagg@yahoo.com
19e39da397SStephan Aßmus//          http://www.antigrain.com
20e39da397SStephan Aßmus//----------------------------------------------------------------------------
21e39da397SStephan Aßmus//
22e39da397SStephan Aßmus// Adaptation for 32-bit screen coordinates has been sponsored by
23e39da397SStephan Aßmus// Liberty Technology Systems, Inc., visit http://lib-sys.com
24e39da397SStephan Aßmus//
25e39da397SStephan Aßmus// Liberty Technology Systems, Inc. is the provider of
26e39da397SStephan Aßmus// PostScript and PDF technology for software developers.
27e39da397SStephan Aßmus//
28e39da397SStephan Aßmus//----------------------------------------------------------------------------
29e39da397SStephan Aßmus#ifndef AGG_RASTERIZER_CELLS_AA_INCLUDED
30e39da397SStephan Aßmus#define AGG_RASTERIZER_CELLS_AA_INCLUDED
31e39da397SStephan Aßmus
32e39da397SStephan Aßmus#include <string.h>
33e39da397SStephan Aßmus#include <math.h>
34e39da397SStephan Aßmus#include "agg_math.h"
35e39da397SStephan Aßmus#include "agg_array.h"
36e39da397SStephan Aßmus
37e39da397SStephan Aßmus
38e39da397SStephan Aßmusnamespace agg
39e39da397SStephan Aßmus{
40e39da397SStephan Aßmus
41e39da397SStephan Aßmus    //-----------------------------------------------------rasterizer_cells_aa
42e39da397SStephan Aßmus    // An internal class that implements the main rasterization algorithm.
43e39da397SStephan Aßmus    // Used in the rasterizer. Should not be used direcly.
44e39da397SStephan Aßmus    template<class Cell> class rasterizer_cells_aa
45e39da397SStephan Aßmus    {
46e39da397SStephan Aßmus        enum cell_block_scale_e
47e39da397SStephan Aßmus        {
48e39da397SStephan Aßmus            cell_block_shift = 12,
49e39da397SStephan Aßmus            cell_block_size  = 1 << cell_block_shift,
50e39da397SStephan Aßmus            cell_block_mask  = cell_block_size - 1,
51e39da397SStephan Aßmus            cell_block_pool  = 256,
52e39da397SStephan Aßmus            cell_block_limit = 1024
53e39da397SStephan Aßmus        };
54e39da397SStephan Aßmus
55e39da397SStephan Aßmus        struct sorted_y
56e39da397SStephan Aßmus        {
57e39da397SStephan Aßmus            unsigned start;
58e39da397SStephan Aßmus            unsigned num;
59e39da397SStephan Aßmus        };
60e39da397SStephan Aßmus
61e39da397SStephan Aßmus    public:
62e39da397SStephan Aßmus        typedef Cell cell_type;
63e39da397SStephan Aßmus        typedef rasterizer_cells_aa<Cell> self_type;
64e39da397SStephan Aßmus
65e39da397SStephan Aßmus        ~rasterizer_cells_aa();
66e39da397SStephan Aßmus        rasterizer_cells_aa();
67e39da397SStephan Aßmus
68e39da397SStephan Aßmus        void reset();
69e39da397SStephan Aßmus        void style(const cell_type& style_cell);
70e39da397SStephan Aßmus        void line(int x1, int y1, int x2, int y2);
71e39da397SStephan Aßmus
72e39da397SStephan Aßmus        int min_x() const { return m_min_x; }
73e39da397SStephan Aßmus        int min_y() const { return m_min_y; }
74e39da397SStephan Aßmus        int max_x() const { return m_max_x; }
75e39da397SStephan Aßmus        int max_y() const { return m_max_y; }
76e39da397SStephan Aßmus
77e39da397SStephan Aßmus        void sort_cells();
78e39da397SStephan Aßmus
79e39da397SStephan Aßmus        unsigned total_cells() const
80e39da397SStephan Aßmus        {
81e39da397SStephan Aßmus            return m_num_cells;
82e39da397SStephan Aßmus        }
83e39da397SStephan Aßmus
84e39da397SStephan Aßmus        unsigned scanline_num_cells(unsigned y) const
85e39da397SStephan Aßmus        {
86e39da397SStephan Aßmus            return m_sorted_y[y - m_min_y].num;
87e39da397SStephan Aßmus        }
88e39da397SStephan Aßmus
89e39da397SStephan Aßmus        const cell_type* const* scanline_cells(unsigned y) const
90e39da397SStephan Aßmus        {
91e39da397SStephan Aßmus            return m_sorted_cells.data() + m_sorted_y[y - m_min_y].start;
92e39da397SStephan Aßmus        }
93e39da397SStephan Aßmus
94e39da397SStephan Aßmus        bool sorted() const { return m_sorted; }
95e39da397SStephan Aßmus
96e39da397SStephan Aßmus    private:
97e39da397SStephan Aßmus        rasterizer_cells_aa(const self_type&);
98e39da397SStephan Aßmus        const self_type& operator = (const self_type&);
99e39da397SStephan Aßmus
100e39da397SStephan Aßmus        void set_curr_cell(int x, int y);
101e39da397SStephan Aßmus        void add_curr_cell();
102e39da397SStephan Aßmus        void render_hline(int ey, int x1, int y1, int x2, int y2);
103e39da397SStephan Aßmus        void allocate_block();
104e39da397SStephan Aßmus
105e39da397SStephan Aßmus    private:
106e39da397SStephan Aßmus        unsigned                m_num_blocks;
107e39da397SStephan Aßmus        unsigned                m_max_blocks;
108e39da397SStephan Aßmus        unsigned                m_curr_block;
109e39da397SStephan Aßmus        unsigned                m_num_cells;
110e39da397SStephan Aßmus        cell_type**             m_cells;
111e39da397SStephan Aßmus        cell_type*              m_curr_cell_ptr;
112e39da397SStephan Aßmus        pod_vector<cell_type*>  m_sorted_cells;
113e39da397SStephan Aßmus        pod_vector<sorted_y>    m_sorted_y;
114e39da397SStephan Aßmus        cell_type               m_curr_cell;
115e39da397SStephan Aßmus        cell_type               m_style_cell;
116e39da397SStephan Aßmus        int                     m_min_x;
117e39da397SStephan Aßmus        int                     m_min_y;
118e39da397SStephan Aßmus        int                     m_max_x;
119e39da397SStephan Aßmus        int                     m_max_y;
120e39da397SStephan Aßmus        bool                    m_sorted;
121e39da397SStephan Aßmus    };
122e39da397SStephan Aßmus
123e39da397SStephan Aßmus
124e39da397SStephan Aßmus
125e39da397SStephan Aßmus
126e39da397SStephan Aßmus    //------------------------------------------------------------------------
127e39da397SStephan Aßmus    template<class Cell>
128e39da397SStephan Aßmus    rasterizer_cells_aa<Cell>::~rasterizer_cells_aa()
129e39da397SStephan Aßmus    {
130e39da397SStephan Aßmus        if(m_num_blocks)
131e39da397SStephan Aßmus        {
132e39da397SStephan Aßmus            cell_type** ptr = m_cells + m_num_blocks - 1;
133e39da397SStephan Aßmus            while(m_num_blocks--)
134e39da397SStephan Aßmus            {
135e39da397SStephan Aßmus                pod_allocator<cell_type>::deallocate(*ptr, cell_block_size);
136e39da397SStephan Aßmus                ptr--;
137e39da397SStephan Aßmus            }
138e39da397SStephan Aßmus            pod_allocator<cell_type*>::deallocate(m_cells, m_max_blocks);
139e39da397SStephan Aßmus        }
140e39da397SStephan Aßmus    }
141e39da397SStephan Aßmus
142e39da397SStephan Aßmus    //------------------------------------------------------------------------
143e39da397SStephan Aßmus    template<class Cell>
144e39da397SStephan Aßmus    rasterizer_cells_aa<Cell>::rasterizer_cells_aa() :
145e39da397SStephan Aßmus        m_num_blocks(0),
146e39da397SStephan Aßmus        m_max_blocks(0),
147e39da397SStephan Aßmus        m_curr_block(0),
148e39da397SStephan Aßmus        m_num_cells(0),
149e39da397SStephan Aßmus        m_cells(0),
150e39da397SStephan Aßmus        m_curr_cell_ptr(0),
151e39da397SStephan Aßmus        m_sorted_cells(),
152e39da397SStephan Aßmus        m_sorted_y(),
153e39da397SStephan Aßmus        m_min_x(0x7FFFFFFF),
154e39da397SStephan Aßmus        m_min_y(0x7FFFFFFF),
155e39da397SStephan Aßmus        m_max_x(-0x7FFFFFFF),
156e39da397SStephan Aßmus        m_max_y(-0x7FFFFFFF),
157e39da397SStephan Aßmus        m_sorted(false)
158e39da397SStephan Aßmus    {
159e39da397SStephan Aßmus        m_style_cell.initial();
160e39da397SStephan Aßmus        m_curr_cell.initial();
161e39da397SStephan Aßmus    }
162e39da397SStephan Aßmus
163e39da397SStephan Aßmus    //------------------------------------------------------------------------
164e39da397SStephan Aßmus    template<class Cell>
165e39da397SStephan Aßmus    void rasterizer_cells_aa<Cell>::reset()
166e39da397SStephan Aßmus    {
167e39da397SStephan Aßmus        m_num_cells = 0;
168e39da397SStephan Aßmus        m_curr_block = 0;
169e39da397SStephan Aßmus        m_curr_cell.initial();
170e39da397SStephan Aßmus        m_style_cell.initial();
171e39da397SStephan Aßmus        m_sorted = false;
172e39da397SStephan Aßmus        m_min_x =  0x7FFFFFFF;
173e39da397SStephan Aßmus        m_min_y =  0x7FFFFFFF;
174e39da397SStephan Aßmus        m_max_x = -0x7FFFFFFF;
175e39da397SStephan Aßmus        m_max_y = -0x7FFFFFFF;
176e39da397SStephan Aßmus    }
177e39da397SStephan Aßmus
178e39da397SStephan Aßmus    //------------------------------------------------------------------------
179e39da397SStephan Aßmus    template<class Cell>
180e39da397SStephan Aßmus    AGG_INLINE void rasterizer_cells_aa<Cell>::add_curr_cell()
181e39da397SStephan Aßmus    {
182e39da397SStephan Aßmus        if(m_curr_cell.area | m_curr_cell.cover)
183e39da397SStephan Aßmus        {
184e39da397SStephan Aßmus            if((m_num_cells & cell_block_mask) == 0)
185e39da397SStephan Aßmus            {
186e39da397SStephan Aßmus                if(m_num_blocks >= cell_block_limit) return;
187e39da397SStephan Aßmus                allocate_block();
188e39da397SStephan Aßmus            }
189e39da397SStephan Aßmus            *m_curr_cell_ptr++ = m_curr_cell;
190e39da397SStephan Aßmus            ++m_num_cells;
191e39da397SStephan Aßmus        }
192e39da397SStephan Aßmus    }
193e39da397SStephan Aßmus
194e39da397SStephan Aßmus    //------------------------------------------------------------------------
195e39da397SStephan Aßmus    template<class Cell>
196e39da397SStephan Aßmus    AGG_INLINE void rasterizer_cells_aa<Cell>::set_curr_cell(int x, int y)
197e39da397SStephan Aßmus    {
198e39da397SStephan Aßmus        if(m_curr_cell.not_equal(x, y, m_style_cell))
199e39da397SStephan Aßmus        {
200e39da397SStephan Aßmus            add_curr_cell();
201e39da397SStephan Aßmus            m_curr_cell.style(m_style_cell);
202e39da397SStephan Aßmus            m_curr_cell.x     = x;
203e39da397SStephan Aßmus            m_curr_cell.y     = y;
204e39da397SStephan Aßmus            m_curr_cell.cover = 0;
205e39da397SStephan Aßmus            m_curr_cell.area  = 0;
206e39da397SStephan Aßmus        }
207e39da397SStephan Aßmus    }
208e39da397SStephan Aßmus
209e39da397SStephan Aßmus    //------------------------------------------------------------------------
210e39da397SStephan Aßmus    template<class Cell>
211e39da397SStephan Aßmus    AGG_INLINE void rasterizer_cells_aa<Cell>::render_hline(int ey,
212e39da397SStephan Aßmus                                                            int x1, int y1,
213e39da397SStephan Aßmus                                                            int x2, int y2)
214e39da397SStephan Aßmus    {
215e39da397SStephan Aßmus        int ex1 = x1 >> poly_subpixel_shift;
216e39da397SStephan Aßmus        int ex2 = x2 >> poly_subpixel_shift;
217e39da397SStephan Aßmus        int fx1 = x1 & poly_subpixel_mask;
218e39da397SStephan Aßmus        int fx2 = x2 & poly_subpixel_mask;
219e39da397SStephan Aßmus
220e39da397SStephan Aßmus        int delta, p, first, dx;
221e39da397SStephan Aßmus        int incr, lift, mod, rem;
222e39da397SStephan Aßmus
223e39da397SStephan Aßmus        //trivial case. Happens often
224e39da397SStephan Aßmus        if(y1 == y2)
225e39da397SStephan Aßmus        {
226e39da397SStephan Aßmus            set_curr_cell(ex2, ey);
227e39da397SStephan Aßmus            return;
228e39da397SStephan Aßmus        }
229e39da397SStephan Aßmus
230e39da397SStephan Aßmus        //everything is located in a single cell.  That is easy!
231e39da397SStephan Aßmus        if(ex1 == ex2)
232e39da397SStephan Aßmus        {
233e39da397SStephan Aßmus            delta = y2 - y1;
234e39da397SStephan Aßmus            m_curr_cell.cover += delta;
235e39da397SStephan Aßmus            m_curr_cell.area  += (fx1 + fx2) * delta;
236e39da397SStephan Aßmus            return;
237e39da397SStephan Aßmus        }
238e39da397SStephan Aßmus
239e39da397SStephan Aßmus        //ok, we'll have to render a run of adjacent cells on the same
240e39da397SStephan Aßmus        //hline...
241e39da397SStephan Aßmus        p     = (poly_subpixel_scale - fx1) * (y2 - y1);
242e39da397SStephan Aßmus        first = poly_subpixel_scale;
243e39da397SStephan Aßmus        incr  = 1;
244e39da397SStephan Aßmus
245e39da397SStephan Aßmus        dx = x2 - x1;
246e39da397SStephan Aßmus
247e39da397SStephan Aßmus        if(dx < 0)
248e39da397SStephan Aßmus        {
249e39da397SStephan Aßmus            p     = fx1 * (y2 - y1);
250e39da397SStephan Aßmus            first = 0;
251e39da397SStephan Aßmus            incr  = -1;
252e39da397SStephan Aßmus            dx    = -dx;
253e39da397SStephan Aßmus        }
254e39da397SStephan Aßmus
255e39da397SStephan Aßmus        delta = p / dx;
256e39da397SStephan Aßmus        mod   = p % dx;
257e39da397SStephan Aßmus
258e39da397SStephan Aßmus        if(mod < 0)
259e39da397SStephan Aßmus        {
260e39da397SStephan Aßmus            delta--;
261e39da397SStephan Aßmus            mod += dx;
262e39da397SStephan Aßmus        }
263e39da397SStephan Aßmus
264e39da397SStephan Aßmus        m_curr_cell.cover += delta;
265e39da397SStephan Aßmus        m_curr_cell.area  += (fx1 + first) * delta;
266e39da397SStephan Aßmus
267e39da397SStephan Aßmus        ex1 += incr;
268e39da397SStephan Aßmus        set_curr_cell(ex1, ey);
269e39da397SStephan Aßmus        y1  += delta;
270e39da397SStephan Aßmus
271e39da397SStephan Aßmus        if(ex1 != ex2)
272e39da397SStephan Aßmus        {
273e39da397SStephan Aßmus            p     = poly_subpixel_scale * (y2 - y1 + delta);
274e39da397SStephan Aßmus            lift  = p / dx;
275e39da397SStephan Aßmus            rem   = p % dx;
276e39da397SStephan Aßmus
277e39da397SStephan Aßmus            if (rem < 0)
278e39da397SStephan Aßmus            {
279e39da397SStephan Aßmus                lift--;
280e39da397SStephan Aßmus                rem += dx;
281e39da397SStephan Aßmus            }
282e39da397SStephan Aßmus
283e39da397SStephan Aßmus            mod -= dx;
284e39da397SStephan Aßmus
285e39da397SStephan Aßmus            while (ex1 != ex2)
286e39da397SStephan Aßmus            {
287e39da397SStephan Aßmus                delta = lift;
288e39da397SStephan Aßmus                mod  += rem;
289e39da397SStephan Aßmus                if(mod >= 0)
290e39da397SStephan Aßmus                {
291e39da397SStephan Aßmus                    mod -= dx;
292e39da397SStephan Aßmus                    delta++;
293e39da397SStephan Aßmus                }
294e39da397SStephan Aßmus
295e39da397SStephan Aßmus                m_curr_cell.cover += delta;
296e39da397SStephan Aßmus                m_curr_cell.area  += poly_subpixel_scale * delta;
297e39da397SStephan Aßmus                y1  += delta;
298e39da397SStephan Aßmus                ex1 += incr;
299e39da397SStephan Aßmus                set_curr_cell(ex1, ey);
300e39da397SStephan Aßmus            }
301e39da397SStephan Aßmus        }
302e39da397SStephan Aßmus        delta = y2 - y1;
303e39da397SStephan Aßmus        m_curr_cell.cover += delta;
304e39da397SStephan Aßmus        m_curr_cell.area  += (fx2 + poly_subpixel_scale - first) * delta;
305e39da397SStephan Aßmus    }
306e39da397SStephan Aßmus
307e39da397SStephan Aßmus    //------------------------------------------------------------------------
308e39da397SStephan Aßmus    template<class Cell>
309e39da397SStephan Aßmus    AGG_INLINE void rasterizer_cells_aa<Cell>::style(const cell_type& style_cell)
310e39da397SStephan Aßmus    {
311e39da397SStephan Aßmus        m_style_cell.style(style_cell);
312e39da397SStephan Aßmus    }
313e39da397SStephan Aßmus
314e39da397SStephan Aßmus    //------------------------------------------------------------------------
315e39da397SStephan Aßmus    template<class Cell>
316e39da397SStephan Aßmus    void rasterizer_cells_aa<Cell>::line(int x1, int y1, int x2, int y2)
317e39da397SStephan Aßmus    {
318e39da397SStephan Aßmus        enum dx_limit_e { dx_limit = 16384 << poly_subpixel_shift };
319e39da397SStephan Aßmus
320e39da397SStephan Aßmus        int dx = x2 - x1;
321e39da397SStephan Aßmus
322e39da397SStephan Aßmus        if(dx >= dx_limit || dx <= -dx_limit)
323e39da397SStephan Aßmus        {
324e39da397SStephan Aßmus            int cx = (x1 + x2) >> 1;
325e39da397SStephan Aßmus            int cy = (y1 + y2) >> 1;
326e39da397SStephan Aßmus            line(x1, y1, cx, cy);
327e39da397SStephan Aßmus            line(cx, cy, x2, y2);
328e39da397SStephan Aßmus        }
329e39da397SStephan Aßmus
330e39da397SStephan Aßmus        int dy = y2 - y1;
331e39da397SStephan Aßmus        int ex1 = x1 >> poly_subpixel_shift;
332e39da397SStephan Aßmus        int ex2 = x2 >> poly_subpixel_shift;
333e39da397SStephan Aßmus        int ey1 = y1 >> poly_subpixel_shift;
334e39da397SStephan Aßmus        int ey2 = y2 >> poly_subpixel_shift;
335e39da397SStephan Aßmus        int fy1 = y1 & poly_subpixel_mask;
336e39da397SStephan Aßmus        int fy2 = y2 & poly_subpixel_mask;
337e39da397SStephan Aßmus
338e39da397SStephan Aßmus        int x_from, x_to;
339e39da397SStephan Aßmus        int p, rem, mod, lift, delta, first, incr;
340e39da397SStephan Aßmus
341e39da397SStephan Aßmus        if(ex1 < m_min_x) m_min_x = ex1;
342e39da397SStephan Aßmus        if(ex1 > m_max_x) m_max_x = ex1;
343e39da397SStephan Aßmus        if(ey1 < m_min_y) m_min_y = ey1;
344e39da397SStephan Aßmus        if(ey1 > m_max_y) m_max_y = ey1;
345e39da397SStephan Aßmus        if(ex2 < m_min_x) m_min_x = ex2;
346e39da397SStephan Aßmus        if(ex2 > m_max_x) m_max_x = ex2;
347e39da397SStephan Aßmus        if(ey2 < m_min_y) m_min_y = ey2;
348e39da397SStephan Aßmus        if(ey2 > m_max_y) m_max_y = ey2;
349e39da397SStephan Aßmus
350e39da397SStephan Aßmus        set_curr_cell(ex1, ey1);
351e39da397SStephan Aßmus
352e39da397SStephan Aßmus        //everything is on a single hline
353e39da397SStephan Aßmus        if(ey1 == ey2)
354e39da397SStephan Aßmus        {
355e39da397SStephan Aßmus            render_hline(ey1, x1, fy1, x2, fy2);
356e39da397SStephan Aßmus            return;
357e39da397SStephan Aßmus        }
358e39da397SStephan Aßmus
359e39da397SStephan Aßmus        //Vertical line - we have to calculate start and end cells,
360e39da397SStephan Aßmus        //and then - the common values of the area and coverage for
361e39da397SStephan Aßmus        //all cells of the line. We know exactly there's only one
362e39da397SStephan Aßmus        //cell, so, we don't have to call render_hline().
363e39da397SStephan Aßmus        incr  = 1;
364e39da397SStephan Aßmus        if(dx == 0)
365e39da397SStephan Aßmus        {
366e39da397SStephan Aßmus            int ex = x1 >> poly_subpixel_shift;
367e39da397SStephan Aßmus            int two_fx = (x1 - (ex << poly_subpixel_shift)) << 1;
368e39da397SStephan Aßmus            int area;
369e39da397SStephan Aßmus
370e39da397SStephan Aßmus            first = poly_subpixel_scale;
371e39da397SStephan Aßmus            if(dy < 0)
372e39da397SStephan Aßmus            {
373e39da397SStephan Aßmus                first = 0;
374e39da397SStephan Aßmus                incr  = -1;
375e39da397SStephan Aßmus            }
376e39da397SStephan Aßmus
377e39da397SStephan Aßmus            x_from = x1;
378e39da397SStephan Aßmus
379e39da397SStephan Aßmus            //render_hline(ey1, x_from, fy1, x_from, first);
380e39da397SStephan Aßmus            delta = first - fy1;
381e39da397SStephan Aßmus            m_curr_cell.cover += delta;
382e39da397SStephan Aßmus            m_curr_cell.area  += two_fx * delta;
383e39da397SStephan Aßmus
384e39da397SStephan Aßmus            ey1 += incr;
385e39da397SStephan Aßmus            set_curr_cell(ex, ey1);
386e39da397SStephan Aßmus
387e39da397SStephan Aßmus            delta = first + first - poly_subpixel_scale;
388e39da397SStephan Aßmus            area = two_fx * delta;
389e39da397SStephan Aßmus            while(ey1 != ey2)
390e39da397SStephan Aßmus            {
391e39da397SStephan Aßmus                //render_hline(ey1, x_from, poly_subpixel_scale - first, x_from, first);
392e39da397SStephan Aßmus                m_curr_cell.cover = delta;
393e39da397SStephan Aßmus                m_curr_cell.area  = area;
394e39da397SStephan Aßmus                ey1 += incr;
395e39da397SStephan Aßmus                set_curr_cell(ex, ey1);
396e39da397SStephan Aßmus            }
397e39da397SStephan Aßmus            //render_hline(ey1, x_from, poly_subpixel_scale - first, x_from, fy2);
398e39da397SStephan Aßmus            delta = fy2 - poly_subpixel_scale + first;
399e39da397SStephan Aßmus            m_curr_cell.cover += delta;
400e39da397SStephan Aßmus            m_curr_cell.area  += two_fx * delta;
401e39da397SStephan Aßmus            return;
402e39da397SStephan Aßmus        }
403e39da397SStephan Aßmus
404e39da397SStephan Aßmus        //ok, we have to render several hlines
405e39da397SStephan Aßmus        p     = (poly_subpixel_scale - fy1) * dx;
406e39da397SStephan Aßmus        first = poly_subpixel_scale;
407e39da397SStephan Aßmus
408e39da397SStephan Aßmus        if(dy < 0)
409e39da397SStephan Aßmus        {
410e39da397SStephan Aßmus            p     = fy1 * dx;
411e39da397SStephan Aßmus            first = 0;
412e39da397SStephan Aßmus            incr  = -1;
413e39da397SStephan Aßmus            dy    = -dy;
414e39da397SStephan Aßmus        }
415e39da397SStephan Aßmus
416e39da397SStephan Aßmus        delta = p / dy;
417e39da397SStephan Aßmus        mod   = p % dy;
418e39da397SStephan Aßmus
419e39da397SStephan Aßmus        if(mod < 0)
420e39da397SStephan Aßmus        {
421e39da397SStephan Aßmus            delta--;
422e39da397SStephan Aßmus            mod += dy;
423e39da397SStephan Aßmus        }
424e39da397SStephan Aßmus
425e39da397SStephan Aßmus        x_from = x1 + delta;
426e39da397SStephan Aßmus        render_hline(ey1, x1, fy1, x_from, first);
427e39da397SStephan Aßmus
428e39da397SStephan Aßmus        ey1 += incr;
429e39da397SStephan Aßmus        set_curr_cell(x_from >> poly_subpixel_shift, ey1);
430e39da397SStephan Aßmus
431e39da397SStephan Aßmus        if(ey1 != ey2)
432e39da397SStephan Aßmus        {
433e39da397SStephan Aßmus            p     = poly_subpixel_scale * dx;
434e39da397SStephan Aßmus            lift  = p / dy;
435e39da397SStephan Aßmus            rem   = p % dy;
436e39da397SStephan Aßmus
437e39da397SStephan Aßmus            if(rem < 0)
438e39da397SStephan Aßmus            {
439e39da397SStephan Aßmus                lift--;
440e39da397SStephan Aßmus                rem += dy;
441e39da397SStephan Aßmus            }
442e39da397SStephan Aßmus            mod -= dy;
443e39da397SStephan Aßmus
444e39da397SStephan Aßmus            while(ey1 != ey2)
445e39da397SStephan Aßmus            {
446e39da397SStephan Aßmus                delta = lift;
447e39da397SStephan Aßmus                mod  += rem;
448e39da397SStephan Aßmus                if (mod >= 0)
449e39da397SStephan Aßmus                {
450e39da397SStephan Aßmus                    mod -= dy;
451e39da397SStephan Aßmus                    delta++;
452e39da397SStephan Aßmus                }
453e39da397SStephan Aßmus
454e39da397SStephan Aßmus                x_to = x_from + delta;
455e39da397SStephan Aßmus                render_hline(ey1, x_from, poly_subpixel_scale - first, x_to, first);
456e39da397SStephan Aßmus                x_from = x_to;
457e39da397SStephan Aßmus
458e39da397SStephan Aßmus                ey1 += incr;
459e39da397SStephan Aßmus                set_curr_cell(x_from >> poly_subpixel_shift, ey1);
460e39da397SStephan Aßmus            }
461e39da397SStephan Aßmus        }
462e39da397SStephan Aßmus        render_hline(ey1, x_from, poly_subpixel_scale - first, x2, fy2);
463e39da397SStephan Aßmus    }
464e39da397SStephan Aßmus
465e39da397SStephan Aßmus    //------------------------------------------------------------------------
466e39da397SStephan Aßmus    template<class Cell>
467e39da397SStephan Aßmus    void rasterizer_cells_aa<Cell>::allocate_block()
468e39da397SStephan Aßmus    {
469e39da397SStephan Aßmus        if(m_curr_block >= m_num_blocks)
470e39da397SStephan Aßmus        {
471e39da397SStephan Aßmus            if(m_num_blocks >= m_max_blocks)
472e39da397SStephan Aßmus            {
473e39da397SStephan Aßmus                cell_type** new_cells =
474e39da397SStephan Aßmus                    pod_allocator<cell_type*>::allocate(m_max_blocks +
475e39da397SStephan Aßmus                                                        cell_block_pool);
476e39da397SStephan Aßmus
477e39da397SStephan Aßmus                if(m_cells)
478e39da397SStephan Aßmus                {
479e39da397SStephan Aßmus                    memcpy(new_cells, m_cells, m_max_blocks * sizeof(cell_type*));
480e39da397SStephan Aßmus                    pod_allocator<cell_type*>::deallocate(m_cells, m_max_blocks);
481e39da397SStephan Aßmus                }
482e39da397SStephan Aßmus                m_cells = new_cells;
483e39da397SStephan Aßmus                m_max_blocks += cell_block_pool;
484e39da397SStephan Aßmus            }
485e39da397SStephan Aßmus
486e39da397SStephan Aßmus            m_cells[m_num_blocks++] =
487e39da397SStephan Aßmus                pod_allocator<cell_type>::allocate(cell_block_size);
488e39da397SStephan Aßmus
489e39da397SStephan Aßmus        }
490e39da397SStephan Aßmus        m_curr_cell_ptr = m_cells[m_curr_block++];
491e39da397SStephan Aßmus    }
492e39da397SStephan Aßmus
493e39da397SStephan Aßmus
494e39da397SStephan Aßmus
495e39da397SStephan Aßmus    //------------------------------------------------------------------------
496e39da397SStephan Aßmus    template <class T> static AGG_INLINE void swap_cells(T* a, T* b)
497e39da397SStephan Aßmus    {
498e39da397SStephan Aßmus        T temp = *a;
499e39da397SStephan Aßmus        *a = *b;
500e39da397SStephan Aßmus        *b = temp;
501e39da397SStephan Aßmus    }
502e39da397SStephan Aßmus
503e39da397SStephan Aßmus
504e39da397SStephan Aßmus    //------------------------------------------------------------------------
505e39da397SStephan Aßmus    enum
506e39da397SStephan Aßmus    {
507e39da397SStephan Aßmus        qsort_threshold = 9
508e39da397SStephan Aßmus    };
509e39da397SStephan Aßmus
510e39da397SStephan Aßmus
511e39da397SStephan Aßmus    //------------------------------------------------------------------------
512e39da397SStephan Aßmus    template<class Cell>
513e39da397SStephan Aßmus    void qsort_cells(Cell** start, unsigned num)
514e39da397SStephan Aßmus    {
515e39da397SStephan Aßmus        Cell**  stack[80];
516e39da397SStephan Aßmus        Cell*** top;
517e39da397SStephan Aßmus        Cell**  limit;
518e39da397SStephan Aßmus        Cell**  base;
519e39da397SStephan Aßmus
520e39da397SStephan Aßmus        limit = start + num;
521e39da397SStephan Aßmus        base  = start;
522e39da397SStephan Aßmus        top   = stack;
523e39da397SStephan Aßmus
524e39da397SStephan Aßmus        for (;;)
525e39da397SStephan Aßmus        {
526e39da397SStephan Aßmus            int len = int(limit - base);
527e39da397SStephan Aßmus
528e39da397SStephan Aßmus            Cell** i;
529e39da397SStephan Aßmus            Cell** j;
530e39da397SStephan Aßmus            Cell** pivot;
531e39da397SStephan Aßmus
532e39da397SStephan Aßmus            if(len > qsort_threshold)
533e39da397SStephan Aßmus            {
534e39da397SStephan Aßmus                // we use base + len/2 as the pivot
535e39da397SStephan Aßmus                pivot = base + len / 2;
536e39da397SStephan Aßmus                swap_cells(base, pivot);
537e39da397SStephan Aßmus
538e39da397SStephan Aßmus                i = base + 1;
539e39da397SStephan Aßmus                j = limit - 1;
540e39da397SStephan Aßmus
541e39da397SStephan Aßmus                // now ensure that *i <= *base <= *j
542e39da397SStephan Aßmus                if((*j)->x < (*i)->x)
543e39da397SStephan Aßmus                {
544e39da397SStephan Aßmus                    swap_cells(i, j);
545e39da397SStephan Aßmus                }
546e39da397SStephan Aßmus
547e39da397SStephan Aßmus                if((*base)->x < (*i)->x)
548e39da397SStephan Aßmus                {
549e39da397SStephan Aßmus                    swap_cells(base, i);
550e39da397SStephan Aßmus                }
551e39da397SStephan Aßmus
552e39da397SStephan Aßmus                if((*j)->x < (*base)->x)
553e39da397SStephan Aßmus                {
554e39da397SStephan Aßmus                    swap_cells(base, j);
555e39da397SStephan Aßmus                }
556e39da397SStephan Aßmus
557e39da397SStephan Aßmus                for(;;)
558e39da397SStephan Aßmus                {
559e39da397SStephan Aßmus                    int x = (*base)->x;
560e39da397SStephan Aßmus                    do i++; while( (*i)->x < x );
561e39da397SStephan Aßmus                    do j--; while( x < (*j)->x );
562e39da397SStephan Aßmus
563e39da397SStephan Aßmus                    if(i > j)
564e39da397SStephan Aßmus                    {
565e39da397SStephan Aßmus                        break;
566e39da397SStephan Aßmus                    }
567e39da397SStephan Aßmus
568e39da397SStephan Aßmus                    swap_cells(i, j);
569e39da397SStephan Aßmus                }
570e39da397SStephan Aßmus
571e39da397SStephan Aßmus                swap_cells(base, j);
572e39da397SStephan Aßmus
573e39da397SStephan Aßmus                // now, push the largest sub-array
574e39da397SStephan Aßmus                if(j - base > limit - i)
575e39da397SStephan Aßmus                {
576e39da397SStephan Aßmus                    top[0] = base;
577e39da397SStephan Aßmus                    top[1] = j;
578e39da397SStephan Aßmus                    base   = i;
579e39da397SStephan Aßmus                }
580e39da397SStephan Aßmus                else
581e39da397SStephan Aßmus                {
582e39da397SStephan Aßmus                    top[0] = i;
583e39da397SStephan Aßmus                    top[1] = limit;
584e39da397SStephan Aßmus                    limit  = j;
585e39da397SStephan Aßmus                }
586e39da397SStephan Aßmus                top += 2;
587e39da397SStephan Aßmus            }
588e39da397SStephan Aßmus            else
589e39da397SStephan Aßmus            {
590e39da397SStephan Aßmus                // the sub-array is small, perform insertion sort
591e39da397SStephan Aßmus                j = base;
592e39da397SStephan Aßmus                i = j + 1;
593e39da397SStephan Aßmus
594e39da397SStephan Aßmus                for(; i < limit; j = i, i++)
595e39da397SStephan Aßmus                {
596e39da397SStephan Aßmus                    for(; j[1]->x < (*j)->x; j--)
597e39da397SStephan Aßmus                    {
598e39da397SStephan Aßmus                        swap_cells(j + 1, j);
599e39da397SStephan Aßmus                        if (j == base)
600e39da397SStephan Aßmus                        {
601e39da397SStephan Aßmus                            break;
602e39da397SStephan Aßmus                        }
603e39da397SStephan Aßmus                    }
604e39da397SStephan Aßmus                }
605e39da397SStephan Aßmus
606e39da397SStephan Aßmus                if(top > stack)
607e39da397SStephan Aßmus                {
608e39da397SStephan Aßmus                    top  -= 2;
609e39da397SStephan Aßmus                    base  = top[0];
610e39da397SStephan Aßmus                    limit = top[1];
611e39da397SStephan Aßmus                }
612e39da397SStephan Aßmus                else
613e39da397SStephan Aßmus                {
614e39da397SStephan Aßmus                    break;
615e39da397SStephan Aßmus                }
616e39da397SStephan Aßmus            }
617e39da397SStephan Aßmus        }
618e39da397SStephan Aßmus    }
619e39da397SStephan Aßmus
620e39da397SStephan Aßmus
621e39da397SStephan Aßmus    //------------------------------------------------------------------------
622e39da397SStephan Aßmus    template<class Cell>
623e39da397SStephan Aßmus    void rasterizer_cells_aa<Cell>::sort_cells()
624e39da397SStephan Aßmus    {
625e39da397SStephan Aßmus        if(m_sorted) return; //Perform sort only the first time.
626e39da397SStephan Aßmus
627e39da397SStephan Aßmus        add_curr_cell();
628e39da397SStephan Aßmus        m_curr_cell.x     = 0x7FFFFFFF;
629e39da397SStephan Aßmus        m_curr_cell.y     = 0x7FFFFFFF;
630e39da397SStephan Aßmus        m_curr_cell.cover = 0;
631e39da397SStephan Aßmus        m_curr_cell.area  = 0;
632e39da397SStephan Aßmus
633e39da397SStephan Aßmus        if(m_num_cells == 0) return;
634e39da397SStephan Aßmus
635e39da397SStephan Aßmus// DBG: Check to see if min/max works well.
636e39da397SStephan Aßmus//for(unsigned nc = 0; nc < m_num_cells; nc++)
637e39da397SStephan Aßmus//{
638e39da397SStephan Aßmus//    cell_type* cell = m_cells[nc >> cell_block_shift] + (nc & cell_block_mask);
639e39da397SStephan Aßmus//    if(cell->x < m_min_x ||
640e39da397SStephan Aßmus//       cell->y < m_min_y ||
641e39da397SStephan Aßmus//       cell->x > m_max_x ||
642e39da397SStephan Aßmus//       cell->y > m_max_y)
643e39da397SStephan Aßmus//    {
644e39da397SStephan Aßmus//        cell = cell; // Breakpoint here
645e39da397SStephan Aßmus//    }
646e39da397SStephan Aßmus//}
647e39da397SStephan Aßmus
648e39da397SStephan Aßmus        // Allocate the array of cell pointers
649e39da397SStephan Aßmus        m_sorted_cells.allocate(m_num_cells, 16);
650e39da397SStephan Aßmus
651e39da397SStephan Aßmus        // Allocate and zero the Y array
652e39da397SStephan Aßmus        m_sorted_y.allocate(m_max_y - m_min_y + 1, 16);
653e39da397SStephan Aßmus        m_sorted_y.zero();
654e39da397SStephan Aßmus
655e39da397SStephan Aßmus        // Create the Y-histogram (count the numbers of cells for each Y)
656e39da397SStephan Aßmus        cell_type** block_ptr = m_cells;
657e39da397SStephan Aßmus        cell_type*  cell_ptr;
658e39da397SStephan Aßmus        unsigned nb = m_num_cells >> cell_block_shift;
659e39da397SStephan Aßmus        unsigned i;
660e39da397SStephan Aßmus        while(nb--)
661e39da397SStephan Aßmus        {
662e39da397SStephan Aßmus            cell_ptr = *block_ptr++;
663e39da397SStephan Aßmus            i = cell_block_size;
664e39da397SStephan Aßmus            while(i--)
665e39da397SStephan Aßmus            {
666e39da397SStephan Aßmus                m_sorted_y[cell_ptr->y - m_min_y].start++;
667e39da397SStephan Aßmus                ++cell_ptr;
668e39da397SStephan Aßmus            }
669e39da397SStephan Aßmus        }
670e39da397SStephan Aßmus
671e39da397SStephan Aßmus        cell_ptr = *block_ptr++;
672e39da397SStephan Aßmus        i = m_num_cells & cell_block_mask;
673e39da397SStephan Aßmus        while(i--)
674e39da397SStephan Aßmus        {
675e39da397SStephan Aßmus            m_sorted_y[cell_ptr->y - m_min_y].start++;
676e39da397SStephan Aßmus            ++cell_ptr;
677e39da397SStephan Aßmus        }
678e39da397SStephan Aßmus
679e39da397SStephan Aßmus        // Convert the Y-histogram into the array of starting indexes
680e39da397SStephan Aßmus        unsigned start = 0;
681e39da397SStephan Aßmus        for(i = 0; i < m_sorted_y.size(); i++)
682e39da397SStephan Aßmus        {
683e39da397SStephan Aßmus            unsigned v = m_sorted_y[i].start;
684e39da397SStephan Aßmus            m_sorted_y[i].start = start;
685e39da397SStephan Aßmus            start += v;
686e39da397SStephan Aßmus        }
687e39da397SStephan Aßmus
688e39da397SStephan Aßmus        // Fill the cell pointer array sorted by Y
689e39da397SStephan Aßmus        block_ptr = m_cells;
690e39da397SStephan Aßmus        nb = m_num_cells >> cell_block_shift;
691e39da397SStephan Aßmus        while(nb--)
692e39da397SStephan Aßmus        {
693e39da397SStephan Aßmus            cell_ptr = *block_ptr++;
694e39da397SStephan Aßmus            i = cell_block_size;
695e39da397SStephan Aßmus            while(i--)
696e39da397SStephan Aßmus            {
697e39da397SStephan Aßmus                sorted_y& curr_y = m_sorted_y[cell_ptr->y - m_min_y];
698e39da397SStephan Aßmus                m_sorted_cells[curr_y.start + curr_y.num] = cell_ptr;
699e39da397SStephan Aßmus                ++curr_y.num;
700e39da397SStephan Aßmus                ++cell_ptr;
701e39da397SStephan Aßmus            }
702e39da397SStephan Aßmus        }
703e39da397SStephan Aßmus
704e39da397SStephan Aßmus        cell_ptr = *block_ptr++;
705e39da397SStephan Aßmus        i = m_num_cells & cell_block_mask;
706e39da397SStephan Aßmus        while(i--)
707e39da397SStephan Aßmus        {
708e39da397SStephan Aßmus            sorted_y& curr_y = m_sorted_y[cell_ptr->y - m_min_y];
709e39da397SStephan Aßmus            m_sorted_cells[curr_y.start + curr_y.num] = cell_ptr;
710e39da397SStephan Aßmus            ++curr_y.num;
711e39da397SStephan Aßmus            ++cell_ptr;
712e39da397SStephan Aßmus        }
713e39da397SStephan Aßmus
714e39da397SStephan Aßmus        // Finally arrange the X-arrays
715e39da397SStephan Aßmus        for(i = 0; i < m_sorted_y.size(); i++)
716e39da397SStephan Aßmus        {
717e39da397SStephan Aßmus            const sorted_y& curr_y = m_sorted_y[i];
718e39da397SStephan Aßmus            if(curr_y.num)
719e39da397SStephan Aßmus            {
720e39da397SStephan Aßmus                qsort_cells(m_sorted_cells.data() + curr_y.start, curr_y.num);
721e39da397SStephan Aßmus            }
722e39da397SStephan Aßmus        }
723e39da397SStephan Aßmus        m_sorted = true;
724e39da397SStephan Aßmus    }
725e39da397SStephan Aßmus
726e39da397SStephan Aßmus
727e39da397SStephan Aßmus
728e39da397SStephan Aßmus    //------------------------------------------------------scanline_hit_test
729e39da397SStephan Aßmus    class scanline_hit_test
730e39da397SStephan Aßmus    {
731e39da397SStephan Aßmus    public:
732e39da397SStephan Aßmus        scanline_hit_test(int x) : m_x(x), m_hit(false) {}
733e39da397SStephan Aßmus
734e39da397SStephan Aßmus        void reset_spans() {}
735e39da397SStephan Aßmus        void finalize(int) {}
736e39da397SStephan Aßmus        void add_cell(int x, int)
737e39da397SStephan Aßmus        {
738e39da397SStephan Aßmus            if(m_x == x) m_hit = true;
739e39da397SStephan Aßmus        }
740e39da397SStephan Aßmus        void add_span(int x, int len, int)
741e39da397SStephan Aßmus        {
742e39da397SStephan Aßmus            if(m_x >= x && m_x < x+len) m_hit = true;
743e39da397SStephan Aßmus        }
744e39da397SStephan Aßmus        unsigned num_spans() const { return 1; }
745e39da397SStephan Aßmus        bool hit() const { return m_hit; }
746e39da397SStephan Aßmus
747e39da397SStephan Aßmus    private:
748e39da397SStephan Aßmus        int  m_x;
749e39da397SStephan Aßmus        bool m_hit;
750e39da397SStephan Aßmus    };
751e39da397SStephan Aßmus
752e39da397SStephan Aßmus
753e39da397SStephan Aßmus}
754e39da397SStephan Aßmus
755e39da397SStephan Aßmus#endif
756