HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_PointTree.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_PointTree.h (C++)
7  *
8  * COMMENTS:
9  * THIS CLASS IS DEPRECATED.
10  * You probably want to use GEO_PointTree.
11  *
12  * This implements an octree variant designed for sorting
13  * points in space for easy access.
14  * It does not support the addition of points in a piecemeal
15  * fashion, they must all be given at once.
16  *
17  */
18 
19 #ifndef __UT_PointTree_h__
20 #define __UT_PointTree_h__
21 
22 #include "UT_API.h"
23 #include "UT_Array.h"
24 #include "UT_BoundingBox.h"
25 #include "UT_FloatArray.h"
26 #include "UT_NonCopyable.h"
27 #include "UT_VectorTypes.h"
28 
29 typedef int (*UT_PointTreeValidNearestFunc)(void *data, void *userdata);
30 
31 class ut_PointTreeQueue;
32 class utPointNode;
33 
35 {
36 public:
37  // Constructors/destructors:
38  UT_PointTree();
39  virtual ~UT_PointTree();
40 
42 
43  // Builds (And possibly rebuilds) the tree with the given data:
44  // Max size is the maximum size of a leaf.
45  int build(const UT_Array<void *> &data,
46  const UT_Vector3Array &points,
47  int maxsize = 5);
48 
49  // Finds the nearest point not more than maxdist away. If there
50  // is none, returns null.
51  void *findNearest(const UT_Vector3 &pt, float maxdist,
53  void *user_data = NULL);
54 
55  // Finds the nearest [groupsize] points not more than maxdist away.
56  // Returns the number of points found and stores the points in group.
57  // The returned groupdist2 array returns their squared distances.
58  void findNearestGroup(const UT_Vector3 &pt, float maxdist,
59  int groupsize,
60  UT_Array<void *> &group,
61  UT_FloatArray &groupdist2,
63  void *user_data = NULL);
64 
65  // Find all points within the specified distance
66  int findAllClose(const UT_Vector3 &pt, float maxdist,
67  UT_Array<void *> &data);
68 
69  // Finds all the points within a specified tube:
70  int findAllInTube(const UT_Vector3 &orig,
71  const UT_Vector3 &dir, fpreal rad,
72  UT_Array<void *> &data);
73 
74  void getBBox(UT_BoundingBox &box) const { box = myBBox; }
75 
76  // Returns 1 if the tree is properly constructed.
77  int verifyTree() const;
78 
79  void destroyTree();
80 
81 protected:
82  // Recursively destroyes the tree.
83  void destroyNode(utPointNode *node);
84 
85  // Verifies a node.
86  int verifyNode(UT_BoundingBox &box, utPointNode *node)
87  const;
88 
89  // Merely counts the number of points that will land in each
90  // bucket.
91  void testAxis(const UT_BoundingBox &box, int axis,
92  const UT_Vector3Array &points,
93  int &splitleft, int &splitright);
94 
95  // Actually divides the points/data into two lists, placed
96  // into *left & *right
97  void splitOnAxis(const UT_BoundingBox &box, int axis,
98  const UT_Array<void *> &data,
99  const UT_Vector3Array &points,
100  UT_Array<void *> &dataleft,
101  UT_Vector3Array &pointsleft,
102  UT_Array<void *> &dataright,
103  UT_Vector3Array &pointsright);
104 
105  utPointNode *buildChildNode(const UT_BoundingBox &box,
106  const UT_Array<void *> &data,
107  const UT_Vector3Array &points,
108  int inbboxnode = 0);
109 
110  void *findNearestNode(UT_BoundingBox &box,
111  utPointNode *node, const UT_Vector3 &pt,
112  float &maxdist,
114  void *user_data = NULL);
115  void findNearestNodeGroup(UT_BoundingBox &box,
116  utPointNode *node, const UT_Vector3 &pt,
117  ut_PointTreeQueue &q,
119  void *user_data = NULL);
120 
121  int findCloseNodes(UT_BoundingBox &box,
122  utPointNode *node, const UT_Vector3 &pt,
123  float &maxdist,
124  UT_Array<void *> &data);
125 
126  int findInTube(UT_BoundingBox &box,
127  utPointNode *node, const UT_Vector3 &orig,
128  const UT_Vector3 &dir,
129  fpreal radius, fpreal radius2,
130  UT_Array<void *> &data);
131 
132  utPointNode *myRoot;
135 };
136 
137 #endif
typedef int(APIENTRYP RE_PFNGLXSWAPINTERVALSGIPROC)(int)
GLdouble GLdouble GLint GLint const GLdouble * points
Definition: glad.h:2676
GLboolean * data
Definition: glcorearb.h:131
#define UT_API
Definition: UT_API.h:14
GLdouble GLdouble GLdouble q
Definition: glad.h:2445
void getBBox(UT_BoundingBox &box) const
Definition: UT_PointTree.h:74
#define UT_NON_COPYABLE(CLASS)
Define deleted copy constructor and assignment operator inside a class.
int(* UT_PointTreeValidNearestFunc)(void *data, void *userdata)
Definition: UT_PointTree.h:29
UT_BoundingBox myBBox
Definition: UT_PointTree.h:133
fpreal64 fpreal
Definition: SYS_Types.h:277
utPointNode * myRoot
Definition: UT_PointTree.h:132
Definition: format.h:895