src/live_effects/lpe-knot.cpp

   1 #define INKSCAPE_LPE_KNOT_CPP
   2 /** \file
   3  * LPE <knot> implementation
   4  */
   5 /*
   6  * Authors:
   7  *   JF Barraud
   8 *
   9 * Copyright (C) JF Barraud 2007 <jf.barraud@gmail.com>
  10  *
  11  * Released under GNU GPL, read the file 'COPYING' for more information
  12  */
  13
  14 #include "sp-shape.h"
  15 #include "display/curve.h"
  16 #include "live_effects/lpe-knot.h"
  17 #include "svg/svg.h"
  18
  19 #include <2geom/sbasis-to-bezier.h>
  20 #include <2geom/sbasis.h>
  21 #include <2geom/d2.h>
  22 #include <2geom/d2-sbasis.h>
  23 #include <2geom/piecewise.h>
  24 #include <2geom/piecewise.h>
  25 #include <2geom/path.h>
  26 #include <2geom/d2.h>
  27 #include <2geom/crossing.h>
  28 #include <2geom/path-intersection.h>
  29 #include <2geom/elliptical-arc.h>
  30
  31 namespace Inkscape {
  32 namespace LivePathEffect {
  33
  34 class KnotHolderEntityCrossingSwitcher : public LPEKnotHolderEntity
  35 {
  36 public:
  37     virtual void knot_set(Geom::Point const &p, Geom::Point const &origin, guint state);
  38     virtual Geom::Point knot_get();
  39     virtual void knot_click(guint state);
  40 };
  41
  42
  43 //---------------------------------------------------------------------------
  44 //LPEKnot specific Interval manipulation.
  45 //---------------------------------------------------------------------------
  46
  47 //remove an interval from an union of intervals.
  48 //TODO: is it worth moving it to 2Geom?
  49 static
  50 std::vector<Geom::Interval> complementOf(Geom::Interval I, std::vector<Geom::Interval> domain){
  51     std::vector<Geom::Interval> ret;
  52     double min = domain.front().min();
  53     double max = domain.back().max();
  54     Geom::Interval I1 = Geom::Interval(min,I.min());
  55     Geom::Interval I2 = Geom::Interval(I.max(),max);
  56
  57     for (unsigned i = 0; i<domain.size(); i++){
  58         boost::optional<Geom::Interval> I1i = intersect(domain.at(i),I1);
  59         if (I1i) ret.push_back(I1i.get());
  60         boost::optional<Geom::Interval> I2i = intersect(domain.at(i),I2);
  61         if (I2i) ret.push_back(I2i.get());
  62     }
  63     return ret;
  64 }
  65
  66 //find the time interval during which patha is hidden by pathb near a given crossing.
  67 // Warning: not accurate!
  68 static
  69 Geom::Interval
  70 findShadowedTime(Geom::Path const &patha,
  71                  Geom::Path const &pathb,
  72                  Geom::Crossing const &crossing,
  73                  unsigned idx, double width){
  74     using namespace Geom;
  75     double curveidx, timeoncurve = modf(crossing.getOtherTime(idx),&curveidx);
  76     if(curveidx == pathb.size() ) { curveidx--; timeoncurve = 1.;}//FIXME: 0.99999; needed?
  77     assert(curveidx >= 0 && curveidx < pathb.size());
  78
  79     std::vector<Point> MV = pathb[unsigned(curveidx)].pointAndDerivatives(timeoncurve,1);
  80     Point T = unit_vector(MV.at(1));
  81     Point N = T.cw();
  82     Point A = MV.at(0)-3*width*T, B = MV.at(0)+3*width*T;
  83
  84     std::vector<Geom::Path> cutter;
  85     Geom::Path cutterPath(A-width*N);
  86     cutterPath.appendNew<LineSegment> (B-width*N);
  87     cutterPath.appendNew<LineSegment> (B+width*N);
  88     cutterPath.appendNew<LineSegment> (A+width*N);
  89     cutterPath.close();
  90     //cutterPath.appendNew<LineSegment> (A-width*N);
  91     cutter.push_back(cutterPath);
  92
  93     std::vector<Geom::Path> patha_as_vect = std::vector<Geom::Path>(1,patha);
  94
  95     CrossingSet crossingTable = crossings (patha_as_vect, cutter);
  96     double t0 = crossing.getTime(idx);
  97     double tmin = 0,tmax = patha.size();//-0.00001;FIXME: FIXED?
  98     assert(crossingTable.size()>=1);
  99     for (unsigned c=0; c<crossingTable.front().size(); c++){
 100         double t = crossingTable.front().at(c).ta;
 101         assert(crossingTable.front().at(c).a==0);
 102         if (t>tmin and t<t0) tmin = t;
 103         if (t<tmax and t>t0) tmax = t;
 104     }
 105     return Interval(tmin,tmax);
 106 }
 107
 108 //---------------------------------------------------------------------------
 109 // a 2Geom work around.
 110 //---------------------------------------------------------------------------
 111
 112 //Cubic Bezier curves might self intersect; the 2geom code used to miss them.
 113 //This is a quick work around; maybe not needed anymore? -- TODO: check!
 114 //TODO/TOCHECK/TOFIX: I think the BUG is in path-intersection.cpp -> curve_mono_split(...):
 115 //the derivative of the curve should be used instead of the curve itself.
 116 std::vector<Geom::Path>
 117 split_at_horiz_vert_tgt (std::vector<Geom::Path> const & path_in){
 118     std::vector<Geom::Path> ret;
 119
 120     using namespace Geom;
 121
 122     Piecewise<D2<SBasis> > f = paths_to_pw(path_in);
 123     D2<Piecewise<SBasis> > df = make_cuts_independent(derivative(f));
 124     std::vector<double> xyroots = roots(df[X]);
 125     std::vector<double> yroots = roots(df[Y]);
 126     xyroots.insert(xyroots.end(), yroots.begin(), yroots.end());
 127     std::sort(xyroots.begin(),xyroots.end());
 128     Piecewise<D2<SBasis> > newf = partition(f,xyroots);
 129     ret = path_from_piecewise(newf,LPE_CONVERSION_TOLERANCE);
 130
 131     return ret;
 132 }
 133
 134
 135 //---------------------------------------------------------------------------
 136 //LPEKnot specific Crossing Data manipulation.
 137 //---------------------------------------------------------------------------
 138
 139 //TODO: Fix this in 2Geom: I think CrossingSets should not contain duplicates.
 140 Geom::CrossingSet crossingSet_remove_double(Geom::CrossingSet const &input){
 141     Geom::CrossingSet result(input.size());
 142     //Yeah, I know, there is a "unique" algorithm for that...
 143     Geom::Crossing last;
 144     for( unsigned i=0; i<input.size(); i++){
 145         for( unsigned j=0; j<input[i].size(); j++){
 146             if( j==0 || !(input[i][j]==last) ){
 147                 result[i].push_back(input[i][j]);
 148                 last = input[i][j];
 149             }else{
 150                 g_warning("Duplicate found in a Geom::CrossingSet!");
 151             }
 152         }
 153     }
 154     return result;
 155 }
 156
 157 //TODO: evaluate how usefull/lpeknot specific that is. Worth being moved to 2geom? (I doubt it)
 158 namespace LPEKnotNS {
 159
 160 //Yet another crossing data representation. Not sure at all it is usefull!
 161 // +: >Given a point, you immediately know which strings are meeting there,
 162 //    and the index of the crossing along each string. This makes it easy to check
 163 //    topology change. In a CrossingSet, you have to do some search to know the index
 164 //    of the crossing along "the second" string (i.e. find the symetric crossing)...
 165 //    >Each point is stored only once.
 166 //    However, we don't have so many crossing points in general, so none of these points might be relevant.
 167 //
 168 // -: one more clumsy data representation, and "parallelism" failures to expect...
 169 //    (in particular, duplicates are hateful with this respect...)
 170
 171 CrossingPoints::CrossingPoints(Geom::CrossingSet const &input, std::vector<Geom::Path> const &path) : std::vector<CrossingPoint>()
 172 {
 173     using namespace Geom;
 174     g_print("JF>\nCrossing set content:\n");
 175     for( unsigned i=0; i<input.size(); i++){
 176         Crossings i_crossings = input[i];
 177         for( unsigned n=0; n<i_crossings.size(); n++ ){
 178             Crossing c = i_crossings[n];
 179             g_print("JF> (%u,%u) at times (%f,%f) ----->",c.a,c.b,c.ta,c.tb);
 180             unsigned j = c.getOther(i);
 181             if (i<j || (i==j && c.ta<c.tb) ){
 182                 CrossingPoint cp;
 183                 cp.pt = path[i].pointAt(c.getTime(i));
 184                 cp.i = i;
 185                 cp.j = j;
 186                 cp.ni = n;
 187                 Crossing c_bar = c;
 188                 if (i==j){
 189                     c_bar.a  = c.b;
 190                     c_bar.b  = c.a;
 191                     c_bar.ta = c.tb;
 192                     c_bar.tb = c.ta;
 193                     c_bar.dir = !c.dir;
 194                 }
 195                 cp.nj = std::find(input[j].begin(),input[j].end(),c_bar)-input[j].begin();
 196                 cp.sign = 1;
 197                 push_back(cp);
 198                 g_print("i=%u, ni=%u, j=%u, nj=%u\n",cp.i,cp.ni,cp.j,cp.nj);
 199             }
 200             else{
 201                 g_print("\n");
 202                 bool found = false;
 203                 for( unsigned ii=0; ii<input.size(); ii++){
 204                     Crossings ii_crossings = input[ii];
 205                     for( unsigned nn=0; nn<ii_crossings.size(); nn++ ){
 206                         Crossing cc = ii_crossings[nn];
 207                         if (cc.b==c.a && cc.a==c.b && cc.ta==c.tb && cc.tb==c.ta) found = true;
 208                     }
 209                 }
 210                 assert( found );
 211             }
 212         }
 213     }
 214 }
 215
 216 CrossingPoints::CrossingPoints(std::vector<double> const &input) : std::vector<CrossingPoint>()
 217 {
 218     if (input.size()>0 && input.size()%7 ==0){
 219         using namespace Geom;
 220         for( unsigned n=0; n<input.size();  ){
 221             CrossingPoint cp;
 222             cp.pt[X] = input[n++];
 223             cp.pt[Y] = input[n++];
 224             cp.i = input[n++];
 225             cp.j = input[n++];
 226             cp.ni = input[n++];
 227             cp.nj = input[n++];
 228             cp.sign = input[n++];
 229             push_back(cp);
 230         }
 231     }
 232 }
 233
 234 std::vector<double>
 235 CrossingPoints::to_vector()
 236 {
 237     using namespace Geom;
 238     std::vector<double> result;
 239     for( unsigned n=0; n<size(); n++){
 240         CrossingPoint cp = (*this)[n];
 241         result.push_back(cp.pt[X]);
 242         result.push_back(cp.pt[Y]);
 243         result.push_back(double(cp.i));
 244         result.push_back(double(cp.j));
 245         result.push_back(double(cp.ni));
 246         result.push_back(double(cp.nj));
 247         result.push_back(double(cp.sign));
 248     }
 249     return result;
 250 }
 251
 252 //FIXME: rewrite to check success: return bool, put result in arg.
 253 CrossingPoint
 254 CrossingPoints::get(unsigned const i, unsigned const ni)
 255 {
 256     for (unsigned k=0; k<size(); k++){
 257         if (
 258             ((*this)[k].i==i && (*this)[k].ni==ni) ||
 259             ((*this)[k].j==i && (*this)[k].nj==ni)
 260             ) return (*this)[k];
 261     }
 262     g_warning("LPEKnotNS::CrossingPoints::get error. %uth crossing along string %u not found.",ni,i);
 263     assert(false);//debug purpose...
 264     return CrossingPoint();
 265 }
 266
 267 unsigned
 268 idx_of_nearest(CrossingPoints const &cpts, Geom::Point const &p)
 269 {
 270     double dist=-1;
 271     unsigned result = cpts.size();
 272     for (unsigned k=0; k<cpts.size(); k++){
 273         double dist_k = Geom::L2(p-cpts[k].pt);
 274         if (dist<0 || dist>dist_k){
 275             result = k;
 276             dist = dist_k;
 277         }
 278     }
 279     return result;
 280 }
 281
 282 //TODO: Find a way to warn the user when the topology changes.
 283 //TODO: be smarter at guessing the signs when the topology changed?
 284 void
 285 CrossingPoints::inherit_signs(CrossingPoints const &other, int default_value)
 286 {
 287     bool topo_changed = false;
 288     for (unsigned n=0; n<size(); n++){
 289         if ( n<other.size() &&
 290              other[n].i  == (*this)[n].i  &&
 291              other[n].j  == (*this)[n].j  &&
 292              other[n].ni == (*this)[n].ni &&
 293              other[n].nj == (*this)[n].nj    )
 294         {
 295             (*this)[n].sign = other[n].sign;
 296         }else{
 297             topo_changed = true;
 298             break;
 299         }
 300     }
 301     if (topo_changed){
 302         //TODO: Find a way to warn the user!!
 303         for (unsigned n=0; n<size(); n++){
 304             Geom::Point p = (*this)[n].pt;
 305             unsigned idx = idx_of_nearest(other,p);
 306             if (idx<other.size()){
 307                 (*this)[n].sign = other[idx].sign;
 308             }else{
 309                 (*this)[n].sign = default_value;
 310             }
 311         }
 312     }
 313 }
 314
 315 }
 316
 317 //---------------------------------------------------------------------------
 318 //---------------------------------------------------------------------------
 319 //LPEKnot effect.
 320 //---------------------------------------------------------------------------
 321 //---------------------------------------------------------------------------
 322
 323
 324 LPEKnot::LPEKnot(LivePathEffectObject *lpeobject) :
 325     Effect(lpeobject),
 326     // initialise your parameters here:
 327     interruption_width(_("Gap width"), _("The width of the gap in the path where it self-intersects"), "interruption_width", &wr, this, 10),
 328     switcher_size(_("Switcher size"), _("Orientation indicator/switcher size"), "switcher_size", &wr, this, 15),
 329     crossing_points_vector(_("Crossing Signs"), _("Crossings signs"), "crossing_points_vector", &wr, this)
 330 {
 331     // register all your parameters here, so Inkscape knows which parameters this effect has:
 332     registerParameter( dynamic_cast<Parameter *>(&interruption_width) );
 333     registerParameter( dynamic_cast<Parameter *>(&switcher_size) );
 334     registerParameter( dynamic_cast<Parameter *>(&crossing_points_vector) );
 335
 336     registerKnotHolderHandle(new KnotHolderEntityCrossingSwitcher(), _("Drag to select a crossing, click to flip it"));
 337     crossing_points = LPEKnotNS::CrossingPoints();
 338     selectedCrossing = 0;
 339     switcher = Geom::Point(0,0);
 340 }
 341
 342 LPEKnot::~LPEKnot()
 343 {
 344
 345 }
 346
 347 void
 348 LPEKnot::doOnApply(SPLPEItem *lpeitem)
 349 {
 350     //SPCurve *curve = SP_SHAPE(lpeitem)->curve;
 351     // //TODO: where should the switcher be initialized? (it shows up here if there is no crossing at all)
 352     // //The best would be able to hide it when there is no crossing!
 353     //Geom::Point A = *(curve->first_point());
 354     //Geom::Point B = *(curve->last_point());
 355     //switcher = (A+B)*.5;
 356 }
 357
 358 void
 359 LPEKnot::updateSwitcher(){
 360     if (selectedCrossing < crossing_points.size()){
 361         switcher = crossing_points[selectedCrossing].pt;
 362     }else if (crossing_points.size()>0){
 363         selectedCrossing = 0;
 364         switcher = crossing_points[selectedCrossing].pt;
 365     }else{
 366         //TODO: is there a way to properly hide the helper.
 367         //switcher = Geom::Point(Geom::infinity(),Geom::infinity());
 368         switcher = Geom::Point(1e10,1e10);
 369     }
 370 }
 371
 372 std::vector<Geom::Path>
 373 LPEKnot::doEffect_path (std::vector<Geom::Path> const &input_path)
 374 {
 375     using namespace Geom;
 376     std::vector<Geom::Path> path_out;
 377     double width = interruption_width;
 378
 379     LPEKnotNS::CrossingPoints old_crdata(crossing_points_vector.data());
 380
 381     std::vector<Geom::Path> path_in = split_at_horiz_vert_tgt(input_path);
 382
 383     CrossingSet crossingTable = crossings_among(path_in);
 384
 385     for(unsigned i=0;i<crossingTable.size();i++){
 386         for(unsigned j=0;j<crossingTable[i].size();j++){
 387             g_print("JF>avant: %u,%u,%f,%f\n",crossingTable[i][j].a, crossingTable[i][j].b, crossingTable[i][j].ta, crossingTable[i][j].tb);
 388         }
 389     }
 390     crossingTable = crossingSet_remove_double(crossingTable);
 391
 392     for(unsigned i=0;i<crossingTable.size();i++){
 393         for(unsigned j=0;j<crossingTable[i].size();j++){
 394             g_print("JF>apres: %u,%u,%f,%f\n",crossingTable[i][j].a, crossingTable[i][j].b, crossingTable[i][j].ta, crossingTable[i][j].tb);
 395         }
 396     }
 397
 398     crossing_points = LPEKnotNS::CrossingPoints(crossingTable, path_in);
 399     crossing_points.inherit_signs(old_crdata);
 400     crossing_points_vector.param_set_and_write_new_value(crossing_points.to_vector());
 401     updateSwitcher();
 402
 403     if (crossingTable.size()==0){
 404         return input_path;
 405     }
 406
 407     for (unsigned i = 0; i < crossingTable.size(); i++){
 408         std::vector<Interval> dom;
 409         dom.push_back(Interval(0.,path_in.at(i).size()));//-0.00001));FIX ME: this should not be needed anymore.
 410         for (unsigned n = 0; n < crossingTable.at(i).size(); n++){
 411             Crossing crossing = crossingTable.at(i).at(n);
 412             unsigned j = crossing.getOther(i);
 413
 414             //FIXME: check success...
 415             LPEKnotNS::CrossingPoint crpt;
 416             crpt = crossing_points.get(i,n);
 417             int sign_code = crpt.sign;
 418
 419             if (sign_code!=0){
 420                 bool sign = (sign_code>0 ? true : false);
 421                 Interval hidden;
 422                 if (((crossing.dir==sign) and crossing.a==i) or ((crossing.dir!=sign) and crossing.b==i)){
 423                     if (i==j and (crossing.dir!=sign)) {
 424                     double temp = crossing.ta;
 425                     crossing.ta = crossing.tb;
 426                     crossing.tb = temp;
 427                     crossing.dir = not crossing.dir;
 428                     }
 429                     hidden = findShadowedTime(path_in.at(i),path_in.at(j),crossing,i,width);
 430                 }
 431                 dom = complementOf(hidden,dom);
 432             }
 433         }
 434         for (unsigned comp = 0; comp < dom.size(); comp++){
 435             assert(dom.at(comp).min() >=0 and dom.at(comp).max() <= path_in.at(i).size());
 436             path_out.push_back(path_in.at(i).portion(dom.at(comp)));
 437         }
 438     }
 439     return path_out;
 440 }
 441
 442
 443 static LPEKnot *
 444 get_effect(SPItem *item)
 445 {
 446     Effect *effect = sp_lpe_item_get_current_lpe(SP_LPE_ITEM(item));
 447     if (effect->effectType() != KNOT) {
 448         g_print ("Warning: Effect is not of type LPEKnot!\n");
 449         return NULL;
 450     }
 451     return static_cast<LPEKnot *>(effect);
 452 }
 453
 454 void
 455 LPEKnot::addCanvasIndicators(SPLPEItem */*lpeitem*/, std::vector<Geom::PathVector> &hp_vec)
 456 {
 457     using namespace Geom;
 458      double r = switcher_size*.1;
 459     char const * svgd;
 460     //TODO: use a nice path!
 461     if (selectedCrossing >= crossing_points.size()||crossing_points[selectedCrossing].sign > 0){
 462         //svgd = "M -10,0 A 10 10 0 1 0 0,-10 l  5,-1 -1,2";
 463         svgd = "m -7.07,7.07 c 3.9,3.91 10.24,3.91 14.14,0 3.91,-3.9 3.91,-10.24 0,-14.14 -3.9,-3.91 -10.24,-3.91 -14.14,0 l 2.83,-4.24 0.7,2.12";
 464     }else if (crossing_points[selectedCrossing].sign < 0){
 465         //svgd = "M  10,0 A 10 10 0 1 1 0,-10 l -5,-1  1,2";
 466         svgd = "m 7.07,7.07 c -3.9,3.91 -10.24,3.91 -14.14,0 -3.91,-3.9 -3.91,-10.24 0,-14.14 3.9,-3.91 10.24,-3.91 14.14,0 l -2.83,-4.24 -0.7,2.12";
 467     }else{
 468         //svgd = "M 10,0 A 10 10 0 1 0 -10,0 A 10 10 0 1 0 10,0 ";
 469         svgd = "M 10,0 C 10,5.52 5.52,10 0,10 -5.52,10 -10,5.52 -10,0 c 0,-5.52 4.48,-10 10,-10 5.52,0 10,4.48 10,10 z";
 470     }
 471     PathVector pathv = sp_svg_read_pathv(svgd);
 472     pathv *= Matrix(r,0,0,r,0,0);
 473     pathv+=switcher;
 474     hp_vec.push_back(pathv);
 475 }
 476
 477 void
 478 KnotHolderEntityCrossingSwitcher::knot_set(Geom::Point const &p, Geom::Point const &/*origin*/, guint state)
 479 {
 480     LPEKnot* lpe = get_effect(item);
 481
 482     lpe->selectedCrossing = idx_of_nearest(lpe->crossing_points,p);
 483     lpe->updateSwitcher();
 484 //    if(lpe->selectedCrossing < lpe->crossing_points.size())
 485 //        lpe->switcher = lpe->crossing_points[lpe->selectedCrossing].pt;
 486 //    else
 487 //        lpe->switcher = p;
 488     // FIXME: this should not directly ask for updating the item. It should write to SVG, which triggers updating.
 489     sp_lpe_item_update_patheffect (SP_LPE_ITEM(item), false, true);
 490 }
 491
 492 Geom::Point
 493 KnotHolderEntityCrossingSwitcher::knot_get()
 494 {
 495     LPEKnot* lpe = get_effect(item);
 496     return snap_knot_position(lpe->switcher);
 497 }
 498
 499 void
 500 KnotHolderEntityCrossingSwitcher::knot_click(guint state)
 501 {
 502     LPEKnot* lpe = get_effect(item);
 503     unsigned s = lpe->selectedCrossing;
 504     if (s < lpe->crossing_points.size()){
 505         if (state & GDK_SHIFT_MASK){
 506             lpe->crossing_points[s].sign = 1;
 507         }else{
 508             int sign = lpe->crossing_points[s].sign;
 509             lpe->crossing_points[s].sign = ((sign+2)%3)-1;
 510         }
 511         lpe->crossing_points_vector.param_set_and_write_new_value(lpe->crossing_points.to_vector());
 512
 513         // FIXME: this should not directly ask for updating the item. It should write to SVG, which triggers updating.
 514         sp_lpe_item_update_patheffect (SP_LPE_ITEM(item), false, true);
 515     }
 516 }
 517
 518
 519 /* ######################## */
 520
 521 } //namespace LivePathEffect (setq default-directory "c:/Documents And Settings/jf/Mes Documents/InkscapeSVN")
 522 } /* namespace Inkscape */
 523
 524 /*
 525   Local Variables:
 526   mode:c++
 527   c-file-style:"stroustrup"
 528   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 529   indent-tabs-mode:nil
 530   fill-column:99
 531   End:
 532 */
 533 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :