126 lines
5.8 KiB
C++
126 lines
5.8 KiB
C++
// Jolt Physics Library (https://github.com/jrouwe/JoltPhysics)
|
|
// SPDX-FileCopyrightText: 2021 Jorrit Rouwe
|
|
// SPDX-License-Identifier: MIT
|
|
|
|
#pragma once
|
|
|
|
#include <Jolt/Physics/Body/BodyID.h>
|
|
#include <Jolt/Core/NonCopyable.h>
|
|
#include <Jolt/Core/Atomics.h>
|
|
|
|
JPH_NAMESPACE_BEGIN
|
|
|
|
class TempAllocator;
|
|
|
|
//#define JPH_VALIDATE_ISLAND_BUILDER
|
|
|
|
/// Keeps track of connected bodies and builds islands for multithreaded velocity/position update
|
|
class IslandBuilder : public NonCopyable
|
|
{
|
|
public:
|
|
/// Destructor
|
|
~IslandBuilder();
|
|
|
|
/// Initialize the island builder with the maximum amount of bodies that could be active
|
|
void Init(uint32 inMaxActiveBodies);
|
|
|
|
/// Prepare for simulation step by allocating space for the contact constraints
|
|
void PrepareContactConstraints(uint32 inMaxContactConstraints, TempAllocator *inTempAllocator);
|
|
|
|
/// Prepare for simulation step by allocating space for the non-contact constraints
|
|
void PrepareNonContactConstraints(uint32 inNumConstraints, TempAllocator *inTempAllocator);
|
|
|
|
/// Link two bodies by their index in the BodyManager::mActiveBodies list to form islands
|
|
void LinkBodies(uint32 inFirst, uint32 inSecond);
|
|
|
|
/// Link a constraint to a body by their index in the BodyManager::mActiveBodies
|
|
void LinkConstraint(uint32 inConstraintIndex, uint32 inFirst, uint32 inSecond);
|
|
|
|
/// Link a contact to a body by their index in the BodyManager::mActiveBodies
|
|
void LinkContact(uint32 inContactIndex, uint32 inFirst, uint32 inSecond);
|
|
|
|
/// Finalize the islands after all bodies have been Link()-ed
|
|
void Finalize(const BodyID *inActiveBodies, uint32 inNumActiveBodies, uint32 inNumContacts, TempAllocator *inTempAllocator);
|
|
|
|
/// Get the amount of islands formed
|
|
uint32 GetNumIslands() const { return mNumIslands; }
|
|
|
|
/// Get iterator for a particular island, return false if there are no constraints
|
|
void GetBodiesInIsland(uint32 inIslandIndex, BodyID *&outBodiesBegin, BodyID *&outBodiesEnd) const;
|
|
bool GetConstraintsInIsland(uint32 inIslandIndex, uint32 *&outConstraintsBegin, uint32 *&outConstraintsEnd) const;
|
|
bool GetContactsInIsland(uint32 inIslandIndex, uint32 *&outContactsBegin, uint32 *&outContactsEnd) const;
|
|
|
|
/// The number of position iterations for each island
|
|
void SetNumPositionSteps(uint32 inIslandIndex, uint inNumPositionSteps) { JPH_ASSERT(inIslandIndex < mNumIslands); JPH_ASSERT(inNumPositionSteps < 256); mNumPositionSteps[inIslandIndex] = uint8(inNumPositionSteps); }
|
|
uint GetNumPositionSteps(uint32 inIslandIndex) const { JPH_ASSERT(inIslandIndex < mNumIslands); return mNumPositionSteps[inIslandIndex]; }
|
|
|
|
/// After you're done calling the three functions above, call this function to free associated data
|
|
void ResetIslands(TempAllocator *inTempAllocator);
|
|
|
|
private:
|
|
/// Returns the index of the lowest body in the group
|
|
uint32 GetLowestBodyIndex(uint32 inActiveBodyIndex) const;
|
|
|
|
#ifdef JPH_VALIDATE_ISLAND_BUILDER
|
|
/// Helper function to validate all islands so far generated
|
|
void ValidateIslands(uint32 inNumActiveBodies) const;
|
|
#endif
|
|
|
|
// Helper functions to build various islands
|
|
void BuildBodyIslands(const BodyID *inActiveBodies, uint32 inNumActiveBodies, TempAllocator *inTempAllocator);
|
|
void BuildConstraintIslands(const uint32 *inConstraintToBody, uint32 inNumConstraints, uint32 *&outConstraints, uint32 *&outConstraintsEnd, TempAllocator *inTempAllocator) const;
|
|
|
|
/// Sorts the islands so that the islands with most constraints go first
|
|
void SortIslands(TempAllocator *inTempAllocator);
|
|
|
|
/// Intermediate data structure that for each body keeps track what the lowest index of the body is that it is connected to
|
|
struct BodyLink
|
|
{
|
|
JPH_OVERRIDE_NEW_DELETE
|
|
|
|
atomic<uint32> mLinkedTo; ///< An index in mBodyLinks pointing to another body in this island with a lower index than this body
|
|
uint32 mIslandIndex; ///< The island index of this body (filled in during Finalize)
|
|
};
|
|
|
|
// Intermediate data
|
|
BodyLink * mBodyLinks = nullptr; ///< Maps bodies to the first body in the island
|
|
uint32 * mConstraintLinks = nullptr; ///< Maps constraint index to body index (which maps to island index)
|
|
uint32 * mContactLinks = nullptr; ///< Maps contact constraint index to body index (which maps to island index)
|
|
|
|
// Final data
|
|
BodyID * mBodyIslands = nullptr; ///< Bodies ordered by island
|
|
uint32 * mBodyIslandEnds = nullptr; ///< End index of each body island
|
|
|
|
uint32 * mConstraintIslands = nullptr; ///< Constraints ordered by island
|
|
uint32 * mConstraintIslandEnds = nullptr; ///< End index of each constraint island
|
|
|
|
uint32 * mContactIslands = nullptr; ///< Contacts ordered by island
|
|
uint32 * mContactIslandEnds = nullptr; ///< End index of each contact island
|
|
|
|
uint32 * mIslandsSorted = nullptr; ///< A list of island indices in order of most constraints first
|
|
|
|
uint8 * mNumPositionSteps = nullptr; ///< Number of position steps for each island
|
|
|
|
// Counters
|
|
uint32 mMaxActiveBodies; ///< Maximum size of the active bodies list (see BodyManager::mActiveBodies)
|
|
uint32 mNumActiveBodies = 0; ///< Number of active bodies passed to
|
|
uint32 mNumConstraints = 0; ///< Size of the constraint list (see ConstraintManager::mConstraints)
|
|
uint32 mMaxContacts = 0; ///< Maximum amount of contacts supported
|
|
uint32 mNumContacts = 0; ///< Size of the contacts list (see ContactConstraintManager::mNumConstraints)
|
|
uint32 mNumIslands = 0; ///< Final number of islands
|
|
|
|
#ifdef JPH_VALIDATE_ISLAND_BUILDER
|
|
/// Structure to keep track of all added links to validate that islands were generated correctly
|
|
struct LinkValidation
|
|
{
|
|
uint32 mFirst;
|
|
uint32 mSecond;
|
|
};
|
|
|
|
LinkValidation * mLinkValidation = nullptr;
|
|
atomic<uint32> mNumLinkValidation;
|
|
#endif
|
|
};
|
|
|
|
JPH_NAMESPACE_END
|