/*------------------------------------------------------------------------+
| Spring NASA R&D Ray Tracing Project; Part 1                             |
| Divide world space into cubes (or seads).  For each object modeled,     |
| determine which seads it will intersect with.  Build a list of the      |
| intersecting objects off of each sead.                                  |
+------------------------------------------------------------------------*/
#include <stdio.h>
#include <math.h>
#include "rtd.h"
#include "extern.h"
#include "macros.h"

int debug=FALSE;
void init_global()
/*------------------------------------------------------------------------+
| Set global world space parameters.                                      |
+------------------------------------------------------------------------*/
  {
  x_world_start = 0.0;
  x_world_end   = 1200.0;
  y_world_start = 0.0;
  y_world_end   = 1200.0;
  z_world_start = 0.0;
  z_world_end   = 1200.0;
  }


void init_seads(min_x, max_x, min_y, max_y, min_z, max_z)
/*------------------------------------------------------------------------+
| Initialize sead area so each sead points to nothing.  Also determine    |
| the number of points in each sead sead (i.e. how many units in total     |
| world space each sead takes.).  Now determine the radius of a bounding  |
| sphere on each sead.                                                    |
+------------------------------------------------------------------------*/
  float  min_x, max_x, min_y, max_y, min_z, max_z;
  {
  int  x, y, z;
  float  temp, x1, y1, z1;

  for (x = 0; x <= NUM_SEADS; x++)
    for (y = 0; y <= NUM_SEADS; y++)
      for (z = 0; z <= NUM_SEADS; z++)
          seads[x][y][z] = NULL;

  num_pts_per_sead = max_x - min_x;         /* find maximum number of points */
  temp = max_y - min_y;                    /* in world                      */

  if (temp > num_pts_per_sead)
    num_pts_per_sead = temp;

  temp = max_z - min_z;

  if (temp > num_pts_per_sead)
    num_pts_per_sead = temp;

  num_pts_per_sead = num_pts_per_sead / NUM_SEADS;  /* make a square bounding */
  half_side = num_pts_per_sead / 2;                /* sead and find middle    */

  x1 = min_x + half_side;
  y1 = min_y + half_side;
  z1 = min_z + half_side;

  sead_radius = sqrt((x1 - min_x) * (x1 - min_x) +  /* find radius of seads */
                    (y1 - min_y) * (y1 - min_y) +  /* this is a bounding   */ 
                    (z1 - min_z) * (z1 - min_z));  /* sphere */
/*
  printf("NUM_SEADS = %d num_pts_per_sead = %4.1f sead_radius = %4.1f\n",
    NUM_SEADS, num_pts_per_sead, sead_radius);
*/
  } /* init_seads */

void print_seads()

{
  int x, y, z, i;
  struct obj_link *temp; 
  FILE *fs;

  fs = fopen("print_seads.out", "w");

  for (x = 0; x <= NUM_SEADS; x++)
    for (y = 0; y <= NUM_SEADS; y++)
      for (z = 0; z <= NUM_SEADS; z++)
        {
         temp = seads[x][y][z];
         while (temp != NULL)
           {
           fprintf(fs, "x= %3d y= %3d z= %3d\n", x, y, z);
           if (temp->the_object->type == SPHERE_TYPE)
             {
             fprintf(fs, "spx= %7.1f ", temp->the_object->object.sphere.cent.x);
             fprintf(fs, "spy= %7.1f ", temp->the_object->object.sphere.cent.y);
             fprintf(fs, "spz= %7.1f\n", temp->the_object->object.sphere.cent.z);
             }
           else
             if (temp->the_object->type == FACET_TYPE)
               {
               for (i = 0; i < 3; i++)
                 {
                 fprintf(fs, " pt[%d].x= %7.3f ", i,
                    temp->the_object->object.facet.point[i].x);
                 fprintf(fs, "pt[%d].y= %7.3f ", i,
                    temp->the_object->object.facet.point[i].y);
                 fprintf(fs, "pt[%d].z= %7.3f \n", i,
                    temp->the_object->object.facet.point[i].z);
                 } /* end of for */
               } /* end of if FACET_TYPE */
           temp = temp->next_obj;
           }
        }
   fclose(fs);
} 

int sphere_intersect(sx, sy, sz, sr, x, y, z)
/*------------------------------------------------------------------------+
| Given the center coordinates of a bounding sphere on an object and an   |
| index in three space for a sead, see if the two intersect.  If a sead is |
| totally enclosed in a sphere, throw it away. If the centers of the      |
| bounding sphere of an object and the bounding sphere of a sead are      |
| are further apart then their radius' then the two cannot intersect.     |
| NOTE: all objects in part 1 are given as spheres. Can be used with a    |
| bounding sphere of any object.                                          |
+------------------------------------------------------------------------*/
  float  sx, sy, sz, sr;
  int  x, y, z;
  {
  int  sph_intersect;
  float  wx, wy, wz, midx, midy, midz, dist;

  wx = x * num_pts_per_sead + x_world_start;   /* find world coordinates  */
  wy = y * num_pts_per_sead + y_world_start;   /* of sead                 */
  wz = z * num_pts_per_sead + z_world_start;

  midx = wx + half_side;                      /* find mid-point of sead  */
  midy = wy + half_side;
  midz = wz + half_side;

  dist = sqrt((midx - sx) * (midx - sx) +    /* find distance between    */
              (midy - sy) * (midy - sy) +    /* object center and sead   */
              (midz - sz) * (midz - sz));    /* center                   */

  if   (dist > sead_radius + sr)              /* find if the two objects  */
       sph_intersect = FALSE;                /* intersect                */
  else if   (dist + sead_radius < sr)
            sph_intersect = FALSE;
       else sph_intersect = TRUE;

  return(sph_intersect);
  } /* of sphere_intersect */


void free_seads_list()
/*------------------------------------------------------------------------+
| Free all dynamically allocated memory.                                  |
+------------------------------------------------------------------------*/
  {
  int  i, j, k;
  struct obj_link *temp, *temp2;

  for (i = 0; i <= NUM_SEADS; i++)
    for (j = 0; j <= NUM_SEADS; j++)
      for (k = 0; k <= NUM_SEADS; k++)
        {
        temp = seads[i][j][k];
        seads[i][j][k] = NULL;
        
        while (temp != NULL)
          {
          temp2 = temp->next_obj;
          free((char *)temp);
          temp = temp2;
          }
        }
  } /* free_seads_list */


void make_seads(data)
struct object_data *data;

/*------------------------------------------------------------------------+
| Read file object.dat containing object descriptions.  For               |
| each object, determine the maximum possible seads they CAN intersect    |
| with in x,y,z (three) space.  For this selected subset of seads, see    |
| if each one actually DOES intersect with the object.  If so, add        |
| the object description to the link lists of objects coming off of the   |
| current sead.  These are added at the front of the list from each sead. |
+------------------------------------------------------------------------*/
  {
  float  cen_x, cen_y, cen_z, num_sead_int;        
  int  i, x, y, z, intersect;
  struct obj_link *temp_link, *temp_link2;
  struct an_object  *new_object;
  double A, A1, A2, A3, B, B1, B2, B3, C, D, dist, minx, maxx, miny, maxy,
    minz, maxz, hold;
  float  wx, wy, wz, midx, midy, midz;
  

  if (data->type == SPHERE_TYPE)
    {
/*
printf("TYPE= %c RAD= %5.1f x= %5.1f  y= %5.1f   z= %5.1f\n",
     data->type, data->object.sphere.rad, 
     data->object.sphere.cent.x,
     data->object.sphere.cent.y,
     data->object.sphere.cent.z);
*/

    sp_r = data->object.sphere.rad;
    sp_x = data->object.sphere.cent.x;
    sp_y = data->object.sphere.cent.y;
    sp_z = data->object.sphere.cent.z;
    cen_x = sp_x / num_pts_per_sead;           /* find seads center of */
    cen_y = sp_y / num_pts_per_sead;           /* sphere is in.        */
    cen_z = sp_z / num_pts_per_sead;

    num_sead_int = sp_r / num_pts_per_sead;     /* find the number of  */
                                              /* seades sphere spans  */
    min_x_sead = floor((cen_x - num_sead_int)-ROUNDOFF);   /* calculate min and   */
    max_x_sead = floor((cen_x + num_sead_int) + ROUNDOFF);   /* max x, y, and z     */
    min_y_sead = floor((cen_y - num_sead_int) - ROUNDOFF);   /* seads to search     */
    max_y_sead = floor((cen_y + num_sead_int) + ROUNDOFF);   /* for a possible      */
    min_z_sead = floor((cen_z - num_sead_int) - ROUNDOFF);   /* intersection        */
    max_z_sead = floor((cen_z + num_sead_int) + ROUNDOFF);
    if (min_x_sead < MIN_SEAD)
      min_x_sead = MIN_SEAD;
    if (min_y_sead < MIN_SEAD)
      min_y_sead = MIN_SEAD;
    if (min_z_sead < MIN_SEAD)
      min_z_sead = MIN_SEAD;
    if (max_x_sead > MAX_SEAD)
      max_x_sead = MAX_SEAD;
    if (max_y_sead > MAX_SEAD)
      max_y_sead = MAX_SEAD;
    if (max_z_sead > MAX_SEAD)
      max_z_sead = MAX_SEAD;
 
    if (debug)
      {printf("\nN_pts_sead=%f ,MAX SEADS x %d,%d y %d,%d, z %d,%d\n",
                  num_pts_per_sead, min_x_sead, max_x_sead,min_y_sead
            ,max_y_sead, min_z_sead, max_z_sead);
        printf("\nsp_x = %5.1f sp_y = %5.1f sp_z = %5.1f sp_r = %5.1f\n", sp_x,
            sp_y, sp_z, sp_r);
       }


    for (x = min_x_sead; x <= max_x_sead; x++)
      for (y = min_y_sead; y <= max_y_sead; y++)
        for (z = min_z_sead; z <= max_z_sead; z++)
          {                                    /* check if sphere intersects */
          intersect = sphere_intersect(sp_x, sp_y, sp_z, sp_r, x, y, z);
          if (intersect)
            {
            if ((temp_link = (struct obj_link *) malloc(sizeof(struct obj_link))) == NULL)
                   { printf("\nERROR no memory to malloc for temp_link");
                   exit(1);}
            temp_link->the_object = data;                      /* link object */
            temp_link->next_obj = seads[x][y][z];
            seads[x][y][z] = temp_link;            /* link sead   */
            } /* of intersect */
          } /* of for x, y, z */
    } /* data_type == SPHERE_TYPE */
  else
    {
    if (data->type == FACET_TYPE)
      { /* equation of a plane */
      A1 = FACET_MINUS(x, 2, 0);
      A2 = FACET_MINUS(y, 2, 0);
      A3 = FACET_MINUS(z, 2, 0);
      B1 = FACET_MINUS(x, 1, 0);
      B2 = FACET_MINUS(y, 1, 0);
      B3 = FACET_MINUS(z, 1, 0);
      A = A2 * B3 - A3 * B2;
      B = A3 * B1 - A1 * B3;
      C = A1 * B2 - A2 * B1;
      D = -(A * FACET_COMP(x, 0) + B * FACET_COMP(y, 0) + C * FACET_COMP(z, 0));

/*
      printf("A1 = %4.1f  A2 = %4.1f  A3 = %4.1f\n", A1, A2, A3);
      printf("B1 = %4.1f  B2 = %4.1f  B3 = %4.1f\n", B1, B2, B3);
      printf("A= %4.1f  B= %4.1f C= %4.1f  D= %4.1f\n", A, B, C, D);
*/

      minx = FACET_COMP(x, 0); maxx = FACET_COMP(x, 0);
      miny = FACET_COMP(y, 0); maxy = FACET_COMP(y, 0);
      minz = FACET_COMP(z, 0); maxz = FACET_COMP(z, 0);

      hold = FACET_COMP(x, 1);
      if (hold < minx)
        minx = hold;
      if (hold > maxx)
        maxx = hold;
      hold = FACET_COMP(y, 1);
      if (hold < miny)
        miny = hold;
      if (hold > maxy)
        maxy = hold;
      hold = FACET_COMP(z, 1);
      if (hold < minz)
        minz = hold;
      if (hold > maxz)
        maxz = hold;

      hold = FACET_COMP(x, 2);
      if (hold < minx)
        minx = hold;
      if (hold > maxx)
        maxx = hold;
      hold = FACET_COMP(y, 2);
      if (hold < miny)
        miny = hold;
      if (hold > maxy)
        maxy = hold;
      hold = FACET_COMP(z, 2);
      if (hold < minz)
        minz = hold;
      if (hold > maxz)
        maxz = hold;

/*
      printf("minx = %4.1f  miny = %4.1f minz = %4.1f\n",
        minx, miny, minz);
*/

      min_x_sead = floor((minx / num_pts_per_sead) - ROUNDOFF);
      max_x_sead = floor((maxx / num_pts_per_sead) + ROUNDOFF);
      min_y_sead = floor((miny / num_pts_per_sead) - ROUNDOFF);
      max_y_sead = floor((maxy / num_pts_per_sead) + ROUNDOFF);
      min_z_sead = floor((minz / num_pts_per_sead) - ROUNDOFF);
      max_z_sead = floor((maxz / num_pts_per_sead) + ROUNDOFF);

      if (min_x_sead < MIN_SEAD)
        min_x_sead = MIN_SEAD;
      if (min_y_sead < MIN_SEAD)
        min_y_sead = MIN_SEAD;
      if (min_z_sead < MIN_SEAD)
        min_z_sead = MIN_SEAD;
      if (max_x_sead > MAX_SEAD)
        max_x_sead = MAX_SEAD;
      if (max_y_sead > MAX_SEAD)
        max_y_sead = MAX_SEAD;
      if (max_z_sead > MAX_SEAD)
        max_z_sead = MAX_SEAD;
 
/*
      printf("min SEADS x = %d  y = %d  z = %d\n", 
             min_x_sead, min_y_sead, min_z_sead);
      printf("max SEADS x = %d  y = %d  z = %d\n", 
             max_x_sead, max_y_sead, max_z_sead);
*/
      for (x = min_x_sead; x <= max_x_sead; x++)
        {
        wx = x * num_pts_per_sead + x_world_start; /* find world coordinates  */
        midx = wx + half_side;                  /* find mid-point of sead  */
/*
        printf("wx = %7.1f  midx = %7.1f\n", wx, midx);
*/
        for (y = min_y_sead; y <= max_y_sead; y++)
          {
          wy = y * num_pts_per_sead + y_world_start;   /* of sead  */
          midy = wy + half_side;
/*
          printf("wy = %7.1f  midy = %7.1f\n", wy, midy);
*/
         
          for (z = min_z_sead; z <= max_z_sead; z++)
            {
            wz = z * num_pts_per_sead + z_world_start;
            midz = wz + half_side;
          
            dist = fabs(A * midx + B * midy + C * midz + D) /
                     sqrt(A * A + B * B + C * C);

/*
            printf("wz = %7.1f  midz = %7.1f  dist= %8.2f\n", wz, midz, dist);
*/
            if (dist <= sead_radius)
              {
/*
              printf(" Intersecting SEAD x = %d y = %d z = %d\n", x, y, z);
*/
              if ((temp_link = (struct obj_link *) malloc(sizeof(struct obj_link))) == NULL)
                { 
                printf("\nERROR no memory to malloc for temp_link");
                exit(1);
                }
              temp_link->the_object = data;                    /* link object */
              temp_link->next_obj = seads[x][y][z];
              seads[x][y][z] = temp_link;            /* link sead   */

              }   /* of dist <= sead_radius */
            } /* of for z seads */
          }  /* end of for y seads */
        }  /* end of for x seads */
      } /* end of if FACET_TYPE */
    } /* end of else */

  } /* make_seads */