As discussed by Breen et al. (not dated) a Catmull-Rom spline is created from a series of linear Hermite curves with tension modified at each control point which can increase the order of continuity. This explains many of the properties of a Catmull-Rom spline.
The resulting curve will always "interpolate all control points" (Pacheco et al., 2010, p. 14), passing through the exact position of each control point will allow me to precisely define the curve during the limb swing phase simply by repositioning the control points alone.
The behaviour also means that when repositioning the curve away from obstacles in the projected path, I can be confident that if the polygon created by the control points is elevated above the obstacle, the cure will not pass through it.
As the tension parameter is increased at the control points to achieve C1 continuity, the curve produced “does not lie in the convex hull” (Pacheco et al., 2010, p. 14) created by its control points.
I had not initially appreciated the extent of this behaviour when selecting curve types to implement. The oscillations between control points may cause significant issues in producing trajectories which appear natural.
The “Catmull-Rom curve is advanced in its local-control ability” (Wang et al., 2017, p. 5) as each Hermite curve connects consecutive control points, only the sections adjacent to each control point are affected by the change.
This gives potential for a more complex trajectory, without any further mathematical curve calculation – though it would require more robust logic to be applied to the positioning of the control points to ensure distance and tension values are adjusted to avoid overfitting of the control point vector values.
Implementation
“A Catmull-Rom Spline is defined by a sequence of control points P0, . . .,Pm. It passes through the control points P1, . . .,P(m-1) and the tangent vector at point Pi is parallel to the vector Pi-1 Pi+1.” (Sprunk, 2008, p. 76).The tangent angles at the control points can be solved with:
 |
| Figure 1: Equation to solve control point tangent angles (Lengyel, 2012, p. 330) |
Though during calculation some additional logic must be incorporated into the algorithm:
“the tangent of the first control point does not exist, since there is no control point before that. The same applies to the last control point, as no control point exists after that, featuring a curve which does not interpolate the extreme control points. To avoid this problem, the extreme points are repeated to allow a complete interpolation of the control points” (Pacheco et al., 2010, p. 14).
Figure 2 shows simple checks added to determine the current control point, which dictates whether the tangent is found from actual control point position vectors or if the exterior points must be duplicated to identify the correct tangent angle.
 |
| Figure 2: Checks to ensure correct vector values are used for each control point position |
After several attempts at constructing the complete cubic curve, I found that calculation of each connecting segment between sequential control points must be found in order – which joins each segment into a continuous curve.
This is done within a for loop, which progresses to the next pair of adjacent control point pairs when incremented.
Within this for loop the interpolation value is calculated before another loop calculates the positions and tangent angles for every resolution point in the segment. The function which solves for the position and tangent vectors is shown in figure 3.
 |
| Figure 3: Calculation of position and tangent angle for each curve resolution point |
Knowing that a Catmull-Rom spline is a series of Hermite curves the resolution point positions of the current control points segment are found with the polynomial equation stated within the code comment in figure 3.
Figure 3 also shows calculation of the derivative of the polynomial returning the tangents angle at each resolution point throughout the curve.
The result:
 |
| Figure 4: My Catmull-Rom curve implementation |
As the same equations apply to a 3D space, having used Vector3 allows the implementation to work along the z-axis too.
 |
| Figure 5: My Catmull-Rom curve implementation, 3D |
As explored by Twigg (2003), the control point tangents can be modified with a tension value to achieve “different results of smoothness for a same group of control points, increasing the domain of generated trajectories” (Pacheco et al., 2010, p. 14).
Different tension values can be applied by altering the fraction value used in the equation shown in figure 1. This is shown during run time in figure 6.
 |
| Figure 6: Adjustment of tension variable |
At a tension value of 0, the linear Hermite curves which form each segment can be clearly seen. Increasing the tension value increases the smoothness of the curve, though the larger the tension value the more prominent the oscillations in the curve become due to the properties of polynomial interpolation.
When the tension parameter is more than 0, for the curve to accommodate the resulting tangent angle through each control point the curve segments are placed outside of the control point polygon convex hull.
The implemented curve exhibits its properties discussed above.
Unfortunately, the curves behaviour is less suited to my solution than I had initially anticipated. In practice the overfitting demonstrated in the curve is likely to create irregular and unnatural trajectories. The unwanted effects may be lessened by the damped seek of my IK solution, though it will not be completely removed.
There is also slight potential for the parts of the curve which fall outside of the convex hull to detect intersection with obstacles which may result in recalculation of the trajectory which would not be necessary with an alternate implementation.
References
Breen, D., Regli, W. and Peysakhov, M. (n.d.). Hermiteand Catmull-Rom Curves. Available at: https://www.cs.drexel.edu/~david/Classes/CS536/Lectures/L-04_Hermite_Catmull_Rom.6.pdf [Accessed 14 Dec. 2018].
George, G., Moitra, A., Caculo, S. and Prince, A. (2018). Efficient Architecture for Implementation of Hermite Interpolation on FPGA. 2018 Conference on Design and Architectures for Signal and Image Processing (DASIP), [online] pp.7-11. Available at: https://ieeexplore-ieee-org.uos.idm.oclc.org/stamp/stamp.jsp?tp=&arnumber=8596920 [Accessed 14 Dec. 2018].
Lengyel, E. (2012). Mathematics for 3D Game Programming and Computer Graphics. 3rd ed. pp.329-335.
Pacheco, R., Hounsell, M., Rosso, R. and Leal, A. (2010). Smooth trajectory tracking interpolation on a robot simulator. 2010 Latin American Robotics Symposium and Intelligent Robotics Meeting, [online] Available at: https://www.researchgate.net/publication/236634816_Smooth_Trajectory_Tracking_Interpolation_on_a_Robot_Simulator [Accessed 15 Dec. 2018].
Sprunk, C. (2008). Planning Motion Trajectories forMobile Robots Using Splines. Master of Science. Albert-Ludwigs-Universitat Freiburg. [online] Available at: http://www2.informatik.uni-freiburg.de/~lau/students/Sprunk2008.pdf [Accessed 17 Dec. 2018]
Twigg, C. (2003). Catmull-Rom splines. [online] Available at: https://www.cs.cmu.edu/~fp/courses/graphics/asst5/catmullRom.pdf [Accessed 17 Dec. 2018].
Wang, X., Jiang, P., Li, D. and Sun, T. (2017). Curvature Continuous and Bounded Path Planning for Fixed-Wing UAVs. [online] Available at: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5620579/ [Accessed 17 Dec. 2018].
Bibiography
Sellarès, T. (n.d.). Curves. Available at: http://ima.udg.edu/~sellares/MEG/CurvesMEG09.pdf [Accessed 14 Dec. 2018].
