Anti-Grain Geometry - AGG (libagg)
2.5
|
00001 //---------------------------------------------------------------------------- 00002 // Anti-Grain Geometry (AGG) - Version 2.5 00003 // A high quality rendering engine for C++ 00004 // Copyright (C) 2002-2006 Maxim Shemanarev 00005 // Contact: mcseem@antigrain.com 00006 // mcseemagg@yahoo.com 00007 // http://antigrain.com 00008 // 00009 // AGG is free software; you can redistribute it and/or 00010 // modify it under the terms of the GNU General Public License 00011 // as published by the Free Software Foundation; either version 2 00012 // of the License, or (at your option) any later version. 00013 // 00014 // AGG is distributed in the hope that it will be useful, 00015 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00016 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00017 // GNU General Public License for more details. 00018 // 00019 // You should have received a copy of the GNU General Public License 00020 // along with AGG; if not, write to the Free Software 00021 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, 00022 // MA 02110-1301, USA. 00023 //---------------------------------------------------------------------------- 00024 00025 #ifndef AGG_CLIP_LIANG_BARSKY_INCLUDED 00026 #define AGG_CLIP_LIANG_BARSKY_INCLUDED 00027 00028 #include "agg_basics.h" 00029 00030 namespace agg 00031 { 00032 00033 //------------------------------------------------------------------------ 00034 enum clipping_flags_e 00035 { 00036 clipping_flags_x1_clipped = 4, 00037 clipping_flags_x2_clipped = 1, 00038 clipping_flags_y1_clipped = 8, 00039 clipping_flags_y2_clipped = 2, 00040 clipping_flags_x_clipped = clipping_flags_x1_clipped | clipping_flags_x2_clipped, 00041 clipping_flags_y_clipped = clipping_flags_y1_clipped | clipping_flags_y2_clipped 00042 }; 00043 00044 //----------------------------------------------------------clipping_flags 00045 // Determine the clipping code of the vertex according to the 00046 // Cyrus-Beck line clipping algorithm 00047 // 00048 // | | 00049 // 0110 | 0010 | 0011 00050 // | | 00051 // -------+--------+-------- clip_box.y2 00052 // | | 00053 // 0100 | 0000 | 0001 00054 // | | 00055 // -------+--------+-------- clip_box.y1 00056 // | | 00057 // 1100 | 1000 | 1001 00058 // | | 00059 // clip_box.x1 clip_box.x2 00060 // 00061 // 00062 template<class T> 00063 inline unsigned clipping_flags(T x, T y, const rect_base<T>& clip_box) 00064 { 00065 return (x > clip_box.x2) | 00066 ((y > clip_box.y2) << 1) | 00067 ((x < clip_box.x1) << 2) | 00068 ((y < clip_box.y1) << 3); 00069 } 00070 00071 //--------------------------------------------------------clipping_flags_x 00072 template<class T> 00073 inline unsigned clipping_flags_x(T x, const rect_base<T>& clip_box) 00074 { 00075 return (x > clip_box.x2) | ((x < clip_box.x1) << 2); 00076 } 00077 00078 00079 //--------------------------------------------------------clipping_flags_y 00080 template<class T> 00081 inline unsigned clipping_flags_y(T y, const rect_base<T>& clip_box) 00082 { 00083 return ((y > clip_box.y2) << 1) | ((y < clip_box.y1) << 3); 00084 } 00085 00086 00087 //-------------------------------------------------------clip_liang_barsky 00088 template<class T> 00089 inline unsigned clip_liang_barsky(T x1, T y1, T x2, T y2, 00090 const rect_base<T>& clip_box, 00091 T* x, T* y) 00092 { 00093 const double nearzero = 1e-30; 00094 00095 double deltax = x2 - x1; 00096 double deltay = y2 - y1; 00097 double xin; 00098 double xout; 00099 double yin; 00100 double yout; 00101 double tinx; 00102 double tiny; 00103 double toutx; 00104 double touty; 00105 double tin1; 00106 double tin2; 00107 double tout1; 00108 unsigned np = 0; 00109 00110 if(deltax == 0.0) 00111 { 00112 // bump off of the vertical 00113 deltax = (x1 > clip_box.x1) ? -nearzero : nearzero; 00114 } 00115 00116 if(deltay == 0.0) 00117 { 00118 // bump off of the horizontal 00119 deltay = (y1 > clip_box.y1) ? -nearzero : nearzero; 00120 } 00121 00122 if(deltax > 0.0) 00123 { 00124 // points to right 00125 xin = clip_box.x1; 00126 xout = clip_box.x2; 00127 } 00128 else 00129 { 00130 xin = clip_box.x2; 00131 xout = clip_box.x1; 00132 } 00133 00134 if(deltay > 0.0) 00135 { 00136 // points up 00137 yin = clip_box.y1; 00138 yout = clip_box.y2; 00139 } 00140 else 00141 { 00142 yin = clip_box.y2; 00143 yout = clip_box.y1; 00144 } 00145 00146 tinx = (xin - x1) / deltax; 00147 tiny = (yin - y1) / deltay; 00148 00149 if (tinx < tiny) 00150 { 00151 // hits x first 00152 tin1 = tinx; 00153 tin2 = tiny; 00154 } 00155 else 00156 { 00157 // hits y first 00158 tin1 = tiny; 00159 tin2 = tinx; 00160 } 00161 00162 if(tin1 <= 1.0) 00163 { 00164 if(0.0 < tin1) 00165 { 00166 *x++ = (T)xin; 00167 *y++ = (T)yin; 00168 ++np; 00169 } 00170 00171 if(tin2 <= 1.0) 00172 { 00173 toutx = (xout - x1) / deltax; 00174 touty = (yout - y1) / deltay; 00175 00176 tout1 = (toutx < touty) ? toutx : touty; 00177 00178 if(tin2 > 0.0 || tout1 > 0.0) 00179 { 00180 if(tin2 <= tout1) 00181 { 00182 if(tin2 > 0.0) 00183 { 00184 if(tinx > tiny) 00185 { 00186 *x++ = (T)xin; 00187 *y++ = (T)(y1 + tinx * deltay); 00188 } 00189 else 00190 { 00191 *x++ = (T)(x1 + tiny * deltax); 00192 *y++ = (T)yin; 00193 } 00194 ++np; 00195 } 00196 00197 if(tout1 < 1.0) 00198 { 00199 if(toutx < touty) 00200 { 00201 *x++ = (T)xout; 00202 *y++ = (T)(y1 + toutx * deltay); 00203 } 00204 else 00205 { 00206 *x++ = (T)(x1 + touty * deltax); 00207 *y++ = (T)yout; 00208 } 00209 } 00210 else 00211 { 00212 *x++ = x2; 00213 *y++ = y2; 00214 } 00215 ++np; 00216 } 00217 else 00218 { 00219 if(tinx > tiny) 00220 { 00221 *x++ = (T)xin; 00222 *y++ = (T)yout; 00223 } 00224 else 00225 { 00226 *x++ = (T)xout; 00227 *y++ = (T)yin; 00228 } 00229 ++np; 00230 } 00231 } 00232 } 00233 } 00234 return np; 00235 } 00236 00237 00238 //---------------------------------------------------------------------------- 00239 template<class T> 00240 bool clip_move_point(T x1, T y1, T x2, T y2, 00241 const rect_base<T>& clip_box, 00242 T* x, T* y, unsigned flags) 00243 { 00244 T bound; 00245 00246 if(flags & clipping_flags_x_clipped) 00247 { 00248 if(x1 == x2) 00249 { 00250 return false; 00251 } 00252 bound = (flags & clipping_flags_x1_clipped) ? clip_box.x1 : clip_box.x2; 00253 *y = (T)(double(bound - x1) * (y2 - y1) / (x2 - x1) + y1); 00254 *x = bound; 00255 } 00256 00257 flags = clipping_flags_y(*y, clip_box); 00258 if(flags & clipping_flags_y_clipped) 00259 { 00260 if(y1 == y2) 00261 { 00262 return false; 00263 } 00264 bound = (flags & clipping_flags_y1_clipped) ? clip_box.y1 : clip_box.y2; 00265 *x = (T)(double(bound - y1) * (x2 - x1) / (y2 - y1) + x1); 00266 *y = bound; 00267 } 00268 return true; 00269 } 00270 00271 //-------------------------------------------------------clip_line_segment 00272 // Returns: ret >= 4 - Fully clipped 00273 // (ret & 1) != 0 - First point has been moved 00274 // (ret & 2) != 0 - Second point has been moved 00275 // 00276 template<class T> 00277 unsigned clip_line_segment(T* x1, T* y1, T* x2, T* y2, 00278 const rect_base<T>& clip_box) 00279 { 00280 unsigned f1 = clipping_flags(*x1, *y1, clip_box); 00281 unsigned f2 = clipping_flags(*x2, *y2, clip_box); 00282 unsigned ret = 0; 00283 00284 if((f2 | f1) == 0) 00285 { 00286 // Fully visible 00287 return 0; 00288 } 00289 00290 if((f1 & clipping_flags_x_clipped) != 0 && 00291 (f1 & clipping_flags_x_clipped) == (f2 & clipping_flags_x_clipped)) 00292 { 00293 // Fully clipped 00294 return 4; 00295 } 00296 00297 if((f1 & clipping_flags_y_clipped) != 0 && 00298 (f1 & clipping_flags_y_clipped) == (f2 & clipping_flags_y_clipped)) 00299 { 00300 // Fully clipped 00301 return 4; 00302 } 00303 00304 T tx1 = *x1; 00305 T ty1 = *y1; 00306 T tx2 = *x2; 00307 T ty2 = *y2; 00308 if(f1) 00309 { 00310 if(!clip_move_point(tx1, ty1, tx2, ty2, clip_box, x1, y1, f1)) 00311 { 00312 return 4; 00313 } 00314 if(*x1 == *x2 && *y1 == *y2) 00315 { 00316 return 4; 00317 } 00318 ret |= 1; 00319 } 00320 if(f2) 00321 { 00322 if(!clip_move_point(tx1, ty1, tx2, ty2, clip_box, x2, y2, f2)) 00323 { 00324 return 4; 00325 } 00326 if(*x1 == *x2 && *y1 == *y2) 00327 { 00328 return 4; 00329 } 00330 ret |= 2; 00331 } 00332 return ret; 00333 } 00334 00335 00336 } 00337 00338 00339 #endif