GU/GU_RayIntersect.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:
 *      Mark Elendt
 *      Side Effects
 *      477 Richmond Street West
 *      Toronto, Ontario
 *      Canada   M5V 3E7
 *      416-504-9876
 *
 * NAME:        GU library (C++)
 *
 * COMMENTS:    Ray intersection for GU library (not necessarily as fast as
 *              RAY library)
 *
 */

#ifndef __GU_RayIntersect_h__
#define __GU_RayIntersect_h__

#include "GU_API.h"
#include <UT/UT_Defines.h>
#include <UT/UT_RefArray.h>
#include <UT/UT_PtrArray.h>
#include <UT/UT_Vector3.h>

class GB_Group;
class GB_PrimitiveGroup;
class GU_Detail;
class GEO_Point;
class guRayTree;
class GEO_Primitive;
class GU_RayPrimInfo;
class GU_IsectCurveSet;
class GU_PrimGroupClosure;
class TS_MetaExpression;


enum GU_RayFindType {
    GU_FIND_CLOSEST     = 0,
    GU_FIND_FURTHEST    = 1,
    GU_FIND_ALL         = 2
};

class GU_API GU_RayInfoHit {
public:
    int operator==(const GU_RayInfoHit &x) const
    {
        return (t==x.t && u == x.u && v == x.v && d2 == x.d2 && prim == x.prim);
    }
    float t, u, v, d2;  // Intersection point.  May add cache here.
    const GEO_Primitive *prim;
};

class GU_API GU_RayInfoCache {
public:
    GU_RayInfoCache( )
    {
        valid = 0;
        priminfo = 0;
        data = 0;
    }

    GU_RayPrimInfo      *priminfo;
    void                *data;
    int                 valid;
};

class GU_API GU_RayInfo {
public:
    GU_RayInfo(float max = 1E18f, float min=0.0f,
                GU_RayFindType type = GU_FIND_CLOSEST, float tol = 1e-1F)
    {
        myHitList = 0;
        myCurveSet = 0;
        myTtol = 1E-2f;         // Points closer than this in "t" will not
                                //      be double counted.
        myIgnoreTrims = true;   // Do we pay attention to trimmed out regions?
        myUseAlgebraic = false; // Use algebraic pruning where available?
        myIgnoreMeta = false;   // Include metaballs.
        myExpandPolygon = false;
        myTValid = false;
        myDomainTol = 1E-2f;
        mySteps = 100;
        myMaxHits = 0;
        myTimeChange = 0.0F;
        myUnitTimeOffset = 0.0F;
        init(max, min, type, tol);
    }
    ~GU_RayInfo();

    void                setFindType(GU_RayFindType type);
    void                init(float max = 1E18f, float min=0.0f,
                                GU_RayFindType type = GU_FIND_CLOSEST,
                                float tolerance = 1e-1F, int ignoretrims=1,
                                int usealgebraic = 0);

    int                 testHit(float t)
                        {
                            return (t >= myTmin && t <= myTmax);
                        }

    int                 insertHit(float nt, float nu=0, float nv=0,
                                    float nd2=0, const GEO_Primitive *nprim=0);

    void                addCurveSet(GU_IsectCurveSet &curveset);

    void                invalidateCache() { myCache.valid = 0; }
    int                 isCacheValid()    { return( myCache.valid ); }

    GU_RayFindType      getFindType() const     { return myFindType; }

    void                reset();

    const GEO_Primitive         *myPrim;
    UT_Vector3                   myNml;
    float                        myTmin;
    float                        myTmax;
    float                        myT;
    float                        myU, myV;      // Hit position on primitive
    float                        myD2;          // Squared error.
    float                        myTol;         // Max error to consider a hit.
    float                        myTtol;        // min dist on ray between
                                                // two points
    float                        myDomainTol;   // Tolerance in domain
    int                          mySteps;       // Marching size
    bool                         myIgnoreTrims; // Pay attention to trim loops?
    bool                         myUseAlgebraic;// Use algebraic pruning?
    bool                         myExpandPolygon; // If true, you can have 
                                        // hits outside of 0,1 on quads.  
                                        // Prevents leaks with non-planar.
    bool                         myIgnoreMeta;  // Ignore metaballs.
    bool                         myTValid;      // Is myT set to a legit hit?
    int                          myMaxHits;     // Number of hits to stop 
                                                // searching at, if 0, is 
                                                // infinite.
    GU_RayInfoCache              myCache;       // Last successful hit.
    UT_RefArray<GU_RayInfoHit>  *myHitList;
    GU_IsectCurveSet            *myCurveSet;    // Set of isect curves.

    float                        myTimeChange;   //Only for moving collision
    float                        myUnitTimeOffset;//Only for moving collision
private:
    GU_RayFindType               myFindType;    // Only way to set is thru init
};

// This is the version of hitinfo used for minimum finding.
// It is similar, but sufficiently different to have its own
// structure.  In particular, more u/v values are needed and
// caching is not.
// NB: All distances are actually distance squareds.
// As soon as a distance smaller than dmin is found, the minimum
// finder will terminate with that value.  This allows early
// exit with collison detection.
class GU_API GU_MinInfo {
public:
    GU_MinInfo(float max = 1E18F, float min=1e-14F, int naccurate = 1)
    {
        dmin = min;
        dmax = max;
        accurate = naccurate;
        u1 = v1 = u2 = v2 = 0.0f;
        prim = 0;
    }

    void                init(float max = 1E18F, float min=1e-14F)
                        {
                            dmin = min;
                            dmax = max;
                        }

    int                 addMin(float dist)
                        {
                            if (dist < dmax)
                            {
                                // Only closest makes sense with minimum
                                dmax = dist;
                                return 1;
                            }
                            else return 0;
                        }

    void                insertMin(float nd2, float nu1, float nv1, 
                                  float nu2, float nv2, 
                                  const GEO_Primitive *p)
                        {
                            d = nd2;    // Recall: Distance squared.
                            u1 = nu1;
                            v1 = nv1;
                            u2 = nu2;
                            v2 = nv2;
                            prim = p;
                        }

    void                swapOrder()
                        {
                            float tmp;

                            tmp = u1;
                            u1 = u2;
                            u2 = tmp;

                            tmp = v1;
                            v1 = v2;
                            v2 = tmp;
                        }

    int operator==( const GU_MinInfo &other ) const
    {
        return(    dmin == other.dmin
                && dmax == other.dmax
                && d == other.d
                && u1 == other.u1
                && v1 == other.v1
                && u2 == other.u2
                && v2 == other.v2
                && accurate == other.accurate
                && prim == other.prim );
    }

    float               dmin, dmax;     // Minimum & maximum squared distances.
    float               d;              // Current squared distance.
    float               u1, v1;         // Current minimum on source.
    float               u2, v2;         // Current minimum on dest.
    int                 accurate;       // Do we polish sol'n?
    const GEO_Primitive*prim;           // What we are close to.
};

class GU_API GU_ProximityHelper
{
public:
    GU_ProximityHelper()            {}
    virtual ~GU_ProximityHelper()   {}

    virtual float   getMaxRadius( int prim_num ) const = 0;
    virtual float   getRadius( int prim_num,
                               float u_real, float v_real ) const = 0;
};

class GU_API GU_RayIntersect {
public:
     GU_RayIntersect();

     // Flag 'picking' should be set to 1.  When set to 0, curves and
     //   surfaces will be polygonalized.  Polygonalized curves have
     //   a different parameterization than the original curve, so the
     //   u coordinates will no longer be valid if picking == 0.
     // Flag 'polylines' indicates to build polylines instead of polygons.
     //   Normally, any closed polygon is treated as a surface.  If polyline
     //   is set to 1, all polygons are treated as wires.
     // Flag 'harden' indicates to build hard geometry - ie: the cached values
     //   will not update with those of the GDP.  This is usually a good thing,
     //   except it requires more memory.
     //   This also means that NURBs and Bezier surfaces will be changed
     //   into meshes, which may result in a faster intersect.
     // Flag 'usevisibility' indicates that it will look for a 3d visibility
     //   group.  If one is found, primitives will only be used if they
     //   are in that group.
     GU_RayIntersect(const GU_Detail *gdp, const GB_PrimitiveGroup *group = 0, 
                     int picking = 0, int polyline = 0, int harden = 0,
                     int usevisibility = 0);

     // This version of the constructor takes a GU_PrimGroupClosure and a 
     // flag to say whether the closure is to be included or excluded from
     // the ray intersect (a closure_hidden value of true excludes it).
     GU_RayIntersect(const GU_Detail *gdp, const GU_PrimGroupClosure &closure,
                     bool closure_hidden, int picking = 0, int polyline = 0,
                     int harden = 0);

     // assume picking for a single primitive
     GU_RayIntersect(const GU_Detail *gdp, const GEO_Primitive *prim,
                     int polyline = 0);

     // This version of the constructor is used for a special case intersector
     // against moving geometry.  Currently it only supports triangles.
     // Unlike the standard rays that are cast against the geometry, when
     // using this version of the intersector, the ray has to have a "speed"
     // associated with it.
     GU_RayIntersect(const GU_Detail *gdp0, const GU_Detail *gdp1);

     // This version of the constructor is like the one that takes a group
     // except the group is from a different gdp that has the same topology
     // (ie. prim counts are the sames). Note that if usevisibility is true,
     // then the visibility from the gdp is used (NOT limit_gdp).
     GU_RayIntersect(const GU_Detail *gdp,
                     const GU_Detail *limit_gdp,
                     const GB_PrimitiveGroup *vis_group,
                     int picking = 0, int polyline = 0, int harden = 0,
                     int usevisibility = 0);

    ~GU_RayIntersect();

    // Returns whether the supplied detail can be used with the deforming
    // geometry code (i.e. it is all triangles).
    static bool validForDeformingGeometry(const GU_Detail *gdp0,
                                          const GU_Detail *gdp1);

    void        init(const GU_Detail *gdp, const GB_PrimitiveGroup *group = 0, 
                     int picking = 0, int polyline = 0);
    void        init(const GU_Detail *gdp, const GEO_Primitive *prim,
                     int polyline = 0);
    void        init(const GU_Detail *gdp,
                     const GU_Detail *limit_gdp,
                     const GB_PrimitiveGroup *limit_group, 
                     int picking = 0, int polyline = 0, int harden = 0,
                     int usevisibility = 0);

    int         init() const { return myTree != 0; }

    // Returns whether this instance is up-to-date for the specified
    // detail or whether it needs to be rebuilt.
    bool        validForDetail(const GU_Detail *gdp) const;

    // Send a ray into the gdp between tmin & tmax.  Returns 0 if miss,
    //  1 if hit.  If hit, the information for the hit is returned in
    //  the hitinfo.
    // Returns -1 if intersection was interrupted.
    int         sendRay(const UT_Vector3 &org, const UT_Vector3 &dir,
                        GU_RayInfo &hitinfo);
    // Find minimum distance between point and gdp between tmin and tmax.
    // Note t = square of distance between point & primitive, so tmin
    // and tmax should be squares of the distance as desired.
    int         minimumPoint(const UT_Vector3 &p, GU_MinInfo &mininfo,
                             const GEO_Primitive *prim = 0);
    // Find all primitives in the gdp that are within a given radius of the
    // given point. Returns a list with u,v values sorted by primitive id in
    // hit_list.
    // If helper is non-NULL, then instead of using radius, we use it to
    // determine our radius.
    int         proximityPoint( UT_RefArray<GU_MinInfo> &hit_list,
                                const UT_Vector3 &p,
                                bool normalize_weights,
                                const GU_ProximityHelper *helper,
                                float radius = 0.0f ) const;

    // Intersects with a rayprimitive, used internally primarily:
    // Note it operates in opposite direction of intersectCaches!
    int         intersectPrim(GU_RayPrimInfo &prim, GU_RayInfo &hitinfo);
    
    // Intersect two raycaches of primitives.  Returns number of hits
    // found.  Only defined for some primitive types (Curves and surfaces)
    int         intersectCaches(GU_RayIntersect &intersect,
                                GU_RayInfo &hitInfo);
    // Find minimum between two raycaches of primitives.  Returns 1 if
    // minimum found.  t value is square of distance between them, as
    // is d2.
    int         minimumCaches(const GU_RayIntersect &intersect,
                              GU_MinInfo &minInfo) const;

    int         isInside(const UT_Vector3 &pt, int ignoretrim = 1);
    int         isInside(const UT_Vector4 &pt, int ignoretrim = 1);
    int         determineState(const UT_Vector3 &pt, 
                               const GEO_Primitive *&prim,
                               int n, long seed = 1, int ignoretrim = 1);
    int         determineState(const UT_Vector4 &pt, 
                               const GEO_Primitive *&prim,
                               int n, long seed = 1, int ignoretrim = 1);

    int         isInsideWinding(const UT_Vector3 &pt, int ignoretrim = 1);
    int         isInsideWinding(const UT_Vector4 &pt, int ignoretrim = 1);
    int         determineStateWinding(const UT_Vector3 &pt, 
                               const GEO_Primitive *&prim,
                               int n, long seed = 1, int ignoretrim = 1);
    int         determineStateWinding(const UT_Vector4 &pt, 
                               const GEO_Primitive *&prim,
                               int n, long seed = 1, int ignoretrim = 1);

    UT_PtrArray<GU_RayPrimInfo *>       &getPrimList() const;

private:
    void        initDetailTracking(const GU_Detail *gdp);
    void        initMetaExpr(const GU_Detail *gdp, bool first_time);

    guRayTree   *myTree;
    int          mySerial;              // Current serial number
    TS_MetaExpression   *myMetaExpr;

    // Keep track of some details about the detail we were initialized
    // with so users can query whether we're still valid.
    int          myDetailUniqueId;
    int          myDetailCacheCount;
};

#endif

---