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);
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, so only one algorithm needed for left, middle, or right
106 df = (f1 -f2*2 + f3)*(1/2.0f);
109 // WARNING -- totally broken
111 inline void FivePointddt(T &df, const T &f1, const T &f2, const T &f3, int bias)
117 //df = (- f1 + f2*16 - f3*30 + f4*16 - f5)*(1/12.0f);
121 df = (f1*7 - f2*26*4 + f3*19*6 - f4*14*4 + f5*11)*(1/12.0f);
125 df = (f1*3 - f2*16 + f3*36 - f4*48 + f5*25)*(1/12.0f);
127 //side ones don't work, use 3 point
130 //implement an arbitrary derivative
133 void DerivativeApprox(T &df, const T f[], const Real t[], int npoints, int indexval)
136 Lj(x) = PI_i!=j (x - xi) / PI_i!=j (xj - xi)
138 so Lj'(x) = SUM_k PI_i!=j|k (x - xi) / PI_i!=j (xj - xi)
141 unsigned int i,j,k,i0,i1;
143 Real Lpj,mult,div,tj;
144 Real tval = t[indexval];
147 for(j=0;j<npoints;++j)
153 for(k=0;k<npoints;++k)
155 if(k != j) //because there is no summand for k == j, since that term is missing from the original equation
158 for(i=0;i<npoints;++i)
166 Lpj += mult; //add into the summation
168 //since the ks follow the exact pattern we need for the divisor (use that too)
173 //get the actual coefficient
176 //add it in to the equation
181 //END numerical derivatives
184 inline int sign(T f, T tol)
186 if(f < -tol) return -1;
187 if(f > tol) return 1;
191 void GetFirstDerivatives(const std::vector<synfig::Point> &f, unsigned int left, unsigned int right, char *out, unsigned int dfstride)
193 unsigned int current = left;
197 else if(right - left < 3)
199 synfig::Vector v = f[left+1] - f[left];
201 //set both to the one we want
202 *(synfig::Vector*)out = v;
204 *(synfig::Vector*)out = v;
207 else if(right - left < 6/*5*/) //should use 3 point
209 //left then middle then right
210 ThreePointdt(*(synfig::Vector*)out,f[left+0], f[left+1], f[left+2], -1);
214 for(;current < right-1; current++, out += dfstride)
216 ThreePointdt(*(synfig::Vector*)out,f[current-1], f[current], f[current+1], 0);
219 ThreePointdt(*(synfig::Vector*)out,f[right-3], f[right-2], f[right-1], 1);
223 }else //can use 5 point
225 //left 2 then middle bunch then right two
226 //may want to use 3 point for inner edge ones
228 FivePointdt(*(synfig::Vector*)out,f[left+0], f[left+1], f[left+2], f[left+3], f[left+4], -2);
230 FivePointdt(*(synfig::Vector*)out,f[left+1], f[left+2], f[left+3], f[left+4], f[left+5], -1);
234 for(;current < right-2; current++, out += dfstride)
236 FivePointdt(*(synfig::Vector*)out,f[current-2], f[current-1], f[current], f[current+1], f[current+2], 0);
239 FivePointdt(*(synfig::Vector*)out,f[right-5], f[right-4], f[right-3], f[right-2], f[right-1], 1);
241 FivePointdt(*(synfig::Vector*)out,f[right-6], f[right-5], f[right-4], f[right-3], f[right-2], 2);
247 void GetSimpleDerivatives(const std::vector<synfig::Point> &f, int left, int right,
248 std::vector<synfig::Point> &df, int outleft,
249 const std::vector<synfig::Real> &/*di*/)
252 int offset = 2; //df = 1/2 (f[i+o]-f[i-o])
254 assert((int)df.size() >= right-left+outleft); //must be big enough
256 for(i = left; i < right; ++i)
258 //right now indices (figure out distance later)
259 i1 = std::max(left,i-offset);
260 i2 = std::max(left,i+offset);
262 df[outleft++] = (f[i2] - f[i1])*0.5f;
266 //get the curve error from the double sample list of work points (hopefully that's enough)
267 Real CurveError(const synfig::Point *pts, unsigned int n, std::vector<synfig::Point> &work, int left, int right)
269 if(right-left < 2) return -1;
273 //get distances to each point
275 //synfig::Vector v,vt;
276 //synfig::Point p1,p2;
278 std::vector<synfig::Point>::const_iterator it;//,end = work.begin()+right;
280 //unsigned int size = work.size();
282 //for each line, get distance
284 for(i = 0; i < (int)n; ++i)
290 it = work.begin()+left;
291 //p2 = *it++; //put it at left+1
292 for(j = left/*+1*/; j < right; ++j,++it)
300 dtemp = v.mag_squared() > 1e-12 ? (vt*v)/v.mag_squared() : 0; //get the projected time value for the current line
302 //get distance to line segment with the time value clamped 0-1
303 if(dtemp >= 1) //use p+v
305 vt += v; //makes it pp - (p+v)
306 }else if(dtemp > 0) //use vt-proj
308 vt -= v*dtemp; // vt - proj_v(vt) //must normalize the projection vector to work
312 dtemp = vt.mag_squared();*/
314 dtemp = (pi - *it).mag_squared();
319 //accumulate the points' min distance from the curve
326 typedef synfigapp::BLineConverter::cpindex cpindex;
328 //has the index data and the tangent scale data (relevant as it may be)
329 int tessellate_curves(const std::vector<cpindex> &inds, const std::vector<Point> &f, const std::vector<synfig::Vector> &df, std::vector<Point> &work)
334 etl::hermite<Point> curve;
337 std::vector<cpindex>::const_iterator j = inds.begin(),j2, end = inds.end();
339 unsigned int ibase = inds[0].curind;
342 for(; j != end; j2 = j++)
344 //if this curve has invalid error (in j) then retessellate its work points (requires reparametrization, etc.)
347 //get the stepsize etc. for the number of points in here
348 unsigned int n = j->curind - j2->curind + 1; //thats the number of points in the span
349 unsigned int k, kend, i0, i3;
350 //so reset the right chunk
352 Real t, dt = 1/(Real)(n*2-2); //assuming that they own only n points
354 //start at first intermediate
357 i0 = j2->curind; i3 = j->curind;
358 k = (i0-ibase)*2; //start on first intermediary point (2x+1)
359 kend = (i3-ibase)*2; //last point to set (not intermediary)
361 //build hermite curve, it's easier
364 curve.t1() = df[i0-ibase] * (df[i0-ibase].mag_squared() > 1e-4
365 ? j2->tangentscale/df[i0-ibase].mag()
367 curve.t2() = df[i3-ibase] * (df[i3-ibase].mag_squared() > 1e-4
368 ? j->tangentscale/df[i3-ibase].mag()
372 //MUST include the end point (since we are ignoring left one)
373 for(; k < kend; ++k, t += dt)
378 work[k] = curve(1); //k == kend, t == 1 -> c(t) == p2
386 synfigapp::BLineConverter::BLineConverter()
394 synfigapp::BLineConverter::clear()
409 synfigapp::BLineConverter::operator () (std::list<synfig::BLinePoint> &out, const std::list<synfig::Point> &in,const std::list<synfig::Real> &in_w)
411 //Profiling information
412 /*etl::clock::value_type initialprocess=0, curveval=0, breakeval=0, disteval=0;
413 etl::clock::value_type preproceval=0, tesseval=0, erroreval=0, spliteval=0;
414 unsigned int numpre=0, numtess=0, numerror=0, numsplit=0;
415 etl::clock_realtime timer,total;*/
423 //removing digitization error harder than expected
425 //intended to fix little pen errors caused by the way people draw (tiny juts in opposite direction)
426 //Different solutions
427 // Average at both end points (will probably eliminate many points at each end of the samples)
428 // Average after the break points are found (weird points would still affect the curve)
429 // Just always get rid of breaks at the beginning and end if they are a certain distance apart
430 // This is will be current approach so all we do now is try to remove duplicate points
432 //remove duplicate points - very bad for fitting
437 std::list<synfig::Point>::const_iterator i = in.begin(), end = in.end();
438 std::list<synfig::Real>::const_iterator iw = in_w.begin();
441 if(in.size() == in_w.size())
443 for(;i != end; ++i,++iw)
445 //eliminate duplicate points
456 //eliminate duplicate points
464 //initialprocess = timer();
469 //get curvature information
474 synfig::Vector v1,v2;
476 cvt.resize(f.size());
481 for(i = 1; i < (int)f.size()-1; ++i)
483 i0 = std::max(0,i - 2);
484 i1 = std::min((int)(f.size()-1),i + 2);
489 cvt[i] = (v1*v2)/(v1.mag()*v2.mag());
493 //curveval = timer();
494 //synfig::info("calculated curvature");
496 //find corner points and interpolate inside those
499 //break at sharp derivative points
500 //TODO tolerance should be set based upon digitization resolution (length dependent index selection)
501 Real tol = 0; //break tolerance, for the cosine of the change in angle (really high curvature or something)
502 Real fixdistsq = 4*width*width; //the distance to ignore breaks at the end points (for fixing stuff)
505 int maxi = -1, last=0;
510 for(i = 1; i < cvt.size()-1; ++i)
512 //insert if too sharp (we need to break the tangents to insert onto the break list)
525 //synfig::info("break: %d-%d",maxi+1,cvt.size());
536 //postprocess for breaks too close to each other
538 Point p = f[brk.front()];
541 for(i = 1; i < brk.size()-1; ++i) //do not want to include end point...
543 d = (f[brk[i]] - p).mag_squared();
544 if(d > fixdistsq) break; //don't want to group breaks if we ever get over the dist...
546 //want to erase all points before...
548 brk.erase(brk.begin(),brk.begin()+i-1);
552 for(i = brk.size()-2; i > 0; --i) //start at one in from the end
554 d = (f[brk[i]] - p).mag_squared();
555 if(d > fixdistsq) break; //don't want to group breaks if we ever get over the dist
557 if(i != brk.size()-2)
558 brk.erase(brk.begin()+i+2,brk.end()); //erase all points that we found... found none if i has not advanced
559 //must not include the one we ended up on
561 //breakeval = timer();
562 //synfig::info("found break points: %d",brk.size());
564 //get the distance calculation of the entire curve (for tangent scaling)
572 di.resize(f.size()); d_i.resize(f.size());
574 for(unsigned int i = 0; i < f.size();)
576 d += (d_i[i] = (p2-p1).mag());
583 //disteval = timer();
584 //synfig::info("calculated distance");
586 //now break at every point - calculate new derivatives each time
589 //must be sure that the break points are 3 or more apart
590 //then must also store the breaks which are not smooth, etc.
591 //and figure out tangents between there
593 //for each pair of break points (as long as they are far enough apart) recursively subdivide stuff
594 //ignore the detected intermediate points
596 unsigned int i0=0,i3=0,is=0;
601 Real errortol = smoothness*pixelwidth; //???? what the hell should this value be
606 //intemp = f; //don't want to smooth out the corners
608 bool breaktan = false, setwidth;
609 a.set_split_tangent_flag(false);
610 //a.set_width(width);
613 setwidth = (f.size() == f_w.size());
615 for(j = 0; j < (int)brk.size() - 1; ++j)
617 //for b[j] to b[j+1] subdivide and stuff
621 unsigned int size = i3-i0+1; //must include the end points
625 ftemp.assign(f.begin()+i0, f.begin()+i3+1);
627 gaussian_blur_3(ftemp.begin(),ftemp.end(),false);
630 GetFirstDerivatives(ftemp,0,size,(char*)&df[0],sizeof(df[0]));
631 //GetSimpleDerivatives(ftemp,0,size,df,0,di);
632 //< don't have to worry about indexing stuff as it is all being taken car of right now
633 //preproceval += timer();
636 work.resize(size*2-1); //guarantee that all points will be tessellated correctly (one point in between every 2 adjacent points)
638 //if size of work is size*2-1, the step size should be 1/(size*2 - 2)
639 //Real step = 1/(Real)(size*2 - 1);
641 //start off with break points as indices
643 curind.push_back(cpindex(i0,di[i3]-di[i0],0)); //0 error because no curve on the left
644 curind.push_back(cpindex(i3,di[i3]-di[i0],-1)); //error needs to be reevaluated
645 done = false; //we want to loop
647 unsigned int dcount = 0;
649 //while there are still enough points between us, and the error is too high subdivide (and invalidate neighbors that share tangents)
652 //tessellate all curves with invalid error values
656 /*numtess += */tessellate_curves(curind,f,df,work);
657 //tesseval += timer();
659 //now get all error values
661 for(i = 1; i < (int)curind.size(); ++i)
663 if(curind[i].error < 0) //must have been retessellated, so now recalculate error value
665 //evaluate error from points (starting at current index)
666 int size = curind[i].curind - curind[i-1].curind + 1;
667 curind[i].error = CurveError(&f[curind[i-1].curind], size,
668 work,(curind[i-1].curind - i0)*2,(curind[i].curind - i0)*2+1);
670 /*if(curind[i].error > 1.0e5)
672 synfig::info("Holy crap %d-%d error %f",curind[i-1].curind,curind[i].curind,curind[i].error);
673 curind[i].error = -1;
674 numtess += tessellate_curves(curind,f,df,work);
675 curind[i].error = CurveError(&f[curind[i-1].curind], size,
676 work,0,work.size());//(curind[i-1].curind - i0)*2,(curind[i].curind - i0)*2+1);
681 //erroreval += timer();
686 //check each error to see if it's too big, if so, then subdivide etc.
687 int indsize = (int)curind.size();
688 Real maxrelerror = 0;
689 int maxi = -1;//, numpoints;
692 //get the maximum error and split there
693 for(i = 1; i < indsize; ++i)
695 //numpoints = curind[i].curind - curind[i-1].curind + 1;
697 if(curind[i].error > maxrelerror && curind[i].curind - curind[i-1].curind > 2) //only accept if it's valid
699 maxrelerror = curind[i].error;
704 //split if error is too great
705 if(maxrelerror > errortol)
707 //add one to the left etc
708 unsigned int ibase = curind[maxi-1].curind, itop = curind[maxi].curind,
709 ibreak = (ibase + itop)/2;
712 assert(ibreak < f.size());
714 //synfig::info("Split %d -%d- %d, error: %f", ibase,ibreak,itop,maxrelerror);
718 //invalidate current error of the changed tangents and add an extra segment
719 //enforce minimum tangents property
720 curind[maxi].error = -1;
721 curind[maxi-1].error = -1;
722 if(maxi+1 < indsize) curind[maxi+1].error = -1; //if there is a curve segment beyond this it will be effected as well
724 scale = di[itop] - di[ibreak];
725 scale2 = maxi+1 < indsize ? di[curind[maxi+1].curind] - di[itop] : scale; //to the right valid?
726 curind[maxi].tangentscale = std::min(scale, scale2);
728 scale = di[ibreak] - di[ibase];
729 scale2 = maxi >= 2 ? di[ibase] - di[curind[maxi-2].curind] : scale; // to the left valid -2 ?
730 curind[maxi-1].tangentscale = std::min(scale, scale2);
732 scale = std::min(di[ibreak] - di[ibase], di[itop] - di[ibreak]);
734 curind.insert(curind.begin()+maxi,cpindex(ibreak, scale, -1));
735 //curind.push_back(cpindex(ibreak, scale, -1));
736 //std::sort(curind.begin(), curind.end());
742 //spliteval += timer();
747 //insert the last point too (just set tangent for now
748 is = curind[0].curind;
750 //first point inherits current tangent status
752 if(v.mag_squared() > EPSILON)
753 v *= (curind[0].tangentscale/v.mag());
757 else a.set_tangent2(v);
760 if(setwidth)a.set_width(f_w[is]);
763 a.set_split_tangent_flag(false); //won't need to break anymore
766 for(i = 1; i < (int)curind.size()-1; ++i)
768 is = curind[i].curind;
770 //first point inherits current tangent status
772 if(v.mag_squared() > EPSILON)
773 v *= (curind[i].tangentscale/v.mag());
775 a.set_tangent(v); // always inside, so guaranteed to be smooth
777 if(setwidth)a.set_width(f_w[is]);
782 //set the last point's data
783 is = curind.back().curind; //should already be this
786 if(v.mag_squared() > EPSILON)
787 v *= (curind.back().tangentscale/v.mag());
790 a.set_split_tangent_flag(true);
793 //will get the vertex and tangent 2 from next round
797 a.set_split_tangent_flag(false);
799 a.set_width(f_w[i3]);
802 /*etl::clock::value_type totaltime = total(),
803 misctime = totaltime - initialprocess - curveval - breakeval - disteval
804 - preproceval - tesseval - erroreval - spliteval;
807 "Curve Convert Profile:\n"
808 "\tInitial Preprocess: %f\n"
809 "\tCurvature Calculation: %f\n"
810 "\tBreak Calculation: %f\n"
811 "\tDistance Calculation: %f\n"
812 " Algorithm: (numtimes,totaltime)\n"
813 "\tPreprocess step: (%d,%f)\n"
814 "\tTessellation step: (%d,%f)\n"
815 "\tError step: (%d,%f)\n"
816 "\tSplit step: (%d,%f)\n"
817 " Num Input: %d, Num Output: %d\n"
818 " Total time: %f, Misc time: %f\n",
819 initialprocess, curveval,breakeval,disteval,
820 numpre,preproceval,numtess,tesseval,numerror,erroreval,numsplit,spliteval,
821 in.size(),out.size(),
822 totaltime,misctime);*/
828 void synfigapp::BLineConverter::EnforceMinWidth(std::list<synfig::BLinePoint> &bline, synfig::Real min_pressure)
830 std::list<synfig::BLinePoint>::iterator i = bline.begin(),
833 for(i = bline.begin(); i != end; ++i)
835 if(i->get_width() < min_pressure)
837 i->set_width(min_pressure);