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