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.
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  ~BV_KDOPTree() override;
82 
84 
85  const char *getType() const override;
86 
87  const BV_Tree
88  *castTo(const char *type) const override;
89  BV_Tree *castTo(const char *type) override;
90 
91  /// This defines the number of "slabs" used to define the polytope.
92  static int getNumSlabs()
93  { return K/2; }
94  /// Retrieve the orientation of the k-th slab.
95  static const UT_Vector3 &getPlaneDir(int k);
96 
97 protected:
98  class bvLeaf
99  {
100  public:
101  // Default copy constructor is fine.
102  // Default assignment operator is fine.
103 
104  // Sort key *must* be first member of this class.
105  float mySortKey;
106  int myLeafId;
108  };
109 
110  BV_Tree *cloneSubclass() const override;
111  int64 getMemoryUsageSubclass() const override;
112  int getNumLeavesSubclass() const override;
113  void saveSubclass(std::ostream &os, bool onlyStructure) const override;
114  bool loadSubclass(UT_IStream &is, bool onlyStructure) override;
115 
116  void buildSubclass(BV_LeafIterator &leafIt) override;
117  void updateExtentsSubclass(BV_LeafIterator &leafIt) override;
119  const BV_Tree &treeb,
120  const UT_DMatrix4 &startxforma,
121  const UT_DMatrix4 &startxformb,
122  const UT_DMatrix4 &endxforma,
123  const UT_DMatrix4 &endxformb,
124  fpreal tol) const override;
125  static bool intersectRecurse(BV_Callback &callback,
126  const BV_KDOPNode<K> &nodea,
127  const BV_KDOPNode<K> &nodeb,
128  fpreal tol);
129 
130  static BV_KDOPNode<K>*buildRecurse(UT_Array<bvLeaf> &leafData,
131  int startLeaf, int numLeaves);
132  static void updateExtentsRecurse(BV_LeafIterator &leafIt,
133  BV_KDOPNode<K> &node);
134 
135 protected:
136  const BV_KDOPNode<K>*getRoot() const
137  { return myRoot; }
138 
139 private:
140  const char *typeImpl() const;
141 
143 };
144 
149 
150 #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:147
const BV_KDOPNode< K > * getRoot() const
Definition: BV_KDOPTree.h:136
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
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:92
bool isLeaf() const
Definition: BV_KDOPTree.h:29
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:155
long long int64
Definition: SYS_Types.h:116
BV_KDOPTree< 6 > BV_AABBTree
Definition: BV_KDOPTree.h:145
BV_KDOPNode * myRight
Definition: BV_KDOPTree.h:50
BV_Status
Definition: BV_Tree.h:27
virtual BV_Tree * cloneSubclass() const =0
virtual const BV_Tree * castTo(const char *type) const
#define BV_API
Definition: BV_API.h:10
fpreal64 fpreal
Definition: SYS_Types.h:277
LeafData & operator=(const LeafData &)=delete
BV_KDOPTree< 14 > BV_14DOPTree
Definition: BV_KDOPTree.h:146
A single node of a BV_KDOPTree.
Definition: BV_KDOPTree.h:22
UT_Vector3 myBarycenter
Definition: BV_KDOPTree.h:107
type
Definition: core.h:1059
virtual const char * getType() const =0
BV_KDOPTree< 26 > BV_26DOPTree
Definition: BV_KDOPTree.h:148
virtual int getNumLeavesSubclass() const =0
myRoot
Definition: UT_RTreeImpl.h:716
virtual void buildSubclass(BV_LeafIterator &leafIt)=0