36 inline NodeID() =
default;
39 static inline NodeID sInvalid() {
return NodeID(cInvalidNodeIndex); }
41 static inline NodeID sFromNodeIndex(
uint32 inIdx) {
JPH_ASSERT((inIdx & cIsNode) == 0);
return NodeID(inIdx | cIsNode); }
44 inline bool IsValid()
const {
return mID != cInvalidNodeIndex; }
45 inline bool IsBody()
const {
return (mID & cIsNode) == 0; }
46 inline bool IsNode()
const {
return (mID & cIsNode) != 0; }
50 inline uint32 GetNodeIndex()
const {
JPH_ASSERT(IsNode());
return mID & ~cIsNode; }
54 inline bool operator == (
const NodeID &inRHS)
const {
return mID == inRHS.mID; }
57 friend class AtomicNodeID;
59 inline explicit NodeID(
uint32 inID) : mID(inID) { }
66 static_assert(
sizeof(NodeID) ==
sizeof(
BodyID),
"Body id's should have the same size as NodeIDs");
73 AtomicNodeID() =
default;
74 explicit AtomicNodeID(
const NodeID &inRHS) : mID(inRHS.mID) { }
77 inline void operator = (
const NodeID &inRHS) { mID = inRHS.mID; }
80 inline operator NodeID ()
const {
return NodeID(mID); }
83 inline bool IsValid()
const {
return mID != cInvalidNodeIndex; }
87 inline bool operator == (
const NodeID &inRHS)
const {
return mID == inRHS.mID; }
90 inline bool CompareExchange(NodeID inOld, NodeID inNew) {
return mID.compare_exchange_strong(inOld.mID, inNew.mID); }
101 explicit Node(
bool inIsChanged);
104 void GetNodeBounds(
AABox &outBounds)
const;
107 void GetChildBounds(
int inChildIndex,
AABox &outBounds)
const;
110 void SetChildBounds(
int inChildIndex,
const AABox &inBounds);
113 void InvalidateChildBounds(
int inChildIndex);
116 bool EncapsulateChildBounds(
int inChildIndex,
const AABox &inBounds);
125 inline void LoadChildBounds(
Vec4 &outMinX,
Vec4 &outMinY,
Vec4 &outMinZ,
Vec4 &outMaxX,
Vec4 &outMaxY,
Vec4 &outMaxZ)
const
137 inline UVec4 LoadChildNodeIDs()
const
143 atomic<float> mBoundsMinX[4];
144 atomic<float> mBoundsMinY[4];
145 atomic<float> mBoundsMinZ[4];
146 atomic<float> mBoundsMaxX[4];
147 atomic<float> mBoundsMaxY[4];
148 atomic<float> mBoundsMaxZ[4];
151 AtomicNodeID mChildNodeID[4];
155 atomic<uint32> mParentNodeIndex = cInvalidNodeIndex;
159 atomic<uint32> mIsChanged;
166 static constexpr int cStackSize = 128;
168 static_assert(
sizeof(atomic<float>) == 4,
"Assuming that an atomic doesn't add any additional storage");
169 static_assert(
sizeof(atomic<uint32>) == 4,
"Assuming that an atomic doesn't add any additional storage");
170 static_assert(std::is_trivially_destructible<Node>(),
"Assuming that we don't have a destructor");
198#if defined(JPH_EXTERNAL_PROFILE) || defined(JPH_PROFILE_ENABLED)
200 void SetName(
const char *inName) { mName = inName; }
201 inline const char *
GetName()
const {
return mName; }
205 inline bool HasBodies()
const {
return mNumBodies != 0; }
208 inline bool IsDirty()
const {
return mIsDirty; }
211 inline bool CanBeUpdated()
const {
return mFreeNodeBatch.mNumObjects == 0; }
214 void Init(Allocator &inAllocator);
278#ifdef JPH_TRACK_BROADPHASE_STATS
280 uint64 GetTicks100Pct()
const;
283 void ReportStats(
uint64 inTicks100Pct)
const;
288 static constexpr uint32 cInvalidNodeIndex = 0xffffffff;
289 static const AABox cInvalidBounds;
295 inline NodeID GetNodeID()
const {
return NodeID::sFromNodeIndex(mIndex); }
298 atomic<uint32> mIndex { cInvalidNodeIndex };
302 void GetBodyLocation(
const TrackingVector &inTracking, BodyID inBodyID,
uint32 &outNodeIdx,
uint32 &outChildIdx)
const;
303 void SetBodyLocation(TrackingVector &ioTracking, BodyID inBodyID,
uint32 inNodeIdx,
uint32 inChildIdx)
const;
304 static void sInvalidateBodyLocation(TrackingVector &ioTracking, BodyID inBodyID);
307 JPH_INLINE
const RootNode & GetCurrentRoot()
const {
return mRootNode[mRootNodeIndex]; }
308 JPH_INLINE RootNode & GetCurrentRoot() {
return mRootNode[mRootNodeIndex]; }
311 inline AABox GetNodeOrBodyBounds(
const BodyVector &inBodies, NodeID inNodeID)
const;
314 inline void MarkNodeAndParentsChanged(
uint32 inNodeIndex);
317 inline void WidenAndMarkNodeAndParentsChanged(
uint32 inNodeIndex,
const AABox &inNewBounds);
320 inline uint32 AllocateNode(
bool inIsChanged);
323 inline bool TryInsertLeaf(TrackingVector &ioTracking,
int inNodeIndex, NodeID inLeafID,
const AABox &inLeafBounds,
int inLeafNumBodies);
326 inline bool TryCreateNewRoot(TrackingVector &ioTracking, atomic<uint32> &ioRootNodeIndex, NodeID inLeafID,
const AABox &inLeafBounds,
int inLeafNumBodies);
329 NodeID BuildTree(
const BodyVector &inBodies, TrackingVector &ioTracking, NodeID *ioNodeIDs,
int inNumber,
uint inMaxDepthMarkChanged, AABox &outBounds);
333 static void sPartition(NodeID *ioNodeIDs, Vec3 *ioNodeCenters,
int inNumber,
int &outMidPoint);
338 static void sPartition4(NodeID *ioNodeIDs, Vec3 *ioNodeCenters,
int inBegin,
int inEnd,
int *outSplit);
343 void ValidateTree(
const BodyVector &inBodies,
const TrackingVector &inTracking,
uint32 inNodeIndex,
uint32 inNumExpectedBodies)
const;
346#ifdef JPH_DUMP_BROADPHASE_TREE
348 void DumpTree(
const NodeID &inRoot,
const char *inFileNamePrefix)
const;
352 Allocator * mAllocator =
nullptr;
355 Allocator::Batch mFreeNodeBatch;
364 RootNode mRootNode[2];
365 atomic<uint32> mRootNodeIndex { 0 };
368 atomic<bool> mIsDirty =
false;
370#ifdef JPH_TRACK_BROADPHASE_STATS
372 mutable Mutex mStatsMutex;
378 uint64 mBodiesVisited = 0;
381 uint64 mCollectorTicks = 0;
384 using LayerToStats = UnorderedMap<String, Stat>;
387 uint64 GetTicks100Pct(
const LayerToStats &inLayer)
const;
390 void ReportStats(
const char *inName,
const LayerToStats &inLayer,
uint64 inTicks100Pct)
const;
392 mutable LayerToStats mCastRayStats;
393 mutable LayerToStats mCollideAABoxStats;
394 mutable LayerToStats mCollideSphereStats;
395 mutable LayerToStats mCollidePointStats;
396 mutable LayerToStats mCollideOrientedBoxStats;
397 mutable LayerToStats mCastAABoxStats;
401 uint GetMaxTreeDepth(
const NodeID &inNodeID)
const;
404 template <
class Visitor>
405 JPH_INLINE
void WalkTree(
const ObjectLayerFilter &inObjectLayerFilter,
const TrackingVector &inTracking, Visitor &ioVisitor
JPH_IF_TRACK_BROADPHASE_STATS(, LayerToStats &ioStats))
const;
407#if defined(JPH_EXTERNAL_PROFILE) || defined(JPH_PROFILE_ENABLED)
409 const char * mName =
"Layer";
Array< Body * > BodyVector
Array of bodies.
Definition BodyManager.h:37
#define JPH_IF_TRACK_BROADPHASE_STATS(...)
Definition BroadPhase.h:16
CollisionCollector< BodyPair, CollisionCollectorTraitsCollideShape > BodyPairCollector
Definition BroadPhase.h:22
CollisionCollector< BroadPhaseCastResult, CollisionCollectorTraitsCastRay > RayCastBodyCollector
Definition BroadPhaseQuery.h:22
CollisionCollector< BodyID, CollisionCollectorTraitsCollideShape > CollideShapeBodyCollector
Definition BroadPhaseQuery.h:24
CollisionCollector< BroadPhaseCastResult, CollisionCollectorTraitsCastShape > CastShapeBodyCollector
Definition BroadPhaseQuery.h:23
#define JPH_EXPORT
Definition Core.h:303
#define JPH_CACHE_LINE_SIZE
Definition Core.h:613
std::uint64_t uint64
Definition Core.h:569
unsigned int uint
Definition Core.h:564
#define JPH_TSAN_NO_SANITIZE
Definition Core.h:704
#define JPH_NAMESPACE_END
Definition Core.h:487
std::uint32_t uint32
Definition Core.h:567
#define JPH_NAMESPACE_BEGIN
Definition Core.h:481
#define JPH_ASSERT(...)
Definition IssueReporting.h:28
const Vec3 Vec3Arg
Definition MathTypes.h:19
#define JPH_OVERRIDE_NEW_DELETE
Macro to override the new and delete functions.
Definition Memory.h:51
Axis aligned box.
Definition AABox.h:16
ID of a body. This is a way of reasoning about bodies in a multithreaded simulation while avoiding ra...
Definition BodyID.h:13
static constexpr uint32 cBroadPhaseBit
This bit is used by the broadphase.
Definition BodyID.h:18
uint32 GetIndexAndSequenceNumber() const
Returns the index and sequence number combined in an uint32.
Definition BodyID.h:59
uint8 Type
Definition BroadPhaseLayer.h:20
Definition FixedSizeFreeList.h:18
static const int ObjectStorageSize
Definition FixedSizeFreeList.h:80
Class that holds 4 float values. Convert to Vec4 to perform calculations.
Definition Float4.h:11
Filter class for object layers.
Definition ObjectLayer.h:27
Filter class to test if two objects can collide based on their object layer. Used while finding colli...
Definition ObjectLayer.h:49
Oriented box.
Definition OrientedBox.h:18
const char * GetName() const
Definition QuadTree.h:201
bool HasBodies() const
Check if there is anything in the tree.
Definition QuadTree.h:205
void CastRay(const RayCast &inRay, RayCastBodyCollector &ioCollector, const ObjectLayerFilter &inObjectLayerFilter, const TrackingVector &inTracking) const
Cast a ray and get the intersecting bodies in ioCollector.
Definition QuadTree.cpp:1075
void FindCollidingPairs(const BodyVector &inBodies, const BodyID *inActiveBodies, int inNumActiveBodies, float inSpeculativeContactDistance, BodyPairCollector &ioPairCollector, const ObjectLayerPairFilter &inObjectLayerPairFilter) const
Find all colliding pairs between dynamic bodies, calls ioPairCollector for every pair found.
Definition QuadTree.cpp:1427
void CollideOrientedBox(const OrientedBox &inBox, CollideShapeBodyCollector &ioCollector, const ObjectLayerFilter &inObjectLayerFilter, const TrackingVector &inTracking) const
Get bodies intersecting with an oriented box and any hits to ioCollector.
Definition QuadTree.cpp:1305
void AddBodiesAbort(TrackingVector &ioTracking, const AddState &inState)
Definition QuadTree.cpp:860
void DiscardOldTree()
Will throw away the previous frame's nodes so that we can start building a new tree in the background...
Definition QuadTree.cpp:246
void AddBodiesPrepare(const BodyVector &inBodies, TrackingVector &ioTracking, BodyID *ioBodyIDs, int inNumber, AddState &outState)
Definition QuadTree.cpp:815
AABox GetBounds() const
Get the bounding box for this tree.
Definition QuadTree.cpp:263
void CollideAABox(const AABox &inBox, CollideShapeBodyCollector &ioCollector, const ObjectLayerFilter &inObjectLayerFilter, const TrackingVector &inTracking) const
Get bodies intersecting with inBox in ioCollector.
Definition QuadTree.cpp:1137
void NotifyBodiesAABBChanged(const BodyVector &inBodies, const TrackingVector &inTracking, const BodyID *ioBodyIDs, int inNumber)
Call whenever the aabb of a body changes.
Definition QuadTree.cpp:937
bool IsDirty() const
Check if the tree needs an UpdatePrepare/Finalize().
Definition QuadTree.h:208
void UpdateFinalize(const BodyVector &inBodies, const TrackingVector &inTracking, const UpdateState &inUpdateState)
Definition QuadTree.cpp:396
void CastAABox(const AABoxCast &inBox, CastShapeBodyCollector &ioCollector, const ObjectLayerFilter &inObjectLayerFilter, const TrackingVector &inTracking) const
Cast a box and get intersecting bodies in ioCollector.
Definition QuadTree.cpp:1359
bool CanBeUpdated() const
Check if this tree can get an UpdatePrepare/Finalize() or if it needs a DiscardOldTree() first.
Definition QuadTree.h:211
void AddBodiesFinalize(TrackingVector &ioTracking, int inNumberBodies, const AddState &inState)
Finalize adding bodies to the quadtree, supply the same number of bodies as in AddBodiesPrepare.
Definition QuadTree.cpp:837
void CollidePoint(Vec3Arg inPoint, CollideShapeBodyCollector &ioCollector, const ObjectLayerFilter &inObjectLayerFilter, const TrackingVector &inTracking) const
Get bodies intersecting with a point and any hits to ioCollector.
Definition QuadTree.cpp:1251
void CollideSphere(Vec3Arg inCenter, float inRadius, CollideShapeBodyCollector &ioCollector, const ObjectLayerFilter &inObjectLayerFilter, const TrackingVector &inTracking) const
Get bodies intersecting with a sphere in ioCollector.
Definition QuadTree.cpp:1191
Array< Tracking > TrackingVector
Definition QuadTree.h:193
void UpdatePrepare(const BodyVector &inBodies, TrackingVector &ioTracking, UpdateState &outUpdateState, bool inFullRebuild)
Definition QuadTree.cpp:274
void SetName(const char *inName)
Name of the tree for debugging purposes.
Definition QuadTree.h:200
void RemoveBodies(const BodyVector &inBodies, TrackingVector &ioTracking, const BodyID *ioBodyIDs, int inNumber)
Remove inNumber bodies in ioBodyIDs from the quadtree.
Definition QuadTree.cpp:901
FixedSizeFreeList< Node > Allocator
Class that allocates tree nodes, can be shared between multiple trees.
Definition QuadTree.h:174
static JPH_INLINE UVec4 sLoadInt4Aligned(const uint32 *inV)
Load 4 ints from memory, aligned to 16 bytes.
Definition UVec4.inl:118
static JPH_INLINE Vec4 sLoadFloat4Aligned(const Float4 *inV)
Load 4 floats from memory, 16 bytes aligned.
Definition Vec4.inl:139
Structure that holds AABox moving linearly through 3d space.
Definition AABoxCast.h:13
Temporary data structure to pass information between AddBodiesPrepare and AddBodiesFinalize/Abort.
Definition QuadTree.h:234
AABox mLeafBounds
Definition QuadTree.h:236
NodeID mLeafID
Definition QuadTree.h:235
atomic< BroadPhaseLayer::Type > mBroadPhaseLayer
Definition QuadTree.h:188
static const uint32 cInvalidBodyLocation
Invalid body location identifier.
Definition QuadTree.h:186
Tracking(const Tracking &inRHS)
Definition QuadTree.h:183
atomic< ObjectLayer > mObjectLayer
Definition QuadTree.h:189
atomic< uint32 > mBodyLocation
Definition QuadTree.h:190
Tracking()=default
Constructor to satisfy the vector class.
Definition QuadTree.h:217
NodeID mRootNodeID
This will be the new root node id.
Definition QuadTree.h:218