agg/source/agg_path_storage.cpp

   1 //----------------------------------------------------------------------------
   2 // Anti-Grain Geometry - Version 2.3
   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 // Class path_storage
  17 //
  18 //----------------------------------------------------------------------------
  19 #include <string.h>
  20 #include <math.h>
  21 #include "agg_path_storage.h"
  22 #include "agg_math.h"
  23 #include "agg_bezier_arc.h"
  24
  25
  26 namespace agg
  27 {
  28
  29     //------------------------------------------------------------------------
  30     path_storage::~path_storage()
  31     {
  32         if(m_total_blocks)
  33         {
  34             double** coord_blk = m_coord_blocks + m_total_blocks - 1;
  35             while(m_total_blocks--)
  36             {
  37                 delete [] *coord_blk;
  38                 --coord_blk;
  39             }
  40             delete [] m_coord_blocks;
  41         }
  42     }
  43
  44
  45     //------------------------------------------------------------------------
  46     path_storage::path_storage() :
  47         m_total_vertices(0),
  48         m_total_blocks(0),
  49         m_max_blocks(0),
  50         m_coord_blocks(0),
  51         m_cmd_blocks(0),
  52         m_iterator(0)
  53     {
  54     }
  55
  56
  57     //------------------------------------------------------------------------
  58     path_storage::path_storage(const path_storage& ps) :
  59         m_total_vertices(0),
  60         m_total_blocks(0),
  61         m_max_blocks(0),
  62         m_coord_blocks(0),
  63         m_cmd_blocks(0),
  64         m_iterator(0)
  65     {
  66         copy_from(ps);
  67     }
  68
  69
  70     //------------------------------------------------------------------------
  71     void path_storage::remove_all()
  72     {
  73         m_total_vertices = 0;
  74         m_iterator = 0;
  75     }
  76
  77
  78     //------------------------------------------------------------------------
  79     void path_storage::copy_from(const path_storage& ps)
  80     {
  81         remove_all();
  82         unsigned i;
  83         for(i = 0; i < ps.total_vertices(); i++)
  84         {
  85             double x, y;
  86             unsigned cmd = ps.vertex(i, &x, &y);
  87             add_vertex(x, y, cmd);
  88         }
  89     }
  90
  91
  92     //------------------------------------------------------------------------
  93     void path_storage::allocate_block(unsigned nb)
  94     {
  95         if(nb >= m_max_blocks)
  96         {
  97             double** new_coords =
  98                 new double* [(m_max_blocks + block_pool) * 2];
  99
 100             unsigned char** new_cmds =
 101                 (unsigned char**)(new_coords + m_max_blocks + block_pool);
 102
 103             if(m_coord_blocks)
 104             {
 105                 memcpy(new_coords,
 106                        m_coord_blocks,
 107                        m_max_blocks * sizeof(double*));
 108
 109                 memcpy(new_cmds,
 110                        m_cmd_blocks,
 111                        m_max_blocks * sizeof(unsigned char*));
 112
 113                 delete [] m_coord_blocks;
 114             }
 115             m_coord_blocks = new_coords;
 116             m_cmd_blocks = new_cmds;
 117             m_max_blocks += block_pool;
 118         }
 119         m_coord_blocks[nb] =
 120             new double [block_size * 2 +
 121                         block_size /
 122                         (sizeof(double) / sizeof(unsigned char))];
 123
 124         m_cmd_blocks[nb]  =
 125             (unsigned char*)(m_coord_blocks[nb] + block_size * 2);
 126
 127         m_total_blocks++;
 128     }
 129
 130
 131     //------------------------------------------------------------------------
 132     void path_storage::rewind(unsigned path_id)
 133     {
 134         m_iterator = path_id;
 135     }
 136
 137
 138
 139     //------------------------------------------------------------------------
 140     void path_storage::arc_to(double rx, double ry,
 141                               double angle,
 142                               bool large_arc_flag,
 143                               bool sweep_flag,
 144                               double x, double y)
 145     {
 146         if(m_total_vertices && is_vertex(command(m_total_vertices - 1)))
 147         {
 148             const double epsilon = 1e-30;
 149             double x0 = 0.0;
 150             double y0 = 0.0;
 151             last_vertex(&x0, &y0);
 152
 153             rx = fabs(rx);
 154             ry = fabs(ry);
 155
 156             // Ensure radii are valid
 157             //-------------------------
 158             if(rx < epsilon || ry < epsilon)
 159             {
 160                 line_to(x, y);
 161                 return;
 162             }
 163
 164             if(calc_distance(x0, y0, x, y) < epsilon)
 165             {
 166                 // If the endpoints (x, y) and (x0, y0) are identical, then this
 167                 // is equivalent to omitting the elliptical arc segment entirely.
 168                 return;
 169             }
 170             bezier_arc_svg a(x0, y0, rx, ry, angle, large_arc_flag, sweep_flag, x, y);
 171             if(a.radii_ok())
 172             {
 173                 add_path(a, 0, true);
 174             }
 175             else
 176             {
 177                 line_to(x, y);
 178             }
 179         }
 180         else
 181         {
 182             move_to(x, y);
 183         }
 184     }
 185
 186
 187     //------------------------------------------------------------------------
 188     void path_storage::arc_rel(double rx, double ry,
 189                                double angle,
 190                                bool large_arc_flag,
 191                                bool sweep_flag,
 192                                double dx, double dy)
 193     {
 194         rel_to_abs(&dx, &dy);
 195         arc_to(rx, ry, angle, large_arc_flag, sweep_flag, dx, dy);
 196     }
 197
 198
 199     //------------------------------------------------------------------------
 200     void path_storage::curve3(double x_ctrl, double y_ctrl,
 201                               double x_to,   double y_to)
 202     {
 203         add_vertex(x_ctrl, y_ctrl, path_cmd_curve3);
 204         add_vertex(x_to,   y_to,   path_cmd_curve3);
 205     }
 206
 207     //------------------------------------------------------------------------
 208     void path_storage::curve3_rel(double dx_ctrl, double dy_ctrl,
 209                                   double dx_to,   double dy_to)
 210     {
 211         rel_to_abs(&dx_ctrl, &dy_ctrl);
 212         rel_to_abs(&dx_to,   &dy_to);
 213         add_vertex(dx_ctrl, dy_ctrl, path_cmd_curve3);
 214         add_vertex(dx_to,   dy_to,   path_cmd_curve3);
 215     }
 216
 217     //------------------------------------------------------------------------
 218     void path_storage::curve3(double x_to, double y_to)
 219     {
 220         double x0 = 0;
 221         double y0 = 0;
 222         if(is_vertex(last_vertex(&x0, &y0)))
 223         {
 224             double x_ctrl = 0;
 225             double y_ctrl = 0;
 226             unsigned cmd = prev_vertex(&x_ctrl, &y_ctrl);
 227             if(is_curve(cmd))
 228             {
 229                 x_ctrl = x0 + x0 - x_ctrl;
 230                 y_ctrl = y0 + y0 - y_ctrl;
 231             }
 232             else
 233             {
 234                 x_ctrl = x0;
 235                 y_ctrl = y0;
 236             }
 237             curve3(x_ctrl, y_ctrl, x_to, y_to);
 238         }
 239     }
 240
 241
 242     //------------------------------------------------------------------------
 243     void path_storage::curve3_rel(double dx_to, double dy_to)
 244     {
 245         rel_to_abs(&dx_to, &dy_to);
 246         curve3(dx_to, dy_to);
 247     }
 248
 249
 250     //------------------------------------------------------------------------
 251     void path_storage::curve4(double x_ctrl1, double y_ctrl1,
 252                               double x_ctrl2, double y_ctrl2,
 253                               double x_to,    double y_to)
 254     {
 255         add_vertex(x_ctrl1, y_ctrl1, path_cmd_curve4);
 256         add_vertex(x_ctrl2, y_ctrl2, path_cmd_curve4);
 257         add_vertex(x_to,    y_to,    path_cmd_curve4);
 258     }
 259
 260     //------------------------------------------------------------------------
 261     void path_storage::curve4_rel(double dx_ctrl1, double dy_ctrl1,
 262                                   double dx_ctrl2, double dy_ctrl2,
 263                                   double dx_to,    double dy_to)
 264     {
 265         rel_to_abs(&dx_ctrl1, &dy_ctrl1);
 266         rel_to_abs(&dx_ctrl2, &dy_ctrl2);
 267         rel_to_abs(&dx_to,    &dy_to);
 268         add_vertex(dx_ctrl1, dy_ctrl1, path_cmd_curve4);
 269         add_vertex(dx_ctrl2, dy_ctrl2, path_cmd_curve4);
 270         add_vertex(dx_to,    dy_to,    path_cmd_curve4);
 271     }
 272
 273
 274     //------------------------------------------------------------------------
 275     void path_storage::curve4(double x_ctrl2, double y_ctrl2,
 276                               double x_to,    double y_to)
 277     {
 278         double x0 = 0;
 279         double y0 = 0;
 280         if(is_vertex(last_vertex(&x0, &y0)))
 281         {
 282             double x_ctrl1 = 0;
 283             double y_ctrl1 = 0;
 284             unsigned cmd = prev_vertex(&x_ctrl1, &y_ctrl1);
 285             if(is_curve(cmd))
 286             {
 287                 x_ctrl1 = x0 + x0 - x_ctrl1;
 288                 y_ctrl1 = y0 + y0 - y_ctrl1;
 289             }
 290             else
 291             {
 292                 x_ctrl1 = x0;
 293                 y_ctrl1 = y0;
 294             }
 295             curve4(x_ctrl1, y_ctrl1, x_ctrl2, y_ctrl2, x_to, y_to);
 296         }
 297     }
 298
 299
 300     //------------------------------------------------------------------------
 301     void path_storage::curve4_rel(double dx_ctrl2, double dy_ctrl2,
 302                                   double dx_to,    double dy_to)
 303     {
 304         rel_to_abs(&dx_ctrl2, &dy_ctrl2);
 305         rel_to_abs(&dx_to,    &dy_to);
 306         curve4(dx_ctrl2, dy_ctrl2, dx_to, dy_to);
 307     }
 308
 309
 310     //------------------------------------------------------------------------
 311     void path_storage::end_poly(unsigned flags)
 312     {
 313         if(m_total_vertices)
 314         {
 315             if(is_vertex(command(m_total_vertices - 1)))
 316             {
 317                 add_vertex(0.0, 0.0, path_cmd_end_poly | flags);
 318             }
 319         }
 320     }
 321
 322
 323     //------------------------------------------------------------------------
 324     unsigned path_storage::start_new_path()
 325     {
 326         if(m_total_vertices)
 327         {
 328             if(!is_stop(command(m_total_vertices - 1)))
 329             {
 330                 add_vertex(0.0, 0.0, path_cmd_stop);
 331             }
 332         }
 333         return m_total_vertices;
 334     }
 335
 336
 337     //------------------------------------------------------------------------
 338     void path_storage::add_poly(const double* vertices, unsigned num,
 339                                 bool solid_path, unsigned end_flags)
 340     {
 341         if(num)
 342         {
 343             if(!solid_path)
 344             {
 345                 move_to(vertices[0], vertices[1]);
 346                 vertices += 2;
 347                 --num;
 348             }
 349             while(num--)
 350             {
 351                 line_to(vertices[0], vertices[1]);
 352                 vertices += 2;
 353             }
 354             if(end_flags) end_poly(end_flags);
 355         }
 356     }
 357
 358
 359     //------------------------------------------------------------------------
 360     unsigned path_storage::perceive_polygon_orientation(unsigned idx,
 361                                                         double xs, double ys,
 362                                                         unsigned* orientation)
 363     {
 364         unsigned i;
 365         double sum = 0.0;
 366         double x, y, xn, yn;
 367
 368         x = xs;
 369         y = ys;
 370         for(i = idx; i < m_total_vertices; ++i)
 371         {
 372             if(is_next_poly(vertex(i, &xn, &yn))) break;
 373             sum += x * yn - y * xn;
 374             x = xn;
 375             y = yn;
 376         }
 377         if(i > idx) sum += x * ys - y * xs;
 378         *orientation = path_flags_none;
 379         if(sum != 0.0)
 380         {
 381             *orientation = (sum < 0.0) ? path_flags_cw : path_flags_ccw;
 382         }
 383         return i;
 384     }
 385
 386
 387     //------------------------------------------------------------------------
 388     void path_storage::reverse_polygon(unsigned _start, unsigned _end)
 389     {
 390         unsigned i;
 391         unsigned tmp_cmd = command(_start);
 392
 393         // Shift all commands to one position
 394         for(i = _start; i < _end; i++)
 395         {
 396             modify_command(i, command(i + 1));
 397         }
 398
 399         // Assign starting command to the ending command
 400         modify_command(_end, tmp_cmd);
 401
 402         // Reverse the polygon
 403         while(_end > _start)
 404         {
 405             unsigned start_nb = _start >> block_shift;
 406             unsigned end_nb   = _end   >> block_shift;
 407             double* start_ptr = m_coord_blocks[start_nb] + ((_start & block_mask) << 1);
 408             double* end_ptr   = m_coord_blocks[end_nb]   + ((_end   & block_mask) << 1);
 409             double tmp_xy;
 410
 411             tmp_xy       = *start_ptr;
 412             *start_ptr++ = *end_ptr;
 413             *end_ptr++   = tmp_xy;
 414
 415             tmp_xy       = *start_ptr;
 416             *start_ptr   = *end_ptr;
 417             *end_ptr     = tmp_xy;
 418
 419             tmp_cmd = m_cmd_blocks[start_nb][_start & block_mask];
 420             m_cmd_blocks[start_nb][_start & block_mask] = m_cmd_blocks[end_nb][_end & block_mask];
 421             m_cmd_blocks[end_nb][_end & block_mask] = (unsigned char)tmp_cmd;
 422
 423             ++_start;
 424             --_end;
 425         }
 426     }
 427
 428
 429     //------------------------------------------------------------------------
 430     unsigned path_storage::arrange_orientations(unsigned path_id,
 431                                                 path_flags_e new_orientation)
 432     {
 433         unsigned _end = m_total_vertices;
 434         if(m_total_vertices && new_orientation != path_flags_none)
 435         {
 436             unsigned start = path_id;
 437
 438             double xs, ys;
 439             unsigned cmd = vertex(start, &xs, &ys);
 440             unsigned inc = 0;
 441             for(;;)
 442             {
 443                 unsigned orientation;
 444                 _end = perceive_polygon_orientation(start + 1, xs, ys,
 445                                                    &orientation);
 446                 if(_end > start + 2 &&
 447                    orientation &&
 448                    orientation != unsigned(new_orientation))
 449                 {
 450                     reverse_polygon(start + inc, _end - 1);
 451                 }
 452                 if(_end >= m_total_vertices) break;
 453                 cmd = command(_end);
 454                 if(is_stop(cmd))
 455                 {
 456                     ++_end;
 457                     break;
 458                 }
 459                 if(is_end_poly(cmd))
 460                 {
 461                     inc = 1;
 462                     modify_command(_end, set_orientation(cmd, new_orientation));
 463                 }
 464                 else
 465                 {
 466                     cmd = vertex(++_end, &xs, &ys);
 467                     inc = 0;
 468                 }
 469                 start = _end;
 470             }
 471         }
 472         return _end;
 473     }
 474
 475
 476
 477     //------------------------------------------------------------------------
 478     void path_storage::arrange_orientations_all_paths(path_flags_e new_orientation)
 479     {
 480         if(new_orientation != path_flags_none)
 481         {
 482             unsigned start = 0;
 483             while(start < m_total_vertices)
 484             {
 485                 start = arrange_orientations(start, new_orientation);
 486             }
 487         }
 488     }
 489
 490
 491
 492     //------------------------------------------------------------------------
 493     void path_storage::flip_x(double x1, double x2)
 494     {
 495         unsigned i;
 496         double x, y;
 497         for(i = 0; i < m_total_vertices; i++)
 498         {
 499             unsigned cmd = vertex(i, &x, &y);
 500             if(is_vertex(cmd))
 501             {
 502                 modify_vertex(i, x2 - x + x1, y);
 503             }
 504         }
 505     }
 506
 507
 508     //------------------------------------------------------------------------
 509     void path_storage::flip_y(double y1, double y2)
 510     {
 511         unsigned i;
 512         double x, y;
 513         for(i = 0; i < m_total_vertices; i++)
 514         {
 515             unsigned cmd = vertex(i, &x, &y);
 516             if(is_vertex(cmd))
 517             {
 518                 modify_vertex(i, x, y2 - y + y1);
 519             }
 520         }
 521     }
 522
 523
 524 }
 525