1//
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions
4// are met:
5// * Redistributions of source code must retain the above copyright
6// notice, this list of conditions and the following disclaimer.
7// * Redistributions in binary form must reproduce the above copyright
8// notice, this list of conditions and the following disclaimer in the
9// documentation and/or other materials provided with the distribution.
10// * Neither the name of NVIDIA CORPORATION nor the names of its
11// contributors may be used to endorse or promote products derived
12// from this software without specific prior written permission.
13//
14// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ''AS IS'' AND ANY
15// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
18// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22// OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25//
26// Copyright (c) 2008-2021 NVIDIA Corporation. All rights reserved.
27// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
28// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
29
30
31#ifndef PXD_THRESHOLDTABLE_H
32#define PXD_THRESHOLDTABLE_H
33#include "Ps.h"
34#include "PsArray.h"
35#include "CmPhysXCommon.h"
36#include "PsAllocator.h"
37#include "PsHash.h"
38#include "foundation/PxMemory.h"
39#include "PxsIslandNodeIndex.h"
40
41namespace physx
42{
43
44class PxsRigidBody;
45
46namespace Sc
47{
48 class ShapeInteraction;
49}
50
51namespace Dy
52{
53
54struct ThresholdStreamElement
55{
56 Sc::ShapeInteraction* shapeInteraction; //4 8
57 PxReal normalForce; //8 12
58 PxReal threshold; //12 16
59 IG::NodeIndex nodeIndexA; //this is the unique node index in island gen which corresonding to that body and it is persistent 16 20
60 IG::NodeIndex nodeIndexB; //This is the unique node index in island gen which corresonding to that body and it is persistent 20 24
61 PxReal accumulatedForce; //24 28
62 PxU32 pad; //28 32
63
64#if !PX_P64_FAMILY
65 PxU32 pad1; //32
66#endif // !PX_X64
67
68 PX_CUDA_CALLABLE bool operator <= (const ThresholdStreamElement& otherPair) const
69 {
70 return ((nodeIndexA < otherPair.nodeIndexA) ||(nodeIndexA == otherPair.nodeIndexA && nodeIndexB <= otherPair.nodeIndexB));
71 }
72
73};
74
75typedef Ps::Array<ThresholdStreamElement, Ps::VirtualAllocator> ThresholdArray;
76
77class ThresholdStream : public ThresholdArray
78{
79public:
80 ThresholdStream(Ps::VirtualAllocatorCallback& allocatorCallback) : ThresholdArray(Ps::VirtualAllocator(&allocatorCallback))
81 {
82 }
83
84};
85
86class ThresholdTable
87{
88public:
89
90 ThresholdTable()
91 : mBuffer(NULL),
92 mHash(NULL),
93 mHashSize(0),
94 mHashCapactiy(0),
95 mPairs(NULL),
96 mNexts(NULL),
97 mPairsSize(0),
98 mPairsCapacity(0)
99 {
100 }
101
102 ~ThresholdTable()
103 {
104 if(mBuffer) PX_FREE(mBuffer);
105 }
106
107 void build(const ThresholdStream& stream);
108
109 bool check(const ThresholdStream& stream, const PxU32 nodexIndexA, const PxU32 nodexIndexB, PxReal dt);
110
111 bool check(const ThresholdStream& stream, const ThresholdStreamElement& elem, PxU32& thresholdIndex);
112
113//private:
114
115 static const PxU32 NO_INDEX = 0xffffffff;
116
117 struct Pair
118 {
119 PxU32 thresholdStreamIndex;
120 PxReal accumulatedForce;
121 //PxU32 next; // hash key & next ptr
122 };
123
124 PxU8* mBuffer;
125
126 PxU32* mHash;
127 PxU32 mHashSize;
128 PxU32 mHashCapactiy;
129
130 Pair* mPairs;
131 PxU32* mNexts;
132 PxU32 mPairsSize;
133 PxU32 mPairsCapacity;
134};
135
136namespace
137{
138 static PX_FORCE_INLINE PxU32 computeHashKey(const PxU32 nodeIndexA, const PxU32 nodeIndexB, const PxU32 hashCapacity)
139 {
140 return (Ps::hash(key: PxU64(nodeIndexA)<<32 | PxU64(nodeIndexB)) % hashCapacity);
141 }
142}
143
144inline bool ThresholdTable::check(const ThresholdStream& stream, const ThresholdStreamElement& elem, PxU32& thresholdIndex)
145{
146 PxU32* PX_RESTRICT hashes = mHash;
147 PxU32* PX_RESTRICT nextIndices = mNexts;
148 Pair* PX_RESTRICT pairs = mPairs;
149
150 PX_ASSERT(elem.nodeIndexA < elem.nodeIndexB);
151 PxU32 hashKey = computeHashKey(nodeIndexA: elem.nodeIndexA.index(), nodeIndexB: elem.nodeIndexB.index(), hashCapacity: mHashSize);
152
153 PxU32 pairIndex = hashes[hashKey];
154
155 while(NO_INDEX != pairIndex)
156 {
157 Pair& pair = pairs[pairIndex];
158 const PxU32 thresholdStreamIndex = pair.thresholdStreamIndex;
159 PX_ASSERT(thresholdStreamIndex < stream.size());
160 const ThresholdStreamElement& otherElement = stream[thresholdStreamIndex];
161 if(otherElement.nodeIndexA==elem.nodeIndexA && otherElement.nodeIndexB==elem.nodeIndexB && otherElement.shapeInteraction == elem.shapeInteraction)
162 {
163 thresholdIndex = thresholdStreamIndex;
164 return true;
165 }
166 pairIndex = nextIndices[pairIndex];
167 }
168
169 thresholdIndex = NO_INDEX;
170 return false;
171}
172
173
174inline void ThresholdTable::build(const ThresholdStream& stream)
175{
176 //Handle the case of an empty stream.
177 if(0==stream.size())
178 {
179 mPairsSize=0;
180 mPairsCapacity=0;
181 mHashSize=0;
182 mHashCapactiy=0;
183 if(mBuffer) PX_FREE(mBuffer);
184 mBuffer = NULL;
185 return;
186 }
187
188 //Realloc/resize if necessary.
189 const PxU32 pairsCapacity = stream.size();
190 const PxU32 hashCapacity = pairsCapacity*2+1;
191 if((pairsCapacity > mPairsCapacity) || (pairsCapacity < (mPairsCapacity >> 2)))
192 {
193 if(mBuffer) PX_FREE(mBuffer);
194 const PxU32 pairsByteSize = sizeof(Pair)*pairsCapacity;
195 const PxU32 nextsByteSize = sizeof(PxU32)*pairsCapacity;
196 const PxU32 hashByteSize = sizeof(PxU32)*hashCapacity;
197 const PxU32 totalByteSize = pairsByteSize + nextsByteSize + hashByteSize;
198 mBuffer = reinterpret_cast<PxU8*>(PX_ALLOC(totalByteSize, "PxThresholdStream"));
199
200 PxU32 offset = 0;
201 mPairs = reinterpret_cast<Pair*>(mBuffer + offset);
202 offset += pairsByteSize;
203 mNexts = reinterpret_cast<PxU32*>(mBuffer + offset);
204 offset += nextsByteSize;
205 mHash = reinterpret_cast<PxU32*>(mBuffer + offset);
206 offset += hashByteSize;
207 PX_ASSERT(totalByteSize == offset);
208
209 mPairsCapacity = pairsCapacity;
210 mHashCapactiy = hashCapacity;
211 }
212
213
214 //Set each entry of the hash table to 0xffffffff
215 PxMemSet(dest: mHash, c: 0xff, count: sizeof(PxU32)*hashCapacity);
216
217 //Init the sizes of the pairs array and hash array.
218 mPairsSize = 0;
219 mHashSize = hashCapacity;
220
221 PxU32* PX_RESTRICT hashes = mHash;
222 PxU32* PX_RESTRICT nextIndices = mNexts;
223 Pair* PX_RESTRICT pairs = mPairs;
224
225 //Add all the pairs from the stream.
226 PxU32 pairsSize = 0;
227 for(PxU32 i = 0; i < pairsCapacity; i++)
228 {
229 const ThresholdStreamElement& element = stream[i];
230 const IG::NodeIndex nodeIndexA = element.nodeIndexA;
231 const IG::NodeIndex nodeIndexB = element.nodeIndexB;
232
233 const PxF32 force = element.normalForce;
234
235 PX_ASSERT(nodeIndexA < nodeIndexB);
236
237 const PxU32 hashKey = computeHashKey(nodeIndexA: nodeIndexA.index(), nodeIndexB: nodeIndexB.index(), hashCapacity);
238
239 //Get the index of the first pair found that resulted in a hash that matched hashKey.
240 PxU32 prevPairIndex = hashKey;
241 PxU32 pairIndex = hashes[hashKey];
242
243 //Search through all pairs found that resulted in a hash that matched hashKey.
244 //Search until the exact same body pair is found.
245 //Increment the accumulated force if the exact same body pair is found.
246 while(NO_INDEX != pairIndex)
247 {
248 Pair& pair = pairs[pairIndex];
249 const PxU32 thresholdStreamIndex = pair.thresholdStreamIndex;
250 PX_ASSERT(thresholdStreamIndex < stream.size());
251 const ThresholdStreamElement& otherElement = stream[thresholdStreamIndex];
252 if(nodeIndexA == otherElement.nodeIndexA && nodeIndexB==otherElement.nodeIndexB)
253 {
254 pair.accumulatedForce += force;
255 prevPairIndex = NO_INDEX;
256 pairIndex = NO_INDEX;
257 break;
258 }
259 prevPairIndex = pairIndex;
260 pairIndex = nextIndices[pairIndex];
261 }
262
263 if(NO_INDEX != prevPairIndex)
264 {
265 nextIndices[pairsSize] = hashes[hashKey];
266 hashes[hashKey] = pairsSize;
267 Pair& newPair = pairs[pairsSize];
268 newPair.thresholdStreamIndex = i;
269 newPair.accumulatedForce = force;
270 pairsSize++;
271 }
272 }
273 mPairsSize = pairsSize;
274}
275
276}
277
278}
279
280#endif //DY_THRESHOLDTABLE_H
281

source code of qtquick3dphysics/src/3rdparty/PhysX/source/lowleveldynamics/include/DyThresholdTable.h