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

#include <MPointArray.h>

SpatialGrid::SpatialGrid( 
	const MBoundingBox& boundingBox, 
	const gridPoint3<int>& numVoxels 
	)
	//
	//	Description:
	//
	//		Constructure just initializes bounding box sizes and sets
	//		all voxel entries to NULL pointers.
	//
	:	fBounds(boundingBox),
	fNumVoxels(numVoxels)
{
	//	artificially expand the bounding box if is too small along one or more
	//	axes
	//
	double minSize[3] = { 0.01, 0.01, 0.01 };
	expandBBoxByPercentage( fBounds, 1.0, minSize );
	
	//	figure out voxel sizes
	//
	fVoxelSizes[0] = fBounds.width() / fNumVoxels[0];
	fVoxelSizes[1] = fBounds.height() / fNumVoxels[1];
	fVoxelSizes[2] = fBounds.depth() / fNumVoxels[2];

	//	make sure none of the voxels are tiny along one dimension
	//
	if( fVoxelSizes[0] < 0.01 )
	{
		fVoxelSizes[0] = fBounds.width();
		fNumVoxels[0] = 1;
	}

	if( fVoxelSizes[1] < 0.01 )
	{
		fVoxelSizes[1] = fBounds.height();
		fNumVoxels[1] = 1;
	}

	if( fVoxelSizes[2] < 0.01 )
	{
		fVoxelSizes[2] = fBounds.depth();
		fNumVoxels[2] = 1;
	}

	//	NULL out all voxel contents
	//
	fVoxels.clear();
	unsigned int totalVoxels = fNumVoxels[0] * fNumVoxels[1] * fNumVoxels[2];
	for( unsigned int i = 0; i < totalVoxels; i++ )
	{
		fVoxels.push_back(NULL);
	}
}

SpatialGrid::~SpatialGrid()
	//
	//	Description:
	//
	//		Just delete non-empty voxel grid entries.
	//
{
	int numVoxels = fNumVoxels[0] * fNumVoxels[1] * fNumVoxels[2];
	for( int v = 0; v < numVoxels; v++ )
	{
		if( fVoxels[v] != NULL )
		{
			delete fVoxels[v];
		}
	}
}

//
//	Some simple accessors
//
const gridPoint3<int>& SpatialGrid::getNumVoxels()
{
	return fNumVoxels;
}

void SpatialGrid::bounds( MPoint& lowerCorner, MPoint& upperCorner )
{
	lowerCorner = fBounds.min();
	upperCorner = fBounds.max();
}

const MBoundingBox& SpatialGrid::bounds()
{
	return fBounds;
}

int SpatialGrid::getLinearVoxelIndex( const gridPoint3<int>& index ) const
	//
	//	Description:
	//
	//		Figures out which linear array element represents the
	//		voxel with the given x,y,z indices.  Remember, voxels
	//		are stored by increasing order of X, then Y, then Z coordinate
	//		indices.
	//
{
	return index[2]*(fNumVoxels[0]*fNumVoxels[1]) 
		+ index[1]*fNumVoxels[0] 
	+ index[0];
}

void 
	SpatialGrid::getVoxelRange(
	const MBoundingBox& box,
	gridPoint3<int>& minIndices,
	gridPoint3<int>& maxIndices 
	) const
	//
	//	Description:
	//
	//		Given a bounding box, compute the min and max voxel
	//		indices (in x, y, z) of the cells that intersect the box.
	//
{
	//	get bbox corners
	//
	const MPoint& minPt = box.min();
	const MPoint& maxPt = box.max();

	//	return indices for min/max corners
	//
	getVoxelCoords( minPt, minIndices, NULL );
	getVoxelCoords( maxPt, maxIndices, NULL );
}

void SpatialGrid::getVoxelCoords( 
	const MPoint& point, 
	gridPoint3<int>& coords,
	MPoint *residuals ) const
	//
	//	Description:
	//
	//		Given a point, compute the x,y,z indices of the voxel grid
	//		in which it resides.  Optionally, return residual which gives
	//		distance from point to next-lowest grid line value in each
	//		dimension.
	//
{
	//	get point relative to voxel grid lower corner
	//
	MPoint relPoint = point - fBounds.min();

	//	get indices for each axis
	//
	for( int axis = 0; axis < 3; axis++ )
	{
		//	figure out which cell point resides in
		//
		float voxSpace = relPoint[axis] / fVoxelSizes[axis];
		coords[axis] = (int)floor( voxSpace );

		//	clamp coordinate to valid range
		//
		if( coords[axis] < 0 ) 
		{
			coords[axis] = 0;
		}
		else if( coords[axis] >= fNumVoxels[axis] )
		{
			coords[axis] = fNumVoxels[axis]-1;
		}

		//	compute residual
		//		
		if( residuals != NULL )
		{
			(*residuals)[axis] = fVoxelSizes[axis]*(voxSpace-coords[axis]);
		}
	}
}

void SpatialGrid::expandBBoxByPercentage( 
	MBoundingBox& bbox,
	double percentage,
	double min[3] 
)
	//
	//	Description:
	//
	//		Expands the given bounding box by the given percentage
	//		in all dimensions.  Percentage should be a value between
	//		0 and 1, representing 0% to 100%.
	//
	//		The optional 3 "min" values specify minimum sizes along each
	//		axis that the bounding box size will be expanded to.  This
	//		is useful for situations where one of the box axes is so small
	//		that a percentagewise increase will not be meaningful.
	//
{
	percentage += 1.0;

	MPoint c = bbox.center();

	float w = bbox.width();
	float h = bbox.height();
	float d = bbox.depth();

	//	clamp the box sizes to the minimums, if given
	//
	if( min != NULL )
	{	
		if( w < min[0] )
		{
			w = min[0];
		}

		if( h < min[1] ) 
		{
			h = min[1];
		}

		if( d < min[2] )
		{
			d = min[2];
		}
	}

	//	increase the box size
	//
	MVector offset(w, h, d);
	offset *= (0.5f * percentage);

	bbox.expand( c + offset);
	bbox.expand( c - offset);
}

void SpatialGrid::getClosestVoxelCoords( 
	const MPoint& point, 
	gridPoint3<int>& coords) const
	//
	//	Description:
	//
	//		Given a point, compute the x,y,z indices of the voxel grid
	//		that it is closest to.   
	//
{	
	MPoint c1 = fBounds.min() + MVector(fBounds.width()/4, fBounds.height()/4, fBounds.depth()/4);
	MPoint c2 = fBounds.max() - MVector(fBounds.width()/4, fBounds.height()/4, fBounds.depth()/4);
	MBoundingBox bounds(c1,c2);
	MPoint relPoint;
	if(bounds.contains(point)){
		relPoint = point - fBounds.min();
	} else {
		//snap to bbox
		MPoint closestPoint = point;
		GPUCache::gpuCacheIsectUtil::getClosestPointOnBox(point, bounds, closestPoint);
		relPoint = closestPoint - fBounds.min();
	} 

	for( int axis = 0; axis < 3; axis++ )
	{
		//	figure out which cell point resides in
		//
		float voxSpace = relPoint[axis] / fVoxelSizes[axis];
		coords[axis] = (int)floor( voxSpace );
	}
	
}

bool SpatialGrid::isValidVoxel(gridPoint3<int>& vox){
	if(vox[0]>=0 && vox[0]<fNumVoxels[0] && vox[1]>=0 && vox[1]<fNumVoxels[1] && vox[2]>=0 && vox[2]<fNumVoxels[2]) 
		return true;
	return false;
}

MUintArray *
	SpatialGrid::getVoxelContents( 
	const gridPoint3<int>& index 
	)
	//
	//	Description:
	//
	//		Returns list of triangles for given voxel.  Allocates the array
	//		if it doesn't exist already
	//
{
	int linearIndex = getLinearVoxelIndex( index );
	if( fVoxels[linearIndex] == NULL )
	{
		fVoxels[linearIndex] = new MUintArray;
	}

	return fVoxels[linearIndex];
}

float SpatialGrid::getMemoryFootprint()
	//
	//	Description:
	//
	//		Returns total amount of memory used by acceleration
	//		structure.  This is the sum of the physical sizes of
	//		all the voxel entries, plus the physical size of the 
	//		linear voxel array as well.
	//
	//		The result is returned in KB.
	//
{
	int totalSize = 0;

	//	total up grid cell contents
	//
	int numVoxels = fNumVoxels[0]*fNumVoxels[1]*fNumVoxels[2];
	for( int v = 0; v < numVoxels; v++ )
	{
		if( fVoxels[v] != NULL )
		{
			totalSize += fVoxels[v]->length()*sizeof(unsigned int);
		}
	}

	//	also add space required for linear array of voxels
	//
	totalSize += fVoxels.size()*sizeof(MUintArray*);

	return ((float)totalSize)/1024.0f;
}

SpatialGridWalker SpatialGrid::getRayIterator( 
	const MPoint& origin,
	const MVector& direction )
	//
	//	Description:
	//
	//		Returns an iterator that will walk through every voxel 
	//		intersected by the ray from 'origin' along direction
	//		'direction'.  The iterator starts off in a valid grid 
	//		cell on initialization.
	//
{
	return SpatialGridWalker( origin, direction, this );
}