Killing Livarot - Revision history

S-Rafael: Updates to the work items section

2022-06-12T17:16:06Z

Updates to the work items section

← Older revision		Revision as of 17:16, 12 June 2022
Line 16:		Line 16:
	Furthermore, it's not able to compute the union, intersection or difference of two identical shapes (as of May 2022).		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 <code>PathIntersectionGraph</code> to capture some of the existing breakage; currently being worked on by [https://gitlab.com/S-Rafael @S-Rafael].		* Write a path uncrossing algorithm.<br/>This provides a <code>flatten</code> primitive which removes self-overlaps and self-crossings and replaces <code>sp_flatten</code> [https://gitlab.com/inkscape/inkscape/-/blob/master/src/path/path-boolop.h#L17]. 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.<br/>In order to work as the definition of an actual “shape”, a path-vector must not have transverse intersection and must follow the convention that each path has the shape on its left and the outside on its right (if the y-axis is pointing up). Currently being worked on by [https://gitlab.com/S-Rafael @S-Rafael]. [[File:Flatten.png\|frame\|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.]]
	* Rework the inclusion classification in the <code>PathIntersectionGraph</code>, 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 [https://gitlab.com/S-Rafael @S-Rafael].
	* Write a path uncrossing algorithm.<br/>This provides a <code>flatten</code> primitive which removes self-overlaps and self-crossings ~~with the help of~~ <code>~~PathIntersectionGraph~~</code>. 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.<br/>~~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 <code>sp_flatten</code>~~. ~~At the moment,~~ [https://gitlab.com/S-Rafael @S-Rafael~~] is working on some supporting functionality needed to implement this function. [https://gitlab.com/inkscape/inkscape/-/blob/master/src/path/path-boolop.h#L17~~]. [[File:Flatten.png\|frame\|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 a new implementation of the boolean operations, using the Greiner-Hormann algorithm and insights from Livarot. The new implementation should use a “geometric” strategy for the classification of crossings and deciding which path portions lie inside the other shape. Currently [https://gitlab.com/S-Rafael @S-Rafael] is designing this feature.

	* 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. [[File:Division.png\|frame\|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 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. [[File:Division.png\|frame\|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.]]
Line 24:		Line 24:
	* Write a function which splits a shape into connected components; this corresponds to <code>split_non_overlapping</code> in Inkscape and should be implemented directly in the <code>PathIntersectionGraph</code>.		* Write a function which splits a shape into connected components; this corresponds to <code>split_non_overlapping</code> in Inkscape and should be implemented directly in the <code>PathIntersectionGraph</code>.

	* 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.		* Write a lot of 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 <code>PathIntersectionGraph</code>.		* If possible, remove all exceptions from <code>PathIntersectionGraph</code>.

	* Implement overloaded boolean operators <code>\|</code>, <code>&</code>, <code>-</code>, <code>^</code> on <code>~~PathVector~~</code> 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.		* Implement overloaded boolean operators <code>\|</code>, <code>&</code>, <code>-</code>, <code>^</code> on <code>Shape</code> 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 [https://gitlab.com/inkscape/inkscape/-/blob/master/src/path/path-boolop.cpp path-boolop.cpp] in Inkscape and eventually deleting it entirely.		* Start migrating the path and boolean operations in Inkscape to the new lib2geom implementation. This will involve rewriting most of the source file [https://gitlab.com/inkscape/inkscape/-/blob/master/src/path/path-boolop.cpp path-boolop.cpp] in Inkscape and eventually deleting it entirely.

S-Rafael: Status update on "flatten", reflect the removal of libnrtype.

2022-06-08T17:33:25Z

Status update on "flatten", reflect the removal of libnrtype.

← Older revision		Revision as of 17:33, 8 June 2022
Line 18:		Line 18:
	* Write additional unit tests for the <code>PathIntersectionGraph</code> to capture some of the existing breakage; currently being worked on by [https://gitlab.com/S-Rafael @S-Rafael].		* Write additional unit tests for the <code>PathIntersectionGraph</code> to capture some of the existing breakage; currently being worked on by [https://gitlab.com/S-Rafael @S-Rafael].
	* Rework the inclusion classification in the <code>PathIntersectionGraph</code>, 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 [https://gitlab.com/S-Rafael @S-Rafael].		* Rework the inclusion classification in the <code>PathIntersectionGraph</code>, 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 [https://gitlab.com/S-Rafael @S-Rafael].
	* Write a path uncrossing algorithm.<br/>This provides a <code>flatten</code> primitive which removes self-overlaps and self-crossings with the help of <code>PathIntersectionGraph</code>. 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.<br/>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 <code>sp_flatten</code> [https://gitlab.com/inkscape/inkscape/-/blob/master/src/path/path-boolop.h#L17]. [[File:Flatten.png\|frame\|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 a path uncrossing algorithm.<br/>This provides a <code>flatten</code> primitive which removes self-overlaps and self-crossings with the help of <code>PathIntersectionGraph</code>. 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.<br/>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 <code>sp_flatten</code>. At the moment, [https://gitlab.com/S-Rafael @S-Rafael] is working on some supporting functionality needed to implement this function. [https://gitlab.com/inkscape/inkscape/-/blob/master/src/path/path-boolop.h#L17]. [[File:Flatten.png\|frame\|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. [[File:Division.png\|frame\|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 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. [[File:Division.png\|frame\|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.]]
Line 58:		Line 58:
	* Measure performance and optimize.		* Measure performance and optimize.

	=== Crazy ~~libnrtype~~ dependency ===		=== Crazy text layout dependency ===
	The text layout library ~~libnrtype~~ 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.		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 ===		=== Python API ===

S-Rafael: Complete rewrite with status updates as of 2022 and significantly more detail.

2022-06-06T20:09:00Z

Complete rewrite with status updates as of 2022 and significantly more detail.

← Older revision		Revision as of 20:09, 6 June 2022
Line 1:		Line 1:
	This page details work items that need to be ~~done~~ to remove Livarot from ~~the~~ code base.		This page details work items that need to be completed in order to remove Livarot from Inkscape's code base.

	~~==Work items==~~		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.

	* Boolean operations		== Work items ==
	** Initial code in 2Geom, needs more work. MSc thesis subject of Krzysztof Kosiński
	* Tweak tool
	* Crazy libnrtype dependency
	** libnrtype uses Livarot for line-breaking text in flow regions
	* Offset tool
	** Path outliner worked on by Liam will eventually be a direct replacement

	==~~See also~~==		=== Project Path Operations ===
	* [[~~Exploring Livarot~~]]		There's an initial implementation of path boolean operations in lib2geom (MSc thesis subject of Krzysztof Kosiński),
	* [[Path ~~Library Improvement Project~~]]		but it needs substantially more work before it has all the features and proven reliability needed to fully replace Livarot.

			==== Path Intersection Graph ====
			The <code>PathIntersectionGraph</code> class underlies all existing boolean operations in lib2geom, implementing the [https://en.wikipedia.org/wiki/Greiner%E2%80%93Hormann_clipping_algorithm 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 <code>PathIntersectionGraph</code> to capture some of the existing breakage; currently being worked on by [https://gitlab.com/S-Rafael @S-Rafael].
			* Rework the inclusion classification in the <code>PathIntersectionGraph</code>, 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 [https://gitlab.com/S-Rafael @S-Rafael].
			* Write a path uncrossing algorithm.<br/>This provides a <code>flatten</code> primitive which removes self-overlaps and self-crossings with the help of <code>PathIntersectionGraph</code>. 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.<br/>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 <code>sp_flatten</code> [https://gitlab.com/inkscape/inkscape/-/blob/master/src/path/path-boolop.h#L17]. [[File:Flatten.png\|frame\|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. [[File:Division.png\|frame\|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 <code>split_non_overlapping</code> in Inkscape and should be implemented directly in the <code>PathIntersectionGraph</code>.

			* 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 <code>PathIntersectionGraph</code>.

			* Implement overloaded boolean operators <code>\|</code>, <code>&</code>, <code>-</code>, <code>^</code> on <code>PathVector</code> 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 [https://gitlab.com/inkscape/inkscape/-/blob/master/src/path/path-boolop.cpp 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 [https://gitlab.com/inkscape/inbox/-/issues/7121]. [[File:Exclusion-on-groups.png\|frame\|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 <code>boost::ptr_vector</code> is actually a good container for this use case.

			=== The Shape Tool ===
			The new tool (shape tool/welder tool/shape welder) [https://gitlab.com/inkscape/ux/-/issues/109 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 [https://gitlab.com/osamaahmad Osama Ahmad] under the title “On-canvas interactive boolean operations”.
			Nonetheless, the [https://gitlab.com/inkscape/inkscape/-/merge_requests/3357 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 [https://gitlab.com/S-Rafael @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.<br/>At first glance, this may seem excessively complicated compared to the apparently simple [https://ieeexplore.ieee.org/abstract/document/4055919 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 libnrtype dependency ===
			The text layout library libnrtype 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 ===

			[[File:Gnarly.png\|thumb\|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) [https://gitlab.com/inkscape/inkscape/-/issues/1124].

			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 <code>PathIntersectionGraph</code>. In addition to enabling a substantial improvement on the extremely crufty <code>FreehandBase</code> and <code>CalligraphicTool</code> classes in Inkscape (as of May 2022), it could help improve the performance of the Pencil Tool.

			== Discussion ==

			[[Category:Developer Discussion]]

Mk at 08:44, 14 June 2020

2020-06-14T08:44:10Z

← Older revision		Revision as of 08:44, 14 June 2020
Line 13:		Line 13:
	==See also==		==See also==
	* [[Exploring Livarot]]		* [[Exploring Livarot]]
			* [[Path Library Improvement Project]]

Mk at 15:30, 22 March 2020

2020-03-22T15:30:56Z

← Older revision		Revision as of 15:30, 22 March 2020
Line 10:		Line 10:
	* Offset tool		* Offset tool
	** Path outliner worked on by Liam will eventually be a direct replacement		** Path outliner worked on by Liam will eventually be a direct replacement

			==See also==
			* [[Exploring Livarot]]

Tweenk: Created page with "This page details work items that need to be done to remove Livarot from the code base. ==Work items== * Boolean operations ** Initial code in 2Geom, needs more work. MSc th..."

2015-04-26T16:28:20Z

Created page with "This page details work items that need to be done to remove Livarot from the code base. ==Work items== * Boolean operations ** Initial code in 2Geom, needs more work. MSc th..."

New page

This page details work items that need to be done to remove Livarot from the code base.

==Work items==

* Boolean operations
** Initial code in 2Geom, needs more work. MSc thesis subject of Krzysztof Kosiński
* Tweak tool
* Crazy libnrtype dependency
** libnrtype uses Livarot for line-breaking text in flow regions
* Offset tool
** Path outliner worked on by Liam will eventually be a direct replacement