1 /* === S I N F G =========================================================== */
3 ** \brief Curve Set Implementation File
5 ** $Id: curveset.cpp,v 1.1.1.1 2005/01/04 01:23:14 darco Exp $
8 ** Copyright (c) 2002 Robert B. Quattlebaum Jr.
10 ** This software and associated documentation
11 ** are CONFIDENTIAL and PROPRIETARY property of
12 ** the above-mentioned copyright holder.
14 ** You may not copy, print, publish, or in any
15 ** other way distribute this software without
16 ** a prior written agreement with
17 ** the copyright holder.
20 /* ========================================================================= */
22 /* === H E A D E R S ======================================================= */
31 #include "curve_helper.h"
33 #include "blinepoint.h"
41 /* === U S I N G =========================================================== */
45 using namespace sinfg;
47 /* === M A C R O S ========================================================= */
49 /* === G L O B A L S ======================================================= */
50 const Real ERROR = 1e-10;
52 /* === P R O C E D U R E S ================================================= */
54 /* === M E T H O D S ======================================================= */
56 /* === E N T R Y P O I N T ================================================= */
57 template < typename T >
58 inline bool Zero(const T &a, const T &tol = (T)ERROR)
60 return a < tol && a > -tol;
63 CurvePoint::CurvePoint(const Point &pin, const Vector &left, const Vector &right)
64 :p(pin),l(left),r(right)
68 CurvePoint::CurvePoint(const BLinePoint &bpoint)
70 p = bpoint.get_vertex();
72 l = p + bpoint.get_tangent1()*(1/3.0f);
73 r = p + bpoint.get_tangent2()*(1/3.0f);
86 int go_in; //going in = 1, coming out = -1
95 bool operator<(const ipoint &rhs) const
97 if(curveindex == rhs.curveindex)
99 if(vertindex == rhs.vertindex)
101 return tvalue < rhs.tvalue;
102 }else return vertindex < rhs.vertindex;
103 }else return curveindex < rhs.curveindex;
106 bool operator >(const ipoint &rhs) const
111 void insert_after(ipoint *i)
113 //from: next - next.prev
114 //to: next* - i - next.prev*
119 //assuming the input point is not connected to anything, we don't have to do anything with it...
126 void insert_before(ipoint *i)
128 //from: prev.next - prev
129 //to: prev.next* - i - prev*
134 //assuming the input point is not connected to anything, we don't have to do anything with it...
141 void insert_sorted(ipoint *i)
143 ipoint *search = this;
151 search = search->next;
152 }while(*i < *search && search != this); //ending conditions...
154 //now we insert previously...
155 search->insert_before(i);
162 search = search->prev;
163 }while(*i > *search && search != this); //ending conditions...
165 //now we insert previously...
166 search->insert_after(i);
183 typedef vector<ipoint *> CurveInts; //in no particular order
185 vector<CurveInts> c1ints;
186 vector<CurveInts> c2ints;
188 //get the intersections
189 void GetIntersections(const CurveSet &lhs, const CurveSet &rhs)
197 //clear out so everyone's happy
201 c1ints.resize(lhs.set.size());
202 c2ints.resize(rhs.set.size());
204 //loop through everyone and be happy...
206 //intersect each curve with each other curve, and we're good
207 for(ci1=0;ci1 < (int)lhs.set.size(); ++ci1)
209 const CurveSet::region &cur1 = lhs.set[ci1];
211 for(j1 = s1-1, i1=0; i1 < s1; j1 = i1++)
215 b1[1] = b1[0] + cur1[j1].r/3;
216 b1[2] = b1[3] - cur1[i1].l/3;
218 for(ci2=0;ci2 < (int)rhs.set.size(); ++ci2)
220 const CurveSet::region &cur2 = rhs.set[ci2];
222 for(j2 = s2-1, i2=0; i2 < s2; j2 = i2++)
226 b2[1] = b2[0] + cur2[j2].r/3;
227 b2[2] = b2[3] - cur2[i2].l/3;
231 for(int index=0; index < (int)isect.times.size(); ++index)
233 //prepare basic intersection information
234 ipoint *ip1 = new ipoint, *ip2 = new ipoint;
237 ip1->curveindex = ci1; ip1->vertindex = j1; ip1->tvalue = isect.times[index].first;
238 ip2->curveindex = ci2; ip2->vertindex = j2; ip2->tvalue = isect.times[index].second;
244 //first one just goes on end of list
245 c1ints[ci1].back()->insert_sorted(ip1);
246 c1ints[ci1].push_back(ip1);
248 //second one must go in order
249 c2ints[ci2].back()->insert_sorted(ip2);
250 c2ints[ci2].push_back(ip2);
259 //Now figure out the containment properties of each int point
262 for(int i = 0; i < (int)c1ints.size(); ++i)
264 if(c1ints[i].size() == 0) continue;
266 //must test insideness for the edges
267 ipoint *start, *iter;
268 start = iter = c1ints[i].front();
270 //i == iter->curveindex == the index of the current curve we're looking at
272 //set the initial insideness on the other curve...
273 p = lhs.set[i][iter->vertindex].p;
274 inside = rhs.intersect(p)%2; //if it's inside by the even odd rule
278 iter->go_in = inside? -1 : 1; //leaving if inside, or coming in if not
281 }while(iter != start); //I hope this isn't an infinite loop!
285 for(int i = 0; i < (int)c2ints.size(); ++i)
287 if(c2ints[i].size() == 0) continue;
289 //must test insideness for the edges
290 ipoint *start, *iter;
291 start = iter = c1ints[i].front();
293 //set the initial insideness on the other curve...
294 p = rhs.set[i][iter->vertindex].p;
295 inside = lhs.intersect(p)%2; //if it's inside by the even odd rule
299 iter->go_in = inside? -1 : 1; //leaving if inside, or coming in if not
302 }while(iter != start); //I hope this isn't an infinite loop!
306 bool ConstructSet(CurveSet &c, const CurveSet &lhs, const CurveSet &rhs, int type)
312 case INTERSECT: //1&2
314 in1 = true; in2 = true;
320 in1 = false; in2 = false;
326 in1 = true; in2 = false;
330 case INVSUBTRACT: //2-1
332 in1 = false; in2 = true;
342 //traverse path based on inside flags
344 //fill all the paths of native stuff
346 for(int ci=0; ci<(int)c1ints.size(); ++ci)
348 for(int i=0; i < (int)c1ints[ci].size(); ++i)
350 ipset.insert(c1ints[ci][i]);
355 while(ipset.size() > 0)
357 //start from one point (always on curveset 1) and traverse until we find it again
358 ipoint *start, *iter;
359 start = iter = *ipset.begin();
361 //All the info to swap when we transition curves...
362 const CurveSet *cur, *other;
366 set<ipoint *>::iterator deliter;
371 CurveSet::region current;
374 cur = &lhs; other = &rhs;
375 curin = in1; otherin = in2;
380 //remove the current iter from the set
383 deliter = ipset.find(iter);
384 if(deliter != ipset.end()) ipset.erase(deliter);
387 //go to next and accumulate information
388 ci = iter->curveindex;
389 i1 = iter->vertindex;
391 iter = iter->next; //move to next and get its info
393 i2 = iter->vertindex;
396 size = cur->set[ci].size();
398 //record all the stuff between us...
399 //start on an intersection - get the curve point...
402 //transition curves...
403 iter = iter->neighbor;
407 }while(iter != start); //I hope THIS isn't an infinite loop
414 void CurveSet::SetClamp(int &i, int &si)
416 if(si > 0 && si < (int)set.size())
418 if(i >= (int)set[si].size())
430 void CurveSet::CleanUp(int curve)
434 /* Detect intersections that are crazy happy good
436 Performance annoyances:
437 1) Recursing down to find an intersection at the end points that doesn't actually exist
438 (can be helped a bit by not including the edges of bouding rectaingles)
439 2) Intersecting curves is slow... oh well
442 1) Inside out scheme, track when edges go into and come out of various objects etc.
444 + doesn't require initial conditions
445 - only works with odd-even rule
448 CurveSet CurveSet::operator &(const CurveSet &rhs) const
453 CurveSet CurveSet::operator |(const CurveSet &rhs) const
458 CurveSet CurveSet::operator -(const CurveSet &rhs) const
463 int CurveSet::intersect(const Point &p) const
465 int inter = 0, ci,i,j,s;
468 for(ci=0; ci < (int)set.size(); ++ci)
470 const vector<CurvePoint> &curve = set[ci];
472 for(j=s-1,i=0; i < s; j = i++)
474 b[0] = curve[j].p; b[3] = curve[i].p;
475 b[1] = b[0] + curve[j].r/3; b[2] = b[3] - curve[i].l/3;
477 inter += sinfg::intersect(b,p);