GB/GB_Basis.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 abstract class handles splines bases.
 *
 * 
 */

#ifndef __GB_Basis_h__
#define __GB_Basis_h__

#include "GB_API.h"
#include <stdio.h>
#include <iostream.h>
#include <UT/UT_Vector4.h>
#include <UT/UT_FloatArray.h>
#include <UT/UT_IntArray.h>
#include <UT/UT_Vector4Array.h>
#include <UT/UT_Math.h>
#include "GB_Defines.h"

class UT_IStream;

#define GB_BASIS_BEZSPLINE      0x00001
#define GB_BASIS_NUBSPLINE      0x00002

#define GB_BASIS_N              "Basis"
#define GB_BASIS_BEZSPLINE_N    "Bezier"
#define GB_BASIS_NUBSPLINE_N    "NURB"

// GB_SPAN_DISTANCE is the distance that we back up from a given knot value
// to ensure that the evaluation is done in the previous span.
const fpreal             GB_SPAN_DISTANCE = 2.0f * UT_FTOLERANCE;


class GB_API GB_Basis {
public:
    // Class constructors. The basis is cubic by default. Last two ctors
    // allocate space for  the knot vector and do NOT verify the validity of
    // the data. It's up to the derived classes to make sure a given vector
    // length is appropriate for the specified order.
    GB_Basis(unsigned len=4, unsigned ord=4) : order(ord), dataVec(len,len) {}
    GB_Basis(float *vec, unsigned len, unsigned ord = 4);
    GB_Basis(fpreal vFirst, fpreal step, unsigned nv, unsigned ord = 4);

    // Class destructor.
    virtual ~GB_Basis();

    // 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 = 0;

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

    // 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.
    virtual int          isSimilar(const GB_Basis &b) const = 0;

    // Return the length of the domain vector or its contents. Careful, the 
    // contents don't belong to you.
    int                  getLength(void) const 
                         {
                             return (int)dataVec.entries(); 
                         }
    const float         *getData(void) const { return dataVec.getRawArray(); }
          float         *getData(void)       { return dataVec.array(); }

    // Query the order and the dimension of the basis:
    int                  getOrder(void) const   { return (int)order; }
    virtual int          getDimension(void) const = 0;

    // Return the boundaries of the valid evaluation interval, both as 
    // indices and as data values:
    virtual void         validInterval(int &a, int &b) const = 0;

    // Return the size of the basis within the valid interval:
    fpreal               validIntervalSize(void) const;

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

    // 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 = 0;

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

    // Compute an array of multiplicities for each knot in the knot sequence.
    // Return the number of breakpoints (i.e. unique knots).
    int                  multiplicities(UT_IntArray &arr) const;

    // Return the multiplicity of a domain point or -1 if outside the domain.
    // "uidx" is the index of the largest breakpoint <= u.
    virtual int          multiplicity(fpreal u, int &uidx) const = 0;

    // Return the expected multiplicity of the end knots (1 by default):
    virtual int          endMultiplicity(void) 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 = 0;
    virtual void         cvRangeOfDomain(fpreal ustart, fpreal ustop,
                                         int &startcv,   int &endcv) const = 0;

    // 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 &stopcv) const = 0;

    // Each derived class has its own name and id:
    virtual const char  *getName(void) const = 0;
    virtual unsigned int getType(void) const = 0;

    // Generate a new basis of the species specified in the name or type
    // respectively.
    static GB_Basis     *newSpecies(const char  *name);
    static GB_Basis     *newSpecies(unsigned int type);

    // 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);

    // 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);

    // 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 = 0) = 0;
    virtual bool         validate(int cvLen, int doesWrap) const = 0;
    virtual bool         validate(int cvLen, int bLen, int doesWrap) const = 0;

    // Compute the idx'th greville abscissa of the domain vector. Clamping
    // to the valid interval is optional and might not make any difference 
    // for some spline types.
    virtual fpreal       greville(unsigned idx, int clamp = 1, 
                                  int wrapped = 0) const = 0;

    // Resize the basis vector. This call updates the number of entries, too.
    void                 resize(unsigned sz, int copydata = 0)
                         {
                             dataVec.resize(sz, (unsigned short)copydata);
                             dataVec.entries(sz);
                         }

    // Grow the length of the basis by one, and set the value of the new entry
    // to last knot + 1. The method returns the index of the appended element.
    virtual int          grow(int wrapped=0) = 0;

    // Shrink the basis by one. The basis should not shrink beyond a valid
    // length. Return the new length.
    virtual int          shrink(int wrapped=0) = 0;

    // 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) = 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) = 0;
    virtual void         unwrap(void) = 0;

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

    // Find index in the knot vector for the break point corresponding to k. 
    virtual int          findOffset(fpreal k, int startIdx=0) const = 0;

    // Convert a value from unit to real knot and vice-versa. Usually you'll
    // want to map only within the valid interval.
    fpreal               unitToReal(fpreal u_unit, int valid_interval=1) const;
    fpreal               realToUnit(fpreal u_real, int valid_interval=1) const;

    // Append or insert or remove an element:
    int                  append(void)           { return (int)dataVec.append();  }
    int                  insert(unsigned i)     { return (int)dataVec.insert(i); }
    int                  remove(unsigned i)     { return (int)dataVec.removeIndex(i); }

    // Merge the given basis into ours provided they both have the same order.
    // If their order is different return -1. Otherwise return 0.
    // A copy of "b"'s knots is mapped to our knot interval first, then merged
    // with us. The second method stres the mapping into "b" itself.
    int                  merge(const GB_Basis &b);
    int                  merge(GB_Basis &b);


    // 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);

    // Find the index of a breakpoint such that the distance between it and the
    // next breakpoint is the largest in the whole sequence. The search is
    // done between two specified indices.
    int                  findMaxSpan(int start, int stop) const;

    // Normalize the vector and optionally shift it to a new origin. Use the 
    // given scale if greater than 0, else normalize to unit length. If "knots"
    // is given, the resulting values are deposited in it.
    void                 normalize(UT_FloatArray &knots,
                                   fpreal scale=0.0F, float *neworig=0) const;
    void                 normalize(fpreal scale=0.0F, float *neworig=0)
                         {
                             normalize(dataVec, scale, neworig);
                         }

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

    // Make the basis uniform of just find out if it is uniform:
    virtual void           uniform(fpreal ustep = 1.0f);
    virtual int          isUniform(void) const;

    // Normalize the vector to the new length and optionally shift it to 
    // a new origin. If "knots" is given, the resulting values are put in it.
    // The first method maps us to the interval of basis "b". In other words,
    // our extremities will be changed to match those of basis "b".
    void                 map(const GB_Basis &b);
    void                 map(UT_FloatArray &knots,
                             fpreal newlen = 1.0F, float *neworig = 0) const;
    void                 map(fpreal newlen = 1.0F, float *neworig = 0)
                         {
                             map(dataVec, newlen, neworig);
                         }

    // Map domain value "u", which should be between our min and max knots,
    // to a domain value in basis "b". If you know the index of the knot
    // in our sequence such that k[uoffset] <= u, enter in as the last
    // parameter. The method returns -1 if it has failed (the two bases don't
    // have the same length or u is out of range). Otherwise it returns the
    // uoffset.
    int                  map(const GB_Basis &b, fpreal &u, int uoffset=0) const;

    // 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) = 0;

    // 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)=0;

    // Set the order of the basis. Careful when you use it because it must
    // be <= GB_MAXORDER and must be appropriate for the number of knots.
    void                 setOrder(unsigned ord) { order = ord; }

    // Get the greatest value knot that is smaller than the search value.
    // Return 0 if search value is out of range. The default search range
    // is from order-1 to dimension.
    int                  findClosest(fpreal val, int &idx, 
                                     int startidx, int endidx) const;

    // Return the index of the first knot that is approximately equal to 
    // val. The entire sequence is searched from startidx.
    // Return  -1 if not found.
    int                  findApproximate(fpreal val, int startidx, 
                                         fpreal tol=0.00001F) const;

    // Compute alphas needed for degree elevation. "increment" is the amount
    // by which we want the degree to grow.
    void                computeRaiseOrderAlphas(unsigned int increment,
                                         float bezalfs[][GB_MAXORDER]) const;

    // 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 = 0;

    // Retrieve the knot/breakpoint vector that contains the raw data and
    // the vector length:
    const UT_FloatArray &getVector(void) const  { return dataVec; }
          UT_FloatArray &getVector(void)        { return dataVec; }

protected:

private:
    // The order of the basis == degree + 1. Max is GB_MAXORDER.
    unsigned int        order;

    // Vector of knots or breakpoints.
    UT_FloatArray       dataVec;

};

#endif

---