OctTree.h

Go to the documentation of this file.

/* $Id:$ */

#ifndef __OCT_TREE_H
#define __OCT_TREE_H

#include <esg/spacesorting/SDS.h>

/*
 * TO DO:
 *   - delay of tree build
 *   - generic insertion of objects
 */

namespace esg {

class OctTree : public SDS {
protected:
    struct Node {
        Node                   * children; // array of eight children or NULL
        Node                   * pParent;
        List<SceneGraphObject>   objectList;

        Node() : children(NULL), pParent(NULL) {}
        ~Node() { objectList.dropAll(); }

        bool isLeaf  () const { return ((children) ? false : true ); }
        bool isInner () const { return ((children) ? true  : false); }
        bool isRoot  () const { return ((pParent)  ? false : true ); }
        bool isEmpty () const { return objectList.empty(); }
    } _root;
    
protected:
    void              _append       (SceneGraphObject*, Node*);
    SceneGraphObject* _detach       (SceneGraphObject::OID, Node);
    void              _build_tree   (Node*);
    void              _rebuild_tree (Node*);
    void              _destroy_tree (Node*);
    
    virtual void _duplicate_attributes (const SDS&) = 0;

protected:
    unsigned _sideLength; // maximal extent of scene

public:
    OctTree(bool /* delay build */, unsigned /* side length */);
    
    virtual ~OctTree() { _destroy_tree(&_root); }

    virtual SDS*          clone           () const;
    virtual Iterator*     createIterator  ();
    virtual InspectorSDS* createInspector (unsigned);
    
    // Operations changing inner structure must be fixed in SDS
    // interface. Operations which traverse inner structure can be
    // moved to Iterator.
    //
    // All operation are applied locally (not recursivelly to sub-nodes)
    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 preffer its real creation not 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);

    // Dump the tree structure into (opened) file
    virtual void dump (const char* /* intent */, const char* /* tab */) {}
    virtual void dump (const char* /* file name */)
    {
        dump("", " ");
        /* to do */
    } 
};
    
}; // namespace 

#endif // __OCT_TREE_H

---