X-Git-Url: https://git.pterodactylus.net/?a=blobdiff_plain;f=synfig-core%2Ftrunk%2Fsrc%2Fsynfig%2Fcurveset.cpp;fp=synfig-core%2Ftrunk%2Fsrc%2Fsynfig%2Fcurveset.cpp;h=0000000000000000000000000000000000000000;hb=a095981e18cc37a8ecc7cd237cc22b9c10329264;hp=e8bd7fab3d3fb74985432d442fa12d998b121534;hpb=9459638ad6797b8139f1e9f0715c96076dbf0890;p=synfig.git diff --git a/synfig-core/trunk/src/synfig/curveset.cpp b/synfig-core/trunk/src/synfig/curveset.cpp deleted file mode 100644 index e8bd7fa..0000000 --- a/synfig-core/trunk/src/synfig/curveset.cpp +++ /dev/null @@ -1,483 +0,0 @@ -/* === S Y N F I G ========================================================= */ -/*! \file curveset.cpp -** \brief Curve Set Implementation File -** -** $Id$ -** -** \legal -** Copyright (c) 2002-2005 Robert B. Quattlebaum Jr., Adrian Bentley -** -** This package is free software; you can redistribute it and/or -** modify it under the terms of the GNU General Public License as -** published by the Free Software Foundation; either version 2 of -** the License, or (at your option) any later version. -** -** This package is distributed in the hope that it will be useful, -** but WITHOUT ANY WARRANTY; without even the implied warranty of -** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -** General Public License for more details. -** \endlegal -*/ -/* ========================================================================= */ - -/* === H E A D E R S ======================================================= */ - -#ifdef USING_PCH -# include "pch.h" -#else -#ifdef HAVE_CONFIG_H -# include -#endif - -#include "curve_helper.h" -#include "curveset.h" -#include "blinepoint.h" -#include -#include -#include -#include - -#endif - -/* === U S I N G =========================================================== */ - -using namespace std; -using namespace etl; -using namespace synfig; - -/* === M A C R O S ========================================================= */ - -/* === G L O B A L S ======================================================= */ -const Real ERROR = 1e-10; - -/* === P R O C E D U R E S ================================================= */ - -/* === M E T H O D S ======================================================= */ - -/* === E N T R Y P O I N T ================================================= */ -template < typename T > -inline bool Zero(const T &a, const T &tol = (T)ERROR) -{ - return a < tol && a > -tol; -} - -CurvePoint::CurvePoint(const Point &pin, const Vector &left, const Vector &right) -:p(pin),l(left),r(right) -{ -} - -CurvePoint::CurvePoint(const BLinePoint &bpoint) -{ - p = bpoint.get_vertex(); - - l = p + bpoint.get_tangent1()*(1/3.0f); - r = p + bpoint.get_tangent2()*(1/3.0f); -} - -struct ipoint -{ - int curveindex; - int vertindex; - float tvalue; - - ipoint *next; - ipoint *prev; - ipoint *neighbor; - - int go_in; //going in = 1, coming out = -1 - - ipoint() - { - next = this; - prev = this; - neighbor = 0; - } - - bool operator<(const ipoint &rhs) const - { - if(curveindex == rhs.curveindex) - { - if(vertindex == rhs.vertindex) - { - return tvalue < rhs.tvalue; - }else return vertindex < rhs.vertindex; - }else return curveindex < rhs.curveindex; - } - - bool operator>(const ipoint &rhs) const - { - return rhs < *this; - } - - void insert_after(ipoint *i) - { - //from: next - next.prev - //to: next* - i - next.prev* - - ipoint *bef = this, - *aft = next; - - //assuming the input point is not connected to anything, we don't have to do anything with it... - bef->next = i; - i->prev = bef; - aft->prev = i; - i->next = aft; - } - - void insert_before(ipoint *i) - { - //from: prev.next - prev - //to: prev.next* - i - prev* - - ipoint *bef = prev, - *aft = this; - - //assuming the input point is not connected to anything, we don't have to do anything with it... - bef->next = i; - i->prev = bef; - aft->prev = i; - i->next = aft; - } - - void insert_sorted(ipoint *i) - { - ipoint *search = this; - - if(*i < *this) - { - //we go forward - search = this; - do - { - search = search->next; - }while(*i < *search && search != this); //ending conditions... - - //now we insert previously... - search->insert_before(i); - }else if(*i > *this) - { - //we go backwards... - search = this; - do - { - search = search->prev; - }while(*i > *search && search != this); //ending conditions... - - //now we insert previously... - search->insert_after(i); - } - } -}; - -enum SetOp -{ - INTERSECT = 0, - UNION, - SUBTRACT, - INVSUBTRACT, - NUM_SETOPERATIONS -}; - -class PolygonClipper -{ -public: - typedef vector CurveInts; //in no particular order - - vector c1ints; - vector c2ints; - - //get the intersections - void GetIntersections(const CurveSet &lhs, const CurveSet &rhs) - { - CIntersect isect; - bezier b1,b2; - - int i1,j1,ci1,s1; - int i2,j2,ci2,s2; - - //clear out so everyone's happy - c1ints.clear(); - c2ints.clear(); - - c1ints.resize(lhs.set.size()); - c2ints.resize(rhs.set.size()); - - //loop through everyone and be happy... - - //intersect each curve with each other curve, and we're good - for(ci1=0;ci1 < (int)lhs.set.size(); ++ci1) - { - const CurveSet::region &cur1 = lhs.set[ci1]; - s1 = cur1.size(); - for(j1 = s1-1, i1=0; i1 < s1; j1 = i1++) - { - b1[0] = cur1[j1].p; - b1[3] = cur1[i1].p; - b1[1] = b1[0] + cur1[j1].r/3; - b1[2] = b1[3] - cur1[i1].l/3; - - for(ci2=0;ci2 < (int)rhs.set.size(); ++ci2) - { - const CurveSet::region &cur2 = rhs.set[ci2]; - s2 = cur2.size(); - for(j2 = s2-1, i2=0; i2 < s2; j2 = i2++) - { - b2[0] = cur2[j2].p; - b2[3] = cur2[i2].p; - b2[1] = b2[0] + cur2[j2].r/3; - b2[2] = b2[3] - cur2[i2].l/3; - - isect(b1,b2); - - for(int index=0; index < (int)isect.times.size(); ++index) - { - //prepare basic intersection information - ipoint *ip1 = new ipoint, *ip2 = new ipoint; - - //set parameters - ip1->curveindex = ci1; ip1->vertindex = j1; ip1->tvalue = isect.times[index].first; - ip2->curveindex = ci2; ip2->vertindex = j2; ip2->tvalue = isect.times[index].second; - - //set neighbors - ip1->neighbor = ip2; - ip2->neighbor = ip1; - - //first one just goes on end of list - c1ints[ci1].back()->insert_sorted(ip1); - c1ints[ci1].push_back(ip1); - - //second one must go in order - c2ints[ci2].back()->insert_sorted(ip2); - c2ints[ci2].push_back(ip2); - - //we're all good... - } - } - } - } - } - - //Now figure out the containment properties of each int point - Point p; - int inside = 0; - for(int i = 0; i < (int)c1ints.size(); ++i) - { - if(c1ints[i].size() == 0) continue; - - //must test insideness for the edges - ipoint *start, *iter; - start = iter = c1ints[i].front(); - - //i == iter->curveindex == the index of the current curve we're looking at - - //set the initial insideness on the other curve... - p = lhs.set[i][iter->vertindex].p; - inside = rhs.intersect(p)%2; //if it's inside by the even odd rule - - do - { - iter->go_in = inside? -1 : 1; //leaving if inside, or coming in if not - inside = !inside; - iter = iter->next; - }while(iter != start); //I hope this isn't an infinite loop! - } - - //and curve 2 - for(int i = 0; i < (int)c2ints.size(); ++i) - { - if(c2ints[i].size() == 0) continue; - - //must test insideness for the edges - ipoint *start, *iter; - start = iter = c1ints[i].front(); - - //set the initial insideness on the other curve... - p = rhs.set[i][iter->vertindex].p; - inside = lhs.intersect(p)%2; //if it's inside by the even odd rule - - do - { - iter->go_in = inside? -1 : 1; //leaving if inside, or coming in if not - inside = !inside; - iter = iter->next; - }while(iter != start); //I hope this isn't an infinite loop! - } - } - - bool ConstructSet(CurveSet &/*c*/, const CurveSet &lhs, const CurveSet &rhs, int type) - { - bool in1,in2; - - switch(type) - { - case INTERSECT: //1&2 - { - in1 = true; in2 = true; - break; - } - - case UNION: //1|2 - { - in1 = false; in2 = false; - break; - } - - case SUBTRACT: //1-2 - { - in1 = true; in2 = false; - break; - } - - case INVSUBTRACT: //2-1 - { - in1 = false; in2 = true; - break; - } - - default: - { - return false; - } - } - - //traverse path based on inside flags - - //fill all the paths of native stuff - set ipset; - for(int ci=0; ci<(int)c1ints.size(); ++ci) - { - for(int i=0; i < (int)c1ints[ci].size(); ++i) - { - ipset.insert(c1ints[ci][i]); - } - } - - // - while(ipset.size() > 0) - { - //start from one point (always on curveset 1) and traverse until we find it again - ipoint *start, *iter; - start = iter = *ipset.begin(); - - //All the info to swap when we transition curves... - const CurveSet *cur, *other; - bool curin, otherin; - bool delcur = true; - - set::iterator deliter; - - int ci,i1,i2,size; - float t1,t2; - - CurveSet::region current; - CurvePoint cp; - - cur = &lhs; other = &rhs; - curin = in1; otherin = in2; - delcur = true; - - do - { - //remove the current iter from the set - if(delcur) - { - deliter = ipset.find(iter); - if(deliter != ipset.end()) ipset.erase(deliter); - } - - //go to next and accumulate information - ci = iter->curveindex; - i1 = iter->vertindex; - t1 = iter->tvalue; - iter = iter->next; //move to next and get its info - - i2 = iter->vertindex; - t2 = iter->tvalue; - - size = cur->set[ci].size(); - - //record all the stuff between us... - //start on an intersection - get the curve point... - - - //transition curves... - iter = iter->neighbor; - swap(cur,other); - swap(curin,otherin); - delcur = !delcur; - }while(iter != start); //I hope THIS isn't an infinite loop - } - - return true; - } -}; - -void CurveSet::SetClamp(int &i, int &si) -{ - if(si > 0 && si < (int)set.size()) - { - if(i >= (int)set[si].size()) - { - i -= set[si].size(); - si++; - }else if (i < 0) - { - i += set[si].size(); - si--; - } - } -} - -void CurveSet::CleanUp(int /*curve*/) -{ -} - -/* Detect intersections that are crazy happy good - - Performance annoyances: - 1) Recursing down to find an intersection at the end points that doesn't actually exist - (can be helped a bit by not including the edges of bounding rectangles) - 2) Intersecting curves is slow... oh well - - Algorithm: - 1) Inside out scheme, track when edges go into and come out of various objects etc. - - + doesn't require initial conditions - - only works with odd-even rule -*/ - -CurveSet CurveSet::operator&(const CurveSet &/*rhs*/) const -{ - return *this; -} - -CurveSet CurveSet::operator|(const CurveSet &/*rhs*/) const -{ - return *this; -} - -CurveSet CurveSet::operator-(const CurveSet &/*rhs*/) const -{ - return *this; -} - -int CurveSet::intersect(const Point &p) const -{ - int inter = 0, ci,i,j,s; - bezier b; - - for(ci=0; ci < (int)set.size(); ++ci) - { - const vector &curve = set[ci]; - s = curve.size(); - for(j=s-1,i=0; i < s; j = i++) - { - b[0] = curve[j].p; b[3] = curve[i].p; - b[1] = b[0] + curve[j].r/3; b[2] = b[3] - curve[i].l/3; - - inter += synfig::intersect(b,p); - } - } - - return inter; -}