/*
 * Name:  
 * Class:  CS 4451
 * Asgn.:  Project #3
 * Due:    Friday March 29, 2002 11:59 PM
 *
 * e-mail: 
 *
*/

#define SHOW_TEXT 0

#include <stdio.h>
#include <math.h>
#include <GL/gl.h>
#include <glut.h>

#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <float.h>

#include "p3.h"
#include "matrixops.h"
#include "transform.h"
#include "dllist.h"
#include "image.h"
#include "color.h"

extern int x_pixels;
extern int y_pixels;
extern vector points[];
extern int nPoints;
extern Face initialFaces[];
extern int nInitialFaces;
extern Color3d colors[];
extern int nColors;
extern Material materials[];
extern Light myLight;

#define sqr(a) ((a)*(a))

/* Faces including the ones created because of the clipping */
Face *faces = NULL;
/* Number of faces */
int nFaces = 0;

/* Vertices */
Vertex *vertices = NULL;
/* Number of vertices */
int nVertices = 0;

/* Image to save into a *.ppm file */
Image image;

/* ---------------------------- Scan line --------------------------------- */
/* Background color */
Color3d bkg = {0.0, 0.0, 0.0};
/* Current scanline */
Color3d *scanLine = NULL;
/* Z-buffer for the current scanline */
double *zBufferLine = NULL;

/*
 * Allocates scanline and z-buffer data
 * Returns FALSE if allocation fails
*/
BOOLEAN allocScan() {
  if( scanLine ) {
    free(scanLine);
  }
  if( zBufferLine ) {
    free(zBufferLine);
  }
  if( (scanLine = (Color3d *)malloc(x_pixels*sizeof(Color3d))) == NULL ) {
    return FALSE;
  }
  if( (zBufferLine = (double *)malloc(x_pixels*sizeof(double))) == NULL ) {
    free(scanLine);
	printf("alloc zBuff\n");
    return FALSE;
  }
  return TRUE;
}

/*
 * Clears scanline with a background color and z-buffer
 * with a z-value specified
*/
void clearScan(Color3d bkg, double z) {
  int i;
  for( i = 0; i < x_pixels; i++ ) {
    scanLine[i] = bkg;
    zBufferLine[i] = z;
  }
}
/* ---------------------------- end scan line ----------------------------- */

/* ---------------------------- Triangle ---------------------------------- */
/*
 * Constructor for Triangle
*/
Triangle Triangle_construct(int vi0, int vi1, int vi2) {
  Triangle t;
  t.vis[0] = vi0;
  t.vis[1] = vi1;
  t.vis[2] = vi2;
  return t;
}

/*
 * Returns a pointer to the actual Vertex of the Triangle, given index i
 */
Vertex *Triangle_getVertex(Triangle *t, int i) {
  return &vertices[t->vis[i]];
};
/* ---------------------------- end Triangle ------------------------------ */

/* ------------------------------ Face ------------------------------------ */
/*
 * Returns Material of Face 
 */
Material *Face_getMaterial(Face *f) {
  return &materials[f->mi];
}

/*
 * Returns Triangle of Face 
*/
Triangle *Face_getTriangle(Face *f) {
  return &f->t;
}
/* ----------------------------- end Face --------------------------------- */

/* ------------------------------ faces ----------------------------------- */
/*
 * Allocates enough space for initial faces 
 * Returns FALSE if allocation fails
*/
BOOLEAN Faces_alloc() {
  if( faces ) {
    free(faces);
  }
  nFaces = nInitialFaces;
  if( (faces = (Face *)malloc(nFaces*sizeof(Face))) == NULL ) {
    nFaces = 0;
    return FALSE;
  }
  return TRUE;
}

/*
 * Assigns initialFaces to faces
*/
void Faces_construct() {
  int i;
  for( i = 0; i < nInitialFaces; i++ ) {
    faces[i] = initialFaces[i];
  }
}

/* compute the unit face normals for flat shading */
void Faces_compute_normals(){
	int i;
	for( i = 0; i < nFaces; i++ ) {
		Face *f = &faces[i];
		Triangle *t = Face_getTriangle(f);
		Vertex *p0 = Triangle_getVertex(t, 0);
		Vertex *p1 = Triangle_getVertex(t, 1);
		Vertex *p2 = Triangle_getVertex(t, 2);
		vector v1, v2;

		/* CODE: compute the _unit_ normal for this face and store it in the face (4 lines) */
	}
}

/* compute the face centers for flat shading */
void Faces_setCenter(){
	int i;
	for( i = 0; i < nFaces; i++ ) {
		Face *f = &faces[i];
		Triangle *t = Face_getTriangle(f);
		Vertex *p0 = Triangle_getVertex(t, 0);
		Vertex *p1 = Triangle_getVertex(t, 1);
		Vertex *p2 = Triangle_getVertex(t, 2);

		/* CODE: compute the center (average point) in the triangle (3 lines) */
	}
}

/* compute the face unit L vectors and distances, d, to the light source for flat shading */
void Faces_setL(){
	int i;
	for( i = 0; i < nFaces; i++ ) {
		Face *f = &faces[i];

		/* CODE: compute the _unit_ L vector and store the distance, d, to the light source (3 lines) */
	}
}

/* compute the face unit V vectors for flat shading */
void Faces_setV(){
	int i;
	vector eyepoint;
	/* CODE: set eyepoint (normalized coords) */

	for( i = 0; i < nFaces; i++ ) {
		Face *f = &faces[i];

		/* CODE: compute the _unit_ vector, V,  from the face center to the eyepoint (2 lines) */
	}
}

/* compute the face unit R vectors for flat shading */
void Faces_setR(){
	int i;
	double NL;
	for( i = 0; i < nFaces; i++ ) {
		Face *f = &faces[i];

		/* CODE: using N and L, calculate the _unit_ vector R (4 lines) */
	}
}

/* ----------------------------- end faces -------------------------------- */

/* ----------------------------- Material --------------------------------- */
/*
 * Get the Diffuse Color of the Material
*/
Color3d Material_getDiffColor3d(Material *m) {
  return colors[m->ci];
}
/*
 * Get the Specular Color of the Material
 */
Color3d Material_getSpecColor3d(Material *m) {
  return colors[m->sci];
}
/* ----------------------------- end Material ----------------------------- */

/* ------------------------------ Vertex ---------------------------------- */
/*
 * Construct Vertex from x, y, and z
*/
void Vertex_construct(Vertex *vx, double x, double y, double z) {
  vx->wc[X] = x;
  vx->wc[Y] = y;
  vx->wc[Z] = z;
  vx->wc[W] = 1.0;
  vx->N[0] = vx->N[1] = vx->N[2] = vx->N[3] = 0.0;
}
/* ------------------------------ end Vertex ------------------------------ */

/* ------------------------------ vertices -------------------------------- */
/*
 * Allocates enough memory for initial vertices
 * Returns FALSE if allocation fails
*/
BOOLEAN Vertices_alloc() {
  if( vertices ) {
    free(vertices);
  }
  nVertices = nPoints;
  if( (vertices = (Vertex *)malloc(nVertices*sizeof(Vertex))) == NULL ) {
    nVertices = 0;
    return FALSE;
  }
  return TRUE;
}

/*
 * Assigns initial vertices
*/
void Vertices_construct() {
  int i;
  for( i = 0; i < nVertices; i++ ) {
    Vertex_construct(&vertices[i],
      points[i][X],
      points[i][Y],
      points[i][Z]);
  }
}

/*
 * Normalizes vertices and light to the canonical view volume
*/
void Vertices_normalize(xform nt) {
  int i;
  for( i = 0; i < nVertices; i++ ) {
    transformPoint(vertices[i].nc,
      nt,
      vertices[i].wc);
  }

  /* normalize the light */
  transformPoint(myLight.nc, nt, myLight.wc);
}

/*
 * Projects vertices to 2D
*/
void Vertices_project(xform pt) {
  int i;
  for( i = 0; i < nVertices; i++ ) {
    projectPoint(vertices[i].pc,
      &vertices[i].zValue,
      pt,
      vertices[i].nc);
  }
}

/*
 * Transforms normalized vertex coordinates to
 * the frame buffer coordinates
*/
void Vertices_tofb(int x_pixels, int y_pixels) {
  int i;
  double xp2 = x_pixels/2.0;
  double yp2 = y_pixels/2.0;

  for( i = 0; i < nVertices; i++ ) {
    Vertex *v = &vertices[i];
    v->xd = v->pc[X]*xp2 + xp2;
    v->yd = v->pc[Y]*yp2 + yp2;
    v->xi = (int)floor(v->xd);
    v->yi = (int)floor(v->yd);
  }
}

/* compute vertex normals for gouraud and phong shading */
void Vertices_compute_normals() {
	int i;
	for( i = 0; i < nInitialFaces; i++ ) {
		Face *f = &faces[i];
		int i0 = f->t.vis[0];
		int i1 = f->t.vis[1];
		int i2 = f->t.vis[2];
		Vertex *v0 = &vertices[i0];
		Vertex *v1 = &vertices[i1];
		Vertex *v2 = &vertices[i2];

		/* CODE: add this face's contribution to the normal for v0 */
		/* CODE: add this face's contribution to the normal for v1 */
		/* CODE: add this face's contribution to the normal for v2 */
	}

	/* normalize vertex norms to length 1.0 */
	for ( i = 0; i < nVertices; i++ ) {
		Vertex *v = &vertices[i];
		/* CODE: normalize the normal for this vertex */
	}
}

/* compute the vertex unit V vectors for gouraud shading */
void Vertices_setV() {
	int i;
	vector eyepoint;

	/* CODE: set eyepoint to location of eye in normalized coordinates */

	for ( i = 0; i < nVertices; i++ ) {
		Vertex *v = &vertices[i];

		/* CODE: calculate the _unit_ vector V (2 lines) */
	}
}

/* compute the vertex unit L vectors for gouraud shading */
void Vertices_setL() {
	int i;
	for ( i = 0; i < nVertices; i++ ) {
		Vertex *v = &vertices[i];

		/* CODE: calculate the _unit_ vector L and 
		 * store the distance from the triangle to light (3 lines) 
		 */
	}
}

/* compute the vertex unit R vectors for gouraud shading */
void Vertices_setR() {
	int i;
	double NL;
	for ( i = 0; i < nVertices; i++ ) {
		Vertex *v = &vertices[i];

		/* CODE: calculate the _unit_ vector R (4 lines) */
	}
}

/* ------------------------------ end vertices ---------------------------- */

/* --------------------------------- Edge --------------------------------- */
/*
 * Prepares the edge for scan converting
*/
void Edge_init(Edge *e) {
  e->accumulated = e->denominator;
  e->x = e->xIntersect;
}

/*
 * Finds new x intersection (incrementally) of the edge with
 * the next scan line
*/
void edgeStep(Edge *e) {
  e->accumulated += e->numerator;
  e->x += e->defInc;
  e->accumulated -= e->defDec;

  if( e->accumulated > e->denominator ) {
    e->x += e->one;
    e->accumulated -= e->denominator;
  }
}
/* --------------------------------- end Edge ----------------------------- */

/* ------------------------------ edge buckets ---------------------------- */
/* Edge table (buckets) */
DLL *edgeBuckets = NULL;
/* Number of edge buckets == number of scan lines */
int nEdgeBuckets = 0;

/* An array for indexing purposes */
int ii[][2] = {
  {0, 1},
  {1, 2},
  {2, 0}
};

void freeDLLStruct1(DLLStructP p) {
  free(p);
}

/*
 * Deallocates memory occupied by edgeBuckets
*/
void EdgeBuckets_destruct() {
  if( edgeBuckets ) {
    int i;
    for( i = 0; i < nEdgeBuckets; i++ ) {
      DLL_destruct(&edgeBuckets[i], freeDLLStruct1);
    }
    free(edgeBuckets);
    edgeBuckets = NULL;
  }
}

/*
 * Allocates edgeBuckets
 * Returns FALSE if allocation fails
*/
BOOLEAN EdgeBuckets_alloc(int nScanLines) {
  int i;

  EdgeBuckets_destruct();
  nEdgeBuckets = nScanLines;
  if( (edgeBuckets = (DLL *)malloc(nEdgeBuckets*sizeof(DLL))) == NULL ) {
    nEdgeBuckets = 0;
    return FALSE;
  }

  for( i = 0; i < nEdgeBuckets; i++ ) {
    DLL_construct(&edgeBuckets[i]);
  }

  return TRUE;
}

/*
 * Constructs edgeBuckets
*/
BOOLEAN EdgeBuckets_construct() {
  int i;
  int j;

  /* for each face */
  for( i = 0; i < nFaces; i++ ) {
    Triangle *t = Face_getTriangle(&faces[i]);
    Vertex *v[3];

    v[0] = Triangle_getVertex(t, 0);
    v[1] = Triangle_getVertex(t, 1);
    v[2] = Triangle_getVertex(t, 2);

    /* for each edge of the triangle */
    for( j = 0; j < 3; j++ ) {
      Vertex *v0 = v[ii[j][0]]; /* one vertex of the edge */
      Vertex *v1 = v[ii[j][1]]; /* another vertex of the edge */
      Vertex *yLowerVertex; /* vertex with the larger y */
      Vertex *yUpperVertex; /* vertex with the smaller y */
      int yLower; /* smaller (lower) y value */
      int yUpper; /* larger (upper) y value */
      Edge *pEdge;
      DLLStruct *pDLLStruct;
	  Color3d diffuse_color, specular_color;
	  double NL0, NL1, VR0, VR1;
	  Face *f;

      yLowerVertex = (v0->yi < v1->yi) ? v0 : v1;
      yUpperVertex = (yLowerVertex == v0) ? v1 : v0;

      yLower = yLowerVertex->yi;
      yUpper = yUpperVertex->yi;

      if( yLower == yUpper ) {
	continue; /* skip horizontal edges */
      } else {
	if( (pDLLStruct = (DLLStruct *)malloc(sizeof(DLLStruct))) == NULL ) {
	  return FALSE;
	}

	if( (pEdge = (Edge *)malloc(sizeof(Edge))) == NULL ) {
	  return FALSE;
	}

	/* initialize the edge's data structure */
	pEdge->yLower = yLower;
	pEdge->yUpper = yUpper;
	pEdge->xIntersect = yLowerVertex->xi;
	pEdge->numerator = yUpperVertex->xi - yLowerVertex->xi;
	pEdge->denominator = yUpper - yLower;
	pEdge->fi = i;

	pEdge->accumulated = pEdge->denominator;
	pEdge->one = (pEdge->numerator > 0) ? 1 : -1;
	pEdge->defInc = pEdge->numerator / pEdge->denominator;
	pEdge->numerator = abs(pEdge->numerator);
	pEdge->defDec = abs(pEdge->defInc) * pEdge->denominator;

	pEdge->z0 = yLowerVertex->zValue;
	pEdge->z1 = yUpperVertex->zValue;

	pEdge->v0 = yLowerVertex;
	pEdge->v1 = yUpperVertex;

	/* get edge vertex colors for gouraud shading */
	f = &faces[pEdge->fi];
	
	/* 'get the diffuse_color' from the material for this face */
	diffuse_color = Material_getDiffColor3d(&materials[f->mi]);
	/* 'get the specular_color' from the material for this face*/
	specular_color = Material_getSpecColor3d(&materials[f->mi]);

	/* CODE: calculate N dot L for pEdge->v0 */
	/* CODE: calculate N dot L for pEdge->v1 */

	/* CODE: calculate V dot R for pEdge->v0 */
	/* CODE: calculate V dot R for pEdge->v1 */

	/* CODE: 'calculate the color' for pEdge->v0 and store in pEdge->c0 */
	/* CODE: 'calculate the color' for pEdge->v1 and store in pEdge->c1 */

	/* add edge to the bucket at yLower */
	pDLLStruct->pData = pEdge;
	DLL_addToTail(&edgeBuckets[yLower], pDLLStruct);
      }
    }
  }

  return TRUE;
}
/* ------------------------------ end edge buckets ------------------------ */

/* ---------------------------- x intersections --------------------------- */

/* Intersections */
Isec *xIsecs = NULL;
/* Number of intersections */
int nIsecs = 0;

/*
 * Allocates memory for maximum possible number of x intersections
 * Returns FALSE if allocation fails
*/
BOOLEAN xIsecs_alloc(int xPixels) {
  if( xIsecs ) {
    free(xIsecs);
  }
  if( (xIsecs = (Isec *)malloc(xPixels*2*sizeof(Isec))) == NULL ) {
    return FALSE;
  }
  return TRUE;
}

/*
 * Initializes x intersections
*/
void xIsecs_init() {
  nIsecs = 0;
}

/*
 * "Allocates" space for n x intersections in xIsecs
 * Returns starting index of the block
*/
int xIsecs_allocIsecs(int n) {
  int i = nIsecs;
  nIsecs += n;
  return i;
}

/* Polygon ids corresponding to xIsecs pairs */
int *polyIds = NULL;
/* Number of ids */
int nPolyIds = 0;

/*
 * Allocates enough memory for maximum possible number of polygon ids
 * Returns FALSE if allocation fails
*/
BOOLEAN polyIds_alloc(int nPolygons) {
  if( polyIds ) {
    free(polyIds);
  }
  if( (polyIds = (int *)malloc(nPolygons*sizeof(int))) == NULL ) {
    return FALSE;
  }
  return TRUE;
}

/*
 * Initializes polygonIds
*/
void polyIds_init() {
  nPolyIds = 0;
}

/*
 * "Allocates" space for id in polyIds
 * and initializes that space with id
*/
void polyIds_allocId(int id) {
  polyIds[nPolyIds] = id;
  nPolyIds++;
}

/* IsecIndex for each polygon */
IsecIndex *isecIndices = NULL;
/* Number of IsecIndex's */
int nIsecIndices = 0;


/*
 * Initializes IsecIndex
*/
void IsecIndex_init(IsecIndex *pIsecIndex) {
  pIsecIndex->index = -1; /* not being scan converted */
  pIsecIndex->n = 0;      /* 0 x intersections so far */
}


/*
 * Allocates space for IsecIndex's
 * Returns FALSE if allocation fails
*/
BOOLEAN isecIndices_alloc(int nPolygons) {
  if( isecIndices ) {
    free(isecIndices);
  }
  if( (isecIndices = (IsecIndex *)malloc(nPolygons*sizeof(IsecIndex))) == NULL ) {
    return FALSE;
  }
  nIsecIndices = nPolygons;
  return TRUE;
}

/*
 * Initializes isecIndices
*/
void isecIndices_init() {
  int i;
  for( i = 0; i < nIsecIndices; i++ ) {
    IsecIndex_init(&isecIndices[i]);
  }
}
/* ---------------------------- end x intersections ----------------------- */

/* --------------------- active edge table -------------------------------- */
/* Active edge table */
DLL aet;

void freeDLLStruct3(DLLStruct *p) {
  free(p);
}

/*
 * Deallocates memory taken by aet
*/
void AET_destruct() {
  DLL_destruct(&aet, freeDLLStruct3);
}

/*
 * Constructs aet
*/
void AET_construct() {
  DLL_destruct(&aet, freeDLLStruct3);
  DLL_construct(&aet);
}

/*
 * Adds and edge to aet
 * Returns FALSE if fails
*/
BOOLEAN AET_addEdge(Edge *pEdge) {
  DLLStruct *pDLLStruct;

  if( (pDLLStruct = malloc(sizeof(DLLStruct))) == NULL ) {
    return FALSE;
  }

  pDLLStruct->pData = pEdge;
  DLL_addToTail(&aet, pDLLStruct);

  return TRUE;
}
/* --------------------- end active edge table ---------------------------- */

/* for a given 'a' between 'a0' and 'a1' interpolate its scalar 'b' value between 'b0' and 'b1' */
void sinterpolate(double *b, double b0, double b1, double a, double a0 , double a1){
	double c, s;

	/* set the scale 's' */
	s = (a - a0) / (a1 - a0);
	/* interpolate */
	c = (s * (b1 - b0)) + b0;
	*b = c;
}

/* for a given 'a' between 'a0' and 'a1' interpolate its vector 'b' value between 'b0' and 'b1' */
void vinterpolate(vector b, vector b0, vector b1, double a, double a0, double a1){
	double s;
	vector c;

	/* CODE: set scale 's' */
	/* CODE: interpolate (4 lines) */
}

/* -------------------------- lighting ----------------------------------- */

/* calculate the color given the lighting parameters */
Color3d calcColor(Light light, double NL, double VR, double dist, Color3d diffuse, Color3d specular){
	Color3d I;
	/* ignore obtuse angles */
	if (NL<0.0) NL = 0.0;
	if (VR<0.0) VR = 0.0;

	/* CODE: 'calculate red wavelength' */
	/* CODE: 'calculate green wavelength' */
	/* CODE: 'calculate blue wavelength' */

	/* make sure I is in range [(0,0,0),(1,1,1)] */
	Color3d_crop(&I);
	return I;
}

/* calculate the wavelength given the lighting parameters */
double calcWavelen(double I, double Ia, double kf, double n_shiny, double NdotL, double RdotV, double dist, double diffuse, double specular){
	double c;
	double ka, kd, ks;
	double fatt;
	double Ip = I;
	double Od = diffuse;
	double Os = specular;
	double d = dist;
	ka = kd = ks = 1.0;

	/* CODE: set fatt with c1 = c2 = 1.0 and c3 = kf */

	/* CODE: calculate the color, 'c', using the Phong illumination model */

	return c;
}
/* -------------------------- end lighting -------------------------------- */


/* -------------------------- scan conversion ----------------------------- */
BOOLEAN scanConvert() {
	int y;
	int x;
	int i;
	DLLStruct *pCur, *pNext;
	Edge *pEdge;
	Edge *pEdge0;
	Edge *pEdge1;
	int fi;
	Color3d diffuse_color, specular_color;
	Isec *i0;
	Isec *i1;

	AET_construct();

	/* for each scan line  */
	for( y = 0; y < y_pixels; y++ ) {
		clearScan(bkg, DBL_MAX);

		/* remove edges not involved in this scan line */
		pCur = aet.pHead; /* start with the head of the list */
		/* for every element in the list */
		while( pCur ) {
			pNext = pCur->pNext;
			pEdge = (Edge *)pCur->pData;
			if( pEdge->yUpper <= y ) {	/* if we are at the upper end of the edge */
				DLL_remove(&aet, pCur);	/* remove the edge */
				fi = pEdge->fi;			/* clear the "flag" structure */
				IsecIndex_init(&isecIndices[fi]);
			}

			pCur = pNext;
		}

		/* add entering edges */
		for( pCur = edgeBuckets[y].pHead; pCur; pCur = pCur->pNext ) {
			pEdge = (Edge *)pCur->pData; /* get the edge */
			Edge_init(pEdge);			/* initialize the edge */
			AET_addEdge(pEdge);			/* add the edge to AET */
		}

		/* determine all x intersections */
		xIsecs_init();	// nIsecs = 0;
		polyIds_init();	// nPolyIds = 0

		/* clear the "flag" structures for all active edges */
		for( pCur = aet.pHead; pCur; pCur = pCur->pNext ) {
			pEdge = (Edge *)pCur->pData;
			fi = pEdge->fi;
			IsecIndex_init(&isecIndices[fi]);
		}
		/* for all active edges, determine x intersections with the current scan line */
		for( pCur = aet.pHead; pCur; pCur = pCur->pNext ) {
			pEdge = (Edge *)pCur->pData; /* get the edge */
			fi = pEdge->fi; /* get face id of the edge */
			if( isecIndices[fi].index == -1 ) { /* if the flag in not set */
				/* set the flag by "allocating" space for a pair of x intersections */
				isecIndices[fi].index = xIsecs_allocIsecs(2);
				/* allocate polygon id corresponding to the pair */
				polyIds_allocId(fi);
			}
			/* store pEdge->x in the xIsecs' space allocated for the polygon fi */
			xIsecs[isecIndices[fi].index+isecIndices[fi].n].x = pEdge->x;
			/* store pEdge in the same space */
			xIsecs[isecIndices[fi].index+isecIndices[fi].n].pEdge = pEdge;
			/* increase number of x intersections found so far */
			isecIndices[fi].n++;
			/* advance current x intersection of the edge with the scan line */
			edgeStep(pEdge);

		}

		/* fill the scan line */
		for( i = 0; i < nPolyIds; i++ ) {
			int xStart, xStop; /* start and stop of the scan line span to fill */
			double zi0, zi1; /* start and stop z-values corresponding to xStart and xStop */
			fi = polyIds[i]; /* get the face id */
			diffuse_color = Material_getDiffColor3d(Face_getMaterial(&faces[fi])); /* get the color of the face */
			specular_color = Material_getSpecColor3d(Face_getMaterial(&faces[fi]));
			/* get the first x intersection and set i0 */
			i0 = &xIsecs[isecIndices[fi].index+0];
			/* get the second x intersection and set i1 */
			i1 = &xIsecs[isecIndices[fi].index+1];

			/* sort x intersections (i0 and i1) in x */
			if (i0->x > i1->x) {
				Isec *temp = i0;
				i0 = i1;
				i1 = temp;
			}

			xStart = i0->x;
			xStop = i1->x;

			pEdge0 = i0->pEdge;


			/* interpolate between pEdge0->z0 and pEdge0->z1 to set zi0 */
			sinterpolate(&zi0, pEdge0->z0, pEdge0->z1, y, pEdge0->yLower, pEdge0->yUpper);

			pEdge1 = i1->pEdge;
			/* interpolate between pEdge1->z0 and pEdge1->z1 to set zi1 */
			sinterpolate(&zi1, pEdge1->z0, pEdge1->z1, y, pEdge1->yLower, pEdge1->yUpper);

			/* set the pixels corresponding to the span */
			for( x = xStart; x < xStop; x++ ) {
				double zValue;
				Color3d I;

				/* interpolate between zi0 and zi1 to set zValue */
				sinterpolate(&zValue, zi0, zi1, x, xStart, xStop);

				if( zValue < zBufferLine[x]) { /* if in front */
					/* set new z-value in zBufferLine */
					zBufferLine[x] = zValue;


					switch (SHADING_MODEL){
					case FLAT:
						I = doFlat(&faces[fi], diffuse_color, specular_color);
						break;
					case GOURAUD:
						I = doGouraud(x, y, pEdge0, pEdge1, xStart, xStop);
						break;
					case PHONG:
						I = doPhong(diffuse_color, specular_color, x, y, pEdge0, pEdge1, zValue, xStart, xStop);
						break;
					}
					scanLine[x] = I;
				}
			}
		}

		/* set pixel values in image */
		for( x = 0; x < x_pixels; x++ ) {
			Image_setPixel3d(&image, x, y, &scanLine[x]);
		}
	}

	return TRUE;
}

/* -------------------------- end scan conversion ------------------------- */


/* lighting */

Color3d doFlat(Face *f, Color3d diffuse, Color3d specular){
	Color3d I;
	/* CODE: calculate the Color for this face */
	return I;
}

Color3d doGouraud(int x, int y, Edge *pEdge0, Edge *pEdge1, int xStart, int xStop){
	Color3d I;
	vector vI0, vI1, vI;
	vector e0_c0, e0_c1, e1_c0, e1_c1;

	/* CODE: set e0_c0 to the pEdge0->c0 */
	/* CODE: set e0_c1 to the pEdge0->c1 */
	/* CODE: set e1_c0 to the pEdge1->c0 */
	/* CODE: set e1_c0 to the pEdge1->c1 */

	/* CODE: interpolate to between e0_c0 and e0_c1 to find vI0 */

	/* CODE: interpolate between e1_c0 and e1_c1 to find vI1 */

	/* CODE: interpolate between vI0 and vI1 to find vI */

	/* CODE: copy the vector vI into the color I. */

	return I;
}

Color3d doPhong(Color3d diffuse_color, Color3d specular_color, int x, int y, Edge *pEdge0, Edge *pEdge1, double zValue, int xStart, int xStop){
	vector norm0, norm1;
	double xi0, xi1, yi0, yi1;
	vector normalizedPixelCoord, normalizedEyePoint;
	double xValue, yValue;
	double NL, VR, dist;
	vector N, L, V, R;
	Color3d I;

	
	/* CODE: interpolate to find the _unit_ normal N (4 lines) */

	/* CODE: interpolate to find this pixel's xValue in normalized coords (3 lines) */

	/* CODE: interpolate to find this pixel's yValue in normalized coords (3 lines) */


	/* CODE: set pixel position 'normalizedPixelCoord' in normalized coordinates */

	/* CODE: set the eye point 'normalizedEyePoint' in normalized coordinates */

	/* CODE: calculate the unit vector L and the distance, 'dist', 
	 * from this pixel to the light source (3 lines) 
	 */

	/* CODE: calculate the unit vector V (2 lines) */

	/* CODE: calculate NL (N dot L) */

	/* CODE: calculate R (2 lines) */					

	/* CODE: calculate VR (V dot R) */

	/* CODE: 'calculate the color' I */

	Color3d_crop(&I);
	return I;
}