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 // General Polygon Clipper based on the GPC library by Alan Murta 00026 // Union, Intersection, XOR, A-B, B-A 00027 // Contact the author if you intend to use it in commercial applications! 00028 // http://www.cs.man.ac.uk/aig/staff/alan/software/ 00029 // Alan Murta (email: gpc@cs.man.ac.uk) 00030 // 00031 //---------------------------------------------------------------------------- 00032 00033 #ifndef AGG_CONV_GPC_INCLUDED 00034 #define AGG_CONV_GPC_INCLUDED 00035 00036 #include <math.h> 00037 #include "agg_basics.h" 00038 #include "agg_array.h" 00039 00040 extern "C" 00041 { 00042 #include "gpc.h" 00043 } 00044 00045 namespace agg 00046 { 00047 enum gpc_op_e 00048 { 00049 gpc_or, 00050 gpc_and, 00051 gpc_xor, 00052 gpc_a_minus_b, 00053 gpc_b_minus_a 00054 }; 00055 00056 00057 //================================================================conv_gpc 00058 template<class VSA, class VSB> class conv_gpc 00059 { 00060 enum status 00061 { 00062 status_move_to, 00063 status_line_to, 00064 status_stop 00065 }; 00066 00067 struct contour_header_type 00068 { 00069 int num_vertices; 00070 int hole_flag; 00071 gpc_vertex* vertices; 00072 }; 00073 00074 typedef pod_bvector<gpc_vertex, 8> vertex_array_type; 00075 typedef pod_bvector<contour_header_type, 6> contour_header_array_type; 00076 00077 00078 public: 00079 typedef VSA source_a_type; 00080 typedef VSB source_b_type; 00081 typedef conv_gpc<source_a_type, source_b_type> self_type; 00082 00083 ~conv_gpc() 00084 { 00085 free_gpc_data(); 00086 } 00087 00088 conv_gpc(source_a_type& a, source_b_type& b, gpc_op_e op = gpc_or) : 00089 m_src_a(&a), 00090 m_src_b(&b), 00091 m_status(status_move_to), 00092 m_vertex(-1), 00093 m_contour(-1), 00094 m_operation(op) 00095 { 00096 memset(&m_poly_a, 0, sizeof(m_poly_a)); 00097 memset(&m_poly_b, 0, sizeof(m_poly_b)); 00098 memset(&m_result, 0, sizeof(m_result)); 00099 } 00100 00101 void attach1(VSA& source) { m_src_a = &source; } 00102 void attach2(VSB& source) { m_src_b = &source; } 00103 00104 void operation(gpc_op_e v) { m_operation = v; } 00105 00106 // Vertex Source Interface 00107 void rewind(unsigned path_id); 00108 unsigned vertex(double* x, double* y); 00109 00110 private: 00111 conv_gpc(const conv_gpc<VSA, VSB>&); 00112 const conv_gpc<VSA, VSB>& operator = (const conv_gpc<VSA, VSB>&); 00113 00114 //-------------------------------------------------------------------- 00115 void free_polygon(gpc_polygon& p); 00116 void free_result(); 00117 void free_gpc_data(); 00118 void start_contour(); 00119 void add_vertex(double x, double y); 00120 void end_contour(unsigned orientation); 00121 void make_polygon(gpc_polygon& p); 00122 void start_extracting(); 00123 bool next_contour(); 00124 bool next_vertex(double* x, double* y); 00125 00126 00127 //-------------------------------------------------------------------- 00128 template<class VS> void add(VS& src, gpc_polygon& p) 00129 { 00130 unsigned cmd; 00131 double x, y; 00132 double start_x = 0.0; 00133 double start_y = 0.0; 00134 bool line_to = false; 00135 unsigned orientation = 0; 00136 00137 m_contour_accumulator.remove_all(); 00138 00139 while(!is_stop(cmd = src.vertex(&x, &y))) 00140 { 00141 if(is_vertex(cmd)) 00142 { 00143 if(is_move_to(cmd)) 00144 { 00145 if(line_to) 00146 { 00147 end_contour(orientation); 00148 orientation = 0; 00149 } 00150 start_contour(); 00151 start_x = x; 00152 start_y = y; 00153 } 00154 add_vertex(x, y); 00155 line_to = true; 00156 } 00157 else 00158 { 00159 if(is_end_poly(cmd)) 00160 { 00161 orientation = get_orientation(cmd); 00162 if(line_to && is_closed(cmd)) 00163 { 00164 add_vertex(start_x, start_y); 00165 } 00166 } 00167 } 00168 } 00169 if(line_to) 00170 { 00171 end_contour(orientation); 00172 } 00173 make_polygon(p); 00174 } 00175 00176 00177 private: 00178 //-------------------------------------------------------------------- 00179 source_a_type* m_src_a; 00180 source_b_type* m_src_b; 00181 status m_status; 00182 int m_vertex; 00183 int m_contour; 00184 gpc_op_e m_operation; 00185 vertex_array_type m_vertex_accumulator; 00186 contour_header_array_type m_contour_accumulator; 00187 gpc_polygon m_poly_a; 00188 gpc_polygon m_poly_b; 00189 gpc_polygon m_result; 00190 }; 00191 00192 00193 00194 00195 00196 //------------------------------------------------------------------------ 00197 template<class VSA, class VSB> 00198 void conv_gpc<VSA, VSB>::free_polygon(gpc_polygon& p) 00199 { 00200 int i; 00201 for(i = 0; i < p.num_contours; i++) 00202 { 00203 pod_allocator<gpc_vertex>::deallocate(p.contour[i].vertex, 00204 p.contour[i].num_vertices); 00205 } 00206 pod_allocator<gpc_vertex_list>::deallocate(p.contour, p.num_contours); 00207 memset(&p, 0, sizeof(gpc_polygon)); 00208 } 00209 00210 00211 //------------------------------------------------------------------------ 00212 template<class VSA, class VSB> 00213 void conv_gpc<VSA, VSB>::free_result() 00214 { 00215 if(m_result.contour) 00216 { 00217 gpc_free_polygon(&m_result); 00218 } 00219 memset(&m_result, 0, sizeof(m_result)); 00220 } 00221 00222 00223 //------------------------------------------------------------------------ 00224 template<class VSA, class VSB> 00225 void conv_gpc<VSA, VSB>::free_gpc_data() 00226 { 00227 free_polygon(m_poly_a); 00228 free_polygon(m_poly_b); 00229 free_result(); 00230 } 00231 00232 00233 //------------------------------------------------------------------------ 00234 template<class VSA, class VSB> 00235 void conv_gpc<VSA, VSB>::start_contour() 00236 { 00237 contour_header_type h; 00238 memset(&h, 0, sizeof(h)); 00239 m_contour_accumulator.add(h); 00240 m_vertex_accumulator.remove_all(); 00241 } 00242 00243 00244 //------------------------------------------------------------------------ 00245 template<class VSA, class VSB> 00246 inline void conv_gpc<VSA, VSB>::add_vertex(double x, double y) 00247 { 00248 gpc_vertex v; 00249 v.x = x; 00250 v.y = y; 00251 m_vertex_accumulator.add(v); 00252 } 00253 00254 00255 //------------------------------------------------------------------------ 00256 template<class VSA, class VSB> 00257 void conv_gpc<VSA, VSB>::end_contour(unsigned orientation) 00258 { 00259 if(m_contour_accumulator.size()) 00260 { 00261 if(m_vertex_accumulator.size() > 2) 00262 { 00263 contour_header_type& h = 00264 m_contour_accumulator[m_contour_accumulator.size() - 1]; 00265 00266 h.num_vertices = m_vertex_accumulator.size(); 00267 h.hole_flag = 0; 00268 00269 // TO DO: Clarify the "holes" 00270 //if(is_cw(orientation)) h.hole_flag = 1; 00271 00272 h.vertices = pod_allocator<gpc_vertex>::allocate(h.num_vertices); 00273 gpc_vertex* d = h.vertices; 00274 int i; 00275 for(i = 0; i < h.num_vertices; i++) 00276 { 00277 const gpc_vertex& s = m_vertex_accumulator[i]; 00278 d->x = s.x; 00279 d->y = s.y; 00280 ++d; 00281 } 00282 } 00283 else 00284 { 00285 m_vertex_accumulator.remove_last(); 00286 } 00287 } 00288 } 00289 00290 00291 //------------------------------------------------------------------------ 00292 template<class VSA, class VSB> 00293 void conv_gpc<VSA, VSB>::make_polygon(gpc_polygon& p) 00294 { 00295 free_polygon(p); 00296 if(m_contour_accumulator.size()) 00297 { 00298 p.num_contours = m_contour_accumulator.size(); 00299 00300 p.hole = 0; 00301 p.contour = pod_allocator<gpc_vertex_list>::allocate(p.num_contours); 00302 00303 int i; 00304 gpc_vertex_list* pv = p.contour; 00305 for(i = 0; i < p.num_contours; i++) 00306 { 00307 const contour_header_type& h = m_contour_accumulator[i]; 00308 pv->num_vertices = h.num_vertices; 00309 pv->vertex = h.vertices; 00310 ++pv; 00311 } 00312 } 00313 } 00314 00315 00316 //------------------------------------------------------------------------ 00317 template<class VSA, class VSB> 00318 void conv_gpc<VSA, VSB>::start_extracting() 00319 { 00320 m_status = status_move_to; 00321 m_contour = -1; 00322 m_vertex = -1; 00323 } 00324 00325 00326 //------------------------------------------------------------------------ 00327 template<class VSA, class VSB> 00328 bool conv_gpc<VSA, VSB>::next_contour() 00329 { 00330 if(++m_contour < m_result.num_contours) 00331 { 00332 m_vertex = -1; 00333 return true; 00334 } 00335 return false; 00336 } 00337 00338 00339 //------------------------------------------------------------------------ 00340 template<class VSA, class VSB> 00341 inline bool conv_gpc<VSA, VSB>::next_vertex(double* x, double* y) 00342 { 00343 const gpc_vertex_list& vlist = m_result.contour[m_contour]; 00344 if(++m_vertex < vlist.num_vertices) 00345 { 00346 const gpc_vertex& v = vlist.vertex[m_vertex]; 00347 *x = v.x; 00348 *y = v.y; 00349 return true; 00350 } 00351 return false; 00352 } 00353 00354 00355 //------------------------------------------------------------------------ 00356 template<class VSA, class VSB> 00357 void conv_gpc<VSA, VSB>::rewind(unsigned path_id) 00358 { 00359 free_result(); 00360 m_src_a->rewind(path_id); 00361 m_src_b->rewind(path_id); 00362 add(*m_src_a, m_poly_a); 00363 add(*m_src_b, m_poly_b); 00364 switch(m_operation) 00365 { 00366 case gpc_or: 00367 gpc_polygon_clip(GPC_UNION, 00368 &m_poly_a, 00369 &m_poly_b, 00370 &m_result); 00371 break; 00372 00373 case gpc_and: 00374 gpc_polygon_clip(GPC_INT, 00375 &m_poly_a, 00376 &m_poly_b, 00377 &m_result); 00378 break; 00379 00380 case gpc_xor: 00381 gpc_polygon_clip(GPC_XOR, 00382 &m_poly_a, 00383 &m_poly_b, 00384 &m_result); 00385 break; 00386 00387 case gpc_a_minus_b: 00388 gpc_polygon_clip(GPC_DIFF, 00389 &m_poly_a, 00390 &m_poly_b, 00391 &m_result); 00392 break; 00393 00394 case gpc_b_minus_a: 00395 gpc_polygon_clip(GPC_DIFF, 00396 &m_poly_b, 00397 &m_poly_a, 00398 &m_result); 00399 break; 00400 } 00401 start_extracting(); 00402 } 00403 00404 00405 //------------------------------------------------------------------------ 00406 template<class VSA, class VSB> 00407 unsigned conv_gpc<VSA, VSB>::vertex(double* x, double* y) 00408 { 00409 if(m_status == status_move_to) 00410 { 00411 if(next_contour()) 00412 { 00413 if(next_vertex(x, y)) 00414 { 00415 m_status = status_line_to; 00416 return path_cmd_move_to; 00417 } 00418 m_status = status_stop; 00419 return path_cmd_end_poly | path_flags_close; 00420 } 00421 } 00422 else 00423 { 00424 if(next_vertex(x, y)) 00425 { 00426 return path_cmd_line_to; 00427 } 00428 else 00429 { 00430 m_status = status_move_to; 00431 } 00432 return path_cmd_end_poly | path_flags_close; 00433 } 00434 return path_cmd_stop; 00435 } 00436 00437 00438 } 00439 00440 00441 #endif