TAPsBVHNode.cpp

Go to the documentation of this file.

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

BVHNode class is for a N Boundary Volume Hierarchy Node.

SUKITTI PUNAK   (01/17/2006)
UPDATE          (10/14/2009)
******************************************************************************/
#include "TAPsBVHNode.hpp"
// Using Inclusion Model (i.e. definitions are included in declarations)
//                       (this name.cpp is included in name.hpp)
// Each friend is defined directly inside its declaration.

BEGIN_NAMESPACE_TAPs
//=============================================================================
// Constructor(s) and Destructor
//-----------------------------------------------------------------------------
template <typename T>
BVHNode<T>::BVHNode (
    Enum::CD        type, 
    int             id, 
    BVHNode<T> *    parent, 
    BVHNode<T> **   children
)
    : m_eType( type ), 
      //m_bIsLeaf( false ), 
      m_iID( id ), 
      m_pParent( parent )

    #ifdef  TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS
    , m_bOnForColDet( true )
    #endif//TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS

    #ifdef  TAPs_DEBUG_COLLISION_DETECTION
    , flag( false )
    #endif//TAPs_DEBUG_COLLISION_DETECTION
{
    InitChildren( type, children );

    //bDraw = false;    // DEBUG
}
//-----------------------------------------------------------------------------
template <typename T>
BVHNode<T>::BVHNode (
    int             numOfChildren, 
    Enum::CD        type, 
    int             id, 
    BVHNode<T> *    parent, 
    BVHNode<T> **   children 
)
    : m_ieType( type ), 
      //m_bIsLeaf( false ), 
      m_iID( id ), 
      m_pParent( parent ), 
      m_iN( numOfChildren )

    #ifdef  TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS
    , m_bOnForColDet( true )
    #endif//TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS

    #ifdef  TAPs_DEBUG_COLLISION_DETECTION
    , flag( false )
    #endif//TAPs_DEBUG_COLLISION_DETECTION
{
    switch ( type ) {
        case Enum::BVH_NODE_GENERIC_SPHERE:
        case Enum::BVH_NODE_GENERIC_AABB:
        case Enum::BVH_NODE_GENERIC_OBB:
            InitChildren( m_iN, children );
            break;
        default:
            std::cout << "ERROR: BVHNode<T> Constructor#2!" << std::endl;
            assert( false );
            break;
    }

    //bDraw = false;    // DEBUG
}
//-----------------------------------------------------------------------------
template <typename T>
BVHNode<T>::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 
)
    : m_eType( type ), 
      //m_bIsLeaf( false ), 
      m_iID( id ), 
      m_pParent( parent ), 
      m_vCenter( center ), 
      m_vU( U ), 
      m_vV( V ), 
      m_vW( W )

    #ifdef  TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS
    , m_bOnForColDet( true )
    #endif//TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS

    #ifdef  TAPs_DEBUG_COLLISION_DETECTION
    , flag( false )
    #endif//TAPs_DEBUG_COLLISION_DETECTION
{
    InitChildren( type, NULL );

    //bDraw = false;    // DEBUG
}
//-----------------------------------------------------------------------------
// For constructing a leaf node
template <typename T>
BVHNode<T>::BVHNode (
    int                 id, 
    Enum::CD            type, 
    BVHNode<T> *        parent )
    : m_eType( type ), 
      //m_bIsLeaf( false ), 
      m_iID( id ), 
      m_pParent( parent ), 
      m_iN( 0 ), 
      m_ppChild( NULL )

    #ifdef  TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS
    , m_bOnForColDet( true )
    #endif//TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS

    #ifdef  TAPs_DEBUG_COLLISION_DETECTION
    , flag( false )
    #endif//TAPs_DEBUG_COLLISION_DETECTION
{
    //bDraw = false;    // DEBUG
}
//-----------------------------------------------------------------------------
// StrInfo
template <typename T>
std::string BVHNode<T>::StrInfo () const
{
    std::stringstream output;
    for ( int i = 0; i < m_iN; ++i ) {
        output << "\n\tChild Ptr#" << m_iN << ": " << m_ppChild[i];
    }
    //-----------------------------------------------------------
    // Output the node info
    output << "\nThe node type is ";
    switch ( m_eType ) {
        case Enum::UNDEFINED_NODE:
            output << "UNDEFINED_NODE.";
            break;
        case Enum::BVH_NODE_BINARY_SPHERE:
            output  << "BVH_NODE_BINARY_SPHERE." 
                    << "  With Center at (" << m_vCenter[0] << ", " 
                    << m_vCenter[1] << ", " << m_vCenter[2] 
                    <<   ") and radius of " << m_vW[0];
            break;
        default:
            output << "\nUnrecognized Node!";
            break;
    }
    output  << "\n";
    return output.str();
}
//-----------------------------------------------------------------------------
template <typename T>
BVHNode<T>::~BVHNode ()
{
    //std::cout << "Delete BVHNode ID: " << m_iID << std::endl;
    //---------------------------------------------------------------
    // Delete All Children
    if ( m_ppChild ) {
        for ( int i = 0; i < m_iN; ++i ) {
            if ( m_ppChild[i] ) delete m_ppChild[i];
            //m_ppChild[i] = NULL;
        }
        delete [] m_ppChild;
        //m_ppChild = NULL;
    }
    //---------------------------------------------------------------
    // Set Parent Node
    if ( m_pParent ) {
        for ( int i = 0; i < m_iN; ++i ) {
            if ( m_pParent->m_ppChild[i] == this ) {
                m_pParent->m_ppChild[i] = NULL;
                break;
            }
        }
        //m_pParent = NULL;
    }
}
//-----------------------------------------------------------------------------
template <typename T>
void BVHNode<T>::InitChildren ( Enum::CD type, BVHNode<T> ** children )
{
    switch ( type ) {
        case Enum::BVH_NODE_BINARY_SPHERE:
        case Enum::BVH_NODE_BINARY_AABB:
        case Enum::BVH_NODE_BINARY_OBB:
            InitChildren( 2, children );
            break;
        case Enum::BVH_NODE_QUAD_SPHERE:
        case Enum::BVH_NODE_QUAD_AABB:
        case Enum::BVH_NODE_QUAD_OBB:
            InitChildren( 4, children );
            break;
        case Enum::BVH_NODE_OCTANT_SPHERE:
        case Enum::BVH_NODE_OCTANT_AABB:
        case Enum::BVH_NODE_OCTANT_OBB:
            InitChildren( 8, children );
            break;
        default:
            std::cout << "Error: BVHNode<T>::InitChildren Fn!" << std::endl;
            assert( false );
            break;
    }
}
//-----------------------------------------------------------------------------
template <typename T>
void BVHNode<T>::InitChildren ( int numOfChildren, BVHNode<T> ** children )
{
    m_iN = numOfChildren;
    /*
    //---------------------------------------------------------------
    // For Leaf Node (i.e. No Children)
    if ( m_iN == 0 ) {
        m_ppChild = NULL;
        return;
    }
    //*/
    //---------------------------------------------------------------
    m_ppChild = new BVHNode<T> *[m_iN];
    if ( children ) {
        for ( int i = 0; i < m_iN; ++i ) {
            m_ppChild[i] = children[i];
        }
    }
    else {
        for ( int i = 0; i < m_iN; ++i ) {
            m_ppChild[i] = NULL;
        }
    }
}
//-----------------------------------------------------------------------------
// Constructor(s) and Destructor
//=============================================================================




//=============================================================================
// Node Operations
//-----------------------------------------------------------------------------
// Update
// update only this node
template <typename T>
void BVHNode<T>::Update ()
{
    //---------------------------------------------------------------
    switch ( m_eType ) {
        case Enum::BVH_NODE_BINARY_SPHERE:
            if  ( m_ppChild[0] != NULL && m_ppChild[1] != NULL ) {
                Vector3<T> V = m_ppChild[0]->GetCenter() - m_ppChild[1]->GetCenter();
                T a = m_ppChild[0]->GetRadius();
                T b = m_ppChild[1]->GetRadius();
                SetCenter( m_ppChild[1]->GetCenter() + V*a/(a+b) );
                // m_vW[0] is m_tRadius
                SetRadius( ( m_ppChild[0]->GetRadius() + m_ppChild[1]->GetRadius()
                            + V.Length() ) / T(2.0) );
            }
            else if ( m_ppChild[0] == NULL && m_ppChild[1] == NULL ) {
            }
            else if ( m_ppChild[0] != NULL ) {
                SetCenter( m_ppChild[0]->GetCenter() );
                // m_vW[0] is m_tRadius
                SetRadius( m_ppChild[0]->GetRadius() );
            }
            else if ( m_ppChild[1] != NULL ) {
                SetCenter( m_ppChild[1]->GetCenter() );
                // m_vW[0] is m_tRadius
                SetRadius( m_ppChild[1]->GetRadius() );
            }
            break;
        case Enum::BVH_NODE_BINARY_AABB:
            break;
        case Enum::BVH_NODE_BINARY_OBB:
            break;
        case Enum::BVH_NODE_QUAD_SPHERE:
            break;
        case Enum::BVH_NODE_QUAD_AABB:
            break;
        case Enum::BVH_NODE_QUAD_OBB:
            break;
        case Enum::BVH_NODE_OCTANT_SPHERE:
            break;
        case Enum::BVH_NODE_OCTANT_AABB:
            break;
        case Enum::BVH_NODE_OCTANT_OBB:
            break;
        default:
            break;
    }
}
//-----------------------------------------------------------------------------
// Node Operations
//=============================================================================




/*
//-----------------------------------------------------------------------------
// TestOverlapWith
template <typename T>
T BVHNode<T>::TestOverlapWith ( BVHNode<T> const * const that ) const
{
    switch ( m_eType ) {
        case Enum::BVH_NODE_BINARY_SPHERE:
        case Enum::BVH_NODE_QUAD_SPHERE:
        case Enum::BVH_NODE_OCTANT_SPHERE:
        case Enum::BVH_NODE_GENERIC_SPHERE:
        case Enum::BVH_NODE_LEAF_SPHERE_HALFEDGE_APRIM:
        case Enum::BVH_NODE_LEAF_SPHERE_HALFEDGE_PRIMS:
            switch ( that->m_eType ) {
                case Enum::BVH_NODE_BINARY_SPHERE:
                case Enum::BVH_NODE_QUAD_SPHERE:
                case Enum::BVH_NODE_OCTANT_SPHERE:
                case Enum::BVH_NODE_GENERIC_SPHERE:
                case Enum::BVH_NODE_LEAF_SPHERE_HALFEDGE_APRIM:
                    return    ( GetCenter() - that->GetCenter() ).Length() 
                            - ( GetRadius() + that->GetRadius() );  // m_vW[0] is m_tRadius
                    break;
                case Enum::BVH_NODE_LEAF_SPHERE_HALFEDGE_PRIMS:
                    return    ( GetCenter() - that->GetCenter() ).Length() 
                            - ( GetRadius() + that->GetRadius() );  // m_vW[0] is m_tRadius
                    break;
                default:
                    std::cout << "Error: BVHNode<T>::TestOverlapWith Fn!" << std::endl;
                    assert( false );
                    break;
            }
            break;
        default:
            std::cout << "Error: BVHNode<T>::TestOverlapWith Fn!" << std::endl;
            assert( false );
            break;
    }
    return -777;    // -777 is an Error Code
}
//-----------------------------------------------------------------------------
// TestOverlapWithNoPrimitiveTests
template <typename T>
T BVHNode<T>::TestOverlapWithNoPrimitiveTests ( BVHNode<T> const * const that ) const
{
    switch ( m_eType ) {
        case Enum::BVH_NODE_BINARY_SPHERE:
        case Enum::BVH_NODE_QUAD_SPHERE:
        case Enum::BVH_NODE_OCTANT_SPHERE:
        case Enum::BVH_NODE_GENERIC_SPHERE:
        case Enum::BVH_NODE_LEAF_SPHERE_HALFEDGE_APRIM:
        case Enum::BVH_NODE_LEAF_SPHERE_HALFEDGE_PRIMS:
            switch ( that->m_eType ) {
                case Enum::BVH_NODE_BINARY_SPHERE:
                case Enum::BVH_NODE_QUAD_SPHERE:
                case Enum::BVH_NODE_OCTANT_SPHERE:
                case Enum::BVH_NODE_GENERIC_SPHERE:
                case Enum::BVH_NODE_LEAF_SPHERE_HALFEDGE_APRIM:
                    return    ( GetCenter() - that->GetCenter() ).Length() 
                            - ( GetRadius() + that->GetRadius() );  // m_vW[0] is m_tRadius
                    break;
                case Enum::BVH_NODE_LEAF_SPHERE_HALFEDGE_PRIMS:
                    return    ( GetCenter() - that->GetCenter() ).Length() 
                            - ( GetRadius() + that->GetRadius() );  // m_vW[0] is m_tRadius
                    break;
                default:
                    std::cout << "Error: BVHNode<T>::TestOverlapWith Fn!" << std::endl;
                    assert( false );
                    break;
            }
            break;
        default:
            std::cout << "Error: BVHNode<T>::TestOverlapWith Fn!" << std::endl;
            assert( false );
            break;
    }
    return -777;    // -777 is an Error Code
}
//-----------------------------------------------------------------------------
//*/




//=============================================================================
// Sphere-BVSphere Intersection Test (BinarySphereTree vs BinarySphereTree)
//-----------------------------------------------------------------------------
// TestOverlapSphereWithSphere #1
template <typename T>
T BVHNode<T>::TestOverlapSphereWithSphere ( BVHNode<T> const * const that ) const
{
    //return    ( GetCenter() - that->GetCenter() ).Length() - ( GetRadius() + that->GetRadius() );
    return TestOverlapSphereWithSphere_NoPrimitiveTests( that );
}
//-----------------------------------------------------------------------------
// TestOverlapSphereWithSphere #2
template <typename T>
T BVHNode<T>::TestOverlapSphereWithSphere ( 
                    BVHNode<T> const * const that, 
                    Matrix4x4<T> const & thatTransform ) const
{
    //Vector3<T>    cB = (thatTransform * Vector4<T>( that->GetCenter() )).GetVector3();
    //return    ( GetCenter() - cB ).Length() - ( GetRadius() + that->GetRadius() );
    return TestOverlapSphereWithSphere_NoPrimitiveTests( that, thatTransform );
}
//-----------------------------------------------------------------------------
// TestOverlapSphereWithSphere #3
template <typename T>
T BVHNode<T>::TestOverlapSphereWithSphere ( 
                    Matrix4x4<T> const & thisTransform, 
                    BVHNode<T> const * const that ) const
{
    //Vector3<T>    cA = (thisTransform * Vector4<T>( GetCenter() )).GetVector3();
    //return    ( cA - that->GetCenter() ).Length() - ( GetRadius() + that->GetRadius() );
    return TestOverlapSphereWithSphere_NoPrimitiveTests( thisTransform, that );
}
//-----------------------------------------------------------------------------
// TestOverlapSphereWithSphere #4
template <typename T>
T BVHNode<T>::TestOverlapSphereWithSphere ( 
                    Matrix4x4<T> const & thisTransform, 
                    BVHNode<T> const * const that, 
                    Matrix4x4<T> const & thatTransform ) const
{
    //Vector3<T>    cA = (thisTransform * Vector4<T>( GetCenter() )).GetVector3();
    //Vector3<T>    cB = (thatTransform * Vector4<T>( that->GetCenter() )).GetVector3();
    //return    ( cA - cB ).Length() - ( GetRadius() + that->GetRadius() );
    return TestOverlapSphereWithSphere_NoPrimitiveTests( thisTransform, that, thatTransform );
}
//-----------------------------------------------------------------------------


//-----------------------------------------------------------------------------
// TestOverlapSphereWithSphere_NoPrimitiveTests #1
template <typename T>
T BVHNode<T>::TestOverlapSphereWithSphere_NoPrimitiveTests ( BVHNode<T> const * const that ) const
{
    #ifdef  TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS
    if ( !GetOnStatus() )   return 1;
    #endif//TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS

    return  ( GetCenter() - that->GetCenter() ).Length() - ( GetRadius() + that->GetRadius() );
}
//-----------------------------------------------------------------------------
// TestOverlapSphereWithSphere_NoPrimitiveTests #2
template <typename T>
T BVHNode<T>::TestOverlapSphereWithSphere_NoPrimitiveTests ( 
                    BVHNode<T> const * const that, 
                    Matrix4x4<T> const & thatTransform ) const
{
    #ifdef  TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS
    if ( !GetOnStatus() )   return 1;
    #endif//TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS

    Vector3<T>  cB = (thatTransform * Vector4<T>( that->GetCenter() )).GetVector3();
    return  ( GetCenter() - cB ).Length() - ( GetRadius() + that->GetRadius() );
}
//-----------------------------------------------------------------------------
// TestOverlapSphereWithSphere_NoPrimitiveTests #3
template <typename T>
T BVHNode<T>::TestOverlapSphereWithSphere_NoPrimitiveTests ( 
                    Matrix4x4<T> const & thisTransform, 
                    BVHNode<T> const * const that ) const
{
    #ifdef  TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS
    if ( !GetOnStatus() )   return 1;
    #endif//TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS

    Vector3<T>  cA = (thisTransform * Vector4<T>( GetCenter() )).GetVector3();
    return  ( cA - that->GetCenter() ).Length() - ( GetRadius() + that->GetRadius() );
}
//-----------------------------------------------------------------------------
// TestOverlapSphereWithSphere_NoPrimitiveTests #4
template <typename T>
T BVHNode<T>::TestOverlapSphereWithSphere_NoPrimitiveTests ( 
                    Matrix4x4<T> const & thisTransform, 
                    BVHNode<T> const * const that, 
                    Matrix4x4<T> const & thatTransform ) const
{
    #ifdef  TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS
    if ( !GetOnStatus() )   return 1;
    #endif//TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS

    Vector3<T>  cA = (thisTransform * Vector4<T>( GetCenter() )).GetVector3();
    Vector3<T>  cB = (thatTransform * Vector4<T>( that->GetCenter() )).GetVector3();
    return  ( cA - cB ).Length() - ( GetRadius() + that->GetRadius() );
}
//-----------------------------------------------------------------------------
// Sphere-Sphere Intersection Test (BinarySphereTree vs BinarySphereTree)
//=============================================================================




//=============================================================================
// Sphere-BVSphere Intersection Test (BinarySphereTree vs Sphere BV)
//-----------------------------------------------------------------------------
// TestOverlapSphereWithBVSphere_NoPrimitiveTests #1
template <typename T>
T BVHNode<T>::TestOverlapSphereWithBVSphere_NoPrimitiveTests ( 
    Vector3<T> const & centerOfBVSphere,    
    T radiusOfBVSphere                      
) const
{
    #ifdef  TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS
    if ( !GetOnStatus() )   return 1;
    #endif//TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS

    return  ( GetCenter() - centerOfBVSphere ).Length() - ( GetRadius() + radiusOfBVSphere );
}
//-----------------------------------------------------------------------------
// TestOverlapSphereWithBVSphere_NoPrimitiveTests #2
template <typename T>
T BVHNode<T>::TestOverlapSphereWithBVSphere_NoPrimitiveTests ( 
    Matrix4x4<T> const & transformA,        
    Vector3<T> const & centerOfBVSphere,    
    T radiusOfBVSphere                      
) const
{
    #ifdef  TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS
    if ( !GetOnStatus() )   return 1;
    #endif//TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS

    Vector3<T>  cA = (transformA * Vector4<T>( GetCenter() )).GetVector3();
    return  ( cA - centerOfBVSphere ).Length() - ( GetRadius() + radiusOfBVSphere );
}
//-----------------------------------------------------------------------------
// Sphere-BVSphere Intersection Test (BinarySphereTree vs Sphere BV)
//=============================================================================




//=============================================================================
// Sphere-BVCylinder Intersection Test (BinarySphereTree vs Cylinder BV)
//-----------------------------------------------------------------------------
// TestOverlapSphereWithBVCylinder_NoPrimitiveTests #1
template <typename T>
bool BVHNode<T>::TestOverlapSphereWithBVCylinder_AtOrigin_NoPrimitiveTests ( 
    T radiusOfBVCylinder,                   
    T heightOfBVCylinder                    
) const
{
    #ifdef  TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS
    if ( !GetOnStatus() )   return 1;
    #endif//TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS

    return TAPs::CGMath<T>::CD_CylinderAtOrigin_vs_Sphere( radiusOfBVCylinder, heightOfBVCylinder, GetCenter(), GetRadius() );
}
//-----------------------------------------------------------------------------
// TestOverlapSphereWithBVSphere_NoPrimitiveTests #2
template <typename T>
bool BVHNode<T>::TestOverlapSphereWithBVCylinder_AtOrigin_NoPrimitiveTests ( 
    Matrix4x4<T> const & transformA,        
    T radiusOfBVCylinder,                   
    T heightOfBVCylinder                    
) const
{
    #ifdef  TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS
    if ( !GetOnStatus() )   return 1;
    #endif//TAPs_ENABLE_COLLISION_DETECTION_ON_OFF_STATUS

    // Sphere's center and radius after the transformation
    Vector3<T>  cA = (transformA * Vector4<T>( GetCenter() )).GetVector3();
    T           rA = ( (transformA * Vector4<T>( GetRadius()+GetCenter()[0], GetCenter()[1], GetCenter()[2], 1 )).GetVector3() - cA ).Length();
    return TAPs::CGMath<T>::CD_CylinderAtOrigin_vs_Sphere( radiusOfBVCylinder, heightOfBVCylinder, cA, rA );
}
//-----------------------------------------------------------------------------
// Sphere-BVSphere Intersection Test (BinarySphereTree vs Sphere BV)
//=============================================================================




#if defined(__gl_h_) || defined(__GL_H__)
//=============================================================================
// DrawByOpenGL
//-----------------------------------------------------------------------------
template <typename T> GLuint BVHNode<T>::m_uiDisplayList = 0;
//-----------------------------------------------------------------------------
template <typename T>
void BVHNode<T>::DrawByOpenGL () const
{
    DrawBV();

    // Draw child nodes
    for ( int i = 0; i < m_iN; ++i ) {
        if ( m_ppChild[i] ) {
            std::cout << *m_ppChild[i] << "\n";
            m_ppChild[i]->DrawByOpenGL();
        }
    }
}
//-----------------------------------------------------------------------------
template <typename T>
void BVHNode<T>::DrawByOpenGL ( 
        int currentLevel, int startLevel, int endLevel ) const
{
    if ( startLevel <= currentLevel && currentLevel <= endLevel ) {
        DrawBV();
    }

    // Draw child nodes
    ++currentLevel;
    for ( int i = 0; i < m_iN; ++i ) {
        if ( m_ppChild[i] ) {
            float div = static_cast<GLfloat>(m_iN);
            m_ppChild[i]->DrawByOpenGL( currentLevel, startLevel, endLevel );
        }
    }
}
//-----------------------------------------------------------------------------
template <typename T>
void BVHNode<T>::DrawByOpenGLOnlyEndLevel () const
{
    bool draw = true;
    for ( int i = 0; i < m_iN; ++i ) {
        if ( m_ppChild[i] ) draw = false;
    }
    if ( draw ) DrawBV();

    // Draw child nodes
    for ( int i = 0; i < m_iN; ++i ) {
        if ( m_ppChild[i] ) {
            m_ppChild[i]->DrawByOpenGLOnlyEndLevel();
        }
    }
}
//-----------------------------------------------------------------------------
template <typename T>
void BVHNode<T>::DrawBV ( GLenum drawStyle ) const
{
    switch ( m_eType ) {
        //-----------------------------------------------------------
        // DRAW SPHERE BVH
        case Enum::BVH_NODE_BINARY_SPHERE:
        case Enum::BVH_NODE_QUAD_SPHERE:
        case Enum::BVH_NODE_OCTANT_SPHERE:
        case Enum::BVH_NODE_GENERIC_SPHERE:
            DrawSphereBV();
            break;
        //-----------------------------------------------------------
        // DRAW AABB BVH
        case Enum::BVH_NODE_BINARY_AABB:
        case Enum::BVH_NODE_QUAD_AABB:
        case Enum::BVH_NODE_OCTANT_AABB:
        case Enum::BVH_NODE_GENERIC_AABB:
            DrawAABBBV();
            break;
        //-----------------------------------------------------------
        // DRAW OBB BVH
        case Enum::BVH_NODE_BINARY_OBB:
        case Enum::BVH_NODE_QUAD_OBB:
        case Enum::BVH_NODE_OCTANT_OBB:
        case Enum::BVH_NODE_GENERIC_OBB:
            DrawOBBBV();
            break;
    }
}
//-----------------------------------------------------------------------------
template <typename T>
void BVHNode<T>::DrawSphereBV ( GLenum drawStyle ) const
{
    //---------------------------------------------------------------
    //std::cout << "Draw SPHERE Bounding Volume\n";

    if ( !m_uiDisplayList ) {

    #ifdef  TAPs_DEBUG_COLLISION_DETECTION

        m_uiDisplayList = glGenLists( 2 );
        GLUquadricObj *qObj = gluNewQuadric();
        glNewList( m_uiDisplayList, GL_COMPILE );
            gluQuadricDrawStyle( qObj, GLU_LINE );
            gluSphere( qObj, 1, 9, 9 );
            //gluSphere( qObj, 1, 12, 12 );
            //gluSphere( qObj, 1, 15, 15 );
        glEndList();
        glNewList( m_uiDisplayList+1, GL_COMPILE );
            gluQuadricDrawStyle( qObj, GLU_FILL );
            gluSphere( qObj, 1, 9, 9 );
            //gluSphere( qObj, 1, 12, 12 );
            //gluSphere( qObj, 1, 15, 15 );
        glEndList();
        gluDeleteQuadric( qObj );

    #else //TAPs_DEBUG_COLLISION_DETECTION

        m_uiDisplayList = glGenLists( 1 );
        GLUquadricObj *qObj = gluNewQuadric();
        glNewList( m_uiDisplayList, GL_COMPILE );
            // GLenum drawStyle
            //  GLU_FILL
            //  GLU_LINE
            //  GLU_SILHOUETTE
            //  GLU_POINT
            gluQuadricDrawStyle( qObj, GLU_LINE );
            gluSphere( qObj, 1, 9, 9 );
            //gluSphere( qObj, 1, 12, 12 );
            //gluSphere( qObj, 1, 15, 15 );
        glEndList();
        gluDeleteQuadric( qObj );

    #endif//TAPs_DEBUG_COLLISION_DETECTION

    }
    //---------------------------------------------------------------
    glPushMatrix();
        glTranslatef( static_cast<GLfloat>(GetCenter()[0]), static_cast<GLfloat>(GetCenter()[1]), static_cast<GLfloat>(GetCenter()[2]) );
        glScalef( static_cast<GLfloat>(GetRadius()), static_cast<GLfloat>(GetRadius()), static_cast<GLfloat>(GetRadius()) );

    #ifdef  TAPs_DEBUG_COLLISION_DETECTION
        if ( flag ) glCallList( m_uiDisplayList );
        else        glCallList( m_uiDisplayList+1 );
    #else //TAPs_DEBUG_COLLISION_DETECTION
        glCallList( m_uiDisplayList );
    #endif//TAPs_DEBUG_COLLISION_DETECTION

        //-------------------------------------------------
        // Draw the sphere center
        //glScalef( 0.1, 0.1, 0.1 );
        //glCallList( m_uiDisplayList );
    glPopMatrix();
}
//-----------------------------------------------------------------------------
template <typename T>
void BVHNode<T>::DrawAABBBV ( GLenum drawStyle ) const
{
    //---------------------------------------------------------------
    //std::cout << "Draw AABB Bounding Volume\n";
    Vector3<T> pt[8];
    // m_vV is the min point
    // m_vW is the max point
    // 
    //     3------2
    //    /|     /|    y
    //   / 0----/-1    |
    //  7----- 6 /     0--x
    //  |/     |/     /
    //  4------5     z
    pt[0] = GetMinPt();                             // Point#0 is the min point
    pt[1].SetXYZ( GetMaxPt()[0], GetMinPt()[1], GetMinPt()[2] );    // Point#1
    pt[2].SetXYZ( GetMaxPt()[0], GetMaxPt()[1], GetMinPt()[2] );    // Point#2
    pt[3].SetXYZ( GetMinPt()[0], GetMaxPt()[1], GetMinPt()[2] );    // Point#3
    pt[4].SetXYZ( GetMinPt()[0], GetMinPt()[1], GetMaxPt()[2] );    // Point#4
    pt[5].SetXYZ( GetMaxPt()[0], GetMinPt()[1], GetMaxPt()[2] );    // Point#5
    pt[6] = GetMaxPt();                             // Point#6 is the max point
    pt[7].SetXYZ( GetMinPt()[0], GetMaxPt()[1], GetMaxPt()[2] );    // Point#7
    /*
    pt[0] = m_vV;                               // Point#0 is the min point
    pt[1].SetXYZ( m_vW[0], m_vV[1], m_vV[2] );  // Point#1
    pt[2].SetXYZ( m_vW[0], m_vW[1], m_vV[2] );  // Point#2
    pt[3].SetXYZ( m_vV[0], m_vW[1], m_vV[2] );  // Point#3
    pt[4].SetXYZ( m_vV[0], m_vV[1], m_vW[2] );  // Point#4
    pt[5].SetXYZ( m_vW[0], m_vV[1], m_vW[2] );  // Point#5
    pt[6] = m_vW;                               // Point#6 is the max point
    pt[7].SetXYZ( m_vV[0], m_vW[1], m_vW[2] );  // Point#7
    //*/
    glPushMatrix();
        glBegin( GL_LINE_LOOP );
            glVertex3f( static_cast<GLfloat>(pt[0][0]), static_cast<GLfloat>(pt[0][1]), static_cast<GLfloat>(pt[0][2]) );
            glVertex3f( static_cast<GLfloat>(pt[1][0]), static_cast<GLfloat>(pt[1][1]), static_cast<GLfloat>(pt[1][2]) );
            glVertex3f( static_cast<GLfloat>(pt[2][0]), static_cast<GLfloat>(pt[2][1]), static_cast<GLfloat>(pt[2][2]) );
            glVertex3f( static_cast<GLfloat>(pt[3][0]), static_cast<GLfloat>(pt[3][1]), static_cast<GLfloat>(pt[3][2]) );
        glEnd();
        glBegin( GL_LINE_LOOP );
            glVertex3f( static_cast<GLfloat>(pt[4][0]), static_cast<GLfloat>(pt[4][1]), static_cast<GLfloat>(pt[4][2]) );
            glVertex3f( static_cast<GLfloat>(pt[5][0]), static_cast<GLfloat>(pt[5][1]), static_cast<GLfloat>(pt[5][2]) );
            glVertex3f( static_cast<GLfloat>(pt[6][0]), static_cast<GLfloat>(pt[6][1]), static_cast<GLfloat>(pt[6][2]) );
            glVertex3f( static_cast<GLfloat>(pt[7][0]), static_cast<GLfloat>(pt[7][1]), static_cast<GLfloat>(pt[7][2]) );
        glEnd();
        glBegin( GL_LINES );
            glVertex3f( static_cast<GLfloat>(pt[0][0]), static_cast<GLfloat>(pt[0][1]), static_cast<GLfloat>(pt[0][2]) );
            glVertex3f( static_cast<GLfloat>(pt[4][0]), static_cast<GLfloat>(pt[4][1]), static_cast<GLfloat>(pt[4][2]) );
            glVertex3f( static_cast<GLfloat>(pt[1][0]), static_cast<GLfloat>(pt[1][1]), static_cast<GLfloat>(pt[1][2]) );
            glVertex3f( static_cast<GLfloat>(pt[5][0]), static_cast<GLfloat>(pt[5][1]), static_cast<GLfloat>(pt[5][2]) );
            glVertex3f( static_cast<GLfloat>(pt[2][0]), static_cast<GLfloat>(pt[2][1]), static_cast<GLfloat>(pt[2][2]) );
            glVertex3f( static_cast<GLfloat>(pt[6][0]), static_cast<GLfloat>(pt[6][1]), static_cast<GLfloat>(pt[6][2]) );
            glVertex3f( static_cast<GLfloat>(pt[3][0]), static_cast<GLfloat>(pt[3][1]), static_cast<GLfloat>(pt[3][2]) );
            glVertex3f( static_cast<GLfloat>(pt[7][0]), static_cast<GLfloat>(pt[7][1]), static_cast<GLfloat>(pt[7][2]) );
        glEnd();
    glPopMatrix();
}
//-----------------------------------------------------------------------------
template <typename T>
void BVHNode<T>::DrawOBBBV ( GLenum drawStyle ) const
{
    //---------------------------------------------------------------
    //std::cout << "Draw OBB Bounding Volume\n";
    if ( !m_uiDisplayList ) {
        m_uiDisplayList = glGenLists( 1 );
        GLUquadricObj *qObj = gluNewQuadric();
        glNewList( m_uiDisplayList, GL_COMPILE );
            gluQuadricDrawStyle( qObj, drawStyle );
            gluSphere( qObj, 1, 9, 9 );
            //gluSphere( qObj, 1, 12, 12 );
            //gluSphere( qObj, 1, 15, 15 );
        glEndList();
        gluDeleteQuadric( qObj );
    }
    //---------------------------------------------------------------
    // Draw The Center of OBB Bounding Volume by a sphere
    T length = Get3rdPrincipleComponent().Length() / T(20.0);
    glPushMatrix();
        glTranslatef( static_cast<GLfloat>(GetCenter()[0]), static_cast<GLfloat>(GetCenter()[1]), static_cast<GLfloat>(GetCenter()[2]) );
        // m_vW[0] is m_tRadius
        glScalef( static_cast<GLfloat>(length), static_cast<GLfloat>(length), static_cast<GLfloat>(length) );
        glCallList( m_uiDisplayList );
    glPopMatrix();
    //---------------------------------------------------------------
    // Draw OBB Bounding Box
    Vector3<T> pt[8];
    pt[0] = m_vV + m_vU + m_vW;
    pt[1] = m_vV + m_vU - m_vW;
    pt[2] = m_vV - m_vU - m_vW;
    pt[3] = m_vV - m_vU + m_vW;
    pt[4] = -pt[2];
    pt[5] = -pt[3];
    pt[6] = -pt[0];
    pt[7] = -pt[1];
    glPushMatrix();
        glTranslatef( static_cast<GLfloat>(GetCenter()[0]), static_cast<GLfloat>(GetCenter()[1]), static_cast<GLfloat>(GetCenter()[2]) );
        glBegin( GL_LINE_LOOP );
            glVertex3f( static_cast<GLfloat>(pt[0][0]), static_cast<GLfloat>(pt[0][1]), static_cast<GLfloat>(pt[0][2]) );
            glVertex3f( static_cast<GLfloat>(pt[1][0]), static_cast<GLfloat>(pt[1][1]), static_cast<GLfloat>(pt[1][2]) );
            glVertex3f( static_cast<GLfloat>(pt[2][0]), static_cast<GLfloat>(pt[2][1]), static_cast<GLfloat>(pt[2][2]) );
            glVertex3f( static_cast<GLfloat>(pt[3][0]), static_cast<GLfloat>(pt[3][1]), static_cast<GLfloat>(pt[3][2]) );
        glEnd();
        glBegin( GL_LINE_LOOP );
            glVertex3f( static_cast<GLfloat>(pt[4][0]), static_cast<GLfloat>(pt[4][1]), static_cast<GLfloat>(pt[4][2]) );
            glVertex3f( static_cast<GLfloat>(pt[5][0]), static_cast<GLfloat>(pt[5][1]), static_cast<GLfloat>(pt[5][2]) );
            glVertex3f( static_cast<GLfloat>(pt[6][0]), static_cast<GLfloat>(pt[6][1]), static_cast<GLfloat>(pt[6][2]) );
            glVertex3f( static_cast<GLfloat>(pt[7][0]), static_cast<GLfloat>(pt[7][1]), static_cast<GLfloat>(pt[7][2]) );
        glEnd();
        glBegin( GL_LINES );
            glVertex3f( static_cast<GLfloat>(pt[0][0]), static_cast<GLfloat>(pt[0][1]), static_cast<GLfloat>(pt[0][2]) );
            glVertex3f( static_cast<GLfloat>(pt[4][0]), static_cast<GLfloat>(pt[4][1]), static_cast<GLfloat>(pt[4][2]) );
            glVertex3f( static_cast<GLfloat>(pt[1][0]), static_cast<GLfloat>(pt[1][1]), static_cast<GLfloat>(pt[1][2]) );
            glVertex3f( static_cast<GLfloat>(pt[5][0]), static_cast<GLfloat>(pt[5][1]), static_cast<GLfloat>(pt[5][2]) );
            glVertex3f( static_cast<GLfloat>(pt[2][0]), static_cast<GLfloat>(pt[2][1]), static_cast<GLfloat>(pt[2][2]) );
            glVertex3f( static_cast<GLfloat>(pt[6][0]), static_cast<GLfloat>(pt[6][1]), static_cast<GLfloat>(pt[6][2]) );
            glVertex3f( static_cast<GLfloat>(pt[3][0]), static_cast<GLfloat>(pt[3][1]), static_cast<GLfloat>(pt[3][2]) );
            glVertex3f( static_cast<GLfloat>(pt[7][0]), static_cast<GLfloat>(pt[7][1]), static_cast<GLfloat>(pt[7][2]) );
        glEnd();
    glPopMatrix();
    //---------------------------------------------------------------
    // Draw Principle Components
    //*
    glDisable( GL_LIGHTING );
    glPushMatrix();
        glTranslatef( static_cast<GLfloat>(GetCenter()[0]), static_cast<GLfloat>(GetCenter()[1]), static_cast<GLfloat>(GetCenter()[2]) );
        glBegin( GL_LINES );
            //---------------------------------------------
            // 1st principle component
            glColor3f( 1, 0, 0 );
            glVertex3f( 0, 0, 0 );
            glVertex3f( static_cast<GLfloat>(m_vU[0]), static_cast<GLfloat>(m_vU[1]), static_cast<GLfloat>(m_vU[2]) );
            //---------------------------------------------
            // 2nd principle component
            glColor3f( 0, 1, 0 );
            glVertex3f( 0, 0, 0 );
            glVertex3f( static_cast<GLfloat>(m_vV[0]), static_cast<GLfloat>(m_vV[1]), static_cast<GLfloat>(m_vV[2]) );
            //---------------------------------------------
            // 3rd principle component
            glColor3f( 0, 0, 1 );
            glVertex3f( 0, 0, 0 );
            glVertex3f( static_cast<GLfloat>(m_vW[0]), static_cast<GLfloat>(m_vW[1]), static_cast<GLfloat>(m_vW[2]) );
        glEnd();
    glPopMatrix();
    glEnable( GL_LIGHTING );
    //*/
}
//-----------------------------------------------------------------------------
#endif // #if defined(__gl_h_) || defined(__GL_H__)
//=============================================================================
END_NAMESPACE_TAPs
//34567890123456789012345678901234567890123456789012345678901234567890123456789
//--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----