/*******************************************************

octree traversal algorithm as described in paper

"An Efficient Parametric Algorithm for Octree Traversal"

by J. Revelles, C. Urena and M. Lastra.

see revision 37 for original recursive version

*******************************************************/

struct OctreeTravState

	Float tx0,ty0,tz0,tx1,ty1,tz1,txm,tym,tzm;

	OctreeNode *node;

	int next;

	OctreeTravState() {};

	OctreeTravState(

		const Float atx0, const Float aty0, const Float atz0,

		const Float atx1, const Float aty1, const Float atz1,

		const Float atxm, const Float atym, const Float atzm,

		OctreeNode *const anode, const int anext):

		tx0(atx0), ty0(aty0), tz0(atz0), tx1(atx1), ty1(aty1), tz1(atz1),

		txm(atxm), tym(atym), tzm(atzm), node(anode), next(anext) {};

};

inline const int &next_node(const Float &txm, const int &xnode,

	const Float &tym, const int &ynode, const Float &tzm, const int &znode)

	OctreeTravState st[max_depth+1];

	register OctreeTravState *st_cur = st;

#	define node	st_cur->node

#	define tx0	st_cur->tx0

#	define ty0	st_cur->ty0

#	define tz0	st_cur->tz0

#	define tx1	st_cur->tx1

#	define ty1	st_cur->ty1

#	define tz1	st_cur->tz1

#	define txm	st_cur->txm

#	define tym	st_cur->tym

#	define tzm	st_cur->tzm

	Vector3 ro(ray.o);

	Vector3 rdir(1.0/ray.dir.x, 1.0/ray.dir.y, 1.0/ray.dir.z);

	tx0 = (bbox.L.x - ro.x) * rdir.x;

	tx1 = (bbox.H.x - ro.x) * rdir.x;

	ty0 = (bbox.L.y - ro.y) * rdir.y;

	ty1 = (bbox.H.y - ro.y) * rdir.y;

	tz0 = (bbox.L.z - ro.z) * rdir.z;

	tz1 = (bbox.H.z - ro.z) * rdir.z;

	if (max3(tx0,ty0,tz0) > min3(tx1,ty1,tz1))

		return NULL;

	node = root;

	st_cur->next = -1;

	Shape *nearest_shape = NULL;

	while (nearest_shape == NULL)

	{

		if (st_cur->next == -1)

		{

			st_cur->next = 8;

			// if ray does intersect this node

			if (!(tx1 < 0.0 || ty1 < 0.0 || tz1 < 0.0))

			{

				if (node->isLeaf())

				{

					ShapeList::iterator shape;

					register Float mindist = max3(tx0,ty0,tz0);

					/* correct & slow */

					//Float dist = min(min3(tx1,ty1,tz1),nearest_distance);

					/* faster */

					register Float dist = nearest_distance;

					for (shape = node->shapes->begin(); shape != node->shapes->end(); shape++)

						if (*shape != origin_shape && (*shape)->intersect(ray, dist) && dist >= mindist)

						{

							nearest_shape = *shape;

							nearest_distance = dist;

						}

				}

				else

				{

					txm = 0.5 * (tx0+tx1);

					tym = 0.5 * (ty0+ty1);

					tzm = 0.5 * (tz0+tz1);

					// first node

					st_cur->next = 0;

					if (tx0 > ty0)

					{

						if (tx0 > tz0)

						{ // YZ

							if (tym < tx0)

								st_cur->next |= 2;

							if (tzm < tx0)

								st_cur->next |= 1;

						}

						else

						{ // XY

							if (txm < tz0)

								st_cur->next |= 4;

							if (tym < tz0)

								st_cur->next |= 2;

						}

					}

					else

					{

						if (ty0 > tz0)

						{ // XZ

							if (txm < ty0)

								st_cur->next |= 4;

							if (tzm < ty0)

								st_cur->next |= 1;

						}

						else

						{ // XY

							if (txm < tz0)

								st_cur->next |= 4;

							if (tym < tz0)

								st_cur->next |= 2;

						}

					}

				}

			}

		}

		while (st_cur->next == 8)

		{

			// pop state from stack

			if (st_cur == st)

				return NULL; // nothing to pop, finish

			--st_cur;

		}

		// push current state

		*(st_cur+1) = *st_cur;

		++st_cur;

		switch (st_cur->next)

		{

			case 0:

				tx1 = txm;

				ty1 = tym;

				tz1 = tzm;

				node = node->getChild(a);

				(st_cur-1)->next = next_node(txm, 4, tym, 2, tzm, 1);

				break;

			case 1:

				tz0 = tzm;

				tx1 = txm;

				ty1 = tym;

				node = node->getChild(1^a);

				(st_cur-1)->next = next_node(txm, 5, tym, 3, tz1, 8);

				break;

			case 2:

				ty0 = tym;

				tx1 = txm;

				tz1 = tzm;

				node = node->getChild(2^a);

				(st_cur-1)->next = next_node(txm, 6, ty1, 8, tzm, 3);

				break;

			case 3:

				ty0 = tym;

				tz0 = tzm;

				tx1 = txm;

				node = node->getChild(3^a);

				(st_cur-1)->next = next_node(txm, 7, ty1, 8, tz1, 8);

				break;

			case 4:

				tx0 = txm;

				ty1 = tym;

				tz1 = tzm;

				node = node->getChild(4^a);

				(st_cur-1)->next = next_node(tx1, 8, tym, 6, tzm, 5);

				break;

			case 5:

				tx0 = txm;

				tz0 = tzm;

				ty1 = tym;

				node = node->getChild(5^a);

				(st_cur-1)->next = next_node(tx1, 8, tym, 7, tz1, 8);

				break;

			case 6:

				tx0 = txm;

				ty0 = tym;

				tz1 = tzm;

				node = node->getChild(6^a);

				(st_cur-1)->next = next_node(tx1, 8, ty1, 8, tzm, 7);

				break;

			case 7:

				tx0 = txm;

				ty0 = tym;

				tz0 = tzm;

				node = node->getChild(7^a);

				(st_cur-1)->next = 8;

				break;

		}

		st_cur->next = -1;

	}

	return nearest_shape;