/* Surface
 * (C) Copyright 1995 by Ashton Mason (amason@cs.uct.ac.za)
 *
 * Permission to use, modify, copy and distribute this source code for
 * any purpose and without fee is granted, provided that this copyright
 * notice appears in all copies and supporting documentation, and that
 * credit is given where due. This source code is provided "as is" with
 * no express or implied warranty.
 */

#include "headers.h"


bresgrid bres;				// bresenham grid walker



	// calculates the intersection of a plane and a line
        // line is defined as the line through the eye point
	// with direction vector ed.
	// plane is defined as the plane passing through point
        // p, with normal vector n. ep = p - eye
        // crucial routine for speed


inline int linePlane(vector &ed, vector &ep, float &normalx, float &normaly,
		     vector &inter)
{
  float t;

  float denom = ed.x * normalx + ed.y * normaly + ed.z;

  if (!ZEROISH(denom))
  {
    t = (ep.x * normalx + ep.y * normaly + ep.z) / denom;

	// correct side of viewplane?

    if (t > 1.0)
    {
      inter.x = eye.x + t * ed.x;
      inter.y = eye.y + t * ed.y;
      inter.z = eye.z + t * ed.z;

      return 1;
    }
  }

  return 0;
}


	// traverses the grid squares crossed by the pixel ray.
        // checks each for intersection.
        // returns intersection point and surface normal.


int traverseGrid(float &x1, float &y1, float &x2, float &y2, vector &pix,
		 vector &inter, vector &normal)
{
  int gridx, gridy;
  int xplus, yplus;

  float az, bz, uz, lz;			// heights of square corners
  float nux, nuy, nlx, nly;		// normals of triangles

  vector ed, ep;			// for intersection calculations

  vector ilower, iupper;		// triangle intersections
  int upper, lower;			// flags

	// calculate ed = d - eye

  ed = pix - eye;

	// mark out the start and end grid points

  bres.setCoords(x1, y1, x2, y2);

	// for each square, in order of increasing distance

  while (bres.getNext(&gridx, &gridy))
  {

	// check for grid edges

    xplus = gridx + (gridx < field.clipsize);
    yplus = gridy + (gridy < field.clipsize);

    az = field.getHeight(gridx, gridy);
    bz = field.getHeight(xplus, yplus);
    uz = field.getHeight(gridx, yplus);
    lz = field.getHeight(xplus, gridy);

	// calculate triangle normals
	// simple because triangle sides = 1

    nux = uz - bz;
    nuy = az - uz;
    nlx = az - lz;
    nly = lz - bz;

	// calculate ep = p - eye for this square

    ep.x = gridx - eye.x;
    ep.y = gridy - eye.y;
    ep.z = az - eye.z;

	// find plane inter for upper triangle

    upper = 0;
    if (linePlane(ed, ep, nux, nuy, iupper))
    {

	// check that in correct square and triangle
	// can't use a cast because of range of ints

      float dx = iupper.x - gridx;
      float dy = iupper.y - gridy;

      if (dx >= 0.0 && dx <= 1.0 && dy >= 0.0 && dy <= 1.0 && dy >= dx)
      {
	upper = 1;
      }
    }

	// find plane inter for lower triangle

    lower = 0;
    if (linePlane(ed, ep, nlx, nly, ilower))
    {

    	// check that in correct square and triangle

      float dx = ilower.x - gridx;
      float dy = ilower.y - gridy;

      if (dx >= 0.0 && dx <= 1.0 && dy >= 0.0 && dy <= 1.0 && dx >= dy)
      {
        lower = 1;
      }
    }

  	// find which triangle was intersected, if any

    switch ((upper << 1) + lower)
    {
      case 0:
        continue;

      case 1:
        inter = ilower;
        normal.set(nlx, nly, 1.0);
        return 1;

      case 2:
        inter = iupper;
        normal.set(nux, nuy, 1.0);
        return 1;

      	  // both triangles: take closest intersection
          // work out distances again here, since this is only done
	  // once for every pixel at most, whereas passing the
	  // distances back from linePlane would always be done for
	  // every triangle tested

      case 3:
        if ((iupper.x - eye.x) * (iupper.x - eye.x) +
            (iupper.y - eye.y) * (iupper.y - eye.y) <
	    (ilower.x - eye.x) * (ilower.x - eye.x) +
	    (ilower.y - eye.y) * (ilower.y - eye.y))
        {
          inter = iupper;
          normal.set(nux, nuy, 1.0);
        }
        else
        {
          inter = ilower;
	  normal.set(nlx, nly, 1.0);
	}
	return 1;
    }
  }

  return 0;
}


	// clips the line passing through p1 and p2 against the
	// grid boundaries. returns new intersections in correct
	// order, with p1 closer than p2


int clipGrid(float &x1, float &y1, float &x2, float &y2)
{
  const float dx = x2 - x1;
  const float dy = y2 - y1;

  int count = 0;
  float alphas[4];
  float clips[4][2] = {{0, 0}, {0, 0}, {0, 0}, {0, 0}};
  float alpha;
  float clip;

  if (!ZEROISH(dy))        	          	// valid horizontal lines?
  {
    alpha = - y1 / dy;          	        // find alpha
    clip = x1 + alpha * dx;   	        	// find clip value
    if (clip >= 0 && clip < field.clipsize) 	// check valid
    {
      clips[count][0] = clip;
      alphas[count++] = alpha;
    }

    alpha = (field.cliptest - y1) / dy;        	// find alpha
    clip = x1 + alpha * dx;               	// find clip value
    if (clip >= 0 && clip < field.clipsize)    	// check valid
    {
      clips[count][0] = clip;
      clips[count][1] = field.cliptest;
      alphas[count++] = alpha;
    }
  }

  if (!ZEROISH(dx))               		// valid vertical lines?
  {
    alpha = - x1 / dx;                  	// find alpha
    clip = y1 + alpha * dy;  			// find clip value
    if (clip >= 0 && clip < field.clipsize)   	// check valid
    {
      clips[count][1] = clip;
      alphas[count++] = alpha;
    }

    alpha = (field.cliptest - x1 ) / dx;       	// find alpha
    clip = y1 + alpha * dy;   			// find clip value
    if (clip >= 0 && clip < field.clipsize)    	// check valid
    {
      clips[count][0] = field.cliptest;
      clips[count][1] = clip;
      alphas[count++] = alpha;
    }
  }

  switch (count)
  {
    case 0 :                           		// no valid points

      return 0;

    case 2 :                            	// 2 or 4 valid points
    case 4 :

      if (alphas[1] > alphas[0])		// sort points
      {
        x1 = clips[0][0];
        y1 = clips[0][1];
        x2 = clips[1][0];
        y2 = clips[1][1];
      }
      else
      {
        x1 = clips[1][0];
        y1 = clips[1][1];
        x2 = clips[0][0];
        y2 = clips[0][1];
      }
      return 1;

    case 3 :                            	// 3 points

      if (alphas[0] < alphas[1])
      {
        if (alphas[0] < alphas[2])		// find nearest
        {
          x1 = clips[0][0];
          y1 = clips[0][1];
        }
        else
        {
          x1 = clips[2][0];
          y1 = clips[2][1];
        }

        if (alphas[1] < alphas[2])		// find furthest
        {
          x2 = clips[2][0];
          y2 = clips[2][1];
        }
        else
        {
          x2 = clips[1][0];
          y2 = clips[1][1];
        }
      }
      else
      {
        if (alphas[1] < alphas[2])		// find nearest
        {
          x1 = clips[1][0];
          y1 = clips[1][1];
        }
        else
        {
          x1 = clips[2][0];
          y1 = clips[2][1];
        }

        if (alphas[0] < alphas[2])		// find furthest
        {
          x2 = clips[2][0];
          y2 = clips[2][1];
        }
        else
        {
          x2 = clips[0][0];
          y2 = clips[0][1];
        }
      }
      return 1;

    default :
      error("invalid number of clip points - program error");
  }

  return 1;                  /* dummy return */
}


	// renders one pixel


int doPixel(int px, int py, vector &pix)
{
  vector inter, normal;

	// project pixel ray onto grid

  float x1 = eye.x;
  float y1 = eye.y;
  float x2 = pix.x;
  float y2 = pix.y;

	// clip against grid boundaries

  if (clipGrid(x1, y1, x2, y2))
  {
    if (traverseGrid(x1, y1, x2, y2, pix, inter, normal))
    {
      renderPixel(px, py, inter, normal);
      return 1;
    }
  }

  return 0;
}


	// renders the grid into the image buffer
	// traverses entire screen, one pixel at a time


int renderGrid()
{
  vector pix;
  int hits, misses;

	// set up viewer

  camera.initView();

	// use bresenham to draw bar graph

  const int hashes = imagex > HASHMARKS ? HASHMARKS : imagex;

	// print percentages

  printf("0%%");
  for (int n = hashes - 6; n; n--)
  {
    printf(" ");
  }
  printf("100%%\n");

  const int twodx = imagex * 2;
  const int twody = hashes * 2;
  int error = -imagex;

	// for all pixels in image

  camera.firstColumn(&pix);
  for (int px = 0; px < imagex; px++)
  {
    error += twody;			// e = e + dy/dx
    if (error >= 0)
    {
      printf("#");
      fflush(stdout);
      error -= twodx;			// e = e - 1
    }

    hits = misses = 0;

    for (int py = imagey - 1; py >= 0; py--)
    {
      if (doPixel(px, py, pix))
      {
        hits = 1;
        misses = 0;
      }
      else
      {
        misses++;
        if (hits && misses > 1) break;
      }
      camera.nextPixel(&pix);
    }

    camera.nextColumn(&pix);
  }
  printf("\n");

  return 1;
}