1 /* === S Y N F I G ========================================================= */
2 /*! \file blineconvert.cpp
3 ** \brief Template File
8 ** Copyright (c) 2002-2005 Robert B. Quattlebaum Jr., Adrian Bentley
10 ** This package is free software; you can redistribute it and/or
11 ** modify it under the terms of the GNU General Public License as
12 ** published by the Free Software Foundation; either version 2 of
13 ** the License, or (at your option) any later version.
15 ** This package is distributed in the hope that it will be useful,
16 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
17 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 ** General Public License for more details.
21 /* ========================================================================= */
23 /* === H E A D E R S ======================================================= */
32 #include "blineconvert.h"
34 #include <ETL/gaussian>
35 #include <ETL/hermite>
39 #include <synfig/general.h>
46 /* === U S I N G =========================================================== */
50 using namespace synfig;
52 /* === M A C R O S ========================================================= */
54 #define EPSILON (1e-10)
56 /* === G L O B A L S ======================================================= */
58 /* === P R O C E D U R E S ================================================= */
60 /* === M E T H O D S ======================================================= */
63 //Derivative Functions for numerical approximation
65 //bias == 0 will get F' at f3, bias < 0 will get F' at f1, and bias > 0 will get F' at f5
67 inline void FivePointdt(T &df, const T &f1, const T &f2, const T &f3, const T &f4, const T &f5, int bias)
72 df = (f1 - f2*8 + f4*8 - f5)*(1/12.0f);
76 df = (-f1*25 + f2*48 - f3*36 + f4*16 - f5*3)*(1/12.0f);
80 df = (f1*3 - f2*16 + f3*36 - f4*48 + f5*25)*(1/12.0f);
85 inline void ThreePointdt(T &df, const T &f1, const T &f2, const T &f3, int bias)
90 df = (-f1 + f3)*(1/2.0f);
94 df = (-f1*3 + f2*4 - f3)*(1/2.0f);
98 df = (f1 - f2*4 + f3*3)*(1/2.0f);
102 // template < class T >
103 // inline void ThreePointddt(T &df, const T &f1, const T &f2, const T &f3, int bias)
105 // // a 3 point approximation pretends to have constant acceleration,
106 // // so only one algorithm needed for left, middle, or right
107 // df = (f1 -f2*2 + f3)*(1/2.0f);
110 // // WARNING -- totally broken
111 // template < class T >
112 // inline void FivePointddt(T &df, const T &f1, const T &f2, const T &f3, int bias)
118 // //df = (- f1 + f2*16 - f3*30 + f4*16 - f5)*(1/12.0f);
119 // }/*else if(bias < 0)
122 // df = (f1*7 - f2*26*4 + f3*19*6 - f4*14*4 + f5*11)*(1/12.0f);
126 // df = (f1*3 - f2*16 + f3*36 - f4*48 + f5*25)*(1/12.0f);
128 // //side ones don't work, use 3 point
131 // //implement an arbitrary derivative
133 // template < class T >
134 // void DerivativeApprox(T &df, const T f[], const Real t[], int npoints, int indexval)
137 // Lj(x) = PI_i!=j (x - xi) / PI_i!=j (xj - xi)
139 // so Lj'(x) = SUM_k PI_i!=j|k (x - xi) / PI_i!=j (xj - xi)
142 // unsigned int i,j,k,i0,i1;
144 // Real Lpj,mult,div,tj;
145 // Real tval = t[indexval];
148 // for(j=0;j<npoints;++j)
154 // for(k=0;k<npoints;++k)
156 // if(k != j) //because there is no summand for k == j, since that term is missing from the original equation
159 // for(i=0;i<npoints;++i)
163 // mult *= tval - t[i];
167 // Lpj += mult; //add into the summation
169 // //since the ks follow the exact pattern we need for the divisor (use that too)
174 // //get the actual coefficient
177 // //add it in to the equation
182 //END numerical derivatives
184 // template < class T >
185 // inline int sign(T f, T tol)
187 // if(f < -tol) return -1;
188 // if(f > tol) return 1;
192 void GetFirstDerivatives(const std::vector<synfig::Point> &f, unsigned int left, unsigned int right, char *out, unsigned int dfstride)
194 unsigned int current = left;
198 else if(right - left < 3)
200 synfig::Vector v = f[left+1] - f[left];
202 //set both to the one we want
203 *(synfig::Vector*)out = v;
205 *(synfig::Vector*)out = v;
208 else if(right - left < 6/*5*/) //should use 3 point
210 //left then middle then right
211 ThreePointdt(*(synfig::Vector*)out,f[left+0], f[left+1], f[left+2], -1);
215 for(;current < right-1; current++, out += dfstride)
217 ThreePointdt(*(synfig::Vector*)out,f[current-1], f[current], f[current+1], 0);
220 ThreePointdt(*(synfig::Vector*)out,f[right-3], f[right-2], f[right-1], 1);
224 }else //can use 5 point
226 //left 2 then middle bunch then right two
227 //may want to use 3 point for inner edge ones
229 FivePointdt(*(synfig::Vector*)out,f[left+0], f[left+1], f[left+2], f[left+3], f[left+4], -2);
231 FivePointdt(*(synfig::Vector*)out,f[left+1], f[left+2], f[left+3], f[left+4], f[left+5], -1);
235 for(;current < right-2; current++, out += dfstride)
237 FivePointdt(*(synfig::Vector*)out,f[current-2], f[current-1], f[current], f[current+1], f[current+2], 0);
240 FivePointdt(*(synfig::Vector*)out,f[right-5], f[right-4], f[right-3], f[right-2], f[right-1], 1);
242 FivePointdt(*(synfig::Vector*)out,f[right-6], f[right-5], f[right-4], f[right-3], f[right-2], 2);
248 void GetSimpleDerivatives(const std::vector<synfig::Point> &f, int left, int right,
249 std::vector<synfig::Point> &df, int outleft,
250 const std::vector<synfig::Real> &/*di*/)
253 int offset = 2; //df = 1/2 (f[i+o]-f[i-o])
255 assert((int)df.size() >= right-left+outleft); //must be big enough
257 for(i = left; i < right; ++i)
259 //right now indices (figure out distance later)
260 i1 = std::max(left,i-offset);
261 i2 = std::max(left,i+offset);
263 df[outleft++] = (f[i2] - f[i1])*0.5f;
267 //get the curve error from the double sample list of work points (hopefully that's enough)
268 Real CurveError(const synfig::Point *pts, unsigned int n, std::vector<synfig::Point> &work, int left, int right)
270 if(right-left < 2) return -1;
274 //get distances to each point
276 //synfig::Vector v,vt;
277 //synfig::Point p1,p2;
279 std::vector<synfig::Point>::const_iterator it;//,end = work.begin()+right;
281 //unsigned int size = work.size();
283 //for each line, get distance
285 for(i = 0; i < (int)n; ++i)
291 it = work.begin()+left;
292 //p2 = *it++; //put it at left+1
293 for(j = left/*+1*/; j < right; ++j,++it)
301 dtemp = v.mag_squared() > 1e-12 ? (vt*v)/v.mag_squared() : 0; //get the projected time value for the current line
303 //get distance to line segment with the time value clamped 0-1
304 if(dtemp >= 1) //use p+v
306 vt += v; //makes it pp - (p+v)
307 }else if(dtemp > 0) //use vt-proj
309 vt -= v*dtemp; // vt - proj_v(vt) //must normalize the projection vector to work
313 dtemp = vt.mag_squared();*/
315 dtemp = (pi - *it).mag_squared();
320 //accumulate the points' min distance from the curve
327 typedef synfigapp::BLineConverter::cpindex cpindex;
329 //has the index data and the tangent scale data (relevant as it may be)
330 int tessellate_curves(const std::vector<cpindex> &inds, const std::vector<Point> &f, const std::vector<synfig::Vector> &df, std::vector<Point> &work)
335 etl::hermite<Point> curve;
338 std::vector<cpindex>::const_iterator j = inds.begin(),j2, end = inds.end();
340 unsigned int ibase = inds[0].curind;
343 for(; j != end; j2 = j++)
345 //if this curve has invalid error (in j) then retessellate its work points (requires reparametrization, etc.)
348 //get the stepsize etc. for the number of points in here
349 unsigned int n = j->curind - j2->curind + 1; //thats the number of points in the span
350 unsigned int k, kend, i0, i3;
351 //so reset the right chunk
353 Real t, dt = 1/(Real)(n*2-2); //assuming that they own only n points
355 //start at first intermediate
358 i0 = j2->curind; i3 = j->curind;
359 k = (i0-ibase)*2; //start on first intermediary point (2x+1)
360 kend = (i3-ibase)*2; //last point to set (not intermediary)
362 //build hermite curve, it's easier
365 curve.t1() = df[i0-ibase] * (df[i0-ibase].mag_squared() > 1e-4
366 ? j2->tangentscale/df[i0-ibase].mag()
368 curve.t2() = df[i3-ibase] * (df[i3-ibase].mag_squared() > 1e-4
369 ? j->tangentscale/df[i3-ibase].mag()
373 //MUST include the end point (since we are ignoring left one)
374 for(; k < kend; ++k, t += dt)
379 work[k] = curve(1); //k == kend, t == 1 -> c(t) == p2
387 synfigapp::BLineConverter::BLineConverter()
395 synfigapp::BLineConverter::clear()
410 synfigapp::BLineConverter::operator () (std::list<synfig::BLinePoint> &out, const std::list<synfig::Point> &in,const std::list<synfig::Real> &in_w)
412 //Profiling information
413 /*etl::clock::value_type initialprocess=0, curveval=0, breakeval=0, disteval=0;
414 etl::clock::value_type preproceval=0, tesseval=0, erroreval=0, spliteval=0;
415 unsigned int numpre=0, numtess=0, numerror=0, numsplit=0;
416 etl::clock_realtime timer,total;*/
424 //removing digitization error harder than expected
426 //intended to fix little pen errors caused by the way people draw (tiny juts in opposite direction)
427 //Different solutions
428 // Average at both end points (will probably eliminate many points at each end of the samples)
429 // Average after the break points are found (weird points would still affect the curve)
430 // Just always get rid of breaks at the beginning and end if they are a certain distance apart
431 // This is will be current approach so all we do now is try to remove duplicate points
433 //remove duplicate points - very bad for fitting
438 std::list<synfig::Point>::const_iterator i = in.begin(), end = in.end();
439 std::list<synfig::Real>::const_iterator iw = in_w.begin();
442 if(in.size() == in_w.size())
444 for(;i != end; ++i,++iw)
446 //eliminate duplicate points
457 //eliminate duplicate points
465 //initialprocess = timer();
470 //get curvature information
475 synfig::Vector v1,v2;
477 cvt.resize(f.size());
482 for(i = 1; i < (int)f.size()-1; ++i)
484 i0 = std::max(0,i - 2);
485 i1 = std::min((int)(f.size()-1),i + 2);
490 cvt[i] = (v1*v2)/(v1.mag()*v2.mag());
494 //curveval = timer();
495 //synfig::info("calculated curvature");
497 //find corner points and interpolate inside those
500 //break at sharp derivative points
501 //TODO tolerance should be set based upon digitization resolution (length dependent index selection)
502 Real tol = 0; //break tolerance, for the cosine of the change in angle (really high curvature or something)
503 Real fixdistsq = 4*width*width; //the distance to ignore breaks at the end points (for fixing stuff)
506 int maxi = -1, last=0;
511 for(i = 1; i < cvt.size()-1; ++i)
513 //insert if too sharp (we need to break the tangents to insert onto the break list)
526 //synfig::info("break: %d-%d",maxi+1,cvt.size());
537 //postprocess for breaks too close to each other
539 Point p = f[brk.front()];
542 for(i = 1; i < brk.size()-1; ++i) //do not want to include end point...
544 d = (f[brk[i]] - p).mag_squared();
545 if(d > fixdistsq) break; //don't want to group breaks if we ever get over the dist...
547 //want to erase all points before...
549 brk.erase(brk.begin(),brk.begin()+i-1);
553 for(i = brk.size()-2; i > 0; --i) //start at one in from the end
555 d = (f[brk[i]] - p).mag_squared();
556 if(d > fixdistsq) break; //don't want to group breaks if we ever get over the dist
558 if(i != brk.size()-2)
559 brk.erase(brk.begin()+i+2,brk.end()); //erase all points that we found... found none if i has not advanced
560 //must not include the one we ended up on
562 //breakeval = timer();
563 //synfig::info("found break points: %d",brk.size());
565 //get the distance calculation of the entire curve (for tangent scaling)
573 di.resize(f.size()); d_i.resize(f.size());
575 for(unsigned int i = 0; i < f.size();)
577 d += (d_i[i] = (p2-p1).mag());
584 //disteval = timer();
585 //synfig::info("calculated distance");
587 //now break at every point - calculate new derivatives each time
590 //must be sure that the break points are 3 or more apart
591 //then must also store the breaks which are not smooth, etc.
592 //and figure out tangents between there
594 //for each pair of break points (as long as they are far enough apart) recursively subdivide stuff
595 //ignore the detected intermediate points
597 unsigned int i0=0,i3=0,is=0;
602 Real errortol = smoothness*pixelwidth; //???? what the hell should this value be
607 //intemp = f; //don't want to smooth out the corners
609 bool breaktan = false, setwidth;
610 a.set_split_tangent_flag(false);
611 //a.set_width(width);
614 setwidth = (f.size() == f_w.size());
616 for(j = 0; j < (int)brk.size() - 1; ++j)
618 //for b[j] to b[j+1] subdivide and stuff
622 unsigned int size = i3-i0+1; //must include the end points
626 ftemp.assign(f.begin()+i0, f.begin()+i3+1);
628 gaussian_blur_3(ftemp.begin(),ftemp.end(),false);
631 GetFirstDerivatives(ftemp,0,size,(char*)&df[0],sizeof(df[0]));
632 //GetSimpleDerivatives(ftemp,0,size,df,0,di);
633 //< don't have to worry about indexing stuff as it is all being taken car of right now
634 //preproceval += timer();
637 work.resize(size*2-1); //guarantee that all points will be tessellated correctly (one point in between every 2 adjacent points)
639 //if size of work is size*2-1, the step size should be 1/(size*2 - 2)
640 //Real step = 1/(Real)(size*2 - 1);
642 //start off with break points as indices
644 curind.push_back(cpindex(i0,di[i3]-di[i0],0)); //0 error because no curve on the left
645 curind.push_back(cpindex(i3,di[i3]-di[i0],-1)); //error needs to be reevaluated
646 done = false; //we want to loop
648 unsigned int dcount = 0;
650 //while there are still enough points between us, and the error is too high subdivide (and invalidate neighbors that share tangents)
653 //tessellate all curves with invalid error values
657 /*numtess += */tessellate_curves(curind,f,df,work);
658 //tesseval += timer();
660 //now get all error values
662 for(i = 1; i < (int)curind.size(); ++i)
664 if(curind[i].error < 0) //must have been retessellated, so now recalculate error value
666 //evaluate error from points (starting at current index)
667 int size = curind[i].curind - curind[i-1].curind + 1;
668 curind[i].error = CurveError(&f[curind[i-1].curind], size,
669 work,(curind[i-1].curind - i0)*2,(curind[i].curind - i0)*2+1);
671 /*if(curind[i].error > 1.0e5)
673 synfig::info("Holy crap %d-%d error %f",curind[i-1].curind,curind[i].curind,curind[i].error);
674 curind[i].error = -1;
675 numtess += tessellate_curves(curind,f,df,work);
676 curind[i].error = CurveError(&f[curind[i-1].curind], size,
677 work,0,work.size());//(curind[i-1].curind - i0)*2,(curind[i].curind - i0)*2+1);
682 //erroreval += timer();
687 //check each error to see if it's too big, if so, then subdivide etc.
688 int indsize = (int)curind.size();
689 Real maxrelerror = 0;
690 int maxi = -1;//, numpoints;
693 //get the maximum error and split there
694 for(i = 1; i < indsize; ++i)
696 //numpoints = curind[i].curind - curind[i-1].curind + 1;
698 if(curind[i].error > maxrelerror && curind[i].curind - curind[i-1].curind > 2) //only accept if it's valid
700 maxrelerror = curind[i].error;
705 //split if error is too great
706 if(maxrelerror > errortol)
708 //add one to the left etc
709 unsigned int ibase = curind[maxi-1].curind, itop = curind[maxi].curind,
710 ibreak = (ibase + itop)/2;
713 assert(ibreak < f.size());
715 //synfig::info("Split %d -%d- %d, error: %f", ibase,ibreak,itop,maxrelerror);
719 //invalidate current error of the changed tangents and add an extra segment
720 //enforce minimum tangents property
721 curind[maxi].error = -1;
722 curind[maxi-1].error = -1;
723 if(maxi+1 < indsize) curind[maxi+1].error = -1; //if there is a curve segment beyond this it will be effected as well
725 scale = di[itop] - di[ibreak];
726 scale2 = maxi+1 < indsize ? di[curind[maxi+1].curind] - di[itop] : scale; //to the right valid?
727 curind[maxi].tangentscale = std::min(scale, scale2);
729 scale = di[ibreak] - di[ibase];
730 scale2 = maxi >= 2 ? di[ibase] - di[curind[maxi-2].curind] : scale; // to the left valid -2 ?
731 curind[maxi-1].tangentscale = std::min(scale, scale2);
733 scale = std::min(di[ibreak] - di[ibase], di[itop] - di[ibreak]);
735 curind.insert(curind.begin()+maxi,cpindex(ibreak, scale, -1));
736 //curind.push_back(cpindex(ibreak, scale, -1));
737 //std::sort(curind.begin(), curind.end());
743 //spliteval += timer();
748 //insert the last point too (just set tangent for now
749 is = curind[0].curind;
751 //first point inherits current tangent status
753 if(v.mag_squared() > EPSILON)
754 v *= (curind[0].tangentscale/v.mag());
758 else a.set_tangent2(v);
761 if(setwidth)a.set_width(f_w[is]);
764 a.set_split_tangent_flag(false); //won't need to break anymore
767 for(i = 1; i < (int)curind.size()-1; ++i)
769 is = curind[i].curind;
771 //first point inherits current tangent status
773 if(v.mag_squared() > EPSILON)
774 v *= (curind[i].tangentscale/v.mag());
776 a.set_tangent(v); // always inside, so guaranteed to be smooth
778 if(setwidth)a.set_width(f_w[is]);
783 //set the last point's data
784 is = curind.back().curind; //should already be this
787 if(v.mag_squared() > EPSILON)
788 v *= (curind.back().tangentscale/v.mag());
791 a.set_split_tangent_flag(true);
794 //will get the vertex and tangent 2 from next round
798 a.set_split_tangent_flag(false);
800 a.set_width(f_w[i3]);
803 /*etl::clock::value_type totaltime = total(),
804 misctime = totaltime - initialprocess - curveval - breakeval - disteval
805 - preproceval - tesseval - erroreval - spliteval;
808 "Curve Convert Profile:\n"
809 "\tInitial Preprocess: %f\n"
810 "\tCurvature Calculation: %f\n"
811 "\tBreak Calculation: %f\n"
812 "\tDistance Calculation: %f\n"
813 " Algorithm: (numtimes,totaltime)\n"
814 "\tPreprocess step: (%d,%f)\n"
815 "\tTessellation step: (%d,%f)\n"
816 "\tError step: (%d,%f)\n"
817 "\tSplit step: (%d,%f)\n"
818 " Num Input: %d, Num Output: %d\n"
819 " Total time: %f, Misc time: %f\n",
820 initialprocess, curveval,breakeval,disteval,
821 numpre,preproceval,numtess,tesseval,numerror,erroreval,numsplit,spliteval,
822 in.size(),out.size(),
823 totaltime,misctime);*/
829 void synfigapp::BLineConverter::EnforceMinWidth(std::list<synfig::BLinePoint> &bline, synfig::Real min_pressure)
831 std::list<synfig::BLinePoint>::iterator i = bline.begin(),
834 for(i = bline.begin(); i != end; ++i)
836 if(i->get_width() < min_pressure)
838 i->set_width(min_pressure);