xref: /haiku/headers/libs/agg/agg_clip_liang_barsky.h (revision e39da397f5ff79f2db9f9a3ddf1852b6710578af)
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 
24 namespace 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>
clipping_flags(T x,T y,const rect_base<T> & clip_box)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>
clipping_flags_x(T x,const rect_base<T> & clip_box)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>
clipping_flags_y(T y,const rect_base<T> & clip_box)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>
clip_liang_barsky(T x1,T y1,T x2,T y2,const rect_base<T> & clip_box,T * x,T * y)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>
clip_move_point(T x1,T y1,T x2,T y2,const rect_base<T> & clip_box,T * x,T * y,unsigned flags)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>
clip_line_segment(T * x1,T * y1,T * x2,T * y2,const rect_base<T> & clip_box)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