GEO/GEO_PointTree.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:
 *      Jeff Lait
 *      Side Effects Software Inc
 *      477 Richmond Street West
 *      Toronto, Ontario
 *      Canada   M5V 3E7
 *      416-504-9876
 *
 * NAME:        GEO_PointTree.h ( GEO Library, C++)
 *
 * COMMENTS:    This provides a method to index points inside of a
 *              geometry.
 */

#ifndef __GEO_PointTree__
#define __GEO_PointTree__

#include "GEO_API.h"
#include <UT/UT_KDTree.h>
#include <UT/UT_PointTree.h>
#include <UT/UT_IntArray.h>
#include <UT/UT_Vector3Array.h>
#include <UT/UT_PtrArray.h>

class GB_PointGroup;
class GEO_Detail;
class GEO_Point;

class GEO_API GEO_PointTree : protected UT_KDTree
{
public:
             GEO_PointTree();
    virtual ~GEO_PointTree();

    /// Rebuilds the PointTree with the given detail and values.
    /// It will make its own internal vector3 array of the points and
    /// original indices.
    void                 build(const GEO_Detail *gdp,
                               const GB_PointGroup *ptgroup);

    /// Rebuilds the PointTree given a list of GEO_Points.
    /// It will make its own internal vector3 array of the points and
    /// original indices.
    void                 build(const GEO_Detail *gdp,
                                const UT_PtrArray<GEO_Point *> &ptlist);

    /// Rebuilds the point tree as a pure index based tree using the
    /// given vectors.
    void                 build(const UT_Vector3Array &pts);

    /// Rebuilds the point tree as a pure index based tree using the
    /// given vector/index lookup.
    void                 build(const UT_Vector3Array &pts,
                                const UT_IntArray &idx);

    /// This will slowly build the tree in place.
    /// Balancing isn't done until the next lookup.
    /// Thus, it can provide a nicer way to initialize a tree.
    /// When auto_rebalance is true, the tree may choose not to rebalance on
    /// the next lookup, and will rebalance after a sufficient number of 
    /// points have been added.  This can be useful in cases where lookups and
    /// appends are interleaved.  When it is false, the tree will be rebalanced
    /// on the next query.
    void                 append(const GEO_Detail *gdp, const GEO_Point *pt,
                                bool auto_rebalance=false);
    void                 append(const UT_Vector3 &pt, int idx,
                                bool auto_rebalance=false);
    void                 append(const UT_Vector3 &pt,
                                bool auto_rebalance=false);

    /// This builds a tree which has a per point radius.
    /// Note that this does not work with the tube testing code.
    /// Note that there is a large performance penalty for the
    /// findNearest methods, but no real penalty for the findAllClose
    /// methods
    /// If any points are added in radius mode, ALL must be added in
    /// radius mode.
    void                 appendPtRadius(const GEO_Detail *gdp, 
                                        const GEO_Point *pt,
                                        fpreal radius);
    void                 appendPtRadius(const UT_Vector3 &pt, fpreal radius, 
                                        int idx);
    void                 appendPtRadius(const UT_Vector3 &pt, fpreal radius);

    /// This makes the tree hard.  This makes any attempt to do a GEO_Point
    /// look up illegal - one must instead fetch by index.
    void                 harden();

    /// This makes the tree soft.  The given GEO_Detail becomes the relevant
    /// GEO_Detail for all look ups involving GEO_Points.
    void                 soften(const GEO_Detail *gdp);

    /// Clears out the tree, leaving it with no entries and no bound gdp.
    void                 clear();

    /// Returns the number of actual points in the tree.
    int                  entries() const;

    /// Returns the amount of memory used by this tree.
    int64                getMemoryUsage() const;

    /// This sets the valid function method.  This call back will be
    /// called for each point to see if it should be included in the search.
    /// This only works for non-hard trees!
    void                 setValidCallback(UT_PointTreeValidNearestFunc,
                                        void *user_data);

    /// Finds the nearest point or index to the given value.  Returns
    /// 0 or -1 on no such point.
    /// NOTE: findNearestPt() will fail if it has not been built with a gdp
    GEO_Point           *findNearestPt(const UT_Vector3 &pt);
    int                  findNearestIdx(const UT_Vector3 &pt);

    /// Finds the nearest point or index to the given value.  Returns
    /// 0 or -1 on no such point.  The point must be within the given range.
    /// NOTE: findNearestPt() will fail if it has not been built with a gdp
    GEO_Point           *findNearestPt(const UT_Vector3 &pt, fpreal maxdist);
    int                  findNearestIdx(const UT_Vector3 &pt, fpreal maxdist);

    /// These use a pre-built queue to reduce memory allocation
    /// You must call UT_KDTree::destroyQueue() when you are done with
    /// the queue.
    ut_KDPQueue         *createFindNearestQueue(fpreal maxdist = 1e18f) const;
    GEO_Point           *findNearestPtQueue(const UT_Vector3 &pt, ut_KDPQueue &q);
    int                  findNearestIdxQueue(const UT_Vector3 &pt, ut_KDPQueue &q);

    /// Find the nearest [groupsize] points not more than maxdist
    /// away.
    /// Returns the number of points found.  Found points will be
    /// stored in the group array.
    /// The resulting points will be sorted by their distance.
    /// NOTE: findNearestGroupPt() will fail if it has not been built with a gdp
    int                  findNearestGroupPt(const UT_Vector3 &pt,
                                        fpreal maxdist,
                                        int groupsize,
                                        UT_PtrArray<GEO_Point *> &group,
                                        UT_FloatArray &groupdist);
    int                  findNearestGroupIdx(const UT_Vector3 &pt,
                                        fpreal maxdist,
                                        int groupsize,
                                        UT_IntArray &group,
                                        UT_FloatArray &groupdist);

    /// Finds all the points within the given radius of a point.
    /// The resulting points will *not* be sorted.
    /// NOTE: findAllClosePt() will fail if it has not been built with a gdp
    int                  findAllClosePt(const UT_Vector3 &pt, float maxdist,
                                        UT_PtrArray<GEO_Point *> &list);
    int                  findAllCloseIdx(const UT_Vector3 &pt, float maxdist,
                                        UT_IntArray &list);

    /// Creates a search queue useful for findAll queries.  You
    /// must destroy it with UT_KDTree::destroyQueue(q) when done.
    ut_KDPQueue         *createFindAllQueue(fpreal maxdist) const;
    int                  findAllCloseIdxQueue(const UT_Vector3 &pt, ut_KDPQueue &queue, UT_IntArray &list);
                                        

    /// Find all of the points inside the given tube.
    /// NOTE: findAllInTubePt() will fail if it has not been built with a gdp
    int                  findAllInTubePt(const UT_Vector3 &orig,
                                        const UT_Vector3 &dir,
                                        fpreal radius,
                                        UT_PtrArray<GEO_Point *> &list);
    int                  findAllInTubeIdx(const UT_Vector3 &orig,
                                        const UT_Vector3 &dir,
                                        fpreal radius,
                                        UT_IntArray &list);

    /// Takes an index and returns the corresponding point. Only valid if it
    /// was built with a gdp and harden() has not been called. Otherwise, it
    /// will always return NULL.
    GEO_Point           *convertIdxToPoint(int idx) const;

    /// Sets the myPointTransform member so that we can build our tree from
    /// a piece of geometry with an implicit transform on it.
    void                 setPointTransform(const UT_DMatrix4 &xform);

    /// Ensures the KD tree has been fully built.  If a KD tree
    /// is being shared among multiple threads, it is important it
    /// has first been compiled on one thread to avoid race conditions
    /// (GEO_PointTree is thread safe on read provided it has been built
    /// and provided no new points are added to it)
    void                 ensureTreeBuilt() { updateKDTree(); }

protected:
    /// These are used by KDTree:
    virtual int          comparePosition(int idx0, int idx1, int dim) const;
    virtual const fpreal*getP(int idx) const;
    virtual bool         isValid(int idx) const;

    /// These are used if the user adds points with radii.
    virtual bool         pointsHaveRadius() const;
    virtual fpreal       getRadius(int idx) const;


    /// Should be called prior to any invocation of KD Tree methods
    /// as it ensures the KDTree knows about the current number of
    /// entries.
    void                 updateKDTree();

    /// Marks the kd tree as out of date.
    void                 dirtyKDTree() { myIsKDTreeDirty = true; }

protected:
    /// Clears the myPointTransform member data.
    void                 clearPointTransform();

    /// This is the gdp we were built from.  0 if we are hardened.
    GEO_Detail          *myGdp;
    
    /// If this pointer is set, then before adding any GEO_Points to
    /// our point list, we transform their position with this matrix.
    UT_DMatrix4         *myPointTransform;
    
    /// This is the mapping from the KD entries into the GDP numbers.
    UT_IntArray          myIndexList;
    
    /// The list of all the points.
    UT_Vector3Array      myPointList;
    
    /// List of radii for each pont.
    UT_FloatArray        myRadii;

    /// Tracks if the underlying KDtree has knowledge of our current
    /// size.
    bool                 myIsKDTreeDirty;

    /// This tracks the callback for the valid nearest function.
    UT_PointTreeValidNearestFunc         myValidNearestFunc;
    void                                *myValidNearestData;
};

#endif

---