.jpg)
During the development of various applications there is a need to generate curves. In the web environment, the SVG format is most often used for such purposes. At the moment the SVG specification only works with quadratic and cubic Bézier curves. But in the case of a curve that goes through many points, we need a method for smoothly merging segments to create a nice looking curve. The solution to this problem is to generate Bézier curves using continuity conditions C2 and C1. One of the many examples is here.
But in our case of connectors for the JointJS open-source library, there is a restriction that the start and end tangents must be defined so that the curve starts and ends perpendicularly (in the default situation). And in this case the usual implementation leads to very twisted curves in certain situations. A Bézier curve works in terms of control points, but this is not very convenient in the case of manipulations with tangents.
So we decided to use Catmull-Rom splines with subsequent conversion to cubic Bézier curves, which are supported by the SVG format. Catmull-Rom splines are not currently supported by the SVG standard, but there are plans to add them.
Catmull-Rom splines are types of cubic splines that define tangents at each point using the previous and next spline points. Unlike a Bézier curve, which has different orders (quadratic, cubic, etc.), a Catmull-Rom spline is defined only for 4 control points, so its segment is always cubic. The curve is drawn only from points \(P_1\) to \(P_2\) while points \(P_0\) and \(P_3\) are used to define tangents at points \(P_1\) and \(P_2\).
Catmull-Rom splines can be defined in terms of tension. This parameter governs the behavior of the curve at the control points. The higher the tension, the shorter the tangents at the start and end points.
A segment of the Catmull-Rom spline can be combined with other segments to obtain a smooth curve through an arbitrary number of points. To ensure a smooth curve, we must assume that at each point the tangents of neighboring segments must be collinear. But we must also adjust the length of the tangent vectors to control the overall flow of the curve.
In our use case the most important parameter which we want to control is tangents at the interpolated points. A common formula for a tangent at a particular point is \(t_i = \tau(p_i-p_{i-1}) + (1-\tau)(p_{i+1}-p_i)\), where \(\tau\) is tension and \(p_i\) is corresponding to control points.
Using this formula we can derive the coordinates of the control points of the curve segments. All we need to know are the tangents for each point through which our curve will pass.
To draw a curve according to our algorithm, we need a list of points \(P_0\ldots P_n\) through which the curve will pass, as well as the source and target directions \(D_s\), \(D_t\) (or tangents \(t_0\), \(t_n\)). For a tension t we are using the default value of 0.5 (it is the most suitable in our case). In our case we know the desired tangents or directions at the start and end points. In the case where only directions are given, we use a formula to determine the length of the tangent as a function of the distance to the nearest point. Here we introduce the coefficient \(k\) - this coefficient is the ratio of the distance between the points to the length of the tangent:
\begin{eqnarray}
&& l_0=k\cdot dist(P_0,P_1), \\
&& l_n=k\cdot dist(P_n,P_{n-1}).
\end{eqnarray}
In JointJS we are using 0.6 as the default value. After this we are calculating the angle \(theta\) between the direction and a vector to the nearest point for every direction.
\begin{eqnarray}
&&\theta_s=angle(P_s,P_1-P_0), \\
&&\theta_t=angle(D_t,P_{n-1}-P_n).
\end{eqnarray}
If \(theta_s\) is greater than 45 degrees, we adjust the length of the tangent so that the curve behaves correctly at certain angles. To control this behavior we use coefficient \(k_\theta\) (in JointJS the default is 80):
\begin{eqnarray}
&& l_0=l_0 + k_\theta(\theta_s-\frac{\pi}{4}), \\
&& l_n=l_n + k_\theta(\theta_t-\frac{\pi}{4}), \\
&& t_0=D_sl_0,\\
&& t_n=D_tl_n.
\end{eqnarray}
You can see how different parameters affect curves in this CodePen:
To construct all curve segments, we need to find corresponding tangents at each point. At each point \(i\) we need to calculate two tangents \(t^1_i\), \(t^2_i\) for two adjacent segments of a spline.
The direction of the tangent at a particular point is calculated from the previous and subsequent points. But for continuity and smoothness instead of first and last points \(P_0\), \(P_n\) we use corresponding points with added tangents \(t_0\), \(t_n\). First we look for vectors to the current point:
\begin{eqnarray}
&&V^1_i=P_{i-1}-P_i, \\
&&V^2_i=P_{i+1}-P_i,
\end{eqnarray}
and find angle \(theta_v\) between these vectors.
Then we find a unit vector \(t\), which corresponds to the "tangent" of an angle \(theta_v\) (see the picture below). To find vector t we need to rotate vector \(V^2_i\) counterclockwise (clockwise if a determinant of (\(V^1_i\), \(V^2_i\)) is less than 0) by \(\frac{\pi-\theta_v}{2}\) degrees. To find the lengths of the tangents for certain segments we use the following formulas:
\begin{eqnarray}
&&t^1_i=t\cdot k\cdot dist(P_i-P_{i-1}), \\
&&t^2_i=t\cdot k\cdot dist(P_i-P_{i+1}).
\end{eqnarray}
After obtaining all tangents we can construct the Catmull-Rom spline in terms of control points. For each \(i\)-th segment of the total \(n\) segments of a spline (the number of points minus one) we create 4 control points as follows:
\begin{eqnarray}
&&p_0=P_{i+1}-\frac{t^2_i}{\tau}, \\
&&p_1=P_i, \\
&&p_2=P_{i+1}, \\
&&p_3=P_i-\frac{t^1_{i+1}}{\tau}.
\end{eqnarray}
To convert Catmull-Rom curves into Bézier curves, we use the formulas from this article. Thus, in our terms we obtain this transformation for each segment:
\begin{eqnarray}
&&B_0=p_1, \\
&&B_1=p_1+\frac{p_2-p_0}{6\tau}, \\
&&B_2=p_2+\frac{p_3-p_1}{6\tau}, \\
&&B_3=p_2.
\end{eqnarray}
where \(B_0\) and \(B_3\) are starting and ending points and \(B_1\) and \(B_2\) are middle control points of a cubic Bézier curve.
All in all, this approach provides a fast and customizable way to create beautiful curves using SVG. We work with Catmull-Rom splines because it makes it easier to manipulate tangents, which is our main goal, and the conversion to Bézier curves is very smooth.
And the result? See it yourself:
.jpg)
