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(void);
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
78  UT_Vector3 getAveragePoint(void) const;
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
99  const BV_CHEdgeInfo* edgeTraversalBegin(void);
100  const BV_CHEdgeInfo* edgeTraversalNext(void);
101 
102  /// Checks for valid edge counts. Debug.
103  void edgeSanityCheck(void);
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(void);
108 
109  /// Resets the manager for the next iteration.
110  void reset(void);
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(void) 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(void) const;
175 
176  /// Clears all points associated with this triangle.
177  void clearAssocPoints(void);
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(void);
188 
189  bool getIsDeleted(void) 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  virtual ~BV_OBBTree();
274 
275  BV_OBBTree &operator=(const BV_OBBTree &);
276 
277  virtual const char *getType() const;
278  virtual const BV_Tree
279  *castTo(const char *type) const;
280  virtual BV_Tree *castTo(const char *type);
281 
282  /// Alternative lazy building: sections of the tree are only built when a
283  /// query needs them. In this case, the leaf iterator *must* not be
284  /// destroyed until the tree is destroyed, or until a fresh call to
285  /// buildLazy.
287  {
288  buildInternal(leafIt, true);
289  }
290 
291  void getRootOBB(UT_Matrix4 &xform, UT_Vector3 &radii) const;
292 
293  /// If true, a somewhat different version of the algorithm is used to compute
294  /// OBBs around nodes, which uses a convex hull around the points instead of
295  /// the points themselves. While slower, it results in a consistent bbox
296  /// that is not influenced by the density/inner points on the mesh. False by default.
297  void setUseConvexHull(bool bValue);
298  bool getUseConvexHull(void);
299 
300 protected:
301  class bvLeaf
302  {
303  public:
304  // Default copy constructor is fine.
305  // Default assignment operator is fine.
306 
307  // Sort key *must* be first member of this class.
308  float sortkey;
309  int leafId;
311  };
312 
313  virtual BV_Tree *cloneSubclass() const;
314  virtual int64 getMemoryUsageSubclass() const;
315  virtual int getNumLeavesSubclass() const;
316  /// Saving and loading only works for non-lazy building.
317  // @{
318  virtual void saveSubclass(std::ostream &os, bool onlyStructure) const;
319  virtual bool loadSubclass(UT_IStream &is, bool onlyStructure);
320  // @}
321 
322  virtual void buildSubclass(BV_LeafIterator &leafIt)
323  {
324  buildInternal(leafIt, false);
325  }
326  virtual void updateExtentsSubclass(BV_LeafIterator &leafIt);
327  /// WARNING: not thread-safe if tree was lazily built!
328  virtual BV_Status intersectSubclass(BV_Callback &callback,
329  const BV_Tree &treeb,
330  const UT_DMatrix4 &startxforma,
331  const UT_DMatrix4 &startxformb,
332  const UT_DMatrix4 &endxforma,
333  const UT_DMatrix4 &endxformb,
334  fpreal tol) const;
335 
337  {
338  return myRoot;
339  }
340  void buildInternal(BV_LeafIterator &leafIt, bool lazy);
341  /// Build the tree. If depth is non-negative, the algorithm is lazy and
342  /// stops after depth levels.
343  BV_OBB *createTree(int startprim, int numleaves,
344  const UT_Matrix3 &rootBasis,
345  const UT_Vector3 &rootPos, int depth = -1);
346  void createChildren(BV_OBB &root, int depth = -1);
347  bool updateExtentsRecurse(BV_OBB &node,
348  const UT_Matrix3 &parentBasis,
349  const UT_Vector3 &parentPos);
350 
351  void getBounds(const UT_Matrix3 &basis,
352  UT_BoundingBox &bbox, bool &firstPrim);
353  /// Calculate the OBB associated with the given node. Stores
354  /// orientation in node->myRot, and calls calcSize to calculate the
355  /// extents. May disable the node if it contains no enabled leaves.
356  void calcOBB(BV_OBB &node);
357  /// Given the input OBB orientation, calculate the OBB extents.
358  /// Stores extents (radii) and position in node.
359  void calcSize(BV_OBB &node);
360 
361  /// Compute a convex hull around the points provided, output result as a series of triangles
362  /// to the array provided. This is currently slower than it should be. Also, note that
363  /// if coplanar points are present, the convex hull constructed might be around jiggled versions
364  /// of those points.
365  bool computeConvexHull(const TPointArray& source_points_in, TSimpleTriangleArray& final_triangles_out);
366  bool doConvexHullIteration(BV_CHDataManager& data_manager, TTriArray& working_triangles);
367 
368  bool intersectRecurse(BV_Callback &callback,
369  const BV_OBBTree &treeb,
370  const BV_OBB &a, const BV_OBB &b,
371  const bvTransform &t1, const bvTransform &t2,
372  const bvTransform &t3, const bvTransform &t4,
373  fpreal tol, int identities) const;
374 
375 
376  static int compareLeaves(const void *t1, const void *t2);
377 
378  void calculateSortKeys(bvLeaf *prims, int numleaves,
379  UT_Matrix3 &basis, int axis) const;
380 
384 
386 };
387 
388 /// Extra data for a lazily constructed BV_OBB node.
390 {
391 public:
394 };
395 
396 
398 {
399  /// relative rotation
401  /// relative translation
403  /// relative transformation
404  UT_DMatrix4 xform[2];
405  /// create a new bvTransform that has updated relative rotation/translation
406  /// for the left tree (tree a)
407  void updateL(const UT_Matrix3 &rot,
408  const UT_Vector3 &trans,
409  bvTransform &xform) const;
410  /// same as updateL, except for the right tree (tree b)
411  void updateR(const UT_Matrix3 &rot,
412  const UT_Vector3 &trans,
413  bvTransform &xform) const;
414  /// update myself given (xforma, xformc) and (xformb, xformb) with
415  /// left tree (ra, ta) and right tree (rb, tb)
416  void update(const UT_Matrix3 &ra,
417  const UT_Matrix3 &rb,
418  const UT_Vector3 &ta,
419  const UT_Vector3 &tb,
420  const UT_DMatrix4 &xforma,
421  const UT_DMatrix4 &xformb,
422  const UT_DMatrix4 &xformc,
423  const UT_DMatrix4 &xformd);
424 };
425 
426 
427 #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
void clearAssocPoints(void)
Clears all points associated with this triangle.
UT_Vector3 myTrans
Center, relative to parent.
Definition: BV_OBBTree.h:232
png_voidp s1
Definition: png.h:2193
UT_Vector3 myVertices[3]
Definition: BV_OBBTree.h:43
UT_Vector3 myRadii
Radii in each axis (half of the dimension)
Definition: BV_OBBTree.h:235
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:189
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:241
TPointArray & getPoints(void)
Definition: BV_OBBTree.h:116
UT_Vector3 barycenter
Definition: BV_OBBTree.h:310
void getNormal(UT_Vector3 &normal)
Gets triangle normal. Cached.
UT_Matrix3 R
relative rotation
Definition: BV_OBBTree.h:400
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
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:107
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)
GLint GLint GLsizei GLsizei GLsizei depth
Definition: glcorearb.h:475
Extra data for a lazily constructed BV_OBB node.
Definition: BV_OBBTree.h:389
UT_Vector3 getAveragePoint(void) const
Returns an average point position accumulated so far.
UT_LinkListT< BV_CHTriangle * > TTriArray
Definition: BV_OBBTree.h:37
void addPoint(const UT_Vector3 point_in)
Accumulated the point position.
void printAssocPoints(void)
void buildLazy(BV_LeafIterator &leafIt)
Definition: BV_OBBTree.h:286
BV_OBB_Extra * myExtra
Definition: BV_OBBTree.h:247
UT_Matrix3 rot
Definition: BV_OBBTree.h:392
UT_Array< BV_CHSimpleTriangle > TSimpleTriangleArray
Definition: BV_OBBTree.h:45
bool myUseConvexHullForBBoxes
Definition: BV_OBBTree.h:385
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:382
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:383
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:40
void * myUserData
Definition: BV_OBBTree.h:249
UT_Array< int > TPointIndexArray
Definition: BV_OBBTree.h:35
UT_Matrix3 myRot
Orientation of the bounding box, relative to parent.
Definition: BV_OBBTree.h:230
double fpreal
Definition: SYS_Types.h:270
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:36
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: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:381
GLint GLint GLsizei GLint GLenum GLenum type
Definition: glcorearb.h:107
UT_Vector3 T
relative translation
Definition: BV_OBBTree.h:402
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:393
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
bool getDoRestart(void) const
Definition: BV_OBBTree.h:118
virtual void buildSubclass(BV_LeafIterator &leafIt)
Definition: BV_OBBTree.h:322
virtual int getNumLeavesSubclass() const =0
BV_OBB * getRoot()
Definition: BV_OBBTree.h:336