/*****************************************************************************
*   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 "iritprsr.h"

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

#define Z_BUFFER_MIN_Z	-32767

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

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

#ifdef DEBUG
void PrintHashTable(void);
void PrintPolygon(IPPolygonStruct *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, OrigScrnXSize, OrigScrnYSize, *ImageSubScanLine,
	SubSamplePixelSquare, *MinIntensityIndex, SubSamplePixel,
	MinYScan = 0, SubSampleLine = 0, LineCount = 0;
    long SaveTime = time(NULL);
    IPPolygonStruct *PPolygon, *PPolygonLast;
    GifPixelType *OneSubScanLine;

    OrigScrnXSize = GlblShadeInfo.ScrnXSize;
    OrigScrnYSize = GlblShadeInfo.ScrnYSize;

    GlblShadeInfo.ScrnXSize *= GlblShadeInfo.SubSamplePixel;
    GlblShadeInfo.ScrnYSize *= GlblShadeInfo.SubSamplePixel;

    if (GlblShadeInfo.SubSamplePixel > 1) {
	OneSubScanLine = (GifPixelType *) MyMalloc(sizeof(GifPixelType) *
						OrigScrnXSize);
	ImageSubScanLine = (int *) MyMalloc(sizeof(int) *
						OrigScrnXSize);
	ImageSubBGScanLine = (char *) MyMalloc(sizeof(char) *
						OrigScrnXSize);
    }
    ImageScanLine = (GifPixelType *) MyMalloc(sizeof(GifPixelType) *
						GlblShadeInfo.ScrnXSize);
    if (GifMask != NULL) {
	if (GlblShadeInfo.SubSamplePixel > 1)
	    MaskSubScanLine = (GifPixelType *) MyMalloc(sizeof(GifPixelType) *
						OrigScrnXSize);
	MaskScanLine = (GifPixelType *) MyMalloc(sizeof(GifPixelType) *
						GlblShadeInfo.ScrnXSize);
    }
    ZBuffer = (int *) MyMalloc(sizeof(int) * GlblShadeInfo.ScrnXSize);

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

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

    for (i = 0; i < GlblShadeInfo.ScrnYSize; 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) * OrigScrnXSize);
		memset(OneSubScanLine, 0,
			sizeof(GifPixelType) * OrigScrnXSize);
		memset(ImageSubBGScanLine, 0,
				   sizeof(char) * OrigScrnXSize);
		if (GifMask) memset(MaskSubScanLine, 0,
			      sizeof(GifPixelType) * OrigScrnXSize);
	    }
	    for (j = 0; j < GlblShadeInfo.ScrnXSize; 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 < OrigScrnXSize; 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,
				OrigScrnXSize);
		    if (GifMask)
			EGifPutLine(GifMask, MaskSubScanLine,
				    OrigScrnXSize);
#	        endif /* DEBUG_NO_GIF */

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

#	    ifndef DEBUG_NO_GIF
		EGifPutLine(GifFile, ImageScanLine, GlblShadeInfo.ScrnXSize);
		if (GifMask)
		    EGifPutLine(GifMask, MaskScanLine,
				GlblShadeInfo.ScrnXSize);
#	    endif /* DEBUG_NO_GIF */
	}
    }

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

    GlblShadeInfo.ScrnXSize = OrigScrnXSize;
    GlblShadeInfo.ScrnYSize = OrigScrnYSize;
}

/*****************************************************************************
* Reset all buffers to clear state:					     *
*****************************************************************************/
static void InitScanLine(void)
{
    memset(ImageScanLine, 0, sizeof(GifPixelType) * GlblShadeInfo.ScrnXSize);

    if (MaskScanLine)
        memset(MaskScanLine, 0, sizeof(GifPixelType) * GlblShadeInfo.ScrnXSize);

    /* Set all Zbuffer to Z_BUFFER_MIN_Z. Can be done in a regular loop as:  */
    /* for (i = 0; i < ScrnXSize; 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) * GlblShadeInfo.ScrnXSize);
}

/*****************************************************************************
* 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(IPPolygonStruct *PPolygon, int Level)
{
    int x1, z1, x2, z2, Color1, Color2;
    RealType t1, t2, *Coord1, *Coord2;
    IPVertexStruct *V;
    PolygonScanConvertStruct
	*PScan = (PolygonScanConvertStruct *) PPolygon -> PAux;

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

    if (PScan -> Bndry2.MaxEdgeY < Level) {
	V = PScan -> Bndry2.VMinY;
	PScan -> Bndry2.VMinY = PScan -> Bndry2.VMaxY;
	PScan -> Bndry2.VMaxY =
	    GetNeighborVrtx(PPolygon, PScan -> Bndry2.VMaxY, V);
	PScan -> Bndry2.MaxEdgeY =
	    (int) PScan -> 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 = PScan -> Bndry1.VMinY -> Coord;
    Coord2 = PScan -> 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 = PScan -> Bndry2.VMinY -> Coord;
    Coord2 = PScan -> 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 (GlblShadeInfo.Gouraud) {
	/* Need to interpolate the colors as well: */
	Color1 = (int) (PScan -> Bndry1.VMinY -> Color * t1 +
			PScan -> Bndry1.VMaxY -> Color * (1.0 - t1));
	Color2 = (int) (PScan -> Bndry2.VMinY -> Color * t2 +
			PScan -> 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, PScan -> Bndry1.VMinY -> Color,
				       PScan -> Bndry1.VMinY -> Color);
    }
}

/*****************************************************************************
* Returns the other neighbor of vertex V in polygon PPolygon which is not    *
* the neighbor NotV.							     *
*****************************************************************************/
static IPVertexStruct *GetNeighborVrtx(IPPolygonStruct *PPolygon,
				       IPVertexStruct *V, IPVertexStruct *NotV)
{
    int i;
    IPVertexStruct *List2,
	*List = PPolygon -> PVertex;

    /* Find index of vertex V. */
    for (i = 0; List != V; i++, List = List -> Pnext);

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

/*****************************************************************************
* 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;
    RealType 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 >= GlblShadeInfo.ScrnXSize) {
	/* Update upper limit to GlblShadeInfo.ScrnXSize - 1: */
	if (x2 == x1) return;
	t = (x2 - (GlblShadeInfo.ScrnXSize - 1)) / (x2 - x1);
	x2 = GlblShadeInfo.ScrnXSize - 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 (GlblShadeInfo.Gouraud) {
	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 (GlblShadeInfo.Gouraud) {
		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 (GlblShadeInfo.Gouraud) {
		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;
    IPPolygonStruct *PPolygon;

    for (i = 0; i < GlblShadeInfo.ScrnYSize; 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(IPPolygonStruct *PPolygon)
{
    int i;
    IPVertexStruct *VList = PPolygon -> PVertex;

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

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

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

#endif /* DEBUG */