Anti-Grain Geometry Tutorial
agg_clip_liang_barsky.h
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>
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
agg
Definition: agg_arc.cpp:24