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_Format.h"
20 #include "UT_VectorTypes.h"
21 #include "UT_BoundingBox.h"
22 #include "UT_Array.h"
23 
24 
25 class utLineTreeNode;
26 class utLeafNode;
27 
29 {
30 public:
31  UT_LineTree();
32  virtual ~UT_LineTree();
33 
34  // add a line segment, returns index of line segment
35  int addLine( const UT_Vector3 &pt1, const UT_Vector3 &pt2 );
36 
37  // return the number of lines in the tree
38  int size() const { return myLineList.size(); }
39 
40  // If you know how many lines you'll add, use this to allocate ahead of
41  // time.
42  void setCapacity( unsigned capacity )
43  {
44  myLineList.setCapacity(capacity);
45  }
46 
47  // build the tree using the line segments added with addLine
48  // returns false if tree is already built or no lines have been added,
49  //
50  bool buildTree();
51 
52  // removes all line segments from tree
53  void clear();
54 
55  // finds the nearest line id to the given point.
56  // if dist2 != NULL, then it is stored the squared distance from the
57  // found line segment and the point pt.
58  // returns -1 if pt is not within our bounding box or the tree is not
59  // build yet
60  int findNearestLineSegment( const UT_Vector3 &pt, float *dist2 = NULL ) const;
61 
62  // finds the k nearest line segments to the given point.
63  // the results are stored into the buffers given by the caller
64  // return value is the number of actual line segments found
65  unsigned findKNearestLineSegments( const UT_Vector3 &pt,
66  int line_id[],
67  float line_dist2[],
68  unsigned max_lines,
69  float max_dist2) const;
70 
71  unsigned findKNearestLineSegments( const UT_Vector3 &pt,
72  int line_id[],
73  float line_dist2[],
74  unsigned max_lines ) const;
75 
76  // set the threshold for splitting up;
77  // will only take effect when starting a new tree!
78  void requestThreshold( unsigned threshold )
79  { myRequestedThreshold = threshold; }
80 
81  // retrieves the added line segment by id
82  // returns true if found, otherwise false
83  bool getLineById( int id, UT_Vector3 &pt1, UT_Vector3 &pt2 );
84 
85  // reverse the positions of the given line segment
86  void reverseLine(int id)
87  { myLineList(id).reverse(); }
88 
89  const UT_Vector3& linePos1(int id) const { return myLineList(id).myP1; }
90  const UT_Vector3& linePos2(int id) const { return myLineList(id).myP2; }
91 
92  // outputs the tree to stdout for debugging
93  void dumpTree(bool verbose = true) const;
94 
95 private:
96  struct Line {
97  Line() {}
98  Line(const UT_Vector3 &p1, const UT_Vector3 &p2)
99  : myP1(p1), myP2(p2)
100  {
101  myIDir = 1.0F / (myP2 - myP1);
102  }
103  void reverse()
104  {
105  UT_Vector3 p = myP1;
106  myP1 = myP2;
107  myP2 = p;
108  myIDir = 1.0F / (myP2 - myP1);
109  }
110 
111  UT_Vector3 myP1;
112  UT_Vector3 myP2;
113  UT_Vector3 myIDir;
114  };
115 
116  class IsInside {
117  public:
118  IsInside(const UT_BoundingBox &box,
119  const UT_Array<Line> &list)
120  : myBox(box)
121  , myLineList(list) {}
122  bool operator()(int idx) const
123  {
124  return myBox.isLineInside(myLineList(idx).myP1,
125  myLineList(idx).myIDir);
126  }
127  private:
128  const UT_BoundingBox &myBox;
129  const UT_Array<Line> &myLineList;
130  };
131 
132  utLineTreeNode *buildTree(const UT_BoundingBox &box,
133  int *lines, int nlines, int depth);
134  void dumpTree(const utLineTreeNode *node,
135  bool verbose,
136  unsigned &num_octnodes,
137  unsigned &num_leafnodes,
138  double &num_leaflines,
139  unsigned &max_depth,
140  unsigned depth = 0) const;
141 
142  static utLineTreeNode *newLeafNode(
143  unsigned max_lines,
144  const UT_Vector3 &corner1,
145  const UT_Vector3 &corner2 );
146 
147  void getKClosestLine(
148  utLeafNode *tree, const UT_Vector3 &pt,
149  int line_idx[], float mindist2[],
150  unsigned &num_lines, unsigned max_lines,
151  float in_max_dist2 ) const;
152 
153 private:
154  UT_Array<Line> myLineList;
155  utLineTreeNode *myRoot;
156  unsigned myRequestedThreshold;
157  unsigned myThreshold;
158 };
159 
160 #endif // __UT_LineTree_h__
void setCapacity(unsigned capacity)
Definition: UT_LineTree.h:42
int size() const
Definition: UT_LineTree.h:38
void reverse(I begin, I end)
Definition: pugixml.cpp:7190
#define UT_API
Definition: UT_API.h:13
void requestThreshold(unsigned threshold)
Definition: UT_LineTree.h:78
GLfloat GLfloat p
Definition: glew.h:16321
const UT_Vector3 & linePos1(int id) const
Definition: UT_LineTree.h:89
Type-safe formatting, modeled on the Python str.format function.
const UT_Vector3 & linePos2(int id) const
Definition: UT_LineTree.h:90
void reverseLine(int id)
Definition: UT_LineTree.h:86
GLint GLint GLsizei GLsizei GLsizei depth
Definition: glew.h:1254