synfig-studio/trunk/src/synfigapp/blineconvert.cpp

   1 /* === S Y N F I G ========================================================= */
   2 /*!     \file blineconvert.cpp
   3 **      \brief Template File
   4 **
   5 **      $Id: blineconvert.cpp,v 1.1.1.1 2005/01/07 03:34:37 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 "blineconvert.h"
  32 #include <vector>
  33 #include <ETL/gaussian>
  34 #include <ETL/hermite>
  35 #include <ETL/clock>
  36 #include <float.h>
  37 #include <algorithm>
  38 #include <synfig/general.h>
  39 #include <cassert>
  40
  41
  42
  43 #endif
  44
  45 /* === U S I N G =========================================================== */
  46
  47 using namespace std;
  48 using namespace etl;
  49 using namespace synfig;
  50
  51 /* === M A C R O S ========================================================= */
  52
  53 #define EPSILON         (1e-10)
  54
  55 /* === G L O B A L S ======================================================= */
  56
  57 /* === P R O C E D U R E S ================================================= */
  58
  59 /* === M E T H O D S ======================================================= */
  60
  61
  62 //Derivative Functions for numerical approximation
  63
  64 //bias == 0 will get F' at f3, bias < 0 will get F' at f1, and bias > 0 will get F' at f5
  65 template < class T >
  66 inline void FivePointdt(T &df, const T &f1, const T &f2, const T &f3, const T &f4, const T &f5, int bias)
  67 {
  68         if(bias == 0)
  69         {
  70                 //middle
  71                 df = (f1 - f2*8 + f4*8 - f5)*(1/12.0f);
  72         }else if(bias < 0)
  73         {
  74                 //left
  75                 df = (-f1*25 + f2*48 - f3*36 + f4*16 - f5*3)*(1/12.0f);
  76         }else
  77         {
  78                 //right
  79                 df = (f1*3 - f2*16 + f3*36 - f4*48 + f5*25)*(1/12.0f);
  80         }
  81 }
  82
  83 template < class T >
  84 inline void ThreePointdt(T &df, const T &f1, const T &f2, const T &f3, int bias)
  85 {
  86         if(bias == 0)
  87         {
  88                 //middle
  89                 df = (-f1 + f3)*(1/2.0f);
  90         }else if(bias < 0)
  91         {
  92                 //left
  93                 df = (-f1*3 + f2*4 - f3)*(1/2.0f);
  94         }else
  95         {
  96                 //right
  97                 df = (f1 - f2*4 + f3*3)*(1/2.0f);
  98         }
  99 }
 100
 101 template < class T >
 102 inline void ThreePointddt(T &df, const T &f1, const T &f2, const T &f3, int bias)
 103 {
 104         //a 3 point approximation pretends to have constant acceleration, so only one algorithm needed for left, middle, or right
 105         df = (f1 -f2*2 + f3)*(1/2.0f);
 106 }
 107
 108 // WARNING -- totaly broken
 109 template < class T >
 110 inline void FivePointddt(T &df, const T &f1, const T &f2, const T &f3, int bias)
 111 {
 112         if(bias == 0)
 113         {
 114                 assert(0); // !?
 115                 //middle
 116                 //df = (- f1 + f2*16 - f3*30 +  f4*16 - f5)*(1/12.0f);
 117         }/*else if(bias < 0)
 118         {
 119                 //left
 120                 df = (f1*7 - f2*26*4 + f3*19*6 - f4*14*4 + f5*11)*(1/12.0f);
 121         }else
 122         {
 123                 //right
 124                 df = (f1*3 - f2*16 + f3*36 - f4*48 + f5*25)*(1/12.0f);
 125         }*/
 126         //side ones don't work, use 3 point
 127 }
 128
 129 //implement an arbitrary derivative
 130 //dumb algorithm
 131 template < class T >
 132 void DerivativeApprox(T &df, const T f[], const Real t[], int npoints, int indexval)
 133 {
 134         /*
 135         Lj(x) = PI_i!=j (x - xi) / PI_i!=j (xj - xi)
 136
 137         so Lj'(x) = SUM_k PI_i!=j|k (x - xi) / PI_i!=j (xj - xi)
 138         */
 139
 140         unsigned int i,j,k,i0,i1;
 141
 142         Real Lpj,mult,div,tj;
 143         Real tval = t[indexval];
 144
 145         //sum k
 146         for(j=0;j<npoints;++j)
 147         {
 148                 Lpj = 0;
 149                 div = 1;
 150                 tj = t[j];
 151
 152                 for(k=0;k<npoints;++k)
 153                 {
 154                         if(k != j) //because there is no summand for k == j, since that term is missing from the original equation
 155                         {
 156                                 //summation for k
 157                                 for(i=0;i<npoints;++i)
 158                                 {
 159                                         if(i != k)
 160                                         {
 161                                                 mult *= tval - t[i];
 162                                         }
 163                                 }
 164
 165                                 Lpj += mult; //add into the summation
 166
 167                                 //since the ks follow the exact patern we need for the divisor (use that too)
 168                                 div *= tj - t[k];
 169                         }
 170                 }
 171
 172                 //get the actual coefficient
 173                 Lpj /= div;
 174
 175                 //add it in to the equation
 176                 df += f[j]*Lpj;
 177         }
 178 }
 179
 180 //END numerical derivatives
 181
 182 template < class T >
 183 inline int sign(T f, T tol)
 184 {
 185         if(f < -tol) return -1;
 186         if(f > tol) return 1;
 187         return 0;
 188 }
 189
 190 void GetFirstDerivatives(const std::vector<synfig::Point> &f, unsigned int left, unsigned int right, char *out, unsigned int dfstride)
 191 {
 192         unsigned int current = left;
 193
 194         if(right - left < 2)
 195                 return;
 196         else if(right - left < 3)
 197         {
 198                 synfig::Vector v = f[left+1] - f[left];
 199
 200                 //set both to the one we want
 201                 *(synfig::Vector*)out = v;
 202                 out += dfstride;
 203                 *(synfig::Vector*)out = v;
 204                 out += dfstride;
 205         }
 206         else if(right - left < 6/*5*/) //should use 3 point
 207         {
 208                 //left then middle then right
 209                 ThreePointdt(*(synfig::Vector*)out,f[left+0], f[left+1], f[left+2], -1);
 210                 current += 1;
 211                 out += dfstride;
 212
 213                 for(;current < right-1; current++, out += dfstride)
 214                 {
 215                         ThreePointdt(*(synfig::Vector*)out,f[current-1], f[current], f[current+1], 0);
 216                 }
 217
 218                 ThreePointdt(*(synfig::Vector*)out,f[right-3], f[right-2], f[right-1], 1);
 219                 current++;
 220                 out += dfstride;
 221
 222         }else //can use 5 point
 223         {
 224                 //left 2 then middle bunch then right two
 225                 //may want to use 3 point for inner edge ones
 226
 227                 FivePointdt(*(synfig::Vector*)out,f[left+0], f[left+1], f[left+2], f[left+3], f[left+4], -2);
 228                 out += dfstride;
 229                 FivePointdt(*(synfig::Vector*)out,f[left+1], f[left+2], f[left+3], f[left+4], f[left+5], -1);
 230                 out += dfstride;
 231                 current += 2;
 232
 233                 for(;current < right-2; current++, out += dfstride)
 234                 {
 235                         FivePointdt(*(synfig::Vector*)out,f[current-2], f[current-1], f[current], f[current+1], f[current+2], 0);
 236                 }
 237
 238                 FivePointdt(*(synfig::Vector*)out,f[right-5], f[right-4], f[right-3], f[right-2], f[right-1], 1);
 239                 out += dfstride;
 240                 FivePointdt(*(synfig::Vector*)out,f[right-6], f[right-5], f[right-4], f[right-3], f[right-2], 2);
 241                 out += dfstride;
 242                 current += 2;
 243         }
 244 }
 245
 246 void GetSimpleDerivatives(const std::vector<synfig::Point> &f, int left, int right,
 247                                                         std::vector<synfig::Point> &df, int outleft,
 248                                                         const std::vector<synfig::Real> &di)
 249 {
 250         int i1,i2,i;
 251         int offset = 2; //df = 1/2 (f[i+o]-f[i-o])
 252
 253         assert((int)df.size() >= right-left+outleft); //must be big enough
 254
 255         for(i = left; i < right; ++i)
 256         {
 257                 //right now indices (figure out distance later)
 258                 i1 = std::max(left,i-offset);
 259                 i2 = std::max(left,i+offset);
 260
 261                 df[outleft++] = (f[i2] - f[i1])*0.5f;
 262         }
 263 }
 264
 265 //get the curve error from the double sample list of work points (hopefully that's enough)
 266 Real CurveError(const synfig::Point *pts, unsigned int n, std::vector<synfig::Point> &work, int left, int right)
 267 {
 268         if(right-left < 2) return -1;
 269
 270         int i,j;
 271
 272         //get distances to each point
 273         Real d,dtemp,dsum;
 274         //synfig::Vector v,vt;
 275         //synfig::Point p1,p2;
 276         synfig::Point pi;
 277         std::vector<synfig::Point>::const_iterator it;//,end = work.begin()+right;
 278
 279         //unsigned int size = work.size();
 280
 281         //for each line, get distance
 282         d = 0; //starts at 0
 283         for(i = 0; i < (int)n; ++i)
 284         {
 285                 pi = pts[i];
 286
 287                 dsum = FLT_MAX;
 288
 289                 it = work.begin()+left;
 290                 //p2 = *it++; //put it at left+1
 291                 for(j = left/*+1*/; j < right; ++j,++it)
 292                 {
 293                         /*p1 = p2;
 294                         p2 = *it;
 295
 296                         v = p2 - p1;
 297                         vt = pi - p1;
 298
 299                         dtemp = v.mag_squared() > 1e-12 ? (vt*v)/v.mag_squared() : 0; //get the projected time value for the current line
 300
 301                         //get distance to line segment with the time value clamped 0-1
 302                         if(dtemp >= 1)  //use p+v
 303                         {
 304                                 vt += v; //makes it pp - (p+v)
 305                         }else if(dtemp > 0)     //use vt-proj
 306                         {
 307                                 vt -= v*dtemp; // vt - proj_v(vt)       //must normalize the projection vector to work
 308                         }
 309
 310                         //else use p
 311                         dtemp = vt.mag_squared();*/
 312
 313                         dtemp = (pi - *it).mag_squared();
 314                         if(dtemp < dsum)
 315                                 dsum = dtemp;
 316                 }
 317
 318                 //accumulate the points' min distance from the curve
 319                 d += sqrt(dsum);
 320         }
 321
 322         return d;
 323 }
 324
 325 typedef synfigapp::BLineConverter::cpindex cpindex;
 326
 327 //has the index data and the tangent scale data (relevant as it may be)
 328 int tesselate_curves(const std::vector<cpindex> &inds, const std::vector<Point> &f, const std::vector<synfig::Vector> &df, std::vector<Point> &work)
 329 {
 330         if(inds.size() < 2)
 331                 return 0;
 332
 333         etl::hermite<Point>     curve;
 334         int ntess = 0;
 335
 336         std::vector<cpindex>::const_iterator j = inds.begin(),j2, end = inds.end();
 337
 338         unsigned int ibase = inds[0].curind;
 339
 340         j2 = j++;
 341         for(; j != end; j2 = j++)
 342         {
 343                 //if this curve has invalid error (in j) then retesselate it's work points (requires reparametrization, etc.)
 344                 if(j->error < 0)
 345                 {
 346                         //get the stepsize etc. for the number of points in here
 347                         unsigned int n = j->curind - j2->curind + 1; //thats the number of points in the span
 348                         unsigned int k, kend, i0, i3;
 349                         //so reset the right chunk
 350
 351                         Real t, dt = 1/(Real)(n*2-2); //assuming that they own only n points
 352
 353                         //start at first intermediate
 354                         t = 0;
 355
 356                         i0 = j2->curind; i3 = j->curind;
 357                         k = (i0-ibase)*2; //start on first intermediary point (2x+1)
 358                         kend = (i3-ibase)*2; //last point to set (not intermediary)
 359
 360                         //build hermite curve, it's easier
 361                         curve.p1() = f[i0];
 362                         curve.p2() = f[i3];
 363                         curve.t1() = df[i0]*(df[i0].mag_squared() > 1e-4 ? j2->tangentscale/df[i0].mag() : j2->tangentscale);
 364                         curve.t2() = df[i3]*(df[i3].mag_squared() > 1e-4 ? j->tangentscale/df[i3].mag() : j->tangentscale);
 365                         curve.sync();
 366
 367                         //MUST include the end point (since we are ignoring left one)
 368                         for(; k < kend; ++k, t += dt)
 369                         {
 370                                 work[k] = curve(t);
 371                         }
 372
 373                         work[k] = curve(1); //k == kend, t == 1 -> c(t) == p2
 374                         ++ntess;
 375                 }
 376         }
 377
 378         return ntess;
 379 }
 380
 381 synfigapp::BLineConverter::BLineConverter()
 382 {
 383         pixelwidth = 1;
 384         smoothness = 0.70f;
 385         width = 0;
 386 };
 387
 388 void
 389 synfigapp::BLineConverter::clear()
 390 {
 391         f.clear();
 392         f_w.clear();
 393         ftemp.clear();
 394         df.clear();
 395         cvt.clear();
 396         brk.clear();
 397         di.clear();
 398         d_i.clear();
 399         work.clear();
 400         curind.clear();
 401 }
 402
 403 void
 404 synfigapp::BLineConverter::operator () (std::list<synfig::BLinePoint> &out, const std::list<synfig::Point> &in,const std::list<synfig::Real> &in_w)
 405 {
 406         //Profiling information
 407         /*etl::clock::value_type initialprocess=0, curveval=0, breakeval=0, disteval=0;
 408         etl::clock::value_type preproceval=0, tesseval=0, erroreval=0, spliteval=0;
 409         unsigned int                    numpre=0, numtess=0, numerror=0, numsplit=0;
 410         etl::clock_realtime timer,total;*/
 411
 412         //total.reset();
 413         if(in.size()<=1)
 414                 return;
 415
 416         clear();
 417
 418         //removing digitization error harder than expected
 419
 420         //intended to fix little pen errors caused by the way people draw (tiny juts in opposite direction)
 421         //Different solutions
 422         //      Average at both end points (will probably eliminate many points at each end of the samples)
 423         //      Average after the break points are found (weird points would still affect the curve)
 424         //      Just always get rid of breaks at the beginning and end if they are a certain distance apart
 425         //              This is will be current approach so all we do now is try to remove duplicate points
 426
 427         //remove duplicate points - very bad for fitting
 428
 429         //timer.reset();
 430
 431         {
 432                 std::list<synfig::Point>::const_iterator i = in.begin(), end = in.end();
 433                 std::list<synfig::Real>::const_iterator iw = in_w.begin();
 434                 synfig::Point   c;
 435
 436                 if(in.size() == in_w.size())
 437                 {
 438                         for(;i != end; ++i,++iw)
 439                         {
 440                                 //eliminate duplicate points
 441                                 if(*i != c)
 442                                 {
 443                                         f.push_back(c = *i);
 444                                         f_w.push_back(*iw);
 445                                 }
 446                         }
 447                 }else
 448                 {
 449                         for(;i != end; ++i)
 450                         {
 451                                 //eliminate duplicate points
 452                                 if(*i != c)
 453                                 {
 454                                         f.push_back(c = *i);
 455                                 }
 456                         }
 457                 }
 458         }
 459         //initialprocess = timer();
 460
 461         if(f.size()<=6)
 462                 return;
 463
 464         //get curvature information
 465         //timer.reset();
 466
 467         {
 468                 int i,i0,i1;
 469                 synfig::Vector v1,v2;
 470
 471                 cvt.resize(f.size());
 472
 473                 cvt.front() = 1;
 474                 cvt.back() = 1;
 475
 476                 for(i = 1; i < (int)f.size()-1; ++i)
 477                 {
 478                         i0 = std::max(0,i - 2);
 479                         i1 = std::min((int)(f.size()-1),i + 2);
 480
 481                         v1 = f[i] - f[i0];
 482                         v2 = f[i1] - f[i];
 483
 484                         cvt[i] = (v1*v2)/(v1.mag()*v2.mag());
 485                 }
 486         }
 487
 488         //curveval = timer();
 489         //synfig::info("calculated curvature");
 490
 491         //find corner points and interpolate inside those
 492         //timer.reset();
 493         {
 494                 //break at sharp derivative points
 495                 //TODO tolerance should be set based upon digitization resolution (length dependent index selection)
 496                 Real    tol = 0;                //break tolerance, for the cosine of the change in angle (really high curvature or something)
 497                 Real    fixdistsq = 4*width*width; //the distance to ignore breaks at the end points (for fixing stuff)
 498                 unsigned int i = 0;
 499
 500                 int             maxi = -1, last=0;
 501                 Real    minc = 1;
 502
 503                 brk.push_back(0);
 504
 505                 for(i = 1; i < cvt.size()-1; ++i)
 506                 {
 507                         //insert if too sharp (we need to break the tangents to insert onto the break list)
 508
 509                         if(cvt[i] < tol)
 510                         {
 511                                 if(cvt[i] < minc)
 512                                 {
 513                                         minc = cvt[i];
 514                                         maxi = i;
 515                                 }
 516                         }else if(maxi >= 0)
 517                         {
 518                                 if(maxi >= last + 8)
 519                                 {
 520                                         //synfig::info("break: %d-%d",maxi+1,cvt.size());
 521                                         brk.push_back(maxi);
 522                                         last = maxi;
 523                                 }
 524                                 maxi = -1;
 525                                 minc = 1;
 526                         }
 527                 }
 528
 529                 brk.push_back(i);
 530
 531                 //postprocess for breaks too close to eachother
 532                 Real d = 0;
 533                 Point p = f[brk.front()];
 534
 535                 //first set
 536                 for(i = 1; i < brk.size()-1; ++i) //do not want to include end point...
 537                 {
 538                         d = (f[brk[i]] - p).mag_squared();
 539                         if(d > fixdistsq) break; //don't want to group breaks if we ever get over the dist...
 540                 }
 541                 //want to erase all points before...
 542                 if(i != 1)
 543                         brk.erase(brk.begin(),brk.begin()+i-1);
 544
 545                 //end set
 546                 p = f[brk.back()];
 547                 for(i = brk.size()-2; i > 0; --i) //start at one in from the end
 548                 {
 549                         d = (f[brk[i]] - p).mag_squared();
 550                         if(d > fixdistsq) break; //don't want to group breaks if we ever get over the dist
 551                 }
 552                 if(i != brk.size()-2)
 553                         brk.erase(brk.begin()+i+2,brk.end()); //erase all points that we found... found none if i has not advanced
 554                 //must not include the one we ended up on
 555         }
 556         //breakeval = timer();
 557         //synfig::info("found break points: %d",brk.size());
 558
 559         //get the distance calculation of the entire curve (for tangent scaling)
 560
 561         //timer.reset();
 562         {
 563                 synfig::Point p1,p2;
 564
 565                 p1=p2=f[0];
 566
 567                 di.resize(f.size()); d_i.resize(f.size());
 568                 Real d = 0;
 569                 for(unsigned int i = 0; i < f.size();)
 570                 {
 571                         d += (d_i[i] = (p2-p1).mag());
 572                         di[i] = d;
 573
 574                         p1=p2;
 575                         p2=f[++i];
 576                 }
 577         }
 578         //disteval = timer();
 579         //synfig::info("calculated distance");
 580
 581         //now break at every point - calculate new derivatives each time
 582
 583         //TODO
 584         //must be sure that the break points are 3 or more apart
 585         //then must also store the breaks which are not smooth, etc.
 586         //and figure out tangents between there
 587
 588         //for each pair of break points (as long as they are far enough apart) recursively subdivide stuff
 589         //ignore the detected intermediate points
 590         {
 591                 unsigned int i0=0,i3=0,is=0;
 592                 int i=0,j=0;
 593
 594                 bool done = false;
 595
 596                 Real errortol = smoothness*pixelwidth; //???? what the hell should this value be
 597
 598                 BLinePoint a;
 599                 synfig::Vector v;
 600
 601                 //intemp = f; //don't want to smooth out the corners
 602
 603                 bool breaktan = false, setwidth;
 604                 a.set_split_tangent_flag(false);
 605                 //a.set_width(width);
 606                 a.set_width(1.0f);
 607
 608                 setwidth = (f.size() == f_w.size());
 609
 610                 for(j = 0; j < (int)brk.size() - 1; ++j)
 611                 {
 612                         //for b[j] to b[j+1] subdivide and stuff
 613                         i0 = brk[j];
 614                         i3 = brk[j+1];
 615
 616                         unsigned int size = i3-i0+1; //must include the end points
 617
 618                         //new derivatives
 619                         //timer.reset();
 620                         ftemp.assign(f.begin()+i0, f.begin()+i3+1);
 621                         for(i=0;i<20;++i)
 622                                 gaussian_blur_3(ftemp.begin(),ftemp.end(),false);
 623
 624                         df.resize(size);
 625                         GetFirstDerivatives(ftemp,0,size,(char*)&df[0],sizeof(df[0]));
 626                         //GetSimpleDerivatives(ftemp,0,size,df,0,di);
 627                         //< don't have to worry about indexing stuff as it is all being taken car of right now
 628                         //preproceval += timer();
 629                         //numpre++;
 630
 631                         work.resize(size*2-1); //guarantee that all points will be tesselated correctly (one point inbetween every 2 adjacent points)
 632
 633                         //if size of work is size*2-1, the step size should be 1/(size*2 - 2)
 634                         //Real step = 1/(Real)(size*2 - 1);
 635
 636                         //start off with break points as indices
 637                         curind.clear();
 638                         curind.push_back(cpindex(i0,di[i3]-di[i0],0)); //0 error because no curve on the left
 639                         curind.push_back(cpindex(i3,di[i3]-di[i0],-1)); //error needs to be reevaluated
 640                         done = false; //we want to loop
 641
 642                         unsigned int dcount = 0;
 643
 644                         //while there are still enough points between us, and the error is too high subdivide (and invalidate neighbors that share tangents)
 645                         while(!done)
 646                         {
 647                                 //tesselate all curves with invalid error values
 648                                 work[0] = f[i0];
 649
 650                                 //timer.reset();
 651                                 /*numtess += */tesselate_curves(curind,f,df,work);
 652                                 //tesseval += timer();
 653
 654                                 //now get all error values
 655                                 //timer.reset();
 656                                 for(i = 1; i < (int)curind.size(); ++i)
 657                                 {
 658                                         if(curind[i].error < 0) //must have been retesselated, so now recalculate error value
 659                                         {
 660                                                 //evaluate error from points (starting at current index)
 661                                                 int size = curind[i].curind - curind[i-1].curind + 1;
 662                                                 curind[i].error = CurveError(&f[curind[i-1].curind], size,
 663                                                                                                          work,(curind[i-1].curind - i0)*2,(curind[i].curind - i0)*2+1);
 664
 665                                                 /*if(curind[i].error > 1.0e5)
 666                                                 {
 667                                                         synfig::info("Holy crap %d-%d error %f",curind[i-1].curind,curind[i].curind,curind[i].error);
 668                                                         curind[i].error = -1;
 669                                                         numtess += tesselate_curves(curind,f,df,work);
 670                                                         curind[i].error = CurveError(&f[curind[i-1].curind], size,
 671                                                                                                          work,0,work.size());//(curind[i-1].curind - i0)*2,(curind[i].curind - i0)*2+1);
 672                                                 }*/
 673                                                 //numerror++;
 674                                         }
 675                                 }
 676                                 //erroreval += timer();
 677
 678                                 //assume we're done
 679                                 done = true;
 680
 681                                 //check each error to see if it's too big, if so, then subdivide etc.
 682                                 int indsize = (int)curind.size();
 683                                 Real maxrelerror = 0;
 684                                 int maxi = -1;//, numpoints;
 685
 686                                 //timer.reset();
 687                                 //get the maximum error and split there
 688                                 for(i = 1; i < indsize; ++i)
 689                                 {
 690                                         //numpoints = curind[i].curind - curind[i-1].curind + 1;
 691
 692                                         if(curind[i].error > maxrelerror && curind[i].curind - curind[i-1].curind > 2) //only accept if it's valid
 693                                         {
 694                                                 maxrelerror = curind[i].error;
 695                                                 maxi = i;
 696                                         }
 697                                 }
 698
 699                                 //split if error is too great
 700                                 if(maxrelerror > errortol)
 701                                 {
 702                                         //add one to the left etc
 703                                         unsigned int    ibase = curind[maxi-1].curind, itop = curind[maxi].curind,
 704                                                                         ibreak = (ibase + itop)/2;
 705                                         Real scale, scale2;
 706
 707                                         assert(ibreak < f.size());
 708
 709                                         //synfig::info("Split %d -%d- %d, error: %f", ibase,ibreak,itop,maxrelerror);
 710
 711                                         if(ibase != itop)
 712                                         {
 713                                                 //invalidate current error of the changed tangents and add an extra segment
 714                                                 //enforce minimum tangents property
 715                                                 curind[maxi].error = -1;
 716                                                 curind[maxi-1].error = -1;
 717                                                 if(maxi+1 < indsize) curind[maxi+1].error = -1; //if there is a curve segment beyond this it will be effected as well
 718
 719                                                 scale = di[itop] - di[ibreak];
 720                                                 scale2 = maxi+1 < indsize ? di[curind[maxi+1].curind] - di[itop] : scale; //to the right valid?
 721                                                 curind[maxi].tangentscale = std::min(scale, scale2);
 722
 723                                                 scale = di[ibreak] - di[ibase];
 724                                                 scale2 = maxi >= 2 ? di[ibase] - di[curind[maxi-2].curind] : scale; // to the left valid -2 ?
 725                                                 curind[maxi-1].tangentscale = std::min(scale, scale2);
 726
 727                                                 scale = std::min(di[ibreak] - di[ibase], di[itop] - di[ibreak]);
 728
 729                                                 curind.insert(curind.begin()+maxi,cpindex(ibreak, scale, -1));
 730                                                 //curind.push_back(cpindex(ibreak, scale, -1));
 731                                                 //std::sort(curind.begin(), curind.end());
 732
 733                                                 done = false;
 734                                                 //numsplit++;
 735                                         }
 736                                 }
 737                                 //spliteval += timer();
 738
 739                                 dcount++;
 740                         }
 741
 742                         //insert the last point too (just set tangent for now
 743                         is = curind[0].curind;
 744
 745                         //first point inherits current tangent status
 746                         v = df[is - i0];
 747                         if(v.mag_squared() > EPSILON)
 748                                 v *= (curind[0].tangentscale/v.mag());
 749
 750                         if(!breaktan)
 751                                 a.set_tangent(v);
 752                         else a.set_tangent2(v);
 753
 754                         a.set_vertex(f[is]);
 755                         if(setwidth)a.set_width(f_w[is]);
 756
 757                         out.push_back(a);
 758                         a.set_split_tangent_flag(false); //won't need to break anymore
 759                         breaktan = false;
 760
 761                         for(i = 1; i < (int)curind.size()-1; ++i)
 762                         {
 763                                 is = curind[i].curind;
 764
 765                                 //first point inherits current tangent status
 766                                 v = df[is-i0];
 767                                 if(v.mag_squared() > EPSILON)
 768                                         v *= (curind[i].tangentscale/v.mag());
 769
 770                                 a.set_tangent(v); // always inside, so guaranteed to be smooth
 771                                 a.set_vertex(f[is]);
 772                                 if(setwidth)a.set_width(f_w[is]);
 773
 774                                 out.push_back(a);
 775                         }
 776
 777                         //set the last point's data
 778                         is = curind.back().curind; //should already be this
 779
 780                         v = df[is-i0];
 781                         if(v.mag_squared() > EPSILON)
 782                                 v *= (curind.back().tangentscale/v.mag());
 783
 784                         a.set_tangent1(v);
 785                         a.set_split_tangent_flag(true);
 786                         breaktan = true;
 787
 788                         //will get the vertex and tangent 2 from next round
 789                 }
 790
 791                 a.set_vertex(f[i3]);
 792                 a.set_split_tangent_flag(false);
 793                 if(setwidth)
 794                         a.set_width(f_w[i3]);
 795                 out.push_back(a);
 796
 797                 /*etl::clock::value_type totaltime = total(),
 798                                                            misctime = totaltime - initialprocess - curveval - breakeval - disteval
 799                                                                           - preproceval - tesseval - erroreval - spliteval;
 800
 801                 synfig::info(
 802                         "Curve Convert Profile:\n"
 803                         "\tInitial Preprocess:    %f\n"
 804                         "\tCurvature Calculation: %f\n"
 805                         "\tBreak Calculation:     %f\n"
 806                         "\tDistance Calculation:  %f\n"
 807                         "  Algorithm: (numtimes,totaltime)\n"
 808                         "\tPreprocess step:      (%d,%f)\n"
 809                         "\tTesselation step:     (%d,%f)\n"
 810                         "\tError step:           (%d,%f)\n"
 811                         "\tSplit step:           (%d,%f)\n"
 812                         "  Num Input: %d, Num Output: %d\n"
 813                         "  Total time: %f, Misc time: %f\n",
 814                         initialprocess, curveval,breakeval,disteval,
 815                         numpre,preproceval,numtess,tesseval,numerror,erroreval,numsplit,spliteval,
 816                         in.size(),out.size(),
 817                         totaltime,misctime);*/
 818
 819                 return;
 820         }
 821 }
 822
 823 void synfigapp::BLineConverter::EnforceMinWidth(std::list<synfig::BLinePoint> &bline, synfig::Real min_pressure)
 824 {
 825         std::list<synfig::BLinePoint>::iterator i = bline.begin(),
 826                                                                                         end = bline.end();
 827
 828         for(i = bline.begin(); i != end; ++i)
 829         {
 830                 if(i->get_width() < min_pressure)
 831                 {
 832                         i->set_width(min_pressure);
 833                 }
 834         }
 835 }