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#ifndef BP_BROADPHASE_UPDATE_H
31#define BP_BROADPHASE_UPDATE_H
32
33#include "foundation/PxAssert.h"
34#include "foundation/PxUnionCast.h"
35#include "CmPhysXCommon.h"
36#include "PxBroadPhase.h"
37#include "Ps.h"
38
39namespace physx
40{
41namespace Bp
42{
43typedef PxU32 ShapeHandle;
44typedef PxU32 BpHandle;
45#define BP_INVALID_BP_HANDLE 0x3fffffff
46
47#define ALIGN_SIZE_16(size) ((unsigned(size)+15)&(unsigned(~15)))
48
49#define BP_USE_AGGREGATE_GROUP_TAIL
50#define BP_FILTERING_USES_TYPE_IN_GROUP
51
52 /*
53 \brief AABBManager volumes with the same filter group value are guaranteed never to generate an overlap pair.
54 \note To ensure that static pairs never overlap, add static shapes with eSTATICS.
55 The value eDYNAMICS_BASE provides a minimum recommended group value for dynamic shapes.
56 If dynamics shapes are assigned group values greater than or equal to eDYNAMICS_BASE then
57 they are allowed to generate broadphase overlaps with statics, and other dynamic shapes provided
58 they have different group values.
59 @see AABBManager::createVolume
60 */
61 struct FilterGroup
62 {
63 enum Enum
64 {
65 eSTATICS = 0,
66 eDYNAMICS_BASE = 1,
67#ifdef BP_USE_AGGREGATE_GROUP_TAIL
68 eAGGREGATE_BASE = 0xfffffffe,
69#endif
70 eINVALID = 0xffffffff
71 };
72 };
73
74#ifdef BP_FILTERING_USES_TYPE_IN_GROUP
75 struct FilterType
76 {
77 enum Enum
78 {
79 STATIC = 0,
80 KINEMATIC = 1,
81 DYNAMIC = 2,
82 AGGREGATE = 3,
83
84 COUNT = 4
85 };
86 };
87#endif
88
89 PX_FORCE_INLINE Bp::FilterGroup::Enum getFilterGroup_Statics()
90 {
91 return Bp::FilterGroup::eSTATICS;
92 }
93
94 PX_FORCE_INLINE Bp::FilterGroup::Enum getFilterGroup_Dynamics(PxU32 rigidId, bool isKinematic)
95 {
96 const PxU32 group = rigidId + Bp::FilterGroup::eDYNAMICS_BASE;
97#ifdef BP_FILTERING_USES_TYPE_IN_GROUP
98 const PxU32 type = isKinematic ? FilterType::KINEMATIC : FilterType::DYNAMIC;
99 return Bp::FilterGroup::Enum((group<<2)|type);
100#else
101 PX_UNUSED(isKinematic);
102 return Bp::FilterGroup::Enum(group);
103#endif
104 }
105
106 PX_FORCE_INLINE Bp::FilterGroup::Enum getFilterGroup(bool isStatic, PxU32 rigidId, bool isKinematic)
107 {
108 return isStatic ? getFilterGroup_Statics() : getFilterGroup_Dynamics(rigidId, isKinematic);
109 }
110
111#ifdef BP_FILTERING_USES_TYPE_IN_GROUP
112 PX_FORCE_INLINE bool groupFiltering(const Bp::FilterGroup::Enum group0, const Bp::FilterGroup::Enum group1, const bool* PX_RESTRICT lut)
113 {
114/* const int g0 = group0 & ~3;
115 const int g1 = group1 & ~3;
116 if(g0==g1)
117 return false;*/
118 if(group0==group1)
119 {
120 PX_ASSERT((group0 & ~3)==(group1 & ~3));
121 return false;
122 }
123
124 const int type0 = group0 & 3;
125 const int type1 = group1 & 3;
126 return lut[type0*4+type1];
127 }
128#else
129 PX_FORCE_INLINE bool groupFiltering(const Bp::FilterGroup::Enum group0, const Bp::FilterGroup::Enum group1)
130 {
131 return group0!=group1;
132 }
133#endif
134
135 /*
136 \brief Encode a single float value with lossless encoding to integer
137 */
138 PX_FORCE_INLINE PxU32 encodeFloat(PxU32 ir)
139 {
140 //we may need to check on -0 and 0
141 //But it should make no practical difference.
142 if(ir & PX_SIGN_BITMASK) //negative?
143 return ~ir;//reverse sequence of negative numbers
144 else
145 return ir | PX_SIGN_BITMASK; // flip sign
146 }
147
148 /*
149 \brief Encode a single float value with lossless encoding to integer
150 */
151 PX_FORCE_INLINE PxU32 decodeFloat(PxU32 ir)
152 {
153 if(ir & PX_SIGN_BITMASK) //positive?
154 return ir & ~PX_SIGN_BITMASK; //flip sign
155 else
156 return ~ir; //undo reversal
157 }
158
159
160/**
161\brief Integer representation of PxBounds3 used by BroadPhase
162@see BroadPhaseUpdateData
163*/
164
165typedef PxU32 ValType;
166
167class IntegerAABB
168{
169public:
170
171 enum
172 {
173 MIN_X = 0,
174 MIN_Y,
175 MIN_Z,
176 MAX_X,
177 MAX_Y,
178 MAX_Z
179 };
180
181 IntegerAABB(const PxBounds3& b, PxReal contactDistance)
182 {
183 const PxVec3 dist(contactDistance);
184 encode(bounds: PxBounds3(b.minimum - dist, b.maximum + dist));
185 }
186
187 /*
188 \brief Return the minimum along a specified axis
189 \param[in] i is the axis
190 */
191 PX_FORCE_INLINE ValType getMin(PxU32 i) const { return (mMinMax)[MIN_X+i]; }
192
193 /*
194 \brief Return the maximum along a specified axis
195 \param[in] i is the axis
196 */
197 PX_FORCE_INLINE ValType getMax(PxU32 i) const { return (mMinMax)[MAX_X+i]; }
198
199 /*
200 \brief Return one of the six min/max values of the bound
201 \param[in] isMax determines whether a min or max value is returned
202 \param[in] index is the axis
203 */
204 PX_FORCE_INLINE ValType getExtent(PxU32 isMax, PxU32 index) const
205 {
206 PX_ASSERT(isMax<=1);
207 return (mMinMax)[3*isMax+index];
208 }
209
210 /*
211 \brief Return the minimum on the x axis
212 */
213 PX_FORCE_INLINE ValType getMinX() const { return mMinMax[MIN_X]; }
214
215 /*
216 \brief Return the minimum on the y axis
217 */
218 PX_FORCE_INLINE ValType getMinY() const { return mMinMax[MIN_Y]; }
219
220 /*
221 \brief Return the minimum on the z axis
222 */
223 PX_FORCE_INLINE ValType getMinZ() const { return mMinMax[MIN_Z]; }
224
225 /*
226 \brief Return the maximum on the x axis
227 */
228 PX_FORCE_INLINE ValType getMaxX() const { return mMinMax[MAX_X]; }
229
230 /*
231 \brief Return the maximum on the y axis
232 */
233 PX_FORCE_INLINE ValType getMaxY() const { return mMinMax[MAX_Y]; }
234
235 /*
236 \brief Return the maximum on the z axis
237 */
238 PX_FORCE_INLINE ValType getMaxZ() const { return mMinMax[MAX_Z]; }
239
240 /*
241 \brief Encode float bounds so they are stored as integer bounds
242 \param[in] bounds is the bounds to be encoded
243 \note The integer values of minima are always even, while the integer values of maxima are always odd
244 \note The encoding process masks off the last four bits for minima and masks on the last four bits for maxima.
245 This keeps the bounds constant when its shape is subjected to small global pose perturbations. In turn, this helps
246 reduce computational effort in the broadphase update by reducing the amount of sorting required on near-stationary
247 bodies that are aligned along one or more axis.
248 @see decode
249 */
250 PX_FORCE_INLINE void encode(const PxBounds3& bounds)
251 {
252 const PxU32* PX_RESTRICT min = PxUnionCast<const PxU32*, const PxF32*>(b: &bounds.minimum.x);
253 const PxU32* PX_RESTRICT max = PxUnionCast<const PxU32*, const PxF32*>(b: &bounds.maximum.x);
254 //Avoid min=max by enforcing the rule that mins are even and maxs are odd.
255 mMinMax[MIN_X] = encodeFloatMin(source: min[0]);
256 mMinMax[MIN_Y] = encodeFloatMin(source: min[1]);
257 mMinMax[MIN_Z] = encodeFloatMin(source: min[2]);
258 mMinMax[MAX_X] = encodeFloatMax(source: max[0]) | (1<<2);
259 mMinMax[MAX_Y] = encodeFloatMax(source: max[1]) | (1<<2);
260 mMinMax[MAX_Z] = encodeFloatMax(source: max[2]) | (1<<2);
261 }
262
263 /*
264 \brief Decode from integer bounds to float bounds
265 \param[out] bounds is the decoded float bounds
266 \note Encode followed by decode will produce a float bound larger than the original
267 due to the masking in encode.
268 @see encode
269 */
270 PX_FORCE_INLINE void decode(PxBounds3& bounds) const
271 {
272 PxU32* PX_RESTRICT min = PxUnionCast<PxU32*, PxF32*>(b: &bounds.minimum.x);
273 PxU32* PX_RESTRICT max = PxUnionCast<PxU32*, PxF32*>(b: &bounds.maximum.x);
274 min[0] = decodeFloat(ir: mMinMax[MIN_X]);
275 min[1] = decodeFloat(ir: mMinMax[MIN_Y]);
276 min[2] = decodeFloat(ir: mMinMax[MIN_Z]);
277 max[0] = decodeFloat(ir: mMinMax[MAX_X]);
278 max[1] = decodeFloat(ir: mMinMax[MAX_Y]);
279 max[2] = decodeFloat(ir: mMinMax[MAX_Z]);
280 }
281
282 /*
283 \brief Encode a single minimum value from integer bounds to float bounds
284 \note The encoding process masks off the last four bits for minima
285 @see encode
286 */
287 static PX_FORCE_INLINE ValType encodeFloatMin(PxU32 source)
288 {
289 return ((encodeFloat(ir: source) >> eGRID_SNAP_VAL) - 1) << eGRID_SNAP_VAL;
290 }
291
292 /*
293 \brief Encode a single maximum value from integer bounds to float bounds
294 \note The encoding process masks on the last four bits for maxima
295 @see encode
296 */
297 static PX_FORCE_INLINE ValType encodeFloatMax(PxU32 source)
298 {
299 return ((encodeFloat(ir: source) >> eGRID_SNAP_VAL) + 1) << eGRID_SNAP_VAL;
300 }
301
302 /*
303 \brief Shift the encoded bounds by a specified vector
304 \param[in] shift is the vector used to shift the bounds
305 */
306 PX_FORCE_INLINE void shift(const PxVec3& shift)
307 {
308 ::physx::PxBounds3 elemBounds;
309 decode(bounds&: elemBounds);
310 elemBounds.minimum -= shift;
311 elemBounds.maximum -= shift;
312 encode(bounds: elemBounds);
313 }
314
315 /*
316 \brief Test if this aabb lies entirely inside another aabb
317 \param[in] box is the other box
318 \return True if this aabb lies entirely inside box
319 */
320 PX_INLINE bool isInside(const IntegerAABB& box) const
321 {
322 if(box.mMinMax[MIN_X]>mMinMax[MIN_X]) return false;
323 if(box.mMinMax[MIN_Y]>mMinMax[MIN_Y]) return false;
324 if(box.mMinMax[MIN_Z]>mMinMax[MIN_Z]) return false;
325 if(box.mMinMax[MAX_X]<mMinMax[MAX_X]) return false;
326 if(box.mMinMax[MAX_Y]<mMinMax[MAX_Y]) return false;
327 if(box.mMinMax[MAX_Z]<mMinMax[MAX_Z]) return false;
328 return true;
329 }
330
331 /*
332 \brief Test if this aabb and another intersect
333 \param[in] b is the other box
334 \return True if this aabb and b intersect
335 */
336 PX_FORCE_INLINE bool intersects(const IntegerAABB& b) const
337 {
338 return !(b.mMinMax[MIN_X] > mMinMax[MAX_X] || mMinMax[MIN_X] > b.mMinMax[MAX_X] ||
339 b.mMinMax[MIN_Y] > mMinMax[MAX_Y] || mMinMax[MIN_Y] > b.mMinMax[MAX_Y] ||
340 b.mMinMax[MIN_Z] > mMinMax[MAX_Z] || mMinMax[MIN_Z] > b.mMinMax[MAX_Z]);
341 }
342
343 PX_FORCE_INLINE bool intersects1D(const IntegerAABB& b, const PxU32 axis) const
344 {
345 const PxU32 maxAxis = axis + 3;
346 return !(b.mMinMax[axis] > mMinMax[maxAxis] || mMinMax[axis] > b.mMinMax[maxAxis]);
347 }
348
349
350 /*
351 \brief Expand bounds to include another
352 \note This is used to compute the aggregate bounds of multiple shape bounds
353 \param[in] b is the bounds to be included
354 */
355 PX_FORCE_INLINE void include(const IntegerAABB& b)
356 {
357 mMinMax[MIN_X] = PxMin(a: mMinMax[MIN_X], b: b.mMinMax[MIN_X]);
358 mMinMax[MIN_Y] = PxMin(a: mMinMax[MIN_Y], b: b.mMinMax[MIN_Y]);
359 mMinMax[MIN_Z] = PxMin(a: mMinMax[MIN_Z], b: b.mMinMax[MIN_Z]);
360 mMinMax[MAX_X] = PxMax(a: mMinMax[MAX_X], b: b.mMinMax[MAX_X]);
361 mMinMax[MAX_Y] = PxMax(a: mMinMax[MAX_Y], b: b.mMinMax[MAX_Y]);
362 mMinMax[MAX_Z] = PxMax(a: mMinMax[MAX_Z], b: b.mMinMax[MAX_Z]);
363 }
364
365 /*
366 \brief Set the bounds to (max, max, max), (min, min, min)
367 */
368 PX_INLINE void setEmpty()
369 {
370 mMinMax[MIN_X] = mMinMax[MIN_Y] = mMinMax[MIN_Z] = 0xff7fffff; //PX_IR(PX_MAX_F32);
371 mMinMax[MAX_X] = mMinMax[MAX_Y] = mMinMax[MAX_Z] = 0x00800000; ///PX_IR(0.0f);
372 }
373
374 ValType mMinMax[6];
375
376private:
377
378 enum
379 {
380 eGRID_SNAP_VAL = 4
381 };
382};
383
384PX_FORCE_INLINE ValType encodeMin(const PxBounds3& bounds, PxU32 axis, PxReal contactDistance)
385{
386 const PxReal val = bounds.minimum[axis] - contactDistance;
387 const PxU32 min = PxUnionCast<PxU32, PxF32>(b: val);
388 const PxU32 m = IntegerAABB::encodeFloatMin(source: min);
389 return m;
390}
391
392PX_FORCE_INLINE ValType encodeMax(const PxBounds3& bounds, PxU32 axis, PxReal contactDistance)
393{
394 const PxReal val = bounds.maximum[axis] + contactDistance;
395 const PxU32 max = PxUnionCast<PxU32, PxF32>(b: val);
396 const PxU32 m = IntegerAABB::encodeFloatMax(source: max) | (1<<2);
397 return m;
398}
399
400class BroadPhase;
401
402class BroadPhaseUpdateData
403{
404public:
405
406 /**
407 \brief A structure detailing the changes to the collection of aabbs, whose overlaps are computed in the broadphase.
408 The structure consists of per-object arrays of object bounds and object groups, and three arrays that index
409 into the per-object arrays, denoting the bounds which are to be created, updated and removed in the broad phase.
410
411 * each entry in the object arrays represents the same shape or aggregate from frame to frame.
412 * each entry in an index array must be less than the capacity of the per-object arrays.
413 * no index value may appear in more than one index array, and may not occur more than once in that array.
414
415 An index value is said to be "in use" if it has appeared in a created list in a previous update, and has not
416 since occurred in a removed list.
417
418 \param[in] created an array of indices describing the bounds that must be inserted into the broadphase.
419 Each index in the array must not be in use.
420
421 \param[in] updated an array of indices (referencing the boxBounds and boxGroups arrays) describing the bounds
422 that have moved since the last broadphase update. Each index in the array must be in use, and each object
423 whose index is in use and whose AABB has changed must appear in the update list.
424
425 \param[in] removed an array of indices describing the bounds that must be removed from the broad phase. Each index in
426 the array must be in use.
427
428 \param[in] boxBounds an array of bounds coordinates for the AABBs to be processed by the broadphase.
429
430 An entry is valid if its values are integer bitwise representations of floating point numbers that satisfy max>min in each dimension,
431 along with a further rule that minima(maxima) must have even(odd) values.
432
433 Each entry whose index is either in use or appears in the created array must be valid. An entry whose index is either not in use or
434 appears in the removed array need not be valid.
435
436 \param[in] boxGroups an array of group ids, one for each bound, used for pair filtering. Bounds with the same group id will not be
437 reported as overlap pairs by the broad phase. Zero is reserved for static bounds.
438
439 Entries in this array are immutable: the only way to change the group of an object is to remove it from the broad phase and reinsert
440 it at a different index (recall that each index must appear at most once in the created/updated/removed lists).
441
442 \param[in] boxesCapacity the length of the boxBounds and boxGroups arrays.
443
444 @see BroadPhase::update
445 */
446 BroadPhaseUpdateData(
447 const ShapeHandle* created, const PxU32 createdSize,
448 const ShapeHandle* updated, const PxU32 updatedSize,
449 const ShapeHandle* removed, const PxU32 removedSize,
450 const PxBounds3* boxBounds, const Bp::FilterGroup::Enum* boxGroups,
451#ifdef BP_FILTERING_USES_TYPE_IN_GROUP
452 const bool* lut,
453#endif
454 const PxReal* boxContactDistances, const PxU32 boxesCapacity,
455 const bool stateChanged) :
456 mCreated (created),
457 mCreatedSize (createdSize),
458 mUpdated (updated),
459 mUpdatedSize (updatedSize),
460 mRemoved (removed),
461 mRemovedSize (removedSize),
462 mBoxBounds (boxBounds),
463 mBoxGroups (boxGroups),
464#ifdef BP_FILTERING_USES_TYPE_IN_GROUP
465 mLUT (lut),
466#endif
467 mContactDistance(boxContactDistances),
468 mBoxesCapacity (boxesCapacity),
469 mStateChanged (stateChanged)
470 {
471 }
472
473 PX_FORCE_INLINE const ShapeHandle* getCreatedHandles() const { return mCreated; }
474 PX_FORCE_INLINE PxU32 getNumCreatedHandles() const { return mCreatedSize; }
475
476 PX_FORCE_INLINE const ShapeHandle* getUpdatedHandles() const { return mUpdated; }
477 PX_FORCE_INLINE PxU32 getNumUpdatedHandles() const { return mUpdatedSize; }
478
479 PX_FORCE_INLINE const ShapeHandle* getRemovedHandles() const { return mRemoved; }
480 PX_FORCE_INLINE PxU32 getNumRemovedHandles() const { return mRemovedSize; }
481
482 PX_FORCE_INLINE const PxBounds3* getAABBs() const { return mBoxBounds; }
483 PX_FORCE_INLINE const Bp::FilterGroup::Enum* getGroups() const { return mBoxGroups; }
484#ifdef BP_FILTERING_USES_TYPE_IN_GROUP
485 PX_FORCE_INLINE const bool* getLUT() const { return mLUT; }
486#endif
487 PX_FORCE_INLINE PxU32 getCapacity() const { return mBoxesCapacity; }
488
489 PX_FORCE_INLINE const PxReal* getContactDistance() const { return mContactDistance; }
490
491 PX_FORCE_INLINE bool getStateChanged() const { return mStateChanged; }
492
493#if PX_CHECKED
494 static bool isValid(const BroadPhaseUpdateData& updateData, const BroadPhase& bp);
495 bool isValid() const;
496#endif
497
498private:
499
500 const ShapeHandle* mCreated;
501 PxU32 mCreatedSize;
502
503 const ShapeHandle* mUpdated;
504 PxU32 mUpdatedSize;
505
506 const ShapeHandle* mRemoved;
507 PxU32 mRemovedSize;
508
509 const PxBounds3* mBoxBounds;
510 const Bp::FilterGroup::Enum* mBoxGroups;
511#ifdef BP_FILTERING_USES_TYPE_IN_GROUP
512 const bool* mLUT;
513#endif
514 const PxReal* mContactDistance;
515 PxU32 mBoxesCapacity;
516 bool mStateChanged;
517};
518
519} //namespace Bp
520
521} //namespace physx
522
523#endif //BP_BROADPHASE_UPDATE_H
524

source code of qtquick3dphysics/src/3rdparty/PhysX/source/lowlevelaabb/include/BpBroadPhaseUpdate.h