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

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