synfig-core/tags/synfig_0_61_05/synfig-core/src/synfig/layer_shape.cpp

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