Powerstroke LPE causes system lock up

Bug #1593963 reported by David Lee on 2016-06-18
10
This bug affects 2 people
Affects Status Importance Assigned to Milestone
Inkscape
High
Alvin Penner

Bug Description

Im using the latest trunk build 1:0.91.0+devel+14995+76~ubuntu16.10.1 (or the .92pre1 build if you like).

Applying the power stroke effect to a 2 node path works fine. Adding a 3rd node works also. However adding a 4th node (or applying the live effect to a path with 4 or more nodes) causes the path to become editable. Attempting to select the nodes and do anything with them causes Inkscape to lock up the entire operating system (in this case linux).

I should add, I can ctrl+esc to bring up the system monitor, use tab and alt+e to kill Inkscape and then the os goes right back to working just fine.
Show less
1

Jabiertxof (jabiertxof) wrote :

Coulden't reproduce in Debian Testing with r.14995 with a clean document, a path with 8 nodes and apply the LPE. I could move the nodes of the path and the powerstroke with normality.

Jabiertxof (jabiertxof) wrote :

Only a fast test :(

su_v (suv-lp) on 2016-06-19
tags: added: livepatheffects
su_v (suv-lp) wrote :

Reproduced with Inkscape 0.92pre1 (prerelease tarball) and latest trunk r14995 on OS X 10.7.5.

One trigger here (based on a few quick tests) seems to be cusp end nodes (with retracted handles) of curved segments (e.g. a 3-node path drawn with the pen tool (mode: bezier path; shape: None), with a smooth node in the middle, and cusp nodes (no extracted handles) as start and end node): either Inkscape freezes immediately when applying the path effect, or later when dragging start and end nodes a few times with the mouse after having adjusted the width with one of the powerstroke knots.

Changed in inkscape:
status: New → Confirmed
Jabiertxof (jabiertxof) wrote :

Thanks su_v!, finaly I could reproduce.

I go trougth the code and seems to be a 2GEOM problem here:
sbasis-to-bezier.cpp:478 in the tail_error comparsion. Give a recursive infinite loop.

Anyway in d2-sbasis.cpp on line 60 there is a TODO in the tail_error function.
I think it overload my math :(.

Jabiertxof (jabiertxof) wrote :

Also notice first segment -D2<sbasis>- has a size of 4. If the first handle is retracted the size becomes 3. No?

jazzynico (jazzynico) wrote :

Reproduced on Xubuntu 16.04, Inkscape trunk rev.14997.

Changed in inkscape:
status: Confirmed → Triaged
Alvin Penner (apenner) wrote :

since rev 14991 it has become more difficult to reproduce this hangup, thanks Jabiertxof!
using current rev 15001, it is still possible to produce a hangup, but the cause seems to have changed.
attached is a diff file which was used for monitoring the data during a hangup. The diff file does not modify anything, just dumps out a lot of data.

Alvin Penner (apenner) wrote :

during a typical hangup the following was observed, see the attached file:
1. the hangup consists of an unending set of recursive calls to 'build_from_sbasis'. These recursive calls are quite rare, except during a hangup.
2. during these recursive calls, the typical sbasis input consists of extremely large numbers, for example '2.12501e+110'.
3. the large numbers originate instantaneously, that is, there is no gradual build-up, just an instantaneous blow-up.
3. the large numbers seem to originate from the function 'compose(n,x)' in the routine 'LPEPowerStroke::doEffect_path'. Attached is a typical printout of the functions 'n' and 'x' and 'compose(n,x)'.

- 'n' appears to be well-behaved, size = 22, bounds = Rect Interval(-1.00172, 1.22372) x Interval(-0.729082, 1.23441)
- 'x' is well-behaved, size = 1, bounds = Interval(0, 2)
- 'compose(n,x)' is badly behaved, size = 24, bounds = Rect Interval(-1.60631e+111, 1.67324e+111) x Interval(-9.89332e+110, 1.03055e+111)

4. it is interesting to note that _only_ the first term, compose(n,x)[0], is badly behaved, all the higher order terms, [i>0], are well-behaved.
5. not sure if it is relevant, but n is of type <D2>, while x is not.

Alvin Penner (apenner) wrote :

attached is an improved diff file for monitoring the hang-up. This one adds some new output from the 'compose' operation in order to check for divide-by-zero during the compose.

Alvin Penner (apenner) wrote :

attached is a typical output after a hang-up occurs.
The hang-up is preceded by the output line:

compose(Piecewise<T>, SBasis) denom = 1, 1.63884e-017, 2.45825e-017, 8.19418e-018

which means that f.cuts[1] and f.cuts[2] are both zero in line 803 of the file 'piecewise.h'. This leads to division by zero, which triggers the hangup.

Jabiertxof (jabiertxof) wrote :

Hi Alvin, thanks for your efforts. One question, you don't notice an infinite loop on sbasis-to-bezier.cpp:478

Jabiertxof (jabiertxof) wrote :

?

Jabiertxof (jabiertxof) wrote :

seems this condition never happends:
if(tail_error(B, 3) < tol || sbasis_size(B) == 2) {

Alvin Penner (apenner) wrote :

yes there is an infinite loop at sbasis-to-bezier.cpp:478, but it is triggered by the division by zero in compose(). The division by zero causes the sbasis to become extremely large, like 1e+110. This in turn causes an infinite recursion loop in sbasis-to-Bezier.

Jabiertxof (jabiertxof) wrote :

We can force a non zero value?

Jabiertxof (jabiertxof) wrote :

trying to comile with:
if (!are_near(t0,t1,EPSILON)) {
instead
if (!are_near(t0,t1,EPSILON*EPSILON)) {

Jabiertxof (jabiertxof) wrote :

this dont fix it :(

Jabiertxof (jabiertxof) wrote :

now trying if (!are_near(t0,t1,EPSILON*EPSILON) && f.cuts[idx+1]-f.cuts[idx] > EPSILON*EPSILON) {

Jabiertxof (jabiertxof) wrote :

Hi Alvin, not sure if is the best way but it works. Please commit you if is OK, you made the hard thing!

Alvin Penner (apenner) wrote :

personally, I think the fix needs to be made upstream, in the calculation of f.cuts[idx]. The f.cuts data is clearly bad, and should not be allowed to reach the compose() routine in the first place.
I assume that the reason it is bad is because the Bezier handles are retracted, which means that the normal first derivatives are zero, and one needs to use something like the chain rule to evaluate the response. In any event, this is an analytical problem which needs to be addressed upstream.

just my 2cents...

Jabiertxof (jabiertxof) wrote :

Sure you are ok!

Alvin Penner (apenner) wrote :

attached is a proposed patch for this bug.
while monitoring the input and output from RescaleForNonVanishingEnds(), it was found that the hangup was always preceded by receiving an SBasis of the type:

unitVector(D2<SBasis>) in = X: {-1.77636e-015, -6.23616e-031}s^0 Y: {-1.73856e-015, -4.68656e-015}s^0

- since this is essentially zero, the tolerance was introduced to recognize that it is zero.
- with this change, I can no longer reproduce the hangup.

su_v (suv-lp) wrote :

@JazzyNico - would you consider setting the milestone for this report to 0.92 until there's a fix committed? AFAICT it's a regression compared to current stable 0.91 (not affected with known STR), and due to the risk of dataloss (it's not easily possible to save the current drawing once Inkscape hangs) it seems quite important to have the issue addressed before the next release (both in lib2geom and in inkscape).

jazzynico (jazzynico) on 2016-06-28
Changed in inkscape:
milestone: none → 0.92
importance: Undecided → High
tags: added: regression
Jabiertxof (jabiertxof) wrote :

Great patch! Thanks Alvin!
Saccesfuly try on debian Stretch r15002
Note: the patch coulden't be applied directly because sbasis-geometric.cpp_org

Alvin Penner (apenner) wrote :

good to hear, committed to Inkscape rev 15003

if there is no adverse reaction, I'll commit this to 2geom in a few days

Alvin Penner (apenner) wrote :
jazzynico (jazzynico) on 2016-11-02
Changed in inkscape:
status: Triaged → Fix Committed
assignee: nobody → Alvin Penner (apenner)
Bryce Harrington (bryce) on 2017-01-10
Changed in inkscape:
status: Fix Committed → Fix Released
To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers