/*
	Functions dealing with the voxels.
	Voxels are spacially adjacent, and together form the total 
	bounding volume of the scene.
	Important of the functions is create_vlist.
		Creates a list of voxels pierced by the ray along its path.
		The list is ordered with piercing order as the ordering.
		The routine has been developed in two phases.
		Phase I : A brute force algorithm (but correct) was developed.
			  -------------- 10 April 1991.
		Phase II : A 3d DDA being tested and subsequently abanodned.
			  -------------- 16 April 1991.
		Phase III : A 3d DDA Adapted from RayShade of Yale Univ.
			  -------------- 24 April 1991.
		As the codes for create_vlist and create_svlist are
		the adapted versions of the 3d-dda code used in Rayshade
		I am obliged to put the following copyright message.

		* Copyright (C) 1989, 1991, Craig E. Kolb
 		* All rights reserved.
 		*
 		* This software may be freely copied, modified, and
		* redistributed
 		* provided that this copyright notice is preserved on
		* all copies.
 		*
 		* You may not distribute this software, in whole or in 
		* part, as part of
 		* any commercial product without the express consent of
		* the original authours i.e. Craig E. Kolb.

	NOTE
	----
	The bruteforce method and the working 3dDDA method give slightly
	different output for the cases where the ray pieces exactly a voxel
	corner or edge without actually entering the voxel. So they donot
	create any problem.
------
sumant
*/
#include <stdio.h>
#include <math.h>
#include <malloc.h>

#include "GraphicsGems.h"
#include "data_structure.h"
#include "vox.h"
#include "raddecl.h"

Vlist *create_vlist(ray_start,ray_direction,tmin,tmax)
/*
	Creates the list of voxels along the ray using 3dDDA.

	IMPORTANT
	--------
	'create_svlist' is a duplicate of this routine with slight
	modification. So any change to this routine must be propagated to 
	'create_svlist'.
--------
sumant 24-April-91
*/
Point3 *ray_start;
Vector3 *ray_direction;
double tmin,tmax;
{
	Vlist *vlist=NULL;
	int x,stepX,outX;
	double tMaxX,tDeltaX;
	int y,stepY,outY;
	double tMaxY,tDeltaY;
	int z,stepZ,outZ;
	double tMaxZ,tDeltaZ;

	double t1;

	Point3 ray_entry,ray_exit;

	point_on_line(*ray_start,*ray_direction,tmin,ray_entry);
	point_on_line(*ray_start,*ray_direction,tmax,ray_exit);

	x=x2voxel(volume_grid,ray_entry.x); if (x == volume_grid.x_subdivision) x--;
	if (ray_direction->x < 0.){
		tMaxX = tmin + (voxel2x(volume_grid,x)-ray_entry.x)/ray_direction->x;
		tDeltaX =  volume_grid.voxel_size.x/(-ray_direction->x);
		stepX = outX = -1;
	}
	else if (ray_direction->x > 0.){
		tMaxX = tmin + (voxel2x(volume_grid,x+1)-ray_entry.x)/ray_direction->x;
		tDeltaX =  volume_grid.voxel_size.x/ray_direction->x;
		stepX = 1;
		outX = volume_grid.x_subdivision;
	}
	else{
		tMaxX=LARGE;
		tDeltaX = 0.;
	}

	y=y2voxel(volume_grid,ray_entry.y); if (y == volume_grid.y_subdivision) y--;
	if (ray_direction->y < 0.){
		tMaxY = tmin + (voxel2y(volume_grid,y)-ray_entry.y)/ray_direction->y;
		tDeltaY =  volume_grid.voxel_size.y/(-ray_direction->y);
		stepY = outY = -1;
	}
	else if (ray_direction->y > 0.){
		tMaxY = tmin + (voxel2y(volume_grid,y+1)-ray_entry.y)/ray_direction->y;
		tDeltaY =  volume_grid.voxel_size.y/ray_direction->y;
		stepY = 1;
		outY = volume_grid.y_subdivision;
	}
	else{
		tMaxY=LARGE;
		tDeltaY = 0.;
	}

	z=z2voxel(volume_grid,ray_entry.z); if (z == volume_grid.z_subdivision) z--;
	if (ray_direction->z < 0.){
		tMaxZ = tmin + (voxel2z(volume_grid,z)-ray_entry.z)/ray_direction->z;
		tDeltaZ =  volume_grid.voxel_size.z/(-ray_direction->z);
		stepZ = outZ = -1;
	}
	else if (ray_direction->z > 0.){
		tMaxZ = tmin + (voxel2z(volume_grid,z+1)-ray_entry.z)/ray_direction->z;
		tDeltaZ =  volume_grid.voxel_size.z/ray_direction->z;
		stepZ = 1;
		outZ = volume_grid.z_subdivision;
	}
	else{
		tMaxZ=LARGE;
		tDeltaZ = 0.;
	}
	t1 = tmin;
	while(1){
		int index=voxel_index(volume_grid,x,y,z);
/*
		Voxel *vox=volume_grid.voxels+index;
		HitBoundingBox(&(vox->extent.min),&(vox->extent.max),
			ray_start,ray_direction,&t1,&t2);
		add_to_list(&vlist,index,t1,t2);
*/

		if ((tMaxX < tMaxY) && (tMaxX < tMaxZ)) {
			add_to_list(&vlist,index,t1,tMaxX); t1 = tMaxX;
			x += stepX;
			if ((tmax < tMaxX) || (x == outX)) break;
                        tMaxX += tDeltaX;
		}else if (tMaxZ < tMaxY) {
			add_to_list(&vlist,index,t1,tMaxZ); t1 = tMaxZ;
			z += stepZ;
                        if ((tmax < tMaxZ) || (z == outZ))
                                break;
                        tMaxZ += tDeltaZ;
                } else {
			add_to_list(&vlist,index,t1,tMaxY); t1 = tMaxY;
                        y += stepY;
                        if ((tmax < tMaxY) || (y == outY))
                                break;
                        tMaxY += tDeltaY;
                }
	}
	return(vlist);
}
	
int add_to_list(vlist,voxnum,t1,t2)
Vlist **vlist;
int voxnum;
double t1,t2;
{
	Vlist *newvox;
	static Vlist *p;
	newvox=(Vlist *)malloc (sizeof(Vlist));
	if (newvox==NULL) error("In Newbox");
	newvox->voxnum=voxnum;
	newvox->t_near=t1;
	newvox->t_far=t2;
	newvox->next=NULL;

	if (*vlist==NULL) *vlist = p = newvox;
	else { p->next = newvox; p = newvox; }
}

int purge_vlist(vlist)
Vlist *vlist;
{
	while(vlist != NULL){
		Vlist *tlist=vlist;
		vlist=vlist->next;
		free((char *)tlist);
	}
}