X-Git-Url: https://git.pterodactylus.net/?a=blobdiff_plain;f=synfig-core%2Ftags%2Fsynfig_0_61_04%2Fsynfig-core%2Fsrc%2Fsynfig%2Fcurveset.cpp;fp=synfig-core%2Ftags%2Fsynfig_0_61_04%2Fsynfig-core%2Fsrc%2Fsynfig%2Fcurveset.cpp;h=a50294779079ef37abb8ee2708a564e669d4a2c1;hb=f64373f72487d6aa502d9bde985b8a2d5519f099;hp=0000000000000000000000000000000000000000;hpb=ad81c2528eb79c7500e65fd15a9f66375f75d121;p=synfig.git

diff --git a/synfig-core/tags/synfig_0_61_04/synfig-core/src/synfig/curveset.cpp b/synfig-core/tags/synfig_0_61_04/synfig-core/src/synfig/curveset.cpp
new file mode 100644
index 0000000..a502947
--- /dev/null
+++ b/synfig-core/tags/synfig_0_61_04/synfig-core/src/synfig/curveset.cpp
@@ -0,0 +1,483 @@
+/* === S Y N F I G ========================================================= */
+/*!	\file curveset.cpp
+**	\brief Curve Set Implementation File
+**
+**	$Id: curveset.cpp,v 1.1.1.1 2005/01/04 01:23:14 darco Exp $
+**
+**	\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 bouding rectaingles)
+	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;
+}