#ifndef __SpatialGridWalker_h 
#define __SpatialGridWalker_h 

//-----------------------------------------------------------------------------
//
//	Class: SpatialGridWalker
//	
//	Purpose: This class can be used to walk through all the voxels that
//			 are intersected by a particular ray.  Voxel cells will be
//			 visited in order of increasing distance from the ray origin.
//			 If the origin of the ray lies outside the voxel grid, it will
//			 be advanced to its nearest intersection with the grid, if it
//			 does intersect the grid.  If the ray does not intersect the
//			 grid at all, the isDone() method will return true immediately
//			 when the iterator is created.
//
//			 Loops with this iterator should look like:
//
//				SpatialGridWalker it = voxelGrid->getRayIterator(origin,dir);
//				while( !it.isDone() )
//				{
//					// do stuff
//					it.next();
//				}
//
//	Algorithm:
//
//		The ray is traveling through an axis-aligned grid of voxels.  For
//		each step of the iterator, we advance the ray to the next voxel, which
//		is adjacent to the current voxel along either the x, y, or z axis.
//		Thus, the decision at each step is which axis to advance along.
//
//		At all times, the ray stores the parametric distances (t-values) from 
//		its current position to its x,y,z neighbors.  Whichever of these
//		distances is lowest dictates which voxel we move to next.
//
//		When we move to the next voxel, we must update the parametric distances.
//		Say we decided to advance along x by the parametric value t.  Now we
//		just update the y and z distances by subtracting t from them.  To 
//		compute the new x distance, we just divide the voxel size in x by the 
//		ray direction's x component - this gives the parametric distance 
//		required to walk across the voxel in that dimension.
//
//		After updating the distances, we also must choose which is the next
//		axis we will advance along - this is just a matter of figuring out
//		which axis' parametric distance value is now the lowest.
// 
// 
//-----------------------------------------------------------------------------

class SpatialGrid; 

class SpatialGridWalker { 
public:

	//	constructor specifies ray details and which grid to walk
	//
	SpatialGridWalker( const MPoint& origin,
		const MVector& direction,
		SpatialGrid *grid );

	//	contents of current voxel. 
	//
	MUintArray *		voxelContents();
	gridPoint3<int>				gridLocation(); 

	//	ray-parametric distances to the start and end of the current
	//	voxel.
	//
	float	curVoxelStartRayParam();
	float	curVoxelEndRayParam();

	//	advances to next voxel along ray
	//
	void 	 next();

	//	returns true if ray has left the voxel grid after the last
	//	next() call, or if the ray never intersects the voxel grid
	//
	bool isDone();

private:

	//	grid being walked through
	// 
	SpatialGrid *		fVoxelGrid;

	//	ray parameters
	//
	MPoint			fOrigin;
	MVector		fDirection;

	//	indices for current voxel in the traversal
	//
	gridPoint3<int>				fCurVoxelCoords;

	//	parametric distances along the ray to the
	//	next voxel grid cells in the x, y, and z directions
	//
	gridPoint3<float>				fCurDistances;

	//	decides which axis the ray will hit next (0=x, 1=y, 2=z)
	//
	int				fNextAxis;

	//	current distance along the ray to the first intersection point
	//	with the current voxel
	//
	float				fCurVoxelStartRayParam;
	float				fCurVoxelEndRayParam;
	//	false if the ray is currently in a valid voxel, true otherwise
	//
	bool			fDone;
};

#endif