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