#ifndef KDTREE_H
#define KDTREE_H

#include "Vertex.h"
#include "Triangle.h"
#include "Ray.h"
#include <stdio.h>

#undef near
#undef far

class KdTreeNode;
class GLViewer;
class Mesh;
struct IntersectedTriangle;

/*

  Start: 2.4s

*/

static const unsigned int kdTreeMinSize = 30;
static const unsigned int kdTreeMaxDepth = 32;

// 3d kd-tree
class KdTreeNode
{
public:

    KdTreeNode(std::vector<unsigned int> indices, const Mesh& mesh, unsigned int depth, const BoundingBox& bbox);

    ~KdTreeNode();

    bool isLeaf() const
    {
        return tris.size() > 0;
    }

    void splitTriangles(float splitPos, const std::vector<unsigned int>& indices, std::vector<unsigned int>& tLeft, std::vector<unsigned int>& tRight) const;

    void findOptimalSplit(const std::vector<unsigned int> &indices, std::vector<unsigned int>& tLeft, std::vector<unsigned int>& tRight);

	bool intersectTriangles(const Ray& r, IntersectedTriangle& tri, float tmin, float tmax) const;

    bool intersect(const Ray& r, float tmin, float tmax, IntersectedTriangle& tri) const;

    Vec3Df axisVec() const;

    void draw(const BoundingBox& bbox, const GLViewer* viewer, const Vec3Df& trans) const;

private:
    // Children
    KdTreeNode* left;
    KdTreeNode* right;

    // Split info
    unsigned int axis;
    float split;

    // Data
    std::vector<unsigned int> tris;
    const BoundingBox& bbox;
    const Mesh& mesh;
};

class KdTree
{
public:
    KdTree(const Mesh& mesh);

    ~KdTree();

    void clear();

    void rebuild();

    bool intersect(Ray r, IntersectedTriangle& tri) const;

    void draw(const GLViewer* viewer, const Vec3Df& trans) const;

private:
    KdTreeNode* root;
    const Mesh& mesh;
};

#endif //KDTREE_H
