Code/Engine/Core/World/SpatialSystem_RegularGrid.h - dev - redgpu/ezEngine

Code/Engine/Core/World/SpatialSystem_RegularGrid.h
135 строк6 KB
Jan Krassnigg
Improved code documentation: Core, Texture, Utilities (#1666)
23 сен 2025, 09:56
23 сен 2025, 09:56a9f6901
#pragma once

#include <Core/World/SpatialSystem.h>
#include <Foundation/Containers/IdTable.h>
#include <Foundation/SimdMath/SimdVec4i.h>
#include <Foundation/Types/UniquePtr.h>

namespace ezInternal
{
  struct QueryHelper;
}

/// \brief Spatial system implementation using regular grids for organizing objects.
///
/// Divides space into uniform grid cells to enable efficient spatial queries. Supports
/// multiple grids for different spatial data categories and implements a caching system
/// to optimize frequently used tag-based queries by creating specialized grid views.
class EZ_CORE_DLL ezSpatialSystem_RegularGrid : public ezSpatialSystem
{
  EZ_ADD_DYNAMIC_REFLECTION(ezSpatialSystem_RegularGrid, ezSpatialSystem);

public:
  /// \brief Creates a regular grid spatial system with the given cell size.
  ezSpatialSystem_RegularGrid(ezUInt32 uiCellSize = 128);
  ~ezSpatialSystem_RegularGrid();

  /// \brief Returns the bounding box of the cell associated with the given spatial data. Useful for debug visualizations.
  ezResult GetCellBoxForSpatialData(const ezSpatialDataHandle& hData, ezBoundingBox& out_boundingBox) const;

  /// \brief Returns bounding boxes of all existing cells.
  void GetAllCellBoxes(ezDynamicArray<ezBoundingBox>& out_boundingBoxes, ezSpatialData::Category filterCategory = ezInvalidSpatialDataCategory) const;

private:
  friend ezInternal::QueryHelper;

  // ezSpatialSystem implementation
  virtual void StartNewFrame() override;

  ezSpatialDataHandle CreateSpatialData(const ezSimdBBoxSphere& bounds, ezGameObject* pObject, ezUInt32 uiCategoryBitmask, const ezTagSet& tags) override;
  ezSpatialDataHandle CreateSpatialDataAlwaysVisible(ezGameObject* pObject, ezUInt32 uiCategoryBitmask, const ezTagSet& tags) override;

  void DeleteSpatialData(const ezSpatialDataHandle& hData) override;

  void UpdateSpatialDataBounds(const ezSpatialDataHandle& hData, const ezSimdBBoxSphere& bounds) override;
  void UpdateSpatialDataObject(const ezSpatialDataHandle& hData, ezGameObject* pObject) override;

  void FindObjectsInSphere(const ezBoundingSphere& sphere, const QueryParams& queryParams, QueryCallback callback) const override;
  void FindObjectsInBox(const ezBoundingBox& box, const QueryParams& queryParams, QueryCallback callback) const override;

  void FindVisibleObjects(const ezFrustum& frustum, const QueryParams& queryParams, ezDynamicArray<const ezGameObject*>& out_Objects, ezSpatialSystem::IsOccludedFunc IsOccluded, ezVisibilityState::Enum visType) const override;

  ezVisibilityState::Enum GetVisibilityState(const ezSpatialDataHandle& hData, ezUInt32 uiNumFramesBeforeInvisible) const override;

#if EZ_ENABLED(EZ_COMPILE_FOR_DEVELOPMENT)
  virtual void GetInternalStats(ezStringBuilder& sb) const override;
#endif

  ezProxyAllocator m_AlignedAllocator;

  ezSimdVec4i m_vCellSize;
  ezSimdVec4f m_vOverlapSize;
  ezSimdFloat m_fInvCellSize;

  enum
  {
    MAX_NUM_GRIDS = 63,
    MAX_NUM_REGULAR_GRIDS = (sizeof(ezSpatialData::Category::m_uiValue) * 8),
    MAX_NUM_CACHED_GRIDS = MAX_NUM_GRIDS - MAX_NUM_REGULAR_GRIDS
  };

  struct Cell;
  struct Grid;
  ezDynamicArray<ezUniquePtr<Grid>> m_Grids;
  ezUInt32 m_uiFirstCachedGridIndex = MAX_NUM_GRIDS;

  /// \brief Internal data structure tracking which grids contain a spatial data object.
  struct Data
  {
    EZ_DECLARE_POD_TYPE();

    ezUInt64 m_uiGridBitmask : MAX_NUM_GRIDS; ///< Bitmask indicating which grids contain this object
    ezUInt64 m_uiAlwaysVisible : 1;           ///< Whether this object is always visible (bypasses spatial queries)
  };

  ezIdTable<ezSpatialDataId, Data, ezLocalAllocatorWrapper> m_DataTable;

  bool IsAlwaysVisibleData(const Data& data) const;

  ezSpatialDataHandle AddSpatialDataToGrids(const ezSimdBBoxSphere& bounds, ezGameObject* pObject, ezUInt32 uiCategoryBitmask, const ezTagSet& tags, bool bAlwaysVisible);

  template <typename Functor>
  void ForEachGrid(const Data& data, const ezSpatialDataHandle& hData, Functor func) const;

  struct Stats;
  using CellCallback = ezDelegate<ezVisitorExecution::Enum(const Cell&, const QueryParams&, Stats&, void*, ezVisibilityState::Enum)>;
  void ForEachCellInBoxInMatchingGrids(const ezSimdBBox& box, const QueryParams& queryParams, CellCallback noFilterCallback, CellCallback filterByTagsCallback, void* pUserData, ezVisibilityState::Enum visType) const;

  /// \brief Candidate for grid caching based on query patterns and filtering efficiency.
  struct CacheCandidate
  {
    ezTagSet m_IncludeTags;                  ///< Tags that must be included for this cached grid
    ezTagSet m_ExcludeTags;                  ///< Tags that must be excluded for this cached grid
    ezSpatialData::Category m_Category;      ///< Spatial data category for this cached grid
    float m_fQueryCount = 0.0f;              ///< How frequently this query pattern is used
    float m_fFilteredRatio = 0.0f;           ///< Ratio of objects that pass the tag filter
    ezUInt32 m_uiGridIndex = ezInvalidIndex; ///< Index of the associated grid if already cached
  };

  mutable ezDynamicArray<CacheCandidate> m_CacheCandidates;
  mutable ezMutex m_CacheCandidatesMutex;

  struct SortedCacheCandidate
  {
    ezUInt32 m_uiIndex = 0;
    float m_fScore = 0;

    bool operator<(const SortedCacheCandidate& other) const
    {
      if (m_fScore != other.m_fScore)
        return m_fScore > other.m_fScore; // higher score comes first

      return m_uiIndex < other.m_uiIndex;
    }
  };

  ezDynamicArray<SortedCacheCandidate> m_SortedCacheCandidates;

  void MigrateCachedGrid(ezUInt32 uiCandidateIndex);
  void MigrateSpatialData(ezUInt32 uiTargetGridIndex, ezUInt32 uiSourceGridIndex);

  void RemoveCachedGrid(ezUInt32 uiCandidateIndex);
  void RemoveAllCachedGrids();

  void UpdateCacheCandidate(const ezTagSet* pIncludeTags, const ezTagSet* pExcludeTags, ezSpatialData::Category category, float filteredRatio) const;
};