#include <gpuCacheSpatialGrid.h> 
#include <gpuCacheSpatialGridWalker.h> 
#include <MIntArray.h> 
#include <gpuCacheIsectUtil.h>

SpatialGridWalker::SpatialGridWalker( 
	const MPoint& origin,
	const MVector& direction,
	SpatialGrid *grid )
	//
	//	Description:
	//
	//		Initializes the ray for its walk through the voxel grid.
	//		We must do the following:
	//
	//		- if the ray is outside the voxel grid bounding box, we must 
	//		  snap it to its closest intersection with the box.  
	//
	//		- compute the initial fDistance values, which give the parametric
	//		  distances to the x,y, and z axes along the ray
	//
	//		- compute the initial fNextAxis value, which tells us which
	//		  axis we will next advance along
	//
	:
fVoxelGrid(grid),
	fOrigin(origin),
	fDirection(direction),
	fDone(false)
{ 
	//	First, snap the ray to the bounding box if necessary
	//
	if( !grid->bounds().contains( origin ) )
	{
		MPoint boxIntersectionPt;
		if(GPUCache::gpuCacheIsectUtil::firstRayIntersection((grid->bounds().min()), (grid->bounds().max()), origin, direction, NULL, &boxIntersectionPt))
		{
			//	ray intersects bounding box, so snap the origin to the
			//	closest hit on the outside of the box
			//
			fOrigin = MPoint( boxIntersectionPt.x, 
				boxIntersectionPt.y, 
				boxIntersectionPt.z );

			float dist = (float) boxIntersectionPt.distanceTo( origin );
			float length = (float) direction.length();
			fCurVoxelStartRayParam = dist/ length;

			fDone = false;
		}
		else
		{
			//	ray doesn't hit box, so it can't hit anything inside the
			//	voxel grid, thus the iterator is done
			//
			fDone = true;
			return;
		}
	}
	else
	{
		fCurVoxelStartRayParam = 0;
	}

	fNextAxis = 0;
	fCurDistances = gridPoint3<float>( 1.0e8, 1.0e8, 1.0e8 );

	//	figure out which grid cell we are in, and how far we are from
	//	the lower corner of that cell
	//
	MPoint residual;
	grid->getVoxelCoords( fOrigin, fCurVoxelCoords, &residual );

	//	for each axis, figure out how far we need to follow the ray before
	//	we hit the next grid line in that axis.  the parametric value to 
	//	the grid line is just the actual distance to the line divided by
	//	the ray's component along the axis.
	//
	for( int axis = 0; axis < 3; axis++ )
	{
		//	take into account that we may be heading towards the next-lowest
		//	grid line or the next-highest, depending on the sign of the ray
		//	direction coordinate for this axis
		//
		if( fDirection[axis] > 0 )
		{
			fCurDistances[axis] = (grid->fVoxelSizes[axis]-
				residual[axis])/fDirection[axis];
		}
		else if( fDirection[axis] < 0 )
		{
			fCurDistances[axis] = -(residual[axis]/fDirection[axis]);
		}
		else
		{
			//	ray direction component along this axis is 0, meaning ray will
			//	never reach the grid cell adjacent along this axis.  just set
			//	the distance to huge value to make sure that we never advance
			//	along that axis
			//
			fCurDistances[axis] = 1.0e8;
		}

		//	store which axis has the smallest distance
		//
		if( fCurDistances[axis] < fCurDistances[fNextAxis] )
		{
			fNextAxis = axis;
		}
	}

	//	figure out total parametric distance from ray origin to end of
	//	this voxel
	//
	fCurVoxelEndRayParam = fCurVoxelStartRayParam + fCurDistances[fNextAxis];
}

void SpatialGridWalker::next()
	//
	//	Description:
	//
	//		Walks the iterator to the voxel adjacent to the current voxel
	//		that the ray will hit next.	
	//
	//		The axis specified by fNextAxis (x=0, y=1, z=2) tells us which
	//		is closest, so we just advance along that axis, and update
	//		the fDistance distances and the fNextAxis value.  We also need
	//		to watch for when the ray leaves the grid, in which case the
	//		fDone member is set to true to indicate that all voxels have
	//		been traversed.
	//
{
	//	axes are represented by indices x=0, y=1, z=2, which makes it
	//	easy to write code that operates on any axis, rather than
	//	having to explicitly code cases for x, y, and z.  
	//
	int curAxis = fNextAxis;
	int otherAxis1 = (curAxis+1)%3;
	int otherAxis2 = (curAxis+2)%3;

	//	we are going to go to the voxel that is adjacent to the current one
	//	along the fNextAxis axis.  Figure out if we are going to a higher
	//	or lower voxel, and figure out if we are leaving the grid.
	//	
	if( fDirection[curAxis] >= 0.0 )
	{
		fCurVoxelCoords[curAxis] += 1;
		if( fCurVoxelCoords[curAxis] >= fVoxelGrid->fNumVoxels[curAxis] )
		{
			fDone = true;
		}
	}
	else
	{
		fCurVoxelCoords[curAxis] -= 1;
		if( fCurVoxelCoords[curAxis] < 0 )
		{
			fDone = true;
		}
	}

	fCurVoxelStartRayParam += fCurDistances[curAxis];

	//	update the fCurDistances, the parametric distances to the closest
	//	adjacent voxels in the x,y,z directions.  We know that
	//	fCurDistances[curAxis] is the smallest, and we are moving that far,
	//	so just subtract that value from the distances for the other axes
	//	
	fCurDistances[otherAxis1] -= fCurDistances[curAxis];
	fCurDistances[otherAxis2] -= fCurDistances[curAxis];

	//	update the distance for the current axis.  Since we have advanced to
	//	the boundary of a voxel along that axis, the new required distance
	//	is a full voxel width in the specified axis.  Make sure to get the
	//	sign right - the distance must always be positive.
	//
	fCurDistances[curAxis] = fVoxelGrid->fVoxelSizes[curAxis] / 
		fabs(fDirection[curAxis]);

	//	figure out which axis now has the smallest distance.  It could be
	//	x, y, or z
	//
	if( fCurDistances[otherAxis1] < fCurDistances[otherAxis2] )
	{
		if( fCurDistances[otherAxis1] < fCurDistances[fNextAxis] )
		{
			fNextAxis = otherAxis1;
		}
	}
	else
	{
		if( fCurDistances[otherAxis2] < fCurDistances[fNextAxis] )
		{
			fNextAxis = otherAxis2;
		}
	}

	//	recompute ray-parametric distance to end of new voxel
	//
	fCurVoxelEndRayParam = fCurVoxelStartRayParam + fCurDistances[fNextAxis];
}

bool SpatialGridWalker::isDone()
	//
	//	Description:
	//
	//		Returns true when the ray has traversed all voxel grid cells
	//		that it intersects.
	//
{
	return fDone;
}

float SpatialGridWalker::curVoxelStartRayParam()
	//
	//	Description:
	//
	//		Returns ray-parametric distance to the start of the current
	//		voxel.  This is useful for determining whether all the voxel
	//		contents lie beyond a particular distance from the ray origin.
	//
{
	return fCurVoxelStartRayParam;
}

float SpatialGridWalker::curVoxelEndRayParam()
	//
	//	Description:
	//
	//		Returns ray-parametric distance to the end of the current
	//		voxel.  
	//
{
	return fCurVoxelEndRayParam;
}

MUintArray *SpatialGridWalker::voxelContents()
	//
	//	Description:
	//
	//		Returns the contents of the voxel in which the iterator
	//		currently resides.  This is a list of triangles that
	//		can be NULL if no triangles are found in the voxel.
	//
{
	return fVoxelGrid->getVoxelContents( fCurVoxelCoords );
}

gridPoint3<int> 
	SpatialGridWalker::gridLocation()
	//
	// Description: 
	//  Returns the current location within the grid. 
	//
{
	return fCurVoxelCoords; 
}