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

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