1// tSpline.h 
2// 
3// Implementations for splines and paths with various degrees of smoothness. A 'path', or 'spline', is arbitrarily long 
4// and may be composed of smaller path sections called 'curves'. For example, a Bezier path is made from multiple 
5// Bezier curves. Implementations for piecewise-linear paths, Hermite/Bezier curves and paths, and Nonuniform 
6// Nonrational Cubic-Basis splines can be found in this file. 
7// 
8// Regarding naming, the word 'spline' refers to any path that is composed of piecewise parts. Strictly speaking one 
9// could call a composite of multiple Bezier curves a 'Bezier Spline' but it is not a common term. In this file the 
10// word 'path' is used for a composite of Bezier curves or a composite of line segments, and we reserve the word spline 
11// for paths composed of multiple cubic polynomial pieces. 
12// 
13// Copyright (c) 2006, 2017, 2020 Tristan Grimmer. 
14// Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby 
15// granted, provided that the above copyright notice and this permission notice appear in all copies. 
16// 
17// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL 
18// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, 
19// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN 
20// AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 
21// PERFORMANCE OF THIS SOFTWARE. 
22 
23#pragma once 
24#include <Foundation/tList.h> 
25#include "Math/tLinearAlgebra.h" 
26#include "Math/tVector3.h" 
27namespace tMath 
28{ 
29 
30 
31class tPiecewiseLinearPath 
32{ 
33public: 
34 tPiecewiseLinearPath(); 
35 
36 // The points array is copied during construction. The points are interpolated and numPoints must be >= 2. 
37 tPiecewiseLinearPath(const tVector3* points, int numPoints); 
38 tPiecewiseLinearPath(const tPiecewiseLinearPath& src); 
39 virtual ~tPiecewiseLinearPath() { delete[] Points; delete[] PercentagePoints; } 
40 
41 // Removes any previous points and uses the new ones. 
42 void SetPoints(const tVector3* points, int numPoints); 
43 
44 // If t E [0, numPoints-1] where numPoints-1 is the number of path segments, this function returns a point on the 
45 // path between the first and last points. For t outside this range linear extrapolation is performed. 
46 tVector3 GetPoint(float t) const; 
47 
48 // Same as GetPoint except when t E [0.0, 1.0] it returns the position that 'percentage' along the path. t = 0 is 
49 // the beginning of the path, and t = 1 is the end. 
50 tVector3 GetPercentPoint(float t) const; 
51 
52 bool IsValid() const { return Points ? true : false; } 
53 void Clear(); 
54 int GetNumCurveSegments() const { return NumPoints - 1; } 
55 float GetLength() const { return TotalLength; } 
56 
57private: 
58 int NumPoints; 
59 
60 // The full list of control points managed by this class. 
61 tVector3* Points; 
62 
63 // Each element is the percentage along the path of the corresponding point. 
64 float* PercentagePoints; 
65 float TotalLength; 
66}; 
67 
68 
69// A tBezierCurve represents a single segment of a Bezier path. It knows how to interpret 4 CVs using the Bezier basis 
70// functions. The class implements cubic Bezier curves -- not linear or quadratic. 
71class tBezierCurve 
72{ 
73public: 
74 // The 4 Bezier control points read by this class are managed externally and are not deleted by this class. Make 
75 // sure they exist for the lifetime of this object. 
76 tBezierCurve(tVector3* points) : ControlVerts(points) { } 
77 void GetPoint(tVector3&, float t) const; // t E [0, 1]. 
78 void GetTangent(tVector3&, float t) const; // t E [0, 1]. 
79 float GetClosestParam 
80 ( 
81 const tVector3& pos, tComponents components = tMath::tComponent_All, 
82 float paramThreshold = tMath::Epsilon 
83 ) const { return GetClosestParamRec(pos, components, 0.0f, 1.0f, paramThreshold); } 
84 
85private: 
86 float GetClosestParamRec(const tVector3& pos, tComponents components, float beginT, float endT, float thresholdT) const; 
87 const tVector3* ControlVerts; // Not owned by this class. 
88}; 
89 
90 
91// A tBezierPath is made of a collection of Bezier curves. If two points are supplied they become the end points of one 
92// BezierCurve and the 2 interior CVs are generated, creating a small straight line. For 3 points the middle point will 
93// be on both BezierCurves and each curve will have equal tangents at that point. 
94class tBezierPath 
95{ 
96public: 
97 enum class tMode 
98 { 
99 InternalCVs, // Supplied points are copied on construction and managed by BezierPath. 
100 ExternalCVs // Points are referenced by the BezierCurve and must have required lifetime. 
101 }; 
102 
103 enum class tType 
104 { 
105 Open, 
106 Closed 
107 }; 
108 
109 // Construct an initially invalid path. Call SetControlVerts or InterpolatePoints sometime later. 
110 tBezierPath() : Mode(tMode::InternalCVs), Type(tType::Open), NumCurveSegments(0), NumControlVerts(0), ControlVerts(nullptr) { } 
111 
112 // The term 'knot' is another name for a point right on the path (an interpolated point). With this constructor the 
113 // knots are supplied and interpolated. NumKnots must be >= 2. Interior Cvs are generated transparently and 
114 // automatically. The points array is copied on construction and the mode is set to InternalCVs. 
115 tBezierPath(const tVector3* knots, int numKnots, tType type = tType::Open) : Mode(tMode::InternalCVs), Type(tType::Open), NumCurveSegments(0), NumControlVerts(0), ControlVerts(nullptr) { InterpolatePoints(knots, numKnots, type); } 
116 
117 // This constructor allows all CVs including non-interpolated ones to be set. Gives fine control over the tangents. 
118 // For open paths numCVs must be some multiple of 3 plus an initial minimum of 4 CVs (4, 7, 10, 13, etc). For a 
119 // closed path the last CV must match the first and the minimum number is 7 (7, 10, 13, 16, etc). 
120 tBezierPath(const tVector3* CVs, int numCVs, tMode mode, tType type = tType::Open) : Mode(tMode::InternalCVs), Type(tType::Open), NumCurveSegments(0), NumControlVerts(0), ControlVerts(nullptr) { SetControlVerts(CVs, numCVs, mode, type); } 
121 
122 // The copy constructor retains the source's ownership mode and copies the points only if mode is InternalCVs.  
123 tBezierPath(const tBezierPath&); 
124 virtual ~tBezierPath() { Clear(); } 
125 
126 tType GetType() const { return Type; } 
127 bool IsClosed() const { return (Type == tType::Closed) ? true : false; } 
128 bool IsValid() const { return (NumCurveSegments > 0) ? true : false; } 
129 void Clear(); 
130 
131 // A closed path will have one more segment than an open for the same number of interpolated points. 
132 int GetNumCurveSegments() const { return NumCurveSegments; } 
133 float GetMaxParam() const { return float(NumCurveSegments); } 
134 
135 // Access to the raw CVs. 
136 int GetNumControlVerts() const { return NumControlVerts; } 
137 const tVector3* GetControlVerts() const { return ControlVerts; } 
138 float ComputeApproxParamPerCoordinateUnit(tComponents = tComponent_All) const; 
139 
140 // Sets the mode to internal and interpolates the supplied points. Internally generates any interior CVs. numPoints 
141 // must be >= 2. @todo Allow the mode to be set by returning the new array of CVs if the mode is external. 
142 void InterpolatePoints(const tVector3* knots, int numKnots, tType); 
143 
144 // Properly deletes any owned previous points. If the new mode is external the CVs must remain valid for the 
145 // lifetime of the path. For internal mode the CVs are copied. For a closed path the last CV must match the first. 
146 void SetControlVerts(const tVector3* CVs, int numCVs, tMode, tType); 
147 
148 // t E [0, numSegments]. If the type is closed, the number of segments is one more than the equivalent open path. 
149 void GetPoint(tVector3&, float t) const; 
150 
151 // Does the same as GetPoint except that t is normalized to be E [0, 1] over all segments. The beginning of the curve 
152 // is at t = 0 and the end at t = 1. Closed paths allow a value bigger than 1 in which case they loop. 
153 void GetPointNorm(tVector3& point, float t) const { GetPoint(point, t * float(NumCurveSegments)); } 
154 
155 // Similar to GetPoint but returns the tangent at the specified point on the path. The tangent is not normalized. 
156 // The longer the tangent the 'more influence' it has pulling the path in that direction. 
157 void GetTangent(tVector3&, float t) const; 
158 
159 // Does the same as GetYangent except that t is normalized to be E [0, 1] over all segments. 
160 void GetTangentNorm(tVector3& tangent, float t) const { GetTangent(tangent, t * float(NumCurveSegments)); } 
161 
162 // This is an _optional_ object the client may create and maintain to make the GetClosestParam function work far 
163 // more quickly when the position being passed in is not jumping around. The client is not required to call the 
164 // member functions of this object. 
165 struct tFastSectionState 
166 { 
167 tFastSectionState() : Components(tComponent_All), Sections(tListMode::ListOwns) { } 
168 tFastSectionState(const tFastSectionState&); 
169 tFastSectionState& operator=(const tFastSectionState&); 
170 ~tFastSectionState() { } 
171 
172 void Clear() const { Sections.Empty(); Components = tComponent_All; } 
173 
174 // Initializes the state. A bit slower than update. 
175 void Set(const tVector3& pos, tComponents components, const tVector3* cvs, int numCVs) const; 
176 void Update(const tVector3& pos, const tVector3* cvs) const; 
177 
178 struct tSectionInfo : public tLink<tSectionInfo> 
179 { 
180 tSectionInfo(int i) : StartIndex(i) { } 
181 int StartIndex; 
182 }; 
183 
184 static tComponents CompareComponents; 
185 static tVector3 ComparePos; 
186 static const tVector3* CompareControlVerts; 
187 static bool CompareSections(const tSectionInfo& a, const tSectionInfo& b); 
188 
189 mutable tComponents Components; 
190 mutable tList<tSectionInfo> Sections; 
191 }; 
192 
193 // This function returns a single closest point. There may be more than one point on the path at the same distance. 
194 // Use ComputeApproxParamPerCoordinateUnit to determine a good paramThreshold. eg. Working in 3D in meters and you 
195 // want a 15cm threshold, use: paramThreshold = ComputeApproxParamPerCoordinateUnit(X | Y | Z) * 0.15f. 
196 float GetClosestParam 
197 ( 
198 const tVector3& pos, uint32 coords, float paramThreshold, 
199 const tFastSectionState& = tFastSectionState() 
200 ) const; 
201 
202 // Same as GetClosestParam but returns the param normalized to [0.0, 1.0]. 
203 float GetClosestParamNorm 
204 ( 
205 const tVector3& pos, uint32 coords, float paramThreshold, 
206 const tFastSectionState& optObj = tFastSectionState() 
207 ) const { return GetClosestParam(pos, coords, paramThreshold, optObj) / float(NumCurveSegments); } 
208 
209private: 
210 tMode Mode; 
211 tType Type; 
212 int NumCurveSegments; 
213 int NumControlVerts; 
214 tVector3* ControlVerts; 
215}; 
216 
217 
218// A Nonuniform, Nonrational, Cubic Basis Spline. Nonuniform allows knots to be spaced unevenly in the parametric 
219// parameter t. Nonrational means no ratio of polynomials, so no conics and not invariant under perspective 
220// transformations. 
221class tNNBSpline 
222{ 
223public: 
224 // The number of values in the knotValueSeq is assumed to be 4 greater than numControlPoints. All memory is managed 
225 // by whoever calls this constructor and is not given to tNNBSpline. The paramRange var specifies how 
226 // large t may get in subsequent GetPoint calls. 
227 tNNBSpline(int* knotValueSeq, tVector3* CVs, int numCVs, float paramRange = 100.0f); 
228 virtual ~tNNBSpline(); 
229 
230 // In this call the t value should range from 0.0 to paramRange inclusive. 
231 tVector3 GetPoint(float t); 
232 
233private: 
234 // Curve segment Qi is defined over 3 <= i < m, t sub i <= t < t sub (i+1) 
235 tVector3 Q(int i, float t); 
236 
237 // Blending functions. Internal t values are as specified as in Foley/Van Damm. Different from externally seen t. 
238 float B1(int i, float t); 
239 float B2(int i, float t); 
240 float B3(int i, float t); 
241 float B4(int i, float t); 
242 
243 int* KVS; // The knot value sequence. 
244 tVector3* CPs; // The control points. 
245 
246 // CurrIndex is stored for efficiency so that when GetPoint is called with a t value close to the previous time, we 
247 // can find the curve segment quickly. 
248 float CurrIndex; 
249 float MinParam; // This is t sub 3 actually. 
250 float MaxParam; // This is t sub (m+1) actually. 
251 int MaxCPIndex; // The number of control points - 1. 
252}; 
253 
254 
255} 
256 
257 
258// Implementation below this line. 
259 
260 
261inline tMath::tPiecewiseLinearPath::tPiecewiseLinearPath() : 
262 NumPoints(0), 
263 Points(0), 
264 PercentagePoints(0), 
265 TotalLength(0.0f) 
266{ 
267} 
268 
269 
270inline tMath::tPiecewiseLinearPath::tPiecewiseLinearPath(const tVector3* points, int numPoints) : 
271 NumPoints(0), 
272 Points(0), 
273 PercentagePoints(0), 
274 TotalLength(0.0f) 
275{ 
276 SetPoints(points, numPoints); 
277} 
278 
279 
280inline tMath::tPiecewiseLinearPath::tPiecewiseLinearPath(const tPiecewiseLinearPath& src) : 
281 NumPoints(0), 
282 Points(0), 
283 PercentagePoints(0), 
284 TotalLength(0.0f) 
285{ 
286 SetPoints(src.Points, src.NumPoints); 
287} 
288 
289 
290inline void tMath::tPiecewiseLinearPath::Clear() 
291{ 
292 delete[] Points; 
293 Points = nullptr; 
294 
295 delete[] PercentagePoints; 
296 PercentagePoints = nullptr; 
297 
298 NumPoints = 0; 
299 TotalLength = 0.0f; 
300} 
301