#include <stdio.h>
#include <math.h>
#include <malloc.h>

#include "GraphicsGems.h"
#include "data_structure.h"
#include "objects.h"
extern int verbose_flag;
#define adjust_limits(o) {\
		xlo=x2voxel(volume_grid,(o).bbox.min.x);\
		ylo=y2voxel(volume_grid,(o).bbox.min.y);\
		zlo=z2voxel(volume_grid,(o).bbox.min.z);\
		xhi=x2voxel(volume_grid,(o).bbox.max.x);\
		yhi=y2voxel(volume_grid,(o).bbox.max.y);\
		zhi=z2voxel(volume_grid,(o).bbox.max.z);\
		\
		if (xlo >= volume_grid.x_subdivision) \
			xlo = volume_grid.x_subdivision-1;\
		if (ylo >= volume_grid.y_subdivision) \
			ylo = volume_grid.y_subdivision-1;\
		if (zlo >= volume_grid.z_subdivision) \
			zlo = volume_grid.z_subdivision-1;\
		if (xhi >= volume_grid.x_subdivision) \
			xhi = volume_grid.x_subdivision-1;\
		if (yhi >= volume_grid.y_subdivision) \
			yhi = volume_grid.y_subdivision-1;\
		if (zhi >= volume_grid.z_subdivision) \
			zhi = volume_grid.z_subdivision-1;\
}
static void spacially_sub_divide()
/* Compute the object list for each voxel. */
{
	int i;

	if (volume_grid.voxels==NULL)error("Null Voxel List.");

	for(i=0; i < number_objects; i++){
		int x,y,z,xlo,ylo,zlo,xhi,yhi,zhi;
		adjust_limits(object[i]);
		for (x = xlo; x <= xhi; x++)
		   for (y = ylo; y <= yhi; y++)
		      for (z = zlo; z <= zhi; z++){
		         Voxel *v=voxel_addr(volume_grid,x,y,z);
		         if (v->nobjects==0)
		            if ((v->intersecting_object_list=
		             (int *)malloc(sizeof(int)*number_objects))
						==NULL) error(
				"Cannot allocate Voxel object list");
		         v->intersecting_object_list[v->nobjects]=i;
		         (v->nobjects)++;
		      }
	}

#if defined(DEBUG)
	/* Check whether the object voxel classification is correct. */
	/* 
	   Step I :
		Check if the Bbox of the objects in the voxel list
		really intersects the Voxel extent.
	*/
	{
	int bounds_overlap();
	Voxel *vox=volume_grid.voxels;
	Box3 b1;
	int i,j,k,n,m;
        for (i=0,b1.min.x=volume_grid.extent.min.x;
        i < volume_grid.x_subdivision; i++, b1.min.x+=volume_grid.voxel_size.x)
        for (j=0, b1.min.y = volume_grid.extent.min.y;
        j<volume_grid.y_subdivision;j++,b1.min.y+=volume_grid.voxel_size.y)
        for (k=0, b1.min.z= volume_grid.extent.min.z;
        k<volume_grid.z_subdivision; k++,b1.min.z+=volume_grid.voxel_size.z,vox++){
		V3Add(&(b1.min),&(volume_grid.voxel_size),&(b1.max));
		for(n=0; n < vox->nobjects; n++)
		if (bounds_overlap(&b1,&(object[vox->intersecting_object_list[n]].bbox))==0)
			fprintf(stderr, "Step I Mismatch in Voxel[%d][%d][%d]\n", i,j,k);
	}
	/*
	   Step II :
		Check for each object Bbox intersection with each Voxel.
		For a valid intersection check if the Object belongs to
		the Voxel list. If it does not NOTIFY.
	*/
	for (n=0; n< number_objects;n++)
		for (i=0,b1.min.x=volume_grid.extent.min.x,vox=volume_grid.voxels;
		i < volume_grid.x_subdivision; i++,b1.min.x+=volume_grid.voxel_size.x)
                for (j=0, b1.min.y = volume_grid.extent.min.y;
                j<volume_grid.y_subdivision;j++,b1.min.y+=volume_grid.voxel_size.y)
                for (k=0, b1.min.z= volume_grid.extent.min.z;
                k<volume_grid.z_subdivision;k++,b1.min.z+=volume_grid.voxel_size.z,vox++){
			V3Add(&(b1.min),&(volume_grid.voxel_size),&(b1.max));
			/* Check if belongs to the current voxel */
			if (bounds_overlap(&b1,&(object[n].bbox))){
				int exists=0;
				/* Then check if it is in the list or has been missed out.*/
				for(m=0; m < vox->nobjects; m++)
					if (n == vox->intersecting_object_list[m]){
						exists=1;
						break;
					}
				if (!exists)
					fprintf(stderr,
				       "Step II Mismatch in object %d Voxel[%d][%d][%d].\n",
					n,i,j,k);
			}
		}
	}
#endif
}
#undef adjust_limits
preprocess()
/*
1. Initialising the grid data structure s.a.
		area of the grid element.

2. Parameterization and related work for all object surfaces.
	For Quadrilateral :
		1) Parameterize the quadrilateral from the given points.
		2) Compute Plane_Normal and Plane_Constant. 
		3) Compute a local co-ordinate system U,V,N and
			Compute a 4 x 4 Matrix for transformation to the
			local co-ordinate system.
		4) Compute the Constants for inverse Mapping of a point 
			on the quadrilateral to (u,v) parameter.
	For Sphere :
	For Other Objects :
		.
		.
		.
		.
3. Cover the whole scene with a bounding box with faces parallel to Major Planes.

4. Divide the Bounding Box into predefined number of voxels (XDiv * YDiv * ZDiv)
   and associate with each box a list of objects.

*/
{
	int i,j,k;
	Point3 min0;
	Voxel *vox;

	/* Initialise the Bounding Box */
	volume_grid.extent.min.x=
		volume_grid.extent.min.y=
			volume_grid.extent.min.z= LARGE;
	volume_grid.extent.max.x=
		volume_grid.extent.max.y=
			volume_grid.extent.max.z= -LARGE;
	for (i=0; i < number_objects; i++){
		ofunc[object[i].surface_geometry_type].object_specific_preprocess(
			object[i].grid,
			object[i].grid_h_reso,object[i].grid_v_reso,
			object[i].object_specific_structure,
			&(object[i].bbox),
			&(volume_grid.extent)
		);
		object[i].mail_box.ray_num= UNDEFINED;
	}
	/*
		Now a tight scene volume bound is ready.
		Loosen the volume extents a bit, to allow for the arithmatic errors.
	*/
	
	volume_grid.extent.min.x-=EPSILON;volume_grid.extent.max.x+=EPSILON;
	volume_grid.extent.min.y-=EPSILON;volume_grid.extent.max.y+=EPSILON;
	volume_grid.extent.min.z-=EPSILON;volume_grid.extent.max.z+=EPSILON;
	

	volume_grid.voxel_size.x=(volume_grid.extent.max.x-volume_grid.extent.min.x)/
			volume_grid.x_subdivision;
	volume_grid.voxel_size.y=(volume_grid.extent.max.y-volume_grid.extent.min.y)/
			volume_grid.y_subdivision;
	volume_grid.voxel_size.z=(volume_grid.extent.max.z-volume_grid.extent.min.z)/
			volume_grid.z_subdivision;
	volume_grid.voxel_density.x=1.0/volume_grid.voxel_size.x;
	volume_grid.voxel_density.y=1.0/volume_grid.voxel_size.y;
	volume_grid.voxel_density.z=1.0/volume_grid.voxel_size.z;

	min0=volume_grid.extent.min;
	for(i=0,vox=volume_grid.voxels;i<volume_grid.x_subdivision;
		i++,min0.x+=volume_grid.voxel_size.x){
		Point3 min1;
		min1=min0;
		for(j=0;j<volume_grid.y_subdivision;
			j++,min1.y+=volume_grid.voxel_size.y){
			Point3 min2;min2=min1;
			for(k=0;k<volume_grid.z_subdivision;
				k++,vox++,min2.z+=volume_grid.voxel_size.z){
				vox->extent.min=min2;
				V3Add(&(vox->extent.min),
					&(volume_grid.voxel_size),
					&(vox->extent.max));
			}
		}
	}

	spacially_sub_divide();
#if defined (DEBUG)
	{
	int j,n=volume_grid.x_subdivision*volume_grid.y_subdivision*volume_grid.z_subdivision;
	char *counter=(char *)malloc(number_objects);
	if (counter==NULL) error("Cannot allocate counter.");
	if(verbose_flag) fprintf(stderr,"Scene Bounding Box extents are <%g,%g,%g> to <%g,%g,%g>.\n",
	      volume_grid.extent.min.x,volume_grid.extent.min.y,volume_grid.extent.min.z,
	      volume_grid.extent.max.x,volume_grid.extent.max.y,volume_grid.extent.max.z);
	
	for(i=0; i<n;i++)
		for(j=0;j<volume_grid.voxels[i].nobjects;j++)
			counter[volume_grid.voxels[i].intersecting_object_list[j]]=1;
	if(verbose_flag) fprintf(stderr,"Objects Not accounted for in Voxel list are : <");
	for (i=0;i<number_objects;i++)
		if(counter[i]==0) fprintf(stderr,"%d ",i);
	if(verbose_flag) fprintf(stderr,">\n");
	}
#endif
}