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 >
Zero(const T & a,const T & tol=(T)ERROR)59 inline bool Zero(const T &a, const T &tol = (T)ERROR)
60 {
61 return a < tol && a > -tol;
62 }
63
CurvePoint(const Point & pin,const Vector & left,const Vector & right)64 CurvePoint::CurvePoint(const Point &pin, const Vector &left, const Vector &right)
65 :p(pin),l(left),r(right)
66 {
67 }
68
CurvePoint(const BLinePoint & bpoint)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
ipointipoint89 ipoint():
90 curveindex(),
91 vertindex(),
92 tvalue(),
93 go_in()
94 {
95 next = this;
96 prev = this;
97 neighbor = NULL;
98 }
99
operator <ipoint100 bool operator<(const ipoint &rhs) const
101 {
102 if(curveindex == rhs.curveindex)
103 {
104 if(vertindex == rhs.vertindex)
105 {
106 return tvalue < rhs.tvalue;
107 }else return vertindex < rhs.vertindex;
108 }else return curveindex < rhs.curveindex;
109 }
110
operator >ipoint111 bool operator>(const ipoint &rhs) const
112 {
113 return rhs < *this;
114 }
115
insert_afteripoint116 void insert_after(ipoint *i)
117 {
118 //from: next - next.prev
119 //to: next* - i - next.prev*
120
121 ipoint *bef = this,
122 *aft = next;
123
124 //assuming the input point is not connected to anything, we don't have to do anything with it...
125 bef->next = i;
126 i->prev = bef;
127 aft->prev = i;
128 i->next = aft;
129 }
130
insert_beforeipoint131 void insert_before(ipoint *i)
132 {
133 //from: prev.next - prev
134 //to: prev.next* - i - prev*
135
136 ipoint *bef = prev,
137 *aft = this;
138
139 //assuming the input point is not connected to anything, we don't have to do anything with it...
140 bef->next = i;
141 i->prev = bef;
142 aft->prev = i;
143 i->next = aft;
144 }
145
insert_sortedipoint146 void insert_sorted(ipoint *i)
147 {
148 ipoint *search = this;
149
150 if(*i < *this)
151 {
152 //we go forward
153 search = this;
154 do
155 {
156 search = search->next;
157 }while(*i < *search && search != this); //ending conditions...
158
159 //now we insert previously...
160 search->insert_before(i);
161 }else if(*i > *this)
162 {
163 //we go backwards...
164 search = this;
165 do
166 {
167 search = search->prev;
168 }while(*i > *search && search != this); //ending conditions...
169
170 //now we insert previously...
171 search->insert_after(i);
172 }
173 }
174 };
175
176 enum SetOp
177 {
178 INTERSECT = 0,
179 UNION,
180 SUBTRACT,
181 INVSUBTRACT,
182 NUM_SETOPERATIONS
183 };
184
185 class PolygonClipper
186 {
187 public:
188 typedef vector<ipoint *> CurveInts; //in no particular order
189
190 vector<CurveInts> c1ints;
191 vector<CurveInts> c2ints;
192
193 //get the intersections
GetIntersections(const CurveSet & lhs,const CurveSet & rhs)194 void GetIntersections(const CurveSet &lhs, const CurveSet &rhs)
195 {
196 CIntersect isect;
197 bezier<Point> b1,b2;
198
199 int i1,j1,ci1,s1;
200 int i2,j2,ci2,s2;
201
202 //clear out so everyone's happy
203 c1ints.clear();
204 c2ints.clear();
205
206 c1ints.resize(lhs.set.size());
207 c2ints.resize(rhs.set.size());
208
209 //loop through everyone and be happy...
210
211 //intersect each curve with each other curve, and we're good
212 for(ci1=0;ci1 < (int)lhs.set.size(); ++ci1)
213 {
214 const CurveSet::region &cur1 = lhs.set[ci1];
215 s1 = cur1.size();
216 for(j1 = s1-1, i1=0; i1 < s1; j1 = i1++)
217 {
218 b1[0] = cur1[j1].p;
219 b1[3] = cur1[i1].p;
220 b1[1] = b1[0] + cur1[j1].r/3;
221 b1[2] = b1[3] - cur1[i1].l/3;
222
223 for(ci2=0;ci2 < (int)rhs.set.size(); ++ci2)
224 {
225 const CurveSet::region &cur2 = rhs.set[ci2];
226 s2 = cur2.size();
227 for(j2 = s2-1, i2=0; i2 < s2; j2 = i2++)
228 {
229 b2[0] = cur2[j2].p;
230 b2[3] = cur2[i2].p;
231 b2[1] = b2[0] + cur2[j2].r/3;
232 b2[2] = b2[3] - cur2[i2].l/3;
233
234 isect(b1,b2);
235
236 for(int index=0; index < (int)isect.times.size(); ++index)
237 {
238 //prepare basic intersection information
239 ipoint *ip1 = new ipoint, *ip2 = new ipoint;
240
241 //set parameters
242 ip1->curveindex = ci1; ip1->vertindex = j1; ip1->tvalue = isect.times[index].first;
243 ip2->curveindex = ci2; ip2->vertindex = j2; ip2->tvalue = isect.times[index].second;
244
245 //set neighbors
246 ip1->neighbor = ip2;
247 ip2->neighbor = ip1;
248
249 //first one just goes on end of list
250 c1ints[ci1].back()->insert_sorted(ip1);
251 c1ints[ci1].push_back(ip1);
252
253 //second one must go in order
254 c2ints[ci2].back()->insert_sorted(ip2);
255 c2ints[ci2].push_back(ip2);
256
257 //we're all good...
258 }
259 }
260 }
261 }
262 }
263
264 //Now figure out the containment properties of each int point
265 Point p;
266 int inside = 0;
267 for(int i = 0; i < (int)c1ints.size(); ++i)
268 {
269 if(c1ints[i].size() == 0) continue;
270
271 //must test insideness for the edges
272 ipoint *start, *iter;
273 start = iter = c1ints[i].front();
274
275 //i == iter->curveindex == the index of the current curve we're looking at
276
277 //set the initial insideness on the other curve...
278 p = lhs.set[i][iter->vertindex].p;
279 inside = rhs.intersect(p)%2; //if it's inside by the even odd rule
280
281 do
282 {
283 iter->go_in = inside? -1 : 1; //leaving if inside, or coming in if not
284 inside = !inside;
285 iter = iter->next;
286 }while(iter != start); //I hope this isn't an infinite loop!
287 }
288
289 //and curve 2
290 for(int i = 0; i < (int)c2ints.size(); ++i)
291 {
292 if(c2ints[i].size() == 0) continue;
293
294 //must test insideness for the edges
295 ipoint *start, *iter;
296 start = iter = c1ints[i].front();
297
298 //set the initial insideness on the other curve...
299 p = rhs.set[i][iter->vertindex].p;
300 inside = lhs.intersect(p)%2; //if it's inside by the even odd rule
301
302 do
303 {
304 iter->go_in = inside? -1 : 1; //leaving if inside, or coming in if not
305 inside = !inside;
306 iter = iter->next;
307 }while(iter != start); //I hope this isn't an infinite loop!
308 }
309 }
310
ConstructSet(CurveSet &,const CurveSet & lhs,const CurveSet & rhs,int type)311 bool ConstructSet(CurveSet &/*c*/, const CurveSet &lhs, const CurveSet &rhs, int type)
312 {
313 bool in1,in2;
314
315 switch(type)
316 {
317 case INTERSECT: //1&2
318 {
319 in1 = true; in2 = true;
320 break;
321 }
322
323 case UNION: //1|2
324 {
325 in1 = false; in2 = false;
326 break;
327 }
328
329 case SUBTRACT: //1-2
330 {
331 in1 = true; in2 = false;
332 break;
333 }
334
335 case INVSUBTRACT: //2-1
336 {
337 in1 = false; in2 = true;
338 break;
339 }
340
341 default:
342 {
343 return false;
344 }
345 }
346
347 //traverse path based on inside flags
348
349 //fill all the paths of native stuff
350 set<ipoint *> ipset;
351 for(int ci=0; ci<(int)c1ints.size(); ++ci)
352 {
353 for(int i=0; i < (int)c1ints[ci].size(); ++i)
354 {
355 ipset.insert(c1ints[ci][i]);
356 }
357 }
358
359 //
360 while(ipset.size() > 0)
361 {
362 //start from one point (always on curveset 1) and traverse until we find it again
363 ipoint *start, *iter;
364 start = iter = *ipset.begin();
365
366 //All the info to swap when we transition curves...
367 const CurveSet *cur, *other;
368 bool curin, otherin;
369 bool delcur = true;
370
371 set<ipoint *>::iterator deliter;
372
373 //int ci,i1,i2,size;
374 //float t1,t2;
375
376 CurveSet::region current;
377 CurvePoint cp;
378
379 cur = &lhs; other = &rhs;
380 curin = in1; otherin = in2;
381 delcur = true;
382
383 do
384 {
385 //remove the current iter from the set
386 if(delcur)
387 {
388 deliter = ipset.find(iter);
389 if(deliter != ipset.end()) ipset.erase(deliter);
390 }
391
392 //go to next and accumulate information
393 //ci = iter->curveindex;
394 //i1 = iter->vertindex;
395 //t1 = iter->tvalue;
396 iter = iter->next; //move to next and get its info
397
398 //i2 = iter->vertindex;
399 //t2 = iter->tvalue;
400
401 //size = cur->set[ci].size();
402
403 //record all the stuff between us...
404 //start on an intersection - get the curve point...
405
406
407 //transition curves...
408 iter = iter->neighbor;
409 swap(cur,other);
410 swap(curin,otherin);
411 delcur = !delcur;
412 }while(iter != start); //I hope THIS isn't an infinite loop
413 }
414
415 return true;
416 }
417 };
418
SetClamp(int & i,int & si)419 void CurveSet::SetClamp(int &i, int &si)
420 {
421 if(si > 0 && si < (int)set.size())
422 {
423 if(i >= (int)set[si].size())
424 {
425 i -= set[si].size();
426 si++;
427 }else if (i < 0)
428 {
429 i += set[si].size();
430 si--;
431 }
432 }
433 }
434
CleanUp(int)435 void CurveSet::CleanUp(int /*curve*/)
436 {
437 }
438
439 /* Detect intersections that are crazy happy good
440
441 Performance annoyances:
442 1) Recursing down to find an intersection at the end points that doesn't actually exist
443 (can be helped a bit by not including the edges of bounding rectangles)
444 2) Intersecting curves is slow... oh well
445
446 Algorithm:
447 1) Inside out scheme, track when edges go into and come out of various objects etc.
448
449 + doesn't require initial conditions
450 - only works with odd-even rule
451 */
452
operator &(const CurveSet &) const453 CurveSet CurveSet::operator&(const CurveSet &/*rhs*/) const
454 {
455 return *this;
456 }
457
operator |(const CurveSet &) const458 CurveSet CurveSet::operator|(const CurveSet &/*rhs*/) const
459 {
460 return *this;
461 }
462
operator -(const CurveSet &) const463 CurveSet CurveSet::operator-(const CurveSet &/*rhs*/) const
464 {
465 return *this;
466 }
467
intersect(const Point & p) const468 int CurveSet::intersect(const Point &p) const
469 {
470 int inter = 0, ci,i,j,s;
471 bezier<Point> b;
472
473 for(ci=0; ci < (int)set.size(); ++ci)
474 {
475 const vector<CurvePoint> &curve = set[ci];
476 s = curve.size();
477 for(j=s-1,i=0; i < s; j = i++)
478 {
479 b[0] = curve[j].p; b[3] = curve[i].p;
480 b[1] = b[0] + curve[j].r/3; b[2] = b[3] - curve[i].l/3;
481
482 inter += synfig::intersect(b,p);
483 }
484 }
485
486 return inter;
487 }
488