/*
 * Octree-R implementation Copyright(c) Oct. 2006 Chia-Kai Liang
 *
 */
// Two intersection methods are implemented
#define USE_METHOD_ONE 0
#define USE_METHOD_TWO (1-USE_METHOD_ONE)
 
// octreer.cpp*
#include "pbrt.h"
#include "primitive.h"

int otherAxis[3][2] = { {1,2}, {0,2}, {0,1} };

// MailboxPrim Declarations
struct MailboxPrim {
	MailboxPrim(const Reference<Primitive> &p) {
		primitive = p;
		lastMailboxId = -1;
	}
	Reference<Primitive> primitive;
	int lastMailboxId;
};
// OctAccelNode Declarations
class OctAccelNode {
public:
	// OctAccelNode Public Methods
	OctAccelNode(){
		// Initial the children nodes as null
		for(int child = 0; child < 8; child++)
			children[child] = NULL;
		primitives = NULL;
		isLeaf = 1;
	}
	~OctAccelNode(){
		if(isLeaf && nPrims > 0)
			delete []primitives;
		else{
			for(int child = 0; child < 8; child++){
				delete children[child];
			}
		}
	}
	void makeLeaf(const vector<int> primNums, MailboxPrim **mailboxPrims){
		nPrims = primNums.size();
		if(nPrims <= 0){
			primitives = 0;
			return;
		}
		primitives = new MailboxPrim*[primNums.size()];
		for(int i = 0; i < nPrims; i++){
			primitives[i] = mailboxPrims[primNums[i]];
		}
		isLeaf = 1;
	}
	void makeInterior(int np[8]){
		nPrims = 0;
		if(primitives) delete []primitives; 
		for(int i = 0; i < 8; i++){
			if(np[i] != 0) children[i] = new OctAccelNode();
			else children[i] = NULL;
		}
		isLeaf = 0;
	}
#if(USE_METHOD_ONE)
	BBox bounds;
#endif
	Point pSplit;
	int nPrims;
	int isLeaf; // May be combined
	MailboxPrim **primitives;
	OctAccelNode *children[8];
};
struct BoundEdge {
	// BoundEdge Public Methods
	BoundEdge() { }
	BoundEdge(float tt, int pn, bool starting) {
		t = tt;
		primNum = pn;
		type = starting ? START : END;
	}
	bool operator<(const BoundEdge &e) const {
		if (t == e.t)
			return (int)type < (int)e.type;
		else return t < e.t;
	}
	float t;
	int primNum;
	enum { START, END } type;
};
// OctTreeRAccel Declarations
class  OctreeRAccel : public Aggregate {
public:
	// OctreeRAccel Public Methods
	OctreeRAccel(const vector<Reference<Primitive> > &p,
		int icost, int scost,
		float ebonus, int maxp, int maxDepth);
	BBox WorldBound() const { return bounds; }
	bool CanIntersect() const { return true; }
	~OctreeRAccel();
	void buildTree(OctAccelNode *node, const BBox &nodeBounds,
		const vector<BBox> &allPrimBounds, 	vector<int> &primNums, //int *primNums,
		int nPrims, int depth, BoundEdge *edges[3],
		int badRefines);
	bool Intersect(const Ray &ray, Intersection *isect) const;
	bool IntersectP(const Ray &ray) const;
//private:
	// OctreeRAccel Private Data
	int isectCost, traversalCost, maxPrims;
	float emptyBonus;
	u_int nMailboxes;
	MailboxPrim **mailboxPrims;
	mutable int curMailboxId;
	OctAccelNode root;	
	BBox bounds;
	//MemoryArena arena;
};

// OctreeRAccel Method Definitions
OctreeRAccel::OctreeRAccel(const vector<Reference<Primitive> > &p,
		int icost, int tcost,
		float ebonus, int maxp, int maxDepth)
	: isectCost(icost), traversalCost(tcost),
	maxPrims(maxp), emptyBonus(ebonus) {
	// Refine all primitives
	vector<Reference<Primitive > > prims;
	for (u_int i = 0; i < p.size(); ++i)
		p[i]->FullyRefine(prims);
	// Initialize mailboxes for _OctreeRAccel_
	curMailboxId = 0;
	nMailboxes = prims.size();
	mailboxPrims = new MailboxPrim *[nMailboxes];
	//mailboxPrims = (MailboxPrim *)AllocAligned(nMailboxes * sizeof(MailboxPrim));
	for (u_int i = 0; i < nMailboxes; ++i)
		mailboxPrims[i] = new MailboxPrim(prims[i]);
	// Build octree for accelerator
	if (maxDepth <= 0)
		maxDepth =
			Round2Int((5 + 1.3f * (Log2Int(float(prims.size()))))/2.0);
	//maxDepth = 0;
	// Compute bounds for octree construction
	vector<BBox> primBounds;
	vector<int> primNums;
	//int *primNums = new int[prims.size()];
	primBounds.reserve(prims.size());
	primNums.reserve(prims.size());
	for (u_int i = 0; i < prims.size(); ++i) {
		BBox b = prims[i]->WorldBound();
		bounds = Union(bounds, b);
		primBounds.push_back(b);
		primNums.push_back(i);
	}
	//root.initNode(primNums, prims.size(), mailboxPrims, bounds);	
	//delete []primNums;
	// Allocate working memory for octree construction
	BoundEdge *edges[3];
	for (int i = 0; i < 3; ++i)
		edges[i] = new BoundEdge[2*prims.size()];
	// Start recursive construction of octree
	buildTree(&root, bounds, primBounds, primNums, prims.size(), maxDepth, edges, 0);
	// Free working memory for octree construction
	for (int i = 0; i < 3; ++i)
		delete[] edges[i];
}

OctreeRAccel::~OctreeRAccel() {
	for (u_int i = 0; i < nMailboxes; ++i)
		delete mailboxPrims[i];
	delete []mailboxPrims;
	//FreeAligned(mailboxPrims);
	//FreeAligned(nodes);
}
void OctreeRAccel::buildTree(OctAccelNode *node, const BBox &nodeBounds,
		const vector<BBox> &allPrimBounds, vector<int> &primNums, 
		int nPrims, int depth, BoundEdge *edges[3], int badRefines){
	// Initialize the current node
#if(USE_METHOD_ONE)
	node->bounds = nodeBounds;
#endif
	// Initialize a leaf node and leave if termination criteria met
	if (nPrims <= maxPrims || depth == 0) {
		node->makeLeaf(primNums, mailboxPrims);		
		return;
	}	
	Vector d = nodeBounds.pMax - nodeBounds.pMin;
	int bestOffset[3];
	float bestCost;
	float bestCostSum = 0;
	float oldCost = isectCost * float(nPrims);
	float totalSA = (2.f * (d.x*d.y + d.x*d.z + d.y*d.z));
	float invTotalSA = 1.f / totalSA;
	Point pSplit;
	for(int axis = 0; axis < 3; axis++){
		bestCost = INFINITY;
		// Initialize edges for _axis_
		for (int i = 0; i < nPrims; ++i) {			
			int pn = primNums[i];
			const BBox &bbox = allPrimBounds[pn];
			edges[axis][2*i] = BoundEdge(allPrimBounds[pn].pMin[axis], pn, true);
			edges[axis][2*i+1] = BoundEdge(allPrimBounds[pn].pMax[axis], pn, false);
		}
		sort(&edges[axis][0], &edges[axis][2*nPrims]);
		// Compute cost of all splits for _axis_ to find best
		int nBelow = 0, nAbove = nPrims;
		bestOffset[axis] = 0;
		for (int i = 0; i < 2*nPrims; ++i) {
			if (edges[axis][i].type == BoundEdge::END) --nAbove;
			float edget = edges[axis][i].t;
			if (edget > nodeBounds.pMin[axis] &&
				edget < nodeBounds.pMax[axis]) {
				// Compute cost for split at _i_th edge
				int otherAxis0 = otherAxis[axis][0];
				int otherAxis1 = otherAxis[axis][1];
				float belowSA = 2 * (d[otherAxis0] * d[otherAxis1] +
			             			(edget - nodeBounds.pMin[axis]) *
									(d[otherAxis0] + d[otherAxis1]));
				float aboveSA = 2 * (d[otherAxis0] * d[otherAxis1] +
									(nodeBounds.pMax[axis] - edget) *
									(d[otherAxis0] + d[otherAxis1]));
				float pBelow = belowSA * invTotalSA;
				float pAbove = aboveSA * invTotalSA;
				float eb = (nAbove == 0 || nBelow == 0) ? emptyBonus : 0.f;
				float cost = traversalCost + isectCost * (1.f - eb) *
					(pBelow * nBelow + pAbove * nAbove);
				// Update best split if this is lowest cost so far
				if (cost < bestCost)  {
					bestCost = cost;
					bestOffset[axis] = i;
				}
			}
			if (edges[axis][i].type == BoundEdge::START) ++nBelow;
		}
		pSplit[axis] = edges[axis][bestOffset[axis]].t;
		if(bestCost > oldCost) ++badRefines;
		bestCostSum += bestCost;		
	}
	node->pSplit = pSplit;
	// Create leaf if no good splits were found	
	if ((bestCostSum > 12.f * oldCost && nPrims < 16) ||
		badRefines == 6) {
		node->makeLeaf(primNums, mailboxPrims);
		return;
	}

	// Allocate 8 dataset for 8 children	
	vector<int> childPrimNums[8];	
	int np[8];	
	for(int i = 0; i < 8; i++) np[i] = 0;	
	// Classify primitives with respect to split	
	bool over[8];
	for(int i = 0; i < nPrims; i++){
		int n = primNums[i];
		BBox dataBound = allPrimBounds[n];
		over[0] = over[1] =	over[2] = over[3] = (dataBound.pMin.x <= pSplit.x);
		over[4] = over[5] =	over[6] = over[7] = (dataBound.pMax.x  > pSplit.x);
		over[0] &= (dataBound.pMin.y <= pSplit.y);
		over[1] &= (dataBound.pMin.y <= pSplit.y);
		over[4] &= (dataBound.pMin.y <= pSplit.y);
		over[5] &= (dataBound.pMin.y <= pSplit.y);
		over[2] &= (dataBound.pMax.y  > pSplit.y);
		over[3] &= (dataBound.pMax.y  > pSplit.y);
		over[6] &= (dataBound.pMax.y  > pSplit.y);
		over[7] &= (dataBound.pMax.y  > pSplit.y);
		over[0] &= (dataBound.pMin.z <= pSplit.z);
		over[2] &= (dataBound.pMin.z <= pSplit.z);
		over[4] &= (dataBound.pMin.z <= pSplit.z);
		over[6] &= (dataBound.pMin.z <= pSplit.z);
		over[1] &= (dataBound.pMax.z  > pSplit.z);
		over[3] &= (dataBound.pMax.z  > pSplit.z);
		over[5] &= (dataBound.pMax.z  > pSplit.z);
		over[7] &= (dataBound.pMax.z  > pSplit.z);
		for(int child = 0; child < 8; child++){
			if(!over[child]) continue;
			np[child]++;
			childPrimNums[child].push_back(n);
		}
	}
	// Setup the childrens
	primNums.clear();
	node->makeInterior(np);
	for(int child = 0; child < 8; child++){
		if(np[child] == 0) continue;
		// Calculate the bound of the child
		BBox childBound;
		childBound.pMin.x = (child & 4) ? pSplit.x : nodeBounds.pMin.x;
		childBound.pMax.x = (child & 4) ? nodeBounds.pMax.x : pSplit.x;
		childBound.pMin.y = (child & 2) ? pSplit.y : nodeBounds.pMin.y;
		childBound.pMax.y = (child & 2) ? nodeBounds.pMax.y : pSplit.y;
		childBound.pMin.z = (child & 1) ? pSplit.z : nodeBounds.pMin.z;
		childBound.pMax.z = (child & 1) ? nodeBounds.pMax.z : pSplit.z;
		buildTree(node->children[child], childBound, allPrimBounds, 
			childPrimNums[child], np[child], depth-1, edges, badRefines);
		childPrimNums[child].clear();
	}
}
struct OctToDo {
	const OctAccelNode *node;
	float tmin, tmax;
#if(USE_METHOD_TWO)
	Point p;
#endif
	bool operator<(const OctToDo &o) const {
		return tmin < o.tmin;
	}
};
struct InterSplit {
	float t;
	int axis;
};
int tNearIdx[8][3] = {{0,1,2}, {0,1,5}, {0,4,2}, {0,4,5}, {3,1,2},
{3,1,5}, {3,4,2}, {3,4,5}};
int tFarIdx[8][3] = {{3,4,5}, {3,4,8}, {3,7,5}, {3,7,8}, {6,4,5},
{6,4,8}, {6,7,5}, {6,7,8}};
char nextChild[8][3] = {{4,2,1}, {5,3,0}, {6,0,3}, {7,1,2}, {0,6,5}, 
{1,7,4}, {2,4,7}, {3,5,6}};
bool OctreeRAccel::Intersect(const Ray &ray, Intersection *isect) const{
	// Compute initial parametric range of ray inside octree extent
	float tmin, tmax;
	if (!bounds.IntersectP(ray, &tmin, &tmax))
		return false;
	// Prepare to traverse octree for ray
	int rayId = curMailboxId++;
	Vector invDir(1.f/ray.d.x, 1.f/ray.d.y, 1.f/ray.d.z);
#define MAX_TODO 64
	OctToDo todo[MAX_TODO];	
	int todoPos = 0;
#if(USE_METHOD_ONE)
	OctToDo tempTodo[4];
#endif
#if(USE_METHOD_TWO)
	Point p = ray.o + tmin*ray.d;
	InterSplit tSplit[3];
#endif
	// Traverse octree nodes in order for ray	
	bool hit = false;
	const OctAccelNode *node = &root;
	while(node != NULL){		
		if(ray.maxt < tmin){
			break;
		}
		else if(node->isLeaf == 0){
#if(USE_METHOD_ONE)
			// Calculate all intersections
			float t[9];
			t[0] = (node->bounds.pMin.x - ray.o.x) * invDir.x;
			t[1] = (node->bounds.pMin.y - ray.o.y) * invDir.y;
			t[2] = (node->bounds.pMin.z - ray.o.z) * invDir.z;
			t[3] = (node->pSplit.x - ray.o.x) * invDir.x;
			t[4] = (node->pSplit.y - ray.o.y) * invDir.y;
			t[5] = (node->pSplit.z - ray.o.z) * invDir.z;
			t[6] = (node->bounds.pMax.x - ray.o.x) * invDir.x;
			t[7] = (node->bounds.pMax.y - ray.o.y) * invDir.y;
			t[8] = (node->bounds.pMax.z - ray.o.z) * invDir.z;
			int cnt = 0;
			for(int child = 0; child < 8; child++){				
				if(node->children[child] != NULL){
					float tt0 = ray.mint, tt1 = ray.maxt;	
					float tNear, tFar;
					int intersect = 1;
					OctAccelNode* children = node->children[child];
					for(int i = 0; i < 3; i++){
						//tNear = (children->bounds.pMin[i] - ray.o[i]) * invDir[i];
						//tFar = (children->bounds.pMax[i] - ray.o[i]) * invDir[i];
						tNear = t[tNearIdx[child][i]];
						tFar = t[tFarIdx[child][i]];
						if (tNear > tFar) swap(tNear, tFar);
						tt0 = tNear > tt0 ? tNear : tt0;
						tt1 = tFar  < tt1 ? tFar  : tt1;
						if (tt0 > tt1){
							intersect = 0;
							break;
						}
					}
					if(intersect == 0)
						continue;
					if(ray.maxt < tt0)
						continue;
					tempTodo[cnt].node = node->children[child];
					tempTodo[cnt].tmin = tt0;
					//tempTodo[cnt].tmax = tt1;
					++cnt;
					if(cnt == 4)
						break;
				}
			}
			switch(cnt)
			{
			case 0:
				break;
			case 1:
				todo[todoPos].node = tempTodo[0].node;
				todo[todoPos].tmin = tempTodo[0].tmin;
				++todoPos;
				break;
			case 2:
				if(tempTodo[0].tmin < tempTodo[1].tmin){
					// Add _tempTodo[1]_ first
					todo[todoPos].node = tempTodo[1].node;
					todo[todoPos].tmin = tempTodo[1].tmin;
					++todoPos;
					todo[todoPos].node = tempTodo[0].node;
					todo[todoPos].tmin = tempTodo[0].tmin;
					++todoPos;
				}
				else{
					// Add _tempTodo[0]_ first
					todo[todoPos].node = tempTodo[0].node;
					todo[todoPos].tmin = tempTodo[0].tmin;
					++todoPos;
					todo[todoPos].node = tempTodo[1].node;
					todo[todoPos].tmin = tempTodo[1].tmin;
					++todoPos;
				}
				break;
			case 3:
			case 4:
				sort(&tempTodo[0], &tempTodo[cnt]);
				for(int i = cnt-1; i >= 0 ; i--){
					todo[todoPos].node = tempTodo[i].node;
					todo[todoPos].tmin = tempTodo[i].tmin;
					//todo[todoPos].tmax = tempTodo[i].tmax;
					++todoPos;
				}
				break;
			}
#endif
#if(USE_METHOD_TWO)
			// Use _tmin_ to calculate P, and determine the index of the first child
			char child[4];
			child[0] = 0;
			if(p.x > node->pSplit.x) child[0] |= 4;
			if(p.y > node->pSplit.y) child[0] |= 2;
			if(p.z > node->pSplit.z) child[0] |= 1;
			// Calculate _t[axis]_, and put it into a list if it's with (tmin, tmax)
			int cnt = 0;
			float tTemp = (node->pSplit.x - ray.o.x)*invDir.x;
			if(tTemp > tmin && tTemp < tmax){
				tSplit[cnt].t = tTemp;
				tSplit[cnt].axis = 0;
				cnt++;
			}
			tTemp = (node->pSplit.y - ray.o.y)*invDir.y;
			if(tTemp > tmin && tTemp < tmax){
				tSplit[cnt].t = tTemp;
				tSplit[cnt].axis = 1;
				cnt++;
			}
			tTemp = (node->pSplit.z - ray.o.z)*invDir.z;
			if(tTemp > tmin && tTemp < tmax){
				tSplit[cnt].t = tTemp;
				tSplit[cnt].axis = 2;
				cnt++;
			}
			cnt++;
			int a0, a1, a2;
			switch(cnt){
				case 1:
					if(node->children[child[0]] != NULL){
						todo[todoPos].node = node->children[child[0]];
						todo[todoPos].tmin = tmin;
						todo[todoPos].tmax = tmax;
						todo[todoPos].p = ray.o + tmin*ray.d;
						todoPos++;
					}
					break;
				case 2:
					child[1] = nextChild[child[0]][tSplit[0].axis];
					// Add the second child
					if(node->children[child[1]] != NULL){
						todo[todoPos].node = node->children[child[1]];
						todo[todoPos].tmin = tSplit[0].t;
						todo[todoPos].tmax = tmax;
						todo[todoPos].p = ray.o + tSplit[0].t*ray.d;
						todoPos++;
					}					
					// Add the first child
					if(node->children[child[0]] != NULL){
						todo[todoPos].node = node->children[child[0]];
						todo[todoPos].tmin = tmin;
						todo[todoPos].tmax = tSplit[0].t;
						todo[todoPos].p = ray.o + tmin*ray.d;
						todoPos++;
					}
					break;
				case 3:
					if(tSplit[0].t < tSplit[1].t){
						a0 = 0;
						a1 = 1;
					}
					else{
						a0 = 1;
						a1 = 0;
					}
					child[1] = nextChild[child[0]][tSplit[a0].axis];
					child[2] = nextChild[child[1]][tSplit[a1].axis];
					// Add the third child
					if(node->children[child[2]] != NULL){
						todo[todoPos].node = node->children[child[2]];
						todo[todoPos].tmin = tSplit[a1].t;
						todo[todoPos].tmax = tmax;
						todo[todoPos].p = ray.o + tSplit[a1].t*ray.d;
						todoPos++;
					}
					// Add the second child
					if(node->children[child[1]] != NULL){
						todo[todoPos].node = node->children[child[1]];
						todo[todoPos].tmin = tSplit[a0].t;
						todo[todoPos].tmax = tSplit[a1].t;
						todo[todoPos].p = ray.o + tSplit[a0].t*ray.d;
						todoPos++;
					}
					// Add the first child
					if(node->children[child[0]] != NULL){
						todo[todoPos].node = node->children[child[0]];
						todo[todoPos].tmin = tmin;
						todo[todoPos].tmax = tSplit[a0].t;
						todo[todoPos].p = ray.o + tmin*ray.d;
						todoPos++;
					}
					break;
				case 4:
					// Sort _tSplit_
					if(tSplit[0].t < tSplit[1].t && tSplit[0].t < tSplit[2].t){
						a0 = 0;
						if(tSplit[1].t < tSplit[2].t){
							a1 = 1; 
							a2 = 2;
						}
						else{
							a1 = 2;
							a2 = 1;
						}
					}
					else if(tSplit[1].t < tSplit[0].t && tSplit[1].t < tSplit[2].t){
						a0 = 1;
						if(tSplit[0].t < tSplit[2].t){
							a1 = 0;
							a2 = 2;
						}
						else{
							a1 = 2;
							a2 = 0;
						}
					}
					else{
						a0 = 2;
						if(tSplit[0].t < tSplit[1].t){
							a1 = 0;
							a2 = 1;
						}
						else{
							a1 = 1; 
							a2 = 0;
						}
					}
					child[1] = nextChild[child[0]][tSplit[a0].axis];
					child[2] = nextChild[child[1]][tSplit[a1].axis];
					child[3] = nextChild[child[2]][tSplit[a2].axis];					
					// Add the fourth child
					if(node->children[child[3]] != NULL){
						todo[todoPos].node = node->children[child[3]];
						todo[todoPos].tmin = tSplit[a2].t;
						todo[todoPos].tmax = tmax;
						todo[todoPos].p = ray.o + tSplit[a2].t*ray.d;
						todoPos++;
					}
					// Add the third child
					if(node->children[child[2]] != NULL){
						todo[todoPos].node = node->children[child[2]];
						todo[todoPos].tmin = tSplit[a1].t;
						todo[todoPos].tmax = tSplit[a2].t;
						todo[todoPos].p = ray.o + tSplit[a1].t*ray.d;
						todoPos++;
					}
					// Add the second child
					if(node->children[child[1]] != NULL){
						todo[todoPos].node = node->children[child[1]];
						todo[todoPos].tmin = tSplit[a0].t;
						todo[todoPos].tmax = tSplit[a1].t;
						todo[todoPos].p = ray.o + tSplit[a0].t*ray.d;
						todoPos++;
					}
					// Add the first child
					if(node->children[child[0]] != NULL){
						todo[todoPos].node = node->children[child[0]];
						todo[todoPos].tmin = tmin;
						todo[todoPos].tmax = tSplit[a0].t;
						todo[todoPos].p = ray.o + tmin*ray.d;
						todoPos++;
					}
					break;
				default:
					break;
			}
#endif
		}
		else{
			// Check for intersections inside leaf node
			int nPrimitives = node->nPrims;
			for (int i = 0; i < nPrimitives; ++i) {
				MailboxPrim *mp = node->primitives[i];
				if (mp->lastMailboxId != rayId) {
					mp->lastMailboxId = rayId;
					if (mp->primitive->Intersect(ray, isect))
						hit = true;
				}
			}
		}
		// Grab next node to process from todo list		
		if (todoPos > 0) {
			--todoPos;
			node = todo[todoPos].node;
			tmin = todo[todoPos].tmin;
#if(USE_METHOD_TWO)
			tmax = todo[todoPos].tmax;
			p = todo[todoPos].p;
#endif
		}
		else
			break;
	}
	return hit;
}
bool OctreeRAccel::IntersectP(const Ray &ray) const {
	// Compute initial parametric range of ray inside octree extent
	float tmin, tmax;
	if (!bounds.IntersectP(ray, &tmin, &tmax))
		return false;
	// Prepare to traverse octree for ray
	int rayId = curMailboxId++;
	Vector invDir(1.f/ray.d.x, 1.f/ray.d.y, 1.f/ray.d.z);
#define MAX_TODO 64
	OctToDo todo[MAX_TODO];	
	int todoPos = 0;
#if(USE_METHOD_ONE)
	OctToDo tempTodo[4];
#endif
#if(USE_METHOD_TWO)
	Point p = ray.o + tmin*ray.d;
	InterSplit tSplit[3];
#endif		
	// Traverse octree nodes in order for ray	
	const OctAccelNode *node = &root;
	while(node != NULL){
		if(ray.maxt < tmin){
			break;
		}
		else if(node->isLeaf == 0){
#if(USE_METHOD_ONE)
			// Calculate all intersections
			float t[9];
			t[0] = (node->bounds.pMin.x - ray.o.x) * invDir.x;
			t[1] = (node->bounds.pMin.y - ray.o.y) * invDir.y;
			t[2] = (node->bounds.pMin.z - ray.o.z) * invDir.z;
			t[3] = (node->pSplit.x - ray.o.x) * invDir.x;
			t[4] = (node->pSplit.y - ray.o.y) * invDir.y;
			t[5] = (node->pSplit.z - ray.o.z) * invDir.z;
			t[6] = (node->bounds.pMax.x - ray.o.x) * invDir.x;
			t[7] = (node->bounds.pMax.y - ray.o.y) * invDir.y;
			t[8] = (node->bounds.pMax.z - ray.o.z) * invDir.z;
			int cnt = 0;
			for(int child = 0; child < 8; child++){
				if(node->children[child] != NULL){
					float tt0 = ray.mint, tt1 = ray.maxt;	
					float tNear, tFar;
					int intersect = 1;
					OctAccelNode* children = node->children[child];
					for(int i = 0; i < 3; i++){
						//tNear = (children->bounds.pMin[i] - ray.o[i]) * invDir[i];
						//tFar = (children->bounds.pMax[i] - ray.o[i]) * invDir[i];
						tNear = t[tNearIdx[child][i]];
						tFar = t[tFarIdx[child][i]];
						if (tNear > tFar) swap(tNear, tFar);
						tt0 = tNear > tt0 ? tNear : tt0;
						tt1 = tFar  < tt1 ? tFar  : tt1;
						if (tt0 > tt1){
							intersect = 0;
							break;
						}
					}
					if(intersect == 0)
						continue;
					if(ray.maxt < tt0)
						continue;
					tempTodo[cnt].node = node->children[child];
					tempTodo[cnt].tmin = tt0;
					//tempTodo[cnt].tmax = tt1;
					++cnt;
					if(cnt == 4)
						break;
				}
			}
			switch(cnt)
			{
			case 0:
				break;
			case 1:
				todo[todoPos].node = tempTodo[0].node;
				todo[todoPos].tmin = tempTodo[0].tmin;
				++todoPos;
				break;
			case 2:
				if(tempTodo[0].tmin < tempTodo[1].tmin){
					// Add _tempTodo[1]_ first
					todo[todoPos].node = tempTodo[1].node;
					todo[todoPos].tmin = tempTodo[1].tmin;
					++todoPos;
					todo[todoPos].node = tempTodo[0].node;
					todo[todoPos].tmin = tempTodo[0].tmin;
					++todoPos;
				}
				else{
					// Add _tempTodo[0]_ first
					todo[todoPos].node = tempTodo[0].node;
					todo[todoPos].tmin = tempTodo[0].tmin;
					++todoPos;
					todo[todoPos].node = tempTodo[1].node;
					todo[todoPos].tmin = tempTodo[1].tmin;
					++todoPos;
				}
				break;
			case 3:
			case 4:
				sort(&tempTodo[0], &tempTodo[cnt]);
				for(int i = cnt-1; i >= 0 ; i--){
					todo[todoPos].node = tempTodo[i].node;
					todo[todoPos].tmin = tempTodo[i].tmin;
					//todo[todoPos].tmax = tempTodo[i].tmax;
					++todoPos;
				}
				break;
			}
#endif
#if(USE_METHOD_TWO)
			// Use _tmin_ to calculate P, and determine the index of the first child
			char child[4];
			child[0] = 0;
			if(p.x > node->pSplit.x) child[0] |= 4;
			if(p.y > node->pSplit.y) child[0] |= 2;
			if(p.z > node->pSplit.z) child[0] |= 1;
			// Calculate _t[axis]_, and put it into a list if it's with (tmin, tmax)
			int cnt = 0;
			float tTemp = (node->pSplit.x - ray.o.x)*invDir.x;
			if(tTemp > tmin && tTemp < tmax){
				tSplit[cnt].t = tTemp;
				tSplit[cnt].axis = 0;
				cnt++;
			}
			tTemp = (node->pSplit.y - ray.o.y)*invDir.y;
			if(tTemp > tmin && tTemp < tmax){
				tSplit[cnt].t = tTemp;
				tSplit[cnt].axis = 1;
				cnt++;
			}
			tTemp = (node->pSplit.z - ray.o.z)*invDir.z;
			if(tTemp > tmin && tTemp < tmax){
				tSplit[cnt].t = tTemp;
				tSplit[cnt].axis = 2;
				cnt++;
			}
			cnt++;
			int a0, a1, a2;
			switch(cnt){
				case 1:
					if(node->children[child[0]] != NULL){
						todo[todoPos].node = node->children[child[0]];
						todo[todoPos].tmin = tmin;
						todo[todoPos].tmax = tmax;
						todo[todoPos].p = ray.o + tmin*ray.d;
						todoPos++;
					}
					break;
				case 2:
					child[1] = nextChild[child[0]][tSplit[0].axis];
					// Add the second child
					if(node->children[child[1]] != NULL){
						todo[todoPos].node = node->children[child[1]];
						todo[todoPos].tmin = tSplit[0].t;
						todo[todoPos].tmax = tmax;
						todo[todoPos].p = ray.o + tSplit[0].t*ray.d;
						todoPos++;
					}					
					// Add the first child
					if(node->children[child[0]] != NULL){
						todo[todoPos].node = node->children[child[0]];
						todo[todoPos].tmin = tmin;
						todo[todoPos].tmax = tSplit[0].t;
						todo[todoPos].p = ray.o + tmin*ray.d;
						todoPos++;
					}
					break;
				case 3:
					if(tSplit[0].t < tSplit[1].t){
						a0 = 0;
						a1 = 1;
					}
					else{
						a0 = 1;
						a1 = 0;
					}
					child[1] = nextChild[child[0]][tSplit[a0].axis];
					child[2] = nextChild[child[1]][tSplit[a1].axis];
					// Add the third child
					if(node->children[child[2]] != NULL){
						todo[todoPos].node = node->children[child[2]];
						todo[todoPos].tmin = tSplit[a1].t;
						todo[todoPos].tmax = tmax;
						todo[todoPos].p = ray.o + tSplit[a1].t*ray.d;
						todoPos++;
					}
					// Add the second child
					if(node->children[child[1]] != NULL){
						todo[todoPos].node = node->children[child[1]];
						todo[todoPos].tmin = tSplit[a0].t;
						todo[todoPos].tmax = tSplit[a1].t;
						todo[todoPos].p = ray.o + tSplit[a0].t*ray.d;
						todoPos++;
					}
					// Add the first child
					if(node->children[child[0]] != NULL){
						todo[todoPos].node = node->children[child[0]];
						todo[todoPos].tmin = tmin;
						todo[todoPos].tmax = tSplit[a0].t;
						todo[todoPos].p = ray.o + tmin*ray.d;
						todoPos++;
					}
					break;
				case 4:
					// Sort _tSplit_
					if(tSplit[0].t < tSplit[1].t && tSplit[0].t < tSplit[2].t){
						a0 = 0;
						if(tSplit[1].t < tSplit[2].t){
							a1 = 1; 
							a2 = 2;
						}
						else{
							a1 = 2;
							a2 = 1;
						}
					}
					else if(tSplit[1].t < tSplit[0].t && tSplit[1].t < tSplit[2].t){
						a0 = 1;
						if(tSplit[0].t < tSplit[2].t){
							a1 = 0;
							a2 = 2;
						}
						else{
							a1 = 2;
							a2 = 0;
						}
					}
					else{
						a0 = 2;
						if(tSplit[0].t < tSplit[1].t){
							a1 = 0;
							a2 = 1;
						}
						else{
							a1 = 1; 
							a2 = 0;
						}
					}
					child[1] = nextChild[child[0]][tSplit[a0].axis];
					child[2] = nextChild[child[1]][tSplit[a1].axis];
					child[3] = nextChild[child[2]][tSplit[a2].axis];
					// Add the fourth child
					if(node->children[child[3]] != NULL){
						todo[todoPos].node = node->children[child[3]];
						todo[todoPos].tmin = tSplit[a2].t;
						todo[todoPos].tmax = tmax;
						todo[todoPos].p = ray.o + tSplit[a2].t*ray.d;
						todoPos++;
					}
					// Add the third child
					if(node->children[child[2]] != NULL){
						todo[todoPos].node = node->children[child[2]];
						todo[todoPos].tmin = tSplit[a1].t;
						todo[todoPos].tmax = tSplit[a2].t;
						todo[todoPos].p = ray.o + tSplit[a1].t*ray.d;
						todoPos++;
					}
					// Add the second child
					if(node->children[child[1]] != NULL){
						todo[todoPos].node = node->children[child[1]];
						todo[todoPos].tmin = tSplit[a0].t;
						todo[todoPos].tmax = tSplit[a1].t;
						todo[todoPos].p = ray.o + tSplit[a0].t*ray.d;
						todoPos++;
					}
					// Add the first child
					if(node->children[child[0]] != NULL){
						todo[todoPos].node = node->children[child[0]];
						todo[todoPos].tmin = tmin;
						todo[todoPos].tmax = tSplit[a0].t;
						todo[todoPos].p = ray.o + tmin*ray.d;
						todoPos++;
					}
					break;
				default:
					break;
			}
#endif
		}
		else{
			// Check for intersections inside leaf node
			int nPrimitives = node->nPrims;
			for (int i = 0; i < nPrimitives; ++i) {
				MailboxPrim *mp = node->primitives[i];
				if (mp->lastMailboxId != rayId) {
					mp->lastMailboxId = rayId;
					if (mp->primitive->IntersectP(ray))
						return true;
				}
			}
		}
		// Grab next node to process from todo list
		if (todoPos > 0) {
			--todoPos;			
			node = todo[todoPos].node;
			tmin = todo[todoPos].tmin;			
#if(USE_METHOD_TWO)
			tmax = todo[todoPos].tmax;
			p = todo[todoPos].p;
#endif
		}
		else
			break;	
	}
	return false;
}
extern "C" DLLEXPORT Primitive *CreateAccelerator(const vector<Reference<Primitive> > &prims,
		const ParamSet &ps) {
	int isectCost = ps.FindOneInt("intersectcost", 80);
	int travCost = ps.FindOneInt("traversalcost", 1);
	float emptyBonus = ps.FindOneFloat("emptybonus", 0.5f);
	int maxPrims = ps.FindOneInt("maxprims", 1);
	int maxDepth = ps.FindOneInt("maxdepth", -1);
	return new OctreeRAccel(prims, isectCost, travCost,
		emptyBonus, maxPrims, maxDepth);
}
