Represent a smooth curve in a small amount of memory. More...

#include <compact_spline.h>

Detailed Description

Represent a smooth curve in a small amount of memory.

This spline interpolates a series of (x, y, derivative) nodes to create a smooth curve.

This class holds a series of such nodes, and aids with the construction of that series by inserting extra nodes when extra smoothness is required.

The data in this class is compacted as quantized values. It's not intended to be read directly. You should use the BulkSplineEvaluator to update and read values from the splines in a performant manner.

Classes
class	BulkOutput

Public Member Functions
	CompactSpline (const Range &y_range, const float x_granularity)

	CompactSpline (const CompactSpline &rhs)

CompactSpline &	operator= (const CompactSpline &rhs)

void	Init (const Range &y_range, const float x_granularity)

void	InitFromNodes (const UncompressedNode *nodes, size_t num_nodes)

void	InitFromSpline (const CompactSpline &spline)

void	AddNode (const float x, const float y, const float derivative, const CompactSplineAddMethod method=kEnsureCubicWellBehaved)

void	AddNodeVerbatim (const CompactSplineXGrain x, const CompactSplineYRung y, const CompactSplineAngle angle)

void	AddUncompressedNodes (const UncompressedNode *nodes, size_t num_nodes)

void	Finalize ()

void	Clear ()
	Remove all nodes from the spline.

size_t	Size () const
	Returns the memory occupied by this spline.

CompactSpline *	Next ()

const CompactSpline *	Next () const

CompactSpline *	NextAtIdx (int idx)

const CompactSpline *	NextAtIdx (int idx) const

CompactSplineIndex	IndexForX (const float x, const CompactSplineIndex guess_index) const

CompactSplineIndex	IndexForXAllowingRepeat (const float x, const CompactSplineIndex guess_index, const bool repeat, float *final_x) const

CompactSplineIndex	ClampIndex (const CompactSplineIndex index, float *x) const

float	StartX () const

float	StartY () const

float	StartDerivative () const

float	EndX () const

float	EndY () const

float	EndDerivative () const

float	NodeX (const CompactSplineIndex index) const

float	NodeY (const CompactSplineIndex index) const

float	NodeDerivative (const CompactSplineIndex index) const

float	LengthX () const

Range	RangeX () const

const Range &	RangeY () const

float	YCalculatedSlowly (const float x) const

float	CalculatedSlowly (const float x, const CurveValueType value_type) const

void	Ys (const float start_x, const float delta_x, const size_t num_points, float ys, float derivatives=nullptr) const

Range	RangeX (const CompactSplineIndex index) const
	The start and end x-values covered by the segment after `index`.

CubicInit	CreateCubicInit (const CompactSplineIndex index) const

CompactSplineIndex	LastNodeIndex () const
	Returns the index of the last node in the spline.

CompactSplineIndex	LastSegmentIndex () const
	Returns the start index of the last segment in the spline.

CompactSplineIndex	num_nodes () const
	Returns the number of nodes in this spline.

CompactSplineIndex	max_nodes () const

const detail::CompactSplineNode *	nodes () const
	Return const versions of internal values. For serialization.

const Range &	y_range () const

float	x_granularity () const

Static Public Member Functions
static CompactSpline *	Create (CompactSplineIndex max_nodes)

static CompactSpline *	CreateInPlace (CompactSplineIndex max_nodes, void *buffer)

static CompactSpline *	CreateFromNodes (const UncompressedNode *nodes, size_t num_nodes)

static CompactSpline *	CreateFromNodesInPlace (const UncompressedNode nodes, size_t num_nodes, void buffer)

static CompactSpline *	CreateFromSpline (const CompactSpline &source_spline, size_t num_nodes)

static CompactSpline *	CreateFromSplineInPlace (const CompactSpline &source_spline, size_t num_nodes, void *buffer)

static void	Destroy (CompactSpline *spline)

static CompactSpline *	CreateArray (CompactSplineIndex max_nodes, int num_splines)

static CompactSpline *	CreateArrayInPlace (CompactSplineIndex max_nodes, int num_splines, void *buffer)

static void	DestroyArray (CompactSpline *splines, int)
	Frees the memory allocated with CreateArray() using global `delete`.

static size_t	Size (CompactSplineIndex max_nodes)

static size_t	ArraySize (size_t num_splines, size_t num_nodes)

static float	RecommendXGranularity (const float max_x)

static void	BulkEvaluate (const CompactSpline const splines, const size_t num_splines, const float start_x, const float delta_x, const size_t num_points, BulkOutput out)

static void	BulkYs (const CompactSpline const splines, const size_t num_splines, const float start_x, const float delta_x, const size_t num_points, float ys, float *derivatives=nullptr)

template<int kDimensions>
static void	BulkYs (const CompactSpline const splines, const float start_x, const float delta_x, const size_t num_ys, mathfu::VectorPacked< float, kDimensions > ys)

Static Public Attributes
static const CompactSplineIndex	kDefaultMaxNodes = 7

Member Function Documentation

void motive::CompactSpline::AddNode	(	const float	x,
		const float	y,
		const float	derivative,
		const CompactSplineAddMethod	method = `kEnsureCubicWellBehaved`
	)

Add a node to the end of the spline. Depending on the method, an intermediate node may also be inserted.

Parameters

x	Must be greater than the x-value of the last spline node. If not, this call is a nop.
y	Must be within the `y_range` specified in Init().
derivative	No restrictions, but excessively large values may still result in overshoot, even with an intermediate node.
method	If kAddWithoutModification, adds the node and does nothing else. If kEnsureCubicWellBehaved, adds the node and (if required) inserts another node in the middle so that the individual cubics have uniform curvature. Uniform curvature means always curving upward or always curving downward. See docs/dual_cubics.pdf for details.

void motive::CompactSpline::AddNodeVerbatim	(	const CompactSplineXGrain	x,
		const CompactSplineYRung	y,
		const CompactSplineAngle	angle
	)

inline

Add values without converting them. Useful when initializing from precalculated data.

void motive::CompactSpline::AddUncompressedNodes	(	const UncompressedNode *	nodes,
		size_t	num_nodes
	)

Compress nodes and append them to the spline.

Parameters

nodes	An array of uncompressed nodes.
num_nodes	Length of the `nodes` array.

static size_t motive::CompactSpline::ArraySize	(	size_t	num_splines,
		size_t	num_nodes
	)

inlinestatic

Returns the size, in bytes, of an array of CompactSplines (as allocated with CreateArray(), say).

This function is useful when allocating a buffer for splines on your own, from which you can then call CreateArrayInPlace().

static void motive::CompactSpline::BulkEvaluate	(	const CompactSpline *const	splines,
		const size_t	num_splines,
		const float	start_x,
		const float	delta_x,
		const size_t	num_points,
		BulkOutput *	out
	)

static

Called by BulkYs with the an additional BulkOutputInterface parameter. BulkOutputInterface specifies the type of evaluations on the splines.

static void motive::CompactSpline::BulkYs	(	const CompactSpline *const	splines,
		const size_t	num_splines,
		const float	start_x,
		const float	delta_x,
		const size_t	num_points,
		float *	ys,
		float *	derivatives = `nullptr`
	)

static

Fast evaluation of several splines.

Parameters

splines	input splines of length `num_splines`.
num_splines	number of splines to evaluate.
start_x	starting point for every spline.
delta_x	increment for each output y.
num_points	the upper dimension of the `ys` and `derivatives` arrays.
ys	two dimensional output array, ys[num_points][num_splines]. ys[0] are `splines` evaluated at start_x. ys[num_points - 1] are `splines` evaluated at start_x + delta_x * num_points.
derivatives	two dimensional output array, with the same indexing as `ys`.

template<int kDimensions>

static void motive::CompactSpline::BulkYs	(	const CompactSpline *const	splines,
		const float	start_x,
		const float	delta_x,
		const size_t	num_ys,
		mathfu::VectorPacked< float, kDimensions > *	ys
	)

inlinestatic

Fast evaluation of several splines, with mathfu::VectorPacked interface. Useful for evaluate three splines which together form a mathfu::vec3, for instance.

float motive::CompactSpline::CalculatedSlowly	(	const float	x,
		const CurveValueType	value_type
	)		const

Evaluate spline at x. This function is somewhat slow because it must find the node for x and create the cubic before the returned value can be evaluated.

CompactSplineIndex motive::CompactSpline::ClampIndex	(	const CompactSplineIndex	index,
		float *	x
	)		const

Returns closest index between 0 and NumNodes() - 1. Clamps x to a value in the range of index. index must be a valid value: i.e. kBeforeSplineIndex, kAfterSplineIndex, or between 0..NumNodes()-1.

static CompactSpline* motive::CompactSpline::Create ( CompactSplineIndex max_nodes )

inlinestatic

Allocate memory for a spline using global new.

Parameters

max_nodes The maximum number of nodes that this spline class can hold. Memory is allocated so that these nodes are held contiguously in memory with the rest of the class.

static CompactSpline* motive::CompactSpline::CreateArray	(	CompactSplineIndex	max_nodes,
		int	num_splines
	)

inlinestatic

Allocate an array of splines, contiguous in memory, each of which can hold up to max_nodes. Use the global new operator to allocate the memory buffer.

This function is useful when passing several-dimensions-worth of splines to MotivatorNf::SetSplines(), for example Motivator3f::SetSplines() takes an array of three splines, like this function returns.

static CompactSpline* motive::CompactSpline::CreateArrayInPlace	(	CompactSplineIndex	max_nodes,
		int	num_splines,
		void *	buffer
	)

inlinestatic

Allocates num_splines CompactSplines contiguously in memory, and returns a pointer to the first spline. Each spline is the same size. Access the next Spline with Next().

Parameters

buffer chuck of memory of size CompactSpline::Size(max_nodes) * num_splines

The returned CompactSpline array does not need to be destroyed, but once the backing memory buffer disappears (e.g. if buffer is an array on the stack), you must stop referencing the returned CompactSpline array.

CubicInit motive::CompactSpline::CreateCubicInit ( const CompactSplineIndex index ) const

Initialization parameters for a cubic curve that starts at index and ends at index + 1. Or a constant curve if index is kBeforeSplineIndex or kAfterSplineIndex.

static CompactSpline* motive::CompactSpline::CreateFromNodes	(	const UncompressedNode *	nodes,
		size_t	num_nodes
	)

inlinestatic

Allocate memory using global new, and initialize it with nodes.

Parameters

nodes	An array holding the curve, in uncompressed floats.
num_nodes	The length of the `nodes` array, and max nodes in the returned spline.

static CompactSpline* motive::CompactSpline::CreateFromNodesInPlace	(	const UncompressedNode *	nodes,
		size_t	num_nodes,
		void *	buffer
	)

inlinestatic

Create a CompactSpline from nodes in the memory provided by buffer.

Parameters

nodes	array of node data, uncompressed as floats.
num_nodes	length of the `nodes` array.
buffer	chunk of memory of size CompactSpline::Size(num_nodes).

The returned CompactSpline does not need to be destroyed, but once the backing memory buffer disappears (e.g. if buffer is an array on the stack), you must stop referencing the returned CompactSpline.

static CompactSpline* motive::CompactSpline::CreateFromSpline	(	const CompactSpline &	source_spline,
		size_t	num_nodes
	)

inlinestatic

Allocate memory using global new, and initialize it by evaluating source_spline at a uniform x-interval.

Parameters

source_spline	Spline to evaluate. The curve in the returned spline matches `source_spline` with its x points spaced uniformly.
num_nodes	The number of uniform x-intervals in the returned spline. Also the max_nodes of the returned spline.

static CompactSpline* motive::CompactSpline::CreateFromSplineInPlace	(	const CompactSpline &	source_spline,
		size_t	num_nodes,
		void *	buffer
	)

inlinestatic

Create a CompactSpline from source_spline in the memory provided by buffer.

Parameters

source_spline	Spline to evaluate. The curve in the returned spline matches `source_spline` with its x points spaced uniformly.
num_nodes	The number of uniform x-intervals in the returned spline. Also the max_nodes of the returned spline.
buffer	chunk of memory of size CompactSpline::Size(num_nodes).

static CompactSpline* motive::CompactSpline::CreateInPlace	(	CompactSplineIndex	max_nodes,
		void *	buffer
	)

inlinestatic

Create a CompactSpline in the memory provided by buffer.

Parameters

buffer chunk of memory of size CompactSpline::Size(max_nodes)

Useful for creating small splines on the stack.

static void motive::CompactSpline::Destroy ( CompactSpline * spline )

inlinestatic

Deallocate the splines memory using global delete. Be sure to call this for every spline returned from Create(), CreateFromNodes(), CreateFromSpline().

void motive::CompactSpline::Finalize ( )

inline

Indicate that we have stopped adding nodes and want to release the remaining memory. Useful for when we have one giant buffer from which we want to add many splines of (potentially unknown) various sizes. We can do something like,

size_t CreateSplines(char* memory_buffer, size_t memory_buffer_size) {
  char* buf = memory_buffer;
  const char* end = memory_buffer + memory_buffer_size;
  while (MoreSplinesToCreate()) {
    // Allocate a spline that can hold as many nodes as buf can hold.
    CompactSpline* spline =
        CompactSpline::CreateInPlaceMaxNodes(buf, end - buf);
    while (MoreNodesToAdd()) {
      // Ensure we haven't reached the end of the buffer.
      if (spline->num_splines() == spline->max_splines()) break;
      // ... spline creation logic ...
      spline->AddNode(...);
    }
    // Shrink `spline` to be the size that it actually is.
    spline->Finalize();
    // Advance pointer so next spline starts where this one ends.
    buf += spline->Size();
  }
  // Return the total bytes consumed from `memory_buffer`.
  return end - buf;
}

CompactSplineIndex motive::CompactSpline::IndexForX	(	const float	x,
		const CompactSplineIndex	guess_index
	)		const

Return index of the first node before x. If x is before the first node, return kBeforeSplineIndex. If x is past the last node, return kAfterSplineIndex.

Parameters

x	x-value in the spline. Most often, the x-axis represents time.
guess_index	Best guess at what the index for `x` will be. Often the caller will be traversing from low to high x, so a good guess is the index after the current index. If you have no idea, set to 0.

CompactSplineIndex motive::CompactSpline::IndexForXAllowingRepeat	(	const float	x,
		const CompactSplineIndex	guess_index,
		const bool	repeat,
		float *	final_x
	)		const

If repeat is true, loop to x = 0 when x >= EndX(). If repeat is false, same as IndexForX().

void motive::CompactSpline::Init	(	const Range &	y_range,
		const float	x_granularity
	)

inline

The range of values for x and y must be specified at spline creation time and cannot be changed afterwards. Empties all nodes, if we have any.

Parameters

y_range The upper and lower bounds for y-values in the nodes. The more narrow this is, the better the precision of the fixed point numbers. Note that you should add 10% padding here, since AddNode may insert a smoothing node that is slightly beyond the source y range.

x_granularity The minimum increment of x-values. If you're working with a spline changes at most 30 times per second, and your x is in units of 1/1000th of a second, then x_granularity = 33 is a good baseline. You'll probably want granularity around 1/50th of that baseline value, though, since AddNode may insert smoothing nodes at intermediate x's. In our example here, you could set x_granularity near 33 / 50. For ease of debugging, an x_granularity of 0.5 or 1 is probably best.

void motive::CompactSpline::InitFromNodes	(	const UncompressedNode *	nodes,
		size_t	num_nodes
	)

Initialize the CompactSpline and add curve in the nodes array.

Parameters

nodes	An array of uncompressed nodes.
num_nodes	Length of the `nodes` array.

void motive::CompactSpline::InitFromSpline ( const CompactSpline & spline )

Evaluate spline at uniform x intervals, where the distance between consecutive x's is spline.LengthX() / (max_nodes() - 1). Initialize this spline with the results.

Parameters

spline The source spline to evaluate at uniform x intervals.

CompactSpline* motive::CompactSpline::Next ( )

inline

Use on an array of splines created by CreateArrayInPlace(). Returns the next spline in the array.

CompactSpline* motive::CompactSpline::NextAtIdx ( int idx )

inline

Use on an array of splines created by CreateArrayInPlace(). Returns the idx'th spline in the array.

static float motive::CompactSpline::RecommendXGranularity ( const float max_x )

static

Recommend a granularity given a maximal-x value. We want to have the most precise granularity when quantizing x's.

static size_t motive::CompactSpline::Size ( CompactSplineIndex max_nodes )

inlinestatic

Returns the size, in bytes, of a CompactSpline class with max_nodes nodes.

This function is useful when you want to provide your own memory buffer for splines, and then pass that buffer into CreateInPlace(). Your memory buffer must be at least Size().

float motive::CompactSpline::YCalculatedSlowly ( const float x ) const

inline

Calls CalculatedSlowly at x, with kCurveValue to evaluate the y value. If calling from inside a loop, replace the loop with one call to Ys(), which is significantly faster.

void motive::CompactSpline::Ys	(	const float	start_x,
		const float	delta_x,
		const size_t	num_points,
		float *	ys,
		float *	derivatives = `nullptr`
	)		const

Fast evaluation of a subset of the x-domain of the spline. Spline is evaluated from start_x and subsequent intervals of delta_x. Evaluated values are returned in ys and, if not nullptr, derivatives.

Member Data Documentation

const CompactSplineIndex motive::CompactSpline::kDefaultMaxNodes = 7

static

When a CompactSpline is created on the stack, it will have this many nodes. This amount is sufficient for the vast majority of cases where you are procedurally generating a spline. We used a fixed number instead of an std::vector to avoid dynamic memory allocation.

The documentation for this class was generated from the following file:

compact_spline.h

Detailed Description

Classes

Public Member Functions

Static Public Member Functions

Static Public Attributes

Member Function Documentation

Member Data Documentation