aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/libraries/ode-0.9/OPCODE/OPC_AABBTree.h
diff options
context:
space:
mode:
authordan miller2007-10-19 05:20:48 +0000
committerdan miller2007-10-19 05:20:48 +0000
commitd48ea5bb797037069d641da41da0f195f0124491 (patch)
tree40ff433d94859d629aac933d5ec73b382f62ba1a /libraries/ode-0.9/OPCODE/OPC_AABBTree.h
parentdont ask (diff)
downloadopensim-SC-d48ea5bb797037069d641da41da0f195f0124491.zip
opensim-SC-d48ea5bb797037069d641da41da0f195f0124491.tar.gz
opensim-SC-d48ea5bb797037069d641da41da0f195f0124491.tar.bz2
opensim-SC-d48ea5bb797037069d641da41da0f195f0124491.tar.xz
one more for the gipper
Diffstat (limited to 'libraries/ode-0.9/OPCODE/OPC_AABBTree.h')
-rw-r--r--libraries/ode-0.9/OPCODE/OPC_AABBTree.h137
1 files changed, 137 insertions, 0 deletions
diff --git a/libraries/ode-0.9/OPCODE/OPC_AABBTree.h b/libraries/ode-0.9/OPCODE/OPC_AABBTree.h
new file mode 100644
index 0000000..ee2533d
--- /dev/null
+++ b/libraries/ode-0.9/OPCODE/OPC_AABBTree.h
@@ -0,0 +1,137 @@
1///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
2/*
3 * OPCODE - Optimized Collision Detection
4 * Copyright (C) 2001 Pierre Terdiman
5 * Homepage: http://www.codercorner.com/Opcode.htm
6 */
7///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
8
9///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
10/**
11 * Contains code for a versatile AABB tree.
12 * \file OPC_AABBTree.h
13 * \author Pierre Terdiman
14 * \date March, 20, 2001
15 */
16///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
17
18///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
19// Include Guard
20#ifndef __OPC_AABBTREE_H__
21#define __OPC_AABBTREE_H__
22
23#ifdef OPC_NO_NEG_VANILLA_TREE
24 //! TO BE DOCUMENTED
25 #define IMPLEMENT_TREE(base_class, volume) \
26 public: \
27 /* Constructor / Destructor */ \
28 base_class(); \
29 ~base_class(); \
30 /* Data access */ \
31 inline_ const volume* Get##volume() const { return &mBV; } \
32 /* Clear the last bit */ \
33 inline_ const base_class* GetPos() const { return (const base_class*)(mPos&~1); } \
34 inline_ const base_class* GetNeg() const { const base_class* P = GetPos(); return P ? P+1 : null;} \
35 \
36 /* We don't need to test both nodes since we can't have one without the other */ \
37 inline_ bool IsLeaf() const { return !GetPos(); } \
38 \
39 /* Stats */ \
40 inline_ udword GetNodeSize() const { return SIZEOFOBJECT; } \
41 protected: \
42 /* Tree-independent data */ \
43 /* Following data always belong to the BV-tree, regardless of what the tree actually contains.*/ \
44 /* Whatever happens we need the two children and the enclosing volume.*/ \
45 volume mBV; /* Global bounding-volume enclosing all the node-related primitives */ \
46 size_t mPos; /* "Positive" & "Negative" children */
47#else
48 //! TO BE DOCUMENTED
49 #define IMPLEMENT_TREE(base_class, volume) \
50 public: \
51 /* Constructor / Destructor */ \
52 base_class(); \
53 ~base_class(); \
54 /* Data access */ \
55 inline_ const volume* Get##volume() const { return &mBV; } \
56 /* Clear the last bit */ \
57 inline_ const base_class* GetPos() const { return (const base_class*)(mPos&~1); } \
58 inline_ const base_class* GetNeg() const { return (const base_class*)(mNeg&~1); } \
59 \
60/* inline_ bool IsLeaf() const { return (!GetPos() && !GetNeg()); } */ \
61 /* We don't need to test both nodes since we can't have one without the other */ \
62 inline_ bool IsLeaf() const { return !GetPos(); } \
63 \
64 /* Stats */ \
65 inline_ udword GetNodeSize() const { return SIZEOFOBJECT; } \
66 protected: \
67 /* Tree-independent data */ \
68 /* Following data always belong to the BV-tree, regardless of what the tree actually contains.*/ \
69 /* Whatever happens we need the two children and the enclosing volume.*/ \
70 volume mBV; /* Global bounding-volume enclosing all the node-related primitives */ \
71 size_t mPos; /* "Positive" child */ \
72 size_t mNeg; /* "Negative" child */
73#endif
74
75 typedef void (*CullingCallback) (udword nb_primitives, udword* node_primitives, BOOL need_clipping, void* user_data);
76
77 class OPCODE_API AABBTreeNode
78 {
79 IMPLEMENT_TREE(AABBTreeNode, AABB)
80 public:
81 // Data access
82 inline_ const udword* GetPrimitives() const { return mNodePrimitives; }
83 inline_ udword GetNbPrimitives() const { return mNbPrimitives; }
84
85 protected:
86 // Tree-dependent data
87 udword* mNodePrimitives; //!< Node-related primitives (shortcut to a position in mIndices below)
88 udword mNbPrimitives; //!< Number of primitives for this node
89 // Internal methods
90 udword Split(udword axis, AABBTreeBuilder* builder);
91 bool Subdivide(AABBTreeBuilder* builder);
92 void _BuildHierarchy(AABBTreeBuilder* builder);
93 void _Refit(AABBTreeBuilder* builder);
94 };
95
96 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
97 /**
98 * User-callback, called for each node by the walking code.
99 * \param current [in] current node
100 * \param depth [in] current node's depth
101 * \param user_data [in] user-defined data
102 * \return true to recurse through children, else false to bypass them
103 */
104 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
105 typedef bool (*WalkingCallback) (const AABBTreeNode* current, udword depth, void* user_data);
106
107 class OPCODE_API AABBTree : public AABBTreeNode
108 {
109 public:
110 // Constructor / Destructor
111 AABBTree();
112 ~AABBTree();
113 // Build
114 bool Build(AABBTreeBuilder* builder);
115 void Release();
116
117 // Data access
118 inline_ const udword* GetIndices() const { return mIndices; } //!< Catch the indices
119 inline_ udword GetNbNodes() const { return mTotalNbNodes; } //!< Catch the number of nodes
120
121 // Infos
122 bool IsComplete() const;
123 // Stats
124 udword ComputeDepth() const;
125 udword GetUsedBytes() const;
126 udword Walk(WalkingCallback callback, void* user_data) const;
127
128 bool Refit(AABBTreeBuilder* builder);
129 bool Refit2(AABBTreeBuilder* builder);
130 private:
131 udword* mIndices; //!< Indices in the app list. Indices are reorganized during build (permutation).
132 AABBTreeNode* mPool; //!< Linear pool of nodes for complete trees. Null otherwise. [Opcode 1.3]
133 // Stats
134 udword mTotalNbNodes; //!< Number of nodes in the tree.
135 };
136
137#endif // __OPC_AABBTREE_H__
generated by cgit v1.1 at 2024-12-25 22:51:16 +0000