source: orxonox.OLD/trunk/src/lib/graphics/spatial_separation/quadtree.h @ 10712

/*!
 * @file quadtree.h
 *  Definition of a spatial data separation using quadtree

  This is the top element of the quadtree framework. A Quadtree is build of QuadtreeNodes, which are again separated
  into QuadtreeNodes until a certain depth is reached
 */

#ifndef _QUADTREE_H
#define _QUADTREE_H


#include "base_object.h"
#include "model.h"


class QuadtreeNode;
class Material;
class Vector;

//! A class for quadtree separation of the world
class Quadtree : public BaseObject {
  ObjectListDeclaration(Quadtree);

  public:
    Quadtree(const modelInfo* pModelInfo, const int treeDepth);
    virtual ~Quadtree();

    QuadtreeNode* getQuadtreeFromPosition(const Vector& position) const;
    sTriangleExt* getTriangleFromPosition(const Vector& position) const;

    void drawTree() const;
    inline Material* getMaterial(int indexNode) const { return this->materials[indexNode % 4]; }


  private:
    void revertHashTable(QuadtreeNode** nodes);
    void sortHashTable(QuadtreeNode** nodes);


  private:
    QuadtreeNode*                   rootNode;              //!< reference to the root node of the quadtree
    QuadtreeNode**                  nodes;                 //!< reference to all quadtree nodes (only leafs of the quad tree)
    const modelInfo*                pModelInfo;            //!< reference to the modelInfo of the object
    int                             treeDepth;             //!< depth of the tree

    float                           quadLength;            //!< length of the leaf quadtree nodes
    Vector*                         offset;                //!< vector to the left lower corner of the root quadtree node
    int                             maxIndex;              //!< maximal index for the nodes array

    Material**                      materials;             //!< materials for debug drawing purposes
};

#endif /* _QUADTREE_H */