All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
splineData.h
1//
2// Copyright 2024 Pixar
3//
4// Licensed under the terms set forth in the LICENSE.txt file available at
5// https://openusd.org/license.
6//
7
8#ifndef PXR_BASE_TS_SPLINE_DATA_H
9#define PXR_BASE_TS_SPLINE_DATA_H
10
11#include "pxr/pxr.h"
12#include "pxr/base/ts/api.h"
13#include "pxr/base/ts/knotData.h"
14#include "pxr/base/ts/types.h"
15#include "pxr/base/ts/typeHelpers.h"
18#include "pxr/base/tf/type.h"
19#include "pxr/base/tf/stl.h"
20
21#include <vector>
22#include <unordered_map>
23#include <algorithm>
24#include <iterator>
25#include <utility>
26#include <cmath>
27
28PXR_NAMESPACE_OPEN_SCOPE
29
30class TsSpline;
31
32
33// Primary data structure for splines. Abstract; subclasses store knot data,
34// which is flexibly typed (double/float/half). This is the unit of data that
35// is managed by shared_ptr, and forms the basis of copy-on-write data sharing.
36//
37struct Ts_SplineData
38{
39public:
40 // If valueType is known, create a TypedSplineData of the specified type.
41 // If valueType is unknown, create a TypedSplineData<double> to store
42 // overall spline parameters in the absence of a value type; this assumes
43 // that when knots arrive, they are most likely to be double-typed. If
44 // overallParamSource is provided, it is a previous overall-only struct, and
45 // our guess about double was wrong, so we are transferring the overall
46 // parameters.
47 static Ts_SplineData* Create(
48 TfType valueType,
49 const Ts_SplineData *overallParamSource = nullptr);
50
51 virtual ~Ts_SplineData();
52
53public:
54 // Virtual interface for typed data.
55
56 virtual TfType GetValueType() const = 0;
57 virtual size_t GetKnotStructSize() const = 0;
58 virtual Ts_SplineData* Clone() const = 0;
59
60 virtual bool operator==(const Ts_SplineData &other) const = 0;
61
62 virtual void ReserveForKnotCount(size_t count) = 0;
63 virtual void PushKnot(
64 const Ts_KnotData *knotData,
65 const VtDictionary &customData) = 0;
66 virtual size_t SetKnot(
67 const Ts_KnotData *knotData,
68 const VtDictionary &customData) = 0;
69
70 virtual Ts_KnotData* CloneKnotAtIndex(size_t index) const = 0;
71 virtual Ts_KnotData* CloneKnotAtTime(TsTime time) const = 0;
72 virtual Ts_KnotData* GetKnotPtrAtIndex(size_t index) = 0;
73 virtual Ts_TypedKnotData<double>
74 GetKnotDataAsDouble(size_t index) const = 0;
75
76 virtual void ClearKnots() = 0;
77 virtual void RemoveKnotAtTime(TsTime time) = 0;
78
79 virtual void ApplyOffsetAndScale(
80 TsTime offset,
81 double scale) = 0;
82
83 virtual bool HasValueBlocks() const = 0;
84 virtual bool HasValueBlockAtTime(TsTime time) const = 0;
85
86public:
87 // Returns whether there is a valid inner-loop configuration. If
88 // firstProtoIndexOut is provided, it receives the index of the first knot
89 // in the prototype.
90 bool HasInnerLoops(
91 size_t *firstProtoIndexOut = nullptr) const;
92
93public:
94 // BITFIELDS - note: for enum-typed bitfields, we declare one bit more than
95 // is minimally needed to represent all declared enum values. For example,
96 // TsCurveType has only two values, so it should be representable in one
97 // bit. However, compilers are free to choose the underlying representation
98 // of enums, and some platforms choose signed values, meaning that we
99 // actually need one bit more, so that we can hold the sign bit. We could
100 // declare the enums with unsigned underlying types, but that runs into a
101 // gcc 9.2 bug. We can spare the extra bit; alignment means there is no
102 // difference in struct size.
103
104 // If true, our subtype is authoritative; we know our value type. If false,
105 // then no value type was provided at initialization, and no knots have been
106 // set. In the latter case, we exist only to store overall parameters, and
107 // we have been presumptively created as TypedSplineData<double>.
108 bool isTyped : 1;
109
110 // Whether ApplyOffsetAndScale applies to values also.
111 bool timeValued : 1;
112
113 // Overall spline parameters.
114 TsCurveType curveType : 2;
115 TsExtrapolation preExtrapolation;
116 TsExtrapolation postExtrapolation;
117 TsLoopParams loopParams;
118
119 // A duplicate of the knot times, so that we can maximize locality while
120 // performing binary searches for knots. This is part of the evaluation hot
121 // path; given an eval time, we must find either the knot at that time, or
122 // the knots before and after that time. The entries in this vector
123 // correspond exactly to the entries in the 'knots' vector in
124 // Ts_TypedSplineData. Times are unique and sorted in ascending order.
125 std::vector<TsTime> times;
126
127 // Custom data for knots, sparsely allocated, keyed by time.
128 std::unordered_map<TsTime, VtDictionary> customData;
129};
130
131
132// Concrete subclass of Ts_SplineData. Templated on T, the value type.
133//
134template <typename T>
135struct Ts_TypedSplineData final :
136 public Ts_SplineData
137{
138public:
139 TfType GetValueType() const override;
140 size_t GetKnotStructSize() const override;
141 Ts_SplineData* Clone() const override;
142
143 bool operator==(const Ts_SplineData &other) const override;
144
145 void ReserveForKnotCount(size_t count) override;
146 void PushKnot(
147 const Ts_KnotData *knotData,
148 const VtDictionary &customData) override;
149 size_t SetKnot(
150 const Ts_KnotData *knotData,
151 const VtDictionary &customData) override;
152
153 Ts_KnotData* CloneKnotAtIndex(size_t index) const override;
154 Ts_KnotData* CloneKnotAtTime(TsTime time) const override;
155 Ts_KnotData* GetKnotPtrAtIndex(size_t index) override;
156 Ts_TypedKnotData<double>
157 GetKnotDataAsDouble(size_t index) const override;
158
159 void ClearKnots() override;
160 void RemoveKnotAtTime(TsTime time) override;
161
162 void ApplyOffsetAndScale(
163 TsTime offset,
164 double scale) override;
165
166 bool HasValueBlocks() const override;
167 bool HasValueBlockAtTime(TsTime time) const override;
168
169public:
170 // Per-knot data.
171 std::vector<Ts_TypedKnotData<T>> knots;
172};
173
174
175// Data-access helpers for the Ts implementation. The untyped functions are
176// friends of TsSpline, and retrieve private data pointers.
177
178Ts_SplineData*
179Ts_GetSplineData(TsSpline &spline);
180
181const Ts_SplineData*
182Ts_GetSplineData(const TsSpline &spline);
183
184template <typename T>
185Ts_TypedSplineData<T>*
186Ts_GetTypedSplineData(TsSpline &spline);
187
188template <typename T>
189const Ts_TypedSplineData<T>*
190Ts_GetTypedSplineData(const TsSpline &spline);
191
192
194// TEMPLATE IMPLEMENTATIONS
195
196template <typename T>
197TfType Ts_TypedSplineData<T>::GetValueType() const
198{
199 if (!isTyped)
200 {
201 return TfType();
202 }
203
204 return Ts_GetType<T>();
205}
206
207template <typename T>
208size_t Ts_TypedSplineData<T>::GetKnotStructSize() const
209{
210 return sizeof(Ts_TypedKnotData<T>);
211}
212
213template <typename T>
214Ts_SplineData*
215Ts_TypedSplineData<T>::Clone() const
216{
217 return new Ts_TypedSplineData<T>(*this);
218}
219
220template <typename T>
221bool Ts_TypedSplineData<T>::operator==(
222 const Ts_SplineData &other) const
223{
224 // Compare non-templated data.
225 if (isTyped != other.isTyped
226 || timeValued != other.timeValued
227 || curveType != other.curveType
228 || preExtrapolation != other.preExtrapolation
229 || postExtrapolation != other.postExtrapolation
230 || loopParams != other.loopParams
231 || customData != other.customData)
232 {
233 return false;
234 }
235
236 // Downcast to our value type. If other is not of the same type, we're not
237 // equal.
238 const Ts_TypedSplineData<T>* const typedOther =
239 dynamic_cast<const Ts_TypedSplineData<T>*>(&other);
240 if (!typedOther)
241 {
242 return false;
243 }
244
245 // Compare all knots.
246 return knots == typedOther->knots;
247}
248
249template <typename T>
250void Ts_TypedSplineData<T>::ReserveForKnotCount(
251 const size_t count)
252{
253 times.reserve(count);
254 knots.reserve(count);
255}
256
257template <typename T>
258void Ts_TypedSplineData<T>::PushKnot(
259 const Ts_KnotData* const knotData,
260 const VtDictionary &customDataIn)
261{
262 const Ts_TypedKnotData<T>* const typedKnotData =
263 static_cast<const Ts_TypedKnotData<T>*>(knotData);
264
265 times.push_back(knotData->time);
266 knots.push_back(*typedKnotData);
267
268 if (!customDataIn.empty())
269 {
270 customData[knotData->time] = customDataIn;
271 }
272}
273
274template <typename T>
275size_t Ts_TypedSplineData<T>::SetKnot(
276 const Ts_KnotData* const knotData,
277 const VtDictionary &customDataIn)
278{
279 const Ts_TypedKnotData<T>* const typedKnotData =
280 static_cast<const Ts_TypedKnotData<T>*>(knotData);
281
282 // Use binary search to find insert-or-overwrite position.
283 const auto it =
284 std::lower_bound(times.begin(), times.end(), knotData->time);
285 const size_t idx =
286 it - times.begin();
287 const bool overwrite =
288 (it != times.end() && *it == knotData->time);
289
290 // Insert or overwrite new time and knot data.
291 if (overwrite)
292 {
293 times[idx] = knotData->time;
294 knots[idx] = *typedKnotData;
295 }
296 else
297 {
298 times.insert(it, knotData->time);
299 knots.insert(knots.begin() + idx, *typedKnotData);
300 }
301
302 // Store customData, if any.
303 if (!customDataIn.empty())
304 {
305 customData[knotData->time] = customDataIn;
306 }
307
308 return idx;
309}
310
311template <typename T>
312Ts_KnotData*
313Ts_TypedSplineData<T>::CloneKnotAtIndex(
314 const size_t index) const
315{
316 return new Ts_TypedKnotData<T>(knots[index]);
317}
318
319template <typename T>
320Ts_KnotData*
321Ts_TypedSplineData<T>::CloneKnotAtTime(
322 const TsTime time) const
323{
324 const auto it = std::lower_bound(times.begin(), times.end(), time);
325 if (it == times.end() || *it != time)
326 {
327 return nullptr;
328 }
329
330 const auto knotIt = knots.begin() + (it - times.begin());
331 return new Ts_TypedKnotData<T>(*knotIt);
332}
333
334template <typename T>
335Ts_KnotData*
336Ts_TypedSplineData<T>::GetKnotPtrAtIndex(
337 const size_t index)
338{
339 return &(knots[index]);
340}
341
342// Depending on T, this is either a verbatim copy or an increase in precision.
343template <typename T>
344Ts_TypedKnotData<double>
345Ts_TypedSplineData<T>::GetKnotDataAsDouble(
346 const size_t index) const
347{
348 const Ts_TypedKnotData<T> &in = knots[index];
349 Ts_TypedKnotData<double> out;
350
351 // Use operator= to copy base-class members. This is admittedly weird, but
352 // it will continue working if members are added to the base class.
353 static_cast<Ts_KnotData&>(out) = static_cast<const Ts_KnotData&>(in);
354
355 // Copy derived members individually.
356 out.value = in.value;
357 out.preValue = in.preValue;
358 out.preTanSlope = in.preTanSlope;
359 out.postTanSlope = in.postTanSlope;
360
361 return out;
362}
363
364template <typename T>
365void Ts_TypedSplineData<T>::ClearKnots()
366{
367 times.clear();
368 customData.clear();
369 knots.clear();
370}
371
372template <typename T>
373void Ts_TypedSplineData<T>::RemoveKnotAtTime(
374 const TsTime time)
375{
376 const auto it = std::lower_bound(times.begin(), times.end(), time);
377 if (it == times.end() || *it != time)
378 {
379 TF_CODING_ERROR("Cannot remove nonexistent knot from SplineData");
380 return;
381 }
382
383 const size_t idx = it - times.begin();
384 times.erase(it);
385 customData.erase(time);
386 knots.erase(knots.begin() + idx);
387}
388
389template <typename T>
390static void _ApplyOffsetAndScaleToKnot(
391 Ts_TypedKnotData<T>* const knotData,
392 const TsTime offset,
393 const double scale)
394{
395 const bool reversing = (scale < 0);
396 const double absScale = std::abs(scale);
397
398 // Process knot time (absolute).
399 knotData->time = knotData->time * scale + offset;
400
401 // Process tangent widths (relative, strictly positive).
402 knotData->preTanWidth *= absScale;
403 knotData->postTanWidth *= absScale;
404
405 // Process slopes (inverse relative).
406 knotData->preTanSlope /= scale;
407 knotData->postTanSlope /= scale;
408
409 // Swap pre- and post-data if time-reversing.
410 if (reversing)
411 {
412 std::swap(knotData->preTanWidth, knotData->postTanWidth);
413 std::swap(knotData->preValue, knotData->value);
414 std::swap(knotData->preTanSlope, knotData->postTanSlope);
415 }
416}
417
418template <typename T>
419void Ts_TypedSplineData<T>::ApplyOffsetAndScale(
420 const TsTime offset,
421 const double scale)
422{
423 // XXX: scale can be negative. We believe this is uncommon. It is supposed
424 // to mean that the spline is not only scaled, but also time-reversed. We
425 // make an attempt, but there will be inconsistencies, because splines have
426 // several evaluation behaviors that are asymmetrical in time. For now,
427 // what we guarantee is invertibility: if a spline is time-reversed twice,
428 // the original shape will be recovered exactly.
429 //
430 // The right fix would probably be to have an isReversed flag in SplineData,
431 // which would cause the evaluation logic to invert all the asymmetrical
432 // behaviors. Those behaviors are:
433 //
434 // - Segment interpolation mode assignment. Each knot controls the mode of
435 // the following segment. Without an isReversed flag, we can preserve the
436 // modes of all segments, but in some cases we will lose the tentative
437 // interpolation mode that was set on the last knot.
438 //
439 // - Inner looping. The knot at the start of the prototype interval is
440 // special. There must be a knot there. It is copied to the end of the
441 // prototype interval and to the end of the post-looping interval. If
442 // there is a knot at the end of the prototype interval, it is ignored and
443 // overwritten. Without an isReversed flag, all we can do is exchange the
444 // prototype start and end times. If there is not a knot authored at the
445 // end time, this will cause the reversed spline not to have inner loops
446 // at all. If there is a knot at the end time, the reversed spline may
447 // have a different shape, because it is the (originally) end knot that
448 // will be copied, not the start knot.
449 //
450 // - Held segments. Evaluating in a held segment always produces the value
451 // from the preceding knot. Without an isReversed flag, the value will be
452 // taken from the (originally) following knot instead.
453 //
454 // - Dual-valued knots. Evaluating exactly at a dual-valued knot produces
455 // the ordinary value, not the pre-value. Without an isReversed flag, the
456 // value will be taken from the (originally) pre-value instead.
457 //
458 const bool reversing = (scale < 0);
459 if (reversing)
460 {
461 TF_WARN("Applying negative scale to spline");
462 }
463
464 // The spline is changed in the time dimension only.
465 // Different parameters are affected in different ways:
466 // - Absolute times (e.g. knot times): apply scale and offset.
467 // - Relative times (e.g. tan widths): apply scale only.
468 // - Inverse relative (slopes): slope = height/width, so we apply 1/scale.
469
470 // Scale extrapolation slopes if applicable (inverse relative).
471 if (preExtrapolation.mode == TsExtrapSloped)
472 {
473 preExtrapolation.slope /= scale;
474 }
475 if (postExtrapolation.mode == TsExtrapSloped)
476 {
477 postExtrapolation.slope /= scale;
478 }
479
480 // Swap extrapolations if time-reversing.
481 if (reversing)
482 {
483 std::swap(preExtrapolation, postExtrapolation);
484 }
485
486 // Process inner-loop params.
487 if (loopParams.protoEnd > loopParams.protoStart)
488 {
489 // Process start and end times (absolute).
490 loopParams.protoStart = loopParams.protoStart * scale + offset;
491 loopParams.protoEnd = loopParams.protoEnd * scale + offset;
492
493 // Swap start and end times if reversing.
494 if (reversing)
495 {
496 std::swap(loopParams.protoStart, loopParams.protoEnd);
497 std::swap(loopParams.numPreLoops, loopParams.numPostLoops);
498 }
499 }
500
501 // Process knot-times vector (absolute).
502 for (TsTime &time : times)
503 time = time * scale + offset;
504
505 // Reorder knot times if reversing.
506 if (reversing)
507 {
508 std::reverse(times.begin(), times.end());
509 }
510
511 // Process knots. Duplicate the logic that is applied unconditionally, so
512 // that we can rip through the entire vector just once, and we don't have to
513 // do the if-check on each iteration.
514 if (timeValued)
515 {
516 for (Ts_TypedKnotData<T> &knotData : knots)
517 {
518 _ApplyOffsetAndScaleToKnot(&knotData, offset, scale);
519
520 // Process time values (absolute).
521 knotData.value =
522 static_cast<T>(knotData.value * scale + offset);
523 knotData.preValue =
524 static_cast<T>(knotData.preValue * scale + offset);
525 }
526 }
527 else
528 {
529 for (Ts_TypedKnotData<T> &knotData : knots)
530 _ApplyOffsetAndScaleToKnot(&knotData, offset, scale);
531 }
532
533 if (reversing)
534 {
535 // Move interpolation modes from start knots to end knots.
536 for (size_t i = 1; i < knots.size(); i++)
537 knots[i - 1].nextInterp = knots[i].nextInterp;
538
539 // Reorder knots.
540 std::reverse(knots.begin(), knots.end());
541 }
542
543 // Re-index custom data. Times are adjusted absolutely.
544 if (!customData.empty())
545 {
546 std::unordered_map<TsTime, VtDictionary> newCustomData;
547 for (const auto &mapPair : customData)
548 newCustomData[mapPair.first * scale + offset] = mapPair.second;
549 customData.swap(newCustomData);
550 }
551}
552
553template <typename T>
554bool Ts_TypedSplineData<T>::HasValueBlocks() const
555{
556 if (knots.empty())
557 {
558 return false;
559 }
560
561 if (preExtrapolation.mode == TsExtrapValueBlock
562 || postExtrapolation.mode == TsExtrapValueBlock)
563 {
564 return true;
565 }
566
567 for (const Ts_TypedKnotData<T> &knotData : knots)
568 {
569 if (knotData.nextInterp == TsInterpValueBlock)
570 {
571 return true;
572 }
573 }
574
575 return false;
576}
577
578template <typename T>
579bool Ts_TypedSplineData<T>::HasValueBlockAtTime(
580 const TsTime time) const
581{
582 // If no knots, no blocks.
583 if (knots.empty())
584 {
585 return false;
586 }
587
588 // Find first knot at or after time.
589 const auto lbIt =
590 std::lower_bound(times.begin(), times.end(), time);
591
592 // If time is after all knots, return whether we have blocked
593 // post-extrapolation.
594 if (lbIt == times.end())
595 {
596 return postExtrapolation.mode == TsExtrapValueBlock;
597 }
598
599 // If there is a knot at this time, return whether its segment has blocked
600 // interpolation.
601 if (*lbIt == time)
602 {
603 const auto knotIt = knots.begin() + (lbIt - times.begin());
604 return knotIt->nextInterp == TsInterpValueBlock;
605 }
606
607 // If time is before all knots, return whether we have blocked
608 // pre-extrapolation.
609 if (lbIt == times.begin())
610 {
611 return preExtrapolation.mode == TsExtrapValueBlock;
612 }
613
614 // Between knots. Return whether the segment that we're in has blocked
615 // interpolation.
616 const auto knotIt = knots.begin() + (lbIt - times.begin());
617 return (knotIt - 1)->nextInterp == TsInterpValueBlock;
618}
619
620template <typename T>
621Ts_TypedSplineData<T>*
622Ts_GetTypedSplineData(TsSpline &spline)
623{
624 return static_cast<Ts_TypedSplineData<T>*>(
625 Ts_GetSplineData(spline));
626}
627
628template <typename T>
629const Ts_TypedSplineData<T>*
630Ts_GetTypedSplineData(const TsSpline &spline)
631{
632 return static_cast<Ts_TypedSplineData<T>*>(
633 Ts_GetSplineData(spline));
634}
635
636
637PXR_NAMESPACE_CLOSE_SCOPE
638
639#endif
Low-level utilities for informing users of various internal and external diagnostic conditions.
TfType represents a dynamic runtime type.
Definition: type.h:48
Extrapolation parameters for the ends of a spline beyond the knots.
Definition: types.h:121
Inner-loop parameters.
Definition: types.h:94
A mathematical description of a curved function from time to value.
Definition: spline.h:59
A map with string keys and VtValue values.
Definition: dictionary.h:43
VT_API bool empty() const
true if the VtDictionary's size is 0.
#define TF_CODING_ERROR(fmt, args)
Issue an internal programming error, but continue execution.
Definition: diagnostic.h:68
#define TF_WARN(...)
Issue a warning, but continue execution.
Definition: diagnostic.h:132