HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
BV_KDOPTree.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_KDOPTree_h__
9 #define __BV_KDOPTree_h__
10 
11 #include "BV_API.h"
12 #include "BV_Tree.h"
13 #include <iosfwd>
14 
15 class UT_IStream;
16 
17 template <class T>
18 class UT_Array;
19 
20 /// A single node of a BV_KDOPTree
21 template <int K>
23 {
24 public:
25  BV_KDOPNode(int leafId = -1);
26  BV_KDOPNode(const BV_KDOPNode &rhs);
27  ~BV_KDOPNode();
28 
29  bool isLeaf() const
30  {
31  UT_ASSERT_P((NULL == myLeft && NULL == myRight && myLeafId >= 0) ||
32  (NULL != myLeft && NULL != myRight && myLeafId < 0));
33  return myLeafId >= 0;
34  }
35 
36  bool overlaps(const BV_KDOPNode &rhs, fpreal tol) const;
37 
38  void save(std::ostream &os, bool onlyStructure) const;
39  static BV_KDOPNode
40  *load(UT_IStream &is, bool onlyStructure);
41 
42  int64 getMemoryUsage() const;
43 
44  // TODO: we need a way to disable.
45 
46  /// Minimum/maximum extent in each of the K/2 directions.
47  fpreal myExtents[K];
48 
49  int myLeafId;
50  BV_KDOPNode *myLeft, *myRight;
51 
52 private:
53  /// Disallowed.
54  BV_KDOPNode &operator=(const BV_KDOPNode &);
55 };
56 
57 /// Bounding Volume Tree using k-Discrete Oriented Polytopes.
58 ///
59 /// Build: O(n^2)
60 /// Update extents: O(n log n)
61 ///
62 /// Defined for:
63 /// k=6 (axis aligned bounding box)
64 /// k=14 (AABB with cut corners)
65 /// k=18 (AABB with cut edges)
66 /// k=26 (AABB with cut corners and edges).
67 ///
68 /// Source:
69 /// Klosowski, Held, Mitchell, Sowizral and Zikan, "Efficient Collision
70 /// Detection Using Bounding Volume Hierarchies of k-DOPs," IEEE Transactions
71 /// on Visualization and Computer Graphics 4(1):21-36, 1998.
72 /// ftp://ams.sunysb.edu/pub/geometry/cd-tvcg-97.ps.gz
73 template <int K>
74 class BV_API BV_KDOPTree : public BV_Tree
75 {
76 public:
77  typedef BV_Tree BaseClass;
78 
79  BV_KDOPTree();
80  BV_KDOPTree(const BV_KDOPTree &);
81  virtual ~BV_KDOPTree();
82 
83  BV_KDOPTree &operator=(const BV_KDOPTree &);
84 
85  virtual const char *getType() const;
86  virtual const BV_Tree
87  *castTo(const char *type) const;
88  virtual BV_Tree *castTo(const char *type);
89 
90  /// This defines the number of "slabs" used to define the polytope.
91  static int getNumSlabs()
92  { return K/2; }
93  /// Retrieve the orientation of the k-th slab.
94  const UT_Vector3 &getPlaneDir(int k) const
95  {
96  UT_ASSERT_P(k < K/2);
97  return myPlaneDirs[k];
98  }
99 
100 protected:
101  class bvLeaf
102  {
103  public:
104  // Default copy constructor is fine.
105  // Default assignment operator is fine.
106 
107  // Sort key *must* be first member of this class.
108  float mySortKey;
109  int myLeafId;
111  };
112 
113  virtual BV_Tree *cloneSubclass() const;
114  virtual int64 getMemoryUsageSubclass() const;
115  virtual int getNumLeavesSubclass() const;
116  virtual void saveSubclass(std::ostream &os, bool onlyStructure) const;
117  virtual bool loadSubclass(UT_IStream &is, bool onlyStructure);
118 
119  virtual void buildSubclass(BV_LeafIterator &leafIt);
120  virtual void updateExtentsSubclass(BV_LeafIterator &leafIt);
121  virtual BV_Status intersectSubclass(BV_Callback &callback,
122  const BV_Tree &treeb,
123  const UT_DMatrix4 &startxforma,
124  const UT_DMatrix4 &startxformb,
125  const UT_DMatrix4 &endxforma,
126  const UT_DMatrix4 &endxformb,
127  fpreal tol) const;
128  static bool intersectRecurse(BV_Callback &callback,
129  const BV_KDOPNode<K> &nodea,
130  const BV_KDOPNode<K> &nodeb,
131  fpreal tol);
132 
133  static BV_KDOPNode<K>*buildRecurse(UT_Array<bvLeaf> &leafData,
134  int startLeaf, int numLeaves);
135  static void updateExtentsRecurse(BV_LeafIterator &leafIt,
136  BV_KDOPNode<K> &node);
137 
138  static const UT_Vector3 myPlaneDirs[K/2];
139 
140 protected:
141  const BV_KDOPNode<K>*getRoot() const
142  { return myRoot; }
143 
144 private:
145  BV_KDOPNode<K> *myRoot;
146 };
147 
152 
153 #endif
virtual void saveSubclass(std::ostream &os, bool onlyStructure) const =0
virtual bool loadSubclass(UT_IStream &is, bool onlyStructure)=0
BV_KDOPTree< 18 > BV_18DOPTree
Definition: BV_KDOPTree.h:150
const BV_KDOPNode< K > * getRoot() const
Definition: BV_KDOPTree.h:141
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
virtual void updateExtentsSubclass(BV_LeafIterator &leafIt)=0
BV_Tree BaseClass
Definition: BV_KDOPTree.h:77
virtual int64 getMemoryUsageSubclass() const =0
long long int64
Definition: SYS_Types.h:107
Callback for bounding volume hierarchy intersection operation.
Definition: BV_Callback.h:17
static int getNumSlabs()
This defines the number of "slabs" used to define the polytope.
Definition: BV_KDOPTree.h:91
bool isLeaf() const
Definition: BV_KDOPTree.h:29
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:125
BV_KDOPTree< 6 > BV_AABBTree
Definition: BV_KDOPTree.h:148
BV_KDOPNode * myRight
Definition: BV_KDOPTree.h:50
BV_Status
Definition: BV_Tree.h:27
double fpreal
Definition: SYS_Types.h:270
virtual BV_Tree * cloneSubclass() const =0
virtual const BV_Tree * castTo(const char *type) const
#define BV_API
Definition: BV_API.h:10
BV_KDOPTree< 14 > BV_14DOPTree
Definition: BV_KDOPTree.h:149
A single node of a BV_KDOPTree.
Definition: BV_KDOPTree.h:22
GLint GLint GLsizei GLint GLenum GLenum type
Definition: glcorearb.h:107
UT_Vector3 myBarycenter
Definition: BV_KDOPTree.h:110
const UT_Vector3 & getPlaneDir(int k) const
Retrieve the orientation of the k-th slab.
Definition: BV_KDOPTree.h:94
virtual const char * getType() const =0
BV_KDOPTree< 26 > BV_26DOPTree
Definition: BV_KDOPTree.h:151
virtual int getNumLeavesSubclass() const =0
virtual void buildSubclass(BV_LeafIterator &leafIt)=0