GxOctree.h

Go to the documentation of this file.

//===========================================================================
//===========================================================================
#pragma once
 
GX_CORE_NAMESPACE_BEGIN()
 
#define GX_RIGHT_HAND 1
 
//---- 空間グラフ(８分木)のタイプ
// 並列実行で構築。変更前の状態。同期オブジェクト数==ノード数
#define GX_OCTREE_ASYNC 0
// 逐次実行で構築。同期オブジェクト数==0。
#define GX_OCTREE_SEQUENCE 1
// 並列実行で構築。同期オブジェクト数 == 1
#define GX_OCTREE_STATIC 2
// 並列実行で構築。同期オブジェクト数 == 任意
#define GX_OCTREE_POOL 3
 
#define GX_OCTREE_TYPE GX_OCTREE_POOL
 
// 開発用：ノード数をカウントする
#if GX_DEVELOP
#define GX_OCTREE_INFO 1
#else //GX_DEVELOP
#define GX_OCTREE_INFO 0
#endif // !GX_DEVELOP
 
//===========================================================================
//===========================================================================
class GxOctree : public GxClassBase
{
    //-------------------------------------------------------------
    //-------------------------------------------------------------
public:
    GX_RTTI_CLASS(GxOctree, GxClassBase)
    // GxClassBase継承クラス用禁止宣言
    GX_PROHIBIT_CLASS_BASE(GxOctree)
    // ノードクラス
    class GxNode;
 
    //-------------------------------------------------------------
    //-------------------------------------------------------------
 
    GxOctree(void);
    GxOctree(GxAllocatorList::ALLOCATOR_TYPE allocateType);
 
    ~GxOctree(void) override;
 
    //-------------------------------------------------------------
    //-------------------------------------------------------------
protected:
    virtual GxOctree::GxNode* allocateNode(void);
 
    constexpr u32 part1By2(u32 value) const
    {
        value = (value ^ (value << 16) ) & 0xFF0000FF;
        value = (value ^ (value <<  8) ) & 0x0300F00F;
        value = (value ^ (value <<  4) ) & 0x030C30C3;
        value = (value ^ (value <<  2) ) & 0x09249249;
        return value;
    }
 
    void queryHighLevel(s32& levelCount, u32& arExorN, const GxVector3& min, const GxVector3& max ) const;
 
    void queryLowerLevelSpaces(const GxVector3& leftTopBack, const u32& initialAABB, const u32& aunParentLevelN, const u32& aunParentSpace, b32* pDirtyFlags );
 
public:
    b32 findObject( GxClassBaseRoot* pObject ) const;
    b32 addObject( GxClassBaseRoot* pObject, const GxVector3& min, const GxVector3& max );
    b32 eraseObject( GxClassBaseRoot* pObject, const GxVector3& min, const GxVector3& max );
    void eraseAllObject(void);
 
    virtual b32 windowQueryForBB(GxArray& arvSpaces, const GxVector3& min, const GxVector3& max);
 
#if (GX_OCTREE_TYPE == GX_OCTREE_POOL)
    void initialize(u32 level, GxVector3& min, GxVector3& max, u32 levelNonShared = 0, u32 numCsecShared = 10);
#else //(GX_OCTREE_TYPE == GX_OCTREE_POOL)
    void initialize(u32 level, GxVector3& min, GxVector3& max);
#endif //(GX_OCTREE_TYPE != GX_OCTREE_POOL)
 
    virtual void beginBuildTree( void );
 
    virtual void finishBuildTree( void );
 
    b32 updateTreeSize(GxVector3& min, GxVector3& max);
 
    virtual void eraseTree(void);
 
    GX_FORCE_INLINE void startCulling(void){ _criticalSectionRegist.lock(); _inCulling = true; _criticalSectionRegist.unlock();}
    GX_FORCE_INLINE void endCulling(void){ _criticalSectionRegist.lock(); _inCulling = false; _criticalSectionRegist.unlock(); }
private:
    void initialize(u32 level);
#if (GX_OCTREE_TYPE == GX_OCTREE_POOL)
    // note:必要に応じてpublic化
    void    createCriticalSectionNode(u32 levelNonShare, u32 numCriticalSectionShared);
    void    deleteCriticalSectionNode(void);
#endif // (GX_OCTREE_TYPE == GX_OCTREE_POOL)
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
public:
    u32 getPointMortonCode(const f32& x, const f32& y, const f32& z) const;
 
    u32 getBBMortonCode(const GxVector3& min, const GxVector3& max) const;
 
    u32 getMortonCode(const u32& x, const u32& y, const u32& z) const;
 
    GX_FORCE_INLINE b32 isRegisting(void) const { return _inCulling; }
 
    virtual b32 isEmpty(void) const { return _pGlobalObjectList == nullptr || _pGlobalObjectList->getCount() == 0; }
 
    GX_FORCE_INLINE         GxArray&    getNodeArray(void)          { return _nodePointerArray; }
    GX_FORCE_INLINE const   GxArray&    getNodeArray(void) const    { return _nodePointerArray; }
 
    GX_FORCE_INLINE         GxVector3&  getUnitLength(void)         { return _unitLength; }
    GX_FORCE_INLINE const   GxVector3&  getUnitLength(void) const   { return _unitLength; }
 
    GX_FORCE_INLINE         GxVector3&  getMin(void)        { return _leftTopBack; }
    GX_FORCE_INLINE const   GxVector3&  getMin(void) const  { return _leftTopBack; }
 
    GX_FORCE_INLINE         GxVector3&  getMax(void)        { return _rightBottomFront; }
    GX_FORCE_INLINE const   GxVector3&  getMax(void) const  { return _rightBottomFront; }
 
    constexpr u32 getTreeLevel(void) const { return _level; }
 
    constexpr u32 getNodeCount(void) const { return _nodePointerArray.getCount(); }
 
    GX_FORCE_INLINE const u32 getLeafNodeCount(u32 leaf) const { GX_ASSERT( leaf <= _level,"level over flow"); return getNodeCount() - getElementIndex(leaf, 0); }
 
    GX_FORCE_INLINE const u32 getUnitNodeCount(const u32& level)  const { return _pUnitCount[level]; }
 
    constexpr GxArray* getGlobalObjectList(void) const { return _pGlobalObjectList; }
protected:
    GX_FORCE_INLINE const u32 getElementIndex(const u32& level, const u32& localIndex) const { return (_pStartIndex[level] + localIndex); }
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
protected:
    u32         _level;                 //<! ツリーの深さ
    u32*        _pStartIndex;           //<! ツリーノードのオフセットインデックス
    u32*        _pUnitCount;            //<! 各軸上の分割数
    
    GxVector3   _leftTopBack;           //<!　x,y,z  左上奥Left, Top, Back
    GxVector3   _rightBottomFront;      //<!  x,y,z　右下手前Right, Bottom, Front
    GxVector3   _unitLength;            //<!　x,y,z  単位長さ
 
    GxArray     _nodePointerArray;                  //<!  線形8分木ノードリスト
    b32*        _pTemporaryFind;                    //<!  探索に利用するフラグ、探索するごとにメモリ確保する時間が惜しいので、最初に確保
    b32*        _pDirtyFlags[GxThread::THREAD_MAX]; //<!  探索に利用するフラグ、探索するごとにメモリ確保する時間が惜しいので、最初に確保
 
    GxArray*    _pGlobalObjectList;     
    GxCriticalSection   _criticalSectionArray;      //<!  リスト用クリティカルセクション
    GxCriticalSection   _criticalSectionRegist;     //<!  カリング処理実行中は登録／削除処理をロックする
    b32                 _inCulling;
    GxAllocatorList::ALLOCATOR_TYPE _allocatorType; 
 
#if (GX_OCTREE_TYPE == GX_OCTREE_POOL)
private:
    u32 _levelNonShare;
    u32 _numCriticalSectionShared;
    u32 _numCriticalSectionNonShared;
 
    GxCriticalSection** _ppCriticalSectionNodeShared;
    GxCriticalSection** _ppCriticalSectionNodeNonShared;
#endif // (GX_OCTREE_TYPE == GX_OCTREE_POOL)
 
};
 
//===========================================================================
//===========================================================================
class GxOctree::GxNode :  public GxClassBase
{
    //-------------------------------------------------------------
    //-------------------------------------------------------------
public:
    GX_RTTI_CLASS(GxOctree::GxNode, GxClassBase)
    friend GxOctree;
 
    //-------------------------------------------------------------
    //-------------------------------------------------------------
 
    GxNode(void);
    ~GxNode(void) override;
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
 
    b32 addObject( GxClassBaseRoot* pObject );
 
    b32 deleteObject(GxClassBaseRoot* pObject);
 
    b32 findObject(GxClassBaseRoot* pObject) const;
 
    void clearObjects(void);
 
#if (GX_OCTREE_TYPE != GX_OCTREE_SEQUENCE)
#if (GX_OCTREE_TYPE == GX_OCTREE_POOL)
public:
    constexpr void setCriticalSectionArray(GxCriticalSection* pCriticalSection) { _pCriticalSectionArray = pCriticalSection; }
#endif // (GX_OCTREE_TYPE == GX_OCTREE_POOL)
protected:
    void setLock(void);
    void setUnlock(void);
#endif // (GX_OCTREE_TYPE != GX_OCTREE_SEQUENCE)
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
public:
    GX_FORCE_INLINE virtual b32 isEmpty(void) const { return _pObjectList->getCount() == 0; }
 
    constexpr GxArray* getObjectList( void ) const { return _pObjectList; }
 
    GX_FORCE_INLINE             GxShapeAxisAlignedBox&   getBoudingBox( void )          { return _aabb; }
    GX_FORCE_INLINE     const   GxShapeAxisAlignedBox&   getBoudingBox( void )  const   { return _aabb; }
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
private:
    GxArray* _pObjectList;          //<!　オブジェクトリスト
    GxShapeAxisAlignedBox _aabb;    //<!  オクタントのAABB
#if (GX_OCTREE_TYPE != GX_OCTREE_SEQUENCE)
#if (GX_OCTREE_TYPE == GX_OCTREE_ASYNC)
protected:
    GxCriticalSection _criticalSectionArray;            //<!  リスト用クリティカルセクション
#elif (GX_OCTREE_TYPE == GX_OCTREE_STATIC)
protected:
    static GxCriticalSection _criticalSectionArray;     //<!  リスト用クリティカルセクション
#endif // (GX_OCTREE_TYPE != GX_OCTREE_STATIC)
#if (GX_OCTREE_TYPE == GX_OCTREE_POOL)
private:
    GxCriticalSection* _pCriticalSectionArray;          //<!  リスト用クリティカルセクション
#endif // (GX_OCTREE_TYPE == GX_OCTREE_POOL)
#endif // (GX_OCTREE_TYPE != GX_OCTREE_SEQUENCE)
 
};
 
GX_CORE_NAMESPACE_END()