source: orxonox.OLD/trunk/src/lib/graphics/spatial_separation/quadtree_node.h @ 8453

/*!
 * @file proto_class.h
 *  Definition of a QuadtreeNode which represents a quad in a Quadtree

  This struct is used to partition big land scapes into smaller ones for different reasons:
    - for collision detection: only a subset of all triangles need to be tested vs a given body
    - for object culling purposes: the quadtrees that are not in the field of view can be ommitted in the draw process
    - for LOD (level of Detail). The models can be drawn using different LODs depending on the distance

  This struct includes all the triangles, vertices, normal informations needed to make something usefull with
  a terrain partition.
 */

#ifndef _QUADTREE_NODE_H
#define _QUADTREE_NODE_H

#include "base_object.h"

#include "plane.h"
#include "model.h"

// FORWARD DECLARATION
class Quadtree;


//! A class for a Quadtree Node representation
class QuadtreeNode : public BaseObject {

  public:
    QuadtreeNode(sTriangleExt** triangles, int numTriangles,
                 const float* pVertices, int numVertices,
                 Quadtree* quadtree, QuadtreeNode* parent,
                 Rectangle* rect, int treeDepth, const int maxDepth, int index
                );
    QuadtreeNode(const modelInfo* pModelInfo, Quadtree* quadtree, const int maxDepth);
    virtual ~QuadtreeNode();

    void buildHashTable(QuadtreeNode** nodeList, int* index);
    inline Rectangle* getDimension() { return this->pDimension; }

    bool includesPoint(const Vector& v) const;
    sTriangleExt* getTriangle(const Vector& position) const;
    float getHeight(const Vector& position) const;


    void drawTree() const;
    void draw() const;


  private:
    void init();

    void separateNode(float minLength);
    void separateNode();
    Rectangle* getDimFromModel();

    bool sameSide(const Vector& p1, const Vector&p2, const Vector& a, const Vector& b) const;
    bool pointInTriangle(const Vector&p, const Vector& a, const Vector& b, const Vector& c) const;

  protected:
    QuadtreeNode*                   parent;             //!< reference to the paren QuadtreeNode (NULL if rootnode)
    QuadtreeNode*                   nodeA;              //!< reference to the node A
    QuadtreeNode*                   nodeB;              //!< reference to the node B
    QuadtreeNode*                   nodeC;              //!< reference to the node C
    QuadtreeNode*                   nodeD;              //!< reference to the node D
    QuadtreeNode**                  nodes;              //!< reference to the quadtree nodes (nodeA, nodeB, nodeC, nodeD=[0..3])


  private:
    Quadtree*                       quadtree;           //!< reference to the quadtree
    Vector                          center;             //!< center coordinate of the quadtree node - relative coordinates in model space(!)
    float                           axisLength;         //!< axis length of the quadtree
    float                           maxHeigth;          //!< max height of the model in the quadtree
    float                           offset;             //!< offset of the actual quadtree rectangle

    int                             treeDepth;          //!< the depth of the tree
    int                             maxDepth;           //!< the maximal depth of the tree
    int                             indexNode;          //!< the index number of the node
    int                             nodeIter;           //!< temp helping variable for the hashing algorithm

    sTriangleExt**                  pTriangles;         //!< reference to the triangles of the node
    const float*                    pVertices;          //!< reference to vertices data
    unsigned int                    numTriangles;       //!< number of triangles of the Node
    unsigned int                    numVertices;        //!< number of vertices of the node
    const modelInfo*                pModelInfo;         //!< reference to the modelInfo of the object
    Rectangle*                      pDimension;         //!< pointer to the local rectangle properties

    bool                            bDraw;              //!< shall it be drawn? DEBUG only
};

#endif /* _QUADTREE_NODE_H */