GB/GB_NUBBasis.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:
 *      Cristin Barghiel
 *      Side Effects Software Inc.
 *      20 Maud St.
 *      Toronto, Ontario,  M5V 2M5
 *      Canada
 *      416-366-4607
 *
 * NAME:        Geometry Library (C++)
 *
 * COMMENTS:
 *      This class implements a piecewise NUB spline basis.
 *
 * 
 */

#ifndef __GB_NUBBasis_h__
#define __GB_NUBBasis_h__

#include "GB_API.h"
#include <UT/UT_Vector4Array.h>
#include <UT/UT_Vector.h>
#include "GB_Basis.h"

#define GB_UNCLAMP_SCALE   3.0F    // knot scale factor for unclamp 
                                    // end interpolating curve/surface

enum GB_KnotSpaceType 
{
        GB_KNOT_UNIFORM         = 0,
        GB_KNOT_AVERAGING       = 1
};

class GB_API GB_NUBBasis : public GB_Basis {
public:
    // Class constructors. The basis is cubic by default and always built to
    // be valid in terms of its order. Therefore, the length will be increased
    // if necessary.
    
    GB_NUBBasis(unsigned len=8, unsigned ord=4);

    // This c-tor takes a given knot vector and its length, and it expects
    // you're making sure it is a valid sequence and in accordance with the
    // type of basis: if end interpolating, the number of equal knots at the
    // ends must == the order; if non-interpolating, the number of equal knots
    // at each end must be 2.
    GB_NUBBasis(float *kVec, unsigned len, unsigned ord, int e = 1);

    // This basis will end up with nk+2 knots if not end-interpolating, and
    // with nk + 2*order knots otherwise. A certain number of end knots will
    // be identical.
    GB_NUBBasis(fpreal kFirst, fpreal step, unsigned nk, unsigned ord,
                 int interpolateEnds = 1);

    // This c-tor allows you to build the equivalent of a Bezier basis. 
    // To end up with a Bezier-like basis, set the multiplicity=ord-1.
    // The end points will always have 'ord' multiplicity, so this is
    // an end-interpolating basis. The multiplicity must be >= 1 and < ord.
    GB_NUBBasis(unsigned bkpoints, unsigned multiplicity, unsigned ord);

    // Class destructor. Virtual by inheritance.
    virtual ~GB_NUBBasis();

    // Copy my data from the given source. If compatible is 1, we copy the
    // data only if b has the same order and length as we do, and if
    // it doesn't we return -1. If all goes well, return 0.
    virtual int          copyFrom(const GB_Basis &b, int compatible = 0);

    // Evaluate on a specific domain interval, on which at least one
    // basis function is non-zero given domain point u.
    virtual void         evalInterval(fpreal u, int offset, int derv, 
                                      float *vals) const;

    // Evaluate the all the derivs of the basis from 0 to derv (inclusive).
    void                 evaluateDerivMatrix(fpreal u, int offset, int derv,
                                             float bmatx[][GB_MAXORDER])const;

    // Compute one basis function (ie. the one with the given index) 
    // value at u.
    virtual fpreal       computeBValue(int index, fpreal u) const;

    // Find out if two knot sequences are similar (ie if the knot spacings
    // are the same all over) and their knot count is the same. We assume
    // "b" is a NUBBasis!
    virtual int          isSimilar(const GB_Basis &b) const;

     // Check if our basis has a similar knot spacing OUTSIDE the valid 
     // interval as the given basis. This is helpful in determining whether
     // merging two non end-interpolating bases requires an a priori conversion
     // to end-interpolating.
     int                 similarOrderEnds(const GB_NUBBasis &b) const;

    // Return the number of breakpoints (ie. unique knots) in the knot
    // vector, in the valid interval.
    virtual int          breakCount(void) const;

    // Find the index of the last knot in the sequence that defines 
    // breakpoint of index bptIdx, or the breakpoint of domain value
    // 'param'. Return -1 if not found. The search is done within the
    // limits of the valid interval.
    int                  breakpnt(int bptIdx) const;
    int                  breakpnt(fpreal param) const;

    // Given the index of a knot (kidx) and two bounds in the knot sequence
    // (a and b) find out the index of the breakpoint that the knot represents,
    // and possibly adjust kidx so that knot[kidx+1] > knot[kidx]. Return -1
    // if not found.
    virtual int          knotToBreakpoint(int &kidx, int a, int b) const;

    // Compute an array of breakpoints (i.e. unique knots) in the valid 
    // interval and return their number:
    virtual int          breakpoints(UT_FloatArray &arr, fpreal tol) const;
    virtual int          breakpoints(UT_FloatArray &arr) const;

    // Query the multiplicity of a knot. The second method assumes the knot
    // index is valid ie [1,len-2]. Return 0 if knot not found, and -1 if 
    // k is outside the valid interval or greater than the number of CVs
    // implied by the knot length and the "wrapped" parameter. The 1st method
    // also returns the index of knot t such that k >= t. 
    virtual int          multiplicity(fpreal k, int &tidx) const;
    int                  multiplicity(int wrapped, int &kidx) const;

    // Return the expected multiplicity of the end knots. It depends on the
    // basis order and the end conditions.
    virtual int          endMultiplicity(void) const;

    // Change the multiplicity of the knot by inserting it "r" times WITHOUT
    // checking its current multiplicity. kidx is the index of a knot t 
    // such that k >= t.
    void                 refine(fpreal k, int kidx, int r, int wrapped);

    // Return the first and last real knot values and indices:
    int                  firstRealIndex() const { return 1; }
    int                   lastRealIndex() const { return getLength()-2; }
    fpreal               firstRealKnot () const 
                         {
                             return getVector()((unsigned)firstRealIndex());
                         }
    fpreal                lastRealKnot () const 
                         {
                             return getVector()((unsigned)lastRealIndex()); 
                         }

    // Return the boundaries of the valid evaluation interval:
    virtual void         validInterval(int   &a,  int &b) const;

    // Return the index of the knot where the valid evaluation begins.
    // Typically, for a cubic spline, this index is 3 in the end-point
    // interpolating case and 1 otherwise. If float is completely outside
    // the valid knot sequence, this method returns -1.
    int                  findValidStart(fpreal u, int uOffset = -1) const;

    // findOffset is similar to findValidStart except it is virtual,
    // and with an input of startIdx to begin searching, 
    // but no uOffset input.
    virtual int          findOffset(fpreal k, int startIdx = 0) const;

    // Given a domain range in the valid interval, compute the range of CVs
    // that will be involved in the evaluation of the curve in that range.
    // Since the basis doesn't know about wrapping, the endcv index might
    // be higher than the spline's number of CVs.
    virtual void        cvRangeOfDomain(int  ustartidx, int  ustopidx,
                                        int &startcv,   int &endcv) const;
    virtual void        cvRangeOfDomain(fpreal ustart, fpreal ustop,
                                        int &startcv,   int &endcv) const;

    // Given valid breakpoint index, compute the range of CVs that have a 
    // non-zero influence at the knot of the breakpoint.  Since the basis
    // doesn't know about wrapping, the endcv index might be higher than the
    // spline's number of CVs.
    virtual void        cvRangeOfBreakpoint(int bkp, int &startcv, 
                                            int &cv) const;

    // Compute the idx'th greville abscissa of the knot vector. The function
    // does not do boundary checking. Clamping to the valid interval is
    // optional.
    virtual fpreal       greville(unsigned idx, int clamp = 1, 
                                    int wrapped = 1) const;

    // Grow the length of the basis by one, and set the value of the new
    // knot to something valid. If the basis is interpolating the second
    // endpoint, the last 'order' knots are made equal. A zero length basis
    // will have its length increased to 2 * order.
    // This method returns the index of the last element.
    virtual int          grow(int wrapped);

    // Shrink the basis by one. Return the new length.
    virtual int          shrink(int wrapped);

    // Insert a new knot as a result of a CV insertion at index cvIdx. The
    // knot index is cvIdx + 1, which is returned by growAt() if all goes OK.
    // -1 is returned upon failure.
    int                  growAt(unsigned cvIdx, int wrapped);

    // Delete a knot as a result of a CV removal at index cvIdx. The knot
    // index is cvIdx + 1. The method returns the new length if successful,
    // and -1 otherwise.
    int                  shrinkAt(unsigned cvIdx, int wrapped);

    // Attach another basis to us and grow our basis as a result. The bases
    // must have the same type and order. Return 0 if successful and -1 
    // otherwise. If "overlap" is true, we overlap the beginning of b with 
    // our end. Spreading makes sense when you can have multiple knots in the
    // basis, and causes identical knots to be spread within range of the
    // neighbouring knots.
    virtual int          attach(const GB_Basis &b, int overlap = 1,
                                int spread = 0);

    // Change the size of the basis (and maybe some of its values too) to 
    // make it a valid basis for wrapped splines. The second method applies
    // the reversed processs:
    virtual void         wrap(void);
    virtual void         unwrap(void);

    // Reverse the breakpoints in the basis.
    virtual void         reverse(int wrapped);

    // Rebuild the basis as a uniform sequence with a given step.
    virtual void         rebuild(fpreal ustart = 0.0f, fpreal ustep = 1.0f);

    // Make the knots uniform of just find out if they are uniform:
    virtual void           uniform(fpreal step = 1.0f);
    virtual int          isUniform(void) const;

    // Check if the basis interpolates the endpoints, or change the flag. 
    // Normally, publis users of these methods should use toggleEndCondition()
    // because it take care about spreading of collapsing the knots for you.
    // Only if you REALLY know what you are doing and just want to toggle the
    // flag, use interpolateEnds(1 or 0).
    short                interpolatesEnds(void) const { return endCondition;  }
    void                 interpolatesEnds(int yesno)  { endCondition = (short)yesno; }
    void                 toggleEndCondition(void);

    // Make the basis periodic (needed by wrapped splines):
    void                 periodic(void);

    // Reparameterize the basis using the chord-length method, and clamp it
    // to the valid interval. The origin and length of the valid domain remains
    // unchanged.
    virtual void         chord(UT_Vector4Array &cvs);

    // Slide the knots found in the given range left or right by an amount at
    // most as large as the distance to the nearest knot outside the range.
    // The bias is a percentage value of the left-right distance, its default
    // value is 0.5 (i.e. don't change anything), and is clamped to [0,1].
    // The method returns 0 if OK and -1 if out of range.
    virtual int          slideRange(fpreal umin, fpreal umax, fpreal ubias=0.5F);

    // Functions redefined from the base class.
    virtual const char          *getName(void) const;
    virtual unsigned int         getType(void) const;
    virtual int                  getDimension(void) const;

    // I/O functions.
    virtual int          save(ostream &os, int wrapped = 0,
                                           int binary  = 0) const;
    virtual bool         load(UT_IStream &is, int cvs,
                                           int wrapped = 0);

    // Validate the basis given CV information: return 1 if OK, 0 if NOK.
    // If adapt is 1, we adapt the basis flags to the knots. If adapt is 2
    // we adapt the knots to the basis flags, if any. If adapt is 0 we
    // return failure.
    virtual bool         validate(int adapt_to_knots = 0);
    virtual bool         validate(int cvLen, int doesWrap) const;
    virtual bool         validate(int cvLen, int basisLen, int doesWrap) const;

    // Maximum order accepted. This value is used to set the sizes of
    // work areas.
    static const int    maxOrder;

     // Find index in the knot vector such that knotVec[idx] <= k and
     // k < knotVec[idx+1]. The function returns a negative value if 
     // k is outside the validInterval(). If k > last valid knot we return the
     // the index of the last valid knot (ie. the dimension) + 1.
     int                 findStart(fpreal k, int startIdx = 0) const;

     // Set up the knot vector with the given parameterization for
     // interpolation.
     void                knotsEqualSpace(UT_Vector &param, int wrapped=0);
     void                knotsAveraging(UT_Vector &param, int wrapped=0);

     // Set up the knot vector with the given parameterization for
     // approximation. 
     void                knotsSpreading(UT_Vector &param);

     // Set up the knot vector with the given parameterization for building
     // a curve out of breakpoints.
     void                knotsBreakpoints(UT_Vector &param);

     // Cycle the knots, optionally keeping the original span length and origin
     int                 cycle(int amount, int keepSpan);

    // Create a new basis containing the partial merging of bases a and b
    // If their order is different return -1. Otherwise return 0.
    // The resultant basis contains knots a0..a1 of basis a merged with
    // knots b0..b1 from basis b (after being mapped onto a0..a1)
    // If the aknot or bknot array is given, they are set with the
    // (appropriately mapped) knots values corresponding to the new insertions

    virtual int          mergePartial(const GB_Basis &a, const GB_Basis &b,
                                      int a0, int a1, int b0, int b1,
                                      UT_FloatArray *aknot = 0,
                                      UT_FloatArray *bknot = 0);

    // will set the endCondition flag to 1 if and only if there are sufficient
    // knots at BOTH ends to make the curve touch the end CVs. Otherwise it will
    // set the endCondition flag to 0
    void                 updateEndCondition(void);

    // Return the discontinuity information for the basis at the given
    // parameter value u.  If discont_derv is returned as -1, the curve
    // is infinitely differentiable here (of course, derivatives >= order
    // will be zero).  Otherwise, discont_derv contains the lowest derivative
    // number that is discontinuous at this point.  It also returns the u
    // value at the other side of the discontinuity, if such a discontinuity
    // exists.
    virtual void        getDiscontinuityInfo(fpreal u, int &discont_derv,
                                             float &prev_span_u,
                                             int wrapped=0) const;

protected:
     // Compute the values or the derivatives at a domain point in the 
     // correct interval.
     void               computeBValues(fpreal u, const float* knots,
                                       int order, float* vals) const;
     void               computeBDerivs(fpreal u, const float* knots, int order,
                                       int derv, float* vals) const;

     // Initialize a knot sequence given an initial knot value and a step:
     void               initialize(fpreal kFirst, fpreal step);

     // Spread the knots within a given range. We assume the rance is valid.
     void               spreadKnots(int aidx, int bidx);

private:
    short               endCondition;   // 1 if it interpolates the ends.

};

#endif

---