X-Git-Url: https://git.pterodactylus.net/?a=blobdiff_plain;f=synfig-studio%2Ftrunk%2Fsrc%2Fsynfigapp%2Fblineconvert.cpp;h=42cb57a369511a8bef21b59b39347ae2fa9433c4;hb=4ba22fb51d97f1ecce04dcc5e40569a4354c1bae;hp=ec69a2e4750935d5e596b6f6a96dfea959493817;hpb=e68d9f9f75956ecfee805a674f139033ded6bec6;p=synfig.git diff --git a/synfig-studio/trunk/src/synfigapp/blineconvert.cpp b/synfig-studio/trunk/src/synfigapp/blineconvert.cpp index ec69a2e..42cb57a 100644 --- a/synfig-studio/trunk/src/synfigapp/blineconvert.cpp +++ b/synfig-studio/trunk/src/synfigapp/blineconvert.cpp @@ -6,6 +6,7 @@ ** ** \legal ** Copyright (c) 2002-2005 Robert B. Quattlebaum Jr., Adrian Bentley +** Copyright (c) 2007 Chris Moore ** ** This package is free software; you can redistribute it and/or ** modify it under the terms of the GNU General Public License as @@ -39,7 +40,7 @@ #include #include - +#include "general.h" #endif @@ -66,37 +67,23 @@ using namespace synfig; template < class T > inline void FivePointdt(T &df, const T &f1, const T &f2, const T &f3, const T &f4, const T &f5, int bias) { - if(bias == 0) - { - //middle + if (bias == 0) // middle df = (f1 - f2*8 + f4*8 - f5)*(1/12.0f); - }else if(bias < 0) - { - //left + else if (bias < 0) // left df = (-f1*25 + f2*48 - f3*36 + f4*16 - f5*3)*(1/12.0f); - }else - { - //right + else // right df = (f1*3 - f2*16 + f3*36 - f4*48 + f5*25)*(1/12.0f); - } } template < class T > inline void ThreePointdt(T &df, const T &f1, const T &f2, const T &f3, int bias) { - if(bias == 0) - { - //middle + if (bias == 0) // middle df = (-f1 + f3)*(1/2.0f); - }else if(bias < 0) - { - //left + else if (bias < 0) // left df = (-f1*3 + f2*4 - f3)*(1/2.0f); - }else - { - //right + else // right df = (f1 - f2*4 + f3*3)*(1/2.0f); - } } // template < class T > @@ -106,7 +93,7 @@ inline void ThreePointdt(T &df, const T &f1, const T &f2, const T &f3, int bias) // // so only one algorithm needed for left, middle, or right // df = (f1 -f2*2 + f3)*(1/2.0f); // } -// +// // // WARNING -- totally broken // template < class T > // inline void FivePointddt(T &df, const T &f1, const T &f2, const T &f3, int bias) @@ -127,7 +114,7 @@ inline void ThreePointdt(T &df, const T &f1, const T &f2, const T &f3, int bias) // }*/ // //side ones don't work, use 3 point // } -// +// // //implement an arbitrary derivative // //dumb algorithm // template < class T > @@ -135,22 +122,22 @@ inline void ThreePointdt(T &df, const T &f1, const T &f2, const T &f3, int bias) // { // /* // Lj(x) = PI_i!=j (x - xi) / PI_i!=j (xj - xi) -// +// // so Lj'(x) = SUM_k PI_i!=j|k (x - xi) / PI_i!=j (xj - xi) // */ -// +// // unsigned int i,j,k,i0,i1; -// +// // Real Lpj,mult,div,tj; // Real tval = t[indexval]; -// +// // //sum k // for(j=0;j &f, unsigned int left, if(right - left < 2) return; - else if(right - left < 3) + else if(right - left == 2) { synfig::Vector v = f[left+1] - f[left]; @@ -209,13 +196,11 @@ void GetFirstDerivatives(const std::vector &f, unsigned int left, { //left then middle then right ThreePointdt(*(synfig::Vector*)out,f[left+0], f[left+1], f[left+2], -1); - current += 1; + current++; out += dfstride; for(;current < right-1; current++, out += dfstride) - { ThreePointdt(*(synfig::Vector*)out,f[current-1], f[current], f[current+1], 0); - } ThreePointdt(*(synfig::Vector*)out,f[right-3], f[right-2], f[right-1], 1); current++; @@ -233,14 +218,12 @@ void GetFirstDerivatives(const std::vector &f, unsigned int left, current += 2; for(;current < right-2; current++, out += dfstride) - { FivePointdt(*(synfig::Vector*)out,f[current-2], f[current-1], f[current], f[current+1], f[current+2], 0); - } - FivePointdt(*(synfig::Vector*)out,f[right-5], f[right-4], f[right-3], f[right-2], f[right-1], 1); - out += dfstride; FivePointdt(*(synfig::Vector*)out,f[right-6], f[right-5], f[right-4], f[right-3], f[right-2], 2); out += dfstride; + FivePointdt(*(synfig::Vector*)out,f[right-5], f[right-4], f[right-3], f[right-2], f[right-1], 1); + out += dfstride; current += 2; } } @@ -394,20 +377,22 @@ synfigapp::BLineConverter::BLineConverter() void synfigapp::BLineConverter::clear() { - f.clear(); - f_w.clear(); + point_cache.clear(); + width_cache.clear(); ftemp.clear(); - df.clear(); - cvt.clear(); - brk.clear(); - di.clear(); - d_i.clear(); + deriv.clear(); + curvature.clear(); + break_tangents.clear(); + cum_dist.clear(); + this_dist.clear(); work.clear(); curind.clear(); } void -synfigapp::BLineConverter::operator () (std::list &out, const std::list &in,const std::list &in_w) +synfigapp::BLineConverter::operator()(std::list &blinepoints_out, + const std::list &points_in, + const std::list &widths_in) { //Profiling information /*etl::clock::value_type initialprocess=0, curveval=0, breakeval=0, disteval=0; @@ -416,7 +401,7 @@ synfigapp::BLineConverter::operator () (std::list &out, cons etl::clock_realtime timer,total;*/ //total.reset(); - if(in.size()<=1) + if (points_in.size() < 2) return; clear(); @@ -435,59 +420,52 @@ synfigapp::BLineConverter::operator () (std::list &out, cons //timer.reset(); { - std::list::const_iterator i = in.begin(), end = in.end(); - std::list::const_iterator iw = in_w.begin(); - synfig::Point c; + std::list::const_iterator point_iter = points_in.begin(), end = points_in.end(); + std::list::const_iterator width_iter = widths_in.begin(); + synfig::Point c; - if(in.size() == in_w.size()) + if (points_in.size() == widths_in.size()) { - for(;i != end; ++i,++iw) - { - //eliminate duplicate points - if(*i != c) + for(bool first = true; point_iter != end; ++point_iter,++width_iter) + if (first || *point_iter != c) // eliminate duplicate points { - f.push_back(c = *i); - f_w.push_back(*iw); + first = false; + point_cache.push_back(c = *point_iter); + width_cache.push_back(*width_iter); } - } - }else - { - for(;i != end; ++i) - { - //eliminate duplicate points - if(*i != c) - { - f.push_back(c = *i); - } - } } + else + for(;point_iter != end; ++point_iter) + if(*point_iter != c) // eliminate duplicate points + point_cache.push_back(c = *point_iter); } //initialprocess = timer(); - if(f.size()<=6) + if (point_cache.size() < 7) + { + info("only %d unique points - giving up", point_cache.size()); return; + } //get curvature information //timer.reset(); { - int i,i0,i1; - synfig::Vector v1,v2; - - cvt.resize(f.size()); + int i_this, i_prev, i_next; + synfig::Vector v_prev, v_next; - cvt.front() = 1; - cvt.back() = 1; + curvature.resize(point_cache.size()); + curvature.front() = curvature.back() = 1; - for(i = 1; i < (int)f.size()-1; ++i) + for (i_this = 1; i_this < (int)point_cache.size()-1; i_this++) { - i0 = std::max(0,i - 2); - i1 = std::min((int)(f.size()-1),i + 2); + i_prev = std::max(0, i_this-2); + i_next = std::min((int)(point_cache.size()-1), i_this+2); - v1 = f[i] - f[i0]; - v2 = f[i1] - f[i]; + v_prev = point_cache[i_this] - point_cache[i_prev]; + v_next = point_cache[i_next] - point_cache[i_this]; - cvt[i] = (v1*v2)/(v1.mag()*v2.mag()); + curvature[i_this] = (v_prev*v_next) / (v_prev.mag()*v_next.mag()); } } @@ -500,67 +478,75 @@ synfigapp::BLineConverter::operator () (std::list &out, cons //break at sharp derivative points //TODO tolerance should be set based upon digitization resolution (length dependent index selection) Real tol = 0; //break tolerance, for the cosine of the change in angle (really high curvature or something) - Real fixdistsq = 4*width*width; //the distance to ignore breaks at the end points (for fixing stuff) unsigned int i = 0; - int maxi = -1, last=0; - Real minc = 1; + int sharpest_i=-1; + int last=0; + Real sharpest_curvature = 1; - brk.push_back(0); + break_tangents.push_back(0); - for(i = 1; i < cvt.size()-1; ++i) + // loop through the curvatures; in each continuous run of + // curvatures that exceed the tolerence, find the one with the + // sharpest curvature and add its index to the list of indices + // at which to split tangents + for (i = 1; i < curvature.size()-1; ++i) { - //insert if too sharp (we need to break the tangents to insert onto the break list) - - if(cvt[i] < tol) + if (curvature[i] < tol) { - if(cvt[i] < minc) + if(curvature[i] < sharpest_curvature) { - minc = cvt[i]; - maxi = i; + sharpest_curvature = curvature[i]; + sharpest_i = i; } - }else if(maxi >= 0) + } + else if (sharpest_i > 0) { - if(maxi >= last + 8) + // don't have 2 corners too close to each other + if (sharpest_i >= last + 8) //! \todo make this configurable { - //synfig::info("break: %d-%d",maxi+1,cvt.size()); - brk.push_back(maxi); - last = maxi; + //synfig::info("break: %d-%d",sharpest_i+1,curvature.size()); + break_tangents.push_back(sharpest_i); + last = sharpest_i; } - maxi = -1; - minc = 1; + sharpest_i = -1; + sharpest_curvature = 1; } } - brk.push_back(i); + break_tangents.push_back(i); +// this section causes bug 1892566 if enabled +#if 1 //postprocess for breaks too close to each other + Real fixdistsq = 4*width*width; //the distance to ignore breaks at the end points (for fixing stuff) Real d = 0; - Point p = f[brk.front()]; + Point p = point_cache[break_tangents.front()]; //first set - for(i = 1; i < brk.size()-1; ++i) //do not want to include end point... + for (i = 1; i < break_tangents.size()-1; ++i) //do not want to include end point... { - d = (f[brk[i]] - p).mag_squared(); + d = (point_cache[break_tangents[i]] - p).mag_squared(); if(d > fixdistsq) break; //don't want to group breaks if we ever get over the dist... } //want to erase all points before... if(i != 1) - brk.erase(brk.begin(),brk.begin()+i-1); + break_tangents.erase(break_tangents.begin(),break_tangents.begin()+i-1); //end set - p = f[brk.back()]; - for(i = brk.size()-2; i > 0; --i) //start at one in from the end + p = point_cache[break_tangents.back()]; + for(i = break_tangents.size()-2; i > 0; --i) //start at one in from the end { - d = (f[brk[i]] - p).mag_squared(); + d = (point_cache[break_tangents[i]] - p).mag_squared(); if(d > fixdistsq) break; //don't want to group breaks if we ever get over the dist } - if(i != brk.size()-2) - brk.erase(brk.begin()+i+2,brk.end()); //erase all points that we found... found none if i has not advanced + if(i != break_tangents.size()-2) + break_tangents.erase(break_tangents.begin()+i+2,break_tangents.end()); //erase all points that we found... found none if i has not advanced //must not include the one we ended up on +#endif } //breakeval = timer(); - //synfig::info("found break points: %d",brk.size()); + //synfig::info("found break points: %d",break_tangents.size()); //get the distance calculation of the entire curve (for tangent scaling) @@ -568,17 +554,18 @@ synfigapp::BLineConverter::operator () (std::list &out, cons { synfig::Point p1,p2; - p1=p2=f[0]; + p1=p2=point_cache[0]; - di.resize(f.size()); d_i.resize(f.size()); + cum_dist.resize(point_cache.size()); this_dist.resize(point_cache.size()); Real d = 0; - for(unsigned int i = 0; i < f.size();) + for(unsigned int i = 0; i < point_cache.size();) { - d += (d_i[i] = (p2-p1).mag()); - di[i] = d; + d += (this_dist[i] = (p2-p1).mag()); + cum_dist[i] = d; p1=p2; - p2=f[++i]; + //! \todo is this legal? it reads off the end of the vector + p2=point_cache[++i]; } } //disteval = timer(); @@ -599,7 +586,7 @@ synfigapp::BLineConverter::operator () (std::list &out, cons bool done = false; - Real errortol = smoothness*pixelwidth; //???? what the hell should this value be + Real errortol = smoothness*pixelwidth; //???? what should this value be BLinePoint a; synfig::Vector v; @@ -611,26 +598,41 @@ synfigapp::BLineConverter::operator () (std::list &out, cons //a.set_width(width); a.set_width(1.0f); - setwidth = (f.size() == f_w.size()); + setwidth = (point_cache.size() == width_cache.size()); - for(j = 0; j < (int)brk.size() - 1; ++j) + for(j = 0; j < (int)break_tangents.size() - 1; ++j) { //for b[j] to b[j+1] subdivide and stuff - i0 = brk[j]; - i3 = brk[j+1]; + i0 = break_tangents[j]; + i3 = break_tangents[j+1]; unsigned int size = i3-i0+1; //must include the end points //new derivatives //timer.reset(); - ftemp.assign(f.begin()+i0, f.begin()+i3+1); + ftemp.assign(point_cache.begin()+i0, point_cache.begin()+i3+1); for(i=0;i<20;++i) gaussian_blur_3(ftemp.begin(),ftemp.end(),false); - df.resize(size); - GetFirstDerivatives(ftemp,0,size,(char*)&df[0],sizeof(df[0])); - //GetSimpleDerivatives(ftemp,0,size,df,0,di); - //< don't have to worry about indexing stuff as it is all being taken car of right now + deriv.resize(size); + + // Wondering whether the modification of the deriv vector + // using a char* pointer and pointer arithmetric was safe, + // I looked it up... + // + // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2369.pdf tells me: + // + // 23.2.5 Class template vector [vector] + // + // [...] The elements of a vector are stored contiguously, + // meaning that if v is a vector where T is + // some type other than bool, then it obeys the identity + // &v[n] == &v[0] + n for all 0 <= n < v.size(). + // + GetFirstDerivatives(ftemp,0,size,(char*)&deriv[0],sizeof(deriv[0])); + + //GetSimpleDerivatives(ftemp,0,size,deriv,0,cum_dist); + //< don't have to worry about indexing stuff as it is all being taken care of right now //preproceval += timer(); //numpre++; @@ -641,8 +643,8 @@ synfigapp::BLineConverter::operator () (std::list &out, cons //start off with break points as indices curind.clear(); - curind.push_back(cpindex(i0,di[i3]-di[i0],0)); //0 error because no curve on the left - curind.push_back(cpindex(i3,di[i3]-di[i0],-1)); //error needs to be reevaluated + curind.push_back(cpindex(i0,cum_dist[i3]-cum_dist[i0],0)); //0 error because no curve on the left + curind.push_back(cpindex(i3,cum_dist[i3]-cum_dist[i0],-1)); //error needs to be reevaluated done = false; //we want to loop unsigned int dcount = 0; @@ -651,10 +653,10 @@ synfigapp::BLineConverter::operator () (std::list &out, cons while(!done) { //tessellate all curves with invalid error values - work[0] = f[i0]; + work[0] = point_cache[i0]; //timer.reset(); - /*numtess += */tessellate_curves(curind,f,df,work); + /*numtess += */tessellate_curves(curind,point_cache,deriv,work); //tesseval += timer(); //now get all error values @@ -665,15 +667,15 @@ synfigapp::BLineConverter::operator () (std::list &out, cons { //evaluate error from points (starting at current index) int size = curind[i].curind - curind[i-1].curind + 1; - curind[i].error = CurveError(&f[curind[i-1].curind], size, + curind[i].error = CurveError(&point_cache[curind[i-1].curind], size, work,(curind[i-1].curind - i0)*2,(curind[i].curind - i0)*2+1); /*if(curind[i].error > 1.0e5) { synfig::info("Holy crap %d-%d error %f",curind[i-1].curind,curind[i].curind,curind[i].error); curind[i].error = -1; - numtess += tessellate_curves(curind,f,df,work); - curind[i].error = CurveError(&f[curind[i-1].curind], size, + numtess += tessellate_curves(curind,f,deriv,work); + curind[i].error = CurveError(&point_cache[curind[i-1].curind], size, work,0,work.size());//(curind[i-1].curind - i0)*2,(curind[i].curind - i0)*2+1); }*/ //numerror++; @@ -710,7 +712,7 @@ synfigapp::BLineConverter::operator () (std::list &out, cons ibreak = (ibase + itop)/2; Real scale, scale2; - assert(ibreak < f.size()); + assert(ibreak < point_cache.size()); //synfig::info("Split %d -%d- %d, error: %f", ibase,ibreak,itop,maxrelerror); @@ -722,15 +724,15 @@ synfigapp::BLineConverter::operator () (std::list &out, cons curind[maxi-1].error = -1; if(maxi+1 < indsize) curind[maxi+1].error = -1; //if there is a curve segment beyond this it will be effected as well - scale = di[itop] - di[ibreak]; - scale2 = maxi+1 < indsize ? di[curind[maxi+1].curind] - di[itop] : scale; //to the right valid? + scale = cum_dist[itop] - cum_dist[ibreak]; + scale2 = maxi+1 < indsize ? cum_dist[curind[maxi+1].curind] - cum_dist[itop] : scale; //to the right valid? curind[maxi].tangentscale = std::min(scale, scale2); - scale = di[ibreak] - di[ibase]; - scale2 = maxi >= 2 ? di[ibase] - di[curind[maxi-2].curind] : scale; // to the left valid -2 ? + scale = cum_dist[ibreak] - cum_dist[ibase]; + scale2 = maxi >= 2 ? cum_dist[ibase] - cum_dist[curind[maxi-2].curind] : scale; // to the left valid -2 ? curind[maxi-1].tangentscale = std::min(scale, scale2); - scale = std::min(di[ibreak] - di[ibase], di[itop] - di[ibreak]); + scale = std::min(cum_dist[ibreak] - cum_dist[ibase], cum_dist[itop] - cum_dist[ibreak]); curind.insert(curind.begin()+maxi,cpindex(ibreak, scale, -1)); //curind.push_back(cpindex(ibreak, scale, -1)); @@ -749,7 +751,7 @@ synfigapp::BLineConverter::operator () (std::list &out, cons is = curind[0].curind; //first point inherits current tangent status - v = df[is - i0]; + v = deriv[is - i0]; if(v.mag_squared() > EPSILON) v *= (curind[0].tangentscale/v.mag()); @@ -757,10 +759,10 @@ synfigapp::BLineConverter::operator () (std::list &out, cons a.set_tangent(v); else a.set_tangent2(v); - a.set_vertex(f[is]); - if(setwidth)a.set_width(f_w[is]); + a.set_vertex(point_cache[is]); + if(setwidth)a.set_width(width_cache[is]); - out.push_back(a); + blinepoints_out.push_back(a); a.set_split_tangent_flag(false); //won't need to break anymore breaktan = false; @@ -769,21 +771,21 @@ synfigapp::BLineConverter::operator () (std::list &out, cons is = curind[i].curind; //first point inherits current tangent status - v = df[is-i0]; + v = deriv[is-i0]; if(v.mag_squared() > EPSILON) v *= (curind[i].tangentscale/v.mag()); a.set_tangent(v); // always inside, so guaranteed to be smooth - a.set_vertex(f[is]); - if(setwidth)a.set_width(f_w[is]); + a.set_vertex(point_cache[is]); + if(setwidth)a.set_width(width_cache[is]); - out.push_back(a); + blinepoints_out.push_back(a); } //set the last point's data is = curind.back().curind; //should already be this - v = df[is-i0]; + v = deriv[is-i0]; if(v.mag_squared() > EPSILON) v *= (curind.back().tangentscale/v.mag()); @@ -794,11 +796,11 @@ synfigapp::BLineConverter::operator () (std::list &out, cons //will get the vertex and tangent 2 from next round } - a.set_vertex(f[i3]); + a.set_vertex(point_cache[i3]); a.set_split_tangent_flag(false); if(setwidth) - a.set_width(f_w[i3]); - out.push_back(a); + a.set_width(width_cache[i3]); + blinepoints_out.push_back(a); /*etl::clock::value_type totaltime = total(), misctime = totaltime - initialprocess - curveval - breakeval - disteval @@ -819,7 +821,7 @@ synfigapp::BLineConverter::operator () (std::list &out, cons " Total time: %f, Misc time: %f\n", initialprocess, curveval,breakeval,disteval, numpre,preproceval,numtess,tesseval,numerror,erroreval,numsplit,spliteval, - in.size(),out.size(), + points_in.size(),blinepoints_out.size(), totaltime,misctime);*/ return; @@ -832,10 +834,6 @@ void synfigapp::BLineConverter::EnforceMinWidth(std::list &b end = bline.end(); for(i = bline.begin(); i != end; ++i) - { if(i->get_width() < min_pressure) - { i->set_width(min_pressure); - } - } }