Correct own error in recent BVH nearest ray
[blender.git] / extern / bullet2 / src / BulletCollision / CollisionDispatch / btHashedSimplePairCache.h
1 /*
2 Bullet Continuous Collision Detection and Physics Library
3 Copyright (c) 2003-2006 Erwin Coumans  http://continuousphysics.com/Bullet/
4
5 This software is provided 'as-is', without any express or implied warranty.
6 In no event will the authors be held liable for any damages arising from the use of this software.
7 Permission is granted to anyone to use this software for any purpose, 
8 including commercial applications, and to alter it and redistribute it freely, 
9 subject to the following restrictions:
10
11 1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
12 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
13 3. This notice may not be removed or altered from any source distribution.
14 */
15
16 #ifndef BT_HASHED_SIMPLE_PAIR_CACHE_H
17 #define BT_HASHED_SIMPLE_PAIR_CACHE_H
18
19
20
21 #include "LinearMath/btAlignedObjectArray.h"
22
23 const int BT_SIMPLE_NULL_PAIR=0xffffffff;
24
25 struct btSimplePair
26 {
27         btSimplePair(int indexA,int indexB)
28                 :m_indexA(indexA),
29                 m_indexB(indexB),
30                 m_userPointer(0)
31         {
32         }
33
34         int m_indexA;
35         int m_indexB;
36         union
37         {
38                 void*   m_userPointer;
39                 int             m_userValue;
40         };
41 };
42
43 typedef btAlignedObjectArray<btSimplePair>      btSimplePairArray;
44
45
46
47 extern int gOverlappingSimplePairs;
48 extern int gRemoveSimplePairs;
49 extern int gAddedSimplePairs;
50 extern int gFindSimplePairs;
51
52
53
54
55 class btHashedSimplePairCache
56 {
57         btSimplePairArray       m_overlappingPairArray;
58         
59         bool            m_blockedForChanges;
60         
61
62 protected:
63         
64         btAlignedObjectArray<int>       m_hashTable;
65         btAlignedObjectArray<int>       m_next;
66         
67
68 public:
69         btHashedSimplePairCache();
70         virtual ~btHashedSimplePairCache();
71         
72         void removeAllPairs();
73
74         virtual void*   removeOverlappingPair(int indexA,int indexB);
75         
76         // Add a pair and return the new pair. If the pair already exists,
77         // no new pair is created and the old one is returned.
78         virtual btSimplePair*   addOverlappingPair(int indexA,int indexB)
79         {
80                 gAddedSimplePairs++;
81
82                 return internalAddPair(indexA,indexB);
83         }
84
85         
86         virtual btSimplePair*   getOverlappingPairArrayPtr()
87         {
88                 return &m_overlappingPairArray[0];
89         }
90
91         const btSimplePair*     getOverlappingPairArrayPtr() const
92         {
93                 return &m_overlappingPairArray[0];
94         }
95
96         btSimplePairArray&      getOverlappingPairArray()
97         {
98                 return m_overlappingPairArray;
99         }
100
101         const btSimplePairArray&        getOverlappingPairArray() const
102         {
103                 return m_overlappingPairArray;
104         }
105
106         
107         btSimplePair* findPair(int indexA,int indexB);
108
109         int GetCount() const { return m_overlappingPairArray.size(); }
110
111         int     getNumOverlappingPairs() const
112         {
113                 return m_overlappingPairArray.size();
114         }
115 private:
116         
117         btSimplePair*   internalAddPair(int indexA, int indexB);
118
119         void    growTables();
120
121         SIMD_FORCE_INLINE bool equalsPair(const btSimplePair& pair, int indexA, int indexB)
122         {       
123                 return pair.m_indexA == indexA && pair.m_indexB == indexB;
124         }
125
126         
127         
128         SIMD_FORCE_INLINE       unsigned int getHash(unsigned int indexA, unsigned int indexB)
129         {
130                 int key = static_cast<int>(((unsigned int)indexA) | (((unsigned int)indexB) <<16));
131                 // Thomas Wang's hash
132
133                 key += ~(key << 15);
134                 key ^=  (key >> 10);
135                 key +=  (key << 3);
136                 key ^=  (key >> 6);
137                 key += ~(key << 11);
138                 key ^=  (key >> 16);
139                 return static_cast<unsigned int>(key);
140         }
141         
142
143
144
145
146         SIMD_FORCE_INLINE btSimplePair* internalFindPair(int proxyIdA , int proxyIdB, int hash)
147         {
148                 
149                 int index = m_hashTable[hash];
150                 
151                 while( index != BT_SIMPLE_NULL_PAIR && equalsPair(m_overlappingPairArray[index], proxyIdA, proxyIdB) == false)
152                 {
153                         index = m_next[index];
154                 }
155
156                 if ( index == BT_SIMPLE_NULL_PAIR )
157                 {
158                         return NULL;
159                 }
160
161                 btAssert(index < m_overlappingPairArray.size());
162
163                 return &m_overlappingPairArray[index];
164         }
165
166         
167 };
168
169
170
171
172 #endif //BT_HASHED_SIMPLE_PAIR_CACHE_H
173
174