#include <GL/glut.h>
#include <iostream.h>
#include "lineseg.h"



/*  some constants  */
const int BUFFWIDTH= 100;
const int BUFFHEIGHT= 100;
const int MAXVERTICES=20;

/* the global variables */
int		fb[BUFFWIDTH][BUFFHEIGHT];  				/* the simulated frame buffer*/


//
//  This is the code for polygon filling
//
//  you must define MAXVERTICES, BUFFWDITH, BUFFHEIGHT
//  and fb[BUFFWIDTH][BUFFHEIGHT]
//
//	you also need the file linseg.h
//
linesegment* sortlist(linesegment* hptr);
float	zclamp(float x);
int		zmod(int i, int j);
int		zround(float x);
int		zceil(float x);


//
//  PolyFill scan converts a filled polygon.  The vertices of the
//  polygon should be in DEVICE coordinates; i.e. x in [0,BUFFWIDTH-1]
//  and y in [0,BUFFHEIGHT-1]
//
//  Arguments:
//        int numvertices     the number of vertices in the polygon
//        float vertices[][2]     the x-y coordinates of the vertices;
// 
//  Error checking:
//        the fill routine prints an error if the polygon falls
//        outside of the framebuffer
//
// 

void PolyFill(int numvertices, float vertices[][2]) 
{
	int i,j;
	float x0, x1, y0, y1;
	linesegment		lsegs[MAXVERTICES];
	linesegment		*ET[BUFFHEIGHT];
	linesegment		*AET,*ptr,*lptr;

	
	// build ET
	for (i=0;i<BUFFHEIGHT;i++)
		ET[i]=NULL;
	for (i=0;i<numvertices;i++) {
		// get first endpoint
		x0 = zclamp(vertices[i][0]);
		y0 = zclamp(vertices[i][1]);
		// get second endpoint
		j=zmod(i+1,numvertices);
		x1 = zclamp(vertices[j][0]);
		y1 = zclamp(vertices[j][1]);
		//create new record
		lsegs[i] = linesegment(x0,y0,x1,y1);
		//add new record to the edge table
		j = zround(lsegs[i].y0);
		lsegs[i].next = ET[j];
		ET[j]= &lsegs[i];
		if (x0 < 0 || x0 > BUFFWIDTH-1 || x1 < 0 || x1 > BUFFWIDTH-1 || y0 < 0 || y0 > BUFFHEIGHT-1 || y1 < 0 || y1 > BUFFHEIGHT-1)
			cerr << "Warning:  Polygon vertices are out of range.\n"
	}


	AET=NULL;
	for (int sline = 0; sline < BUFFHEIGHT; sline ++) {

		// update x intercepts
		ptr = AET;
		while (ptr!=NULL) {
			ptr->updatex();
			ptr = ptr->next;
		}
	
		//  add new line segments from ET

		if (AET == NULL)
			AET = ET[sline];
		else {
			ptr = AET;
			while (ptr->next != NULL)
				ptr = ptr->next;
			ptr->next = ET[sline];
		}

		//  remove done lines from AET
		bool found=FALSE;
		//  find first good line, if there is one
		while (AET!= NULL && found==FALSE) {
			if (zround(AET->y1) > sline)
				found=TRUE;
			else 
				AET = AET->next;
		}
		// if good line found then search remainder of list
		if (AET != NULL) {
			ptr = AET->next;
			lptr = AET;
			while (ptr != NULL) {
				if (zround(ptr->y1) <= sline)  
					lptr->next = ptr->next;
				else
					lptr = ptr;
				ptr = ptr->next;
			}
		}

		// sort
		AET = sortlist(AET);
			
		// scan convert
		ptr = AET;
		while (ptr != NULL) {
			for (i=zceil(zclamp(ptr->currx)); i<zclamp(ptr->next->currx); i++) {
				fb[i][sline]=1;
			}
			ptr = ptr->next->next;			
		}
	}

	return;
}
//
//  insertion sort
//


linesegment* sortlist(linesegment *hptr)
{
	linesegment *ptr,*lptr, *nptr, *head;
	int found;

	head = hptr;
	if (head != NULL) {
		ptr = head-> next;
		lptr = head;
		lptr->prev = NULL;
		while (ptr!=NULL) {
			ptr->prev = lptr;
			lptr = ptr;
			ptr = ptr->next;
		}
		ptr = head->next;
		while (ptr != NULL) {
			nptr = ptr->next;
			lptr =  ptr->prev;
			found = (ptr->currx >= lptr->currx);
			while (lptr != NULL && !found) {
				lptr = lptr->prev;
				if (lptr!=NULL)
					found = (ptr->currx > lptr->currx);	
			}
			if (lptr!=ptr->prev) {
				// remove ptr record from list
				ptr->prev->next = ptr->next;
				if (ptr->next != NULL)
					ptr->next->prev = ptr->prev;
				// insert in correct position
				if (lptr==NULL) {
					ptr->next = head;
					ptr->prev = NULL;
					head=ptr;
				}
				else {
					ptr->next = lptr->next;
					ptr->prev = lptr;
					if (lptr->next != NULL)
						lptr->next->prev=ptr;
					lptr->next = ptr;
				}

			}
			ptr=nptr;
		}
	}
	return head;
}

//
//  a simple mod function for i in [0 .. 2j-1]
//

int zmod(int i, int j)
{
	if (i>=j)
		return(i-j);
	else 
		return(i);
}

//  
//  a ceiling function
//

int zceil(float x)
{
	int i;
	i = (int) x;
	if (i < x)
		i = i+1;
	return(i);
}
//
//  a rounding function
//
int zround(float x) 
{
	if (x >= (float) 0)
		return (int) (x+0.5);
	return (int) (x-0.5);
	
}
//
// this reduces the significant digits
// to four -- it is used to
// eliminate slight errors introduced
// during transformations
//

float zclamp(float x)
{
	int i;
	i=zround((float) 1000.0 * x);
	return (float) i/(float) 1000.0;
}