Enabled $Id$ expansion.
[synfig.git] / synfig-core / trunk / src / synfig / curveset.cpp
1 /* === S Y N F I G ========================================================= */
2 /*!     \file curveset.cpp
3 **      \brief Curve Set Implementation File
4 **
5 **      $Id$
6 **
7 **      \legal
8 **      Copyright (c) 2002-2005 Robert B. Quattlebaum Jr., Adrian Bentley
9 **
10 **      This package is free software; you can redistribute it and/or
11 **      modify it under the terms of the GNU General Public License as
12 **      published by the Free Software Foundation; either version 2 of
13 **      the License, or (at your option) any later version.
14 **
15 **      This package is distributed in the hope that it will be useful,
16 **      but WITHOUT ANY WARRANTY; without even the implied warranty of
17 **      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 **      General Public License for more details.
19 **      \endlegal
20 */
21 /* ========================================================================= */
22
23 /* === H E A D E R S ======================================================= */
24
25 #ifdef USING_PCH
26 #       include "pch.h"
27 #else
28 #ifdef HAVE_CONFIG_H
29 #       include <config.h>
30 #endif
31
32 #include "curve_helper.h"
33 #include "curveset.h"
34 #include "blinepoint.h"
35 #include <ETL/bezier>
36 #include <vector>
37 #include <list>
38 #include <set>
39
40 #endif
41
42 /* === U S I N G =========================================================== */
43
44 using namespace std;
45 using namespace etl;
46 using namespace synfig;
47
48 /* === M A C R O S ========================================================= */
49
50 /* === G L O B A L S ======================================================= */
51 const Real ERROR = 1e-10;
52
53 /* === P R O C E D U R E S ================================================= */
54
55 /* === M E T H O D S ======================================================= */
56
57 /* === E N T R Y P O I N T ================================================= */
58 template < typename T >
59 inline bool Zero(const T &a, const T &tol = (T)ERROR)
60 {
61         return a < tol && a > -tol;
62 }
63
64 CurvePoint::CurvePoint(const Point &pin, const Vector &left, const Vector &right)
65 :p(pin),l(left),r(right)
66 {
67 }
68
69 CurvePoint::CurvePoint(const BLinePoint &bpoint)
70 {
71         p = bpoint.get_vertex();
72
73         l = p + bpoint.get_tangent1()*(1/3.0f);
74         r = p + bpoint.get_tangent2()*(1/3.0f);
75 }
76
77 struct ipoint
78 {
79         int     curveindex;
80         int             vertindex;
81         float   tvalue;
82
83         ipoint  *next;
84         ipoint  *prev;
85         ipoint  *neighbor;
86
87         int     go_in;  //going in = 1, coming out = -1
88
89         ipoint()
90         {
91                 next = this;
92                 prev = this;
93                 neighbor = 0;
94         }
95
96         bool operator<(const ipoint &rhs) const
97         {
98                 if(curveindex == rhs.curveindex)
99                 {
100                         if(vertindex == rhs.vertindex)
101                         {
102                                 return tvalue < rhs.tvalue;
103                         }else return vertindex < rhs.vertindex;
104                 }else return curveindex < rhs.curveindex;
105         }
106
107         bool operator >(const ipoint &rhs) const
108         {
109                 return rhs < *this;
110         }
111
112         void insert_after(ipoint *i)
113         {
114                 //from: next - next.prev
115                 //to: next* - i - next.prev*
116
117                 ipoint  *bef = this,
118                                 *aft = next;
119
120                 //assuming the input point is not connected to anything, we don't have to do anything with it...
121                 bef->next = i;
122                 i->prev = bef;
123                 aft->prev = i;
124                 i->next = aft;
125         }
126
127         void insert_before(ipoint *i)
128         {
129                 //from: prev.next - prev
130                 //to: prev.next* - i - prev*
131
132                 ipoint  *bef = prev,
133                                 *aft = this;
134
135                 //assuming the input point is not connected to anything, we don't have to do anything with it...
136                 bef->next = i;
137                 i->prev = bef;
138                 aft->prev = i;
139                 i->next = aft;
140         }
141
142         void insert_sorted(ipoint *i)
143         {
144                 ipoint *search = this;
145
146                 if(*i < *this)
147                 {
148                         //we go forward
149                         search = this;
150                         do
151                         {
152                                 search = search->next;
153                         }while(*i < *search && search != this); //ending conditions...
154
155                         //now we insert previously...
156                         search->insert_before(i);
157                 }else if(*i > *this)
158                 {
159                         //we go backwards...
160                         search = this;
161                         do
162                         {
163                                 search = search->prev;
164                         }while(*i > *search && search != this); //ending conditions...
165
166                         //now we insert previously...
167                         search->insert_after(i);
168                 }
169         }
170 };
171
172 enum SetOp
173 {
174         INTERSECT       = 0,
175         UNION,
176         SUBTRACT,
177         INVSUBTRACT,
178         NUM_SETOPERATIONS
179 };
180
181 class PolygonClipper
182 {
183 public:
184         typedef vector<ipoint *>        CurveInts; //in no particular order
185
186         vector<CurveInts>       c1ints;
187         vector<CurveInts>       c2ints;
188
189         //get the intersections
190         void GetIntersections(const CurveSet &lhs, const CurveSet &rhs)
191         {
192                 CIntersect      isect;
193                 bezier<Point>   b1,b2;
194
195                 int i1,j1,ci1,s1;
196                 int i2,j2,ci2,s2;
197
198                 //clear out so everyone's happy
199                 c1ints.clear();
200                 c2ints.clear();
201
202                 c1ints.resize(lhs.set.size());
203                 c2ints.resize(rhs.set.size());
204
205                 //loop through everyone and be happy...
206
207                 //intersect each curve with each other curve, and we're good
208                 for(ci1=0;ci1 < (int)lhs.set.size(); ++ci1)
209                 {
210                         const CurveSet::region &cur1 = lhs.set[ci1];
211                         s1 = cur1.size();
212                         for(j1 = s1-1, i1=0; i1 < s1; j1 = i1++)
213                         {
214                                 b1[0] = cur1[j1].p;
215                                 b1[3] = cur1[i1].p;
216                                 b1[1] = b1[0] + cur1[j1].r/3;
217                                 b1[2] = b1[3] - cur1[i1].l/3;
218
219                                 for(ci2=0;ci2 < (int)rhs.set.size(); ++ci2)
220                                 {
221                                         const CurveSet::region &cur2 = rhs.set[ci2];
222                                         s2 = cur2.size();
223                                         for(j2 = s2-1, i2=0; i2 < s2; j2 = i2++)
224                                         {
225                                                 b2[0] = cur2[j2].p;
226                                                 b2[3] = cur2[i2].p;
227                                                 b2[1] = b2[0] + cur2[j2].r/3;
228                                                 b2[2] = b2[3] - cur2[i2].l/3;
229
230                                                 isect(b1,b2);
231
232                                                 for(int index=0; index < (int)isect.times.size(); ++index)
233                                                 {
234                                                         //prepare basic intersection information
235                                                         ipoint *ip1 = new ipoint, *ip2 = new ipoint;
236
237                                                         //set parameters
238                                                         ip1->curveindex = ci1; ip1->vertindex = j1; ip1->tvalue = isect.times[index].first;
239                                                         ip2->curveindex = ci2; ip2->vertindex = j2; ip2->tvalue = isect.times[index].second;
240
241                                                         //set neighbors
242                                                         ip1->neighbor = ip2;
243                                                         ip2->neighbor = ip1;
244
245                                                         //first one just goes on end of list
246                                                         c1ints[ci1].back()->insert_sorted(ip1);
247                                                         c1ints[ci1].push_back(ip1);
248
249                                                         //second one must go in order
250                                                         c2ints[ci2].back()->insert_sorted(ip2);
251                                                         c2ints[ci2].push_back(ip2);
252
253                                                         //we're all good...
254                                                 }
255                                         }
256                                 }
257                         }
258                 }
259
260                 //Now figure out the containment properties of each int point
261                 Point p;
262                 int inside = 0;
263                 for(int i = 0; i < (int)c1ints.size(); ++i)
264                 {
265                         if(c1ints[i].size() == 0) continue;
266
267                         //must test insideness for the edges
268                         ipoint *start, *iter;
269                         start = iter = c1ints[i].front();
270
271                         //i == iter->curveindex == the index of the current curve we're looking at
272
273                         //set the initial insideness on the other curve...
274                         p = lhs.set[i][iter->vertindex].p;
275                         inside = rhs.intersect(p)%2; //if it's inside by the even odd rule
276
277                         do
278                         {
279                                 iter->go_in = inside? -1 : 1; //leaving if inside, or coming in if not
280                                 inside = !inside;
281                                 iter = iter->next;
282                         }while(iter != start); //I hope this isn't an infinite loop!
283                 }
284
285                 //and curve 2
286                 for(int i = 0; i < (int)c2ints.size(); ++i)
287                 {
288                         if(c2ints[i].size() == 0) continue;
289
290                         //must test insideness for the edges
291                         ipoint *start, *iter;
292                         start = iter = c1ints[i].front();
293
294                         //set the initial insideness on the other curve...
295                         p = rhs.set[i][iter->vertindex].p;
296                         inside = lhs.intersect(p)%2; //if it's inside by the even odd rule
297
298                         do
299                         {
300                                 iter->go_in = inside? -1 : 1; //leaving if inside, or coming in if not
301                                 inside = !inside;
302                                 iter = iter->next;
303                         }while(iter != start); //I hope this isn't an infinite loop!
304                 }
305         }
306
307         bool ConstructSet(CurveSet &c, const CurveSet &lhs, const CurveSet &rhs, int type)
308         {
309                 bool in1,in2;
310
311                 switch(type)
312                 {
313                         case INTERSECT: //1&2
314                         {
315                                 in1 = true; in2 = true;
316                                 break;
317                         }
318
319                         case UNION: //1|2
320                         {
321                                 in1 = false; in2 = false;
322                                 break;
323                         }
324
325                         case SUBTRACT: //1-2
326                         {
327                                 in1 = true; in2 = false;
328                                 break;
329                         }
330
331                         case INVSUBTRACT: //2-1
332                         {
333                                 in1 = false; in2 = true;
334                                 break;
335                         }
336
337                         default:
338                         {
339                                 return false;
340                         }
341                 }
342
343                 //traverse path based on inside flags
344
345                 //fill all the paths of native stuff
346                 set<ipoint *>   ipset;
347                 for(int ci=0; ci<(int)c1ints.size(); ++ci)
348                 {
349                         for(int i=0; i < (int)c1ints[ci].size(); ++i)
350                         {
351                                 ipset.insert(c1ints[ci][i]);
352                         }
353                 }
354
355                 //
356                 while(ipset.size() > 0)
357                 {
358                         //start from one point (always on curveset 1) and traverse until we find it again
359                         ipoint *start, *iter;
360                         start = iter = *ipset.begin();
361
362                         //All the info to swap when we transition curves...
363                         const CurveSet *cur, *other;
364                         bool curin, otherin;
365                         bool delcur = true;
366
367                         set<ipoint *>::iterator deliter;
368
369                         int ci,i1,i2,size;
370                         float t1,t2;
371
372                         CurveSet::region        current;
373                         CurvePoint      cp;
374
375                         cur = &lhs; other = &rhs;
376                         curin = in1; otherin = in2;
377                         delcur = true;
378
379                         do
380                         {
381                                 //remove the current iter from the set
382                                 if(delcur)
383                                 {
384                                         deliter = ipset.find(iter);
385                                         if(deliter != ipset.end()) ipset.erase(deliter);
386                                 }
387
388                                 //go to next and accumulate information
389                                 ci = iter->curveindex;
390                                 i1 = iter->vertindex;
391                                 t1 = iter->tvalue;
392                                 iter = iter->next; //move to next and get its info
393
394                                 i2 = iter->vertindex;
395                                 t2 = iter->tvalue;
396
397                                 size = cur->set[ci].size();
398
399                                 //record all the stuff between us...
400                                 //start on an intersection - get the curve point...
401
402
403                                 //transition curves...
404                                 iter = iter->neighbor;
405                                 swap(cur,other);
406                                 swap(curin,otherin);
407                                 delcur = !delcur;
408                         }while(iter != start); //I hope THIS isn't an infinite loop
409                 }
410
411                 return true;
412         }
413 };
414
415 void CurveSet::SetClamp(int &i, int &si)
416 {
417         if(si > 0 && si < (int)set.size())
418         {
419                 if(i >= (int)set[si].size())
420                 {
421                         i -= set[si].size();
422                         si++;
423                 }else if (i < 0)
424                 {
425                         i += set[si].size();
426                         si--;
427                 }
428         }
429 }
430
431 void CurveSet::CleanUp(int curve)
432 {
433 }
434
435 /*      Detect intersections that are crazy happy good
436
437         Performance annoyances:
438         1) Recursing down to find an intersection at the end points that doesn't actually exist
439                 (can be helped a bit by not including the edges of bouding rectaingles)
440         2) Intersecting curves is slow... oh well
441
442         Algorithm:
443         1) Inside out scheme, track when edges go into and come out of various objects etc.
444
445         + doesn't require initial conditions
446         - only works with odd-even rule
447 */
448
449 CurveSet CurveSet::operator &(const CurveSet &rhs) const
450 {
451         return *this;
452 }
453
454 CurveSet CurveSet::operator |(const CurveSet &rhs) const
455 {
456         return *this;
457 }
458
459 CurveSet CurveSet::operator -(const CurveSet &rhs) const
460 {
461         return *this;
462 }
463
464 int CurveSet::intersect(const Point &p) const
465 {
466         int inter = 0, ci,i,j,s;
467         bezier<Point>   b;
468
469         for(ci=0; ci < (int)set.size(); ++ci)
470         {
471                 const vector<CurvePoint> &curve = set[ci];
472                 s = curve.size();
473                 for(j=s-1,i=0; i < s; j = i++)
474                 {
475                         b[0] = curve[j].p; b[3] = curve[i].p;
476                         b[1] = b[0] + curve[j].r/3; b[2] = b[3] - curve[i].l/3;
477
478                         inter += synfig::intersect(b,p);
479                 }
480         }
481
482         return inter;
483 }