brace.h File Reference

This file provides code for 'bracing' a b-spline's coefficient array. More...

#include "common.h"

Go to the source code of this file.

Classes
struct	vspline::bracer< _dimension, _value_type >
	class bracer encodes the entire bracing process. Note that contrary to my initial implementation, class bracer is now used exclusively for populating the frame around a core area of data. It has no code to determine which size a brace/frame should have. This is now determined in class bspline, see especially class bspline's methods get_left_brace_size(), get_right_brace_size() and setup_metrics(). More...

Namespaces
namespace	vspline

Detailed Description

This file provides code for 'bracing' a b-spline's coefficient array.

Note that this isn't really user code, it's code used by class vspline::bspline.

Inspired by libeinspline, I wrote code to 'brace' the spline coefficients. The concept is this: while the IIR filter used to calculate the coefficients has infinite support (though arithmetic precision limits this in real-world applications), the evaluation of the spline at a specific location only looks at a small window of coefficients (compact, finite support). This fact can be exploited by taking note of how large the support area is and providing a few more coefficients in a frame around the 'core' coefficients to allow the evaluation to proceed without having to check for boundary conditions. While the difference is not excessive (the main computational cost is the actual evaluation itself), it's still nice to be able to code the evaluation without boundary checking, which makes the code very straightforward and legible.

There is another aspect to bracing: In my implementation of vectorized evaluation, the window into the coefficient array used to pick out coefficients to evaluate at a specific location is coded as a set of offsets from it's center. This way, several such windows can be processed in parallel. This mechanism can only function efficiently in a braced coefficient array, since it would otherwise have to give up if any of the windows accessed by the vector of coordinates had members outside the (unbraced) coefficient array and submit the coordinate vector to individual processing. I consider the logic to code this and the loss in performance too much of a bother to go down this path; all my evaluation code uses braced coefficient arrays. Of course the user is free to omit bracing, but then they have to use their own evaluation code.

What's in the brace? Of course this depends on the boundary conditions chosen. In vspline, I offer code for several boundary conditions, but most have something in common: the original, finite sequence is extrapolated into an infinite periodic signal. With straight PERIODIC boundary conditions, the initial sequence is immediately followed and preceded by copies of itself. The other boundary conditions mirror the signal in some way and then repeat the mirrored signal periodically. Using boundary conditions like these, both the extrapolated signal and the coefficients share the same periodicity and mirroring. There is one exception: 'natural' boundary conditions use point-mirroring on the bounds. With this extrapolation, the extrapolated value can not be obtained by a coordinate manipulation. The method of bracing the spline does still function, though. So with bracing, we can provide b-splines with 'natural' boundary conditions as well, but here we are limited to evaluation inside the spline's defined range.

There are two ways of arriving at a coeffcient array: We can start from the extrapolated signal, pick a section large enough to make margin effects vanish (due to limited arithmetic precision), prefilter it and pick out a subsection containing the 'core' coefficients and their support. Alternatively, we can work only on the core coefficients, calculate suitable initial causal and anticausal coeffcients (where the calculation considers the extrapolated signal, which remains implicit), and apply the filter with these known initial coefficients. vspline uses the latter approach. Once the 'core' coefficients are known, the brace is filled.

The bracing can be performed without any solver-related maths by simply copying (possibly trivially modified) slices of the core coefficients to the margin area.

Since the bracing mainly requires copying data or trivial maths we can do the operations on higher-dimensional objects, like slices of a volume. To efficiently code these operations we make use of vigra's multi-math facility and it's bindAt array method, which makes these subarrays easily available.

Definition in file brace.h.