HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
BV_OBBTree.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  */
7 
8 #ifndef __BV_OBBTree_h__
9 #define __BV_OBBTree_h__
10 
11 #include "BV_API.h"
12 #include "BV_Tree.h"
13 #include <UT/UT_Array.h>
14 #include <UT/UT_BoundingBox.h>
15 #include <UT/UT_LinkListT.h>
16 #include <UT/UT_Matrix3.h>
17 #include <UT/UT_Vector3.h>
18 
19 #include <set>
20 #include <map>
21 
22 class UT_IStream;
23 struct bvTransform;
24 class BV_OBB_Extra;
25 
26 // Set to 1 to allow debug output statements.
27 #define CONVEX_HULL_DEBUG 0
28 
29 /**********************************************************************************************************************************/
30 class BV_CHTriangle;
32 
33 // A linked list holding all temporary triangles created while building the hull
38 /**********************************************************************************************************************************/
39 // Temporary structure to get the triangles out of the convex hull algorithm.
40 // Should probably be replaced with something better later on.
42 {
44 };
46 /**********************************************************************************************************************************/
47 // A helper structure that holds edge information as the algorithm is running.
49 {
50 public:
51  BV_CHEdgeInfo();
52 
53  void reset();
54 
55  bool operator()(const BV_CHEdgeInfo& s1, const BV_CHEdgeInfo& s2) const;
56 
59 
60  // Only relevant when myUsedCount is one. If true, the edge remaining
61  // in use goes from myV1 to myV2, opposite if false.
62  // Not valid for myUsedCount == 2 (both are used), or myUsedCount == 0
63  // (none are used).
65 };
66 typedef std::set<BV_CHEdgeInfo,BV_CHEdgeInfo> TEdgeInfoSet;
67 /**********************************************************************************************************************************/
69 {
70 public:
72  BV_CHPointInfo(const UT_Vector3 point_in);
73 
74  /// Accumulated the point position
75  void addPoint(const UT_Vector3 point_in);
76 
77  /// Returns an average point position accumulated so far
79 
80  bool operator()(const UT_Vector3& s1, const UT_Vector3& s2) const;
81 
82 private:
83  UT_Vector3 myAccumPosition;
84  int myAccumCount;
85 };
86 typedef std::map<UT_Vector3, BV_CHPointInfo, BV_CHPointInfo> TPointInfoMap;
87 /**********************************************************************************************************************************/
89 {
90 public:
91 
92  /// Constructs the manager, welds input points.
93  BV_CHDataManager(const TPointArray& points_in);
94 
95  /// Find an edge between two vertices
96  const BV_CHEdgeInfo* findEdge(int curr_v1_idx, int curr_v2_idx) const;
97 
98  /// Traverse edges
101 
102  /// Checks for valid edge counts. Debug.
103  void edgeSanityCheck();
104 
105  /// Sets a flag telling the manager we will do a reset next,
106  /// so that no triangle-edge management code is called to save time.
107  void setAboutToReset();
108 
109  /// Resets the manager for the next iteration.
110  void reset();
111 
112  /// Welds points from the points_in array and puts the new set of points
113  /// into the merged_pts_out array. Currently welds within FLT_EPSILON.
114  void weldPoints(const TPointArray& points_in, TPointArray& merged_pts_out);
115 
117  { return myPoints; }
118  bool getDoRestart() const
119  { return myDoRestart; }
120 
121  /// Called every time a triangle is created.
122  void onTriangleDeleted(BV_CHTriangle* triangle_in);
123 
124  /// Called every time a triangle is deleted or is marked as deleted.
125  void onTriangleCreated(BV_CHTriangle* triangle_in);
126 
127  /// Jiggles a point to lie more than FLT_EPSILON away from the triangle.
128  fpreal jigglePointTetra(BV_CHTriangle *coplanar_triangle, int iPointIndex);
129 
130 private:
131 
132  // A copy of all points
133  TPointArray myPoints;
134 
135  // A set of all edges currently in existence.
136  TEdgeInfoSet myEdges;
137  TEdgeInfoSet::iterator myTraversalIt;
138 
139  bool myDoRestart;
140  bool myIsAboutToReset;
141 
142  // Multiplier array, per point. Not cleared in reset().
143  TFloatArray myPointJiggleMults;
144 
145 #if CONVEX_HULL_DEBUG
146  int myDBJigglePath;
147 #endif
148 
149 };
150 /**********************************************************************************************************************************/
152 {
153 public:
154 
155  BV_CHTriangle(BV_CHDataManager& parent_manager, uint point1_idx,uint point2_idx,uint point3_idx);
156  ~BV_CHTriangle();
157 
158  /// Marks the triangle as deleted. If bCallManager is true, calls CCHDataManager::onTriangleDeleted()
159  /// to manage related edges.
160  void markDeleted(bool do_call_manager = true);
161 
162  /// Gets signed distance from the given point to the triangle
163  inline fpreal getSignedDistance(const uint point_index);
164 
165  /// Checks whether this triangle can see the given point or not.
166  bool canSee(const uint point_index);
167 
168  /// Associates all points that this triangle can see that are still not associated
169  /// from the points_in array. If do_ignore_restart_flag is true, keeps on going even
170  /// if a restart becomes necessary.
171  void associatePoints(TPointIndexArray& points_in, bool do_ignore_restart_flag);
172 
173  /// Returns true if this is a "bad" triangle, false otherwise.
174  bool getIsBad() const;
175 
176  /// Clears all points associated with this triangle.
177  void clearAssocPoints();
178 
179  /// Find the most distant point associated with this triangle.
180  bool findMostDistantAssocPoint(uint& point_idx_out);
181 
182  /// Gets triangle normal. Cached.
183  void getNormal(UT_Vector3 &normal);
184 
185  /// Appends this triangle's associated points to rPointsOut array.
186  void getAssocPoints(TPointIndexArray& points_idx_out);
187  void printAssocPoints();
188 
189  bool getIsDeleted() const
190  { return myIsDeleted; }
191  inline uint getVertex(int index) const
192  { return myVertices[index]; }
193 
194 private:
195  BV_CHDataManager *myManager;
196  uint myVertices[3];
197  bool myIsDeleted;
198 
199  UT_Vector3 myCachedNormal;
200  bool myIsNormalValid;
201 
202  // An array of associated points
203  TPointIndexArray myAssocPoints;
204 
205  TPointArray& myAllPoints;
206 };
207 /**********************************************************************************************************************************/
208 
209 /// A single node in a BV_OBBTree
211 {
212 public:
213  BV_OBB(int startLeaf, int numLeaves);
214  BV_OBB(const BV_OBB &);
215  ~BV_OBB();
216 
217  bool isLeaf() const;
218 
219  void save(std::ostream &os, bool onlyStructure) const;
220  static BV_OBB *load(UT_IStream &is, bool onlyStructure);
221 
222  int64 getMemoryUsage() const;
223 
224  /// Hackish way of determining if a leaf is disabled or not.
225  bool isDisabled() const
226  { return mySize < 0; }
227 
228 
229  /// Orientation of the bounding box, relative to parent
231  /// Center, relative to parent.
233 
234  /// Radii in each axis (half of the dimension)
236  /// Length of myRadii.
237  /// Special value of "-1" is used to signal that a node is disabled.
239 
240  /// Index of first leaf.
242  /// How many leaves I own.
244 
245  BV_OBB *myLeft, *myRight;
246 
248 
249  void *myUserData;
250 
251 private:
252  /// Disallowed.
253  BV_OBB &operator=(const BV_OBB &);
254 };
255 
256 /// Bounding volume hierarchy based on Oriented Bounding Boxes (OBBs).
257 ///
258 /// Build: O(n^2)
259 /// Update extents: O(n^2)
260 
261 // Source:
262 // Gottschalk, Lin and Manocha, "OBB-Tree: A Hierarchical Structure for
263 // Rapid Interference Detection," Proceedings of ACM SIGGRAPH 1996, pages
264 // 171-180. ACM Press, 1996.
265 // ftp://ftp.cs.unc.edu/pub/users/gottscha/obbt.ps.gz
266 class BV_API BV_OBBTree : public BV_Tree
267 {
268 public:
270 
271  BV_OBBTree();
272  BV_OBBTree(const BV_OBBTree &);
273  ~BV_OBBTree() override;
274 
275  BV_OBBTree &operator=(const BV_OBBTree &);
276 
277  const char *getType() const override;
278  const BV_Tree *castTo(const char *type) const override;
279  BV_Tree *castTo(const char *type) override;
280 
281  /// Alternative lazy building: sections of the tree are only built when a
282  /// query needs them. In this case, the leaf iterator *must* not be
283  /// destroyed until the tree is destroyed, or until a fresh call to
284  /// buildLazy.
286  {
287  buildInternal(leafIt, true);
288  }
289 
290  void getRootOBB(UT_Matrix4 &xform, UT_Vector3 &radii) const;
291 
292  /// If true, a somewhat different version of the algorithm is used to compute
293  /// OBBs around nodes, which uses a convex hull around the points instead of
294  /// the points themselves. While slower, it results in a consistent bbox
295  /// that is not influenced by the density/inner points on the mesh. False by default.
296  void setUseConvexHull(bool bValue);
297  bool getUseConvexHull();
298 
299 protected:
300  class bvLeaf
301  {
302  public:
303  // Default copy constructor is fine.
304  // Default assignment operator is fine.
305 
306  // Sort key *must* be first member of this class.
307  float sortkey;
308  int leafId;
310  };
311 
312  BV_Tree *cloneSubclass() const override;
313  int64 getMemoryUsageSubclass() const override;
314  int getNumLeavesSubclass() const override;
315  /// Saving and loading only works for non-lazy building.
316  // @{
317  void saveSubclass(std::ostream &os,
318  bool onlyStructure) const override;
319  bool loadSubclass(UT_IStream &is,
320  bool onlyStructure) override;
321  // @}
322 
323  void buildSubclass(BV_LeafIterator &leafIt) override
324  {
325  buildInternal(leafIt, false);
326  }
328  BV_LeafIterator &leafIt) override;
329  /// WARNING: not thread-safe if tree was lazily built!
330  BV_Status intersectSubclass(BV_Callback &callback,
331  const BV_Tree &treeb,
332  const UT_DMatrix4 &startxforma,
333  const UT_DMatrix4 &startxformb,
334  const UT_DMatrix4 &endxforma,
335  const UT_DMatrix4 &endxformb,
336  fpreal tol) const override;
337 
339  {
340  return myRoot;
341  }
342  void buildInternal(BV_LeafIterator &leafIt, bool lazy);
343  /// Build the tree. If depth is non-negative, the algorithm is lazy and
344  /// stops after depth levels.
345  BV_OBB *createTree(int startprim, int numleaves,
346  const UT_Matrix3 &rootBasis,
347  const UT_Vector3 &rootPos, int depth = -1);
348  void createChildren(BV_OBB &root, int depth = -1);
349  bool updateExtentsRecurse(BV_OBB &node,
350  const UT_Matrix3 &parentBasis,
351  const UT_Vector3 &parentPos);
352 
353  void getBounds(const UT_Matrix3 &basis,
354  UT_BoundingBox &bbox, bool &firstPrim);
355  /// Calculate the OBB associated with the given node. Stores
356  /// orientation in node->myRot, and calls calcSize to calculate the
357  /// extents. May disable the node if it contains no enabled leaves.
358  void calcOBB(BV_OBB &node);
359  /// Given the input OBB orientation, calculate the OBB extents.
360  /// Stores extents (radii) and position in node.
361  void calcSize(BV_OBB &node);
362 
363  /// Compute a convex hull around the points provided, output result as a series of triangles
364  /// to the array provided. This is currently slower than it should be. Also, note that
365  /// if coplanar points are present, the convex hull constructed might be around jiggled versions
366  /// of those points.
367  bool computeConvexHull(const TPointArray& source_points_in, TSimpleTriangleArray& final_triangles_out);
368  bool doConvexHullIteration(BV_CHDataManager& data_manager, TTriArray& working_triangles);
369 
370  bool intersectRecurse(BV_Callback &callback,
371  const BV_OBBTree &treeb,
372  const BV_OBB &a, const BV_OBB &b,
373  const bvTransform &t1, const bvTransform &t2,
374  const bvTransform &t3, const bvTransform &t4,
375  fpreal tol, int identities) const;
376 
377 
378  static int compareLeaves(const void *t1, const void *t2);
379 
380  void calculateSortKeys(bvLeaf *prims, int numleaves,
381  UT_Matrix3 &basis, int axis) const;
382 
386 
388 };
389 
390 /// Extra data for a lazily constructed BV_OBB node.
392 {
393 public:
396 };
397 
398 
400 {
401  /// relative rotation
403  /// relative translation
405  /// relative transformation
406  UT_DMatrix4 xform[2];
407  /// create a new bvTransform that has updated relative rotation/translation
408  /// for the left tree (tree a)
409  void updateL(const UT_Matrix3 &rot,
410  const UT_Vector3 &trans,
411  bvTransform &xform) const;
412  /// same as updateL, except for the right tree (tree b)
413  void updateR(const UT_Matrix3 &rot,
414  const UT_Vector3 &trans,
415  bvTransform &xform) const;
416  /// update myself given (xforma, xformc) and (xformb, xformb) with
417  /// left tree (ra, ta) and right tree (rb, tb)
418  void update(const UT_Matrix3 &ra,
419  const UT_Matrix3 &rb,
420  const UT_Vector3 &ta,
421  const UT_Vector3 &tb,
422  const UT_DMatrix4 &xforma,
423  const UT_DMatrix4 &xformb,
424  const UT_DMatrix4 &xformc,
425  const UT_DMatrix4 &xformd);
426 };
427 
428 
429 #endif
BV_OBB * myRight
Definition: BV_OBBTree.h:245
virtual void saveSubclass(std::ostream &os, bool onlyStructure) const =0
uint getVertex(int index) const
Definition: BV_OBBTree.h:191
TPointArray & getPoints()
Definition: BV_OBBTree.h:116
UT_Vector3 myTrans
Center, relative to parent.
Definition: BV_OBBTree.h:232
UT_Vector3 myVertices[3]
Definition: BV_OBBTree.h:43
void buildSubclass(BV_LeafIterator &leafIt) override
Definition: BV_OBBTree.h:323
UT_Vector3 myRadii
Radii in each axis (half of the dimension)
Definition: BV_OBBTree.h:235
void edgeSanityCheck()
Checks for valid edge counts. Debug.
void clearAssocPoints()
Clears all points associated with this triangle.
virtual bool loadSubclass(UT_IStream &is, bool onlyStructure)=0
GA_API const UT_StringHolder rot
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1222
void printAssocPoints()
virtual BV_Status intersectSubclass(BV_Callback &callback, const BV_Tree &treeb, const UT_DMatrix4 &startxforma, const UT_DMatrix4 &startxformb, const UT_DMatrix4 &endxforma, const UT_DMatrix4 &endxformb, fpreal tol) const =0
const BV_CHEdgeInfo * edgeTraversalNext()
BV_CHTriangle(BV_CHDataManager &parent_manager, uint point1_idx, uint point2_idx, uint point3_idx)
int myStartLeaf
Index of first leaf.
Definition: BV_OBBTree.h:241
UT_Vector3 barycenter
Definition: BV_OBBTree.h:309
const BV_CHEdgeInfo * edgeTraversalBegin()
Traverse edges.
void reset()
Resets the manager for the next iteration.
void getNormal(UT_Vector3 &normal)
Gets triangle normal. Cached.
UT_Matrix3 R
relative rotation
Definition: BV_OBBTree.h:402
bool isDisabled() const
Hackish way of determining if a leaf is disabled or not.
Definition: BV_OBBTree.h:225
bool myIsV1Starting
Definition: BV_OBBTree.h:64
bool operator()(const UT_Vector3 &s1, const UT_Vector3 &s2) const
virtual void updateExtentsSubclass(BV_LeafIterator &leafIt)=0
virtual int64 getMemoryUsageSubclass() const =0
void onTriangleCreated(BV_CHTriangle *triangle_in)
Called every time a triangle is deleted or is marked as deleted.
A single node in a BV_OBBTree.
Definition: BV_OBBTree.h:210
Callback for bounding volume hierarchy intersection operation.
Definition: BV_Callback.h:17
void markDeleted(bool do_call_manager=true)
Extra data for a lazily constructed BV_OBB node.
Definition: BV_OBBTree.h:391
GA_API const UT_StringHolder trans
UT_LinkListT< BV_CHTriangle * > TTriArray
Definition: BV_OBBTree.h:37
void addPoint(const UT_Vector3 point_in)
Accumulated the point position.
void buildLazy(BV_LeafIterator &leafIt)
Definition: BV_OBBTree.h:285
bool getIsBad() const
Returns true if this is a "bad" triangle, false otherwise.
BV_OBB_Extra * myExtra
Definition: BV_OBBTree.h:247
long long int64
Definition: SYS_Types.h:116
UT_Matrix3 rot
Definition: BV_OBBTree.h:394
UT_Array< BV_CHSimpleTriangle > TSimpleTriangleArray
Definition: BV_OBBTree.h:45
bool myUseConvexHullForBBoxes
Definition: BV_OBBTree.h:387
int myNumLeaves
How many leaves I own.
Definition: BV_OBBTree.h:243
bool findMostDistantAssocPoint(uint &point_idx_out)
Find the most distant point associated with this triangle.
UT_Array< bvLeaf > myLeaves
Definition: BV_OBBTree.h:384
BV_Tree BaseClass
Definition: BV_OBBTree.h:269
UT_Array< UT_Vector3 > TPointArray
Definition: BV_OBBTree.h:31
BV_LeafIterator * myLeafIt
Definition: BV_OBBTree.h:385
fpreal jigglePointTetra(BV_CHTriangle *coplanar_triangle, int iPointIndex)
Jiggles a point to lie more than FLT_EPSILON away from the triangle.
bool canSee(const uint point_index)
Checks whether this triangle can see the given point or not.
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1222
void * myUserData
Definition: BV_OBBTree.h:249
UT_Array< int > TPointIndexArray
Definition: BV_OBBTree.h:35
GLint GLint GLsizei GLsizei GLsizei depth
Definition: glcorearb.h:476
UT_Matrix3 myRot
Orientation of the bounding box, relative to parent.
Definition: BV_OBBTree.h:230
BV_CHDataManager(const TPointArray &points_in)
Constructs the manager, welds input points.
virtual BV_Tree * cloneSubclass() const =0
virtual const BV_Tree * castTo(const char *type) const
fpreal getSignedDistance(const uint point_index)
Gets signed distance from the given point to the triangle.
UT_Array< fpreal > TFloatArray
Definition: BV_OBBTree.h:36
void getAssocPoints(TPointIndexArray &points_idx_out)
Appends this triangle's associated points to rPointsOut array.
#define BV_API
Definition: BV_API.h:10
UT_Vector3 getAveragePoint() const
Returns an average point position accumulated so far.
fpreal64 fpreal
Definition: SYS_Types.h:277
LeafData & operator=(const LeafData &)=delete
void setAboutToReset()
GLuint index
Definition: glcorearb.h:786
std::map< UT_Vector3, BV_CHPointInfo, BV_CHPointInfo > TPointInfoMap
Definition: BV_OBBTree.h:86
std::set< BV_CHEdgeInfo, BV_CHEdgeInfo > TEdgeInfoSet
Definition: BV_OBBTree.h:66
void onTriangleDeleted(BV_CHTriangle *triangle_in)
Called every time a triangle is created.
BV_OBB * myRoot
Definition: BV_OBBTree.h:383
UT_Vector3 T
relative translation
Definition: BV_OBBTree.h:404
bool operator()(const BV_CHEdgeInfo &s1, const BV_CHEdgeInfo &s2) const
void associatePoints(TPointIndexArray &points_in, bool do_ignore_restart_flag)
void weldPoints(const TPointArray &points_in, TPointArray &merged_pts_out)
UT_Vector3 trans
Definition: BV_OBBTree.h:395
bool getIsDeleted() const
Definition: BV_OBBTree.h:189
type
Definition: core.h:1059
const BV_CHEdgeInfo * findEdge(int curr_v1_idx, int curr_v2_idx) const
Find an edge between two vertices.
fpreal mySize
Definition: BV_OBBTree.h:238
virtual const char * getType() const =0
unsigned int uint
Definition: SYS_Types.h:45
virtual int getNumLeavesSubclass() const =0
myRoot
Definition: UT_RTreeImpl.h:716
BV_OBB * getRoot()
Definition: BV_OBBTree.h:338
bool getDoRestart() const
Definition: BV_OBBTree.h:118