/*
** intx.c 
*/

#include <stdio.h>
#include <stdlib.h>
#include "peek.h"

/* slice_vert()
** does intersection of given vertex with ((piece->space_d)-1)-space.
** If vertex does lie in this space then will return a copy of this
** vertex, otherwise, a NULL pointer.
** Let k = piece->space_d - 1
** The k-space is where the piece->space_d coord is cut_x.
** This function really checks to see if -zero < vert->coord[k]-cut_x < zero,
** where is zero the float near 0 and > 0 to fudge
** coplanarity of things that probably aren't exactly coplanar.
** (so a correctly alligned intersetion of an dodecahedron with a plane
** does in fact result in a pentagon)
** If the vert did not lie in the k-space, then vert->spare is set:
** to -1 if vert->coord[k] - cut_x <= -zero
** to  1 if vert->coord[k] - cut_x >= zero
** for the benefit of the parent edge's intentions to know its intersection.
*/
int
slice_vert(Piece *piece, Part *vert, Piece *intxion_piece, 
	   float zero, float cut_x) {
  float
    x;           /* to hold current vert->coord[i] */
  struct part_t *
    intxion_vert = NULL;   /* new intersection vert, if there is one */
  char err2[ERRSTRLEN];
  int k;
  
  k = piece->space_d;
  vert->done = 1;
  x = vert->coord[k-1] - cut_x;
  if (-zero < x && x < zero) {
    if (build_part(&intxion_vert, 0, 0, 0, vert->color, vert->coord)) {
      sprintf(err2, "intx_vert: intxing vert/part #%d\n", vert->ID);
      strcat(err, err2); return(-1);
    }
    intxion_vert->coord[k-1] = 0;
    tag(intxion_piece, intxion_vert);
    vert->result = intxion_vert;
    vert->spare = 0;
  }
  else if (x <= -zero) {
    vert->result = NULL;
    vert->spare = -1;
  }
  else if (zero <= x) {
    vert->result = NULL;
    vert->spare = 1;
  }
  return 0;
}

/*
** slice_edge()
** k = piece->space_d - 1;
** The k-space is where the piece->space_d coord is cut_x.
** (k is not passed- to do arbitrary dimension cross-section slices use 
** intx_object iteratively)
** If there is an intersection, it may be one of the endpoints or a points 
** along the interior of the edge, or it may be the whole edge.  In these 
** cases the edge's result is set to point a new object which is the 
** intersection.
** If there is no intersection then the edge's result is set to NULL.
** Like intx_vert(), this is really checking to see if the edge lies in some
** proximity to the k-space, having been passed the fudge factor zero.
*/
int
slice_edge(Piece *piece, Part *edge, Piece *intxion_piece,
	   float zero, float cut_x) {

  Part
    *vert1,                 /* first vertex of edge */   
    *vert2,                 /* second vertex of edge */
    *intxion_vert = NULL,   /* intersection vertex, if there is any */
    *intxion_edge = NULL;   /* whole new intersection edge, if there is any */
  Image
    *vert_im = NULL;  /* vertex image pointer, for image list under 
			 intersection edge */
  float
    t1, t2, w1, w2;   /* for use in computing interior intersection 
			 of edge */
  int
    i, k;
  char err2[ERRSTRLEN];

  k = piece->space_d;
  edge->done = 1;
  vert1 = edge->thought->sense;
  vert2 = edge->thought->next->sense;
  if (!vert1->done)
    slice_vert(piece, vert1, intxion_piece, zero, cut_x);
  if (!vert2->done)
    slice_vert(piece, vert2, intxion_piece, zero, cut_x);
  switch (vert1->spare * vert2->spare) {
  case 1: {
    /* both vertices lie on one side of k-space => no intxion */
    edge->result = NULL;
    break;
  }
  case 0: {
    /* one or both of the vertices lie in k-space => intxion is either
       one of the verts or the whole edge */
    if (0 == vert1->spare && 0 == vert2->spare) {
      /* both vertices lie in k-space => intersection is simply a copy 
	 of this edge */
      if (build_part(&intxion_edge, 1, 0, 0, edge->color, edge->coord)) {
	sprintf(err2, "intx_edge: making copy of this edge/part #%d\n", 
		edge->ID); strcat(err, err2); return(-1);
      }
      edge->coord[k-1] = 0; /* probably not necessary or useful */
      tag(intxion_piece, intxion_edge);
      /* build image list under this edge for the previously generated 
	 kid verts */
      image_alloc(&vert_im);
      intxion_edge->thought = vert_im;
      vert_im->sense = vert1->result;
      image_alloc(&vert_im->next);
      vert_im = vert_im->next;
      vert_im->sense = vert2->result;
      vert_im->next = NULL;
      edge->result = intxion_edge;
      /* we don't really need to set spare because calling function will
	 see that we intersected in ourselves */
    }
    else if (0 == vert1->spare) {
      /* vert1 (but not vert2) lies in k-space => intersection is 
	 vert1's result */
      edge->result = vert1->result;
      edge->spare = 1;
    }
    else if (0 == vert2->spare) {
      /* vert2 (but not vert1) lies in k-space => intersection is 
	 vert2's result */
      edge->result = vert2->result;
      edge->spare = 1;
    }
    break;
  }
  case -1: {
    /* vertices lie on opposite sides of k-space => intxion is an 
       interior point */
    build_part(&intxion_vert, 0, 0, 0, edge->color, NULL);
    tag(intxion_piece, intxion_vert);
    t1 = vert1->coord[k - 1] - cut_x;
    t2 = vert2->coord[k - 1] - cut_x;
    w1 = t1/(t2 - t1); w1 = (w1 < 0 ? -w1 : w1);
    w2 = t2/(t2 - t1); w2 = (w2 < 0 ? -w2 : w2);
    for (i=0; i<=MAXSPACED; ++i) {
      intxion_vert->coord[i] = (i < k
				? w1*vert2->coord[i] + w2*vert1->coord[i] 
				: 0);
    }
    edge->result = intxion_vert;
    edge->spare = 0;
    break;
  }
  }
  return(0);
}

/*
** novel()
** returns a 1 if the given part is not below the given image list,
** 0 otherwise
*/
int
novel(Part *test, Image *image) {
  int new = 1;

  if (!image)
    return(1);

  do {
    if (test == image->sense) {
      new = 0;
    }
    image = image->next;
  } while (image);
  return(new);
}

/*
** slice_part()
** let k = piece->space_d -1
** The k-space is where the piece->space_d coord is cut_x.
** In the following the value of part->spare has the following meaning
** if part had an intersection:
** 0 : intersection intersects with the interior of the part
** 1 : intersection lies in boundary of part
*/
int
slice_part(Piece *piece, Part *part, Piece *intxion_piece, 
	   float zero, float cut_x) {
  Image 
    *kid_im = NULL,          /* pointer to image of part's kid */
    *intxion_kid_im = NULL,  /* pointer to image of intersection of part's 
				kid */
    *intxs_head = NULL;
  Part 
    *kid = NULL,             /* pointer to part's kid */
    *intxion_part = NULL,    /* pointer to part's intersection */
    *intxion_kid = NULL,     /* pointer to intersection of part's kid */
    *intxs_kid[MAXSPACED];
  int
    num_kids,              /* number of kids in this part */
    intxed,                /* true if any kid intxed */
    n,                     /* = part->d - 1 */
    i,                     /* innocent little all-purpose int */
    len,                   /* length of image list for kid's results */
    intxs_num[MAXSPACED];      /* intxs[i] = number of kids that reported
			      i dimensional results */
  char err2[ERRSTRLEN];

  part->done = 1;
  n = part->d - 1;
  kid_im = NULL;
  num_kids = 0;
  intxed = 0;
  bzero(intxs_num, MAXSPACED*sizeof(int));
  bzero(intxs_kid, MAXSPACED*sizeof(Part *));
  /* go through kid list and do all intxions, don't assemble intxion part 
     yet */
  do {
    ++num_kids;
    kid_im = (!kid_im ? part->thought : kid_im->next);
    kid = kid_im->sense;
    if (!kid->done) {
      if (1 < kid->d ) {
	if (slice_part(piece, kid, intxion_piece, zero, cut_x)) {
	  sprintf(err2, "trying to intx kid/part #%d of part #%d\n",
		  kid->ID, part->ID); strcat(err, err2); return(-1);
	}
      }
      else {
	if (slice_edge(piece, kid, intxion_piece, zero, cut_x)) {
	  sprintf(err2, "trying in intx edge/part #%d of part #%d\n",
		  kid->ID, part->ID); strcat(err, err2); return(-1);
	}
      }
    } /* if !kid->done */
    if (NULL != kid->result) {
      /* create/udpate the intxs_num[] and intxs_kid[] arrays */
      intxed = 1;
      ++(intxs_num[kid->result->d]);
      if (!intxs_kid[kid->result->d])
	intxs_kid[kid->result->d] = kid;
    }
  } while (NULL != kid_im->next);

  /* if there were any intxions then compute intxion part */
  if (intxed) {
    if (num_kids == intxs_num[n]) {
      /* every kid intersected in itself, result is a copy of this part */
      kid_im = NULL;
      intxion_kid_im = NULL;
      do {
	kid_im = (!kid_im ? part->thought : kid_im->next);
	kid = kid_im->sense;
	if (!intxion_kid_im) {
	  image_alloc(&intxion_kid_im);
	  build_part(&intxion_part, n+1, 0, 0, part->color, part->coord);
	  tag(intxion_piece, intxion_part);
	  part->result = intxion_part;
	  intxion_part->thought = intxion_kid_im;
	}
	else {
	  image_alloc(&intxion_kid_im->next);
	  intxion_kid_im = intxion_kid_im->next;
	}
	intxion_kid_im->sense = kid->result;
      } while (kid_im->next);
      intxion_kid_im->next = NULL;
      /* we don't really need to set spare- the calling part will
	 see that we intersected in ourselves and as such doesn't
	 refer to the boundary flag */
      return(0);
    }
    else if (1 == intxs_num[n]) {
      /* one kid intersected in itself, result is that kid's result */
      part->result = (intxs_kid[n])->result;
      part->spare = 1;
      return(0);
    }
    else if (intxs_num[n]) {
      /* detected non-coplanarity; stop */
      sprintf(err, "slice_part: deteced non-coplanarity in part %d\n",
	      part->ID); return(-1);
    }
    else {
      /* 0 == intxs_num[n] */
      if (intxs_num[n-1]) {
	/* gather unique (n-1)D results into image list, intx_head is
	   head of this image list */
	kid_im = NULL;
	intxion_kid_im = NULL;
	len = 0; /* len stores how kids have an (n-1)D result */
	do {
	  kid_im = (!kid_im ? part->thought : kid_im->next);
	  kid = kid_im->sense;
	  if (kid->result              /* kid did intersect */
	      && n-1 == kid->result->d /* its an (n-1)D intxion */
	      && (kid->spare = 0       /* its an interior intxion */
		                       /* its a new boundary intxion */
		  || novel(kid->result, intxs_head))) { 
	    /* this is a new part, add it to the image list */
	    if (!intxion_kid_im) {
	      image_alloc(&intxion_kid_im);
	      intxs_head = intxion_kid_im;
	    }
	    else {
	      image_alloc(&intxion_kid_im->next);
	      intxion_kid_im = intxion_kid_im->next;
	    }
	    intxion_kid_im->next = NULL;
	    intxion_kid_im->sense = kid->result;
	    ++len;
	  }
	} while (kid_im->next);
	if (len > n) {
	  /* the (n-1)D kid results together form an (n)D result */
	  build_part(&intxion_part, n, 0, 0, part->color, part->coord);
	  tag(intxion_piece, intxion_part);
	  part->result = intxion_part;
	  intxion_part->thought = intxs_head;
	  part->spare = 0;
	  return(0);
	}
	else if (1 == len) {
	  part->result = intxs_head->sense;
	  part->spare = 0;
	  return(0);
	}
	else {
	  /* number of (n-1)D kids <= n and > 1, so this is wacky */
	  sprintf(err, "slice_part: non-coplanarity in kids of part %d\n",
		  part->ID);
	  return(-1);
	}
      } /* if intxs_num[n-1] */
      else {
	/* result is on the boundary, and at the highest dimension
	   at which there is intersection then there is only one
	   true part to that intersection, so we can use the first
	   part of the many parts that reported that as their
	   intersection */
	for (i = n - 2; !intxs_num[i]; --i);
	part->result = (intxs_kid[i])->result;
	part->spare = 1;
	return(0);
      }
    }
  } /* if intxed */
  else
    part->result = NULL;
  return(0);
}

/*
** slice_piece()
** let k = piece->space_d - 1
** The k-space is where the piece->space_d coord is cut_x.
** indicates that there was an intersection by setting piece->result
** to point to (given) intxion_piece in case of intersection, or to
** NULL of there was no intersection.
*/
int
slice_piece(Piece *piece, Piece *intxion_piece, float zero, float cut_x) {
  Image 
    *surf_im,
    *intxion_surf_im;
  Part 
    *surf,
    *intxion_surf;
  int p = 1;

  surf_im = NULL;
  intxion_surf_im = NULL;
  do {
    surf_im = (!surf_im ? piece->thought : surf_im->next);
    surf = surf_im->sense;
    slice_part(piece, surf, intxion_piece, zero, cut_x);
    if (surf->result) {
      if (!intxion_surf_im) {
	/* start intxion surface list */
	/* intxion_piece has already been made, but we have to set piece_d 
	   in it now that we know the dimension of the intersection of the 
	   first surface, and we have to set result */
	piece->result = intxion_piece;
	intxion_piece->piece_d = surf->result->d;
	image_alloc(&intxion_surf_im);
	intxion_piece->thought = intxion_surf_im;
      }
      else {
	/* continue intxion surface list */
	image_alloc(&intxion_surf_im->next);
	intxion_surf_im = intxion_surf_im->next;
      }
      intxion_surf_im->sense = surf->result;
    }
    ++p;
  } while (NULL != surf_im->next);
  if (intxion_surf_im)
    intxion_surf_im->next = NULL;
  else
    piece->result = NULL;
  return(0);
}

/*
** slice_object()
** The k-space is where the piece->space_d coord is cut_x.
** intersects given object with k-space, sets *intxion_object to point it
** indicates that there was in intersection by setting the value of the
** passed pointer sliced_object.
** the k-space 
*/ 
int
slice_object(Piece *object, Piece **sliced_object, 
	     float zero, float cut_x) {
  Piece 
    *piece,
    *intxion_piece,
    *last_intxed;
  int p = 1;

  if (!object) {
    *sliced_object = NULL;
    return(0);
  }
  piece = NULL;
  intxion_piece = NULL;
  last_intxed = NULL;
  do {
    piece = (!piece ? object : piece->next);
    /* We have to build a piece so that if there is an intersection
       then we have a piece to catalog the parts in. If there is no
       intersection then this will be disposed of */
    build_piece(&intxion_piece, 0, piece->space_d - 1, piece->color, NULL);
    slice_piece(piece, intxion_piece, zero, cut_x);
    if (piece->result) {
      if (!last_intxed) {
	*sliced_object = intxion_piece;
      }
      else {
	last_intxed->next = intxion_piece;
      }
      last_intxed = intxion_piece;
    }
    else {
      dispose_piece(intxion_piece);
    }
    ++p;
  } while (piece->next);
  if (last_intxed)
    last_intxed->next = NULL;
  else
    *sliced_object = NULL;
  reset_object(object);
  return(0);
}

/*
** intx_object()
** intersects given object with R^k, where k is given.
** Does this by repeatedly calling slice_object and supplying
** a cut_x of 0 every time.
*/
int
intx_object(Piece *object, Piece **intxed_object, float zero, int k) {
  int steps, i, d;
  Piece 
    *interm = NULL,
    *slice_me;
  char err2[ERRSTRLEN];

  if (!object) {
    *intxed_object = NULL;
    return(0);
  }
  d = object->space_d;
  if (0 > k) {
    sprintf(err, "intx_object: k = %d is not valid\n", k);
    return(-1);
  }
  else if (k >= d) {
    /* this is wrong. *intx_object should end up pointing to an
       object independant of the given object.  Use duplicate_object() */
    *intxed_object = object;
    return(0);
  }
  else {
    steps = d - k;
    for (i=0; i<=steps-1; ++i) {
      slice_me = (!i ? object : interm);
      if (slice_object(slice_me, &interm, zero, 0)) {
	sprintf(err2, "intx_object: slice_object died on i=%d\n", i);
	strcat(err, err2); return(-1);
      }
      if (i) {
	dispose_object(slice_me);
      }
    }
    *intxed_object = interm;
  }
  /* reset_object() called in slice_object */
  return(0);
}