TAPsBVHNode.hpp

Go to the documentation of this file.

/******************************************************************************
TAPsBVHNode.hpp

SUKITTI PUNAK   (01/17/2006)
UPDATE          (10/08/2010)
******************************************************************************/
#ifndef TAPs_BVH_NODE_HPP
#define TAPs_BVH_NODE_HPP

#include "../Core/TAPsLib.hpp"

#include "../GeometricDataStructure/HalfEdge/TAPsHalfEdgeDataStructure.hpp" // DEBUG
#include "../GeometricDataStructure/TAPsFace.hpp"   // DEBUG
//#include <list>   // DEBUG

template <typename T> class BVHTree;

//=============================================================================
// Enable collision detection on/off status
//-----------------------------------------------------------------------------
//#define TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS
//-----------------------------------------------------------------------------
#ifdef  TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS
#endif//TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS
//=============================================================================

BEGIN_NAMESPACE_TAPs
//=============================================================================
template <typename T>
class BVHNode {
//=============================================================================
// Data Members
    friend class BVHTree<T>;
protected:
    //--------------------------------------------------------------------
    // Data
    Enum::CD        m_eType;        
    //bool          m_bIsLeaf;      //!< flag for a leaf node
    int             m_iID;          
    BVHNode<T> *    m_pParent;      
    BVHNode<T> **   m_ppChild;      
    int             m_iN;           
    //--------------------------------------------------------------------
    Vector3<T>  m_vCenter;
    //--------------------------------------------------------------------
    //          OBB         AABB        Sphere
    //--------------------------------------------------------------------
    Vector3<T>  m_vU;   //
    Vector3<T>  m_vV;   
    Vector3<T>  m_vW;   
    //--------------------------------------------------------------------
    // Using "union" Doesn't Work!
    //      OBB                 AABB                    Sphere
    //union {   Vector3<T> m_vU;    Vector3<T> m_vMin;  };
    //union {   Vector3<T> m_vV;    Vector3<T> m_vMax;  };
    //union {   Vector3<T> m_vW;                        T m_tRadius;    };
    // Sphere uses the x component of m_vW
    //--------------------------------------------------------------------
    // Working but with unused space
    //          Sphere
    //T     m_tRadius;
    //--------------------------------------------------------------------
    //          AABB
    //Vector3<T>    m_vMin, m_vMax;
    //--------------------------------------------------------------------
    //          OBB
    //Vector3<T>    m_vU, m_vV, m_vW;
    //--------------------------------------------------------------------
#ifdef  TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS
    bool    m_bOnForColDet;     
#endif//TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS

public:
    //std::list< HEFace<T> * > listHEFace;  // DEBUG
//=============================================================================
// Member Functions
public:

    #ifdef  TAPs_DEBUG_COLLISION_DETECTION
    bool    flag;
    #endif//TAPs_DEBUG_COLLISION_DETECTION

    //-------------------------------------------------------------------------
    // Output Operator <<
    friend std::ostream & operator<< ( std::ostream &output, BVHNode<T> const &node )
    {
        return output << node.StrInfo();

        for ( int i = 0; i < node.m_iN; ++i ) {
            output << "\n\tChild Ptr#" << node.m_iN << ": " << node.m_ppChild[i];
        }
        //-----------------------------------------------------------
        // Output the node info
        output << "\nThe node type is ";
        switch ( node.m_eType ) {
            case Enum::UNDEFINED_NODE:
                output << "UNDEFINED_NODE.";
                break;
            case Enum::BVH_NODE_BINARY_SPHERE:
                output  << "BVH_NODE_BINARY_SPHERE." 
                        << "  With Center at (" << node.m_vCenter[0] << ", " 
                        << node.m_vCenter[1] << ", " << node.m_vCenter[2] 
                        <<   ") and radius of " << node.m_vW[0];
                break;
            default:
                output << "\nUnrecognized Node!";
                break;
        }
        output  << "\n";
        return output;
    }
    //-------------------------------------------------------------------------
    BVHNode ( Enum::CD type, 
              int id                 = -1, 
              BVHNode<T> * parent    = NULL, 
              BVHNode<T> ** children = NULL );
    BVHNode ( int numOfChildren, 
              Enum::CD type, 
              int id                 = -1, 
              BVHNode<T> * parent    = NULL, 
              BVHNode<T> ** children = NULL );
protected:
    BVHNode ( Enum::CD type, 
              int id, 
              BVHNode<T> * parent, 
              Vector3<T> const & center, 
              Vector3<T> const & U, 
              Vector3<T> const & V, 
              Vector3<T> const & W );
    //-------------------------------------------------------------------------
    BVHNode ( int id, 
              Enum::CD type, 
              BVHNode<T> * parent = NULL );
    //-------------------------------------------------------------------------
public:
    virtual ~BVHNode ();
    //-------------------------------------------------------------------------
    virtual std::string StrInfo () const;
protected:
    //-------------------------------------------------------------------------
    void InitChildren ( Enum::CD type,     BVHNode<T> ** children = NULL );
    void InitChildren ( int numOfChildren, BVHNode<T> ** children = NULL );
public:
    //-------------------------------------------------------------------------
    // Get/Set Fn(s)
    //---------------------------------------------------------------

#ifdef  TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS
    bool GetOnStatus () const   { return m_bOnForColDet; }
    void SetOnStatus ( bool b ) { m_bOnForColDet = b; }
    void ToggleOnStatus ()      { m_bOnForColDet = !m_bOnForColDet; }
#endif//TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS

public:
    inline int  GetType () const { return m_eType; }
    virtual inline bool IsLeaf () const     { return 0 == m_iN; }
    virtual inline bool IsNotLeaf () const  { return 0 != m_iN; }
protected:
    inline void SetType ( Enum::CD type ) { m_eType = type; }
public:
    inline int  GetID () const { return m_iID; }
protected:
    inline void SetID ( int id ) { m_iID = id; }
    //---------------------------------------------------------------
    // Get/Set for Parent Pointer
public:
    inline BVHNode<T> const * const Parent () const { return m_pParent; }
protected:
    inline BVHNode<T> * Parent () { return m_pParent; }
    inline void Parent ( BVHNode<T> * parent )  { m_pParent = parent; }
    //---------------------------------------------------------------
    // Get/Set for Child Pointers
public:
    inline int GetNumOfChildren () const    { return m_iN; }
    inline virtual BVHNode<T> const * const Child ( int i ) const
        { assert ( 0 <= i && i < m_iN );    return m_ppChild[i]; }
        /*{
            if ( 0 <= i && i < m_iN )   return m_ppChild[i];
            else                        return NULL;
        }//*/
//protected:
    inline virtual BVHNode<T> * Child ( int i )
        { assert ( 0 <= i && i < m_iN );    return m_ppChild[i]; }
        /*{
            if ( 0 <= i && i < m_iN )   return m_ppChild[i];
            else                        return NULL;
        }//*/
    inline void Child  ( int i, BVHNode<T> * pChild )
        { assert ( 0 <= i && i < m_iN );    m_ppChild[i] = pChild; }
    //---------------------------------------------------------------
    // Get/Set Sphere Bounding Volume
public:
    inline Vector3<T> const & GetCenter () const { return m_vCenter; }
//protected:
    inline Vector3<T> & GetCenter () { return m_vCenter; }
    inline void SetCenter ( Vector3<T> const & center ) { m_vCenter = center; }
    inline void SetCenter ( T x, T y, T z ) { m_vCenter.SetXYZ( x, y, z ); }
public:
    // m_vW[0] is m_tRadius
    inline T GetRadius () const {return m_vW[0]; }
//protected:
    // m_vW[0] is m_tRadius
    inline void SetRadius ( T radius ) { m_vW[0] = radius; }
    //---------------------------------------------------------------
    // Get/Set OBB Bounding Volume
public:
    inline Vector3<T> const & Get1stPrincipleComponent () const
        { return m_vU; }
    inline Vector3<T> const & Get2ndPrincipleComponent () const
        { return m_vV; }
    inline Vector3<T> const & Get3rdPrincipleComponent () const
        { return m_vW; }
    inline void GetPrincipleComponents ( 
        Vector3<T> & U, Vector3<T> & V, Vector3<T> & W ) const
        { U = m_vU; V = m_vV; W = m_vW; }
protected:
    inline void Set1stPrincipleComponent ( Vector3<T> const & v )
        { m_vU = v; }
    inline void Set2ndPrincipleComponent ( Vector3<T> const & v )
        { m_vV = v; }
    inline void Set3rdPrincipleComponent ( Vector3<T> const & v )
        { m_vW = v; }
    inline void SetPrincipleComponents ( 
        Vector3<T> const & U, Vector3<T> const & V, Vector3<T> const & W )
        { m_vU = U; m_vV = V; m_vW = W; }
    //---------------------------------------------------------------
    // Get/Set ABB Bounding Volume
public:
    inline Vector3<T> const & GetMinPt () const     { return m_vV; }
    inline Vector3<T> const & GetMaxPt () const     { return m_vW; }
protected:
    inline void SetMinPt ( Vector3<T> const & v )   { m_vV = v; }
    inline void SetMaxPt ( Vector3<T> const & v )   { m_vW = v; }
    //---------------------------------------------------------------
    // Get Primitive(s)
public:
    inline virtual HEFace<T> *  GetAPrimitiveHalfEdgeFace () const
        { return NULL; }
    inline virtual Face<T> *    GetAPrimitiveFace () const
        { return NULL; }
    //-------------------------------------------------------------------------
    // Node Operations
public:
    //-------------------------------------------------------------------------
    virtual void Update ();
    //-------------------------------------------------------------------------
//  virtual T TestOverlapWith ( BVHNode<T> const * const that ) const;
    //-------------------------------------------------------------------------
//  virtual T TestOverlapWithNoPrimitiveTests ( BVHNode<T> const * const that ) const;
    //-------------------------------------------------------------------------
public:
    //=========================================================================
    // Sphere-Sphere Intersection Test (BinarySphereTree vs BinarySphereTree)
    //-------------------------------------------------------------------------
    inline virtual T TestOverlapSphereWithSphere ( 
                        BVHNode<T> const * const that       
                    ) const;
    inline virtual T TestOverlapSphereWithSphere ( 
                        BVHNode<T> const * const that,      
                        Matrix4x4<T> const & thatTransform  
                    ) const;
    inline virtual T TestOverlapSphereWithSphere ( 
                        Matrix4x4<T> const & thisTransform, 
                        BVHNode<T> const * const that       
                    ) const;
    inline virtual T TestOverlapSphereWithSphere ( 
                        Matrix4x4<T> const & thisTransform, 
                        BVHNode<T> const * const that,      
                        Matrix4x4<T> const & thatTransform  
                    ) const;
    //-------------------------------------------------------------------------
    inline T TestOverlapSphereWithSphere_NoPrimitiveTests ( 
                        BVHNode<T> const * const that       
                    ) const;
    inline T TestOverlapSphereWithSphere_NoPrimitiveTests ( 
                        BVHNode<T> const * const that,      
                        Matrix4x4<T> const & thatTransform  
                    ) const;
    inline T TestOverlapSphereWithSphere_NoPrimitiveTests ( 
                        Matrix4x4<T> const & thisTransform, 
                        BVHNode<T> const * const that       
                    ) const;
    inline T TestOverlapSphereWithSphere_NoPrimitiveTests ( 
                        Matrix4x4<T> const & thisTransform, 
                        BVHNode<T> const * const that,      
                        Matrix4x4<T> const & thatTransform  
                    ) const;
    //-------------------------------------------------------------------------

    //=========================================================================
    // Primitive-Primitive Intersection Test
    //-------------------------------------------------------------------------
    //inline virtual T TestOverlapPrimitiveWithPrimitive ( BVHNode<T> const * const that ) const;
    //inline virtual T TestOverlapPrimitiveWithPrimitive ( BVHNode<T> const * const that, 
    //                                      Matrix4x4<T> const & thatTransform ) const;
    //inline virtual T TestOverlapPrimitiveWithPrimitive ( Matrix4x4<T> const & thisTransform, 
    //                                      BVHNode<T> const * const that ) const;
    //inline virtual T TestOverlapPrimitiveWithPrimitive ( Matrix4x4<T> const & thisTransform, 
    //                                      BVHNode<T> const * const that, 
    //                                      Matrix4x4<T> const & thatTransform ) const;
    //-------------------------------------------------------------------------

    //=========================================================================
    // Sphere-BVSphere Intersection Test (BinarySphereTree vs Sphere BV)
    //-------------------------------------------------------------------------
    inline T TestOverlapSphereWithBVSphere_NoPrimitiveTests ( 
                        Vector3<T> const & centerOfBVSphere,    
                        T radiusOfBVSphere                      
                    ) const;
    inline T TestOverlapSphereWithBVSphere_NoPrimitiveTests ( 
                        Matrix4x4<T> const & transformA,        
                        Vector3<T> const & centerOfBVSphere,    
                        T radiusOfBVSphere                      
                    ) const;
    //-------------------------------------------------------------------------
    inline virtual T TestOverlapSphereWithBVSphere ( 
                        Vector3<T> const & centerOfBVSphere,    
                        T radiusOfBVSphere                      
                    ) const
    {
        // Same as testing TestOverlapSphereWithBVSphere_NoPrimitiveTests(), since it is not a leaf node.
        // Must be overrided by its subclass for primitive-primitive test.
        return TestOverlapSphereWithBVSphere_NoPrimitiveTests( centerOfBVSphere, radiusOfBVSphere );
    }
    inline virtual T TestOverlapSphereWithBVSphere ( 
                        Matrix4x4<T> const & transformA,        
                        Vector3<T> const & centerOfBVSphere,    
                        T radiusOfBVSphere                      
                    ) const
    {
        // Same as testing TestOverlapSphereWithBVSphere_NoPrimitiveTests(), since it is not a leaf node.
        // Must be overrided by its subclass for primitive-primitive test.
        return TestOverlapSphereWithBVSphere_NoPrimitiveTests( transformA, centerOfBVSphere, radiusOfBVSphere );
    }
    //-------------------------------------------------------------------------

    //=========================================================================
    // Sphere-BVCylinder Intersection Test (BinarySphereTree vs Cylinder BV)
    //-------------------------------------------------------------------------
    inline bool TestOverlapSphereWithBVCylinder_AtOrigin_NoPrimitiveTests ( 
                        T radiusOfBVCylinder,                   
                        T heightOfBVCylinder                    
                    ) const;
    inline bool TestOverlapSphereWithBVCylinder_AtOrigin_NoPrimitiveTests ( 
                        Matrix4x4<T> const & transformA,        
                        T radiusOfBVCylinder,                   
                        T heightOfBVCylinder                    
                    ) const;
    //-------------------------------------------------------------------------
    inline virtual bool TestOverlapSphereWithBVCylinder_AtOrigin ( 
                        T radiusOfBVCylinder,                   
                        T heightOfBVCylinder                    
                    ) const
    {
        // Same as testing TestOverlapSphereWithBVSphere_NoPrimitiveTests(), since it is not a leaf node.
        // Must be overrided by its subclass for primitive-primitive test.
        return TestOverlapSphereWithBVCylinder_AtOrigin_NoPrimitiveTests( radiusOfBVCylinder, heightOfBVCylinder );
    }
    inline virtual bool TestOverlapSphereWithBVCylinder_AtOrigin ( 
                        Matrix4x4<T> const & transformA,        
                        T radiusOfBVCylinder,                   
                        T heightOfBVCylinder                    
                    ) const
    {
        // Same as testing TestOverlapSphereWithBVSphere_NoPrimitiveTests(), since it is not a leaf node.
        // Must be overrided by its subclass for primitive-primitive test.
        return TestOverlapSphereWithBVCylinder_AtOrigin_NoPrimitiveTests( transformA, radiusOfBVCylinder, heightOfBVCylinder );
    }
    //-------------------------------------------------------------------------

    //-------------------------------------------------------------------------
#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;
    //---------------------------------------------------------------
//protected:
public: // DEBUG
    virtual void DrawBV ( GLenum drawStyle = GLU_LINE ) const;
    virtual void DrawPrim ( GLenum drawStyle = GLU_LINE ) const {}; // DEBUG
protected:
    virtual void DrawSphereBV ( GLenum drawStyle = GLU_LINE ) const;
    virtual void DrawAABBBV ( GLenum drawStyle = GLU_LINE ) const;
    virtual void DrawOBBBV ( GLenum drawStyle = GLU_LINE ) const;
    //---------------------------------------------------------------
    static GLuint   m_uiDisplayList;        // for OpenGL (sphere) drawing
#endif
    //-------------------------------------------------------------------------
}; // END CLASS BVHNode
//=============================================================================
END_NAMESPACE_TAPs
//-----------------------------------------------------------------------------
// Include definition if TAPs_USE_EXPORT is not defined
//#if !defined( TAPs_USE_EXPORT )
    #include "TAPsBVHNode.cpp"
//#endif
//-----------------------------------------------------------------------------
#endif
//34567890123456789012345678901234567890123456789012345678901234567890123456789
//--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----