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