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