Boolean ops unstable for "degenerate" paths

[Eric Greveson]

As noted in Bug #168158, Inkscape (via the livarot library) quantizes path coordinates (effectively snapping to a fine grid) before applying Boolean operations. This usually works without any noticeable problems. However, when paths are so small that they are below the grid size, Inkscape can generate strange results from Boolean operations. This behaviour appears to be inconsistent across platforms/builds (perhaps different math models?), and therefore reproduction with a given data set is not guaranteed.

Results on Ubuntu 12.04, with Inkscape 0.49.x bazaar trunk rev 12472 are attached. Essentially, the source file (boolop_bug.svg) contains two paths - a tiny red path (only visible upon zooming in to the appropriate image area), and a much larger green "trellis" path (visible at normal zoom), on top of, and partially overlaypping, the tiny path. To reproduce, open the file in Inkscape, Select All, and perform Path/Difference. Expected result: the trellis should be subtracted from the tiny path (leaving nothing visible). Actual result: the tiny path takes on the trellis coordinates, and the trellis path is deleted. This can be seen in "boolop_bug_result.svg".

Performing the same steps on a Windows 7 x64 machine, running Inkscape 0.48.4, rev 9939, results in both paths being removed. While not exactly correct, this is an understandable result considering the path coordinates are quantized (perhaps resulting in the quantized tiny path being completely covered by the quantized trellis path, and hence completely removed upon subtraction).

[su_v (suv-lp)]

Results reproduced on OS X 10.7.5:
- stable version (Inkscape 0.48.4): both paths removed
- current trunk (r12472): the tiny path takes on the trellis coordinates, and the trellis path is deleted.

[su_v (suv-lp)]

On 2013-08-07 18:34 +0200, ~suv wrote:> Results reproduced on OS X 10.7.5:
> - stable version (Inkscape 0.48.4): both paths removed
> - current trunk (r12472): the tiny path takes on the trellis
> coordinates, and the trellis path is deleted.

Testing with archived builds of trunk on OS X 10.7.5:
- with rev <= 12175: both paths removed
- with rev >= 12176: tiny path takes on the trellis coordinates, and the trellis path is deleted

The change in behavior - between current stable (0.48.4) and trunk (0.48+devel) - for this particular case is likely a side-effect of
<http://bazaar.launchpad.net/~inkscape.dev/inkscape/trunk/revision/12176>
which addressed bug #168907.

[Eric Greveson (7-eric)]

Interesting, thanks for that investigation. I guess that while the fix of rev 12176 is correct for the union operation (and perhaps other bool ops on objects that fall beneath the grid size), it does exactly the wrong thing for difference op. I'll consider making a fix by testing the type of boolean op being performed, and doing something different (probably removing both paths) in case of a difference operation on excessively small paths.

A long-term, "proper" fix would be to replace the current livarot line-sweep algorithm with something that is stable and correct for all edge cases at machine precision, i.e. so that no quantization is required. This is obviously a bigger task.

[ScislaC (scislac)]

@Eric: A full rewrite of boolops is actually the eventual plan. Unfortunately it hasn't been taken on since it's not exactly a small task. The plan is to actually implement boolops upstream in lib2geom and remove livarot from Inkscape when possible. There was someone who began working on it last year and unfortunately he didn't continue. If you're interested in seeing what was done (not a ton, but it's something), check out https://code.launchpad.net/~vincent-barrielle/lib2geom/boolops

[Eric Greveson (7-eric)]

Interesting! Sounds good. Is it actually necessary to rewrite all the intersection code etc from scratch though? There seems to be a good GPL implementation available in CGAL already (http://www.cgal.org/Manual/beta/doc_html/cgal_manual/packages.html#part_VIII) - while this would be an additional dependency, it might not be too big a price to pay for a working, tested, stable implementation for minimum effort? Once the intersections etc are found, implementing the boolean operations themselves would be a much easier task.