TAPsBVHTree.hpp

Go to the documentation of this file.

/******************************************************************************
TAPsBVHTree.hpp
******************************************************************************/
// See comment below
/******************************************************************************
SUKITTI PUNAK   (01/17/2006)
UPDATE          (10/12/2010)
******************************************************************************/
#ifndef TAPs_BVH_TREE_HPP
#define TAPs_BVH_TREE_HPP

#include "../Core/TAPsLib.hpp"
#include <set>
#include "TApsBVHNodeLeaf.hpp"
#include "TAPsBVHNodeLeafHalfEdgeAPrim.hpp"
#include "../Support/TAPsInteractionPointGroup.hpp"
#include "TAPsBVHNodeLeafALinkFormedByTwoPointMasses.hpp"
#include "../Support/TAPsTransformationSupport.hpp"

#include "TAPsMultiBoundingVolume.hpp"

BEGIN_NAMESPACE_TAPs
//=============================================================================


template <typename T>
class BVsAndNodesList {
public:
    BVsAndNodesList ( BoundingVolume<T> * pBV, std::vector< BVHNode<T> * > nodeList )
        : BV( pBV ), NodeList( nodeList )
    {}
    BoundingVolume<T> *         BV;         
    std::vector< BVHNode<T> * > NodeList;   
};


template <typename T>
class BVHTree {
//=============================================================================
// Data Members
protected:
    Enum::CD        m_eType;        
    int             m_iTotalNodes;  
    //-------------------------------------------------------------------------
    // Root Node
    BVHNode<T> *    m_pRoot;
    // Collided Nodes
    std::vector< BVHNode<T> * > m_svCollidedNode;       
    std::vector< BVHNode<T> * > m_svCollidedNodeThat;   
    std::vector< BVsAndNodesList<T> > m_svCollidedBVAndNodeList;    

    std::set< BVHNode<T> * >    m_svLeafNodes;      

    //-------------------------------------------------------------------------
    // Transformation Support
    TransformationSupport<T> &  m_Transform;    
    //Matrix4x4<T>  m_FwdTransformMatrix[2];    //!< forward transformations for collision detection
    //Matrix4x4<T>  m_InvTransformMatrix[2];    //!< inverse transformations for collision detection

    //-------------------------------------------------------------------------
//=============================================================================
// Member Functions
public:

    #ifdef  TAPs_DEBUG_COLLISION_DETECTION
    void ClearFlags ();
    void ClearFlags ( BVHNode<T> * const node );
    #endif//TAPs_DEBUG_COLLISION_DETECTION

    //-------------------------------------------------------------------------
    friend std::ostream & operator<< ( std::ostream &output, BVHTree<T> const &obj )
    {
        output  << "BVHTree<" << typeid(T).name() << ">"
                << " with " << obj.GetNumOfNodes() << " nodes"
                << " (" << obj.CountLeafNodes() << " are Leaf nodes)"
                << " and the root ptr is " << obj.m_pRoot 
                << "\n";
        return output;
    }

    std::string DisplayAllNodesAsString () const
    {
        std::string str;
        DisplayAllNodesAsString( m_pRoot, str );
        return str;
    }

    //-------------------------------------------------------------------------
    BVHTree (   TransformationSupport<T> & transform, 
                Enum::CD type = Enum::UNDEFINED_TREE, 
                int numOfNodes = 0, 
                BVHNode<T> * rootNode = NULL );

    // Constructor
    //BVHTree ( TransformationSupport<T> & transform,   //!< I/O: Transform
    //          HEFaceList<T> * heFaceList )            //!< I/P: half-edge face list
    //{}

    virtual ~BVHTree ();
    //-------------------------------------------------------------------------
    // Get/Set Fn(s)
    inline Enum::CD GetType () const    { return m_eType; }
    inline int  GetNumOfNodes () const  { return m_iTotalNodes; }
    inline void SetNumOfNodes ( int n ) { m_iTotalNodes = n; }
    inline BVHNode<T> *             Root ()         { return m_pRoot; }
    inline BVHNode<T> const * const Root () const   { return m_pRoot; }
    inline void Root ( BVHNode<T> * root )          { m_pRoot = root; }
    //int CountNumOfNodes () const = 0;
    //-------------------------------------------------------------------------
    // Get Transformation Support Fn(s)
    TransformationSupport<T> const &    GetTransform() const
        { return m_Transform; }
    TransformationSupport<T> &          GetTransform()
        { return m_Transform; }
    //-------------------------------------------------------------------------
    // Tree Operations
    //virtual CheckSelfIntersection ...
    inline int CountNodes () const;
    inline int CountLeafNodes () const;
protected:
    int CountNodes ( BVHNode<T> const * const node ) const;
    int CountLeafNodes ( BVHNode<T> const * const node ) const;

    void FindListOfLeafNodes ( BVHNode<T> * node, std::set< BVHNode<T> * > & leafNodeSet );

    std::set< BVHNode<T> * > & GetListOfLeafNodes ()
    { return m_svLeafNodes; }

    void FindListOfLeafNodes ()
    { FindListOfLeafNodes( m_pRoot, m_svLeafNodes ); }

    // Display all nodes as string (recursively)
    void DisplayAllNodesAsString ( BVHNode<T> * node, std::string & str, int level = 0 ) const;

public:
    virtual void Update ();

    virtual void Update ( std::set< BVHNode<T> * > & nodeSet );

    //=========================================================================
    // PURE VIRTUAL FNs -------------------------------------------------------
    //-------------------------------------------------------------------------
    virtual bool TestOverlapWith ( BVHTree<T> const * const that ) = 0;

    virtual bool TestOverlapWithTillLeafNodes ( BVHTree<T> const * const that ) = 0;

    virtual bool TestOverlapWith ( BVHNode<T> const * const node ) = 0;

    virtual bool TestOverlapWithTillLeafNodes ( BVHNode<T> const * const node ) = 0;

    virtual bool TestOverlapWith ( MultiBoundingVolume<T> const * const pMBV ) = 0;

    virtual bool TestOverlapWithTillLeafNodes ( MultiBoundingVolume<T> const * const pMBV ) = 0;

    virtual bool TestOverlapWith ( BoundingVolume<T> const * const pBV ) = 0;

    virtual bool TestOverlapWithTillLeafNodes ( BoundingVolume<T> const * const pBV ) = 0;

    virtual bool TestIntersectionWithLineSegmentTillLeafNodes ( Vector3<T> const * const ptA, Vector3<T> const * const ptB ) = 0;

    virtual bool TestIntersectionWithCircleTillLeafNodes ( Vector3<T> const * const circleNormalPlane, Vector3<T> const * const circleCenter, T circleRadius ) = 0;

    virtual bool TestOverlapWith (
        InteractionPointGroup<T> * const    pIPG,           
        std::vector< PointForce<T> > & ListOfPointForces    
    ) = 0;

    virtual bool TestOverlapWithTillLeafNodes (
        InteractionPointGroup<T> * const    pIPG,           
        std::vector< PointForce<T> > & ListOfPointForces    
    ) = 0;

    //-------------------------------------------------------------------------
    // PURE VIRTUAL FNs -------------------------------------------------------
    //=========================================================================

    //-------------------------------------------------------------------------
    // Collided Nodes
    virtual std::vector< BVHNode<T> * > & GetListOfCollidedNodes ()     { return m_svCollidedNode; }
    virtual std::vector< BVHNode<T> * > & GetListOfCollidedNodesThat () { return m_svCollidedNodeThat; }
    virtual std::vector< BVsAndNodesList<T> > & GetListOfCollidedBoundingVolumesAndNodes () { return m_svCollidedBVAndNodeList; }
    //-------------------------------------------------------------------------

protected:

    //void CalAndSaveTransformations ( BoundingVolume<T> const * const pBV );
    //void CalAndSaveTransformations ( BoundingVolume<T> const * const pBV, Matrix4x4<T> const & transformB );
    //void CalAndSaveTransformations ( Matrix4x4<T> const & transformA, BoundingVolume<T> const * const pBV );
    //void CalAndSaveTransformations ( Matrix4x4<T> const & transformA, BoundingVolume<T> const * const pBV, Matrix4x4<T> const & transformB );

    /*
    //=========================================================================
    // Test Overlap with a MultiBoundingVolume
    //-------------------------------------------------------------------------
    virtual bool TestOverlap_vs_MBV ( 
                    BVHNode<T> const * const nodeA, 
                    Matrix4x4<T> const & transformA, 
                    MultiBoundingVolume<T> const * const pMBV, 
                    Matrix4x4<T> const & transformB )           = 0;
    //-------------------------------------------------------------------------
    virtual bool TestOverlap_vs_MBV_TillLeafNodes ( 
                    BVHNode<T> const * const nodeA, 
                    Matrix4x4<T> const & transformA, 
                    MultiBoundingVolume<T> const * const pMBV, 
                    Matrix4x4<T> const & transformB )           = 0;
    //-------------------------------------------------------------------------
    //=========================================================================
    //*/

    //*
    //=========================================================================
    // Test Overlap with a BoundingVolume
    //-------------------------------------------------------------------------
    virtual bool TestOverlap_vs_BV ( 
                    BVHNode<T> const * const nodeA, 
                    Matrix4x4<T> const & transformA, 
                    BoundingVolume<T> const * const pBV, 
                    Matrix4x4<T> const & transformB )       = 0;
    //-------------------------------------------------------------------------
    virtual bool TestOverlap_vs_BV_TillLeafNodes ( 
                    BVHNode<T> const * const nodeA, 
                    Matrix4x4<T> const & transformA, 
                    BoundingVolume<T> const * const pBV, 
                    Matrix4x4<T> const & transformB )       = 0;
    //-------------------------------------------------------------------------
    //=========================================================================
    //*/

    //=========================================================================
    // Test Overlap with Another BVHTree_BinarySphere
    //-------------------------------------------------------------------------
    virtual bool TestOverlap_vs_BinarySphere ( 
                    BVHNode<T> const * const nodeA, 
                    Matrix4x4<T> const & transformA, 
                    BVHNode<T> const * const nodeB, 
                    Matrix4x4<T> const & transformB )   = 0;
    //-------------------------------------------------------------------------
    virtual bool TestOverlap_vs_BinarySphere_TillLeafNodes ( 
                    BVHNode<T> const * const nodeA, 
                    Matrix4x4<T> const & transformA, 
                    BVHNode<T> const * const nodeB, 
                    Matrix4x4<T> const & transformB )   = 0;
    //-------------------------------------------------------------------------
    //=========================================================================

    /*
    //=========================================================================
    // Test Overlap with Another BVHTree_BinaryAABB
    //-------------------------------------------------------------------------
    virtual bool TestOverlap_vs_BinaryAABB ( 
                    BVHNode<T> const * const nodeA, 
                    Matrix4x4<T> const & transformA, 
                    BVHNode<T> const * const nodeB, 
                    Matrix4x4<T> const & transformB )   = 0;
    //-------------------------------------------------------------------------
    virtual bool TestOverlap_vs_BinaryAABB_TillLeafNodes ( 
                    BVHNode<T> const * const nodeA, 
                    Matrix4x4<T> const & transformA, 
                    BVHNode<T> const * const nodeB, 
                    Matrix4x4<T> const & transformB )   = 0;
    //-------------------------------------------------------------------------
    //=========================================================================
    //*/

    /*
    //=========================================================================
    // Test Overlap with Another BVHTree_BinaryOBB
    //-------------------------------------------------------------------------
    virtual bool TestOverlap_vs_BinaryOBB ( 
                    BVHNode<T> const * const nodeA, 
                    Matrix4x4<T> const & transformA, 
                    BVHNode<T> const * const nodeB, 
                    Matrix4x4<T> const & transformB )   = 0;
    //-------------------------------------------------------------------------
    virtual bool TestOverlap_vs_BinaryOBB_TillLeafNodes ( 
                    BVHNode<T> const * const nodeA, 
                    Matrix4x4<T> const & transformA, 
                    BVHNode<T> const * const nodeB, 
                    Matrix4x4<T> const & transformB )   = 0;
    //-------------------------------------------------------------------------
    //=========================================================================
    //*/

protected:
    //=========================================================================
    // BINARY ORIENTED BOUNDING BOX (0BB) HIERARCHY TREE
    //-------------------------------------------------------------------------
    // Create Binary OBB Tree
    static BVHTree<T> * BOBBBuild (
      TransformationSupport<T> & transform, // I/O: Transform
      const std::list< HEFace<T> * > & heFaceList,  // I/P: half-edge face list
      BVHTree<T> * cdtree );                        // O/P: pointer to BVHTree
    //-------------------------------------------------------------------------
    // Create Binary Child OBBs
    static void BOBBBuildChildren ( BVHNode<T> * pParentNode, 
                    const std::list< HEFace<T> * > & heFaceList, 
                    Vector3<T> const & principleVector );
    //-------------------------------------------------------------------------
    // Find the group that this face belongs to
    static int BOBBDetermineFaceGroup ( 
                    HEFace<T> * face, 
                    const Vector3<T> & center, 
                    const Vector3<T> & direction );
    static void BOBBDivideToFaceGroups ( 
                    const std::list< HEFace<T> * > & faces, // input
                    std::list< HEFace<T> * > & group1,      // output group1
                    std::list< HEFace<T> * > & group2,      // output group2
                    const Vector3<T> & center, 
                    const Vector3<T> & direction );
    //-------------------------------------------------------------------------
    // Create a new OBB bounding volume node from the face list
    static BVHNode<T> * CreateBVHNodeBOBB ( 
                    BVHNode<T> * pParentNode, 
                    const std::list< HEFace<T> * > & heFaceList );
    //-------------------------------------------------------------------------
    //=========================================================================

    //=========================================================================
    // BINARY AXIS-ALIGNED BOUNDING BOX (AABB) HIERARCHY TREE
    //-------------------------------------------------------------------------
    // Create Binary AABB Tree
    static BVHTree<T> * BAABBBuild (
      TransformationSupport<T> & transform, // I/O: Transform
      const std::list< HEFace<T> * > & heFaceList,  // I/P: half-edge face list
      BVHTree<T> * cdtree );                        // O/P: pointer to BVHTree
    //-------------------------------------------------------------------------
    // Create Binary Child AABBs
    static void BAABBBuildChildren (    BVHNode<T> * pParentNode, 
                    const std::list< HEFace<T> * > & heFaceList, 
                    Vector3<T> const & principleVector );
    //-------------------------------------------------------------------------
    // Find the group that this face belongs to
    static int BAABBDetermineFaceGroup ( 
                    HEFace<T> * face, 
                    const Vector3<T> & center, 
                    const Vector3<T> & direction );
    static void BAABBDivideToFaceGroups ( 
                    const std::list< HEFace<T> * > & faces, // input
                    std::list< HEFace<T> * > & group1,      // output group1
                    std::list< HEFace<T> * > & group2,      // output group2
                    const Vector3<T> & center, 
                    const Vector3<T> & direction );
    //-------------------------------------------------------------------------
    // Create a new AABB bounding volume node from the face list
    static BVHNode<T> * CreateBVHNodeBAABB ( 
                    BVHNode<T> * pParentNode, 
                    const std::list< HEFace<T> * > & heFaceList );
    //-------------------------------------------------------------------------
    //=========================================================================

    //=========================================================================
    // This fn is used for dividing the face list into two groups according to
    // the longest principle component
    // Used by BINARY OBB    BOUNDING VOLUME HIERARCHY TREE
    //         BINARY SPHERE BOUNDING VOLUME HIERARCHY TREE
    //         BINARY AABB   BOUNDING VOLUME HIERARCHY TREE
    //-------------------------------------------------------------------------
    // Find OOB (Oriented Bounding Box) (see OBB of Gottschalk, et al.)
    static void FindOBBOfFaceList ( 
            const std::list< HEFace<T> * > & heFaceList,    // I/P: face list
            Vector3<T> & center,    // I/P: center
            Vector3<T> & U,         // O/P: 1st principle component
            Vector3<T> & V,         // O/P: 2nd principle component
            Vector3<T> & W );       // O/P: 3rd principle component
    //-------------------------------------------------------------------------
    //=========================================================================

    //=========================================================================
    // QUAD SPHERE BOUNDING VOLUME HIERARCHY TREE
    //-------------------------------------------------------------------------
    //-------------------------------------------------------------------------
    //=========================================================================

    //=========================================================================
    // OCTANT SPHERE BOUNDING VOLUME HIERARCHY TREE
    //-------------------------------------------------------------------------
    //-------------------------------------------------------------------------
    //=========================================================================

    //=========================================================================
#if defined(__gl_h_) || defined(__GL_H__)
public:
    // DrawByOpenGL
    virtual void Draw () const  { DrawByOpenGL(); }
    virtual void DrawByOpenGL () const;
    virtual void DrawByOpenGL ( int currentLevel, int startLevel, int endLevel ) const;
    virtual void DrawByOpenGLOnlyEndLevel () const;
    virtual void DrawByOpenGLCollidedNodes () const;
    virtual void DrawByOpenGLCollidedNodesThat ( TransformationSupport<T> const & transformSupport ) const;
#endif
    //-------------------------------------------------------------------------
}; // END CLASS BVHTree
//=============================================================================
END_NAMESPACE_TAPs
//-----------------------------------------------------------------------------
// Include definition if TAPs_USE_EXPORT is not defined
//#if !defined( TAPs_USE_EXPORT )
    #include "TAPsBVHTree.cpp"
//#endif
//-----------------------------------------------------------------------------
#endif
//34567890123456789012345678901234567890123456789012345678901234567890123456789
//--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----