Killing Livarot

This page details work items that need to be completed in order to remove Livarot from Inkscape's code base.

This project requires a substantial amount of work and welcomes all volunteers who would like to contribute code, help in code review, as well as help test the new functionality at later stages of the development.

Work items

Project Path Operations

There's an initial implementation of path boolean operations in lib2geom (MSc thesis subject of Krzysztof Kosiński), but it needs substantially more work before it has all the features and proven reliability needed to fully replace Livarot.

Path Intersection Graph

The PathIntersectionGraph class underlies all existing boolean operations in lib2geom, implementing the Greiner-Hormann algorithm. Unfortunately, the current implementation is flawed in several ways. For instance, it cannot handle certain kinds of intersections, e.g., two paths merging and traveling together for some distance. Furthermore, it's not able to compute the union, intersection or difference of two identical shapes (as of May 2022).

• Write additional unit tests for the PathIntersectionGraph to capture some of the existing breakage; currently being worked on by @S-Rafael.
• Rework the inclusion classification in the PathIntersectionGraph, a key step of the Greiner-Hormann algorithm. This provides an alternative “geometric” strategy for the classification of crossings and deciding which path portions lie inside the other path-vector. Currently being worked on by @S-Rafael.
• Write a path uncrossing algorithm.
  This provides a flatten primitive which removes self-overlaps and self-crossings with the help of PathIntersectionGraph. A path that self-intersects should be cut at the intersection points and replaced by one or several paths that do not have self-intersections. Note that we only need to remove actual transverse self-intersections and not all spurious solutions from the sweepline algorithm.
  Implicitly, the 2-dimensional shapes in lib2geom are defined by path-vectors using the “even-odd” fill rule. The flattening function converts such a path-vector to one which works with the “non-zero” fill rule, similar to sp_flatten. At the moment, @S-Rafael is working on some supporting functionality needed to implement this function. [1].
  

  The "flatten" operation replaces a self-intersecting path with one that doesn't cross over itself. The result path, shown on the right, has the same fill region regardless of whether "even-odd" or "nonzero" fill rule is used.

• Write functions that implement path cutting (slicing) and division. “Slicing” refers to cutting all paths in a path-vector along all intersection points with another path-vector. “Division” refers to using one path-vector as a “cookie cutter” which divides the other path-vector (the “dough”) into several shapes.
  

  The "division" operation is analogous to using a cookie cutter on a piece of dough. Note that the white gaps between the resulting pieces have been thickened for better visibility; in reality, these pieces should fit together perfectly.

• Write a function which splits a shape into connected components; this corresponds to split_non_overlapping in Inkscape and should be implemented directly in the PathIntersectionGraph.

• Write even more unit tests to ensure that all this functionality is robust and handles all weird and exotic corner cases. If the “geometric” classification strategy works well, make it the default strategy.

• If possible, remove all exceptions from PathIntersectionGraph.

• Implement overloaded boolean operators |, &, -, ^ on PathVector operands. This is just a cherry on top of the cake and should be added once the new strategy is robust enough for general use.

• Start migrating the path and boolean operations in Inkscape to the new lib2geom implementation. This will involve rewriting most of the source file path-boolop.cpp in Inkscape and eventually deleting it entirely.

• Migrate all Live Path Effects which use boolean operations to the new lib2geom facilities.

• Implement boolean operations on sets of shapes, including nested groups [2].
  

  The proposed "exclusion" operation on groups of shapes; based on an illustration by Chris Rogers.

• Measure the performance of the new boolean operations and devise performance optimizations; in particular consider cache-friendliness of the code and whether or not boost::ptr_vector is actually a good container for this use case.

The Shape Tool

The new tool (shape tool/welder tool/shape welder) was proposed as an alternative to “shape builder” functionality found in other vector drawing programs. Developing this functionality was the subject of the 2021 Google Summer of Code project by Osama Ahmad under the title “On-canvas interactive boolean operations”. Nonetheless, the already-developed UI requires a stable and convenient engine that can power this tool.

Path outliner

Path outliner was worked on by Liam but the status of this work is unknown. The biggest obstacle to a robust path outlining functionality is the unreliability of the lib2geom boolean operations as of May 2022. Once the boolean operations are robust, path outlining can be developed on this basis, although it still requires some work; the main tasks are listed below.

• Write outlining functions for all curve types used in SVG specification: quadratic and cubic Bézier curves, elliptical arcs. A design requirement is the ability to control the relative error of the outline distance (contact @S-Rafael for more details).

• Optionally, provide outlining algorithms for other curve types supported by lib2geom.

• The final implementation should outline paths by outlining the constituent curves and combining the outlines with boolean union.
  At first glance, this may seem excessively complicated compared to the apparently simple Tiller–Hanson method, but is actually required for a general implementation. Note that the Tiller–Hanson algorithm was invented for shapes used in CAD, which are a lot less crazy and irregular than arbitrary paths which lib2geom must support.

• Write unit tests for the path outliner.

• Measure performance and optimize.

Crazy text layout dependency

The text layout engine (formerly contained in the "libnrtype" library) uses Livarot for line-breaking text in flow regions. This involves using path outline and boolean operation functionality in Livarot and has been the source of some bugs and headaches. However, once path outlining is available in lib2geom, it will not be very hard to use it to create flow regions with variable padding.

Python API

All of the new functionality described above should be gradually exposed in the Python API, so that Inkscape's extensions can call lib2geom directly instead of routing their calls through Inkscape. This will enable extension authors to perform advanced path operations directly in their Python code.

Streaming outliner

A gnarly, jagged outline created by the Eraser Tool due to the retrograde motion of the ends of the tool's nib.

The free-hand drawing tools in Inkscape, such as the Calligraphic and Eraser tools, implement a very primitive (but fast) form of path outlining via Bézier fitting. This outlining method causes some problems such as a gnarly, knotted tool trace when one of the nib extremities experiences retrograde motion (leading to the fitting of Bézier curves with loops) [3].

A much more robust replacement for use in tools would be a “streaming outliner” which accepts incoming sample points in real time, outlines the incoming segments and appends them to a stored, gradually growing outline of the toolpath. This is a long-term goal, since it would require a more streaming-friendly implementation of the functionality in PathIntersectionGraph. In addition to enabling a substantial improvement on the extremely crufty FreehandBase and CalligraphicTool classes in Inkscape (as of May 2022), it could help improve the performance of the Pencil Tool.