UT/UT_Spline.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * Produced by:
 *      Side Effects Software Inc
 *      123 Front Street West, Suite 1401
 *      Toronto, Ontario
 *      Canada   M5J 2M2
 *      416-504-9876
 *
 * NAME:        UT_Spline.h ( UT Library, C++)
 *
 * COMMENTS:    Simple spline class.
 * 
 * The linear and catmull-rom splines expect a parametric evaluation coordinate
 * between 0 and 1.
 */

#ifndef __UT_Spline__
#define __UT_Spline__

#include "UT_API.h"
#include "UT_Color.h"
#include <SYS/SYS_Types.h>

typedef enum {
    // These splines all work on uniform keys.
    UT_SPLINE_CONSTANT,                 // Constant between keys
    UT_SPLINE_LINEAR,                   // Linear interpolation between keys
    UT_SPLINE_CATMULL_ROM,              // Catmull-Rom Cardinal Spline
    UT_SPLINE_MONOTONECUBIC,            // Monotone Cubic Hermite Spline

    // This interpolation works a little differently.  It takes a set of scalar
    // values, and "fits" the parametric coordinate into the keys.  That is, it
    // performs the binary search to find where the parametric coordinate maps,
    // then, it performs a linear interpolation between the two nearest key
    // values to figure out what the coordinate should be.
    UT_SPLINE_LINEAR_SOLVE,
} UT_SPLINE_BASIS;

/// The Linear & Catmull-Rom splines expect a parametric coordinate for
/// evaluation between 0 and 1.  The Catmull-Rom spline requires additional
/// key values at the beginning and end of the spline to evaluate the slopes
/// of the Hermite spline properly.
///
/// The LinearSolve only works on scalar values.  It will compute the
/// parametric coordinate associated with the value passed in.  This can be
/// used to simulate non-uniform keys on the spline.
class UT_API UT_Spline {
public:
     UT_Spline();
    ~UT_Spline();

    /// Query the basis or knot length of the spline
    UT_SPLINE_BASIS     getGlobalBasis() const  { return myGlobalBasis; }
    int                 getVectorSize() const   { return myVectorSize; }
    int                 getKnotLength() const   { return myKnotLength; }
    fpreal64            getTension() const      { return myTension; }

    void                setGlobalBasis(UT_SPLINE_BASIS b)
                            { myGlobalBasis = b; }

    /// Construction of the spline object.  All values are initialized to 0.
    /// Warning, calling setSize() will clear all existing values.
    void                setSize(int nkeys, int vector_size);
    /// Cubic splines may have a "tension".  The tension defaults to 0.5 which
    /// results in Catmull-Rom splines.
    void                setTension(fpreal64 t);

    /// Once the spline has been constructed, the values need to be set.
    /// It is possible to change values between evaluations.
    // @{
    void                setValue(int key, const fpreal32 *value, int size);
    void                setValue(int key, const fpreal64 *value, int size);
    // @}

    /// Set the basis for the given key index.
    /// This will also set the global basis.
    void                setBasis(int key, UT_SPLINE_BASIS b);

    /// Evaluate the spline using the global basis.
    /// When interp_space is not UT_RGB, then values are treated as UT_RGBA
    /// and converted into the desired color space before being interpolated.
    /// The result is always returned as UT_RGBA.
    // @{
    bool                evaluate(fpreal t, fpreal32 *result, int size,
                                 UT_ColorType interp_space) const;
    bool                evaluate(fpreal t, fpreal64 *result, int size,
                                 UT_ColorType interp_space) const;
    // @}

    /// Evaluate the spline using multiple basis types depending on t.
    /// Also unlike evaluate(), evaluateMulti() doesn't require extra keys for
    /// Catmull-Rom on the ends. It always evaluates using a 0 slope at the
    /// ends.
    // @{
    bool                evaluateMulti(fpreal t, fpreal32 *result, int n,
                                      UT_ColorType interp_space) const;
    bool                evaluateMulti(fpreal t, fpreal64 *result, int n,
                                      UT_ColorType interp_space) const;
    // @}

    /// Return _monotone_ cubic Hermite slopes at the current knot given the
    /// previous and next knots.
    // @{
    /// Fritsch-Carlson (local) method.
    /// It gives relatively good looking C1 curves but might not give a C2
    /// solution even if it exists.
    /// 1. Fritsch, F.N., Carlson, R.E., Monotone piecewise cubic interpolant,
    ///    SIAM J. Numer. Anal., 17(1980), 238-246.
    static fpreal64     getMonotoneSlopeFC(fpreal64 v_cur,  fpreal64 t_cur,
                                           fpreal64 v_prev, fpreal64 t_prev,
                                           fpreal64 v_next, fpreal64 t_next);
    /// Paul Kupan's method.
    /// Similar to Fritsch-Carlson method except it gives more visually
    /// pleasing results when the intervals next to the knot are uneven. 
    /// 2. Kupan, P.A., Monotone Interpolant Built with Slopes Obtained by
    ///    Linear Combination, Studia Universitatis Babes-Bolyai Mathematica,
    ///    53(2008), 59-66.
    static fpreal64     getMonotoneSlopePA(fpreal64 v_cur,  fpreal64 t_cur,
                                           fpreal64 v_prev, fpreal64 t_prev,
                                           fpreal64 v_next, fpreal64 t_next);
    // @}

    /// Given the keys surrounding a channel segment, evaluate it as cubic
    /// hermite spline. This function assumes dt > 0.
    /// kt is [0,1] which maps over the dt time interval.
    template <typename T>
    static T evalCubic(T kt, T dt, T iv, T im, T ov, T om)
    {
        T x0 = iv;
        T x1 = im*dt;
        T x3 = 2*(iv - ov) + (im + om)*dt;
        T x2 = ov - iv - im*dt - x3;
        return x0 + kt*(x1 + kt*(x2 + kt*x3));
    }

private:
    UT_Spline(const UT_Spline &copy);               // not implemented yet
    UT_Spline &operator =(const UT_Spline &copy);   // not implemented yet

private:
    void                 grow(int size);
    int                  getInterp(fpreal t, int knots[], fpreal weights[]);

    int64                getSizeOfValues() const
                         { return myKnotLength*myVectorSize*sizeof(fpreal64); }
    int64                getSizeOfBases() const
                         { return myKnotLength*sizeof(UT_SPLINE_BASIS); }

    template <typename T>
    inline void          combineKeys(T *result, int vector_size,
                                     fpreal64 weights[], int indices[],
                                     int num_indices,
                                     UT_ColorType interp_space) const;

    template <typename T>
    inline void          evalMonotoneCubic(fpreal t, T *result,
                                           int n, UT_ColorType interp_space,
                                           bool do_multi) const;

    template <typename T>
    inline void         setValueInternal(int key, const T *value, int size);

    template <typename T>
    inline bool         evaluateInternal(fpreal t, T *result, int size,
                                 UT_ColorType interp_space) const;

    template <typename T>
    inline bool         evaluateMultiInternal(fpreal t, T *result, int n,
                                      UT_ColorType interp_space) const;

    fpreal64            *myValues;
    UT_SPLINE_BASIS     *myBases;
    fpreal64             myTension;
    int                  myVectorSize;
    int                  myKnotLength;
    UT_SPLINE_BASIS      myGlobalBasis;
};

#endif

---