HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_LineTree.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: UT_LineTree.h (C++)
7  *
8  * COMMENTS:
9  *
10  * This implements an PMR-Tree/octree variant designed for sorting
11  * line segments in 3-space for easy access.
12  *
13  */
14 
15 #ifndef __UT_LineTree_h__
16 #define __UT_LineTree_h__
17 
18 #include "UT_API.h"
19 #include "UT_VectorTypes.h"
20 #include "UT_BoundingBox.h"
21 #include "UT_Array.h"
22 
23 
24 class utLineTreeNode;
25 class utLeafNode;
26 
28 {
29 public:
30  UT_LineTree();
31  virtual ~UT_LineTree();
32 
33  // add a line segment, returns index of line segment
34  int addLine( const UT_Vector3 &pt1, const UT_Vector3 &pt2 );
35 
36  // return the number of lines in the tree
37  int size() const { return myLineList.size(); }
38 
39  // build the tree using the line segments added with addLine
40  // returns FALSE if tree is already built or no lines have been added,
41  //
42  int buildTree();
43 
44  // removes all line segments from tree
45  void clear();
46 
47  // finds the nearest line id to the given point.
48  // if dist2 != NULL, then it is stored the squared distance from the
49  // found line segment and the point pt.
50  // returns -1 if pt is not within our bounding box or the tree is not
51  // build yet
52  int findNearestLineSegment( const UT_Vector3 &pt, float *dist2 = NULL ) const;
53 
54  // finds the k nearest line segments to the given point.
55  // the results are stored into the buffers given by the caller
56  // return value is the number of actual line segments found
57  unsigned findKNearestLineSegments( const UT_Vector3 &pt,
58  int line_id[],
59  float line_dist2[],
60  unsigned max_lines ) const;
61 
62  // set the threshold for splitting up;
63  // will only take effect when starting a new tree!
64  void requestThreshold( unsigned threshold )
65  { myRequestedThreshold = threshold; }
66 
67  // retrieves the added line segment by id
68  // returns TRUE if found, otherwise FALSE
69  int getLineById( int id, UT_Vector3 &pt1, UT_Vector3 &pt2 );
70 
71  // reverse the positions of the given line segment
72  void reverseLine(int id)
73  { myLineList(id).reverse(); }
74 
75  const UT_Vector3& linePos1(int id) const { return myLineList(id).myP1; }
76  const UT_Vector3& linePos2(int id) const { return myLineList(id).myP2; }
77 
78  // outputs the tree to stdout for debugging
79  void dumpTree(bool verbose = true) const;
80 
81 private:
82  struct Line {
83  Line() {}
84  Line(const UT_Vector3 &p1, const UT_Vector3 &p2)
85  : myP1(p1), myP2(p2)
86  {
87  myIDir = 1.0F / (myP2 - myP1);
88  }
89  void reverse()
90  {
91  UT_Vector3 p = myP1;
92  myP1 = myP2;
93  myP2 = p;
94  myIDir = 1.0F / (myP2 - myP1);
95  }
96 
97  UT_Vector3 myP1;
98  UT_Vector3 myP2;
99  UT_Vector3 myIDir;
100  };
101 
102  class IsInside {
103  public:
104  IsInside(const UT_BoundingBox &box,
105  const UT_Array<Line> &list)
106  : myBox(box)
107  , myLineList(list) {}
108  bool operator()(int idx) const
109  {
110  return myBox.isLineInside(myLineList(idx).myP1,
111  myLineList(idx).myIDir);
112  }
113  private:
114  const UT_BoundingBox &myBox;
115  const UT_Array<Line> &myLineList;
116  };
117 
118  utLineTreeNode *buildTree(const UT_BoundingBox &box,
119  int *lines, int nlines, int depth);
120  void dumpTree(const utLineTreeNode *node,
121  bool verbose,
122  unsigned &num_octnodes,
123  unsigned &num_leafnodes,
124  double &num_leaflines,
125  unsigned &max_depth,
126  unsigned depth = 0) const;
127 
128  static utLineTreeNode *newLeafNode(
129  unsigned max_lines,
130  const UT_Vector3 &corner1,
131  const UT_Vector3 &corner2 );
132 
133  void getKClosestLine(
134  utLeafNode *tree, const UT_Vector3 &pt,
135  int line_idx[], float mindist2[],
136  unsigned &num_lines, unsigned max_lines ) const;
137 
138 private:
139  UT_Array<Line> myLineList;
140  utLineTreeNode *myRoot;
141  unsigned myRequestedThreshold;
142  unsigned myThreshold;
143 };
144 
145 #endif // __UT_LineTree_h__
int size() const
Definition: UT_LineTree.h:37
#define UT_API
Definition: UT_API.h:13
GLint GLint GLsizei GLsizei GLsizei depth
Definition: glcorearb.h:475
void requestThreshold(unsigned threshold)
Definition: UT_LineTree.h:64
const UT_Vector3 & linePos1(int id) const
Definition: UT_LineTree.h:75
const UT_Vector3 & linePos2(int id) const
Definition: UT_LineTree.h:76
void reverseLine(int id)
Definition: UT_LineTree.h:72