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 }