/* -----------------------------------------------------------------------------
	GSFramework
	Copyright 2001-2013 Emmanuel Julien. All Rights Reserved.
----------------------------------------------------------------------------- */


		#include "bih/bih.h"

		using namespace GS;
		using namespace GS::BIH;


//------------------------------------------------------------------------------
void				Tree::Raytrace(Trace &trace, const Vector4 &s, const Vector4 &d, float l, void *parm)
{
	trace.has_i = false;
	trace.i_t = -1;
	trace.node_visited = 0;
	trace.stack_pos = 0;

	// Intersect BIH bounding volume.
	float tmin, tmax;
	if	(!minmax.IntersectRay(s, d, tmin, tmax))
		return;

	// Reject if intersection is too far away.
	if	((l > 0) && (tmin >= l))
		return;

	// Initialize trace.
	trace.s = s;
	trace.d = d;

	tmax = ((l > 0) && (tmax > l)) ? l : tmax;

	// Iterative trace.
	float i_t[2];

	for	(Node *node = root; node; )
	{
		if	(!trace.has_i || ((tmin < trace.i_t) && trace.want_closest))	// Only bother about rays that could lead to a closer hit.
		{
			while (node->axis != 3)
			{
				if	(d[node->axis] == 0)			// Axis aligned.
				{
					if	(node->split[0] > s[node->axis])
					{
						if	(s[node->axis] > node->split[1])
						{
							trace.stack[trace.stack_pos].node = &((Node *)node->p)[1];
							trace.stack[trace.stack_pos].tmin = tmin;
							trace.stack[trace.stack_pos++].tmax = tmax;
						}
						node = &((Node *)node->p)[0];
					}
					else	if	(s[node->axis] > node->split[1])
							node = &((Node *)node->p)[1];
					else	break;	// Empty space.
				}
				else
				{
					float idn = 1.f / d[node->axis];
					i_t[0] = (node->split[0] - s[node->axis]) * idn;
					i_t[1] = (node->split[1] - s[node->axis]) * idn;

					int min = d[node->axis] > 0 ? 0 : 1, max = 1 - min;

					if	(i_t[min] > tmin)
					{
						if	(tmax > i_t[max])
						{
							trace.stack[trace.stack_pos].node = &((Node *)node->p)[max];
							trace.stack[trace.stack_pos].tmin = (i_t[max] > tmin) ? i_t[max] : tmin;
							trace.stack[trace.stack_pos++].tmax = tmax;
						}
						node = &((Node *)node->p)[min];
						tmax = (i_t[min] < tmax) ? i_t[min] : tmax;
					}
					else	if	(tmax > i_t[max])
					{
						node = &((Node *)node->p)[max];
						tmin = (i_t[max] > tmin) ? i_t[max] : tmin;
					}
					else	break;	// Empty space.
				}
				trace.node_visited++;
			}
			if	(node->axis == 3)
				TraceLeaf(node, tmin, tmax, trace, parm);
		}

		if	(!trace.stack_pos)
			break;

		node = trace.stack[--trace.stack_pos].node;
		tmin = trace.stack[trace.stack_pos].tmin;
		tmax = trace.stack[trace.stack_pos].tmax;
	}
}
//------------------------------------------------------------------------------