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_BoundingBox.h"
24 #include "UT_Array.h"
25 #include "UT_FloatArray.h"
26 
27 typedef int (*UT_PointTreeValidNearestFunc)(void *data, void *userdata);
28 
29 class ut_PointTreeQueue;
30 
31 class utPointNode;
32 #include "UT_VectorTypes.h"
33 
35 {
36 public:
37  // Constructors/destructors:
38  UT_PointTree();
39  virtual ~UT_PointTree(void);
40 
41 
42  // Builds (And possibly rebuilds) the tree with the given data:
43  // Max size is the maximum size of a leaf.
44  int build(const UT_Array<void *> &data,
45  const UT_Vector3Array &points,
46  int maxsize = 5);
47 
48  // Finds the nearest point not more than maxdist away. If there
49  // is none, returns null.
50  void *findNearest(const UT_Vector3 &pt, float maxdist,
52  void *user_data = NULL);
53 
54  // Finds the nearest [groupsize] points not more than maxdist away.
55  // Returns the number of points found and stores the points in group.
56  // The returned groupdist2 array returns their squared distances.
57  void findNearestGroup(const UT_Vector3 &pt, float maxdist,
58  int groupsize,
59  UT_Array<void *> &group,
60  UT_FloatArray &groupdist2,
62  void *user_data = NULL);
63 
64  // Find all points within the specified distance
65  int findAllClose(const UT_Vector3 &pt, float maxdist,
66  UT_Array<void *> &data);
67 
68  // Finds all the points within a specified tube:
69  int findAllInTube(const UT_Vector3 &orig,
70  const UT_Vector3 &dir, fpreal rad,
71  UT_Array<void *> &data);
72 
73  void getBBox(UT_BoundingBox &box) const { box = myBBox; }
74 
75  // Returns 1 if the tree is properly constructed.
76  int verifyTree() const;
77 
78  void destroyTree();
79 
80 protected:
81  // Recursively destroyes the tree.
82  void destroyNode(utPointNode *node);
83 
84  // Verifies a node.
85  int verifyNode(UT_BoundingBox &box, utPointNode *node)
86  const;
87 
88  // Merely counts the number of points that will land in each
89  // bucket.
90  void testAxis(const UT_BoundingBox &box, int axis,
91  const UT_Vector3Array &points,
92  int &splitleft, int &splitright);
93 
94  // Actually divides the points/data into two lists, placed
95  // into *left & *right
96  void splitOnAxis(const UT_BoundingBox &box, int axis,
97  const UT_Array<void *> &data,
98  const UT_Vector3Array &points,
99  UT_Array<void *> &dataleft,
100  UT_Vector3Array &pointsleft,
101  UT_Array<void *> &dataright,
102  UT_Vector3Array &pointsright);
103 
104  utPointNode *buildChildNode(const UT_BoundingBox &box,
105  const UT_Array<void *> &data,
106  const UT_Vector3Array &points,
107  int inbboxnode = 0);
108 
109  void *findNearestNode(UT_BoundingBox &box,
110  utPointNode *node, const UT_Vector3 &pt,
111  float &maxdist,
113  void *user_data = NULL);
114  void findNearestNodeGroup(UT_BoundingBox &box,
115  utPointNode *node, const UT_Vector3 &pt,
116  ut_PointTreeQueue &q,
118  void *user_data = NULL);
119 
120  int findCloseNodes(UT_BoundingBox &box,
121  utPointNode *node, const UT_Vector3 &pt,
122  float &maxdist,
123  UT_Array<void *> &data);
124 
125  int findInTube(UT_BoundingBox &box,
126  utPointNode *node, const UT_Vector3 &orig,
127  const UT_Vector3 &dir,
128  fpreal radius, fpreal radius2,
129  UT_Array<void *> &data);
130 
131  utPointNode *myRoot;
134 };
135 
136 #endif
#define UT_API
Definition: UT_API.h:13
void getBBox(UT_BoundingBox &box) const
Definition: UT_PointTree.h:73
int(* UT_PointTreeValidNearestFunc)(void *data, void *userdata)
Definition: UT_PointTree.h:27
GLboolean * data
Definition: glcorearb.h:130
UT_BoundingBox myBBox
Definition: UT_PointTree.h:132
double fpreal
Definition: SYS_Types.h:270
typedef int
Definition: png.h:1175
utPointNode * myRoot
Definition: UT_PointTree.h:131