001// Copyright (c) FIRST and other WPILib contributors. 002// Open Source Software; you can modify and/or share it under the terms of 003// the WPILib BSD license file in the root directory of this project. 004 005package edu.wpi.first.math.spline; 006 007import edu.wpi.first.math.geometry.Pose2d; 008import edu.wpi.first.math.geometry.Translation2d; 009import java.util.Arrays; 010import java.util.List; 011import org.ejml.simple.SimpleMatrix; 012 013public final class SplineHelper { 014 /** Private constructor because this is a utility class. */ 015 private SplineHelper() {} 016 017 /** 018 * Returns 2 cubic control vectors from a set of exterior waypoints and interior translations. 019 * 020 * @param start The starting pose. 021 * @param interiorWaypoints The interior waypoints. 022 * @param end The ending pose. 023 * @return 2 cubic control vectors. 024 */ 025 public static Spline.ControlVector[] getCubicControlVectorsFromWaypoints( 026 Pose2d start, Translation2d[] interiorWaypoints, Pose2d end) { 027 // Generate control vectors from poses. 028 Spline.ControlVector initialCV; 029 Spline.ControlVector endCV; 030 031 // Chooses a magnitude automatically that makes the splines look better. 032 if (interiorWaypoints.length < 1) { 033 double scalar = start.getTranslation().getDistance(end.getTranslation()) * 1.2; 034 initialCV = getCubicControlVector(scalar, start); 035 endCV = getCubicControlVector(scalar, end); 036 } else { 037 double scalar = start.getTranslation().getDistance(interiorWaypoints[0]) * 1.2; 038 initialCV = getCubicControlVector(scalar, start); 039 scalar = 040 end.getTranslation().getDistance(interiorWaypoints[interiorWaypoints.length - 1]) * 1.2; 041 endCV = getCubicControlVector(scalar, end); 042 } 043 return new Spline.ControlVector[] {initialCV, endCV}; 044 } 045 046 /** 047 * Returns quintic splines from a set of waypoints. 048 * 049 * @param waypoints The waypoints 050 * @return array of splines. 051 */ 052 public static QuinticHermiteSpline[] getQuinticSplinesFromWaypoints(List<Pose2d> waypoints) { 053 QuinticHermiteSpline[] splines = new QuinticHermiteSpline[waypoints.size() - 1]; 054 for (int i = 0; i < waypoints.size() - 1; ++i) { 055 var p0 = waypoints.get(i); 056 var p1 = waypoints.get(i + 1); 057 058 // This just makes the splines look better. 059 final var scalar = 1.2 * p0.getTranslation().getDistance(p1.getTranslation()); 060 061 var controlVecA = getQuinticControlVector(scalar, p0); 062 var controlVecB = getQuinticControlVector(scalar, p1); 063 064 splines[i] = 065 new QuinticHermiteSpline(controlVecA.x, controlVecB.x, controlVecA.y, controlVecB.y); 066 } 067 return splines; 068 } 069 070 /** 071 * Returns a set of cubic splines corresponding to the provided control vectors. The user is free 072 * to set the direction of the start and end point. The directions for the middle waypoints are 073 * determined automatically to ensure continuous curvature throughout the path. 074 * 075 * @param start The starting control vector. 076 * @param waypoints The middle waypoints. This can be left blank if you only wish to create a path 077 * with two waypoints. 078 * @param end The ending control vector. 079 * @return A vector of cubic hermite splines that interpolate through the provided waypoints and 080 * control vectors. 081 */ 082 public static CubicHermiteSpline[] getCubicSplinesFromControlVectors( 083 Spline.ControlVector start, Translation2d[] waypoints, Spline.ControlVector end) { 084 CubicHermiteSpline[] splines = new CubicHermiteSpline[waypoints.length + 1]; 085 086 double[] xInitial = start.x; 087 double[] yInitial = start.y; 088 double[] xFinal = end.x; 089 double[] yFinal = end.y; 090 091 if (waypoints.length > 1) { 092 Translation2d[] newWaypts = new Translation2d[waypoints.length + 2]; 093 094 // Create an array of all waypoints, including the start and end. 095 newWaypts[0] = new Translation2d(xInitial[0], yInitial[0]); 096 System.arraycopy(waypoints, 0, newWaypts, 1, waypoints.length); 097 newWaypts[newWaypts.length - 1] = new Translation2d(xFinal[0], yFinal[0]); 098 099 // Populate tridiagonal system for clamped cubic 100 /* See: 101 https://www.uio.no/studier/emner/matnat/ifi/nedlagte-emner/INF-MAT4350/h08 102 /undervisningsmateriale/chap7alecture.pdf 103 */ 104 // Above-diagonal of tridiagonal matrix, zero-padded 105 final double[] a = new double[newWaypts.length - 2]; 106 107 // Diagonal of tridiagonal matrix 108 final double[] b = new double[newWaypts.length - 2]; 109 Arrays.fill(b, 4.0); 110 111 // Below-diagonal of tridiagonal matrix, zero-padded 112 final double[] c = new double[newWaypts.length - 2]; 113 114 // rhs vectors 115 final double[] dx = new double[newWaypts.length - 2]; 116 final double[] dy = new double[newWaypts.length - 2]; 117 118 // solution vectors 119 final double[] fx = new double[newWaypts.length - 2]; 120 final double[] fy = new double[newWaypts.length - 2]; 121 122 // populate above-diagonal and below-diagonal vectors 123 a[0] = 0.0; 124 for (int i = 0; i < newWaypts.length - 3; i++) { 125 a[i + 1] = 1; 126 c[i] = 1; 127 } 128 c[c.length - 1] = 0.0; 129 130 // populate rhs vectors 131 dx[0] = 3 * (newWaypts[2].getX() - newWaypts[0].getX()) - xInitial[1]; 132 dy[0] = 3 * (newWaypts[2].getY() - newWaypts[0].getY()) - yInitial[1]; 133 134 if (newWaypts.length > 4) { 135 for (int i = 1; i <= newWaypts.length - 4; i++) { 136 // dx and dy represent the derivatives of the internal waypoints. The derivative 137 // of the second internal waypoint should involve the third and first internal waypoint, 138 // which have indices of 1 and 3 in the newWaypts list (which contains ALL waypoints). 139 dx[i] = 3 * (newWaypts[i + 2].getX() - newWaypts[i].getX()); 140 dy[i] = 3 * (newWaypts[i + 2].getY() - newWaypts[i].getY()); 141 } 142 } 143 144 dx[dx.length - 1] = 145 3 * (newWaypts[newWaypts.length - 1].getX() - newWaypts[newWaypts.length - 3].getX()) 146 - xFinal[1]; 147 dy[dy.length - 1] = 148 3 * (newWaypts[newWaypts.length - 1].getY() - newWaypts[newWaypts.length - 3].getY()) 149 - yFinal[1]; 150 151 // Compute solution to tridiagonal system 152 thomasAlgorithm(a, b, c, dx, fx); 153 thomasAlgorithm(a, b, c, dy, fy); 154 155 double[] newFx = new double[fx.length + 2]; 156 double[] newFy = new double[fy.length + 2]; 157 158 newFx[0] = xInitial[1]; 159 newFy[0] = yInitial[1]; 160 System.arraycopy(fx, 0, newFx, 1, fx.length); 161 System.arraycopy(fy, 0, newFy, 1, fy.length); 162 newFx[newFx.length - 1] = xFinal[1]; 163 newFy[newFy.length - 1] = yFinal[1]; 164 165 for (int i = 0; i < newFx.length - 1; i++) { 166 splines[i] = 167 new CubicHermiteSpline( 168 new double[] {newWaypts[i].getX(), newFx[i]}, 169 new double[] {newWaypts[i + 1].getX(), newFx[i + 1]}, 170 new double[] {newWaypts[i].getY(), newFy[i]}, 171 new double[] {newWaypts[i + 1].getY(), newFy[i + 1]}); 172 } 173 } else if (waypoints.length == 1) { 174 final var xDeriv = (3 * (xFinal[0] - xInitial[0]) - xFinal[1] - xInitial[1]) / 4.0; 175 final var yDeriv = (3 * (yFinal[0] - yInitial[0]) - yFinal[1] - yInitial[1]) / 4.0; 176 177 double[] midXControlVector = {waypoints[0].getX(), xDeriv}; 178 double[] midYControlVector = {waypoints[0].getY(), yDeriv}; 179 180 splines[0] = 181 new CubicHermiteSpline( 182 xInitial, midXControlVector, 183 yInitial, midYControlVector); 184 splines[1] = 185 new CubicHermiteSpline( 186 midXControlVector, xFinal, 187 midYControlVector, yFinal); 188 } else { 189 splines[0] = 190 new CubicHermiteSpline( 191 xInitial, xFinal, 192 yInitial, yFinal); 193 } 194 return splines; 195 } 196 197 /** 198 * Returns a set of quintic splines corresponding to the provided control vectors. The user is 199 * free to set the direction of all control vectors. Continuous curvature is guaranteed throughout 200 * the path. 201 * 202 * @param controlVectors The control vectors. 203 * @return A vector of quintic hermite splines that interpolate through the provided waypoints. 204 */ 205 public static QuinticHermiteSpline[] getQuinticSplinesFromControlVectors( 206 Spline.ControlVector[] controlVectors) { 207 QuinticHermiteSpline[] splines = new QuinticHermiteSpline[controlVectors.length - 1]; 208 for (int i = 0; i < controlVectors.length - 1; i++) { 209 var xInitial = controlVectors[i].x; 210 var xFinal = controlVectors[i + 1].x; 211 var yInitial = controlVectors[i].y; 212 var yFinal = controlVectors[i + 1].y; 213 splines[i] = 214 new QuinticHermiteSpline( 215 xInitial, xFinal, 216 yInitial, yFinal); 217 } 218 return splines; 219 } 220 221 /** 222 * Optimizes the curvature of 2 or more quintic splines at knot points. Overall, this reduces the 223 * integral of the absolute value of the second derivative across the set of splines. 224 * 225 * @param splines An array of un-optimized quintic splines. 226 * @return An array of optimized quintic splines. 227 */ 228 @SuppressWarnings({"LocalVariableName", "PMD.AvoidInstantiatingObjectsInLoops"}) 229 public static QuinticHermiteSpline[] optimizeCurvature(QuinticHermiteSpline[] splines) { 230 // If there's only spline in the array, we can't optimize anything so just return that. 231 if (splines.length < 2) { 232 return splines; 233 } 234 235 // Implements Section 4.1.2 of 236 // http://www2.informatik.uni-freiburg.de/~lau/students/Sprunk2008.pdf. 237 238 // Cubic splines minimize the integral of the second derivative's absolute value. Therefore, we 239 // can create cubic splines with the same 0th and 1st derivatives and the provided quintic 240 // splines, find the second derivative of those cubic splines and then use a weighted average 241 // for the second derivatives of the quintic splines. 242 243 QuinticHermiteSpline[] optimizedSplines = new QuinticHermiteSpline[splines.length]; 244 for (int i = 0; i < splines.length - 1; ++i) { 245 QuinticHermiteSpline a = splines[i]; 246 QuinticHermiteSpline b = splines[i + 1]; 247 248 // Get the control vectors that created the quintic splines above. 249 Spline.ControlVector aInitial = a.getInitialControlVector(); 250 Spline.ControlVector aFinal = a.getFinalControlVector(); 251 Spline.ControlVector bInitial = b.getInitialControlVector(); 252 Spline.ControlVector bFinal = b.getFinalControlVector(); 253 254 // Create cubic splines with the same control vectors. 255 CubicHermiteSpline ca = new CubicHermiteSpline(aInitial.x, aFinal.x, aInitial.y, aFinal.y); 256 CubicHermiteSpline cb = new CubicHermiteSpline(bInitial.x, bFinal.x, bInitial.y, bFinal.y); 257 258 // Calculate the second derivatives at the knot points. 259 SimpleMatrix bases = new SimpleMatrix(4, 1, true, new double[] {1, 1, 1, 1}); 260 SimpleMatrix combinedA = ca.getCoefficients().mult(bases); 261 262 double ddxA = combinedA.get(4, 0); 263 double ddyA = combinedA.get(5, 0); 264 double ddxB = cb.getCoefficients().get(4, 1); 265 double ddyB = cb.getCoefficients().get(5, 1); 266 267 // Calculate the parameters for the weighted average. 268 double dAB = Math.hypot(aFinal.x[0] - aInitial.x[0], aFinal.y[0] - aInitial.y[0]); 269 double dBC = Math.hypot(bFinal.x[0] - bInitial.x[0], bFinal.y[0] - bInitial.y[0]); 270 double alpha = dBC / (dAB + dBC); 271 double beta = dAB / (dAB + dBC); 272 273 // Calculate the weighted average. 274 double ddx = alpha * ddxA + beta * ddxB; 275 double ddy = alpha * ddyA + beta * ddyB; 276 277 // Create new splines. 278 optimizedSplines[i] = 279 new QuinticHermiteSpline( 280 aInitial.x, 281 new double[] {aFinal.x[0], aFinal.x[1], ddx}, 282 aInitial.y, 283 new double[] {aFinal.y[0], aFinal.y[1], ddy}); 284 optimizedSplines[i + 1] = 285 new QuinticHermiteSpline( 286 new double[] {bInitial.x[0], bInitial.x[1], ddx}, 287 bFinal.x, 288 new double[] {bInitial.y[0], bInitial.y[1], ddy}, 289 bFinal.y); 290 } 291 return optimizedSplines; 292 } 293 294 /** 295 * Thomas algorithm for solving tridiagonal systems Af = d. 296 * 297 * @param a the values of A above the diagonal 298 * @param b the values of A on the diagonal 299 * @param c the values of A below the diagonal 300 * @param d the vector on the rhs 301 * @param solutionVector the unknown (solution) vector, modified in-place 302 */ 303 private static void thomasAlgorithm( 304 double[] a, double[] b, double[] c, double[] d, double[] solutionVector) { 305 int N = d.length; 306 307 double[] cStar = new double[N]; 308 double[] dStar = new double[N]; 309 310 // This updates the coefficients in the first row 311 // Note that we should be checking for division by zero here 312 cStar[0] = c[0] / b[0]; 313 dStar[0] = d[0] / b[0]; 314 315 // Create the c_star and d_star coefficients in the forward sweep 316 for (int i = 1; i < N; i++) { 317 double m = 1.0 / (b[i] - a[i] * cStar[i - 1]); 318 cStar[i] = c[i] * m; 319 dStar[i] = (d[i] - a[i] * dStar[i - 1]) * m; 320 } 321 solutionVector[N - 1] = dStar[N - 1]; 322 // This is the reverse sweep, used to update the solution vector f 323 for (int i = N - 2; i >= 0; i--) { 324 solutionVector[i] = dStar[i] - cStar[i] * solutionVector[i + 1]; 325 } 326 } 327 328 private static Spline.ControlVector getCubicControlVector(double scalar, Pose2d point) { 329 return new Spline.ControlVector( 330 new double[] {point.getX(), scalar * point.getRotation().getCos()}, 331 new double[] {point.getY(), scalar * point.getRotation().getSin()}); 332 } 333 334 private static Spline.ControlVector getQuinticControlVector(double scalar, Pose2d point) { 335 return new Spline.ControlVector( 336 new double[] {point.getX(), scalar * point.getRotation().getCos(), 0.0}, 337 new double[] {point.getY(), scalar * point.getRotation().getSin(), 0.0}); 338 } 339}