GEO/GEO_Curve.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 handles curves of arbitrary degree.
 *      The Face class maintains the control vertices for the curve.
 *
 */

#ifndef __GEO_Curve_h__
#define __GEO_Curve_h__

#include "GEO_API.h"
#include <UT/UT_RefArray.h>

#include <GB/GB_Basis.h>
#include <GB/GB_Parameterization.h>
#include <UT/UT_IntArray.h>
#include "GEO_Face.h"
#include "GEO_PrimType.h"
#include "GEO_Greville.h"

class UT_Vector3;
class UT_Vector4;
class GB_AttributeData;
class GB_FloatOffsets;
class GEO_AttributeHandleList;
class GEO_WorkVertexBuffer;
class GEO_Delta;

class GEO_API GEO_Curve : public GEO_Face {
public:
    // Constructor that attaches this curve to detail "d". You can optionally
    // specify the number of vertices m.
    GEO_Curve(GEO_Detail *d, int m = 0);

    // Class destructor, virtual by inheritance. It assumes it is OK to
    // delete the basis, so make sure you always set the basis with an object
    // allocated from the heap.
    virtual ~GEO_Curve();

    // Overwrite this curve with the data from src. Virtual by inheritance.
    virtual void                 copyPrimitive(const GEO_Primitive *src,
                                               GEO_Point **ptredirect);
    virtual GEO_Primitive       *copy(int preserve_shared_pts = 0) const;

    virtual void        changePointRef(GB_Element *from, GB_Element *to);

    // Evaluate one point (when du=0), or the du-th derivative.
    // Return 0 if successful, and -1 otherwise.
    virtual bool        evaluate(float u, GEO_Vertex &result,
                                GEO_AttributeHandleList &hlist,
                                unsigned du=0, int uOffset=-1) const;
    virtual int         evaluate(float u, UT_Vector4 &pos,
                                 unsigned du=0, int uOffset=-1) const;
    virtual int         evaluateWAttrib(float u, UT_Vector4 &pos, 
                                     GB_AttributeData &adata,
                                     const GB_FloatOffsets &foffsets,
                                     unsigned du=0, int uOffset=-1) const;

    // Given a domain value (u), store all the basis derivatives (from 0 to du
    // inclusive) into bmatx. Return the min and max index of the CVs needed
    // for the linear combination. The indices may exceed the number of
    // vertices if the curve is wrapped, so remember to use % getVertexCount().
    virtual int         evaluateBasisDerivs(float u,float bmatx[][GB_MAXORDER],
                                            int &cvoffset, unsigned du = 0,
                                            int uoffset = -1) const = 0;

    // Evaluate the basis at the given point in the domain and also return
    // the index of the first CV to linearly combine the basis with. The CV
    // index may exceed the number of vertices if the curve is wrapped,
    // so remember to use modulus (%). This method handles both rational and
    // non-rational curves.
    virtual int         evaluateBasis(float u,float *ubvals, int &cvoffset,
                                      unsigned du=0, int uoffset=-1) const = 0;

    // Return the value of the i'th basis at parameter u. This method handles
    // both rational an non-rational curves.
    float               computeBValue(float u, int i) const;

    // Two flavours of a bulk curve evaluator that computes points or
    // derivatives inside a parametric segment determined by:
    // a) the u values specified in uArr . The length of the parameter array
    // is arrLen. b) uStart, uStop.
    // The functions return  0 if successful, and -1 otherwise.
    virtual int         evaluateSegm(float *uArr, unsigned uArrLen, 
                                     UT_Vector4 *pos, unsigned du=0) const;
    virtual bool        evaluateSegm(float uStart, float uStop,
                                     uint nu, GEO_Vertex **results,
                                     GEO_AttributeHandleList &hlist,
                                     uint du) const;
    virtual int         evaluateSegm(float uStart, float uStop, unsigned nu,
                                     UT_Vector4 *pos, unsigned du=0) const;
    virtual int         evaluateSegmWAttrib(float uStart, float uStop, 
                                     unsigned nu, UT_Vector4 *pos,
                                     GB_AttributeData *adata,
                                     const GB_FloatOffsets &foffsets,
                                     unsigned du=0) const;

    // Another pair of curve evaluators. These take a start and a stop index
    // in the valid knot domain and an lod representing number of points to
    // be interpolated between every two breakpoints. The methods ALWAYS
    // interpolate the encountered breakpoints (aka "edit points").They return
    // the number of points in the list or -1 if unsuccessful. Please save
    // yourself headaches and pass VALID start and end indices (see the
    // method validInterval() in GB_Basis).
    virtual int         evaluateBreakSegm(int uStartIdx, int uStopIdx,
                            int lod, GEO_Vertex **result,
                            GEO_AttributeHandleList &hlist,
                            unsigned du) const;
    virtual int         evaluateBreakSegm(int uStartIdx, int uStopIdx,
                            int lod, UT_Vector4 *pos, unsigned du=0) const;
    virtual int         evaluateBreakSegmWAttrib(int uStartIdx, int uStopIdx,
                            int lod, UT_Vector4 *pos,
                            GB_AttributeData *adata,
                            const GB_FloatOffsets &foffsets,
                            unsigned du=0) const;

    // This method takes a start and a stop index in the valid domain, a lod
    // representing number of points between every two breakpoints, an integer
    // index, and return the value of the DOMAIN of point index after the
    // domain has lod points inserted between breakpoints.
    virtual float       breakSegmIndexToDomain(int ustartidx, int ustopidx,
                            int lod, int index) const;

    // Evaluate the position or the derivative at domain point (u,v), where
    // u and v MUST be in [0,1]. "v" and "dv" will be ignored here. Return 0 if
    // OK and -1 otherwise.
    virtual bool         evaluatePoint( GEO_Vertex &result,
                                        GEO_AttributeHandleList &hlist,
                                        float u_unit, float=0,
                                        unsigned du=0, unsigned = 0) const;
    virtual int          evaluatePoint( UT_Vector4 &pos, float u_unit, float=0,
                                        unsigned du=0, unsigned = 0) const;
    virtual int          evaluatePointWAttrib(UT_Vector4 &pos,
                                        GB_AttributeData &adata,
                                        const GB_FloatOffsets &foffsets,
                                        float u_unit, float=0, unsigned du = 0,
                                        unsigned = 0) const;

    // Evaluate the unit normal at (u). Return 0 if successful, and -1 
    // otherwise.
    int                 evaluateNormal(float u, UT_Vector3 &nml) const;

    // Evaluate the curvature at (u). Return 0 if successful and -1 otherwise.
    int                 curvature(float u, UT_Vector3 &curv) const;

    // Evaluate the arc length of the curve within a range. If the
    // values are invalid, return -1. divs means divisions per span.
    // If use_frwd_diff is true, forward differencing is used to speed
    // up the computation of the arc length; if false, a more precise
    // but slower solution is computed.
    float               arcLength(float u0, float u1, bool use_frwd_diff = true,
                                  int divs = 10) const;

    // compute the un-normalized lengths corresponding to points on the curve
    // evaluated at the valid knots parameter values
    // (ones with which lie within curve paramer domain) and store them
    // in the 'lengths' array. Returns the curve "length" (same as last knot).
    // The meaning of "length" depends on ptype, and can mean chord length,
    // square chord length, approximate arc length.
    virtual float       getKnotLengths(GB_ParmType ptype, 
                                       UT_FloatArray &lengths) const=0;

    // Evaluate the curve over the valid parametric interval and place the
    // points in the pos array. Return 0 if successful, and -1 otherwise.
    virtual int         fillCurve(int nu, UT_Vector4 *pos) const=0;

    // Increase the order. Return 0 if successful, -1 otherwise (eg.
    // order cannot be increased because it's >= MAXORDER).
    virtual int          raiseOrder(int neworder, GEO_AttributeHandleList &)=0;
    virtual int          raiseOrder       (int neworder) = 0;
    virtual int          raiseOrderWAttrib(int neworder,
                                        const GB_FloatOffsets &foffsets) = 0;

    // Translate the CVs such that the given breakpoint change positions by
    // the given delta.  Return -1 if something goes wrong, 0 if translation
    // was successful.
    // NOTE: uindices cannot contain any duplicates.  If the curve is closed,
    //       the first and last breakpoint are considered the same.
    virtual int          translateBreakpoints(const UT_IntArray &uindices,
                                              const UT_Vector3 &delta,
                                              int fixbkpts = 1,
                                              GB_PointGroup *ptgroup = NULL,
                                              GEO_Delta *geodelta = 0)= 0;

    virtual int          transformBreakpoints(const UT_IntArray &uindices,
                                              const UT_Matrix4 &matx,
                                              int fixbkpts = 1,
                                              GB_PointGroup *ptgroup = NULL,
                                              GEO_Delta *geodelta = 0)= 0;

    // Append another face to us in one of two ways: blend the two endpoints
    // or connect them straight or rounded. The bias ranges from 0 to 1 and is
    // relevant only to blending. The tolerance for blending: if 0, the two
    // endpoints will merge into one point with a discontinuity; if less than
    // 1, we insert knots into the curves to minimize the affected areas; if 1,
    // no refinement is done. For the non-blend case, the tolerance will
    // generate a span whose shape goes from round to straight; 0 tolerance
    // means straight connection. If unrefine is on, we'll try to reduce the
    // complexity of the face if we're connecting rounded. We return 0 if OK
    // and -1 if error. Both curves must be open and have the same order.
    virtual int         attach(const GEO_Face &face, int blend = 1,
                               float bias = 0.5f, float tolerance = 1.0f,
                               int unrefine = 1, GB_PointGroup *ptgroup=0);

    // Given a CV index figure out the min/max indicies of the knots between
    // which the curve needs to be re-evaluated if the CV changes. If not
    // given a valid CV index, the method returns -1. Otherwise it returns 0.
    virtual int         domainRangeOfCV(int cvidx, int &mink,
                                        int &maxk) const = 0;

    // Given a CV index figure out the min/max breakpoints which are
    // affected if the CV changes.  If not given a valid CV index, the
    // method returns -1.  Otherwise it returns 0.  Also returns -1 if
    // no breakpoints are affected.
    // NOTE: use % breakCount since maxbkp may be >= breakCount
    virtual int         breakpointRangeOfCV(int cvidx, int &minbkp,
                                            int &maxbkp) const = 0;

    // Reparameterize the curve by changing its basis. This type of 
    // reparameterization is generally NOT shape preserving:
    virtual void        reparameterize(GB_ParmType ptype) = 0;

    // Recompute the image of Greville point[r] on the curve.  The
    // second function updates all the Grevilles in case you have made
    // massive CV updates. Both functions return -1 if unsuccessful.
    int                 setGreville(unsigned int r); 
    int                 setGrevilles(void); 

    // At startup (or after a refinement) compute the UV and CV images of 
    // each Greville point. resize is expensive: try to avoid it if possible.
    // The function returns -1 if unsuccessful.
    int                 buildGreville (unsigned r);
    int                 buildGrevilles(int resize = 1);

    // Delete all the Grevilles and indicate that the Greville array need 
    // not be updated anymore:
    void                clearGrevilles(void) { grevArray.resize(0); }

    // Fast greville retriever: does _not_ check for boundary overflow!
    const GEO_Greville& getGreville(unsigned int r) const
                        {
                            return grevArray(r); 
                        }

    // Find out whether the Grevillle info is being computed or not. 
    // (Sometimes we don't need it).
    unsigned            hasGreville(void) const { return !grevArray.isEmpty(); }

    // Set the coordinates of cv[r] and call recordChanges() to notify those
    // interested. The method returns 0 if OK and -1 if the indices are wrong.
    int                 setCV(unsigned r, const UT_Vector4 &v);

    // Take the weights into consideration or don't. If you do, the curve
    // becomes a rational, and possibly different algorithms apply. If 'onOff'
    // is true, this function first checks if any two weights are different
    // before setting the rational flag to TRUE; if they are all the same,
    // the curve is set to non-rational (=> faster evaluation). weights()
    // calls normalizeWeights() to bring the weights to standard form, and
    // invokes recordChanges() if necessary. Weights that are <= 0 are bumped
    // up to FLT_EPSILON.
    void                weights(unsigned short onOff);

    // Set the weight of cv[r] to w. If the indices are out of bounds, it
    // returns -1; otherwise it returns 0. Weights that are <= 0 are bumped
    // up to FLT_EPSILON. This method calls recordChange() if appropriate.
    int                 setWeight(unsigned int r, float w);

    // Get the weight of cv[r]. Return -1 if indices are wrong.
    float               getWeight(unsigned int r) const;

    // Find out whether the curve is currently computed as a rational:
    int                 isRational(void) const { return (int) theRational; }

    // Homogenize the curve and disable the "rational" flag. Use the method
    // cvRangeOfDomain() to figure out the cv range given a domain range.
    void                makeHomogeneous(GEO_AttributeHandleList &hlist,
                                        int startcv=0, int endcv=-1)
                        {
                            homogenize(hlist, startcv, endcv);
                            theRational = 0;
                        }
    void                makeHomogeneous(int startcv = 0, int endcv = -1)
                        {
                            homogenize(startcv, endcv);
                            theRational = 0;
                        }
    void                makeHomogeneousWAttrib(const GB_FloatOffsets &foffsets,
                                        int startcv = 0, int endcv = -1)
                        {
                            homogenizeWAttrib(foffsets, startcv, endcv);
                            theRational = 0;
                        }
    void                makeNonHomogeneous(GEO_AttributeHandleList &hlist,
                                        int startcv=0, int endcv=-1)
                        {
                            dehomogenize(hlist, startcv, endcv);
                            theRational = 1;
                        }
    void                makeNonHomogeneous(int startcv = 0, int endcv = -1)
                        {
                            dehomogenize(startcv, endcv);
                            theRational = 1;
                        }
    void                makeNonHomogeneousWAttrib(
                                        const GB_FloatOffsets &foffsets,
                                        int startcv = 0, int endcv = -1)
                        {
                            dehomogenizeWAttrib(foffsets, startcv, endcv);
                            theRational = 1;
                        }

    // Normalize the weights of the control mesh so that edge weights are 1,
    // and all weights are >= 0 (those that are <= 0 are bumped up to 
    // FLT_EPSILON).
    void                normalizeWeights();

    // Normalize the domain and optionally shift it to a new origin. Use the 
    // given length if greater than 0.
    void                normalizeDomain(float len = 0.0F, float *neworigin = 0)
                        {
                            uBasis->normalize(len, neworigin);
                        }

    // Go from a normalized domain ([0,1]) to the real domain or vice versa.
    // We look only at the valid interval.
    virtual float       unitToRealDomain(float u_unit) const;
    virtual float       realToUnitDomain(float u_real) const;

    // Calculate the real domains for n consecutive operations on the domain
    // given n normalized domains and the operation
    // Here the real domain ranges from 0 to vertexcount - 1 + isClosed().

    virtual void        unitToRealSequence(float *uunit, float *ureal, 
                                int ulen) const;
    
    // Map the normalized length (distance value [0,1]) parameter to the unit 
    // parameterization of the primitve. The tolerance specifies max
    // error of the returned value (cannot be 0.0f)

    virtual float        unitLengthToUnitDomain(float ulength, 
                                                float tolerance = 1e-05F) const;
    virtual float        unitToUnitLengthDomain(float  uparm) const;


    // Return the bounds of the valid evaluation interval in domain space:
    virtual void        validInterval(int &a, int &b) const;
    virtual void        validRange(float &ua, float &ub) const;

    // Compute the texture coordinates either uniformly of chord length. If
    // the offset if negative, the methods find it and create the attribute
    // if necessary. If ptattrib is 1 we deal with points, else with vertices.
    // Return the texture offset or -1 if problems.
    int                 uniformTexture (int txtoff = -1, int ptattrib = 1);
    int                 grevilleTexture(int txtoff = -1, int ptattrib = 1);
    int                 chordLenTexture(int txtoff = -1, int ptattrib = 1);

    // Reverses the vertices of a given face. It's virtual because some faces,
    // such as rational splines, need to be aware of it.
    virtual void        reverse();

    // Notify those interested of a change in cv[r]'s weight or coordinates
    // (in recordChange()), or a change of more CV's and possibly bases (in
    // recordChanges()). If 'basisChange' is true, the basis composition must
    // have been affected. If 'sizeChange' is true, the basis and mesh 
    // dimension have been altered. If they are both zero, it must have been a
    // simple CV displacement or weight adjustment.
    // Currently, recordChanges() only updates the Greville matrix if present.
    virtual int         recordChange(unsigned r);
    virtual int         recordChanges(unsigned short basisChange = 0,
                                      unsigned short sizeChange = 0);

    // Set or query the basis. The "set" function  overwrites the current
    // basis pointer, so use with care; it returns -1 if the basis is invalid.
    int                 setBasis(GB_Basis *ub)
                        {
                            if (ub && ub->validate((int)getVertexCount(),(int)isClosed()))
                            {
                                delete uBasis; uBasis = ub;
                                return 0;
                            }
                            else return -1;
                        }
    GB_Basis*           getBasis(void) const    { return uBasis; }
    void                setAnyBasis(GB_Basis *ub) // Use with care!
                        {
                            delete uBasis; uBasis = ub;
                        }

    // Query the order and the dimension of the basis.
    virtual unsigned    getOrder(void) const;
    unsigned            getDim(void) const  { return (unsigned)uBasis->getDimension(); }

    // Inherited from the base class: just checks the validity of the basis.
    virtual int         isDegenerate(void) const;

    // Dehomogenize data (with attributes):
    static void         dehomogenizeData(GEO_Vertex **vertices,
                                        GEO_AttributeHandleList &hlist,
                                        int count);
    static void         dehomogenizeData(UT_Vector4 *pos, int count);
    static void         dehomogenizeDataWAttrib(UT_Vector4 *pos,
                                         GB_AttributeData *adata,
                                         const GB_FloatOffsets &foffsets,
                                         int count);

    // Return the surrounding values of the real-space u,v parameters.
    // Returns 1 if succesful, 0 if out-of-range.
    virtual int         parametricBBox(float u, float v,
                                       float *u0, float *u1,
                                       float *v0, float *v1);

    // If ustart and ustop are two values in the valid interval,ustart < ustop,
    // return the part of curve defined by ustart and ustop in a new primitive.
    // Return 0 if a problem is encountered.
    virtual GEO_Curve           *extract(float ustart,float ustop) const = 0;
    virtual int         breakCount() const;


    // Contraint based manipulation.
    // If the parameterization and derivative constraints do not change and
    // the curve's basis and order don't change, then the system only needs to
    // be solved once.  The solution can then be applied multiple times,
    // with different changes at the given parameters.

    // Return 0 if the resulting system is overdetermined or the dimensions
    //          are incorrect.
    //        1 if ok.
    int                  solveConstraints(const UT_Vector &param,
                                          const UT_IntArray &dervs,
                                          UT_Matrix &soln,
                                          UT_IntArray &cv_index);
    // Return 0 if the given data is invalid (incorrect dimensions or indices).
    //        1 if ok.
    // If the curve is rational, the changes matrix will be modified.
    int                  applyConstraints(UT_Matrix &changes,
                                          const UT_Vector &param,
                                          const UT_IntArray &dervs,
                                          const UT_IntArray &cv_index,
                                          const UT_Matrix &soln);

    // Return 0 if the resulting system is overdetermined.
    //        1 if ok.
    // Only call this method when the solution cannot be reused.
    // If the curve is rational, the changes matrix will be modified.
    int                  solveAndApplyConstraints(const UT_Vector &param,
                                                  const UT_IntArray &dervs,
                                                  UT_Matrix &changes);

protected:
    // The basis. Not const because we want to be able to (re)set it at
    // initialization time or elsewhere. It must be assigned an object
    // allocated from the heap so that we can delete it when calling this
    // class's destructor.
    GB_Basis           *uBasis;
      
    // Load and save functions redefined from the parent class.
    virtual int         savePrivate(ostream &os, int binary) const;
    virtual bool        loadPrivate(UT_IStream &is);
    virtual void        copyBasis(const GEO_Curve *src);

    // Copy from a primitive given a point offset for source points
    virtual void        copyOffsetPrimitive(const GEO_Primitive *src, int base);

    // Get a new basis of a type that matches our type:
    virtual GB_Basis    *newBasis(void) const = 0;

    // Check the validity of the data. Meant to be called especially at loading
    // time, since it also checks the weights. The method returns 1 if OK and 
    // 0 if trouble.
    virtual bool        validate(void) const;

    // Set the order of the basis:
    void                 setOrder(unsigned ord) { uBasis->setOrder(ord); }

    // Compute an evalution stepsize that is surely valid.
    float               stepSize(float start, float stop, int count) const
                        {
                            return (count > 0) ? ((stop - start)/(float)count)
                                               : 0.0F;
                        }

    // Turn the rational flag on or off. Use with discretion.
    void                rational(int yesno)     { theRational = (unsigned short) yesno; }


private:
    // The array of Greville abscissae. Its number of elements must match that
    // of the control vertex array (defined in the base class).  We will want 
    // to define a flag to tell us whether we should be interested in building 
    // and updating the Greville array or not.
    UT_RefArray<GEO_Greville>   grevArray;

    // Flag that indicates whether the CV weights should be taken into 
    // account when evaluating the curve or otherwise affecting its
    // geometry.
    unsigned short              theRational;

    // Evaluate one point of a RATIONAL curve (when du=0), or the du-th
    // derivative. Return 0 if successful, and -1 otherwise.
    bool                evaluateRational(float u,
                                GEO_Vertex &result,
                                GEO_AttributeHandleList &hl,
                                unsigned du=0, int uOffset=-1) const;
    int                 evaluateRational(float u, UT_Vector4 &pos,
                                 unsigned du=0, int uOffset=-1) const;
    int                 evaluateRationalWAttrib(float u, UT_Vector4 &pos, 
                                     GB_AttributeData &adata,
                                     const GB_FloatOffsets &foffsets,
                                     unsigned du=0, int uOffset=-1) const;

    // Given a derivative count (du), compute the numerator (aders) and
    // denominator (wders) of the expression that gives the curve value
    // for all derivatives from 0 to du. Return 0 if successful and -1
    // otherwise.
    int                  linearCombine(float bmatx[][GB_MAXORDER],
                                unsigned du, int cvoffset,
                                GEO_WorkVertexBuffer &vbuffer,
                                GEO_AttributeHandleList &hlist,
                                float *wders) const;
    int                  linearCombine(float bmatx[][GB_MAXORDER],
                                unsigned du, int cvoffset, UT_Vector4 *aders,
                                float *wders) const;
    int                  linearCombineWAttrib(float bmatx[][GB_MAXORDER],
                                unsigned du, int cvoffset, UT_Vector4 *aders,
                                float *wders, GB_AttributeData *attr_aders,
                                const GB_FloatOffsets &foffsets) const;

    friend ostream      &operator<<(ostream &os, const GEO_Curve &d)
                        {
                            d.save(os, 0);
                            return os;
                        }
};

#endif

---