/*
 *  Copyright (C) 2008 Hannu Saransaari
 *
 *  This program is distributed under the terms of the
 *  GNU General Public License.
 *
 *  This file is part of Dave the Ordinary Spaceman.
 *
 *  Dave the Ordinary Spaceman is free software: you can redistribute
 *  it and/or modify it under the terms of the GNU General Public
 *  License as published by the Free Software Foundation, either
 *  version 3 of the License, or (at your option) any later version.
 *
 *  Dave the Ordinary Spaceman is distributed in the hope that it
 *  will be useful, but WITHOUT ANY WARRANTY; without even the
 *  implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
 *  PURPOSE.  See the GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with Dave the Ordinary Spaceman. If not, see
 *  <http://www.gnu.org/licenses/>.
 *
 */

#ifndef _KDTREE_H
#define _KDTREE_H

#include "vector3.h"
#include <vector>
#ifdef WIN32
typedef unsigned int uint32_t;
#else
#include <stdint.h>
#endif

class KDTree
{
public:
	KDTree();
	~KDTree();

	int feedTriangles(const std::vector<Vector3>& vertices, int* triangles, int n);

	void update();

	int intersect(const Vector3& p, const Vector3& d, float& t, float& u, float& v) const;
	bool shadowIntersect(const Vector3& p, const Vector3& d, float maxT) const;

	inline size_t getTriangleCount() const { return triangles.size(); }

public:
	struct Node
	{
		uint32_t dir;
		float pos;
		uint32_t right;
	};

private:
	struct Triangle
	{
		uint32_t a, b, c;
	};

private:
	int newNode();
	int build(int* tris, int n, const Vector3& min, const Vector3& max);
	void allocateBuckets(int n);

private:
	// KD-tree nodes.
	unsigned int totalNodes;
	Node* nodes;

	// Scene bounding box.
	Vector3 sceneMin;
	Vector3 sceneMax;

	// Vertices and triangles.
	std::vector<Vector3> vertices;
	std::vector<Triangle> triangles;

	// Triangle buckets for lead nodes in kd-tree.
	int* triangleBuckets;
	int triangleBucketsCount;
	int triangleBucketsSize;

	// Bounding boxes of triangles. Used only in precalculation.
	std::vector<std::pair<Vector3, Vector3> > bboxes;
};

#endif
