UT/UT_LineTree.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:
 *      Edward Lam
 *      Side Effects
 *      477 Richmond Street West
 *      Toronto, Ontario
 *      Canada   M5V 3E7
 *      416-504-9876
 *
 * NAME:        UT_LineTree.h (C++)
 *
 * COMMENTS:
 *
 *      This implements an PMR-Tree/octree variant designed for sorting
 * line segments in 3-space for easy access.
 *
 */

#ifndef __UT_LineTree_h__
#define __UT_LineTree_h__

#include "UT_API.h"
class UT_Vector3;
class UT_BoundingBox;
class utLineTreeNode;
class utLeafNode;
class utLineList;

class UT_API UT_LineTree 
{
public:
    UT_LineTree();
    virtual ~UT_LineTree();

    // add a line segment, returns index of line segment
    int addLine( const UT_Vector3 &pt1, const UT_Vector3 &pt2 );

    // build the tree using the line segments added with addLine
    //      bbox - bounding box that will enclose all possible query points
    //             (this bounding box is enlarged with all line segments)
    // returns FALSE if tree is already built or no lines have been added, 
    // 
    int buildTree( UT_BoundingBox &bbox );
    
    // removes all line segments from tree
    void clear();

    // finds the nearest line id to the given point.
    // if dist2 != NULL, then it is stored the squared distance from the
    // found line segment and the point pt.
    // returns -1 if pt is not within our bounding box or the tree is not
    // build yet
    int findNearestLineSegment( const UT_Vector3 &pt, float *dist2 = NULL );

    // finds the k nearest line segments to the given point.
    // this function only works if you built the tree with a threshold that
    // is >= max_lines.
    // the results are stored into the buffers given by the caller
    // return value is the number of actual line segments found
    unsigned findKNearestLineSegments(  const UT_Vector3 &pt, 
                                        int line_id[],
                                        float line_dist2[],
                                        unsigned max_lines );

    // set the threshold for splitting up; 
    // will only take effect when starting a new tree!
    void requestThreshold( unsigned threshold )
            { myRequestedThreshold = threshold; }

    // retrieves the added line segment by id 
    // returns TRUE if found, otherwise FALSE
    int getLineById( int id, UT_Vector3 &pt1, UT_Vector3 &pt2 );

    // outputs the tree to stdout for debugging
    void dumpTree() const;

private:

    void addLineToTree( utLineTreeNode *&root, unsigned idx, int depth = 0,
                        int split = 1 );

    static utLineTreeNode  *newLeafNode( 
                                unsigned max_lines, 
                                const UT_Vector3 &corner1,
                                const UT_Vector3 &corner2 );

    int findPoint( utLineTreeNode *tree, const UT_Vector3 &pt, 
                   utLeafNode *&node, utLineTreeNode *&parent ) const;

    int getClosestLine( utLineTreeNode *tree, const UT_Vector3 &pt,
                        utLineTreeNode *avoid,
                        int &line_idx, float &mindist2 ) const;
    int getClosestLineWithinBBox( utLineTreeNode *tree, 
                                  const UT_Vector3 &pt, 
                                  const UT_BoundingBox &bbox, 
                                  utLineTreeNode *avoid, int &line_idx, 
                                  float &mindist2 ) const;

    void getKClosestLineWithinBBox( 
                    utLineTreeNode *tree, const UT_Vector3 &pt, 
                    const UT_BoundingBox &bbox, utLineTreeNode *avoid, 
                    int line_idx[], float mindist2[], 
                    unsigned &num_lines, unsigned max_lines ) const;
    void getKClosestLine( 
                    utLineTreeNode *tree, const UT_Vector3 &pt,
                    utLineTreeNode *avoid,
                    int line_idx[], float mindist2[],
                    unsigned &num_lines, unsigned max_lines ) const;

private: 
    utLineTreeNode  *myRoot;
    utLineList      *myLineList;
    char            *myLineUsed;
    unsigned        myRequestedThreshold;
    unsigned        myThreshold;
};

#endif // __UT_LineTree_h__

---