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// Liang-Barsky clipping
17//
18//----------------------------------------------------------------------------
19#ifndef AGG_CLIP_LIANG_BARSKY_INCLUDED
20#define AGG_CLIP_LIANG_BARSKY_INCLUDED
21
22#include "agg_basics.h"
23
24namespace agg
25{
26
27    //------------------------------------------------------------------------
28    enum clipping_flags_e
29    {
30        clipping_flags_x1_clipped = 4,
31        clipping_flags_x2_clipped = 1,
32        clipping_flags_y1_clipped = 8,
33        clipping_flags_y2_clipped = 2,
34        clipping_flags_x_clipped = clipping_flags_x1_clipped | clipping_flags_x2_clipped,
35        clipping_flags_y_clipped = clipping_flags_y1_clipped | clipping_flags_y2_clipped
36    };
37
38    //----------------------------------------------------------clipping_flags
39    // Determine the clipping code of the vertex according to the
40    // Cyrus-Beck line clipping algorithm
41    //
42    //        |        |
43    //  0110  |  0010  | 0011
44    //        |        |
45    // -------+--------+-------- clip_box.y2
46    //        |        |
47    //  0100  |  0000  | 0001
48    //        |        |
49    // -------+--------+-------- clip_box.y1
50    //        |        |
51    //  1100  |  1000  | 1001
52    //        |        |
53    //  clip_box.x1  clip_box.x2
54    //
55    //
56    template<class T>
57    inline unsigned clipping_flags(T x, T y, const rect_base<T>& clip_box)
58    {
59        return  (x > clip_box.x2) |
60               ((y > clip_box.y2) << 1) |
61               ((x < clip_box.x1) << 2) |
62               ((y < clip_box.y1) << 3);
63    }
64
65    //--------------------------------------------------------clipping_flags_x
66    template<class T>
67    inline unsigned clipping_flags_x(T x, const rect_base<T>& clip_box)
68    {
69        return  (x > clip_box.x2) | ((x < clip_box.x1) << 2);
70    }
71
72
73    //--------------------------------------------------------clipping_flags_y
74    template<class T>
75    inline unsigned clipping_flags_y(T y, const rect_base<T>& clip_box)
76    {
77        return ((y > clip_box.y2) << 1) | ((y < clip_box.y1) << 3);
78    }
79
80
81    //-------------------------------------------------------clip_liang_barsky
82    template<class T>
83    inline unsigned clip_liang_barsky(T x1, T y1, T x2, T y2,
84                                      const rect_base<T>& clip_box,
85                                      T* x, T* y)
86    {
87        const double nearzero = 1e-30;
88
89        double deltax = x2 - x1;
90        double deltay = y2 - y1;
91        double xin;
92        double xout;
93        double yin;
94        double yout;
95        double tinx;
96        double tiny;
97        double toutx;
98        double touty;
99        double tin1;
100        double tin2;
101        double tout1;
102        unsigned np = 0;
103
104        if(deltax == 0.0)
105        {
106            // bump off of the vertical
107            deltax = (x1 > clip_box.x1) ? -nearzero : nearzero;
108        }
109
110        if(deltay == 0.0)
111        {
112            // bump off of the horizontal
113            deltay = (y1 > clip_box.y1) ? -nearzero : nearzero;
114        }
115
116        if(deltax > 0.0)
117        {
118            // points to right
119            xin  = clip_box.x1;
120            xout = clip_box.x2;
121        }
122        else
123        {
124            xin  = clip_box.x2;
125            xout = clip_box.x1;
126        }
127
128        if(deltay > 0.0)
129        {
130            // points up
131            yin  = clip_box.y1;
132            yout = clip_box.y2;
133        }
134        else
135        {
136            yin  = clip_box.y2;
137            yout = clip_box.y1;
138        }
139
140        tinx = (xin - x1) / deltax;
141        tiny = (yin - y1) / deltay;
142
143        if (tinx < tiny)
144        {
145            // hits x first
146            tin1 = tinx;
147            tin2 = tiny;
148        }
149        else
150        {
151            // hits y first
152            tin1 = tiny;
153            tin2 = tinx;
154        }
155
156        if(tin1 <= 1.0)
157        {
158            if(0.0 < tin1)
159            {
160                *x++ = (T)xin;
161                *y++ = (T)yin;
162                ++np;
163            }
164
165            if(tin2 <= 1.0)
166            {
167                toutx = (xout - x1) / deltax;
168                touty = (yout - y1) / deltay;
169
170                tout1 = (toutx < touty) ? toutx : touty;
171
172                if(tin2 > 0.0 || tout1 > 0.0)
173                {
174                    if(tin2 <= tout1)
175                    {
176                        if(tin2 > 0.0)
177                        {
178                            if(tinx > tiny)
179                            {
180                                *x++ = (T)xin;
181                                *y++ = (T)(y1 + tinx * deltay);
182                            }
183                            else
184                            {
185                                *x++ = (T)(x1 + tiny * deltax);
186                                *y++ = (T)yin;
187                            }
188                            ++np;
189                        }
190
191                        if(tout1 < 1.0)
192                        {
193                            if(toutx < touty)
194                            {
195                                *x++ = (T)xout;
196                                *y++ = (T)(y1 + toutx * deltay);
197                            }
198                            else
199                            {
200                                *x++ = (T)(x1 + touty * deltax);
201                                *y++ = (T)yout;
202                            }
203                        }
204                        else
205                        {
206                            *x++ = x2;
207                            *y++ = y2;
208                        }
209                        ++np;
210                    }
211                    else
212                    {
213                        if(tinx > tiny)
214                        {
215                            *x++ = (T)xin;
216                            *y++ = (T)yout;
217                        }
218                        else
219                        {
220                            *x++ = (T)xout;
221                            *y++ = (T)yin;
222                        }
223                        ++np;
224                    }
225                }
226            }
227        }
228        return np;
229    }
230
231
232    //----------------------------------------------------------------------------
233    template<class T>
234    bool clip_move_point(T x1, T y1, T x2, T y2,
235                         const rect_base<T>& clip_box,
236                         T* x, T* y, unsigned flags)
237    {
238       T bound;
239
240       if(flags & clipping_flags_x_clipped)
241       {
242           if(x1 == x2)
243           {
244               return false;
245           }
246           bound = (flags & clipping_flags_x1_clipped) ? clip_box.x1 : clip_box.x2;
247           *y = (T)(double(bound - x1) * (y2 - y1) / (x2 - x1) + y1);
248           *x = bound;
249       }
250
251       flags = clipping_flags_y(*y, clip_box);
252       if(flags & clipping_flags_y_clipped)
253       {
254           if(y1 == y2)
255           {
256               return false;
257           }
258           bound = (flags & clipping_flags_y1_clipped) ? clip_box.y1 : clip_box.y2;
259           *x = (T)(double(bound - y1) * (x2 - x1) / (y2 - y1) + x1);
260           *y = bound;
261       }
262       return true;
263    }
264
265    //-------------------------------------------------------clip_line_segment
266    // Returns: ret >= 4        - Fully clipped
267    //          (ret & 1) != 0  - First point has been moved
268    //          (ret & 2) != 0  - Second point has been moved
269    //
270    template<class T>
271    unsigned clip_line_segment(T* x1, T* y1, T* x2, T* y2,
272                               const rect_base<T>& clip_box)
273    {
274        unsigned f1 = clipping_flags(*x1, *y1, clip_box);
275        unsigned f2 = clipping_flags(*x2, *y2, clip_box);
276        unsigned ret = 0;
277
278        if((f2 | f1) == 0)
279        {
280            // Fully visible
281            return 0;
282        }
283
284        if((f1 & clipping_flags_x_clipped) != 0 &&
285           (f1 & clipping_flags_x_clipped) == (f2 & clipping_flags_x_clipped))
286        {
287            // Fully clipped
288            return 4;
289        }
290
291        if((f1 & clipping_flags_y_clipped) != 0 &&
292           (f1 & clipping_flags_y_clipped) == (f2 & clipping_flags_y_clipped))
293        {
294            // Fully clipped
295            return 4;
296        }
297
298        T tx1 = *x1;
299        T ty1 = *y1;
300        T tx2 = *x2;
301        T ty2 = *y2;
302        if(f1)
303        {
304            if(!clip_move_point(tx1, ty1, tx2, ty2, clip_box, x1, y1, f1))
305            {
306                return 4;
307            }
308            if(*x1 == *x2 && *y1 == *y2)
309            {
310                return 4;
311            }
312            ret |= 1;
313        }
314        if(f2)
315        {
316            if(!clip_move_point(tx1, ty1, tx2, ty2, clip_box, x2, y2, f2))
317            {
318                return 4;
319            }
320            if(*x1 == *x2 && *y1 == *y2)
321            {
322                return 4;
323            }
324            ret |= 2;
325        }
326        return ret;
327    }
328
329
330}
331
332
333#endif
334