synfig-core/trunk/src/synfig/layer_shape.cpp

   1 /* === S Y N F I G ========================================================= */
   2 /*!     \file layer_shape.cpp
   3 **      \brief Implementation of the "Shape" layer
   4 **
   5 **      $Id$
   6 **
   7 **      \legal
   8 **      Copyright (c) 2002-2005 Robert B. Quattlebaum Jr., Adrian Bentley
   9 **      Copyright (c) 2007 Chris Moore
  10 **
  11 **      This package is free software; you can redistribute it and/or
  12 **      modify it under the terms of the GNU General Public License as
  13 **      published by the Free Software Foundation; either version 2 of
  14 **      the License, or (at your option) any later version.
  15 **
  16 **      This package is distributed in the hope that it will be useful,
  17 **      but WITHOUT ANY WARRANTY; without even the implied warranty of
  18 **      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  19 **      General Public License for more details.
  20 **      \endlegal
  21 */
  22 /* ========================================================================= */
  23
  24 /* === H E A D E R S ======================================================= */
  25
  26 #ifdef USING_PCH
  27 #       include "pch.h"
  28 #else
  29 #ifdef HAVE_CONFIG_H
  30 #       include <config.h>
  31 #endif
  32
  33 #include "layer_shape.h"
  34 #include "string.h"
  35 #include "time.h"
  36 #include "context.h"
  37 #include "paramdesc.h"
  38 #include "renddesc.h"
  39 #include "surface.h"
  40 #include "value.h"
  41 #include "valuenode.h"
  42 #include "float.h"
  43 #include "blur.h"
  44
  45 #include "curve_helper.h"
  46
  47 #include <vector>
  48
  49 #include <deque>
  50
  51 #endif
  52
  53 /* === U S I N G =========================================================== */
  54
  55 using namespace synfig;
  56 using namespace std;
  57 using namespace etl;
  58
  59 /* === G L O B A L S ======================================================= */
  60
  61 SYNFIG_LAYER_INIT(Layer_Shape);
  62 SYNFIG_LAYER_SET_NAME(Layer_Shape,"shape");
  63 SYNFIG_LAYER_SET_LOCAL_NAME(Layer_Shape,N_("Shape"));
  64 SYNFIG_LAYER_SET_CATEGORY(Layer_Shape,N_("Internal"));
  65 SYNFIG_LAYER_SET_VERSION(Layer_Shape,"0.1");
  66 SYNFIG_LAYER_SET_CVS_ID(Layer_Shape,"$Id$");
  67
  68 #define EPSILON 1e-12
  69
  70 template < class T >
  71 inline bool IsZero(const T &n)
  72 {
  73         return (n < EPSILON) && (n > -EPSILON);
  74 }
  75
  76 /* === C L A S S E S ======================================================= */
  77
  78 //Assumes 64 byte aligned structures if at all
  79 struct Primitive
  80 {
  81         int             operation;
  82         int             number;
  83
  84         //Point data[0];
  85
  86         enum Operations
  87         {
  88                 NONE = -1,
  89                 MOVE_TO = 0,            //(x,y)+                                after first point treated as line_to
  90                 CLOSE,                          //                                              NOT RUNLENGTH enabled
  91                 LINE_TO,                        //(x,y)+                                continuous func
  92                 CONIC_TO,                       //(x1,y1,x,y)+                  "   "
  93                 CONIC_TO_SMOOTH,        //(x,y)+                                "   "
  94                 CUBIC_TO,                       //(x1,y1,x2,y2,x,y)+    "   "
  95                 CUBIC_TO_SMOOTH,        //(x2,y2,x,y)+                  "   "
  96                 END
  97         };
  98 };
  99
 100 //******** CURVE FUNCTIONS *****************
 101 const int       MAX_SUBDIVISION_SIZE = 64;
 102 const int       MIN_SUBDIVISION_DRAW_LEVELS = 4;
 103
 104 static void Subd_Conic_Stack(Point *arc)
 105 {
 106         /*
 107
 108         b0
 109         *               0+1 a
 110         b1 b    *               1+2*1+2 a
 111         *               1+2     b       *
 112         b2              *
 113         *
 114
 115         0.1.2 ->        0.1 2 3.4
 116
 117         */
 118
 119         Real a,b;
 120
 121
 122         arc[4][0] = arc[2][0];
 123         b = arc[1][0];
 124
 125         a = arc[1][0] = (arc[0][0] + b)/2;
 126         b = arc[3][0] = (arc[4][0] + b)/2;
 127         arc[2][0] = (a + b)/2;
 128
 129
 130         arc[4][1] = arc[2][1];
 131         b = arc[1][1];
 132
 133         a = arc[1][1] = (arc[0][1] + b)/2;
 134         b = arc[3][1] = (arc[4][1] + b)/2;
 135         arc[2][1] = (a + b)/2;
 136
 137         /* //USING SIMD
 138
 139         arc[4] = arc[2];
 140
 141         arc[3] = (arc[2] + arc[1])/2;
 142         arc[1] = (arc[0] + arc[1])/2;
 143
 144         arc[2] = (arc[1] + arc[3])/2;
 145
 146         */
 147
 148 }
 149
 150 static void Subd_Cubic_Stack(Point *arc)
 151 {
 152         Real a,b,c;
 153
 154         /*
 155
 156         b0
 157         *               0+1 a
 158         b1 b    *               1+2*1+2 a
 159         *               1+2     b       *                       0+3*1+3*2+3
 160         b2 c    *               1+2*2+2 b       *
 161         *               2+3     c       *
 162         b3              *
 163         *
 164
 165         0.1 2.3 ->      0.1 2 3 4 5.6
 166
 167         */
 168
 169         arc[6][0] = arc[3][0];
 170
 171         b = arc[1][0];
 172         c = arc[2][0];
 173
 174         a = arc[1][0] = (arc[0][0] + b)/2;
 175         b = (b + c)/2;
 176         c = arc[5][0] = (arc[6][0] + c)/2;
 177
 178         a = arc[2][0] = (a + b)/2;
 179         b = arc[4][0] = (b + c)/2;
 180
 181         arc[3][0] = (a + b)/2;
 182
 183
 184         arc[6][1] = arc[3][1];
 185
 186         b = arc[1][1];
 187         c = arc[2][1];
 188
 189         a = arc[1][1] = (arc[0][1] + b)/2;
 190         b = (b + c)/2;
 191         c = arc[5][1] = (arc[6][1] + c)/2;
 192
 193         a = arc[2][1] = (a + b)/2;
 194         b = arc[4][1] = (b + c)/2;
 195
 196         arc[3][1] = (a + b)/2;
 197
 198         /* //USING SIMD
 199         temp
 200
 201         arc[6] = arc[3];
 202
 203         //backwards to avoid overwriting
 204         arc[5] = (arc[2] + arc[3])/2;
 205         temp = (arc[1] + arc[2])/2;
 206         arc[1] = (arc[0] + arc[1])/2;
 207
 208         arc[4] = (temp + arc[5])/2;
 209         arc[2] = (arc[1] + temp)/2;
 210
 211         arc[3] = (arc[2] + arc[4])/2;
 212
 213         */
 214 }
 215
 216 //************** PARAMETRIC RENDERER SUPPORT STRUCTURES ****************
 217
 218 // super segment
 219 struct MonoSegment
 220 {
 221         Rect    aabb;
 222         int             ydir;
 223         vector<Point>   pointlist;
 224
 225         MonoSegment(int dir = 0, Real x0 = 0, Real x1 = 0, Real y0 = 0, Real y1 = 0)
 226         {
 227                 aabb.minx = x0;
 228                 aabb.maxx = x1;
 229                 aabb.miny = y0;
 230                 aabb.maxy = y1;
 231
 232                 ydir = dir;
 233         }
 234
 235         int intersect(Real x,Real y) const
 236         {
 237                 if((y < aabb.miny+EPSILON) || (y > aabb.maxy) || (x < aabb.minx)) return 0;
 238                 if(x > aabb.maxx) return ydir;
 239
 240                 //int i = 0;
 241                 //int size = pointlist.size();
 242                 //vector<Point>::const_iterator end = pointlist.end();
 243                 vector<Point>::const_iterator p = pointlist.begin();
 244
 245                 //assumes that the rect culled away anything that would be beyond the edges
 246                 if(ydir > 0)
 247                 {
 248                         while(y > (*++p)[1]);
 249                 }
 250                 else
 251                 {
 252                         while(y < (*++p)[1]);
 253                 }
 254
 255                 //for the loop to break there must have been a slope (straight line would do nothing)
 256                 //vector<Point>::const_iterator p1 = p-1;
 257                 Real dy = p[-1][1] - p[0][1];
 258                 Real dx = p[-1][0] - p[0][0];
 259
 260                 assert(dy != 0);
 261
 262                 Real xi = p[0][0] + (y - p[0][1]) * dx / dy;
 263                 return (x > xi)*ydir;
 264         }
 265 };
 266
 267 struct CurveArray
 268 {
 269         Rect    aabb;   //not necessarily as effective - can only reject values
 270         vector<Point>   pointlist;      //run length - p0, p1, p2, p3 = p10, p11, p12, p13 = p20 ...
 271         vector<char>    degrees;
 272
 273         CurveArray(Real x0 = 0, Real x1 = 0, Real y0 = 0, Real y1 = 0)
 274         {
 275                 aabb.set(x0,y0,x1,y1);
 276         }
 277
 278         void reset(Real x0 = 0, Real x1 = 0, Real y0 = 0, Real y1 = 0)
 279         {
 280                 aabb.set(x0,y0,x1,y1);
 281                 pointlist.clear();
 282                 degrees.clear();
 283         }
 284
 285         int size () const
 286         {
 287                 return degrees.size();
 288         }
 289
 290         void Start(Point m)
 291         {
 292                 reset(m[0],m[0],m[1],m[1]);
 293                 pointlist.push_back(m);
 294         }
 295
 296         void AddCubic(Point p1, Point p2, Point dest)
 297         {
 298                 aabb.expand(p1[0],p1[1]);
 299                 aabb.expand(p2[0],p2[1]);
 300                 aabb.expand(dest[0],dest[1]);
 301
 302                 pointlist.push_back(p1);
 303                 pointlist.push_back(p2);
 304                 pointlist.push_back(dest);
 305
 306                 degrees.push_back(3);
 307         }
 308
 309         void AddConic(Point p1, Point dest)
 310         {
 311                 aabb.expand(p1[0],p1[1]);
 312                 aabb.expand(dest[0],dest[1]);
 313
 314                 pointlist.push_back(p1);
 315                 pointlist.push_back(dest);
 316
 317                 degrees.push_back(2);
 318         }
 319
 320         static int intersect_conic(Real x, Real y, Point *p, int /*level*/ = 0)
 321         {
 322                 Real ymin,ymax,xmin,xmax;
 323                 int intersects = 0;
 324
 325                 //sort the overall curve ys - degenerate detection
 326                 ymin = min(p[0][1],p[2][1]);
 327                 ymax = max(p[0][1],p[2][1]);
 328
 329                 xmin = min(min(p[0][0],p[1][0]),p[2][0]);
 330                 xmax = max(max(p[0][0],p[1][0]),p[2][0]);
 331
 332                 //to the left, to the right and out of range y, or completely out of range y
 333                 if( x < xmin ) return 0;
 334                 if( x > xmax  && (y > ymax || y < ymin) ) return 0;
 335                 if( (y > ymax && y > p[1][1]) || (y < ymin && y < p[1][1]) ) return 0;
 336
 337                 //degenerate line max
 338                 if(ymin == ymax == p[1][1])
 339                         return 0;
 340
 341                 //degenerate accept - to the right and crossing the base line
 342                 if(x > xmax)
 343                 {
 344                         return (y <= ymax && y >= ymin);
 345                 }
 346
 347                 //solve for curve = y
 348
 349                 //real roots:
 350                 //0 roots       - 0 intersection
 351                 //1 root        - get x, and figure out x
 352                 //2 roots (non-double root)     - get 2 xs, and count xs to the left
 353
 354                 //for conic we can assume 1 intersection for monotonic curve
 355                 Real    a = p[2][1] -   2*p[1][1] +     p[0][1],
 356                                 b =                     2*p[1][1] -     2*p[0][1],
 357                                 c =                                                     p[0][1]         -       y;
 358
 359                 Real t1 = -1, t2 = -1;
 360
 361                 if(a == 0)
 362                 {
 363                         //linear - easier :)
 364                         if(b == 0) return 0; //may not need this check
 365
 366                         t1 = - c / b; //bt + c = 0 solved
 367                 }else
 368                 {
 369                         //2 degree polynomial
 370                         Real b2_4ac = b*b - 4*a*c;
 371
 372                         //if there are double/no roots - no intersections (in real #s that is)
 373                         if(b2_4ac <= 0)
 374                         {
 375                                 return 0;
 376                         }
 377
 378                         b2_4ac = sqrt(b2_4ac);
 379
 380                         t1 = (-b - b2_4ac) / 2*a,
 381                         t2 = (-b + b2_4ac) / 2*a;
 382                 }
 383
 384                 //calculate number of intersections
 385                 if(t1 >= 0 && t1 <= 1)
 386                 {
 387                         const Real t = t1;
 388                         const Real invt = 1 - t;
 389
 390                         //find x val and it counts if it's to the left of the point
 391                         const Real xi = invt*invt*p[0][0] + 2*t*invt*p[1][0] + t*t*p[2][0];
 392                         const Real dy_t = 2*a*t + b;
 393
 394                         if(dy_t)
 395                         {
 396                                 intersects += (x >= xi) * ( dy_t > 0 ? 1 : -1);
 397                         }
 398                 }
 399
 400                 if(t2 >= 0 && t2 <= 1)
 401                 {
 402                         const Real t = t2;
 403                         const Real invt = 1 - t;
 404
 405                         //find x val and it counts if it's to the left of the point
 406                         const Real xi = invt*invt*p[0][0] + 2*t*invt*p[1][0] + t*t*p[2][0];
 407                         const Real dy_t = 2*a*t + b;
 408
 409                         if(dy_t)
 410                         {
 411                                 intersects += (x >= xi) * ( dy_t > 0 ? 1 : -1);
 412                         }
 413                 }
 414
 415                 return intersects;
 416         }
 417
 418         static int      quadratic_eqn(Real a, Real b, Real c, Real *t0, Real *t1)
 419         {
 420                 const Real b2_4ac = b*b - 4*a*c;
 421
 422                 //degenerate reject (can't take sqrt)
 423                 if(b2_4ac < 0)
 424                 {
 425                         return 0;
 426                 }
 427
 428                 const Real sqrtb2_4ac = sqrt(b2_4ac);
 429                 const Real signb = b < 0 ? -1 : 1;
 430                 const Real q = - 0.5 * (b + signb * sqrtb2_4ac);
 431
 432                 *t0 = q/a;
 433                 *t1 = c/q;
 434
 435                 return sqrtb2_4ac == 0 ? 1 : 2;
 436         }
 437
 438         //Newton-Raphson root polishing (we don't care about bounds, assumes very near the desired root)
 439         static Real polish_cubicroot(Real a, Real b, Real c, Real d, Real t, Real *dpdt)
 440         {
 441                 const Real cn[4] = {a,b,c,d};
 442                 Real p,dp,newt,oldpmag=FLT_MAX;
 443
 444                 //eval cubic eqn and its derivative
 445                 for(;;)
 446                 {
 447                         p = cn[0]*t + cn[1];
 448                         dp = cn[0];
 449
 450                         for(int i = 2; i < 4; i++)
 451                         {
 452                                 dp = p + dp*t;
 453                                 p = cn[i] + p*t;
 454                         }
 455
 456                         if(dp == 0)
 457                         {
 458                                 synfig::warning("polish_cubicroot: Derivative should not vanish!!!");
 459                                 return t;
 460                         }
 461
 462                         newt = t - p/dp;
 463
 464                         if(newt == t || fabs(p) >= oldpmag)
 465                         {
 466                                 *dpdt = dp;
 467                                 return t;
 468                         }
 469
 470                         t = newt;
 471                         oldpmag = fabs(p);
 472                 }
 473         }
 474
 475         static int intersect_cubic(Real x, Real y, Point *p, int /*level*/ = 0)
 476         {
 477                 const Real INVALIDROOT = -FLT_MAX;
 478                 Real ymin,ymax,xmin,xmax;
 479                 Real ymin2,ymax2,ymintot,ymaxtot;
 480                 int intersects = 0;
 481
 482                 //sort the overall curve ys and xs - degenerate detection
 483
 484                 //open span for the two end points
 485                 ymin = min(p[0][1],p[3][1]);
 486                 ymax = max(p[0][1],p[3][1]);
 487
 488                 //other points etc.
 489                 ymin2 = min(p[1][1],p[2][1]);
 490                 ymax2 = max(p[1][1],p[2][1]);
 491
 492                 ymintot = min(ymin,ymin2);
 493                 ymaxtot = max(ymax,ymax2);
 494
 495                 //the entire curve control polygon is in this x range
 496                 xmin = min(min(p[0][0],p[1][0]),min(p[2][0],p[3][0]));
 497                 xmax = max(max(p[0][0],p[1][0]),max(p[2][0],p[3][0]));
 498
 499                 //outside all y boundaries (no intersect)
 500                 if( (y > ymaxtot) || (y < ymintot) ) return 0;
 501
 502                 //left of curve (no intersect)
 503                 if(x < xmin) return 0;
 504
 505                 //right of curve (and outside base range)
 506                 if( x > xmax )
 507                 {
 508                         if( (y > ymax) || (y < ymin) ) return 0;
 509
 510                         //degenerate accept - to the right and inside the [ymin,ymax] range (already rejected if out of range)
 511                         const Real n = p[3][1] - p[0][1];
 512
 513                         //extract the sign from the value (we need valid data)
 514                         return n < 0 ? -1 : 1;
 515                 }
 516
 517                 //degenerate horizontal line max -- doesn't happen enough to check for
 518                 if( ymintot == ymaxtot ) return 0;
 519
 520                 //calculate roots:
 521                 // can have 0,1,2, or 3 real roots
 522                 // if any of them are double then reject the two...
 523
 524                 // y-coefficients for f_y(t) - y = 0
 525                 Real    a = p[3][1]     - 3*p[2][1]     + 3*p[1][1]     -   p[0][1],
 526                                 b =                       3*p[2][1]     - 6*p[1][1]     + 3*p[0][1],
 527                                 c =                                                       3*p[1][1]     - 3*p[0][1],
 528                                 d =                                                                             p[0][1] - y;
 529
 530                 Real    ax = p[3][0]    - 3*p[2][0]     + 3*p[1][0]     -   p[0][0],
 531                                 bx =                      3*p[2][0]     - 6*p[1][0]     + 3*p[0][0],
 532                                 cx =                                              3*p[1][0]     - 3*p[0][0],
 533                                 dx =                                                                            p[0][0];
 534
 535                 Real t1 = INVALIDROOT, t2 = INVALIDROOT, t3 = INVALIDROOT, t, dydt;
 536
 537                 if(a == 0)
 538                 {
 539                         //only 2nd degree
 540                         if(b == 0)
 541                         {
 542                                 //linear
 543                                 if(c == 0) return 0;
 544
 545                                 t1 = - d / c; //equation devolved into: ct + d = 0 - solve...
 546                         }else
 547                         {
 548                                 //0 roots = 0 intersections, 1 root = 2 intersections at the same place (0 effective)
 549                                 if(quadratic_eqn(a,b,c,&t1,&t2) != 2) return 0;
 550                         }
 551                 }else
 552                 {
 553                         //cubic - sigh....
 554
 555                         //algorithm courtesy of Numerical Recipes in C (algorithm copied from pg. 184/185)
 556                         Real an = b / a,
 557                                  bn = c / a,
 558                                  cn = d / a;
 559
 560                         //if cn is 0 (or really really close), then we can simplify this...
 561                         if(IsZero(cn))
 562                         {
 563                                 t3 = 0;
 564
 565                                 //0 roots = 0 intersections, 1 root = 2 intersections at the same place (0 effective)
 566                                 if(quadratic_eqn(a,b,c,&t1,&t2) != 2)
 567                                 {
 568                                         t1 = t2 = INVALIDROOT;
 569                                 }
 570                         }
 571                         else
 572                         {
 573                                 //otherwise run the normal cubic root equation
 574                                 Real Q = (an*an - 3.0*bn) / 9.0;
 575                                 Real R = ((2.0*an*an - 9.0*bn)*an + 27.0*cn)/54.0;
 576
 577                                 if(R*R < Q*Q*Q)
 578                                 {
 579                                         Real theta = acos(R / sqrt(Q*Q*Q));
 580
 581                                         t1 = -2.0*sqrt(Q)*cos(theta/3) - an/3.0;
 582                                         t2 = -2.0*sqrt(Q)*cos((theta+2*PI)/3.0) - an/3.0;
 583                                         t3 = -2.0*sqrt(Q)*cos((theta-2*PI)/3.0) - an/3.0;
 584
 585                                         //don't need to reorder,l just need to eliminate double/triple roots
 586                                         //if(t3 == t2 && t1 == t2) t2 = t3 = INVALIDROOT;
 587                                         if(t3 == t2) t2 = t3 = INVALIDROOT;
 588                                         if(t1 == t2) t1 = t2 = INVALIDROOT;
 589                                         if(t1 == t3) t1 = t3 = INVALIDROOT;
 590                                 }else
 591                                 {
 592                                         Real signR = R < 0 ? -1 : 1;
 593                                         Real A = - signR * pow(signR*R + sqrt(R*R - Q*Q*Q),1/3.0);
 594
 595                                         Real B;
 596                                         if(A == 0) B = 0;
 597                                         else B = Q / A;
 598
 599                                         //single real root in this case
 600                                         t1 = (A + B) - an/3.0;
 601                                 }
 602                         }
 603                 }
 604
 605                 //if(t1 != INVALIDROOT)
 606                 {
 607                         t = t1;//polish_cubicroot(a,b,c,d,t1,&dydt);
 608                         if(t >= 0 && t < 1)
 609                         {
 610                                 //const Real invt = 1 - t;
 611
 612                                 //find x val and it counts if it's to the left of the point
 613                                 const Real xi = ((ax*t + bx)*t + cx)*t + dx;
 614                                 dydt = (3*a*t + 2*b)*t + c;
 615
 616                                 if(dydt)
 617                                 {
 618                                         intersects += (x >= xi) * ( dydt > 0 ? 1 : -1);
 619                                 }
 620                         }
 621                 }
 622
 623                 //if(t2 != INVALIDROOT)
 624                 {
 625                         t = t2;//polish_cubicroot(a,b,c,d,t2,&dydt);
 626                         if(t >= 0 && t < 1)
 627                         {
 628                                 //const Real invt = 1 - t;
 629
 630                                 //find x val and it counts if it's to the left of the point
 631                                 const Real xi = ((ax*t + bx)*t + cx)*t + dx;
 632                                 dydt = (3*a*t + 2*b)*t + c;
 633
 634                                 if(dydt)
 635                                 {
 636                                         intersects += (x >= xi) * ( dydt > 0 ? 1 : -1);
 637                                 }
 638                         }
 639                 }
 640
 641                 //if(t3 != INVALIDROOT)
 642                 {
 643                         t = t3;//polish_cubicroot(a,b,c,d,t3,&dydt);
 644                         if(t >= 0 && t < 1)
 645                         {
 646                                 //const Real invt = 1 - t;
 647
 648                                 //find x val and it counts if it's to the left of the point
 649                                 const Real xi = ((ax*t + bx)*t + cx)*t + dx;
 650                                 dydt = (3*a*t + 2*b)*t + c;
 651
 652                                 if(dydt)
 653                                 {
 654                                         intersects += (x >= xi) * ( dydt > 0 ? 1 : -1);
 655                                 }
 656                         }
 657                 }
 658
 659                 return intersects;
 660         }
 661
 662         int intersect(Real x,Real y, Point *table) const
 663         {
 664                 if((y < aabb.miny) || (y > aabb.maxy) || (x < aabb.minx)) return 0;
 665
 666                 int i, curdeg, intersects = 0;
 667                 const int numcurves = degrees.size();
 668
 669                 vector<Point>::const_iterator   p = pointlist.begin();
 670
 671                 for(i=0; i < numcurves; i++)
 672                 {
 673                         curdeg = degrees[i];
 674
 675                         switch(curdeg)
 676                         {
 677                                 case 2:
 678                                 {
 679                                         table[0] = *p++;
 680                                         table[1] = *p++;
 681                                         table[2] = *p;  //we want to include the last point for the next curve
 682
 683                                         intersects += intersect_conic(x,y,table);
 684
 685                                         break;
 686                                 }
 687
 688                                 case 3:
 689                                 {
 690                                         table[0] = *p++;
 691                                         table[1] = *p++;
 692                                         table[2] = *p++;
 693                                         table[3] = *p;  //we want to include the last point for the next curve
 694
 695                                         intersects += intersect_cubic(x,y,table);
 696
 697                                         break;
 698                                 }
 699
 700                                 default:
 701                                 {
 702                                         warning("Invalid degree (%d) inserted into the list (index: %d)\n", curdeg, i);
 703                                         return 0;
 704                                 }
 705                         }
 706                 }
 707
 708                 return intersects;
 709         }
 710 };
 711
 712 struct Layer_Shape::Intersector
 713 {
 714         Rect    aabb;
 715
 716         //! true iff aabb hasn't been initialized yet
 717         bool    initaabb;
 718
 719         int     flags;
 720
 721         enum IntersectorFlags
 722         {
 723                 NotClosed = 0x8000
 724         };
 725
 726         enum PrimitiveType
 727         {
 728                 TYPE_NONE = 0,
 729                 TYPE_LINE,
 730                 TYPE_CURVE
 731         };
 732
 733         Real    cur_x,cur_y;
 734         Real    close_x,close_y;
 735
 736         vector<MonoSegment>                             segs;   //monotonically increasing
 737         vector<CurveArray>                              curves; //big array of consecutive curves
 738
 739         int                                                             prim;
 740         Vector                                                  tangent;
 741
 742         Intersector()
 743         {
 744                 clear();
 745         }
 746
 747         bool notclosed()
 748         {
 749                 return (flags & NotClosed) || (cur_x != close_x) || (cur_y != close_y);
 750         }
 751
 752         void move_to(Real x, Real y)
 753         {
 754                 close();
 755
 756                 close_x = cur_x = x;
 757                 close_y = cur_y = y;
 758
 759                 tangent[0] = tangent[1] = 0;
 760
 761                 if(initaabb)
 762                 {
 763                         aabb.set_point(x,y);
 764                         initaabb = false;
 765                 }else aabb.expand(x,y);
 766
 767                 prim = TYPE_NONE;
 768         }
 769
 770         void line_to(Real x, Real y)
 771         {
 772                 int dir = (y > cur_y)*1 + (-1)*(y < cur_y);
 773
 774                 //check for context (if not line start a new segment)
 775                 //if we're not in line mode (covers 0 set case), or if directions are different (not valid for 0 direction)
 776                 if(prim != TYPE_LINE || (dir && segs.back().ydir != dir))
 777                 {
 778                         MonoSegment             seg(dir,x,x,y,y);
 779
 780                         seg.aabb.expand(cur_x,cur_y);
 781                         seg.pointlist.push_back(Point(cur_x,cur_y));
 782                         seg.pointlist.push_back(Point(x,y));
 783                         segs.push_back(seg);
 784                 }
 785                 //add to the last segment, because it works
 786                 else
 787                 {
 788                         segs.back().pointlist.push_back(Point(x,y));
 789                         segs.back().aabb.expand(x,y);
 790                 }
 791
 792
 793
 794                 cur_x = x;
 795                 cur_y = y;
 796                 aabb.expand(x,y); //expand the entire thing's bounding box
 797
 798                 tangent[0] = x - cur_x;
 799                 tangent[1] = x - cur_y;
 800
 801                 flags |= NotClosed;
 802                 prim = TYPE_LINE;
 803         }
 804
 805         void conic_to_smooth(Real x, Real y)
 806         {
 807                 const Real x1 = tangent[0]/2.0 + cur_x;
 808                 const Real y1 = tangent[1]/2.0 + cur_y;
 809
 810                 conic_to(x1,y1,x,y);
 811         }
 812
 813         void conic_to(Real x1, Real y1, Real x, Real y)
 814         {
 815                 //if we're not already a curve start one
 816                 if(prim != TYPE_CURVE)
 817                 {
 818                         CurveArray      c;
 819
 820                         c.Start(Point(cur_x,cur_y));
 821                         c.AddConic(Point(x1,y1),Point(x,y));
 822
 823                         curves.push_back(c);
 824                 }else
 825                 {
 826                         curves.back().AddConic(Point(x1,y1),Point(x,y));
 827                 }
 828
 829                 cur_x = x;
 830                 cur_y = y;
 831
 832                 aabb.expand(x1,y1);
 833                 aabb.expand(x,y);
 834
 835                 tangent[0] = 2*(x - x1);
 836                 tangent[1] = 2*(y - y1);
 837
 838                 flags |= NotClosed;
 839                 prim = TYPE_CURVE;
 840         }
 841
 842         void curve_to_smooth(Real x2, Real y2, Real x, Real y)
 843         {
 844                 Real x1 = tangent[0]/3.0 + cur_x;
 845                 Real y1 = tangent[1]/3.0 + cur_y;
 846
 847                 curve_to(x1,y1,x2,y2,x,y);
 848         }
 849
 850         void curve_to(Real x1, Real y1, Real x2, Real y2, Real x, Real y)
 851         {
 852                 //if we're not already a curve start one
 853                 if(prim != TYPE_CURVE)
 854                 {
 855                         CurveArray      c;
 856
 857                         c.Start(Point(cur_x,cur_y));
 858                         c.AddCubic(Point(x1,y1),Point(x2,y2),Point(x,y));
 859
 860                         curves.push_back(c);
 861                 }else
 862                 {
 863                         curves.back().AddCubic(Point(x1,y1),Point(x2,y2),Point(x,y));
 864                 }
 865
 866                 cur_x = x;
 867                 cur_y = y;
 868
 869                 //expand bounding box around ALL of it
 870                 aabb.expand(x1,y1);
 871                 aabb.expand(x2,y2);
 872                 aabb.expand(x,y);
 873
 874                 tangent[0] = 3*(x - x2);
 875                 tangent[1] = 3*(y - y2);
 876
 877                 flags |= NotClosed;
 878                 prim = TYPE_CURVE;
 879         }
 880
 881         void close()
 882         {
 883                 if(flags & NotClosed)
 884                 {
 885                         if(cur_x != close_x || cur_y != close_y)
 886                         {
 887                                 line_to(close_x,close_y);
 888                         }
 889
 890                         flags &= ~NotClosed;
 891                 }
 892         }
 893
 894         //assumes the line to count the intersections with is (-1,0)
 895         int     intersect (Real x, Real y) const
 896         {
 897                 int inter = 0;
 898                 unsigned int i;
 899                 vector<MonoSegment>::const_iterator s = segs.begin();
 900                 vector<CurveArray>::const_iterator c = curves.begin();
 901
 902                 Point   memory[3*MAX_SUBDIVISION_SIZE + 1];
 903
 904                 for(i = 0; i < segs.size(); i++,s++)
 905                 {
 906                         inter += s->intersect(x,y);
 907                 }
 908
 909                 for(i=0; i < curves.size(); i++,c++)
 910                         inter += c->intersect(x,y,memory);
 911
 912                 return inter;
 913         }
 914
 915         //intersect an arbitrary line
 916         //int   intersect (Real x, Real y, Real vx, Real vy) {return 0;}
 917
 918         void clear()
 919         {
 920                 segs.clear();
 921                 curves.clear();
 922
 923                 flags = 0;
 924                 cur_x = cur_y = close_x = close_y = 0;
 925                 prim = TYPE_NONE;
 926                 tangent[0] = tangent[1] = 0;
 927                 initaabb = true;
 928         }
 929 };
 930
 931 //*********** SCANLINE RENDERER SUPPORT STRUCTURES ***************
 932 struct PenMark
 933 {
 934         int y,x;
 935         Real cover,area;
 936
 937         PenMark(){}
 938         PenMark(int xin, int yin, Real c, Real a)
 939                 :y(yin),x(xin),cover(c),area(a) {}
 940
 941         void set(int xin, int yin, Real c, Real a)      { y = yin; x = xin; cover = c; area = a;        }
 942
 943         void setcoord(int xin, int yin)                         { y = yin; x = xin;     }
 944
 945         void setcover(Real c, Real a)                           { cover = c; area = a; }
 946         void addcover(Real c, Real a)                           { cover += c; area += a; }
 947
 948         bool operator < (const PenMark &rhs) const
 949         {
 950                 return y == rhs.y ? x < rhs.x : y < rhs.y;
 951         }
 952 };
 953
 954 typedef rect<int> ContextRect;
 955
 956 class Layer_Shape::PolySpan
 957 {
 958 public:
 959         typedef deque<PenMark>  cover_array;
 960
 961         Point                   arc[3*MAX_SUBDIVISION_SIZE + 1];
 962
 963         cover_array             covers;
 964         PenMark                 current;
 965
 966         int                             open_index;
 967
 968         //ending position of last primitive
 969         Real                    cur_x;
 970         Real                    cur_y;
 971
 972         //starting position of current primitive list
 973         Real                    close_x;
 974         Real                    close_y;
 975
 976         //flags for the current segment
 977         int                             flags;
 978
 979         //the window that will be drawn (used for clipping)
 980         ContextRect             window;
 981
 982         //for assignment to flags value
 983         enum PolySpanFlags
 984         {
 985                 NotSorted = 0x8000,
 986                 NotClosed =     0x4000
 987         };
 988
 989         //default constructor - 0 everything
 990         PolySpan() :current(0,0,0,0),flags(NotSorted)
 991         {
 992                 cur_x = cur_y = close_x = close_y = 0;
 993                 open_index = 0;
 994         }
 995
 996         bool notclosed() const
 997         {
 998                 return (flags & NotClosed) || (cur_x != close_x) || (cur_y != close_y);
 999         }
1000
1001         //0 out all the variables involved in processing
1002         void clear()
1003         {
1004                 covers.clear();
1005                 cur_x = cur_y = close_x = close_y = 0;
1006                 open_index = 0;
1007                 current.set(0,0,0,0);
1008                 flags = NotSorted;
1009         }
1010
1011         //add the current cell, but only if there is information to add
1012         void addcurrent()
1013         {
1014                 if(current.cover || current.area)
1015                 {
1016                         covers.push_back(current);
1017                 }
1018         }
1019
1020         //move to the next cell (cover values 0 initially), keeping the current if necessary
1021         void move_pen(int x, int y)
1022         {
1023                 if(y != current.y || x != current.x)
1024                 {
1025                         addcurrent();
1026                         current.set(x,y,0,0);
1027                 }
1028         }
1029
1030         //close the primitives with a line (or rendering will not work as expected)
1031         void close()
1032         {
1033                 if(flags & NotClosed)
1034                 {
1035                         if(cur_x != close_x || cur_y != close_y)
1036                         {
1037                                 line_to(close_x,close_y);
1038                                 addcurrent();
1039                                 current.setcover(0,0);
1040                         }
1041                         flags &= ~NotClosed;
1042                 }
1043         }
1044
1045         // Not recommended - destroys any separation of spans currently held
1046         void merge_all()
1047         {
1048                 sort(covers.begin(),covers.end());
1049                 open_index = 0;
1050         }
1051
1052         //will sort the marks if they are not sorted
1053         void sort_marks()
1054         {
1055                 if(flags & NotSorted)
1056                 {
1057                         //only sort the open index
1058                         addcurrent();
1059                         current.setcover(0,0);
1060
1061                         sort(covers.begin() + open_index,covers.end());
1062                         flags &= ~NotSorted;
1063                 }
1064         }
1065
1066         //encapsulate the current sublist of marks (used for drawing)
1067         void encapsulate_current()
1068         {
1069                 //sort the current list then reposition the open list section
1070                 sort_marks();
1071                 open_index = covers.size();
1072         }
1073
1074         //move to start a new primitive list (enclose the last primitive if need be)
1075         void move_to(Real x, Real y)
1076         {
1077                 close();
1078                 if(isnan(x))x=0;
1079                 if(isnan(y))y=0;
1080                 move_pen((int)floor(x),(int)floor(y));
1081                 close_y = cur_y = y;
1082                 close_x = cur_x = x;
1083         }
1084
1085         //primitive_to functions
1086         void line_to(Real x, Real y);
1087         void conic_to(Real x1, Real y1, Real x, Real y);
1088         void cubic_to(Real x1, Real y1, Real x2, Real y2, Real x, Real y);
1089
1090         void draw_scanline(int y, Real x1, Real y1, Real x2, Real y2);
1091         void draw_line(Real x1, Real y1, Real x2, Real y2);
1092
1093         Real ExtractAlpha(Real area, WindingStyle winding_style)
1094         {
1095                 if (area < 0)
1096                         area = -area;
1097
1098                 if (winding_style == WINDING_NON_ZERO)
1099                 {
1100                         // non-zero winding style
1101                         if (area > 1)
1102                                 return 1;
1103                 }
1104                 else // if (winding_style == WINDING_EVEN_ODD)
1105                 {
1106                         // even-odd winding style
1107                         while (area > 1)
1108                                 area -= 2;
1109
1110                         // want pyramid like thing
1111                         if (area < 0)
1112                                 area = -area;
1113                 }
1114
1115                 return area;
1116         }
1117 };
1118
1119 /* === M E T H O D S ======================================================= */
1120
1121 Layer_Shape::Layer_Shape(const Real &a, const Color::BlendMethod m):
1122         Layer_Composite (a,m),
1123         edge_table              (new Intersector),
1124         color                   (Color::black()),
1125         offset                  (0,0),
1126         invert                  (false),
1127         antialias               (true),
1128         blurtype                (Blur::FASTGAUSSIAN),
1129         feather                 (0),
1130         winding_style   (WINDING_NON_ZERO),
1131         bytestream              (0),
1132         lastbyteop              (Primitive::NONE),
1133         lastoppos               (-1)
1134 {
1135 }
1136
1137 Layer_Shape::~Layer_Shape()
1138 {
1139         delete edge_table;
1140 }
1141
1142 void
1143 Layer_Shape::clear()
1144 {
1145         edge_table->clear();
1146         bytestream.clear();
1147 }
1148
1149 bool
1150 Layer_Shape::set_param(const String & param, const ValueBase &value)
1151 {
1152         IMPORT_PLUS(color, { if (color.get_a() == 0) if (converted_blend_) {
1153                                         set_blend_method(Color::BLEND_ALPHA_OVER);
1154                                         color.set_a(1); } else transparent_color_ = true; });
1155         IMPORT(offset);
1156         IMPORT(invert);
1157         IMPORT(antialias);
1158         IMPORT(feather);
1159         IMPORT(blurtype);
1160         IMPORT(winding_style);
1161
1162         return Layer_Composite::set_param(param,value);
1163 }
1164
1165 ValueBase
1166 Layer_Shape::get_param(const String &param)const
1167 {
1168         EXPORT(color);
1169         EXPORT(offset);
1170         EXPORT(invert);
1171         EXPORT(antialias);
1172         EXPORT(feather);
1173         EXPORT(blurtype);
1174         EXPORT(winding_style);
1175
1176         EXPORT_NAME();
1177         EXPORT_VERSION();
1178
1179         return Layer_Composite::get_param(param);
1180 }
1181
1182 Layer::Vocab
1183 Layer_Shape::get_param_vocab()const
1184 {
1185         Layer::Vocab ret(Layer_Composite::get_param_vocab());
1186
1187         ret.push_back(ParamDesc("color")
1188                 .set_local_name(_("Color"))
1189                 .set_description(_("Layer_Shape Color"))
1190         );
1191         ret.push_back(ParamDesc("offset")
1192                 .set_local_name(_("Position"))
1193         );
1194         ret.push_back(ParamDesc("invert")
1195                 .set_local_name(_("Invert"))
1196         );
1197         ret.push_back(ParamDesc("antialias")
1198                 .set_local_name(_("Antialiasing"))
1199         );
1200         ret.push_back(ParamDesc("feather")
1201                 .set_local_name(_("Feather"))
1202                 .set_is_distance()
1203         );
1204         ret.push_back(ParamDesc("blurtype")
1205                 .set_local_name(_("Type of Feather"))
1206                 .set_description(_("Type of feathering to use"))
1207                 .set_hint("enum")
1208                 .add_enum_value(Blur::BOX,"box",_("Box Blur"))
1209                 .add_enum_value(Blur::FASTGAUSSIAN,"fastgaussian",_("Fast Gaussian Blur"))
1210                 .add_enum_value(Blur::CROSS,"cross",_("Cross-Hatch Blur"))
1211                 .add_enum_value(Blur::GAUSSIAN,"gaussian",_("Gaussian Blur"))
1212                 .add_enum_value(Blur::DISC,"disc",_("Disc Blur"))
1213         );
1214         ret.push_back(ParamDesc("winding_style")
1215                 .set_local_name(_("Winding Style"))
1216                 .set_description(_("Winding style to use"))
1217                 .set_hint("enum")
1218                 .add_enum_value(WINDING_NON_ZERO,"nonzero",_("Non Zero"))
1219                 .add_enum_value(WINDING_EVEN_ODD,"evenodd",_("Even/Odd"))
1220         );
1221
1222         return ret;
1223 }
1224
1225 synfig::Layer::Handle
1226 Layer_Shape::hit_check(synfig::Context context, const synfig::Point &p)const
1227 {
1228         Point pos(p-offset);
1229
1230         int intercepts = edge_table->intersect(pos[0],pos[1]);
1231
1232         // If we have an odd number of intercepts, we are inside.
1233         // If we have an even number of intercepts, we are outside.
1234         bool intersect = ((!!intercepts) ^ invert);
1235
1236         if(get_amount() == 0 || get_blend_method() == Color::BLEND_ALPHA_OVER)
1237         {
1238                 intersect = false;
1239         }
1240
1241         if(intersect)
1242         {
1243                 synfig::Layer::Handle tmp;
1244                 if(get_blend_method()==Color::BLEND_BEHIND && (tmp=context.hit_check(p)))
1245                         return tmp;
1246                 if(Color::is_onto(get_blend_method()))
1247                 {
1248                         //if there's something in the lower layer then we're set...
1249                         if(!context.hit_check(p).empty())
1250                                 return const_cast<Layer_Shape*>(this);
1251                 }else if(get_blend_method() == Color::BLEND_ALPHA_OVER)
1252                 {
1253                         synfig::info("layer_shape::hit_check - we've got alphaover");
1254                         //if there's something in the lower layer then we're set...
1255                         if(color.get_a() < 0.1 && get_amount() > .9)
1256                         {
1257                                 synfig::info("layer_shape::hit_check - can see through us... so nothing");
1258                                 return Handle();
1259                         }else return context.hit_check(p);
1260                 }else
1261                         return const_cast<Layer_Shape*>(this);
1262         }
1263
1264         return context.hit_check(p);
1265 }
1266
1267 Color
1268 Layer_Shape::get_color(Context context, const Point &p)const
1269 {
1270         Point pp = p;
1271
1272         if(feather)
1273                 pp = Blur(feather,feather,blurtype)(p);
1274
1275         Point pos(pp-offset);
1276
1277         int intercepts = edge_table->intersect(pos[0],pos[1]);
1278
1279         // If we have an odd number of intercepts, we are inside.
1280         // If we have an even number of intercepts, we are outside.
1281         bool intersect = ((!!intercepts) ^ invert);
1282
1283         if(!intersect)
1284                 return context.get_color(pp);
1285
1286         //Ok, we're inside... bummmm ba bum buM...
1287         if(get_blend_method() == Color::BLEND_STRAIGHT && get_amount() == 1)
1288                 return color;
1289         else
1290                 return Color::blend(color,context.get_color(p),get_amount(),get_blend_method());
1291 }
1292
1293 //************** SCANLINE RENDERING *********************
1294 void Layer_Shape::PolySpan::line_to(Real x, Real y)
1295 {
1296         Real n[4] = {0,0,0,0};
1297         bool afterx = false;
1298
1299         const Real xin(x), yin(y);
1300
1301         Real dx = x - cur_x;
1302         Real dy = y - cur_y;
1303
1304         //CLIP IT!!!!
1305         try {
1306         //outside y - ignore entirely
1307         if(      (cur_y >= window.maxy && y >= window.maxy)
1308            ||(cur_y <  window.miny && y <  window.miny) )
1309         {
1310                 cur_x = x;
1311                 cur_y = y;
1312         }
1313         else //not degenerate - more complicated
1314         {
1315                 if(dy > 0) //be sure it's not tooooo small
1316                 {
1317                         // cur_y ... window.miny ... window.maxy ... y
1318
1319                         //initial degenerate - initial clip
1320                         if(cur_y < window.miny)
1321                         {
1322                                 //new clipped start point (must also move pen)
1323                                 n[2] = cur_x + (window.miny - cur_y) * dx / dy;
1324
1325                                 cur_x = n[2];
1326                                 cur_y = window.miny;
1327                                 move_pen((int)floor(cur_x),window.miny);
1328                         }
1329
1330                         //generate data for the ending clipped info
1331                         if(y > window.maxy)
1332                         {
1333                                 //initial line to intersection (and degenerate)
1334                                 n[2] = x + (window.maxy - y) * dx / dy;
1335
1336                                 //intersect coords
1337                                 x = n[2];
1338                                 y = window.maxy;
1339                         }
1340                 }
1341                 else
1342                 {
1343                         //initial degenerate - initial clip
1344                         if(cur_y > window.maxy)
1345                         {
1346                                 //new clipped start point (must also move pen)
1347                                 n[2] = cur_x + (window.maxy - cur_y) * dx / dy;
1348
1349                                 cur_x = n[2];
1350                                 cur_y = window.maxy;
1351                                 move_pen((int)floor(cur_x),window.maxy);
1352                         }
1353
1354                         //generate data for the ending clipped info
1355                         if(y < window.miny)
1356                         {
1357                                 //initial line to intersection (and degenerate)
1358                                 n[2] = x + (window.miny - y) * dx / dy;
1359
1360                                 //intersect coords
1361                                 x = n[2];
1362                                 y = window.miny;
1363                         }
1364                 }
1365
1366                 //all degenerate - but require bounded clipped values
1367                 if(   (cur_x >= window.maxx && x >= window.maxx)
1368                         ||(cur_x <  window.minx && x <  window.minx) )
1369                 {
1370                         //clip both vertices - but only needed in the x direction
1371                         cur_x = max(cur_x,      (Real)window.minx);
1372                         cur_x = min(cur_x,      (Real)window.maxx);
1373
1374                         //clip the dest values - y is already clipped
1375                         x = max(x,(Real)window.minx);
1376                         x = min(x,(Real)window.maxx);
1377
1378                         //must start at new point...
1379                         move_pen((int)floor(cur_x),(int)floor(cur_y));
1380
1381                         draw_line(cur_x,cur_y,x,y);
1382
1383                         cur_x = xin;
1384                         cur_y = yin;
1385                 }
1386                 else
1387                 {
1388                         //clip x
1389                         if(dx > 0)
1390                         {
1391                                 //initial degenerate - initial clip
1392                                 if(cur_x < window.minx)
1393                                 {
1394                                         //need to draw an initial segment from clippedx,cur_y to clippedx,intersecty
1395                                         n[2] = cur_y + (window.minx - cur_x) * dy / dx;
1396
1397                                         move_pen(window.minx,(int)floor(cur_y));
1398                                         draw_line(window.minx,cur_y,window.minx,n[2]);
1399
1400                                         cur_x = window.minx;
1401                                         cur_y = n[2];
1402                                 }
1403
1404                                 //generate data for the ending clipped info
1405                                 if(x > window.maxx)
1406                                 {
1407                                         //initial line to intersection (and degenerate)
1408                                         n[2] = y + (window.maxx - x) * dy / dx;
1409
1410                                         n[0] = window.maxx;
1411                                         n[1] = y;
1412
1413                                         //intersect coords
1414                                         x = window.maxx;
1415                                         y = n[2];
1416                                         afterx = true;
1417                                 }
1418                         }else
1419                         {
1420                                 //initial degenerate - initial clip
1421                                 if(cur_x > window.maxx)
1422                                 {
1423                                         //need to draw an initial segment from clippedx,cur_y to clippedx,intersecty
1424                                         n[2] = cur_y + (window.maxx - cur_x) * dy / dx;
1425
1426                                         move_pen(window.maxx,(int)floor(cur_y));
1427                                         draw_line(window.maxx,cur_y,window.maxx,n[2]);
1428
1429                                         cur_x = window.maxx;
1430                                         cur_y = n[2];
1431                                 }
1432
1433                                 //generate data for the ending clipped info
1434                                 if(x < window.minx)
1435                                 {
1436                                         //initial line to intersection (and degenerate)
1437                                         n[2] = y + (window.minx - x) * dy / dx;
1438
1439                                         n[0] = window.minx;
1440                                         n[1] = y;
1441
1442                                         //intersect coords
1443                                         x = window.minx;
1444                                         y = n[2];
1445                                         afterx = true;
1446                                 }
1447                         }
1448
1449                         move_pen((int)floor(cur_x),(int)floor(cur_y));
1450                         //draw the relevant line (clipped)
1451                         draw_line(cur_x,cur_y,x,y);
1452
1453                         if(afterx)
1454                         {
1455                                 draw_line(x,y,n[0],n[1]);
1456                         }
1457
1458                         cur_x = xin;
1459                         cur_y = yin;
1460                 }
1461         }
1462         } catch(...) { synfig::error("line_to: cur_x=%f, cur_y=%f, x=%f, y=%f", cur_x, cur_y, x, y); throw; }
1463
1464         flags |= NotClosed|NotSorted;
1465 }
1466
1467 static inline bool clip_conic(const Point *const p, const ContextRect &r)
1468 {
1469         const Real minx = min(min(p[0][0],p[1][0]),p[2][0]);
1470         const Real miny = min(min(p[0][1],p[1][1]),p[2][1]);
1471         const Real maxx = max(max(p[0][0],p[1][0]),p[2][0]);
1472         const Real maxy = max(max(p[0][1],p[1][1]),p[2][1]);
1473
1474         return  (minx > r.maxx) ||
1475                         (maxx < r.minx) ||
1476                         (miny > r.maxy) ||
1477                         (maxy < r.miny);
1478 }
1479
1480 static inline bool clip_cubic(const Point *const p, const ContextRect &r)
1481 {
1482         /*const Real minx = min(min(p[0][0],p[1][0]),min(p[2][0],p[3][0]));
1483         const Real miny = min(min(p[0][1],p[1][1]),min(p[2][1],p[3][1]));
1484         const Real maxx = max(max(p[0][0],p[1][0]),max(p[2][0],p[3][1]));
1485         const Real maxy = max(max(p[0][1],p[1][1]),max(p[2][1],p[3][1]));
1486
1487         return  (minx > r.maxx) ||
1488                         (maxx < r.minx) ||
1489                         (miny > r.maxy) ||
1490                         (maxy < r.miny);*/
1491
1492         return  ((p[0][0] > r.maxx) && (p[1][0] > r.maxx) && (p[2][0] > r.maxx) && (p[3][0] > r.maxx)) ||
1493                         ((p[0][0] < r.minx) && (p[1][0] < r.minx) && (p[2][0] < r.minx) && (p[3][0] < r.minx)) ||
1494                         ((p[0][1] > r.maxy) && (p[1][1] > r.maxy) && (p[2][1] > r.maxy) && (p[3][1] > r.maxy)) ||
1495                         ((p[0][1] < r.miny) && (p[1][1] < r.miny) && (p[2][1] < r.miny) && (p[3][1] < r.miny));
1496 }
1497
1498 static inline Real max_edges_cubic(const Point *const p)
1499 {
1500         const Real x1 = p[1][0] - p[0][0];
1501         const Real y1 = p[1][1] - p[0][1];
1502
1503         const Real x2 = p[2][0] - p[1][0];
1504         const Real y2 = p[2][1] - p[1][1];
1505
1506         const Real x3 = p[3][0] - p[2][0];
1507         const Real y3 = p[3][1] - p[2][1];
1508
1509         const Real d1 = x1*x1 + y1*y1;
1510         const Real d2 = x2*x2 + y2*y2;
1511         const Real d3 = x3*x3 + y3*y3;
1512
1513         return max(max(d1,d2),d3);
1514 }
1515
1516 static inline Real max_edges_conic(const Point *const p)
1517 {
1518         const Real x1 = p[1][0] - p[0][0];
1519         const Real y1 = p[1][1] - p[0][1];
1520
1521         const Real x2 = p[2][0] - p[1][0];
1522         const Real y2 = p[2][1] - p[1][1];
1523
1524         const Real d1 = x1*x1 + y1*y1;
1525         const Real d2 = x2*x2 + y2*y2;
1526
1527         return max(d1,d2);
1528 }
1529
1530 void Layer_Shape::PolySpan::conic_to(Real x1, Real y1, Real x, Real y)
1531 {
1532         Point *current = arc;
1533         int             level = 0;
1534         int     num = 0;
1535         bool    onsecond = false;
1536
1537         arc[0] = Point(x,y);
1538         arc[1] = Point(x1,y1);
1539         arc[2] = Point(cur_x,cur_y);
1540
1541         //just draw the line if it's outside
1542         if(clip_conic(arc,window))
1543         {
1544                 line_to(x,y);
1545                 return;
1546         }
1547
1548         //Ok so it's not super degenerate, subdivide and draw (run through minimum subdivision levels first)
1549         while(current >= arc)
1550         {
1551                 if(num >= MAX_SUBDIVISION_SIZE)
1552                 {
1553                         warning("Curve subdivision somehow ran out of space while tessellating!");
1554
1555                         //do something...
1556                         assert(0);
1557                         return;
1558                 }else
1559                 //if the curve is clipping then draw degenerate
1560                 if(clip_conic(current,window))
1561                 {
1562                         line_to(current[0][0],current[0][1]); //backwards so front is destination
1563                         current -= 2;
1564                         if(onsecond) level--;
1565                         onsecond = true;
1566                         num--;
1567                         continue;
1568                 }else
1569                 //if we are not at the level minimum
1570                 if(level < MIN_SUBDIVISION_DRAW_LEVELS)
1571                 {
1572                         Subd_Conic_Stack(current);
1573                         current += 2;           //cursor on second curve
1574                         level ++;
1575                         num ++;
1576                         onsecond = false;
1577                         continue;
1578                 }else
1579                 //split it again, if it's too big
1580                 if(max_edges_conic(current) > 0.25) //distance of .5 (cover no more than half the pixel)
1581                 {
1582                         Subd_Conic_Stack(current);
1583                         current += 2;           //cursor on second curve
1584                         level ++;
1585                         num ++;
1586                         onsecond = false;
1587                 }
1588                 else    //NOT TOO BIG? RENDER!!!
1589                 {
1590                         //cur_x,cur_y = current[2], so we need to go 1,0
1591                         line_to(current[1][0],current[1][1]);
1592                         line_to(current[0][0],current[0][1]);
1593
1594                         current -= 2;
1595                         if(onsecond) level--;
1596                         num--;
1597                         onsecond = true;
1598                 }
1599         }
1600 }
1601
1602 void Layer_Shape::PolySpan::cubic_to(Real x1, Real y1, Real x2, Real y2, Real x, Real y)
1603 {
1604         Point *current = arc;
1605         int             num = 0;
1606         int             level = 0;
1607         bool    onsecond = false;
1608
1609         arc[0] = Point(x,y);
1610         arc[1] = Point(x2,y2);
1611         arc[2] = Point(x1,y1);
1612         arc[3] = Point(cur_x,cur_y);
1613
1614         //just draw the line if it's outside
1615         if(clip_cubic(arc,window))
1616         {
1617                 line_to(x,y);
1618                 return;
1619         }
1620
1621         //Ok so it's not super degenerate, subdivide and draw (run through minimum subdivision levels first)
1622         while(current >= arc) //once current goes below arc, there are no more curves left
1623         {
1624                 if(num >= MAX_SUBDIVISION_SIZE)
1625                 {
1626                         warning("Curve subdivision somehow ran out of space while tessellating!");
1627
1628                         //do something...
1629                         assert(0);
1630                         return;
1631                 }else
1632
1633                 //if we are not at the level minimum
1634                 if(level < MIN_SUBDIVISION_DRAW_LEVELS)
1635                 {
1636                         Subd_Cubic_Stack(current);
1637                         current += 3;           //cursor on second curve
1638                         level ++;
1639                         num ++;
1640                         onsecond = false;
1641                         continue;
1642                 }else
1643                 //if the curve is clipping then draw degenerate
1644                 if(clip_cubic(current,window))
1645                 {
1646                         line_to(current[0][0],current[0][1]); //backwards so front is destination
1647                         current -= 3;
1648                         if(onsecond) level--;
1649                         onsecond = true;
1650                         num --;
1651                         continue;
1652                 }
1653                 else
1654                 //split it again, if it's too big
1655                 if(max_edges_cubic(current) > 0.25) //could use max_edges<3>
1656                 {
1657                         Subd_Cubic_Stack(current);
1658                         current += 3;           //cursor on second curve
1659                         level ++;
1660                         num ++;
1661                         onsecond = false;
1662                 }
1663                 else //NOT TOO BIG? RENDER!!!
1664                 {
1665                         //cur_x,cur_y = current[3], so we need to go 2,1,0
1666                         line_to(current[2][0],current[2][1]);
1667                         line_to(current[1][0],current[1][1]);
1668                         line_to(current[0][0],current[0][1]);
1669
1670                         current -= 3;
1671                         if(onsecond) level--;
1672                         num --;
1673                         onsecond = true;
1674                 }
1675         }
1676 }
1677
1678 //******************** LINE ALGORITHMS ****************************
1679 // THESE CALCULATE THE AREA AND THE COVER FOR THE MARKS, TO THEN SCAN CONVERT
1680 // - BROKEN UP INTO SCANLINES (draw_line - y intersections),
1681 //   THEN THE COVER AND AREA PER TOUCHED PIXEL IS CALCULATED (draw_scanline - x intersections)
1682 void Layer_Shape::PolySpan::draw_scanline(int y, Real x1, Real fy1, Real x2, Real fy2)
1683 {
1684         int     ix1 = (int)floor(x1);
1685         int     ix2 = (int)floor(x2);
1686         Real fx1 = x1 - ix1;
1687         Real fx2 = x2 - ix2;
1688
1689         Real dx,dy,dydx,mult;
1690
1691         dx = x2 - x1;
1692         dy = fy2 - fy1;
1693
1694         //case horizontal line
1695         if(fy1 == fy2)
1696         {
1697                 move_pen(ix2,y); //pen needs to be at the last coord
1698                 return;
1699         }
1700
1701         //case all in same pixel
1702         if(ix1 == ix2)  //impossible for degenerate case (covered by the previous cases)
1703         {
1704                 current.addcover(dy,(fx1 + fx2)*dy/2); //horizontal trapezoid area
1705                 return;
1706         }
1707
1708         if(dx > 0)
1709         {
1710                 // ---->        fx1...1  0...1  ...  0...1  0...fx2
1711                 dydx = dy / dx;
1712
1713                 //set initial values
1714                 //Iterate through the covered pixels
1715                 mult = (1 - fx1)*dydx;  //next y intersection diff value (at 1)
1716
1717                 //first pixel
1718                 current.addcover(mult,(1 + fx1)*mult/2);        // fx1,fy1,1,fy@1 - starting trapezoidal area
1719
1720                 //move to the next pixel
1721                 fy1 += mult;
1722                 ix1++;
1723
1724                 move_pen(ix1,y);
1725
1726                 //set up for whole ones
1727                 while(ix1 != ix2)
1728                 {
1729                         //trapezoid(0,y1,1,y1+dydx);
1730                         current.addcover(dydx,dydx/2);  //accumulated area 1/2 the cover
1731
1732                         //move to next pixel (+1)
1733                         ix1++;
1734                         fy1 += dydx;
1735                         move_pen(ix1,y);
1736                 }
1737
1738                 //last pixel
1739                 //final y-pos - last intersect pos
1740                 mult = fx2 * dydx;
1741                 current.addcover(mult,(0+fx2)*mult/2);
1742         }else
1743         {
1744                 // fx2...1  0...1  ...  0...1  0...fx1   <----
1745                 //mult = (0 - fx1) * dy / dx;
1746                 //neg sign sucked into dydx
1747                 dydx = -dy / dx;
1748
1749                 //set initial values
1750                 //Iterate through the covered pixels
1751                 mult = fx1*dydx;        //next y intersection diff value
1752
1753                 //first pixel
1754                 current.addcover(mult,fx1*mult/2);      // fx1,fy1,0,fy@0 - starting trapezoidal area
1755
1756                 //move to next pixel
1757                 fy1 += mult;
1758                 ix1--;
1759
1760                 move_pen(ix1,y);
1761
1762                 //set up for whole ones
1763                 while(ix1 != ix2)
1764                 {
1765                         //trapezoid(0,y1,1,y1+dydx);
1766                         current.addcover(dydx,dydx/2);  //accumulated area 1/2 the cover
1767
1768                         //move to next pixel (-1)
1769                         fy1 += dydx;
1770                         ix1--;
1771                         move_pen(ix1,y);
1772                 }
1773
1774                 //last pixel
1775                 mult = fy2 - fy1; //final y-pos - last intersect pos
1776
1777                 current.addcover(mult,(fx2+1)*mult/2);
1778         }
1779 }
1780
1781 void Layer_Shape::PolySpan::draw_line(Real x1, Real y1, Real x2, Real y2)
1782 {
1783         int iy1 = (int)floor(y1);
1784         int iy2 = (int)floor(y2);
1785         Real fy1 = y1 - iy1;
1786         Real fy2 = y2 - iy2;
1787
1788         assert(!isnan(fy1));
1789         assert(!isnan(fy2));
1790
1791         Real dx,dy,dxdy,mult,x_from,x_to;
1792
1793         const Real SLOPE_EPSILON = 1e-10;
1794
1795         //case all one scanline
1796         if(iy1 == iy2)
1797         {
1798                 draw_scanline(iy1,x1,y1,x2,y2);
1799                 return;
1800         }
1801
1802         //difference values
1803         dy = y2 - y1;
1804         dx = x2 - x1;
1805
1806         //case vertical line
1807         if(dx < SLOPE_EPSILON && dx > -SLOPE_EPSILON)
1808         {
1809                 //calc area and cover on vertical line
1810                 if(dy > 0)
1811                 {
1812                         // ---->        fx1...1  0...1  ...  0...1  0...fx2
1813                         Real sub;
1814
1815                         int      ix1 = (int)floor(x1);
1816                         Real fx1 = x1 - ix1;
1817
1818                         //current pixel
1819                         sub = 1 - fy1;
1820
1821                         current.addcover(sub,fx1*sub);
1822
1823                         //next pixel
1824                         iy1++;
1825
1826                         //move pen to next pixel
1827                         move_pen(ix1,iy1);
1828
1829                         while(iy1 != iy2)
1830                         {
1831                                 //accumulate cover
1832                                 current.addcover(1,fx1);
1833
1834                                 //next pixel
1835                                 iy1++;
1836                                 move_pen(ix1,iy1);
1837                         }
1838
1839                         //last pixel
1840                         current.addcover(fy2,fy2*fx1);
1841                 }else
1842                 {
1843                         Real sub;
1844
1845                         int      ix1 = (int)floor(x1);
1846                         Real fx1 = x1 - ix1;
1847
1848                         //current pixel
1849                         sub = 0 - fy1;
1850
1851                         current.addcover(sub,fx1*sub);
1852
1853                         //next pixel
1854                         iy1--;
1855
1856                         move_pen(ix1,iy1);
1857
1858                         while(iy1 != iy2)
1859                         {
1860                                 //accumulate in current pixel
1861                                 current.addcover(-1,-fx1);
1862
1863                                 //move to next
1864                                 iy1--;
1865                                 move_pen(ix1,iy1);
1866                         }
1867
1868                         current.addcover(fy2-1,(fy2-1)*fx1);
1869                 }
1870                 return;
1871         }
1872
1873         //case normal line - guaranteed dx != 0 && dy != 0
1874
1875         //calculate the initial intersection with "next" scanline
1876         if(dy > 0)
1877         {
1878                 dxdy = dx / dy;
1879
1880                 mult = (1 - fy1) * dxdy;
1881
1882                 //x intersect scanline
1883                 x_from = x1 + mult;
1884                 draw_scanline(iy1,x1,fy1,x_from,1);
1885
1886                 //move to next line
1887                 iy1++;
1888
1889                 move_pen((int)floor(x_from),iy1);
1890
1891                 while(iy1 != iy2)
1892                 {
1893                         //keep up on the x axis, and render the current scanline
1894                         x_to = x_from + dxdy;
1895                         draw_scanline(iy1,x_from,0,x_to,1);
1896                         x_from = x_to;
1897
1898                         //move to next pixel
1899                         iy1++;
1900                         move_pen((int)floor(x_from),iy1);
1901                 }
1902
1903                 //draw the last one, fractional
1904                 draw_scanline(iy2,x_from,0,x2,fy2);
1905
1906         }else
1907         {
1908                 dxdy = -dx / dy;
1909
1910                 mult = fy1 * dxdy;
1911
1912                 //x intersect scanline
1913                 x_from = x1 + mult;
1914                 draw_scanline(iy1,x1,fy1,x_from,0);
1915
1916                 //each line after
1917                 iy1--;
1918
1919                 move_pen((int)floor(x_from),iy1);
1920
1921                 while(iy1 != iy2)
1922                 {
1923                         x_to = x_from + dxdy;
1924                         draw_scanline(iy1,x_from,1,x_to,0);
1925                         x_from = x_to;
1926
1927                         iy1--;
1928                         move_pen((int)floor(x_from),iy1);
1929                 }
1930                 //draw the last one, fractional
1931                 draw_scanline(iy2,x_from,1,x2,fy2);
1932         }
1933 }
1934
1935 //****** LAYER PEN OPERATIONS (move_to, line_to, etc.) ******
1936 void Layer_Shape::move_to(Real x, Real y)
1937 {
1938         //const int sizeblock = sizeof(Primitive)+sizeof(Point);
1939         Primitive       op;
1940         Point           p(x,y);
1941
1942         op.operation = Primitive::MOVE_TO;
1943         op.number = 1;  //one point for now
1944
1945         if(lastbyteop == Primitive::MOVE_TO)
1946         {
1947                 char *ptr = &bytestream[lastoppos];
1948                 memcpy(ptr,&op,sizeof(op));
1949                 memcpy(ptr+sizeof(op),&p,sizeof(p));
1950         }
1951         else //make a new op
1952         {
1953                 lastbyteop = Primitive::MOVE_TO;
1954                 lastoppos = bytestream.size();
1955
1956                 bytestream.insert(bytestream.end(),(char*)&op,(char*)(&op+1));  //insert the bytes for the header
1957                 bytestream.insert(bytestream.end(),(char*)&p,(char*)(&p+1));    //insert the bytes for data
1958         }
1959
1960         edge_table->move_to(x,y);
1961 }
1962
1963 void Layer_Shape::close()
1964 {
1965         Primitive op;
1966
1967         op.operation = Primitive::CLOSE;
1968         op.number = 0;
1969
1970         if(lastbyteop == Primitive::CLOSE)
1971         {
1972         }else
1973         {
1974                 lastbyteop = Primitive::CLOSE;
1975                 lastoppos = bytestream.size();
1976
1977                 bytestream.insert(bytestream.end(),(char*)&op,(char*)(&op+1)); //insert header
1978         }
1979
1980         edge_table->close();
1981         //should not affect the bounding box since it would just be returning to old point...
1982 }
1983
1984 void Layer_Shape::endpath()
1985 {
1986         Primitive op;
1987
1988         op.operation = Primitive::END;
1989         op.number = 0;
1990
1991         if(lastbyteop == Primitive::END || lastbyteop == Primitive::NONE)
1992         {
1993         }else
1994         {
1995                 bytestream.insert(bytestream.end(),(char*)&op,(char*)(&op+1));
1996         }
1997         //should not affect the bounding box since it would just be returning to old point... if at all
1998 }
1999
2000 void Layer_Shape::line_to(Real x, Real y)
2001 {
2002         assert(!isnan(x));
2003         assert(!isnan(y));
2004
2005         //const int sizeblock = sizeof(Primitive)+sizeof(Point);
2006         Primitive       op;
2007         Point           p(x,y);
2008
2009         op.operation = Primitive::LINE_TO;
2010         op.number = 1;  //one point for now
2011
2012         if(lastbyteop == Primitive::MOVE_TO || lastbyteop == Primitive::LINE_TO)
2013         {
2014                 //only need to insert the point
2015                 bytestream.insert(bytestream.end(),(char*)&p,(char*)(&p+1));
2016
2017                 Primitive * prim = (Primitive *)&bytestream[lastoppos];
2018                 prim->number++; //increment number of points in the list
2019         }else
2020         {
2021                 lastbyteop = Primitive::LINE_TO;
2022                 lastoppos = bytestream.size();
2023
2024                 bytestream.insert(bytestream.end(),(char*)&op,(char*)(&op+1));  //insert the bytes for the header
2025                 bytestream.insert(bytestream.end(),(char*)&p,(char*)(&p+1));    //insert the bytes for data
2026         }
2027
2028         edge_table->line_to(x,y);
2029 }
2030
2031 void Layer_Shape::conic_to(Real x1, Real y1, Real x, Real y)
2032 {
2033         //const int sizeblock = sizeof(Primitive)+sizeof(Point)*2;
2034         Primitive       op;
2035         Point           p(x,y);
2036         Point           p1(x1,y1);
2037
2038         op.operation = Primitive::CONIC_TO;
2039         op.number = 2;  //2 points for now
2040
2041         if(lastbyteop == Primitive::CONIC_TO)
2042         {
2043                 //only need to insert the new points
2044                 bytestream.insert(bytestream.end(),(char*)&p1,(char*)(&p1+1));
2045                 bytestream.insert(bytestream.end(),(char*)&p,(char*)(&p+1));
2046
2047                 Primitive * prim = (Primitive *)&bytestream[lastoppos];
2048                 prim->number += 2; //increment number of points in the list
2049         }else
2050         {
2051                 lastbyteop = Primitive::CONIC_TO;
2052                 lastoppos = bytestream.size();
2053
2054                 bytestream.insert(bytestream.end(),(char*)&op,(char*)(&op+1));  //insert the bytes for the header
2055                 bytestream.insert(bytestream.end(),(char*)&p1,(char*)(&p1+1));  //insert the bytes for data
2056                 bytestream.insert(bytestream.end(),(char*)&p,(char*)(&p+1));    //insert the bytes for data
2057         }
2058
2059         edge_table->conic_to(x1,y1,x,y);
2060 }
2061
2062 void Layer_Shape::conic_to_smooth(Real x, Real y)                               //x1,y1 derived from current tangent
2063 {
2064         //const int sizeblock = sizeof(Primitive)+sizeof(Point);
2065         Primitive       op;
2066         Point           p(x,y);
2067
2068         op.operation = Primitive::CONIC_TO_SMOOTH;
2069         op.number = 1;  //2 points for now
2070
2071         if(lastbyteop == Primitive::CONIC_TO_SMOOTH)
2072         {
2073                 //only need to insert the new point
2074                 bytestream.insert(bytestream.end(),(char*)&p,(char*)(&p+1));
2075
2076                 Primitive * prim = (Primitive *)&bytestream[lastoppos];
2077                 prim->number += 1; //increment number of points in the list
2078         }else
2079         {
2080                 lastbyteop = Primitive::CONIC_TO_SMOOTH;
2081                 lastoppos = bytestream.size();
2082
2083                 bytestream.insert(bytestream.end(),(char*)&op,(char*)(&op+1));  //insert the bytes for the header
2084                 bytestream.insert(bytestream.end(),(char*)&p,(char*)(&p+1));    //insert the bytes for data
2085         }
2086
2087         edge_table->conic_to_smooth(x,y);
2088 }
2089
2090 void Layer_Shape::curve_to(Real x1, Real y1, Real x2, Real y2, Real x, Real y)
2091 {
2092         //const int sizeblock = sizeof(Primitive)+sizeof(Point)*3;
2093         Primitive       op;
2094         Point           p(x,y);
2095         Point           p1(x1,y1);
2096         Point           p2(x2,y2);
2097
2098         op.operation = Primitive::CUBIC_TO;
2099         op.number = 3;  //3 points for now
2100
2101         if(lastbyteop == Primitive::CUBIC_TO)
2102         {
2103                 //only need to insert the new points
2104                 bytestream.insert(bytestream.end(),(char*)&p1,(char*)(&p1+1));
2105                 bytestream.insert(bytestream.end(),(char*)&p2,(char*)(&p2+1));
2106                 bytestream.insert(bytestream.end(),(char*)&p,(char*)(&p+1));
2107
2108                 Primitive * prim = (Primitive *)&bytestream[lastoppos];
2109                 prim->number += 3; //increment number of points in the list
2110         }else
2111         {
2112                 lastbyteop = Primitive::CUBIC_TO;
2113                 lastoppos = bytestream.size();
2114
2115                 bytestream.insert(bytestream.end(),(char*)&op,(char*)(&op+1));  //insert the bytes for the header
2116                 bytestream.insert(bytestream.end(),(char*)&p1,(char*)(&p1+1));  //insert the bytes for data
2117                 bytestream.insert(bytestream.end(),(char*)&p2,(char*)(&p2+1));  //insert the bytes for data
2118                 bytestream.insert(bytestream.end(),(char*)&p,(char*)(&p+1));    //insert the bytes for data
2119         }
2120
2121         edge_table->curve_to(x1,y1,x2,y2,x,y);
2122 }
2123
2124 void Layer_Shape::curve_to_smooth(Real x2, Real y2, Real x, Real y)             //x1,y1 derived from current tangent
2125 {
2126         //const int sizeblock = sizeof(Primitive)+sizeof(Point)*3;
2127         Primitive       op;
2128         Point           p(x,y);
2129         Point           p2(x2,y2);
2130
2131         op.operation = Primitive::CUBIC_TO_SMOOTH;
2132         op.number = 2;  //3 points for now
2133
2134         if(lastbyteop == Primitive::CUBIC_TO_SMOOTH)
2135         {
2136                 //only need to insert the new points
2137                 bytestream.insert(bytestream.end(),(char*)&p2,(char*)(&p2+1));
2138                 bytestream.insert(bytestream.end(),(char*)&p,(char*)(&p+1));
2139
2140                 Primitive * prim = (Primitive *)&bytestream[lastoppos];
2141                 prim->number += 2; //increment number of points in the list
2142         }else
2143         {
2144                 lastbyteop = Primitive::CUBIC_TO_SMOOTH;
2145                 lastoppos = bytestream.size();
2146
2147                 bytestream.insert(bytestream.end(),(char*)&op,(char*)(&op+1));  //insert the bytes for the header
2148                 bytestream.insert(bytestream.end(),(char*)&p2,(char*)(&p2+1));  //insert the bytes for data
2149                 bytestream.insert(bytestream.end(),(char*)&p,(char*)(&p+1));    //insert the bytes for data
2150         }
2151 }
2152
2153 // ACCELERATED RENDER FUNCTION - TRANSLATE BYTE CODE INTO FUNCTION CALLS
2154
2155 bool Layer_Shape::render_polyspan(Surface *surface, PolySpan &polyspan,
2156                                                                 Color::BlendMethod got_blend_method, Color::value_type got_amount) const
2157 {
2158         Surface::alpha_pen p(surface->begin(),got_amount,_BlendFunc(got_blend_method));
2159         PolySpan::cover_array::iterator cur_mark = polyspan.covers.begin();
2160         PolySpan::cover_array::iterator end_mark = polyspan.covers.end();
2161
2162         Real cover,area,alpha;
2163
2164         int     y,x;
2165
2166         p.set_value(color);
2167         cover = 0;
2168
2169         if(cur_mark == end_mark)
2170         {
2171                 //no marks at all
2172                 if(invert)
2173                 {
2174                         p.move_to(polyspan.window.minx,polyspan.window.miny);
2175                         p.put_block(polyspan.window.maxy - polyspan.window.miny,polyspan.window.maxx - polyspan.window.minx);
2176                 }
2177                 return true;
2178         }
2179
2180         //fill initial rect / line
2181         if(invert)
2182         {
2183                 //fill all the area above the first vertex
2184                 p.move_to(polyspan.window.minx,polyspan.window.miny);
2185                 y = polyspan.window.miny;
2186                 int l = polyspan.window.maxx - polyspan.window.minx;
2187
2188                 p.put_block(cur_mark->y - polyspan.window.miny,l);
2189
2190                 //fill the area to the left of the first vertex on that line
2191                 l = cur_mark->x - polyspan.window.minx;
2192                 p.move_to(polyspan.window.minx,cur_mark->y);
2193                 if(l) p.put_hline(l);
2194         }
2195
2196         for(;;)
2197         {
2198                 y = cur_mark->y;
2199                 x = cur_mark->x;
2200
2201                 p.move_to(x,y);
2202
2203                 area = cur_mark->area;
2204                 cover += cur_mark->cover;
2205
2206                 //accumulate for the current pixel
2207                 while(++cur_mark != polyspan.covers.end())
2208                 {
2209                         if(y != cur_mark->y || x != cur_mark->x)
2210                                 break;
2211
2212                         area += cur_mark->area;
2213                         cover += cur_mark->cover;
2214                 }
2215
2216                 //draw pixel - based on covered area
2217                 if(area)        //if we're ok, draw the current pixel
2218                 {
2219                         alpha = polyspan.ExtractAlpha(cover - area, winding_style);
2220                         if(invert) alpha = 1 - alpha;
2221
2222                         if(!antialias)
2223                         {
2224                                 if(alpha >= .5) p.put_value();
2225                         }
2226                         else if(alpha) p.put_value_alpha(alpha);
2227
2228                         p.inc_x();
2229                         x++;
2230                 }
2231
2232                 //if we're done, don't use iterator and exit
2233                 if(cur_mark == end_mark) break;
2234
2235                 //if there is no more live pixels on this line, goto next
2236                 if(y != cur_mark->y)
2237                 {
2238                         if(invert)
2239                         {
2240                                 //fill the area at the end of the line
2241                                 p.put_hline(polyspan.window.maxx - x);
2242
2243                                 //fill area at the beginning of the next line
2244                                 p.move_to(polyspan.window.minx,cur_mark->y);
2245                                 p.put_hline(cur_mark->x - polyspan.window.minx);
2246                         }
2247
2248                         cover = 0;
2249
2250                         continue;
2251                 }
2252
2253                 //draw span to next pixel - based on total amount of pixel cover
2254                 if(x < cur_mark->x)
2255                 {
2256                         alpha = polyspan.ExtractAlpha(cover, winding_style);
2257                         if(invert) alpha = 1 - alpha;
2258
2259                         if(!antialias)
2260                         {
2261                                 if(alpha >= .5) p.put_hline(cur_mark->x - x);
2262                         }
2263                         else if(alpha) p.put_hline(cur_mark->x - x,alpha);
2264                 }
2265         }
2266
2267         //fill the after stuff
2268         if(invert)
2269         {
2270                 //fill the area at the end of the line
2271                 p.put_hline(polyspan.window.maxx - x);
2272
2273                 //fill area at the beginning of the next line
2274                 p.move_to(polyspan.window.minx,y+1);
2275                 p.put_block(polyspan.window.maxy - y - 1,polyspan.window.maxx - polyspan.window.minx);
2276         }
2277
2278         return true;
2279 }
2280
2281 bool Layer_Shape::render_polyspan(etl::surface<float> *surface, PolySpan &polyspan) const
2282 {
2283         etl::surface<float>::pen p(surface->begin());
2284         PolySpan::cover_array::iterator cur_mark = polyspan.covers.begin();
2285         PolySpan::cover_array::iterator end_mark = polyspan.covers.end();
2286
2287         Real cover,area,alpha;
2288
2289         int     y,x;
2290
2291         cover = 0;
2292
2293         //the pen always writes 1 (unless told to do otherwise)
2294         p.set_value(1);
2295
2296         if(cur_mark == end_mark)
2297         {
2298                 //no marks at all
2299                 if(invert)
2300                 {
2301                         p.move_to(polyspan.window.minx,polyspan.window.miny);
2302                         p.put_block(polyspan.window.maxy - polyspan.window.miny,polyspan.window.maxx - polyspan.window.minx);
2303                 }
2304                 return true;
2305         }
2306
2307         //fill initial rect / line
2308         if(invert)
2309         {
2310                 //fill all the area above the first vertex
2311                 p.move_to(polyspan.window.minx,polyspan.window.miny);
2312                 y = polyspan.window.miny;
2313                 int l = polyspan.window.maxx - polyspan.window.minx;
2314
2315                 p.put_block(cur_mark->y - polyspan.window.miny,l);
2316
2317                 //fill the area to the left of the first vertex on that line
2318                 l = cur_mark->x - polyspan.window.minx;
2319                 p.move_to(polyspan.window.minx,cur_mark->y);
2320                 if(l) p.put_hline(l);
2321
2322                 for(;;)
2323                 {
2324                         y = cur_mark->y;
2325                         x = cur_mark->x;
2326
2327                         p.move_to(x,y);
2328
2329                         area = cur_mark->area;
2330                         cover += cur_mark->cover;
2331
2332                         //accumulate for the current pixel
2333                         while(++cur_mark != polyspan.covers.end())
2334                         {
2335                                 if(y != cur_mark->y || x != cur_mark->x)
2336                                         break;
2337
2338                                 area += cur_mark->area;
2339                                 cover += cur_mark->cover;
2340                         }
2341
2342                         //draw pixel - based on covered area
2343                         if(area)        //if we're ok, draw the current pixel
2344                         {
2345                                 alpha = 1 - polyspan.ExtractAlpha(cover - area, winding_style);
2346                                 if(!antialias)
2347                                 {
2348                                         if(alpha >= .5) p.put_value();
2349                                 }
2350                                 else if(alpha) p.put_value(alpha);
2351
2352                                 p.inc_x();
2353                                 x++;
2354                         }
2355
2356                         //if we're done, don't use iterator and exit
2357                         if(cur_mark == end_mark) break;
2358
2359                         //if there is no more live pixels on this line, goto next
2360                         if(y != cur_mark->y)
2361                         {
2362                                 //fill the area at the end of the line
2363                                 p.put_hline(polyspan.window.maxx - x);
2364
2365                                 //fill area at the beginning of the next line
2366                                 p.move_to(polyspan.window.minx,cur_mark->y);
2367                                 p.put_hline(cur_mark->x - polyspan.window.minx);
2368
2369                                 cover = 0;
2370
2371                                 continue;
2372                         }
2373
2374                         //draw span to next pixel - based on total amount of pixel cover
2375                         if(x < cur_mark->x)
2376                         {
2377                                 alpha = 1 - polyspan.ExtractAlpha(cover, winding_style);
2378                                 if(!antialias)
2379                                 {
2380                                         if(alpha >= .5) p.put_hline(cur_mark->x - x);
2381                                 }
2382                                 else if(alpha) p.put_hline(cur_mark->x - x,alpha);
2383                         }
2384                 }
2385
2386                 //fill the area at the end of the line
2387                 p.put_hline(polyspan.window.maxx - x);
2388
2389                 //fill area at the beginning of the next line
2390                 p.move_to(polyspan.window.minx,y+1);
2391                 p.put_block(polyspan.window.maxy - y - 1,polyspan.window.maxx - polyspan.window.minx);
2392         }else
2393         {
2394                 for(;;)
2395                 {
2396                         y = cur_mark->y;
2397                         x = cur_mark->x;
2398
2399                         p.move_to(x,y);
2400
2401                         area = cur_mark->area;
2402                         cover += cur_mark->cover;
2403
2404                         //accumulate for the current pixel
2405                         while(++cur_mark != polyspan.covers.end())
2406                         {
2407                                 if(y != cur_mark->y || x != cur_mark->x)
2408                                         break;
2409
2410                                 area += cur_mark->area;
2411                                 cover += cur_mark->cover;
2412                         }
2413
2414                         //draw pixel - based on covered area
2415                         if(area)        //if we're ok, draw the current pixel
2416                         {
2417                                 alpha = polyspan.ExtractAlpha(cover - area, winding_style);
2418                                 if(!antialias)
2419                                 {
2420                                         if(alpha >= .5) p.put_value();
2421                                 }
2422                                 else if(alpha) p.put_value(alpha);
2423
2424                                 p.inc_x();
2425                                 x++;
2426                         }
2427
2428                         //if we're done, don't use iterator and exit
2429                         if(cur_mark == end_mark) break;
2430
2431                         //if there is no more live pixels on this line, goto next
2432                         if(y != cur_mark->y)
2433                         {
2434                                 cover = 0;
2435
2436                                 continue;
2437                         }
2438
2439                         //draw span to next pixel - based on total amount of pixel cover
2440                         if(x < cur_mark->x)
2441                         {
2442                                 alpha = polyspan.ExtractAlpha(cover, winding_style);
2443                                 if(!antialias)
2444                                 {
2445                                         if(alpha >= .5) p.put_hline(cur_mark->x - x);
2446                                 }
2447                                 else if(alpha) p.put_hline(cur_mark->x - x,alpha);
2448                         }
2449                 }
2450         }
2451
2452         return true;
2453 }
2454
2455 bool
2456 Layer_Shape::accelerated_render(Context context,Surface *surface,int quality, const RendDesc &renddesc, ProgressCallback *cb)const
2457 {
2458         const unsigned int w = renddesc.get_w();
2459         const unsigned int h = renddesc.get_h();
2460
2461         const Real pw = abs(renddesc.get_pw());
2462         const Real ph = abs(renddesc.get_ph());
2463
2464         //const Real OFFSET_EPSILON = 1e-8;
2465         SuperCallback stageone(cb,1,10000,15001+renddesc.get_h());
2466         SuperCallback stagetwo(cb,10000,10001+renddesc.get_h(),15001+renddesc.get_h());
2467         SuperCallback stagethree(cb,10001+renddesc.get_h(),15001+renddesc.get_h(),15001+renddesc.get_h());
2468
2469         // Render what is behind us
2470
2471         //clip if it satisfies the invert solid thing
2472         if(is_solid_color() && invert)
2473         {
2474                 Rect aabb = edge_table->aabb;
2475                 Point tl = renddesc.get_tl() - offset;
2476
2477                 Real    pw = renddesc.get_pw(),
2478                                 ph = renddesc.get_ph();
2479
2480                 Rect    nrect;
2481
2482                 Real    pixelfeatherx = quality == 10 ? 0 : abs(feather/pw),
2483                                 pixelfeathery = quality == 10 ? 0 : abs(feather/ph);
2484
2485                 nrect.set_point((aabb.minx - tl[0])/pw,(aabb.miny - tl[1])/ph);
2486                 nrect.expand((aabb.maxx - tl[0])/pw,(aabb.maxy - tl[1])/ph);
2487
2488                 RendDesc        optdesc(renddesc);
2489
2490                 //make sure to expand so we gain subpixels rather than lose them
2491                 nrect.minx = floor(nrect.minx-pixelfeatherx); nrect.miny = floor(nrect.miny-pixelfeathery);
2492                 nrect.maxx = ceil(nrect.maxx+pixelfeatherx); nrect.maxy = ceil(nrect.maxy+pixelfeathery);
2493
2494                 //make sure the subwindow is clipped with our tile window (minimize useless drawing)
2495                 set_intersect(nrect,nrect,Rect(0,0,renddesc.get_w(),renddesc.get_h()));
2496
2497                 //must resize the surface first
2498                 surface->set_wh(renddesc.get_w(),renddesc.get_h());
2499                 surface->clear();
2500
2501                 //only render anything if it's visible from our current tile
2502                 if(nrect.valid())
2503                 {
2504                         //set the subwindow to the viewable pixels and render it to the subsurface
2505                         optdesc.set_subwindow((int)nrect.minx, (int)nrect.miny,
2506                                 (int)(nrect.maxx - nrect.minx), (int)(nrect.maxy - nrect.miny));
2507
2508                         Surface optimizedbacksurf;
2509                         if(!context.accelerated_render(&optimizedbacksurf,quality,optdesc,&stageone))
2510                                 return false;
2511
2512                         //blit that onto the original surface so we can pretend that nothing ever happened
2513                         Surface::pen p = surface->get_pen((int)nrect.minx,(int)nrect.miny);
2514                         optimizedbacksurf.blit_to(p);
2515                 }
2516         }else
2517         {
2518                 if(!context.accelerated_render(surface,quality,renddesc,&stageone))
2519                         return false;
2520         }
2521
2522         if(cb && !cb->amount_complete(10000,10001+renddesc.get_h())) return false;
2523
2524         if(feather && quality != 10)
2525         {
2526                 //we have to blur rather than be crappy
2527
2528                 //so make a separate surface
2529                 RendDesc        workdesc(renddesc);
2530
2531                 etl::surface<float>     shapesurface;
2532
2533                 //the expanded size = 1/2 the size in each direction rounded up
2534                 int     halfsizex = (int) (abs(feather*.5/pw) + 3),
2535                         halfsizey = (int) (abs(feather*.5/ph) + 3);
2536
2537                 //expand by 1/2 size in each direction on either side
2538                 switch(blurtype)
2539                 {
2540                         case Blur::DISC:
2541                         case Blur::BOX:
2542                         case Blur::CROSS:
2543                         {
2544                                 workdesc.set_subwindow(-max(1,halfsizex),-max(1,halfsizey),w+2*max(1,halfsizex),h+2*max(1,halfsizey));
2545                                 break;
2546                         }
2547                         case Blur::FASTGAUSSIAN:
2548                         {
2549                                 if(quality < 4)
2550                                 {
2551                                         halfsizex*=2;
2552                                         halfsizey*=2;
2553                                 }
2554                                 workdesc.set_subwindow(-max(1,halfsizex),-max(1,halfsizey),w+2*max(1,halfsizex),h+2*max(1,halfsizey));
2555                                 break;
2556                         }
2557                         case Blur::GAUSSIAN:
2558                         {
2559                         #define GAUSSIAN_ADJUSTMENT             (0.05)
2560                                 Real    pw = (Real)workdesc.get_w()/(workdesc.get_br()[0]-workdesc.get_tl()[0]);
2561                                 Real    ph = (Real)workdesc.get_h()/(workdesc.get_br()[1]-workdesc.get_tl()[1]);
2562
2563                                 pw=pw*pw;
2564                                 ph=ph*ph;
2565
2566                                 halfsizex = (int)(abs(pw)*feather*GAUSSIAN_ADJUSTMENT+0.5);
2567                                 halfsizey = (int)(abs(ph)*feather*GAUSSIAN_ADJUSTMENT+0.5);
2568
2569                                 halfsizex = (halfsizex + 1)/2;
2570                                 halfsizey = (halfsizey + 1)/2;
2571                                 workdesc.set_subwindow( -halfsizex, -halfsizey, w+2*halfsizex, h+2*halfsizey );
2572
2573                                 break;
2574                         }
2575                 }
2576
2577                 shapesurface.set_wh(workdesc.get_w(),workdesc.get_h());
2578                 shapesurface.clear();
2579
2580                 //render the shape
2581                 if(!render_shape(&shapesurface,quality,workdesc,&stagetwo))return false;
2582
2583                 //blur the image
2584                 Blur(feather,feather,blurtype,&stagethree)(shapesurface,workdesc.get_br()-workdesc.get_tl(),shapesurface);
2585
2586                 //blend with stuff below it...
2587                 unsigned int u = halfsizex, v = halfsizey, x = 0, y = 0;
2588                 for(y = 0; y < h; y++,v++)
2589                 {
2590                         u = halfsizex;
2591                         for(x = 0; x < w; x++,u++)
2592                         {
2593                                 float a = shapesurface[v][u];
2594                                 if(a)
2595                                 {
2596                                         //a = floor(a*255+0.5f)/255;
2597                                         (*surface)[y][x]=Color::blend(color,(*surface)[y][x],a*get_amount(),get_blend_method());
2598                                 }
2599                                 //else (*surface)[y][x] = worksurface[v][u];
2600                         }
2601                 }
2602
2603                 //we are done
2604                 if(cb && !cb->amount_complete(100,100))
2605                 {
2606                         synfig::warning("Layer_Shape: could not set amount complete");
2607                         return false;
2608                 }
2609
2610                 return true;
2611         }else
2612         {
2613                 //might take out to reduce code size
2614                 return render_shape(surface,true,quality,renddesc,&stagetwo);
2615         }
2616
2617 }
2618
2619 bool
2620 Layer_Shape::render_shape(Surface *surface,bool useblend,int /*quality*/,
2621                                                         const RendDesc &renddesc, ProgressCallback *cb)const
2622 {
2623         int tmp(0);
2624
2625         SuperCallback   progress(cb,0,renddesc.get_h(),renddesc.get_h());
2626
2627         // If our amount is set to zero, no need to render anything
2628         if(!get_amount())
2629                 return true;
2630
2631         //test new polygon renderer
2632         // Build edge table
2633         // Width and Height of a pixel
2634         const int       w = renddesc.get_w();
2635         const int       h = renddesc.get_h();
2636         const Real      pw = renddesc.get_w()/(renddesc.get_br()[0]-renddesc.get_tl()[0]);
2637         const Real      ph = renddesc.get_h()/(renddesc.get_br()[1]-renddesc.get_tl()[1]);
2638
2639         const Point     tl = renddesc.get_tl();
2640
2641         Vector tangent (0,0);
2642
2643         PolySpan        span;
2644
2645         // if the pixels are zero sized then we're too zoomed out to see anything
2646         if (pw == 0 || ph == 0)
2647                 return true;
2648
2649         //optimization for tessellating only inside tiles
2650         span.window.minx = 0;
2651         span.window.miny = 0;
2652         span.window.maxx = w;
2653         span.window.maxy = h;
2654
2655         //pointers for processing the bytestream
2656         const char *current     = &bytestream[0];
2657         const char *end                 = &bytestream[bytestream.size()];
2658
2659         int     operation       = Primitive::NONE;
2660         int number              = 0;
2661         int curnum;
2662
2663         Primitive       *curprim;
2664         Point           *data;
2665
2666         Real x,y,x1,y1,x2,y2;
2667
2668
2669         while(current < end)
2670         {
2671                 tmp++;
2672
2673                 try {
2674
2675                 //get the op code safely
2676                 curprim = (Primitive *)current;
2677
2678                 //advance past indices
2679                 current += sizeof(Primitive);
2680                 if(current > end)
2681                 {
2682                         warning("Layer_Shape::accelerated_render - Error in the byte stream, not enough space for next declaration");
2683                         return false;
2684                 }
2685
2686                 //get the relevant data
2687                 operation       = curprim->operation;
2688                 number          = curprim->number;
2689
2690                 if(operation == Primitive::END)
2691                         break;
2692
2693                 if(operation == Primitive::CLOSE)
2694                 {
2695                         if(span.notclosed())
2696                         {
2697                                 tangent[0] = span.close_x - span.cur_x;
2698                                 tangent[1] = span.close_y - span.cur_y;
2699                                 span.close();
2700                         }
2701                         continue;
2702                 }
2703
2704                 data = (Point*)current;
2705                 current += sizeof(Point)*number;
2706
2707                 //check data positioning
2708                 if(current > end)
2709                 {
2710                         warning("Layer_Shape::accelerated_render - Error in the byte stream, in sufficient data space for declared number of points");
2711                         return false;
2712                 }
2713
2714                 } catch(...) { synfig::error("Layer_Shape::render_shape()1: Caught an exception after %d loops, rethrowing...", tmp); throw; }
2715
2716                 //transfer all the data - RLE optimized
2717                 for(curnum=0; curnum < number;)
2718                 {
2719                         switch(operation)
2720                         {
2721                                 case Primitive::MOVE_TO:
2722                                 {
2723                                         x = data[curnum][0];
2724                                         x = (x - tl[0] + offset[0])*pw;
2725                                         y = data[curnum][1];
2726                                         y = (y - tl[1] + offset[1])*ph;
2727
2728                                         if(curnum == 0)
2729                                         {
2730                                                 span.move_to(x,y);
2731
2732                                                 tangent[0] = 0;
2733                                                 tangent[1] = 0;
2734                                         }
2735                                         else
2736                                         {
2737                                                 tangent[0] = x - span.cur_x;
2738                                                 tangent[1] = y - span.cur_y;
2739
2740                                                 span.line_to(x,y);
2741                                         }
2742
2743                                         curnum++; //only advance one point
2744
2745                                         break;
2746                                 }
2747
2748                                 case Primitive::LINE_TO:
2749                                 {
2750                                         x = data[curnum][0];
2751                                         x = (x - tl[0] + offset[0])*pw;
2752                                         y = data[curnum][1];
2753                                         y = (y - tl[1] + offset[1])*ph;
2754
2755                                         tangent[0] = x - span.cur_x;
2756                                         tangent[1] = y - span.cur_y;
2757
2758                                         span.line_to(x,y);
2759                                         curnum++;
2760                                         break;
2761                                 }
2762
2763                                 case Primitive::CONIC_TO:
2764                                 {
2765                                         x = data[curnum+1][0];
2766                                         x = (x - tl[0] + offset[0])*pw;
2767                                         y = data[curnum+1][1];
2768                                         y = (y - tl[1] + offset[1])*ph;
2769
2770                                         x1 = data[curnum][0];
2771                                         x1 = (x1 - tl[0] + offset[0])*pw;
2772                                         y1 = data[curnum][1];
2773                                         y1 = (y1 - tl[1] + offset[1])*ph;
2774
2775                                         tangent[0] = 2*(x - x1);
2776                                         tangent[1] = 2*(y - y1);
2777
2778                                         span.conic_to(x1,y1,x,y);
2779                                         curnum += 2;
2780                                         break;
2781                                 }
2782
2783                                 case Primitive::CONIC_TO_SMOOTH:
2784                                 {
2785                                         x = data[curnum][0];
2786                                         x = (x - tl[0] + offset[0])*pw;
2787                                         y = data[curnum][1];
2788                                         y = (y - tl[1] + offset[1])*ph;
2789
2790                                         x1 = span.cur_x + tangent[0]/2;
2791                                         y1 = span.cur_y + tangent[1]/2;
2792
2793                                         tangent[0] = 2*(x - x1);
2794                                         tangent[1] = 2*(y - y1);
2795
2796                                         span.conic_to(x1,y1,x,y);
2797                                         curnum ++;
2798
2799                                         break;
2800                                 }
2801
2802                                 case Primitive::CUBIC_TO:
2803                                 {
2804                                         x = data[curnum+2][0];
2805                                         x = (x - tl[0] + offset[0])*pw;
2806                                         y = data[curnum+2][1];
2807                                         y = (y - tl[1] + offset[1])*ph;
2808
2809                                         x2 = data[curnum+1][0];
2810                                         x2 = (x2 - tl[0] + offset[0])*pw;
2811                                         y2 = data[curnum+1][1];
2812                                         y2 = (y2 - tl[1] + offset[1])*ph;
2813
2814                                         x1 = data[curnum][0];
2815                                         x1 = (x1 - tl[0] + offset[0])*pw;
2816                                         y1 = data[curnum][1];
2817                                         y1 = (y1 - tl[1] + offset[1])*ph;
2818
2819                                         tangent[0] = 2*(x - x2);
2820                                         tangent[1] = 2*(y - y2);
2821
2822                                         span.cubic_to(x1,y1,x2,y2,x,y);
2823                                         curnum += 3;
2824
2825                                         break;
2826                                 }
2827
2828                                 case Primitive::CUBIC_TO_SMOOTH:
2829                                 {
2830                                         x = data[curnum+1][0];
2831                                         x = (x - tl[0] + offset[0])*pw;
2832                                         y = data[curnum+1][1];
2833                                         y = (y - tl[1] + offset[1])*ph;
2834
2835                                         x2 = data[curnum][0];
2836                                         x2 = (x2 - tl[0] + offset[0])*pw;
2837                                         y2 = data[curnum][1];
2838                                         y2 = (y2 - tl[1] + offset[1])*ph;
2839
2840                                         x1 = span.cur_x + tangent[0]/3.0;
2841                                         y1 = span.cur_y + tangent[1]/3.0;
2842
2843                                         tangent[0] = 2*(x - x2);
2844                                         tangent[1] = 2*(y - y2);
2845
2846                                         span.cubic_to(x1,y1,x2,y2,x,y);
2847                                         curnum += 2;
2848
2849                                         break;
2850                                 }
2851                         }
2852                 }
2853         }
2854
2855         //sort the bastards so we can render everything
2856         span.sort_marks();
2857
2858         return render_polyspan(surface, span,
2859                         useblend?get_blend_method():Color::BLEND_STRAIGHT,
2860                         useblend?get_amount():1.0);
2861 }
2862
2863 bool
2864 Layer_Shape::render_shape(etl::surface<float> *surface,int /*quality*/,
2865                                                         const RendDesc &renddesc, ProgressCallback */*cb*/)const
2866 {
2867         // If our amount is set to zero, no need to render anything
2868         if(!get_amount())
2869                 return true;
2870
2871         //test new polygon renderer
2872         // Build edge table
2873         // Width and Height of a pixel
2874         const int       w = renddesc.get_w();
2875         const int       h = renddesc.get_h();
2876         const Real      pw = renddesc.get_w()/(renddesc.get_br()[0]-renddesc.get_tl()[0]);
2877         const Real      ph = renddesc.get_h()/(renddesc.get_br()[1]-renddesc.get_tl()[1]);
2878
2879         const Point     tl = renddesc.get_tl();
2880
2881         Vector tangent (0,0);
2882
2883         PolySpan        span;
2884
2885         //optimization for tessellating only inside tiles
2886         span.window.minx = 0;
2887         span.window.miny = 0;
2888         span.window.maxx = w;
2889         span.window.maxy = h;
2890
2891         //pointers for processing the bytestream
2892         const char *current     = &bytestream[0];
2893         const char *end                 = &bytestream[bytestream.size()];
2894
2895         int     operation       = Primitive::NONE;
2896         int number              = 0;
2897         int curnum;
2898
2899         Primitive       *curprim;
2900         Point           *data;
2901
2902         Real x,y,x1,y1,x2,y2;
2903
2904         while(current < end)
2905         {
2906                 //get the op code safely
2907                 curprim = (Primitive *)current;
2908
2909                 //advance past indices
2910                 current += sizeof(Primitive);
2911                 if(current > end)
2912                 {
2913                         warning("Layer_Shape::accelerated_render - Error in the byte stream, not enough space for next declaration");
2914                         return false;
2915                 }
2916
2917                 //get the relevant data
2918                 operation       = curprim->operation;
2919                 number          = curprim->number;
2920
2921                 if(operation == Primitive::END)
2922                         break;
2923
2924                 if(operation == Primitive::CLOSE)
2925                 {
2926                         if(span.notclosed())
2927                         {
2928                                 tangent[0] = span.close_x - span.cur_x;
2929                                 tangent[1] = span.close_y - span.cur_y;
2930                                 span.close();
2931                         }
2932                         continue;
2933                 }
2934
2935                 data = (Point*)current;
2936                 current += sizeof(Point)*number;
2937
2938                 //check data positioning
2939                 if(current > end)
2940                 {
2941                         warning("Layer_Shape::accelerated_render - Error in the byte stream, in sufficient data space for declared number of points");
2942                         return false;
2943                 }
2944
2945                 //transfer all the data
2946                 for(curnum=0; curnum < number;)
2947                 {
2948                         switch(operation)
2949                         {
2950                                 case Primitive::MOVE_TO:
2951                                 {
2952                                         x = data[curnum][0];
2953                                         x = (x - tl[0] + offset[0])*pw;
2954                                         y = data[curnum][1];
2955                                         y = (y - tl[1] + offset[1])*ph;
2956
2957                                         if(curnum == 0)
2958                                         {
2959                                                 span.move_to(x,y);
2960
2961                                                 tangent[0] = 0;
2962                                                 tangent[1] = 0;
2963                                         }
2964                                         else
2965                                         {
2966                                                 tangent[0] = x - span.cur_x;
2967                                                 tangent[1] = y - span.cur_y;
2968
2969                                                 span.line_to(x,y);
2970                                         }
2971
2972                                         curnum++; //only advance one point
2973
2974                                         break;
2975                                 }
2976
2977                                 case Primitive::LINE_TO:
2978                                 {
2979                                         x = data[curnum][0];
2980                                         x = (x - tl[0] + offset[0])*pw;
2981                                         y = data[curnum][1];
2982                                         y = (y - tl[1] + offset[1])*ph;
2983
2984                                         tangent[0] = x - span.cur_x;
2985                                         tangent[1] = y - span.cur_y;
2986
2987                                         span.line_to(x,y);
2988                                         curnum++;
2989                                         break;
2990                                 }
2991
2992                                 case Primitive::CONIC_TO:
2993                                 {
2994                                         x = data[curnum+1][0];
2995                                         x = (x - tl[0] + offset[0])*pw;
2996                                         y = data[curnum+1][1];
2997                                         y = (y - tl[1] + offset[1])*ph;
2998
2999                                         x1 = data[curnum][0];
3000                                         x1 = (x1 - tl[0] + offset[0])*pw;
3001                                         y1 = data[curnum][1];
3002                                         y1 = (y1 - tl[1] + offset[1])*ph;
3003
3004                                         tangent[0] = 2*(x - x1);
3005                                         tangent[1] = 2*(y - y1);
3006
3007                                         span.conic_to(x1,y1,x,y);
3008                                         curnum += 2;
3009                                         break;
3010                                 }
3011
3012                                 case Primitive::CONIC_TO_SMOOTH:
3013                                 {
3014                                         x = data[curnum][0];
3015                                         x = (x - tl[0] + offset[0])*pw;
3016                                         y = data[curnum][1];
3017                                         y = (y - tl[1] + offset[1])*ph;
3018
3019                                         x1 = span.cur_x + tangent[0]/2;
3020                                         y1 = span.cur_y + tangent[1]/2;
3021
3022                                         tangent[0] = 2*(x - x1);
3023                                         tangent[1] = 2*(y - y1);
3024
3025                                         span.conic_to(x1,y1,x,y);
3026                                         curnum ++;
3027
3028                                         break;
3029                                 }
3030
3031                                 case Primitive::CUBIC_TO:
3032                                 {
3033                                         x = data[curnum+2][0];
3034                                         x = (x - tl[0] + offset[0])*pw;
3035                                         y = data[curnum+2][1];
3036                                         y = (y - tl[1] + offset[1])*ph;
3037
3038                                         x2 = data[curnum+1][0];
3039                                         x2 = (x2 - tl[0] + offset[0])*pw;
3040                                         y2 = data[curnum+1][1];
3041                                         y2 = (y2 - tl[1] + offset[1])*ph;
3042
3043                                         x1 = data[curnum][0];
3044                                         x1 = (x1 - tl[0] + offset[0])*pw;
3045                                         y1 = data[curnum][1];
3046                                         y1 = (y1 - tl[1] + offset[1])*ph;
3047
3048                                         tangent[0] = 2*(x - x2);
3049                                         tangent[1] = 2*(y - y2);
3050
3051                                         span.cubic_to(x1,y1,x2,y2,x,y);
3052                                         curnum += 3;
3053
3054                                         break;
3055                                 }
3056
3057                                 case Primitive::CUBIC_TO_SMOOTH:
3058                                 {
3059                                         x = data[curnum+1][0];
3060                                         x = (x - tl[0] + offset[0])*pw;
3061                                         y = data[curnum+1][1];
3062                                         y = (y - tl[1] + offset[1])*ph;
3063
3064                                         x2 = data[curnum][0];
3065                                         x2 = (x2 - tl[0] + offset[0])*pw;
3066                                         y2 = data[curnum][1];
3067                                         y2 = (y2 - tl[1] + offset[1])*ph;
3068
3069                                         x1 = span.cur_x + tangent[0]/3.0;
3070                                         y1 = span.cur_y + tangent[1]/3.0;
3071
3072                                         tangent[0] = 2*(x - x2);
3073                                         tangent[1] = 2*(y - y2);
3074
3075                                         span.cubic_to(x1,y1,x2,y2,x,y);
3076                                         curnum += 2;
3077
3078                                         break;
3079                                 }
3080                         }
3081                 }
3082         }
3083
3084         //sort the bastards so we can render everything
3085         span.sort_marks();
3086
3087         return render_polyspan(surface, span);
3088 }
3089
3090 Rect
3091 Layer_Shape::get_bounding_rect()const
3092 {
3093         if(invert)
3094                 return Rect::full_plane();
3095
3096         if (edge_table->initaabb)
3097                 return Rect::zero();
3098
3099         Rect bounds(edge_table->aabb+offset);
3100         bounds.expand(max((bounds.get_min() - bounds.get_max()).mag()*0.01,
3101                                           feather));
3102
3103         return bounds;
3104 }