/*****************************************************************************
*   Routines to	scan convert the input (polygons), which is sorted into	     *
* global hash table PolyHashTable according to polygons Ymin.		     *
*									     *
* Written by:  Gershon Elber				Ver 2.0, Mar. 1990   *
*****************************************************************************/

#ifdef __MSDOS__
#include <stdlib.h>
#endif /* __MSDOS__ */

#include <math.h>
#include <time.h>
#include <stdio.h>
#include <string.h>
#include "program.h"
#include "parser.h"
#include "gif_lib.h"

/* #define DEBUG		    /* Add some printing to stderr routines. */

#define Z_BUFFER_MIN_Z	-32767

static PixelType *MaskSubScanLine = NULL;
static PixelType *ImageScanLine = NULL;
static PixelType *MaskScanLine = NULL;
static int *ZBuffer;

static void InitScanLine(void);
static void ScanOnePolygon(PolygonStruct *PPolygon, int Level);
static VertexStruct *GetNeighborVrtx(PolygonStruct *PPolygon, VertexStruct *V,
							VertexStruct *NotV);
static void UpdateScanLine(int x1, int z1, int x2, int z2,
						int Color1, int Color2);

#ifdef DEBUG
void PrintHashTable(void);
void PrintPolygon(PolygonStruct *PPolygon);
void PrintImageScanLine(void);
#endif DEBUG

/*****************************************************************************
* Routine to scan convert all polygons in PolyHashTable.		     *
* The real images goes to GifFile, while GifMask (if not NULL) will have a   *
* booleam mask, where image was created.				     *
*****************************************************************************/
void ScanConvertData(GifFileType *GifFile, GifFileType *GifMask)
{
    char *ImageSubBGScanLine;
    int i, j, k, OrigScreenXSize, OrigScreenYSize, *ImageSubScanLine,
	SubSamplePixelSquare, *MinIntensityIndex, SubSamplePixel,
	MinYScan = 0, SubSampleLine = 0, LineCount = 0;
    long SaveTime = time(NULL);
    PolygonStruct *PPolygon, *PPolygonLast;
    PixelType *OneSubScanLine;

    OrigScreenXSize = ScreenXSize;
    OrigScreenYSize = ScreenYSize;

    ScreenXSize *= ShadingInfo.SubSamplePixel;
    ScreenYSize *= ShadingInfo.SubSamplePixel;

    if (ShadingInfo.SubSamplePixel > 1) {
	OneSubScanLine = (PixelType *) MyMalloc(sizeof(PixelType) *
							OrigScreenXSize);
	ImageSubScanLine = (int *) MyMalloc(sizeof(int) * OrigScreenXSize);
	ImageSubBGScanLine = (char *) MyMalloc(sizeof(char) * OrigScreenXSize);
    }
    ImageScanLine = (PixelType *) MyMalloc(sizeof(PixelType) * ScreenXSize);
    if (GifMask != NULL) {
	if (ShadingInfo.SubSamplePixel > 1)
	    MaskSubScanLine = (PixelType *) MyMalloc(sizeof(PixelType) *
							OrigScreenXSize);
	MaskScanLine = (PixelType *) MyMalloc(sizeof(PixelType) * ScreenXSize);
    }
    ZBuffer = (int *) MyMalloc(sizeof(int) * ScreenXSize);

    MinIntensityIndex = ShadingInfo.MinIntensityIndex;
    SubSamplePixel = ShadingInfo.SubSamplePixel;
    SubSamplePixelSquare = SQR(SubSamplePixel);

    fprintf(stderr, "\nPass 4, Level [%4d] =      ", OrigScreenYSize);

    for (i=0; i<ScreenYSize; i++) {			     /* Scan line i: */
	/* First lets scan and delete all polygons below this scan line: */
	for (j=MinYScan; j<=i; j++) {
	    PPolygon = PPolygonLast = PolyHashTable[j];
	    while (PPolygon) {
		if (PPolygon -> Ymax < i) {	     /* Delete this polygon. */
		    /* If it is first one, update the hash table also. Note  */
		    /* we dont free the polygon as, we are not going to      */
		    /* allocate anything any more, so why bather.	     */
		    if (PPolygon == PolyHashTable[j])
			PolyHashTable[j] = PPolygonLast = PPolygon =
			    PPolygon -> Pnext;
		    else PPolygonLast -> Pnext = PPolygon = PPolygon -> Pnext;
		}
		else {
		    PPolygonLast = PPolygon;
		    PPolygon = PPolygon -> Pnext;
		}
	    }
	    /* If this level is empty - advance the minimum level to scan: */
	    if (j == MinYScan && PolyHashTable[j] == NULL) MinYScan++;
	}

	/* New do the scan conversion of the active polygons: */
	InitScanLine();
	for (j=MinYScan; j<=i; j++) {
	    PPolygon = PPolygonLast = PolyHashTable[j];
	    while (PPolygon) {
		ScanOnePolygon(PPolygon, i);
		PPolygonLast = PPolygon;
		PPolygon = PPolygon -> Pnext;
	    }
	}

	if (SubSamplePixel > 1) {
	    if (SubSampleLine == 0) {	  /* Reset the sub sumpling buffers. */
		memset(ImageSubScanLine, 0,
					sizeof(int) * OrigScreenXSize);
		memset(OneSubScanLine, 0,
					sizeof(PixelType) * OrigScreenXSize);
		memset(ImageSubBGScanLine, 0,
					sizeof(char) * OrigScreenXSize);
		if (GifMask) memset(MaskSubScanLine, 0,
					sizeof(PixelType) * OrigScreenXSize);
	    }
	    for (j=0; j<ScreenXSize; j++)
		if (ImageScanLine[j] == 0)
		    ImageSubBGScanLine[j / SubSamplePixel]++;
		else {
		    k = j / SubSamplePixel;
		    ImageSubScanLine[k] += ImageScanLine[j];
		    OneSubScanLine[k] = ImageScanLine[j];
		    if (GifMask) MaskSubScanLine[k] = MaskScanLine[j] != 0 ||
							   MaskSubScanLine[k];
		}
	    SubSampleLine++;
	    if (SubSampleLine == SubSamplePixel) {
		for (j=0; j<OrigScreenXSize; j++) {
		    /* Instead of Back Ground - add the lowest intensity of */
		    /* This color. Note we still may have problems if two   */
		    /* colors are averaged to a color index in between...   */
		    if (ImageSubScanLine[j] > 0)
			ImageSubScanLine[j] += ImageSubBGScanLine[j] *
					MinIntensityIndex[OneSubScanLine[j]];
		    OneSubScanLine[j] = ImageSubScanLine[j] /
							SubSamplePixelSquare;
		}
		fprintf(stderr, "\b\b\b\b\b%5d", ++LineCount);

#	        ifndef DEBUG_NO_GIF
		    EGifPutLine(GifFile, OneSubScanLine, OrigScreenXSize);
		    if (GifMask)
			EGifPutLine(GifMask, MaskSubScanLine, OrigScreenXSize);
#	        endif DEBUG_NO_GIF

		SubSampleLine = 0;
	    }
	}
	else {
	    fprintf(stderr, "\b\b\b\b\b%5d", ++LineCount);

#	    ifndef DEBUG_NO_GIF
		EGifPutLine(GifFile, ImageScanLine, ScreenXSize);
		if (GifMask)
		    EGifPutLine(GifMask, MaskScanLine, ScreenXSize);
#	    endif DEBUG_NO_GIF
	}
    }

    fprintf(stderr, ",  %ld seconds.", time(NULL) - SaveTime);

    ScreenXSize = OrigScreenXSize;
    ScreenYSize = OrigScreenYSize;
}

/*****************************************************************************
* Reset all buffers to clear state:					     *
*****************************************************************************/
static void InitScanLine(void)
{
    memset(ImageScanLine, 0, sizeof(PixelType) * ScreenXSize);

    if (MaskScanLine) memset(MaskScanLine, 0, sizeof(PixelType) * ScreenXSize);

    /* Set all Zbuffer to Z_BUFFER_MIN_Z. Can be done in a regular loop as:  */
    /* for (i=0; i<ScreenXSize; i++) ZBuffer[i] = Z_BUFFER_MIN_Z;            */
    /* As memset allows setting of only one byte, the minimum we can set     */
    /* here is -32640 which is 0x8080, so we do that instead:		     */
    memset(ZBuffer, 0x80, sizeof(int) * ScreenXSize);
}

/*****************************************************************************
* Scan convert one polygon:						     *
* 1. If one of the left/right boundaries is found to be below current level  *
*    that boundary edge is updated.					     *
* 2. Interpolate the Color and Z value of the intersection of scan line with *
*    the boundaries and call UpdateScanLine to update the buffers.	     *
*****************************************************************************/
static void ScanOnePolygon(PolygonStruct *PPolygon, int Level)
{
    int x1, z1, x2, z2, Color1, Color2;
    float t1, t2, *Coord1, *Coord2;
    VertexStruct *V;

    /* Stage 1 - verify that both boundaries are in range: */
    if (PPolygon -> Bndry1.MaxEdgeY < Level) {
	V = PPolygon -> Bndry1.VMinY;
	PPolygon -> Bndry1.VMinY = PPolygon -> Bndry1.VMaxY;
	PPolygon -> Bndry1.VMaxY =
	    GetNeighborVrtx(PPolygon, PPolygon -> Bndry1.VMaxY, V);
	PPolygon -> Bndry1.MaxEdgeY =
	    (int) PPolygon -> Bndry1.VMaxY -> Coord[1];
    }

    if (PPolygon -> Bndry2.MaxEdgeY < Level) {
	V = PPolygon -> Bndry2.VMinY;
	PPolygon -> Bndry2.VMinY = PPolygon -> Bndry2.VMaxY;
	PPolygon -> Bndry2.VMaxY =
	    GetNeighborVrtx(PPolygon, PPolygon -> Bndry2.VMaxY, V);
	PPolygon -> Bndry2.MaxEdgeY =
	    (int) PPolygon -> Bndry2.VMaxY -> Coord[1];
    }

    /* Stage 2 - evaluate the interpolated X & Z for this line and call      */
    /* UpdateScanLine with them. Note we could do it using some sort of DDA  */
    /* (integer arithmetic) but as UpdateScanLine is much more expensive     */
    /* we will gain almost nothing in speed, doing that.		     */
    /* Also as this polygon assumed to intersect with the scan line using    */
    /* integer arithmetic, it might not be so, when we actuallt evaluate it. */
    /* We simply quit if that is the case.				     */
    Coord1 = PPolygon -> Bndry1.VMinY -> Coord;
    Coord2 = PPolygon -> Bndry1.VMaxY -> Coord;
    if (ABS(Coord2[1] - Coord1[1]) == 0.0)
	 t1 = 0.5;
    else t1 = (Coord2[1] - Level) / (Coord2[1] - Coord1[1]);
    if (t1 < 0.0 || t1 > 1.0) return;

    x1 = Coord1[0] * t1 + Coord2[0] * (1.0 - t1);
    z1 = Coord1[2] * t1 + Coord2[2] * (1.0 - t1);

    Coord1 = PPolygon -> Bndry2.VMinY -> Coord;
    Coord2 = PPolygon -> Bndry2.VMaxY -> Coord;
    if (ABS(Coord2[1] - Coord1[1]) == 0.0)
	 t2 = 0.5;
    else t2 = (Coord2[1] - Level) / (Coord2[1] - Coord1[1]);
    if (t2 < 0.0 || t2 > 1.0) return;

    x2 = Coord1[0] * t2 + Coord2[0] * (1.0 - t2);
    z2 = Coord1[2] * t2 + Coord2[2] * (1.0 - t2);

    if (GouraudFlag) {
	/* Need to interpolate the colors as well: */
	Color1 = (int) (PPolygon -> Bndry1.VMinY -> Color * t1 +
			PPolygon -> Bndry1.VMaxY -> Color * (1.0 - t1));
	Color2 = (int) (PPolygon -> Bndry2.VMinY -> Color * t2 +
			PPolygon -> Bndry2.VMaxY -> Color * (1.0 - t2));
	UpdateScanLine(x1, z1, x2, z2, Color1, Color2);
    }
    else {

	/* Flat shading - all vertices has same intensity - pick one: */
	UpdateScanLine(x1, z1, x2, z2, PPolygon -> Bndry1.VMinY -> Color,
				       PPolygon -> Bndry1.VMinY -> Color);
    }
}

/*****************************************************************************
* Returns the other neighbor of vertex V in polygon PPolygon which is not    *
* the neighbor NotV.							     *
*****************************************************************************/
static VertexStruct *GetNeighborVrtx(PolygonStruct *PPolygon, VertexStruct *V,
							VertexStruct *NotV)
{
    struct VertexStruct *List = PPolygon -> PVertex, *ListLast;

    if (List == V) {
	/* The vertex is first - its neighbors are second and last in list.  */
	if (List -> Pnext == NotV) {
	    /* We need the last one: */
	    while (List -> Pnext != NULL) List = List -> Pnext;
	    return List;
	}
	else return List -> Pnext;
    }

    ListLast = List;
    List = List -> Pnext;
    while (List != NULL) {
	if (List == V) {
	    if (ListLast == NotV) {
		/* We need the next vertex instead of last one: */
		if (List -> Pnext == NULL)
		     return PPolygon -> PVertex;
		else return List -> Pnext;
	    }
	    else return ListLast;
	}
	ListLast = List;
	List = List -> Pnext;
    }
    return List;	     /* Should never be here - make warnings silent. */
}

/*****************************************************************************
* Update the scan line itself by linearly interplate the two end points for  *
* all internal points of scan line if closer than old data.		     *
*****************************************************************************/
static void UpdateScanLine(int x1, int z1, int x2, int z2,
						int Color1, int Color2)
{
    int i, Dx, Dz, Dc, Az, Ac, x, z, Color;
    float t;

    if (x2 < x1) {
	i = x2; x2 = x1; x1 = i;
	i = z2; z2 = z1; z1 = i;
	i = Color2; Color2 = Color1; Color1 = i;
    }
    if (x1 < 0) {
	/* Update lower limit to zero: */
	if (x2 == x1) return;
	t = -x1 / (x2 - x1);
	x1 = 0;
	z1 = (int) (z1 * (1.0 - t) + z2 * t);
	Color1 = (int) (Color1 * (1.0 - t) + Color2 * t);
    }
    if (x2 >= ScreenXSize) {
	/* Update upper limit to ScreenXSize - 1: */
	if (x2 == x1) return;
	t = (x2 - (ScreenXSize - 1)) / (x2 - x1);
	x2 = ScreenXSize - 1;
	z2 = (int) (z1 * t + z2 * (1.0 - t));
	Color2 = (int) (Color1 * t + Color2 * (1.0 - t));
    }

    Dx = x2 - x1;
    x = x1;
    Dz = z2 - z1;
    Az = -Dx;			      /* DDA accumulator of Z interpolation. */
    z = z1;
    Color = Color1;
    if (GouraudFlag) {
	Dc = Color2 - Color1;	     /* Needed if Gouraud shading is in use. */
	Ac = -Dx;		  /* DDA accumulator of Color interpolation. */
    }

    /* We are going to execute the loop once but might be stack forever in   */
    /* one of the internal interplation loops, so make it non zero:	     */
    if (Dx == 0) Dx = 999;

    if (Dz > 0) {
	while (x <= x2) {
	    /* Update buffers iff is closer to view point: */
	    if (ZBuffer[x] < z) {
		ZBuffer[x] = z;
		ImageScanLine[x] = Color;
		if (MaskScanLine != NULL) MaskScanLine[x] = 1;
	    }
	    else
	    if (ZBuffer[x] == z) {
		/* This case is hard to solve, and it may create high	     */
		/* intensity lines on polygon boundaries. To prevent from    */
		/* that, update iff new color intensity is less than old on. */
		if (ImageScanLine[x] < Color) ImageScanLine[x] = Color;
		if (MaskScanLine != NULL) MaskScanLine[x] = 1;
	    }

	    Az += Dz;
	    x++;
	    while (Az > 0) {
		z++;
		Az -= Dx;
	    }
	    if (GouraudFlag) {
		if (Dc > 0) {
		    Ac += Dc;
		    while (Ac > 0) {
			Color++;
			Ac -= Dx;
		    }
		}
		else { /* Dc < 0 */
		    Ac -= Dc;
		    while (Ac > 0) {
			Color--;
			Ac -= Dx;
		    }
		}
	    }
	}
    }
    else { /* Dz < 0 */
	while (x <= x2) {
	    /* Update buffers iff is closer to view point: */
	    if (ZBuffer[x] < z) {
		ZBuffer[x] = z;
		ImageScanLine[x] = Color;
		if (MaskScanLine != NULL) MaskScanLine[x] = 1;
	    }
	    else
	    if (ZBuffer[x] == z) {
		/* This case is hard to solve, and it may create high	     */
		/* intensity lines on polygon boundaries. To prevent from    */
		/* that, update iff new color intensity is less than old on. */
		if (ImageScanLine[x] < Color) ImageScanLine[x] = Color;
		if (MaskScanLine != NULL) MaskScanLine[x] = 1;
	    }

	    Az -= Dz;
	    x++;
	    while (Az > 0) {
		z--;
		Az -= Dx;
	    }
	    if (GouraudFlag) {
		if (Dc > 0) {
		    Ac += Dc;
		    while (Ac > 0) {
			Color++;
			Ac -= Dx;
		    }
		}
		else { /* Dc < 0 */
		    Ac -= Dc;
		    while (Ac > 0) {
			Color--;
			Ac -= Dx;
		    }
		}
	    }
	}
    }
}

#ifdef DEBUG

/*****************************************************************************
* Routine to print the content of a given edge:				     *
*****************************************************************************/
void PrintHashTable(void)
{
    int i;
    PolygonStruct *PPolygon;

    for (i=0; i<ScreenYSize; i++) if (PolyHashTable[i] != NULL) {
	fprintf(stderr,
	    "\n***************** HashTable entry %d *****************\n", i);
	PPolygon = PolyHashTable[i];
	while (PPolygon) {
	    fprintf(stderr, "\t+++++++ Polygon:\n");
	    PrintPolygon(PPolygon);
	    PPolygon = PPolygon -> Pnext;
	}
    }
}

/*****************************************************************************
* Routine to print the content of a given edge:				     *
*****************************************************************************/
void PrintPolygon(PolygonStruct *PPolygon)
{
    struct VertexStruct *PList = PPolygon -> PVertex;

    while (PList) {
	fprintf(stderr, "\t%12f %12f %12f (Color = %d)\n",
	    PList -> Coord[0],
	    PList -> Coord[1],
	    PList -> Coord[2],
	    PList -> Color);
	PList =	PList -> Pnext;
    }
}

/*****************************************************************************
* Routine to print content of Image Scan Line buffer:			     *
*****************************************************************************/
void PrintImageScanLine(void)
{
    int i;

    for (i=0; i<ScreenXSize; i++) {
	if (i % 26 == 0) fprintf(stderr, "\n");
	fprintf(stderr, "%02x ", ImageScanLine[i]);
    }
}

#endif DEBUG