BVH.h

Go to the documentation of this file.

/* $Id: BVH.h,v 1.12 2002/11/20 15:22:15 cvs Exp $ */

#ifndef __BOUNDING_VOLUME_HIERARCHY_H
#define __BOUNDING_VOLUME_HIERARCHY_H

#include <esg/SceneGraphObject.h>
#include <esg/spacesorting/SDS.h>
#include <esg/spacesorting/DistRot.h>
#include <esg/geometry/Geometry.h>
#include <esg/geometry/BVList.h>
#include <esg/SceneGraphObject.h>
//#include <esg/metric/Metric.h>

namespace esg {

class OGSCENE_EXPORT BVH : public SDS {
        friend class IteratorBVH;
        friend class InspectorBVH;
        friend class BVDistance;
        friend class BVExplorer;
  
public:
        struct Node {
                Geometry*  bv;         
                BVList*    list;       
                Node*      leftChild;  
                Node*      rightChild; 
                Node*      parent;     
                Node*      sibling;    
                bool       leaf;       
                
                Node() {
                    leftChild = (rightChild = (parent = (sibling = NULL)));
                    bv   = NULL;
                    list = NULL;
                }
        };

protected:
        struct DRInfo {
                double      minD;     
                BVH::Node * pLeafA;   
                BVH::Node * pLeafB;
                Vector3   * pDir;     
                DistRot   * pDistRot; 

                unsigned    myMaxDepth;
                unsigned    hisMaxDepth;
                unsigned    maxDepth; 
        
        /* In the case we reached a leaf of the tree we can use only the leaf
         * and don't pass any argument for it. Following fields are used only
         * in this case: */
                bool        leafInMe; 
                BVH::Node * pLeaf;    
                enum Strategy {
                    POINT_COLLISION,
                    SEPARATION,
                    DISTANCE
                }           strategy;
        } _drInfo;

protected:        
        bool      _append       (SceneGraphObject*,Geometry*, Node*, unsigned);
        void      _remove_leaf  (Node*);
        void      _build_tree   (Node*, unsigned);
        void      _destroy_tree (Node*);
        void      _rebuild_tree (Node*);
        Geometry* _create_bv    (BVList&);
        void      _collision    (Node*, Geometry&, List<SceneGraphObject>*);
        void      _dump         (const Node*, const char*, const char*);
    
        virtual DistRot* _create_dist_rot (BVH::Node*);
        virtual void     _dr_init         (const Matrix4*,const Matrix4*,BVH*);
        virtual void     _dr_primitives   (DRInfo&, Node*, Vector3*);
        virtual void     _dr_leaf         (DRInfo&, Node*, unsigned);
        virtual void     _dr_inner        (DRInfo&, Node*, Node*, unsigned);
    
        virtual bool      _enlarge_bv  (Geometry**, Geometry&)   = 0;
        virtual Geometry* _create_bv   (List<SceneGraphObject>&) = 0;
        virtual Geometry* _create_bv   (Geometry&, Geometry&)    = 0;
        virtual Geometry* _create_bv   (SceneGraphObject&)       = 0;
        virtual BVList*   _create_list ()                        = 0;
 
        virtual void _duplicate_attributes (const SDS&);

        //void _bv_distance (Node*, Metric&) const;
    
        BVH () {
            _root       = (_leftLeaf = NULL);
            _leafLimit  = 1;
            _depthLimit = 0;
            _scaleRatio = 1.0;
        }

protected:
        Node*     _root;
        Node*     _leftLeaf;
        unsigned  _leafLimit;
        unsigned  _depthLimit;
        unsigned  _treeDepth;
        
        Matrix4 _myTrMat;
        Matrix4 _coordMat;   
        double  _scaleRatio; 
        BVH   * _pPartner;   

        BVList::SplitStrategy _splitStrategy;
        
public:
        BVH (unsigned              /* leaf limit                 */,
             unsigned              /* depth limit                */,
             bool                  /* delay creation             */,
             BVList::SplitStrategy /* strategy of space division */);
    
    virtual ~BVH();
    
    virtual SDS*          clone           () const = 0;
    virtual Iterator*     createIterator  ();
    virtual InspectorSDS* createInspector (unsigned);

    // Add new object to tree. When tree is full, that is the
    // leaf limit and depth limit are over, then ignore leaf limit.
    virtual int               append (SceneGraphObject*);
    virtual SceneGraphObject* detach (SceneGraphObject::OID);

    // Update inner structure. Typically when some stored object
    // has been moved.
    virtual bool update (void);

    // Build inner structure. Some space sub-division structures
    // may prefer its real creation until they know most of storing objects.
    // This method must be called after all objects are appended when
    // delayBuild is set to true in constructor
    virtual bool build (void);

    unsigned leafLimit  (void) const { return _leafLimit;  }
    unsigned depthLimit (void) const { return _depthLimit; }

    /*
     * Find such two nodes, my and partner's, that are closest to each
     * other, put them into *ppMinA and *ppMinB and return their distance.
     * Returned distance is distance of bouding volumes, not stored
     * objects themselves!
     *
     * Parameters ppMinA and ppMinB should be either NULL or they should
     * points to closest leaves from previous pass.
     * In the second case, better optimization is used.
     *
     * Acually the only supported transformations are those don't
     * deforming objects, i.e. rotation, translation and single value scale.
     *
     * d1 and d2 are maximal depths for collision detection traversal.
     * If they are reached sooner then leaves then detection ends
     * (hierarchies behave like having depth d1 and d2 respectively).
     */
    virtual double distance (Matrix4* /* my tr. matrix                     */,
                             BVH&     /* tested hierarchy                  */,
                             Matrix4* /* its tr. matrix                    */,
                             Node**   /* my best leaf from prev. pass      */,
                             Node**   /* partner's  -"-                    */,
                             Vector3* pDir=NULL/* approx. dir. of distance */,
                             unsigned d1  =UINT_MAX /* my max. depth       */,
                             unsigned d2  =UINT_MAX /* partner's max depth */);

    /*
     * Output separation diraction is valid only for objects that are
     * penetrated and represents the approximately shortest way to
     * get the colliding leaves separated. Therefore this is not the
     * shortest way to get separated the whole complex object stored
     * in the hierarchy!
     *
     * d1 and d2 are maximal depths for collision detection traversal.
     * If they are reached sooner then leaves then detection ends
     * (hierarchies behave like having depth d1 and d2 respectively).
     */
    virtual bool separation (Matrix4* /* my tr. matrix                     */,
                             BVH&     /* tested hierarchy                  */,
                             Matrix4* /* its tr. matrix                    */,
                             Vector3* pDir=NULL/* approx. dir. of distance */,
                             unsigned d1  =UINT_MAX /* my max. depth       */,
                             unsigned d2  =UINT_MAX /* partner's max depth */);

    /*
     * Collision detection with 3D point.
     * It returns geometries of all leaf objects penetrating
     * a sphere that surrounds given point.
     */
    virtual Geometry** collision (Matrix4*            /* my tr.. matrix */,
                                  float, float, float /* 3D point */,
                                  float               /* rasius */,
                                  int*                /* # of returned obj.*/);

//    virtual void acceptMetric (Metric& metric) { metric.visitBVH(this); }

    // Dump the tree structure into (opened) file
    virtual void dump (const char* /* intent */, const char* /* tab */);

    

    
    // For debugging purposes only:
    virtual void __debug (void);
    virtual void __debug (Node* n, int d);

    // rot == 0 => zadna rotace
    // rot == 1 => rotace pomoci pMyTr
    // rot == 2 => rotace pomoci _pCoordMat
    void   __get_edges(Matrix4 *,Node*,unsigned,unsigned,int,float*,unsigned&);
    float* __getEdges (Matrix4 * pMyTr,unsigned level,int rot,unsigned& size);

    void  __get_meshes(Matrix4 *,Node*,unsigned,unsigned,int,Mesh**,unsigned&);
    Mesh**__getMeshes (Matrix4 * pMyTr,unsigned level,int rot,unsigned& size);
};

}; // namespace

#endif // __BOUNDING_VOLUME_HIERARCHY_H

---