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 334