1 /* === S Y N F I G ========================================================= */
2 /*! \file blineconvert.cpp
3 ** \brief Template File
5 ** $Id: blineconvert.cpp,v 1.1.1.1 2005/01/07 03:34:37 darco Exp $
8 ** Copyright (c) 2002 Robert B. Quattlebaum Jr.
10 ** This software and associated documentation
11 ** are CONFIDENTIAL and PROPRIETARY property of
12 ** the above-mentioned copyright holder.
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.
20 /* ========================================================================= */
22 /* === H E A D E R S ======================================================= */
31 #include "blineconvert.h"
33 #include <ETL/gaussian>
34 #include <ETL/hermite>
38 #include <synfig/general.h>
45 /* === U S I N G =========================================================== */
49 using namespace synfig;
51 /* === M A C R O S ========================================================= */
53 #define EPSILON (1e-10)
55 /* === G L O B A L S ======================================================= */
57 /* === P R O C E D U R E S ================================================= */
59 /* === M E T H O D S ======================================================= */
62 //Derivative Functions for numerical approximation
64 //bias == 0 will get F' at f3, bias < 0 will get F' at f1, and bias > 0 will get F' at f5
66 inline void FivePointdt(T &df, const T &f1, const T &f2, const T &f3, const T &f4, const T &f5, int bias)
71 df = (f1 - f2*8 + f4*8 - f5)*(1/12.0f);
75 df = (-f1*25 + f2*48 - f3*36 + f4*16 - f5*3)*(1/12.0f);
79 df = (f1*3 - f2*16 + f3*36 - f4*48 + f5*25)*(1/12.0f);
84 inline void ThreePointdt(T &df, const T &f1, const T &f2, const T &f3, int bias)
89 df = (-f1 + f3)*(1/2.0f);
93 df = (-f1*3 + f2*4 - f3)*(1/2.0f);
97 df = (f1 - f2*4 + f3*3)*(1/2.0f);
102 inline void ThreePointddt(T &df, const T &f1, const T &f2, const T &f3, int bias)
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);
108 // WARNING -- totaly broken
110 inline void FivePointddt(T &df, const T &f1, const T &f2, const T &f3, int bias)
116 //df = (- f1 + f2*16 - f3*30 + f4*16 - f5)*(1/12.0f);
120 df = (f1*7 - f2*26*4 + f3*19*6 - f4*14*4 + f5*11)*(1/12.0f);
124 df = (f1*3 - f2*16 + f3*36 - f4*48 + f5*25)*(1/12.0f);
126 //side ones don't work, use 3 point
129 //implement an arbitrary derivative
132 void DerivativeApprox(T &df, const T f[], const Real t[], int npoints, int indexval)
135 Lj(x) = PI_i!=j (x - xi) / PI_i!=j (xj - xi)
137 so Lj'(x) = SUM_k PI_i!=j|k (x - xi) / PI_i!=j (xj - xi)
140 unsigned int i,j,k,i0,i1;
142 Real Lpj,mult,div,tj;
143 Real tval = t[indexval];
146 for(j=0;j<npoints;++j)
152 for(k=0;k<npoints;++k)
154 if(k != j) //because there is no summand for k == j, since that term is missing from the original equation
157 for(i=0;i<npoints;++i)
165 Lpj += mult; //add into the summation
167 //since the ks follow the exact patern we need for the divisor (use that too)
172 //get the actual coefficient
175 //add it in to the equation
180 //END numerical derivatives
183 inline int sign(T f, T tol)
185 if(f < -tol) return -1;
186 if(f > tol) return 1;
190 void GetFirstDerivatives(const std::vector<synfig::Point> &f, unsigned int left, unsigned int right, char *out, unsigned int dfstride)
192 unsigned int current = left;
196 else if(right - left < 3)
198 synfig::Vector v = f[left+1] - f[left];
200 //set both to the one we want
201 *(synfig::Vector*)out = v;
203 *(synfig::Vector*)out = v;
206 else if(right - left < 6/*5*/) //should use 3 point
208 //left then middle then right
209 ThreePointdt(*(synfig::Vector*)out,f[left+0], f[left+1], f[left+2], -1);
213 for(;current < right-1; current++, out += dfstride)
215 ThreePointdt(*(synfig::Vector*)out,f[current-1], f[current], f[current+1], 0);
218 ThreePointdt(*(synfig::Vector*)out,f[right-3], f[right-2], f[right-1], 1);
222 }else //can use 5 point
224 //left 2 then middle bunch then right two
225 //may want to use 3 point for inner edge ones
227 FivePointdt(*(synfig::Vector*)out,f[left+0], f[left+1], f[left+2], f[left+3], f[left+4], -2);
229 FivePointdt(*(synfig::Vector*)out,f[left+1], f[left+2], f[left+3], f[left+4], f[left+5], -1);
233 for(;current < right-2; current++, out += dfstride)
235 FivePointdt(*(synfig::Vector*)out,f[current-2], f[current-1], f[current], f[current+1], f[current+2], 0);
238 FivePointdt(*(synfig::Vector*)out,f[right-5], f[right-4], f[right-3], f[right-2], f[right-1], 1);
240 FivePointdt(*(synfig::Vector*)out,f[right-6], f[right-5], f[right-4], f[right-3], f[right-2], 2);
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)
251 int offset = 2; //df = 1/2 (f[i+o]-f[i-o])
253 assert((int)df.size() >= right-left+outleft); //must be big enough
255 for(i = left; i < right; ++i)
257 //right now indices (figure out distance later)
258 i1 = std::max(left,i-offset);
259 i2 = std::max(left,i+offset);
261 df[outleft++] = (f[i2] - f[i1])*0.5f;
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)
268 if(right-left < 2) return -1;
272 //get distances to each point
274 //synfig::Vector v,vt;
275 //synfig::Point p1,p2;
277 std::vector<synfig::Point>::const_iterator it;//,end = work.begin()+right;
279 //unsigned int size = work.size();
281 //for each line, get distance
283 for(i = 0; i < (int)n; ++i)
289 it = work.begin()+left;
290 //p2 = *it++; //put it at left+1
291 for(j = left/*+1*/; j < right; ++j,++it)
299 dtemp = v.mag_squared() > 1e-12 ? (vt*v)/v.mag_squared() : 0; //get the projected time value for the current line
301 //get distance to line segment with the time value clamped 0-1
302 if(dtemp >= 1) //use p+v
304 vt += v; //makes it pp - (p+v)
305 }else if(dtemp > 0) //use vt-proj
307 vt -= v*dtemp; // vt - proj_v(vt) //must normalize the projection vector to work
311 dtemp = vt.mag_squared();*/
313 dtemp = (pi - *it).mag_squared();
318 //accumulate the points' min distance from the curve
325 typedef synfigapp::BLineConverter::cpindex cpindex;
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)
333 etl::hermite<Point> curve;
336 std::vector<cpindex>::const_iterator j = inds.begin(),j2, end = inds.end();
338 unsigned int ibase = inds[0].curind;
341 for(; j != end; j2 = j++)
343 //if this curve has invalid error (in j) then retesselate it's work points (requires reparametrization, etc.)
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
351 Real t, dt = 1/(Real)(n*2-2); //assuming that they own only n points
353 //start at first intermediate
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)
360 //build hermite curve, it's easier
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);
367 //MUST include the end point (since we are ignoring left one)
368 for(; k < kend; ++k, t += dt)
373 work[k] = curve(1); //k == kend, t == 1 -> c(t) == p2
381 synfigapp::BLineConverter::BLineConverter()
389 synfigapp::BLineConverter::clear()
404 synfigapp::BLineConverter::operator () (std::list<synfig::BLinePoint> &out, const std::list<synfig::Point> &in,const std::list<synfig::Real> &in_w)
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;*/
418 //removing digitization error harder than expected
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
427 //remove duplicate points - very bad for fitting
432 std::list<synfig::Point>::const_iterator i = in.begin(), end = in.end();
433 std::list<synfig::Real>::const_iterator iw = in_w.begin();
436 if(in.size() == in_w.size())
438 for(;i != end; ++i,++iw)
440 //eliminate duplicate points
451 //eliminate duplicate points
459 //initialprocess = timer();
464 //get curvature information
469 synfig::Vector v1,v2;
471 cvt.resize(f.size());
476 for(i = 1; i < (int)f.size()-1; ++i)
478 i0 = std::max(0,i - 2);
479 i1 = std::min((int)(f.size()-1),i + 2);
484 cvt[i] = (v1*v2)/(v1.mag()*v2.mag());
488 //curveval = timer();
489 //synfig::info("calculated curvature");
491 //find corner points and interpolate inside those
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)
500 int maxi = -1, last=0;
505 for(i = 1; i < cvt.size()-1; ++i)
507 //insert if too sharp (we need to break the tangents to insert onto the break list)
520 //synfig::info("break: %d-%d",maxi+1,cvt.size());
531 //postprocess for breaks too close to eachother
533 Point p = f[brk.front()];
536 for(i = 1; i < brk.size()-1; ++i) //do not want to include end point...
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...
541 //want to erase all points before...
543 brk.erase(brk.begin(),brk.begin()+i-1);
547 for(i = brk.size()-2; i > 0; --i) //start at one in from the end
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
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
556 //breakeval = timer();
557 //synfig::info("found break points: %d",brk.size());
559 //get the distance calculation of the entire curve (for tangent scaling)
567 di.resize(f.size()); d_i.resize(f.size());
569 for(unsigned int i = 0; i < f.size();)
571 d += (d_i[i] = (p2-p1).mag());
578 //disteval = timer();
579 //synfig::info("calculated distance");
581 //now break at every point - calculate new derivatives each time
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
588 //for each pair of break points (as long as they are far enough apart) recursively subdivide stuff
589 //ignore the detected intermediate points
591 unsigned int i0=0,i3=0,is=0;
596 Real errortol = smoothness*pixelwidth; //???? what the hell should this value be
601 //intemp = f; //don't want to smooth out the corners
603 bool breaktan = false, setwidth;
604 a.set_split_tangent_flag(false);
605 //a.set_width(width);
608 setwidth = (f.size() == f_w.size());
610 for(j = 0; j < (int)brk.size() - 1; ++j)
612 //for b[j] to b[j+1] subdivide and stuff
616 unsigned int size = i3-i0+1; //must include the end points
620 ftemp.assign(f.begin()+i0, f.begin()+i3+1);
622 gaussian_blur_3(ftemp.begin(),ftemp.end(),false);
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();
631 work.resize(size*2-1); //guarantee that all points will be tesselated correctly (one point inbetween every 2 adjacent points)
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);
636 //start off with break points as indices
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
642 unsigned int dcount = 0;
644 //while there are still enough points between us, and the error is too high subdivide (and invalidate neighbors that share tangents)
647 //tesselate all curves with invalid error values
651 /*numtess += */tesselate_curves(curind,f,df,work);
652 //tesseval += timer();
654 //now get all error values
656 for(i = 1; i < (int)curind.size(); ++i)
658 if(curind[i].error < 0) //must have been retesselated, so now recalculate error value
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);
665 /*if(curind[i].error > 1.0e5)
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);
676 //erroreval += timer();
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;
687 //get the maximum error and split there
688 for(i = 1; i < indsize; ++i)
690 //numpoints = curind[i].curind - curind[i-1].curind + 1;
692 if(curind[i].error > maxrelerror && curind[i].curind - curind[i-1].curind > 2) //only accept if it's valid
694 maxrelerror = curind[i].error;
699 //split if error is too great
700 if(maxrelerror > errortol)
702 //add one to the left etc
703 unsigned int ibase = curind[maxi-1].curind, itop = curind[maxi].curind,
704 ibreak = (ibase + itop)/2;
707 assert(ibreak < f.size());
709 //synfig::info("Split %d -%d- %d, error: %f", ibase,ibreak,itop,maxrelerror);
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
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);
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);
727 scale = std::min(di[ibreak] - di[ibase], di[itop] - di[ibreak]);
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());
737 //spliteval += timer();
742 //insert the last point too (just set tangent for now
743 is = curind[0].curind;
745 //first point inherits current tangent status
747 if(v.mag_squared() > EPSILON)
748 v *= (curind[0].tangentscale/v.mag());
752 else a.set_tangent2(v);
755 if(setwidth)a.set_width(f_w[is]);
758 a.set_split_tangent_flag(false); //won't need to break anymore
761 for(i = 1; i < (int)curind.size()-1; ++i)
763 is = curind[i].curind;
765 //first point inherits current tangent status
767 if(v.mag_squared() > EPSILON)
768 v *= (curind[i].tangentscale/v.mag());
770 a.set_tangent(v); // always inside, so guaranteed to be smooth
772 if(setwidth)a.set_width(f_w[is]);
777 //set the last point's data
778 is = curind.back().curind; //should already be this
781 if(v.mag_squared() > EPSILON)
782 v *= (curind.back().tangentscale/v.mag());
785 a.set_split_tangent_flag(true);
788 //will get the vertex and tangent 2 from next round
792 a.set_split_tangent_flag(false);
794 a.set_width(f_w[i3]);
797 /*etl::clock::value_type totaltime = total(),
798 misctime = totaltime - initialprocess - curveval - breakeval - disteval
799 - preproceval - tesseval - erroreval - spliteval;
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);*/
823 void synfigapp::BLineConverter::EnforceMinWidth(std::list<synfig::BLinePoint> &bline, synfig::Real min_pressure)
825 std::list<synfig::BLinePoint>::iterator i = bline.begin(),
828 for(i = bline.begin(); i != end; ++i)
830 if(i->get_width() < min_pressure)
832 i->set_width(min_pressure);