1 //----------------------------------------------------------------------------
2 // Anti-Grain Geometry - Version 2.4
3 // Copyright (C) 2002-2005 Maxim Shemanarev (http://www.antigrain.com)
4 //
5 // Permission to copy, use, modify, sell and distribute this software
6 // is granted provided this copyright notice appears in all copies.
7 // This software is provided "as is" without express or implied
8 // warranty, and with no claim as to its suitability for any purpose.
9 //
10 //----------------------------------------------------------------------------
11 // Contact: mcseem@antigrain.com
12 //          mcseemagg@yahoo.com
13 //          http://www.antigrain.com
14 //----------------------------------------------------------------------------
15 //
16 // classes dda_line_interpolator, dda2_line_interpolator
17 //
18 //----------------------------------------------------------------------------
19 
20 #ifndef AGG_DDA_LINE_INCLUDED
21 #define AGG_DDA_LINE_INCLUDED
22 
23 #include <stdlib.h>
24 #include "agg_basics.h"
25 
26 namespace mapserver
27 {
28 
29     //===================================================dda_line_interpolator
30     template<int FractionShift, int YShift=0> class dda_line_interpolator
31     {
32     public:
33         //--------------------------------------------------------------------
dda_line_interpolator()34         dda_line_interpolator() {}
35 
36         //--------------------------------------------------------------------
dda_line_interpolator(int y1,int y2,unsigned count)37         dda_line_interpolator(int y1, int y2, unsigned count) :
38             m_y(y1),
39             m_inc(((y2 - y1) << FractionShift) / int(count)),
40             m_dy(0)
41         {
42         }
43 
44         //--------------------------------------------------------------------
45         void operator ++ ()
46         {
47             m_dy += m_inc;
48         }
49 
50         //--------------------------------------------------------------------
51         void operator -- ()
52         {
53             m_dy -= m_inc;
54         }
55 
56         //--------------------------------------------------------------------
57         void operator += (unsigned n)
58         {
59             m_dy += m_inc * n;
60         }
61 
62         //--------------------------------------------------------------------
63         void operator -= (unsigned n)
64         {
65             m_dy -= m_inc * n;
66         }
67 
68 
69         //--------------------------------------------------------------------
y()70         int y()  const { return m_y + (m_dy >> (FractionShift-YShift)); }
dy()71         int dy() const { return m_dy; }
72 
73 
74     private:
75         int m_y;
76         int m_inc;
77         int m_dy;
78     };
79 
80 
81 
82 
83 
84     //=================================================dda2_line_interpolator
85     class dda2_line_interpolator
86     {
87     public:
88         typedef int save_data_type;
89         enum save_size_e { save_size = 2 };
90 
91         //--------------------------------------------------------------------
dda2_line_interpolator()92         dda2_line_interpolator() {}
93 
94         //-------------------------------------------- Forward-adjusted line
dda2_line_interpolator(int y1,int y2,int count)95         dda2_line_interpolator(int y1, int y2, int count) :
96             m_cnt(count <= 0 ? 1 : count),
97             m_lft((y2 - y1) / m_cnt),
98             m_rem((y2 - y1) % m_cnt),
99             m_mod(m_rem),
100             m_y(y1)
101         {
102             if(m_mod <= 0)
103             {
104                 m_mod += count;
105                 m_rem += count;
106                 m_lft--;
107             }
108             m_mod -= count;
109         }
110 
111         //-------------------------------------------- Backward-adjusted line
dda2_line_interpolator(int y1,int y2,int count,int)112         dda2_line_interpolator(int y1, int y2, int count, int) :
113             m_cnt(count <= 0 ? 1 : count),
114             m_lft((y2 - y1) / m_cnt),
115             m_rem((y2 - y1) % m_cnt),
116             m_mod(m_rem),
117             m_y(y1)
118         {
119             if(m_mod <= 0)
120             {
121                 m_mod += count;
122                 m_rem += count;
123                 m_lft--;
124             }
125         }
126 
127         //-------------------------------------------- Backward-adjusted line
dda2_line_interpolator(int y,int count)128         dda2_line_interpolator(int y, int count) :
129             m_cnt(count <= 0 ? 1 : count),
130             m_lft(y / m_cnt),
131             m_rem(y % m_cnt),
132             m_mod(m_rem),
133             m_y(0)
134         {
135             if(m_mod <= 0)
136             {
137                 m_mod += count;
138                 m_rem += count;
139                 m_lft--;
140             }
141         }
142 
143 
144         //--------------------------------------------------------------------
save(save_data_type * data)145         void save(save_data_type* data) const
146         {
147             data[0] = m_mod;
148             data[1] = m_y;
149         }
150 
151         //--------------------------------------------------------------------
load(const save_data_type * data)152         void load(const save_data_type* data)
153         {
154             m_mod = data[0];
155             m_y   = data[1];
156         }
157 
158         //--------------------------------------------------------------------
159         void operator++()
160         {
161             m_mod += m_rem;
162             m_y += m_lft;
163             if(m_mod > 0)
164             {
165                 m_mod -= m_cnt;
166                 m_y++;
167             }
168         }
169 
170         //--------------------------------------------------------------------
171         void operator--()
172         {
173             if(m_mod <= m_rem)
174             {
175                 m_mod += m_cnt;
176                 m_y--;
177             }
178             m_mod -= m_rem;
179             m_y -= m_lft;
180         }
181 
182         //--------------------------------------------------------------------
adjust_forward()183         void adjust_forward()
184         {
185             m_mod -= m_cnt;
186         }
187 
188         //--------------------------------------------------------------------
adjust_backward()189         void adjust_backward()
190         {
191             m_mod += m_cnt;
192         }
193 
194         //--------------------------------------------------------------------
mod()195         int mod() const { return m_mod; }
rem()196         int rem() const { return m_rem; }
lft()197         int lft() const { return m_lft; }
198 
199         //--------------------------------------------------------------------
y()200         int y() const { return m_y; }
201 
202     private:
203         int m_cnt;
204         int m_lft;
205         int m_rem;
206         int m_mod;
207         int m_y;
208     };
209 
210 
211 
212 
213 
214 
215 
216     //---------------------------------------------line_bresenham_interpolator
217     class line_bresenham_interpolator
218     {
219     public:
220         enum subpixel_scale_e
221         {
222             subpixel_shift = 8,
223             subpixel_scale = 1 << subpixel_shift,
224             subpixel_mask  = subpixel_scale - 1
225         };
226 
227         //--------------------------------------------------------------------
line_lr(int v)228         static int line_lr(int v) { return v >> subpixel_shift; }
229 
230         //--------------------------------------------------------------------
line_bresenham_interpolator(int x1,int y1,int x2,int y2)231         line_bresenham_interpolator(int x1, int y1, int x2, int y2) :
232             m_x1_lr(line_lr(x1)),
233             m_y1_lr(line_lr(y1)),
234             m_x2_lr(line_lr(x2)),
235             m_y2_lr(line_lr(y2)),
236             m_ver(abs(m_x2_lr - m_x1_lr) < abs(m_y2_lr - m_y1_lr)),
237             m_len(m_ver ? abs(m_y2_lr - m_y1_lr) :
238                           abs(m_x2_lr - m_x1_lr)),
239             m_inc(m_ver ? ((y2 > y1) ? 1 : -1) : ((x2 > x1) ? 1 : -1)),
240             m_interpolator(m_ver ? x1 : y1,
241                            m_ver ? x2 : y2,
242                            m_len)
243         {
244         }
245 
246         //--------------------------------------------------------------------
is_ver()247         bool     is_ver() const { return m_ver; }
len()248         unsigned len()    const { return m_len; }
inc()249         int      inc()    const { return m_inc; }
250 
251         //--------------------------------------------------------------------
hstep()252         void hstep()
253         {
254             ++m_interpolator;
255             m_x1_lr += m_inc;
256         }
257 
258         //--------------------------------------------------------------------
vstep()259         void vstep()
260         {
261             ++m_interpolator;
262             m_y1_lr += m_inc;
263         }
264 
265         //--------------------------------------------------------------------
x1()266         int x1() const { return m_x1_lr; }
y1()267         int y1() const { return m_y1_lr; }
x2()268         int x2() const { return line_lr(m_interpolator.y()); }
y2()269         int y2() const { return line_lr(m_interpolator.y()); }
x2_hr()270         int x2_hr() const { return m_interpolator.y(); }
y2_hr()271         int y2_hr() const { return m_interpolator.y(); }
272 
273     private:
274         int                    m_x1_lr;
275         int                    m_y1_lr;
276         int                    m_x2_lr;
277         int                    m_y2_lr;
278         bool                   m_ver;
279         unsigned               m_len;
280         int                    m_inc;
281         dda2_line_interpolator m_interpolator;
282 
283     };
284 
285 
286 }
287 
288 
289 
290 #endif
291