Inkscape Wiki - User contributions [en]

Path Library Improvement Project

2020-06-14T12:22:22Z

Mk:

This wiki page will hold all extra documentation that I intend to write as I progress in the project.

The first functionality that I have succeeded to implement is Path Simplification.

== Path Simplification ==
It is a two step process:
# Given a threshold value, break a path into line segments (we call this a polyline)
# Fit cubic bezier patches on the polyline such that the total error is controlled and the number of patches are kept minimum.

=== Breaking up into line segments ===
While this process can be very simple if we simply use lib2geom's <code>Geom::Curve</code> abstraction with a recursive path splitting algorithm. I think it's still better to use separate pieces of codes to deal with each type of curve separately. There are two advantages to doing this. Firstly, if you know the curve type, you can use a faster algorithm to do the splitting, secondly we can use the same path splitting algorithms as livarot does and have identical results.

At the moment, I have custom code to deal with Cubic Bezier curves and Line Segments (<code>PathFlattener::breakLine</code> and <code>PathFlattener::breakCubic</code>) and for every other type a generalized function <code>PathFlattener::breakCurve</code> is used.

==== Breaking Line Segments ====
Usually line segments aren't further broken at all. So only their endpoint is added to the sequence. However, if the flag <code>convertEvenLines</code> is set, we break the line into smaller line segments such that each line segment has a length that's smaller than or equal to the threshold. This is useful in Path Simplification.

==== Breaking Cubic Beziers ====
[[File:Bezier-splitting.png|thumb]]

The algorithm that livarot uses to decide how/if to split a cubic curve is slightly complex to understand. Therefore, I decided it would be best to explain it with the help of a picture. The cubic bezier shown in the picture is defined by two endpoints $$\vec{P_{0}}$$ and $$\vec{P_{3}}$$ and two control points $$\vec{P_{1}}$$ and $$\vec{P_{1}}$$.
Now let us define three vectors:
\begin{align}\vec{sD} = \vec{P_{1}}-\vec{P_{0}}\end{align}
\begin{align}\vec{eD} = \vec{P_{3}}-\vec{P_{2}}\end{align}
\begin{align}\vec{se} = \vec{P_{3}}-\vec{P_{0}}\end{align}
Let us also define two scalar values:
\begin{align}Sy = |\vec{sD}|\sin\theta_{1}\end{align}
\begin{align}Ey = |\vec{eD}|\sin\theta_{2}\end{align}
$$\vec{sD}$$ is a vector from the first end point to the first control point, similarly, $$\vec{eD}$$ is a vector from second control point to the second end point, $$\vec{se}$$ is a vector from the first end point to the second end point. $$Sy$$ and $$Ey$$ are the projections of the vectors $$\vec{sD}$$ and $$\vec{eD}$$ on the the axis perpendicular to the vector $$\vec{se}$$.

This cubic bezier can be approximated by a line segment through its endpoints if the following three conditions are true:
\begin{align}|\vec{se}| < 0.01\end{align}
\begin{align}|3\vec{sD}|^2 < threshold\end{align}
\begin{align}|3\vec{eD}|^2 < threshold\end{align}

Or if the following four are true:
\begin{align}|\vec{se}| >= 0.01\end{align}
\begin{align}|3Sy| < threshold\end{align}
\begin{align}|3Ey| < threshold\end{align}
\begin{align}|\vec{se}| <= maxL\end{align}

Otherwise, the bezier curve is split into two bezier curves as shown with colors magenta and green in the picture and then both are checked by the same conditions recursively. The center point (which is the common endpoint for both bezier curves) is added to the sequence of points.

Path Library Improvement Project

2020-06-14T12:15:42Z

Mk:

This wiki page will hold all extra documentation that I intend to write as I progress in the project.

The first functionality that I have succeeded to implement is Path Simplification.

== Path Simplification ==
It is a two step process:
# Given a threshold value, break a path into line segments (we call this a polyline)
# Fit cubic bezier patches on the polyline such that the total error is controlled and the number of patches are kept minimum.

=== Breaking up into line segments ===
While this process can be very simple if we simply use lib2geom's <code>Geom::Curve</code> abstraction with a recursive path splitting algorithm. I think it's still better to use separate pieces of codes to deal with each type of curve separately. There are two advantages to doing this. Firstly, if you know the curve type, you can use a faster algorithm to do the splitting, secondly we can use the same path splitting algorithms as livarot does and have identical results.

At the moment, I have custom code to deal with Cubic Bezier curves and Line Segments (<code>PathFlattener::breakLine</code> and <code>PathFlattener::breakCubic</code>) and for every other type a generalized function <code>PathFlattener::breakCurve</code> is used.

==== Breaking Line Segments ====
Usually line segments aren't further broken at all. So only their endpoint is added to the sequence. However, if the flag <code>convertEvenLines</code> is set, we break the line into smaller line segments such that each line segment has a length that's smaller than or equal to the threshold. This is useful in Path Simplification.

==== Breaking Cubic Beziers ====
[[File:Bezier-splitting.png|thumb]]

The algorithm that livarot uses to decide how/if to split a cubic curve is slightly complex to understand. Therefore, I decided it would be best to explain it with the help of a picture. The cubic bezier shown in the picture is defined by two endpoints $$\vec{P_{0}}$$ and $$\vec{P_{3}}$$ and two control points $$\vec{P_{1}}$$ and $$\vec{P_{1}}$$.
Now let us define three vectors:
\begin{align}\vec{sD} = \vec{P_{1}}-\vec{P_{0}}\end{align}
\begin{align}\vec{eD} = \vec{P_{3}}-\vec{P_{2}}\end{align}
\begin{align}\vec{se} = \vec{P_{3}}-\vec{P_{0}}\end{align}
Let us also define two scalar values:
\begin{align}Sy = |\vec{sD}|\sin\theta_{1}\end{align}
\begin{align}Ey = |\vec{eD}|\sin\theta_{2}\end{align}
$$\vec{sD}$$ is a vector from the first end point to the first control point, similarly, $$\vec{eD}$$ is a vector from second control point to the second end point, $$\vec{se}$$ is a vector from the first end point to the second end point. $$Sy$$ and $$Ey$$ are the projections of the vectors $$\vec{sD}$$ and $$\vec{eD}$$ on the vector $$\vec{se}$$.

This cubic bezier can be approximated by a line segment through its endpoints if the following three conditions are true:
\begin{align}|\vec{se}| < 0.01\end{align}
\begin{align}|3\vec{sD}|^2 < threshold\end{align}
\begin{align}|3\vec{eD}|^2 < threshold\end{align}

Or if the following four are true:
\begin{align}|\vec{se}| >= 0.01\end{align}
\begin{align}|3Sy| < threshold\end{align}
\begin{align}|3Ey| < threshold\end{align}
\begin{align}|\vec{se}| <= maxL\end{align}

Otherwise, the bezier curve is split into two bezier curves as shown with colors magenta and green in the picture and then both are checked by the same conditions recursively. The center point (which is the common endpoint for both bezier curves) is added to the sequence of points.

Path Library Improvement Project

2020-06-14T12:01:02Z

Mk:

This wiki page will hold all extra documentation that I intend to write as I progress in the project.

The first functionality that I have succeeded to implement is Path Simplification.

== Path Simplification ==
It is a two step process:
# Given a threshold value, break a path into line segments (we call this a polyline)
# Fit cubic bezier patches on the polyline such that the total error is controlled and the number of patches are kept minimum.

=== Breaking up into line segments ===
While this process can be very simple if we simply use lib2geom's <code>Geom::Curve</code> abstraction with a recursive path splitting algorithm. I think it's still better to use separate pieces of codes to deal with each type of curve separately. There are two advantages to doing this. Firstly, if you know the curve type, you can use a faster algorithm to do the splitting, secondly we can use the same path splitting algorithms as livarot does and have identical results.

At the moment, I have custom code to deal with Cubic Bezier curves and Line Segments (<code>PathFlattener::breakLine</code> and <code>PathFlattener::breakCubic</code>) and for every other type a generalized function <code>PathFlattener::breakCurve</code> is used.

==== Breaking Line Segments ====
Usually line segments aren't further broken at all. So only their endpoint is added to the sequence. However, if the flag <code>convertEvenLines</code> is set, we break the line into smaller line segments such that each line segment has a length that's smaller than or equal to the threshold. This is useful in Path Simplification.

==== Breaking Cubic Beziers ====
[[File:Bezier-splitting.png|thumb]]

The algorithm that livarot uses to decide how/if to split a cubic curve is slightly complex to understand. Therefore, I decided it would be best to explain it with the help of a picture. The cubic bezier shown in the picture is defined by two endpoints $$\vec{P_{0}}$$ and $$\vec{P_{3}}$$ and two control points $$\vec{P_{1}}$$ and $$\vec{P_{1}}$$.
Now let us define three vectors:
\begin{align}\vec{sD} = \vec{P_{1}}-\vec{P_{0}}\end{align}
\begin{align}\vec{eD} = \vec{P_{3}}-\vec{P_{2}}\end{align}
\begin{align}\vec{se} = \vec{P_{3}}-\vec{P_{0}}\end{align}
Let us also define two scalar values:
\begin{align}Sy = |\vec{sD}|\sin\theta_{1}\end{align}
\begin{align}Ey = |\vec{eD}|\sin\theta_{2}\end{align}
$$\vec{sD}$$ is a vector from the first end point to the first control point, similarly, $$\vec{eD}$$ is a vector from second control point to the second end point, $$\vec{se}$$ is a vector from the first end point to the second end point. $$Sy$$ and $$Ey$$ are the projections of the vectors $$\vec{sD}$$ and $$\vec{eD}$$ on the vector $$\vec{se}$$.

This cubic bezier can be approximated by a line segment through its endpoints if:
\begin{align}|\vec{se}| < 0.01 \& |3\vec{sD}|^2 < threshold \& |3\vec{eD}|^2 < threshold\end{align}

Path Library Improvement Project

2020-06-14T11:46:49Z

Mk:

Path Library Improvement Project

2020-06-14T11:30:30Z

Mk:

Path Library Improvement Project

2020-06-14T11:00:06Z

Mk:

File:Bezier-splitting.png

2020-06-14T10:59:42Z

Mk:

Splitting a cubic Bezier curve into two

Path Library Improvement Project

2020-06-14T09:01:48Z

Mk:

Path Library Improvement Project

2020-06-14T08:56:47Z

Mk:

Path Library Improvement Project

2020-06-14T08:50:59Z

Mk:

Path Library Improvement Project

2020-06-14T08:45:54Z

Mk: Created page with "This wiki page will hold all extra documentation that I intend to write as I progress in the project. The first functionality that I have succeeded to implement is Path Simpl..."

Killing Livarot

2020-06-14T08:44:10Z

Mk:

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

==See also==
* [[Exploring Livarot]]
* [[Path Library Improvement Project]]

Exploring Livarot

2020-03-23T08:01:37Z

Mk:

===Why is it being used?===
# Tweak Tool
# Path Offsetting
# Boolean Operations
# Flowing Text
# Path Simplification
# Path Flattening

===How's it typically used?===
# Creating a livarot <code>Path</code> object by using Inkscape’s functions such as <code>Path_for_item</code> or <code>Path_for_pathvector</code>. These functions just store path descriptions inside the <code>Path</code> object. Such as <code>moveTo</code>,<code>lineTo</code>, <code>cubicTo</code>, etc. These are just instructions.
# Calling <code>path->Convert</code> or <code>path->ConvertWithBackData</code>. Given a threshold value, these functions create a polygon that approximates the path descriptions given in step 1. The smaller the threshold value, the better the approximation. This approximation is the fundamental tool of livarot that gives it the ability to do things like path boolean operations.
# Calling <code>path->Fill(shape, ...)</code> . This creates a directed graph structure from the approximated polygon. A directed graph just has points connected by edges.
# Calling <code>shape->ConvertToShape(shape_input, ...)</code>. This function converts the graph created earlier, to a polygon without any self-intersections or duplicate points. It is one of the most important functions of livarot. It also takes a fill rule as the argument.
# Here whatever actual function you wanna perform is called. If you’re tweaking, you would call <code>shape->MakeTweak</code>, if you’re performing outset/inset, you’d call <code>shape->MakeOffset</code>. Similar functions exist for boolean operations.
# Calling <code>shape->ConvertToForme(path)</code>. This converts the shape object back to a path whose SVG description you can grab and put in the XML tree.

Exploring Livarot

2020-03-23T06:39:01Z

Mk:

===Why is it being used?===
# Tweak Tool
# Path Offsetting
# Boolean Operations
# Flowing Text
# Path Simplification
# Path Flattening

Exploring Livarot

2020-03-23T06:30:44Z

Mk:

===Why is it being used?===
# Tweak Tool
# Path Offsetting
# Boolean Operations
# Flowing Text
# Path Simplification

===Detailed List===
# Tweak Tool
#* <code>sp_tweak_dilate_recursive()</code> in ''src/ui/tools/tweak-tool.cpp'' uses <code>shape->MakeTweak</code> for tweak modes such as <code>TWEAK_MODE_SHRINK_GROW</code>, <code>TWEAK_MODE_ATTRACT_REPEL</code>, <code>TWEAK_MODE_PUSH</code> and <code>TWEAK_MODE_ROUGHEN</code>.
# Path Offsetting
#*

Exploring Livarot

2020-03-23T06:13:19Z

Mk: Created page with "===Why is it being used?=== # Path Offsetting # Tweak Tool # Boolean Operations # Flowing Text"

===Why is it being used?===
# Path Offsetting
# Tweak Tool
# Boolean Operations
# Flowing Text

Killing Livarot

2020-03-22T15:30:56Z

Mk: