+++ /dev/null
-/* === 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 <config.h>
-#endif
-
-#include "curve_helper.h"
-#include "curveset.h"
-#include "blinepoint.h"
-#include <ETL/bezier>
-#include <vector>
-#include <list>
-#include <set>
-
-#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<ipoint *> CurveInts; //in no particular order
-
- vector<CurveInts> c1ints;
- vector<CurveInts> c2ints;
-
- //get the intersections
- void GetIntersections(const CurveSet &lhs, const CurveSet &rhs)
- {
- CIntersect isect;
- bezier<Point> 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<ipoint *> 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<ipoint *>::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<Point> b;
-
- for(ci=0; ci < (int)set.size(); ++ci)
- {
- const vector<CurvePoint> &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;
-}
projects / synfig.git / blobdiff