/*****************************************************************************
*   Routines to	prepare objects for the scan conversion:		     *
* At this stage, it is assumed all vertices normals has been evaluated, if   *
* is is required to interpolate them (i.e. Gouraud shading.)		     *
* This module sort the polygons into hash table of ScreenYSize size,	     *
* according to their lowest vertex, and update a pointer to it.		     *
*									     *
* Written by:  Gershon Elber				Ver 2.0, Mar. 1990   *
*****************************************************************************/

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

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

static int PrepareAllObjects(FileDescription **FD);
static int VisitObjectTree(BinTree *PBinTree);
static void PrepareOneObject(ObjectStruct *PObject);
static void PrepareOnePolygon(PolygonStruct *PPolygon);
static VertexStruct *UpdateBBoxPolygon(PolygonStruct *PPolygon);
static void UpdateScanConvertData(VertexStruct *PMinY, PolygonStruct *PPolygon);

/*****************************************************************************
* Routine to prepare NumOfObjects given in Objects from FileDescription FD   *
* according to view matrix Mat. If NumOfObjects == 0 then all the objects    *
* defined by the data sturcture are handled, and NumOfObjects is set to real *
* number of objects exists.						     *
*****************************************************************************/
void PrepareViewData(FileDescription **FD, int *NumOfObjects, char **Objects)
{
    int	i;
    long SaveTime = time(NULL);
    struct ObjectStruct	*PObject;

    fprintf(stderr, "\nPass 2, Polys [%4d] =      ", NumOfPolygons);

    if (*NumOfObjects > 0)	   /* There was something on command line... */
	for (i=0; i<*NumOfObjects; i++) {
	    if ((PObject = SearchObject(FD, *Objects)) == NULL)
		fprintf(stderr,
		    "\n\nGiven Object %s not found in data files\n", *Objects);
	    else PrepareOneObject(PObject);
	    Objects++;
	}
    else {		    /* Prepare all objects by scanning object trees. */
	*NumOfObjects = PrepareAllObjects(FD);
    }

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

/*****************************************************************************
* Routine to search for	an object in the File descriptions FD. Note that if  *
* an object exists more	than once only the first will be returned. If none   *
* is found then	NULL is	returned, else a pointer to that object	struct.	     *
*****************************************************************************/
ObjectStruct *SearchObject(FileDescription **FD, char *Object)
{
    struct BinTree *PBinTree;

    while (*FD) {
	if ((PBinTree = GetBinTree(Object, (*FD++) -> ObjectPointer)) !=
							(BinTree *) NULL)
	    return PBinTree -> Data.PObject;
    }
    return (ObjectStruct *) NULL;
}

/*****************************************************************************
* Scan all objects.							     *
*****************************************************************************/
static int PrepareAllObjects(FileDescription **FD)
{
    int Num = 0;

    while (*FD)	Num += VisitObjectTree((*FD++) -> ObjectPointer);

    return Num;
}

/*****************************************************************************
* Scanning all the object in tree PBinTree and prepare them.		     *
*****************************************************************************/
static int VisitObjectTree(BinTree *PBinTree)
{
    int Num;

    if (PBinTree == (BinTree *)	NULL) return 0;

    Num = VisitObjectTree(PBinTree -> right);

    PrepareOneObject(PBinTree -> Data.PObject);

    Num += VisitObjectTree(PBinTree -> left);

    return Num + 1;
}

/*****************************************************************************
* Routine to prepare one object PObject.				     *
*****************************************************************************/
static void PrepareOneObject(ObjectStruct *PObject)
{
    struct PolygonStruct *Ptemp, *PList = PObject -> PPolygon;

    while (PList) {
	Ptemp = PList -> Pnext;

	PrepareOnePolygon(PList);

	PList =	Ptemp;
    }
}

/*****************************************************************************
* Routine to prepare one polygon PPolygon.				     *
*****************************************************************************/
static void PrepareOnePolygon(PolygonStruct *PPolygon)
{
    static PolyCount = 0;
    int	i;
    double CpCoord[3];
    struct VertexStruct *PList = PPolygon -> PVertex;

    fprintf(stderr, "\b\b\b\b\b%5d", ++PolyCount);

    while (PList) {
	/* Use the transform flag to specify number of references   */
	/* and if one allready trasnform it, dont do that again.    */
	if (++PList -> Transform > 1) break;

	/* Convert the coordinate to screen space (in double pres.). */
	MultVecby4by4(CpCoord, PList -> Coord, GlblViewMat);
	for (i=0; i<3; i++) PList -> Coord[i] = CpCoord[i];
	PList =	PList -> Pnext;
    }

    if (PPolygon -> Polyline) return;

    /* Find X, Y extremum in screen space, and use the lowest vertex in Y to */
    /* initialize the scan conversion structure of the polygon:		     */
    PList = UpdateBBoxPolygon(PPolygon);
    UpdateScanConvertData(PList, PPolygon);

    /* Transform the polygon plane equation as well, and normalize it: */
    UpdateEqnPolygon(PPolygon, FALSE);
}

/*****************************************************************************
* Routine to update polygon boundary box in screen space:		     *
* Note this routine is called after the	polygons was checked for validity -  *
* all the list of objects was found to be vertices only.		     *
*****************************************************************************/
static VertexStruct *UpdateBBoxPolygon(PolygonStruct *PPolygon)
{
    float *Coord, Xmin, Xmax, Ymin, Ymax;
    struct VertexStruct *PList = PPolygon -> PVertex, *PMinY;

    PMinY = PList;
    Xmin = Xmax = PList -> Coord[0];
    Ymin = Ymax = PList -> Coord[1];
    PList = PList -> Pnext;
    while (PList) {
	Coord = PList -> Coord;
	if (Coord[0] > Xmax) Xmax = Coord[0];
	if (Coord[0] < Xmin) Xmin = Coord[0];
	if (Coord[1] > Ymax) Ymax = Coord[1];
	if (Coord[1] < Ymin) {
	    Ymin = Coord[1];
	    PMinY = PList;
	}
	PList =	PList -> Pnext;
    }

    PPolygon -> Xmin = (int) Xmin;
    PPolygon -> Xmax = (int) Xmax;
    PPolygon -> Ymin = (int) Ymin;
    PPolygon -> Ymax = (int) Ymax;

    return PMinY;
}

/*****************************************************************************
* Routine to update polygon scan conversion information:		     *
* Each polygon (Remember they must be convex), has two boundaries we cross   *
* by the scan lines if it is active. These are LeftBndry and RightBndry we   *
* update here.								     *
*****************************************************************************/
static void UpdateScanConvertData(VertexStruct *PMinY, PolygonStruct *PPolygon)
{
    struct VertexStruct *PList = PPolygon -> PVertex,
	*VMinY, *VBefore, *VAfter;

    /* Find the minimum location again: */
    while (PList != PMinY && PList -> Pnext != PMinY)
	PList = PList -> Pnext;
    if (PList == PMinY) {
	/* Its the first vertex that has minimum Y value: */
	VMinY = PList;
	VAfter = PList -> Pnext;
	while (PList -> Pnext != NULL) PList = PList -> Pnext;
	VBefore = PList;
    }
    else {
	VMinY = PList -> Pnext;
	VBefore = PList;
	if (PList -> Pnext -> Pnext != NULL)
	     VAfter = PList -> Pnext -> Pnext;
	else VAfter = PPolygon -> PVertex;
    }

    PPolygon -> Bndry1.VMinY = VMinY;
    PPolygon -> Bndry1.VMaxY = VBefore;
    PPolygon -> Bndry1.MaxEdgeY = (int) VBefore -> Coord[1];

    PPolygon -> Bndry2.VMinY = VMinY;
    PPolygon -> Bndry2.VMaxY = VAfter;
    PPolygon -> Bndry2.MaxEdgeY = (int) VAfter -> Coord[1];
}