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