Jolt Physics
A multi core friendly Game Physics Engine
Loading...
Searching...
No Matches
BroadPhaseQuadTree.h
Go to the documentation of this file.
1// Jolt Physics Library (https://github.com/jrouwe/JoltPhysics)
2// SPDX-FileCopyrightText: 2021 Jorrit Rouwe
3// SPDX-License-Identifier: MIT
4
5#pragma once
6
10
12
15{
16public:
18
20 virtual ~BroadPhaseQuadTree() override;
21
22 // Implementing interface of BroadPhase (see BroadPhase for documentation)
23 virtual void Init(BodyManager *inBodyManager, const BroadPhaseLayerInterface &inLayerInterface) override;
24 virtual void Optimize() override;
25 virtual void FrameSync() override;
26 virtual void LockModifications() override;
27 virtual UpdateState UpdatePrepare() override;
28 virtual void UpdateFinalize(const UpdateState &inUpdateState) override;
29 virtual void UnlockModifications() override;
30 virtual AddState AddBodiesPrepare(BodyID *ioBodies, int inNumber) override;
31 virtual void AddBodiesFinalize(BodyID *ioBodies, int inNumber, AddState inAddState) override;
32 virtual void AddBodiesAbort(BodyID *ioBodies, int inNumber, AddState inAddState) override;
33 virtual void RemoveBodies(BodyID *ioBodies, int inNumber) override;
34 virtual void NotifyBodiesAABBChanged(BodyID *ioBodies, int inNumber, bool inTakeLock) override;
35 virtual void NotifyBodiesLayerChanged(BodyID *ioBodies, int inNumber) override;
36 virtual void CastRay(const RayCast &inRay, RayCastBodyCollector &ioCollector, const BroadPhaseLayerFilter &inBroadPhaseLayerFilter, const ObjectLayerFilter &inObjectLayerFilter) const override;
37 virtual void CollideAABox(const AABox &inBox, CollideShapeBodyCollector &ioCollector, const BroadPhaseLayerFilter &inBroadPhaseLayerFilter, const ObjectLayerFilter &inObjectLayerFilter) const override;
38 virtual void CollideSphere(Vec3Arg inCenter, float inRadius, CollideShapeBodyCollector &ioCollector, const BroadPhaseLayerFilter &inBroadPhaseLayerFilter, const ObjectLayerFilter &inObjectLayerFilter) const override;
39 virtual void CollidePoint(Vec3Arg inPoint, CollideShapeBodyCollector &ioCollector, const BroadPhaseLayerFilter &inBroadPhaseLayerFilter, const ObjectLayerFilter &inObjectLayerFilter) const override;
40 virtual void CollideOrientedBox(const OrientedBox &inBox, CollideShapeBodyCollector &ioCollector, const BroadPhaseLayerFilter &inBroadPhaseLayerFilter, const ObjectLayerFilter &inObjectLayerFilter) const override;
41 virtual void CastAABoxNoLock(const AABoxCast &inBox, CastShapeBodyCollector &ioCollector, const BroadPhaseLayerFilter &inBroadPhaseLayerFilter, const ObjectLayerFilter &inObjectLayerFilter) const override;
42 virtual void CastAABox(const AABoxCast &inBox, CastShapeBodyCollector &ioCollector, const BroadPhaseLayerFilter &inBroadPhaseLayerFilter, const ObjectLayerFilter &inObjectLayerFilter) const override;
43 virtual void FindCollidingPairs(BodyID *ioActiveBodies, int inNumActiveBodies, float inSpeculativeContactDistance, const ObjectVsBroadPhaseLayerFilter &inObjectVsBroadPhaseLayerFilter, const ObjectLayerPairFilter &inObjectLayerPairFilter, BodyPairCollector &ioPairCollector) const override;
44 virtual AABox GetBounds() const override;
45#ifdef JPH_TRACK_BROADPHASE_STATS
46 virtual void ReportStats() override;
47#endif // JPH_TRACK_BROADPHASE_STATS
48
49private:
51 struct LayerState
52 {
54
55 BodyID * mBodyStart = nullptr;
56 BodyID * mBodyEnd;
57 QuadTree::AddState mAddState;
58 };
59
61 using TrackingVector = QuadTree::TrackingVector;
62
63#ifdef JPH_ENABLE_ASSERTS
65 PhysicsLockContext mLockContext = nullptr;
66#endif // JPH_ENABLE_ASSERTS
67
69 size_t mMaxBodies = 0;
70
72 TrackingVector mTracking;
73
75 QuadTree::Allocator mAllocator;
76
78 const BroadPhaseLayerInterface *mBroadPhaseLayerInterface = nullptr;
79
81 QuadTree * mLayers;
82 uint mNumLayers;
83
85 struct UpdateStateImpl
86 {
87 QuadTree * mTree;
88 QuadTree::UpdateState mUpdateState;
89 };
90
91 static_assert(sizeof(UpdateStateImpl) <= sizeof(UpdateState));
92 static_assert(alignof(UpdateStateImpl) <= alignof(UpdateState));
93
95 SharedMutex mUpdateMutex;
96
99 mutable SharedMutex mQueryLocks[2];
100
102 atomic<uint32> mQueryLockIdx { 0 };
103
105 uint32 mNextLayerToUpdate = 0;
106};
107
#define JPH_EXPORT
Definition: Core.h:227
unsigned int uint
Definition: Core.h:439
#define JPH_NAMESPACE_END
Definition: Core.h:367
std::uint32_t uint32
Definition: Core.h:442
#define JPH_NAMESPACE_BEGIN
Definition: Core.h:361
#define JPH_OVERRIDE_NEW_DELETE
Macro to override the new and delete functions.
Definition: Memory.h:29
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
Class that contains all bodies.
Definition: BodyManager.h:32
Used to do coarse collision detection operations to quickly prune out bodies that will not collide.
Definition: BroadPhase.h:26
virtual void AddBodiesAbort(BodyID *ioBodies, int inNumber, AddState inAddState)
Definition: BroadPhase.h:71
virtual void AddBodiesFinalize(BodyID *ioBodies, int inNumber, AddState inAddState)=0
virtual void LockModifications()
Must be called before UpdatePrepare to prevent modifications from being made to the tree.
Definition: BroadPhase.h:41
virtual void NotifyBodiesAABBChanged(BodyID *ioBodies, int inNumber, bool inTakeLock=true)=0
virtual void CastAABoxNoLock(const AABoxCast &inBox, CastShapeBodyCollector &ioCollector, const BroadPhaseLayerFilter &inBroadPhaseLayerFilter, const ObjectLayerFilter &inObjectLayerFilter) const =0
Same as BroadPhaseQuery::CastAABox but can be implemented in a way to take no broad phase locks.
virtual void FrameSync()
Must be called just before updating the broadphase when none of the body mutexes are locked.
Definition: BroadPhase.h:38
virtual void UnlockModifications()
Must be called after UpdateFinalize to allow modifications to the broadphase.
Definition: BroadPhase.h:54
virtual void NotifyBodiesLayerChanged(BodyID *ioBodies, int inNumber)=0
Call whenever the layer (and optionally the aabb as well) of a body changes (can change order of ioBo...
virtual void Optimize()
Should be called after many objects have been inserted to make the broadphase more efficient,...
Definition: BroadPhase.h:35
virtual void UpdateFinalize(const UpdateState &inUpdateState)
Finalizing the update will quickly apply the changes.
Definition: BroadPhase.h:51
virtual AABox GetBounds() const =0
Get the bounding box of all objects in the broadphase.
virtual void Init(BodyManager *inBodyManager, const BroadPhaseLayerInterface &inLayerInterface)
Definition: BroadPhase.cpp:11
virtual AddState AddBodiesPrepare(BodyID *ioBodies, int inNumber)
Definition: BroadPhase.h:62
virtual void RemoveBodies(BodyID *ioBodies, int inNumber)=0
void * AddState
Handle used during adding bodies to the broadphase.
Definition: BroadPhase.h:57
virtual void FindCollidingPairs(BodyID *ioActiveBodies, int inNumActiveBodies, float inSpeculativeContactDistance, const ObjectVsBroadPhaseLayerFilter &inObjectVsBroadPhaseLayerFilter, const ObjectLayerPairFilter &inObjectLayerPairFilter, BodyPairCollector &ioPairCollector) const =0
virtual UpdateState UpdatePrepare()
Definition: BroadPhase.h:48
Filter class for broadphase layers.
Definition: BroadPhaseLayer.h:94
Interface that the application should implement to allow mapping object layers to broadphase layers.
Definition: BroadPhaseLayer.h:61
Fast SIMD based quad tree BroadPhase that is multithreading aware and tries to do a minimal amount of...
Definition: BroadPhaseQuadTree.h:15
virtual void CollidePoint(Vec3Arg inPoint, CollideShapeBodyCollector &ioCollector, const BroadPhaseLayerFilter &inBroadPhaseLayerFilter={ }, const ObjectLayerFilter &inObjectLayerFilter={ }) const =0
Get bodies intersecting with a point and any hits to ioCollector.
virtual void CastRay(const RayCast &inRay, RayCastBodyCollector &ioCollector, const BroadPhaseLayerFilter &inBroadPhaseLayerFilter={ }, const ObjectLayerFilter &inObjectLayerFilter={ }) const =0
Cast a ray and add any hits to ioCollector.
virtual void CollideAABox(const AABox &inBox, CollideShapeBodyCollector &ioCollector, const BroadPhaseLayerFilter &inBroadPhaseLayerFilter={ }, const ObjectLayerFilter &inObjectLayerFilter={ }) const =0
Get bodies intersecting with inBox and any hits to ioCollector.
virtual void CastAABox(const AABoxCast &inBox, CastShapeBodyCollector &ioCollector, const BroadPhaseLayerFilter &inBroadPhaseLayerFilter={ }, const ObjectLayerFilter &inObjectLayerFilter={ }) const =0
Cast a box and add any hits to ioCollector.
virtual void CollideOrientedBox(const OrientedBox &inBox, CollideShapeBodyCollector &ioCollector, const BroadPhaseLayerFilter &inBroadPhaseLayerFilter={ }, const ObjectLayerFilter &inObjectLayerFilter={ }) const =0
Get bodies intersecting with an oriented box and any hits to ioCollector.
virtual void CollideSphere(Vec3Arg inCenter, float inRadius, CollideShapeBodyCollector &ioCollector, const BroadPhaseLayerFilter &inBroadPhaseLayerFilter={ }, const ObjectLayerFilter &inObjectLayerFilter={ }) const =0
Get bodies intersecting with a sphere and any hits to ioCollector.
Virtual interface that allows collecting multiple collision results.
Definition: CollisionCollector.h:45
Filter class for object layers.
Definition: ObjectLayer.h:28
Filter class to test if two objects can collide based on their object layer. Used while finding colli...
Definition: ObjectLayer.h:50
Class to test if an object can collide with a broadphase layer. Used while finding collision pairs.
Definition: BroadPhaseLayer.h:80
Oriented box.
Definition: OrientedBox.h:18
Definition: QuadTree.h:21
Array< Tracking > TrackingVector
Definition: QuadTree.h:169
Definition: Mutex.h:166
Definition: Vec3.h:16
Structure that holds AABox moving linearly through 3d space.
Definition: AABoxCast.h:13
Context used during broadphase update.
Definition: BroadPhase.h:44
Temporary data structure to pass information between AddBodiesPrepare and AddBodiesFinalize/Abort.
Definition: QuadTree.h:210
Data to track location of a Body in the tree.
Definition: QuadTree.h:156
Definition: QuadTree.h:193
Definition: RayCast.h:47