eval.h File Reference

code to evaluate uniform b-splines More...

#include <array>
#include "basis.h"
#include "bspline.h"
#include "unary_functor.h"
#include "map.h"

Go to the source code of this file.

Classes
struct	std14::integer_sequence< T, Ints >
struct	std14::make_integer_sequence< T, N, Is >
struct	std14::make_integer_sequence< T, 0, Is... >
struct	vspline::bf_grok_type< _delta_et, _target_et, _vsize >
	If there are several differently-typed basis functors to be combined in a multi_bf_type object, we can erase their type, just like grok_type does for vspline::unary_functors. grokking a basis functor may cost a little bit of performance but it makes the code to handle multi_bf_types simple: instead of having to cope for several, potentially differently-typed per-axis functors there is only one type - which may be a bf_grok_type if the need arises to put differently-typed basis functors into the multi_bf_type. With this mechanism, the code to build evaluators can be kept simple (handling only one uniform type of basis functor used for all axes) and still use different basis functors. More...
struct	vspline::multi_bf_type< bf_type, ndim >
	When several basis functors have to be passed to an evaluator, it's okay to pass a container type like a std::array or std::vector. All of these basis functors have to be of the same type, but using the method given above ('grokking' basis functors) it's possible to 'slot in' differently-typed basis functors - the functionality required by the evaluation code is provided by the 'grokked' functors and their inner workings remain opaque. More...
struct	vspline::homogeneous_mbf_type< bf_type >
	homogeneous_mbf_type can be used for cases where all basis functors are the same. The evaluation code uses operator[] to pick the functor for each axis, so here we merely override operator[] to always yield a const reference to the same basis functor. More...
struct	vspline::multi_bf_type< vspline::basis_functor< math_type >, ndim >
	For b-spline processing, we use a multi_bf_type of b-spline basis functors (class vspline::basis_functor). We can't use the unspecialized template for this basis functor, because it takes the derivative specification, which is specified per-axis, so we need to 'pick it out' from the derivative specification and pass the per-axis value to the per-axis basis function c'tors. So here, instead of merely using the index_sequence to produce a sequence of basis function c'tor calls and ignoring the indices, we use the indices to pick out the per-axis derivative specs. More...
struct	vspline::detail::inner_evaluator< _ic_ele_type, _rc_ele_type, _ofs_ele_type, _cf_ele_type, _math_ele_type, _trg_ele_type, _dimension, _channels, _specialize, _mbf_type >
	'inner_evaluator' implements evaluation of a uniform b-spline, or some other spline-like construct relying on basis functions which can provide sets of weights for given deltas. While class evaluator (below, after namespace detail ends) provides objects derived from vspline::unary_functor which are meant to be used by user code, here we have a 'workhorse' object to which 'evaluator' delegates. This code 'rolls out' the per-axis weights the basis functor produces to the set of coefficients relevant to the current evaluation locus (the support window). We rely on a few constraints: More...
struct	vspline::bspline_evaluator_tag
	tag class used to identify all vspline::evaluator instantiations More...
class	vspline::evaluator< _coordinate_type, _trg_type, _vsize, _specialize, _math_ele_type, _cf_type, _mbf_type >
	class evaluator encodes evaluation of a spline-like object. This is a generalization of b-spline evaluation, which is the default if no other basis functions are specified. Technically, a vspline::evaluator is a vspline::unary_functor, which has the specific capability of evaluating a specific spline-like object. This makes it a candidate to be passed to the functions in transform.h, like remap() and transform(), and it also makes it suitable for vspline's functional constructs like chaining, mapping, etc. More...
struct	vspline::detail::build_ev< spline_type, rc_type, _vsize, math_ele_type, result_type >
	helper object to create a type-erased vspline::evaluator for a given bspline object. The evaluator is specialized to the spline's degree, so that degree-0 splines are evaluated with nearest neighbour interpolation, degree-1 splines with linear interpolation, and all other splines with general b-spline evaluation. The resulting vspline::evaluator is 'grokked' to erase it's type to make it easier to handle on the receiving side: build_ev will always return a vspline::grok_type, not one of the several possible evaluators which it produces initially. Why the type erasure? Because a function can only return one distinct type. With specialization for degree-0, degre-1 and arbitrary spline degrees, there are three distinct types of evaluator to take care of. If they are to be returned as a common type, type erasure is the only way. More...
struct	vspline::detail::build_safe_ev< level, spline_type, rc_type, _vsize, math_ele_type, result_type, gate_types >
	helper object to create a vspline::mapper object with gate types matching a bspline's boundary conditions and extents matching the spline's lower and upper limits. Please note that these limits depend on the boundary conditions and are not always simply 0 and N-1, as they are for, say, mirror boundary conditions. see lower_limit() and upper_limit() in vspline::bspline. More...
struct	vspline::detail::build_safe_ev< -1, spline_type, rc_type, _vsize, math_ele_type, result_type, gate_types ... >
	at level -1, there are no more axes to deal with, here the recursion ends and the actual mapper object is created. Specializing on the spline's degree (0, 1, or indeterminate), an evaluator is created and chained to the mapper object. The resulting functor is grokked to produce a uniform return type, which is returned to the caller. More...

Namespaces
namespace	std14
namespace	vspline
namespace	vspline::detail

Typedefs
template<std::size_t... Ints>
using	std14::index_sequence = integer_sequence< std::size_t, Ints... >
template<std::size_t N>
using	std14::make_index_sequence = make_integer_sequence< std::size_t, N >
template<typename... T>
using	std14::index_sequence_for = make_index_sequence< sizeof...(T)>
template<typename coordinate_type , typename value_type >
using	vspline::default_math_type = typename vigra::NumericTraits< typename vigra::PromoteTraits< typename vigra::ExpandElementResult< coordinate_type > ::type, typename vigra::ExpandElementResult< value_type > ::type > ::Promote > ::RealPromote
template<typename _coordinate_type , typename _trg_type , typename _mbf_type , size_t _vsize = vspline::vector_traits < _trg_type > :: size, typename _math_ele_type = default_math_type < _coordinate_type , _trg_type >, typename _cf_type = _trg_type>
using	vspline::abf_evaluator = evaluator< _coordinate_type, _trg_type, _vsize, -1, _math_ele_type, _cf_type, _mbf_type >
	alias template to make the declaration of non-bspline evaluators easier. Note that we fix the 'specialze' template parameter at -1 (no specialization) and pass the mbf type argument in third position. 'abf' stands for 'alternative basis function'. One example of such an alternative basis function is vspline::area_basis_functor - see basis.h. More...

Functions
template<typename _grokkee_t , typename _delta_et = float, typename _target_et = _delta_et, std::size_t _vsize = vspline::vector_traits < _delta_et > :: size>
bf_grok_type< _delta_et, _target_et, _vsize >	vspline::bf_grok (const _grokkee_t &grokkee)
template<class spline_type , typename rc_type = typename vigra::NumericTraits < typename spline_type::ele_type > :: RealPromote, size_t _vsize = vspline::vector_traits < typename spline_type::value_type > :: size, typename math_ele_type = default_math_type < typename spline_type::value_type , rc_type >, typename result_type = typename spline_type::value_type>
vspline::grok_type< bspl_coordinate_type< spline_type, rc_type >, result_type, _vsize >	vspline::make_evaluator (const spline_type &bspl, vigra::TinyVector< int, spline_type::dimension > dspec=vigra::TinyVector< int, spline_type::dimension >(0), int shift=0)
	make_evaluator is a factory function, producing a functor which provides access to an evaluator object. Evaluation using the resulting object is not intrinsically safe, it's the user's responsibility not to pass coordinates which are outside the spline's defined range. If you need safe access, see 'make_safe_evaluator' below. 'Not safe' in this context means that evaluation at out-of-bounds locations may result in a memory fault or produce wrong or undefined results. Note that vspline's bspline objects are set up as to allow evaluation at the lower and upper limit of the spline and will also tolerate values 'just outside' the bounds to guard against quantization errors. see vspline::bspline for details. More...
template<class spline_type , typename rc_type = typename vigra::NumericTraits < typename spline_type::ele_type > :: RealPromote, size_t _vsize = vspline::vector_traits < typename spline_type::value_type > :: size, typename math_ele_type = default_math_type < typename spline_type::value_type , rc_type >, typename result_type = typename spline_type::value_type>
vspline::grok_type< bspl_coordinate_type< spline_type, rc_type >, result_type, _vsize >	vspline::make_safe_evaluator (const spline_type &bspl, vigra::TinyVector< int, spline_type::dimension > dspec=vigra::TinyVector< int, spline_type::dimension >(0), int shift=0)
	make_safe_evaluator is a factory function, producing a functor which provides safe access to an evaluator object. This functor will map incoming coordinates into the spline's defined range, as given by the spline with it's lower_limit and upper_limit methods, honoring the bspline objects's boundary conditions. So if, for example, the spline is periodic, all incoming coordinates are valid and will be mapped to the first period. Note the use of lower_limit and upper_limit. These values also depend on the spline's boundary conditions, please see class vspline::bspline for details. If there is no way to meaningfully fold a coordinate into the defined range, the coordinate is clamped to the nearest limit. More...

Detailed Description

code to evaluate uniform b-splines

This body of code contains class evaluator and auxilliary classes which are needed for it's smooth operation.

The evaluation is a reasonably straightforward process: A subset of the coefficient array, containing coefficients 'near' the point of interest, is picked out, and a weighted summation over this subset produces the result of the evaluation. The complex bit is to have the right coefficients in the first place (this is what prefiltering does), and to use the appropriate weights on the coefficient window. For b-splines, there is an efficient method to calculate the weights by means of a matrix multiplication, which is easily extended to handle b-spline derivatives as well. Since this code lends itself to a generic implementation, and it can be parametrized by the spline's order, and since the method performs well, I use it here in preference to the code which P. Thevenaz uses (which is, for the orders of splines it encompasses, the matrix multiplication written out with a few optimizations, like omitting multiplications with zero, and slightly more concise calculation of powers). The weight generation code is in basis.h.

Evaluation of a b-spline seems to profit more from vectorization than prefiltering, especially for float data. On my system, I found single-precision operation was about three to four times as fast as unvectorized code (AVX2).

The central class of this file is class evaluator. evaluator objects are set up to provide evaluation of a specific b-spline. Once they are set up they don't change and effectively become pure functors. The evaluation methods typically take their arguments per reference. The details of the evaluation variants, together with explanations of specializations used for extra speed, can be found with the individual evaluation routines. 'Ordinary' call syntax via operator() is also provided for convenience.

What do I mean by the term 'pure' functor? It's a concept from functional programming. It means that calling the functor will not have any effect on the functor itself - it can't change once it has been constructed. This has several nice effects: it can potentially be optimized very well, it is thread-safe, and it will play well with functional programming concepts - and it's conceptually appealing.

Code using class evaluator will probably use it at some core place where it is part of some processing pipeline. An example would be an image processing program: one might have some outer loop generating arguments (typically simdized types) which are processed one after the other to yield a result. The processing will typically have several stages, like coordinate generation and transformations, then use class evaluator to pick an interpolated intermediate result, which is further processed by, say, colour or data type manipulations before finally being stored in some target container. The whole processing pipeline can be coded to become a single functor, with one of class evaluator's eval-type routines embedded somewhere in the middle, and all that's left is code to efficiently handle the source and destination to provide arguments to the pipeline - like the code in transform.h. And since this code is made to provide the data feeding and storing, the only coding needed is for the pipeline, which is where the 'interesting' stuff happens.

class evaluator is the 'front' class for evaluation, the implementation of the functionality is in class inner_evaluator. User code will typically not use class inner_evaluator, which lives in namespace vspline::detail.

The code in this file concludes by providing factory functions to obtain evaluators for vspline::bspline objects. These factory functions produce objects which are type-erased (see vspline::grok_type) wrappers around the evaluators, which hide what's inside and simply provide evaluation of the spline at given coordinates. These objects also provide operator(), so that they can be used like functions.

Passing vectorized coordinates results in vectorized results, where the specific types for the vectorized input and output is gleaned from vspline::vector_traits. If Vc is used and the fundamental data types can be made into a Vc::SimdArray, the data types for vectorized input/output will be Vc::SimdArrays (or vigra::TinyVectors of Vc::SimdArrays for multichannel data). Otherwise, vspline's SIMD emulation will be used, which replaces Vc::SimdArray with vspline::simd_type, which is an autovectorization-friendly type with similar performance. Since the objects produced by the factory functions are derived from vspline::unary_functor, they can be fed to the functions in transform.h, like any other vspline::unary_functor.

If you use vspline::transform and relatives, vectorization is done automatically: the transform routines will inquire for the functor's vectorized signature which is encoded as it's in_v and out_v types, which are - normally - results of querying vspline::vector_traits. The data are then deinterleaved into the vectorized input type, fed to the functor, and the vectorized result is interleaved into target memory. class evaluator has all the relevant attributes and capabilites, so using it with transform and relatives is easy and you need not be aware of any of the 'vector magic' going on internally - nor of the automatic multithreading. See transform.h for more on the topic.

Definition in file eval.h.