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");
176 static_assert(Allocator::ObjectStorageSize == 128,
"Node should be 128 bytes");
183 Tracking(
const Tracking &inRHS) : mBroadPhaseLayer(inRHS.mBroadPhaseLayer.load()), mObjectLayer(inRHS.mObjectLayer.load()), mBodyLocation(inRHS.mBodyLocation.load()) { }
186 static const uint32 cInvalidBodyLocation = 0xffffffff;
189 atomic<ObjectLayer> mObjectLayer = cObjectLayerInvalid;
190 atomic<uint32> mBodyLocation { cInvalidBodyLocation };
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);
222 void DiscardOldTree();
225 AABox GetBounds()
const;
235 NodeID mLeafID = NodeID::sInvalid();
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;
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>
407#if defined(JPH_EXTERNAL_PROFILE) || defined(JPH_PROFILE_ENABLED)
409 const char * mName =
"Layer";
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