inkscape hangs when snapping to path intersections with large number of clipped objects

[vlad seghete]

Using Inkscape 0.48.2 r9819 on OS X (pre-built package).

When I open the attached file Inkscape behaves sluggishly. I imagine this is because it contains a large number of nodes, although there are probably only around a few thousand points in the plot, and that shouldn't have an impact on CPU performance. Then, I turn on snapping to intersections and try and draw a horizontal line between the two tick marks above the blue region and below the green (snapping at the intersection of the tick marks with the graph boundaries). Right before I finish drawing the line Inkscape hangs and starts using 100% CPU.

I did not get a backtrace because when running inkscape inside gdb all fonts get replaced by empty squares and icons by a not found symbol. I don't know if that's an issue with gdb on my system or Inkscape on OS X.

[su_v (suv-lp)]

<off-topic>
> I did not get a backtrace because when running inkscape inside gdb all fonts
> get replaced by empty squares and icons by a not found symbol. I don't
> know if that's an issue with gdb on my system or Inkscape on OS X.

The bundled version is not really easy (and not intended) to be used on the command line (even more so with gdb) unless you now the inner structure of the application package and which of the nested shell script sets which environment variables before executing the actual binary (Contents/Resources/bin/inkscape-bin) - if you intend to debug inkscape, install the cli version via MacPorts. Otherwise - the crash report saved by the system (~/Library/Logs/CrashReporter or ~/Library/Logs/DiagnosticReports for 'inkscape-bin') if the process actually segfaults does always include a backtrace: <http://developer.apple.com/library/mac/#technotes/tn2004/tn2123.html> has more information (even if outdated, the basics still apply as far as I know).
</off-topic>

[su_v (suv-lp)]

Could you provide more information about the PDF? Are you round-trip editing it in Inkscape or was it created by a third-party application which also uses cairo 1.10.2 to export to PDF?

[su_v (suv-lp)]

> When I open the attached file Inkscape behaves sluggishly.

Most likely because each data point is clipped with a page-sized clip-path. Which tool created the PDF?

> Then, I turn on snapping to intersections and try and draw
> a horizontal line between the two tick marks above the
> blue region and below the green

Snapping to intersections of paths is the snapping option which by nature will be slow and result in "poor" performance because it requires lots of calculations to determine possible snap candidates (AFAIU. Maybe Diederik will explain…) Why don't you simply snap to cusp nodes and connect the end nodes of the two tick marks? (work fine for me with Inkscape 0.48.2 on Mac OS X 10.5.8 (i386), without inkscape hanging with 100% CPU usage.

[su_v (suv-lp)]

> Most likely because each data point is clipped (…)

It is even clipped twice (on nested groups which wrap the actual object used to symbolize the data point): the outer clip has the size of the visual bbox of the marker (circle), the inner clip has the size of the page. This structure is repeated for each of the red, green and blue dots (2008 total, each of them a path with 8 nodes).

[su_v (suv-lp)]

Attaching an SVG version of the PDF, with the content split into layers, and most nested group levels resolved (only the parent group for each color does have a clip to limit the dots to the page area).

Done with Inkscape 0.48.2 on Mac OS X 10.5.8 (i396) (MBP Intel C2D, 2.4 GHz, 2 GB RAM) - most while running inkscape inside gdb. The repeated ungrouping and moving the resulting paths to a new layer does take its time of course (vacuuming the defs afterwards to get rid of the clip-paths is quite fast OTOH) .

After splitting the content onto different layers, the lines on the layer 'grid' have been created with the pencil tool, snapping to path intersections (without hangs) - with the layers of the red/green/blue data points hidden, to avoid unnecessary snap candidates ;)

[vlad seghete (vloodo)]

I made the figure with matplotlib's PDF backend and using default options. Maybe I'd have more luck with saving to SVG? I don't really want to dig through the pyplot documentation to figure out why they save things this way, but if this becomes a frequent issue I might have to do that.

I am running Snow Leopard , but other than that our systems seem to be pretty much identical, so I don't know why it would consistently hang on mine and not yours. I haven't tried the MacPorts version of Inkscape yet, I'm hoping to get around to that as soon as possible. I had already found a few workarounds to do what I wanted (used snap to path which didn't trigger a crash and eyed the position of the lines), but your solution is much more elegant.

Anyway, thanks a lot for all the invaluable help! I couldn't fully follow what was wrong with the PDF, it just sounded highly redundant. I guess I'll have to learn about clipping. I still don't think that Inkscape should have crashed, but at least now I have some idea of what to do to keep it from doing it again.

[su_v (suv-lp)]

<off-topic rant(ish) comments ;) >
> so I don't know why it would consistently hang on mine and not yours

Maybe because we have different expectations about what Inkscape is (it is not a full-featured PDF editor), and I adapted my workflow based on that? ;)

> I haven't tried the MacPorts version of Inkscape yet, I'm
> hoping to get around to that as soon as possible.

Instead of spending hours with installing MacPorts and compiling dozens of dependencies required for Inkscape - maybe invest more time in getting familiar with Inkscape? ;)

> I couldn't fully follow what was wrong with the PDF

AFAICT there is nothing _wrong_ with the PDF. What matters IMHO is that the PDF format was not really intended as file format to exchange vector data between different applications (it was designed as display format, to grant identical visual appearance on whatever output device it is rendered on). If you open/import a PDF file in Inkscape, the content gets converted into an SVG structure (with help of the poppler library) - which can result in many "redundant" structures you'd probably not use when simple exchanging the vector information required to regenerate the diagram, or drawing it in Inkscape itself.
</off-topic rant(ish) comments ;) >

> I still don't think that Inkscape should have crashed

You haven't said it crashed (else, please attach the crash report, see comment #1) - how much time did you wait before force-quitting the non-responsive application?

Here's the backtrace after interrupting inkscape 0.48.2 (with default (new) preferences) apparently unresponsive while trying to snap to paths & path intersections of the otherwise unedited document (i.e. without any edits after the PDF file was converted into an SVG structure on import):

Program received signal SIGINT, Interrupt.
0x90d86d06 in szone_size ()
(gdb) bt
#0 0x90d86d06 in szone_size ()
#1 0x90d83347 in free ()
#2 0x00322080 in Geom::portion ()
#3 0x00323a80 in Geom::bounds_local<Geom::Bezier> ()
#4 0x00323dd6 in Geom::BezierCurve<1u>::boundsLocal ()
#5 0x007c0e95 in Geom::pair_intersect ()
#6 0x007c1241 in Geom::pair_intersect ()
#7 0x007c1296 in Geom::pair_intersect ()
#8 0x007c1241 in Geom::pair_intersect ()
#9 0x007c1241 in Geom::pair_intersect ()
#10 0x007c1296 in Geom::pair_intersect ()
#11 0x007c1241 in Geom::pair_intersect ()
#12 0x007c1241 in Geom::pair_intersect ()
#13 0x007c1241 in Geom::pair_intersect ()
#14 0x007c1241 in Geom::pair_intersect ()
#15 0x007c3857 in Geom::SimpleCrosser::crossings ()
#16 0x001141d9 in Inkscape::SnappedCurve::intersect ()
#17 0x0011481c in getClosestIntersectionCS ()
#18 0x0010f51b in SnapManager::findBestSnap ()
#19 0x00110731 in SnapManager::freeSnap ()
#20 0x001123a8 in SnapManager::freeSnapReturnByRef ()
#21 0x000560a2 in spdc_endpoint_snap_free ()
#22 0x000d92c6 in sp_pencil_context_root_handler ()
#23 0x0006cdec in sp_event_context_virtual_root_handler ()
#24 0x0006d49c in sp_event_context_virtual_item_handler ()
#25 0x0006d8b6 in sp_event_context_snap_watchdog_callback ()
#26 0x0205b981 in g_timeout_dispatch ()
#27 0x0205951d in g_main_context_dispatch ()
#28 0x0205d3ab in g_main_context_iterate ()
#29 0x0205d687 in g_main...

[su_v (suv-lp)]

With regard to the performance when snapping to path intersections, let me also refer you to this recent comment by Diederik van Lierop (who implemented most of Inkscape's snapping features and is constantly working on improving it):
<https://bugs.launchpad.net/inkscape/+bug/847457/comments/2>
(Snapping to path intersections is inherently a costly operation performance-wise)

[su_v (suv-lp)]

After having ranted in my earlier comments (sorry for that :) ) - I revisited the issue and tried to produce a reduced test case (without involving PDF import):

In the attached file, use the pencil tool to draw a straight line between the two T-shaped figures to the left and right of the page using 'Snap to path intersections' (Note: In Inkscape 0.48.2, you need to enable 'Snap to paths' as well, unlike in current development builds).
As soon as the mouse pointer crosses the page border, CPU usage goes up, and Inkscape pauses quite a while until the other snap target outside the opposite page border is detected.

It seems that the clipped area (or the clip-paths themselves) are time-consuming to be considered for path intersections: each of the small rectangles is clipped with a page-size rectangle.

If the page is filled with such clipped rectangles, Inkscape appears to hang indefinitely (I wasn't patient enough to time whether the calculations at some point are done and normal drawing can be resumed).

Tested with Inkscape 0.48+devel r10640 on Mac OS X 10.5.8 (i386)

[su_v (suv-lp)]

The second test file has more clipped objects.

The relevant snap setting for the two test files seems to be 'Snap delay' set to 0 (zero) with otherwise default preferences.

[vlad seghete (vloodo)]

Thank you for looking into the bug and making a detailed and actually useful report. Like you said, "crash" is the wrong word here, it definitely depends on how long one is willing to wait, possibly indefinitely.

[Diederik van Lierop (mail-diedenrezi)]

This is to be expected: When trying to snap Inkscape collects all items within snapping range, and for this it uses the bounding box. But because the bounding box also includes this useless page-size clipping path, it will consider all items for snapping as soon as you move into the page boundaries, instead of just the few rectangles near the mouse pointer. Subsequently, it will try to find intersections for 342 items (~suv's file), which constitute 341*340*339*...*2 = 10^717 combinations! Now let's just forget the fact that calculating intersections is inherently slow anyway ;-).

I will have a look if the bounding box calculation can be improved for cases like this, but this could be quite tricky.

BTW, this is a very nice use-case demonstrating why I've implemented the snap-delay. A snap delay > 0 allows you to move across the page because snapping will be on hold while you move, and Inkscape will remain responsive.

[Diederik van Lierop (mail-diedenrezi)]

Ofcourse the number of combinations is not 341! but only 341 + 340 + .. + 1, i.e. approx. 58k.... which is still a lot!

[Diederik van Lierop (mail-diedenrezi)]

This has been fixed as of rev. 10672. The cause was slightly different from what I explained above, because it was not simply the bounding box calculation being wrong. In fact the snapping code explicitly try to snap to the clip or mask paths, when available. Now this might be handy in some use cases, but it certainly wasn't very useful here ;-).

So the easy fix was to make snapping to such clipping or mask paths optional, and turn it off by default (I'm guessing not many people will use this feature on a daily basis, but it can cause serious troubles as reported above). You can find a checkbox in the document properties dialog, on the snapping tab. I decided to put it there instead of in the snap toolbar, because IMHO it doesn't deserve such a prominent place in the UI (and screen real estate is too expensive already).

Please test and let me know if it isn't working as expected for some reason.

Thanks for reporting, triaging, debugging, and being patient ;-)

[su_v (suv-lp)]

> the easy fix was to make snapping to such clipping or mask paths optional
> (…)
> Please test and let me know if it isn't working as expected for some reason.

No new issues noticed so far - many thanks for adding this new option. IMHO it's in the right place - stored with each document and not globally, and not on the tool bar itself (I'd rather favor the toggle 'Only snap the node closest to the pointer' to be added to the toolbar ;) ).

When testing with snapping to clip-paths enabled, I notice the same issues with intersections as mentioned here:
<https://bugs.launchpad.net/inkscape/+bug/847457/comments/3>
and I'm surprised how much snapping to intersections (specially if one of the intersecting segments is a curve) depends on the zoom level (with regular paths as well as clip-paths): the closer I zoom in, the more path intersections are detected as snap targets - this is with r10672 on Mac OS X 10.5.8 (i386), optimized build, both with my usual preferences as well as the default ones.

Do we have a report tracking issues with path intersections as snap targets? Bug #847457 is 'Fix Committed' (path - guides intersection), as is this one here (optionally snap to intersections with clip-paths). Maybe <https://bugs.launchpad.net/inkscape/+bug/847457/comments/3> should be filed as new report…

[Diederik van Lierop (mail-diedenrezi)]

There are some bugs in the 2geom library which I've been able to isolate, and which are related to finding closest points on a path, intersections, tangent points, etc. Nathan Hurst has already found the cause and fixed it partially, but he's still working on a proper fix for all cases. It has to do with finding the roots of an s-basis equation. After that work has been committed then we can see what snapping bugs are remaining. So don't waste too much time on this for now.