Thea
Public Types | Public Member Functions | Protected Member Functions | Static Protected Member Functions | List of all members
SplineN< N, T > Class Template Referenceabstract

A spline curve segment in N-dimensional space. More...

#include <SplineN.hpp>

Inheritance diagram for SplineN< N, T >:
ParametricCurveN< N, T > ParametricCurveNBase< N, T > BezierN< N, T >

Public Types

typedef ParametricCurveN< N, T > ParametricCurveT
 Parametric curve segment in N dimensions. More...
 
typedef BaseT::VectorT VectorT
 N-dimensional vector type. More...
 

Public Member Functions

template<typename InputIterator , typename std::enable_if< Algorithms::IsPointN< typename std::iterator_traits< InputIterator >::value_type, N >::value, int >::type = 0>
double fitToPoints (InputIterator begin, InputIterator end, T const *initial_params=nullptr, T *final_params=nullptr, bool fix_first_and_last=false, intx max_reparam_iters=-1, intx num_reparam_steps_per_iter=-1)
 Fit the curve to a sequence of points [begin, end). More...
 
VectorT getBinormal (T const &t) const
 Get the unit binormal vector (third Frenet vector) to the curve at parameter value t. More...
 
virtual VectorT const & getControl (intx index) const =0
 Get a control vector of the curve. More...
 
VectorT getDeriv (T const &t, intx deriv_order=1) const
 Get the first, second, or higher derivative (specified by deriv_order = 1, 2, ...) of the curve at parameter value t, in the range [minParam(), maxParam()]. More...
 
virtual void getEvenlySpacedPoints (intx num_points, VectorT *pts_begin=nullptr, T *params_begin=nullptr, intx num_arc_samples=-1) const
 Get a sequence of points roughly evenly spaced by arc length along the curve, with associated parameter values. More...
 
VectorT getFrenetVector (T const &t, intx deriv_order) const
 Get the Frenet vector of the curve at parameter value t, for a given order. More...
 
VectorT getNormal (T const &t) const
 Get the unit normal vector (second Frenet vector) to the curve at parameter value t. More...
 
virtual intx getOrder () const
 Get the order of the curve, or a negative value if the curve has no well-defined order. More...
 
VectorT getPoint (T const &t) const
 Get the point on the curve with parameter value t, in the range [minParam(), maxParam()]. More...
 
VectorT getTangent (T const &t) const
 Get the unit tangent vector (first Frenet vector) to the curve at parameter value t. More...
 
virtual bool hasDeriv (intx deriv_order) const =0
 Check if the curve's getDeriv() function supports evaluating derivatives upto and including a given order (1 for first derivative, 2 for second, and so on). More...
 
T const & maxParam () const
 Get the maximum possible parameter value for the segment, which is the value at the end of the curve. More...
 
T const & minParam () const
 Get the minimum possible parameter value for the segment, which is the value at the beginning of the curve. More...
 
virtual intx numControls () const
 Get the number of control vectors of the curve, or a negative value if the curve is not defined by control vectors. More...
 
virtual void setControl (intx index, VectorT const &pos)=0
 Set a control vector of the curve. More...
 
 SplineN (T const &min_param_=0, T const &max_param_=1)
 Constructor, sets parameter limits. More...
 
std::string toString () const
 Get a textual representation of the curve. More...
 

Protected Member Functions

virtual VectorT eval (T const &t, intx deriv_order) const =0
 Evaluate the curve position, or one of its derivatives, at a given parameter value. More...
 
virtual bool firstAndLastControlsArePositions () const =0
 Check if the first and last control vectors of the curve can be interpreted as the positions of the beginning and end of the curve respectively. More...
 
virtual void getBasisFunctions (float64 t, VectorX< float64 > &b) const =0
 Get the numControls() basis functions for the curve, evaluated at curve parameter t. More...
 
bool isChanged () const
 Check if the curve was changed and hence cached data should be recomputed. More...
 
template<typename InputIterator >
float64 llsqFit (InputIterator begin, InputIterator end, Array< float64 > const &u, bool fix_first_and_last)
 Fit the curve to a sequence of points using linear least-squares. More...
 
template<typename InputIterator >
bool refineParameters (InputIterator begin, InputIterator end, Array< float64 > &u, intx num_newton_iters)
 Optimize each parameter value to bring the curve closer to the corresponding target point, using Newton-Raphson steps. More...
 
void setChanged (bool value=true) const
 Mark the curve as having changed or not changed. More...
 
virtual void update () const =0
 Updated cached data for the curve, marked as invalid after control vectors (for instance) have changed. More...
 

Static Protected Member Functions

template<typename InputIterator >
static void chordLengthParametrize (InputIterator begin, InputIterator end, Array< double > &u, double min_param_=0, double max_param_=1)
 Estimate curve parameters for a sequence of points, by accumulating pairwise segment lengths along the sequence. More...
 

Detailed Description

template<int N, typename T = Real>
class Thea::SplineN< N, T >

A spline curve segment in N-dimensional space.

The curve is assumed to be the weighted sum of a set of control vectors, where the weights are given by (typically polynomial or rational) differentiable basis functions of a scalar curve parameter. If the functions are polynomial, the maximum degree of these polynomials is the order of the curve.

This class contains code for fitting the curve to a sequence of points, extending the code from "An Algorithm for Automatically Fitting Digitized Curves", Philip J. Schneider, Graphics Gems, Academic Press, 1990.

Definition at line 47 of file SplineN.hpp.

Member Typedef Documentation

typedef ParametricCurveN<N, T> ParametricCurveT
inherited

Parametric curve segment in N dimensions.

Definition at line 42 of file ParametricCurveN.hpp.

typedef BaseT::VectorT VectorT

N-dimensional vector type.

Definition at line 55 of file SplineN.hpp.

Constructor & Destructor Documentation

SplineN ( T const &  min_param_ = 0,
T const &  max_param_ = 1 
)

Constructor, sets parameter limits.

Definition at line 58 of file SplineN.hpp.

Member Function Documentation

static void chordLengthParametrize ( InputIterator  begin,
InputIterator  end,
Array< double > &  u,
double  min_param_ = 0,
double  max_param_ = 1 
)
staticprotectedinherited

Estimate curve parameters for a sequence of points, by accumulating pairwise segment lengths along the sequence.

Definition at line 242 of file ParametricCurveN.hpp.

virtual VectorT eval ( T const &  t,
intx  deriv_order 
) const
protectedpure virtualinherited

Evaluate the curve position, or one of its derivatives, at a given parameter value.

Parameters
tThe curve parameter value, in the range [minParam(), maxParam()].
deriv_order0 to get the point position, 1 to get the first derivative, 2 for the second, and so on.
Returns
The desired position or derivative vector.
virtual bool firstAndLastControlsArePositions ( ) const
protectedpure virtual

Check if the first and last control vectors of the curve can be interpreted as the positions of the beginning and end of the curve respectively.

double fitToPoints ( InputIterator  begin,
InputIterator  end,
T const *  initial_params = nullptr,
T *  final_params = nullptr,
bool  fix_first_and_last = false,
intx  max_reparam_iters = -1,
intx  num_reparam_steps_per_iter = -1 
)

Fit the curve to a sequence of points [begin, end).

The algorithm alternates between least-squares fitting (with known parameters) and Newton-Raphson parameter optimization, following Graphics Gems.

Parameters
beginFirst point in the sequence to be fitted.
endOne past the last point in the sequence to be fitted.
initial_paramsThe curve parameters of the points, if known in advance. If this argument is not null, no reparametrization will be done by default, unless max_reparam_iters is explicitly set to a positive number.
fix_first_and_lastIf true, the first and last control vectors will be set to the positions of the first and last points, respectively, in the sequence. Note that curves whose first and last control vectors are not precisely the beginning and end positions of the curve will have this feature automatically disabled, with a warning.
max_reparam_itersIf greater than zero, the parameter values of the points will be re-estimated (at most) this many times, guided by initial values (initial_params) if any. Pass a negative value to pick a suitable default.
num_reparam_steps_per_iterThe number of successive Newton-Raphson steps in each iteration of reparametrization. Pass a negative value to pick a suitable default.
final_paramsIf non-null, used to return the final parameter values of the point sequence. Must be pre-allocated to have at least as many entries as the number of points.
Returns
The non-negative squared fitting error on success, or a negative value on error.

Definition at line 102 of file SplineN.hpp.

virtual void getBasisFunctions ( float64  t,
VectorX< float64 > &  b 
) const
protectedpure virtual

Get the numControls() basis functions for the curve, evaluated at curve parameter t.

A point on the curve is the sum of the control vectors, weighted by these basis functions as coefficients. (This need not be the most efficient way to evaluate points on the curve, and hence the implementation of eval() is left to the subclass.)

VectorT getBinormal ( T const &  t) const
inherited

Get the unit binormal vector (third Frenet vector) to the curve at parameter value t.

This requires the third derivative, and the return value is zero if hasDeriv(3) returns false (or N < 3, in which case the binormal is undefined).

Note
This function has an optimized implementation in 3 dimensions, where only the second derivative is required since the binormal can be computed as the cross-product of the unit tangent and normal vectors.
Warning
This function is currently strongly susceptible to numerical error, when the unnormalized tangent/normal/binormal has length nearly zero, but normalization rescales it to unit length. Use with caution.

Definition at line 317 of file ParametricCurveN.hpp.

virtual VectorT const& getControl ( intx  index) const
pure virtual

Get a control vector of the curve.

Parameters
indexThe index of the control vector, in the range 0 to numControls() - 1.

Implemented in BezierN< N, T >.

VectorT getDeriv ( T const &  t,
intx  deriv_order = 1 
) const
inherited

Get the first, second, or higher derivative (specified by deriv_order = 1, 2, ...) of the curve at parameter value t, in the range [minParam(), maxParam()].

Definition at line 83 of file ParametricCurveN.hpp.

virtual void getEvenlySpacedPoints ( intx  num_points,
VectorT pts_begin = nullptr,
T *  params_begin = nullptr,
intx  num_arc_samples = -1 
) const
virtualinherited

Get a sequence of points roughly evenly spaced by arc length along the curve, with associated parameter values.

The beginning and end of the curve (parameter values minParam() and maxParam() respectively) are always included.

Parameters
num_pointsThe number of evenly spaced points to be returned (must be at least 2).
pts_beginIf non-null, used to return the point sequence. Must have capacity at least num_points.
params_beginIf non-null, used to return the corresponding curve parameter sequence. Must have capacity at least num_points.
num_arc_samplesIf non-negative, specifies the number of samples for approximating arc lengths along the curve (must be at least 2). This value should normally be left at the default setting.

Definition at line 161 of file ParametricCurveN.hpp.

VectorT getFrenetVector ( T const &  t,
intx  deriv_order 
) const
inherited

Get the Frenet vector of the curve at parameter value t, for a given order.

The first Frenet vector is the unit tangent vector returned by getTangent(), the second is the unit normal vector returned by getNormal(), the third the unit binormal, and so on. The return value is zero if hasDeriv(deriv_order) returns false (or deriv_order > N, in which case the Frenet vector is undefined).

Warning
This function is currently strongly susceptible to numerical error, when the unnormalized Frenet vector of any order (upto deriv_order) has length nearly zero, but normalization rescales it to unit length. Use higher-order Frenet vectors with caution.

Definition at line 127 of file ParametricCurveN.hpp.

VectorT getNormal ( T const &  t) const
inherited

Get the unit normal vector (second Frenet vector) to the curve at parameter value t.

This requires the second derivative, and the return value is zero if hasDeriv(2) returns false (or N < 2, in which case the normal is undefined).

Definition at line 103 of file ParametricCurveN.hpp.

virtual intx getOrder ( ) const
virtualinherited

Get the order of the curve, or a negative value if the curve has no well-defined order.

Reimplemented in BezierN< N, T >.

Definition at line 61 of file ParametricCurveN.hpp.

VectorT getPoint ( T const &  t) const
inherited

Get the point on the curve with parameter value t, in the range [minParam(), maxParam()].

Definition at line 67 of file ParametricCurveN.hpp.

VectorT getTangent ( T const &  t) const
inherited

Get the unit tangent vector (first Frenet vector) to the curve at parameter value t.

This requires the first derivative, and the return value is zero if hasDeriv(1) returns false (or N < 1, in which case the tangent is undefined).

Definition at line 92 of file ParametricCurveN.hpp.

virtual bool hasDeriv ( intx  deriv_order) const
pure virtualinherited

Check if the curve's getDeriv() function supports evaluating derivatives upto and including a given order (1 for first derivative, 2 for second, and so on).

Note that if the function returns false for some deriv_order, then it must also return false for all higher orders.

Implemented in BezierN< N, T >.

bool isChanged ( ) const
protected

Check if the curve was changed and hence cached data should be recomputed.

Definition at line 367 of file SplineN.hpp.

float64 llsqFit ( InputIterator  begin,
InputIterator  end,
Array< float64 > const &  u,
bool  fix_first_and_last 
)
protected

Fit the curve to a sequence of points using linear least-squares.

Control vector positions are estimated by minimizing the sum of squared errors between the points and their corresponding curve points with known parameters u.

Parameters
beginThe beginning of the point sequence.
endOne past the end of the point sequence.
uThe curve parameter for each point.
fix_first_and_lastIf true, the first and last control vectors will be set to the positions of the first and last points, respectively, in the sequence. Note that curves whose first and last control vectors are not precisely the beginning and end positions of the curve will have this feature automatically disabled, with a warning.
Returns
The sum of squared fitting errors, or a negative value on error.

Definition at line 219 of file SplineN.hpp.

T const& maxParam ( ) const
inherited

Get the maximum possible parameter value for the segment, which is the value at the end of the curve.

Definition at line 58 of file ParametricCurveN.hpp.

T const& minParam ( ) const
inherited

Get the minimum possible parameter value for the segment, which is the value at the beginning of the curve.

Definition at line 55 of file ParametricCurveN.hpp.

virtual intx numControls ( ) const
virtualinherited

Get the number of control vectors of the curve, or a negative value if the curve is not defined by control vectors.

Reimplemented in BezierN< N, T >.

Definition at line 64 of file ParametricCurveN.hpp.

bool refineParameters ( InputIterator  begin,
InputIterator  end,
Array< float64 > &  u,
intx  num_newton_iters 
)
protected

Optimize each parameter value to bring the curve closer to the corresponding target point, using Newton-Raphson steps.

See "An Algorithm for Automatically Fitting Digitized Curves", Philip J. Schneider, Graphics Gems, 1990.

Definition at line 328 of file SplineN.hpp.

void setChanged ( bool  value = true) const
protected

Mark the curve as having changed or not changed.

Setting the value to true will cause update() to refresh cached data. Can be called even from the const update() function to unset the flag.

Definition at line 376 of file SplineN.hpp.

virtual void setControl ( intx  index,
VectorT const &  pos 
)
pure virtual

Set a control vector of the curve.

Parameters
indexThe index of the control vector to be set, in the range 0 to numControls() - 1.
posThe new position of the control vector.
Note
Subclasses that implement this function should remember to call setChanged(true), to trigger a call to update() to refresh cached data when required.
std::string toString ( ) const
virtual

Get a textual representation of the curve.

Reimplemented from ParametricCurveNBase< N, T >.

Definition at line 158 of file SplineN.hpp.

virtual void update ( ) const
protectedpure virtual

Updated cached data for the curve, marked as invalid after control vectors (for instance) have changed.

Note
Subclasses implementing this function should call isChanged() at the beginning to check if the curve has actually been changed, and setChanged(false) at the end to notify that the cached data is now up-to-date. In other words, the structure of the subclass function should be:
void update() const
{
if (!this->isChanged()) return;
...
// update cached data
...
this->setChanged(false);
}

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