1 //---------------------------------------------------------------------------- 2 // Anti-Grain Geometry - Version 2.2 3 // Copyright (C) 2002-2004 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 //----------------------------------------------------------clipping_flags 28 // Determine the clipping code of the vertex according to the 29 // Cyrus-Beck line clipping algorithm 30 // 31 // | | 32 // 0110 | 0010 | 0011 33 // | | 34 // -------+--------+-------- clip_box.y2 35 // | | 36 // 0100 | 0000 | 0001 37 // | | 38 // -------+--------+-------- clip_box.y1 39 // | | 40 // 1100 | 1000 | 1001 41 // | | 42 // clip_box.x1 clip_box.x2 43 // 44 // 45 template<class T> 46 inline unsigned clipping_flags(T x, T y, const rect_base<T>& clip_box) 47 { 48 return (x > clip_box.x2) | 49 ((y > clip_box.y2) << 1) | 50 ((x < clip_box.x1) << 2) | 51 ((y < clip_box.y1) << 3); 52 } 53 54 55 56 //-------------------------------------------------------clip_liang_barsky 57 template<class T> 58 inline unsigned clip_liang_barsky(T x1, T y1, T x2, T y2, 59 const rect_base<T>& clip_box, 60 T* x, T* y) 61 { 62 const double nearzero = 1e-30; 63 64 double deltax = x2 - x1; 65 double deltay = y2 - y1; 66 double xin; 67 double xout; 68 double yin; 69 double yout; 70 double tinx; 71 double tiny; 72 double toutx; 73 double touty; 74 double tin1; 75 double tin2; 76 double tout1; 77 unsigned np = 0; 78 79 if(deltax == 0.0) 80 { 81 // bump off of the vertical 82 deltax = (x1 > clip_box.x1) ? -nearzero : nearzero; 83 } 84 85 if(deltay == 0.0) 86 { 87 // bump off of the horizontal 88 deltay = (y1 > clip_box.y1) ? -nearzero : nearzero; 89 } 90 91 if(deltax > 0.0) 92 { 93 // points to right 94 xin = clip_box.x1; 95 xout = clip_box.x2; 96 } 97 else 98 { 99 xin = clip_box.x2; 100 xout = clip_box.x1; 101 } 102 103 if(deltay > 0.0) 104 { 105 // points up 106 yin = clip_box.y1; 107 yout = clip_box.y2; 108 } 109 else 110 { 111 yin = clip_box.y2; 112 yout = clip_box.y1; 113 } 114 115 tinx = (xin - x1) / deltax; 116 tiny = (yin - y1) / deltay; 117 118 if (tinx < tiny) 119 { 120 // hits x first 121 tin1 = tinx; 122 tin2 = tiny; 123 } 124 else 125 { 126 // hits y first 127 tin1 = tiny; 128 tin2 = tinx; 129 } 130 131 if(tin1 <= 1.0) 132 { 133 if(0.0 < tin1) 134 { 135 *x++ = (T)xin; 136 *y++ = (T)yin; 137 ++np; 138 } 139 140 if(tin2 <= 1.0) 141 { 142 toutx = (xout - x1) / deltax; 143 touty = (yout - y1) / deltay; 144 145 tout1 = (toutx < touty) ? toutx : touty; 146 147 if(tin2 > 0.0 || tout1 > 0.0) 148 { 149 if(tin2 <= tout1) 150 { 151 if(tin2 > 0.0) 152 { 153 if(tinx > tiny) 154 { 155 *x++ = (T)xin; 156 *y++ = (T)(y1 + tinx * deltay); 157 } 158 else 159 { 160 *x++ = (T)(x1 + tiny * deltax); 161 *y++ = (T)yin; 162 } 163 ++np; 164 } 165 166 if(tout1 < 1.0) 167 { 168 if(toutx < touty) 169 { 170 *x++ = (T)xout; 171 *y++ = (T)(y1 + toutx * deltay); 172 } 173 else 174 { 175 *x++ = (T)(x1 + touty * deltax); 176 *y++ = (T)yout; 177 } 178 } 179 else 180 { 181 *x++ = x2; 182 *y++ = y2; 183 } 184 ++np; 185 } 186 else 187 { 188 if(tinx > tiny) 189 { 190 *x++ = (T)xin; 191 *y++ = (T)yout; 192 } 193 else 194 { 195 *x++ = (T)xout; 196 *y++ = (T)yin; 197 } 198 ++np; 199 } 200 } 201 } 202 } 203 return np; 204 } 205 206 207 } 208 209 #endif 210