headers/libs/agg/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