/*****************************************************************************
* Flat data structures creation and prerendering initialization.	     *
******************************************************************************
* (C) Gershon Elber, Technion, Israel Institute of Technology                *
******************************************************************************
* Written by:  Bassarab Dmitri & Plavnik Michael       Ver 0.2, Apr. 1995    *
*****************************************************************************/

#include "program.h"
#include "debug.h"

static int IsPolyBackfaced(IPPolygonStruct *Poly);
static int VertexGetUVAttrAux(IPVertexStruct *Vertex,
                              RealType *u,
                              RealType *v);
static int VertexHasUVAttrAux(IPObjectStruct *IPObject, ObjectStruct *PObject);
static void PolyAveragePoint(IPPolygonStruct *Poly, PointType p);
static FlatStruct *FlatCreate(IPPolygonStruct *Poly, ObjectStruct *o);
static ObjectStruct *ObjectCreate(IPObjectStruct *o);

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Determines if viewer sees the backface side of the polygon, uses plane   *
*   equation to obtain normal value.                                         *
*   Assumes that normal is directed into the object normaly and both viewer  *
*   and Plane equation are in object space.                                  *
*                                                                            *
* PARAMETERS:                                                                *
*   Poly:   Pointer to Irit polygon object.                                  *
*                                                                            *
* RETURN VALUE:                                                              *
*   int:    Boolean value, zero if viewer sees front side of the polygon.    *
*****************************************************************************/
static int IsPolyBackfaced(IPPolygonStruct *Poly)
{
    /* Assume that normal to the sphere is directed into sphere. */
    return IS_VIEWER_POINT() ?
        PLANE_EQ_EVAL(Poly -> Plane, Context.Viewer) > -IRIT_EPS :
        DOT_PROD(Poly -> Plane, Context.Viewer) > -IRIT_EPS;
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Retrievs "uuvals" attribute from the vertex object. Returns zero if      *
*   fails to return those attribute values.                                  *
*                                                                            *
* PARAMETERS:                                                                *
*   Vertex:  IN, pointer to the Irit vertex object.                          *
*   u:       OUT, pointer to result object U (1-st in the attr. string)      *
*   v:       OUT, pointer to result object V (2-nd in the attr.string)       *
*                                                                            *
* RETURN VALUE:                                                              *
*   int:    Boolean, zero if function fails to return proper values.         *
*****************************************************************************/
static int VertexGetUVAttrAux(IPVertexStruct *Vertex, RealType *u, RealType *v)
{
    char *uv;

    if ((uv = AttrGetStrAttrib(Vertex -> Attrs, "uvvals")) != NULL)
#ifdef IRIT_DOUBLE
        return sscanf(uv, "%lf %lf", u, v) == 2;
#else
        return sscanf(uv, "%f %f", u, v) == 2;
#endif /* IRIT_DOUBLE */
    return FALSE;
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Checks "uuvals" attribute presence in the vertices of object and their   *
*   validity. Side effect: computes parametric domain of object.             *
*                                                                            *
* PARAMETERS:                                                                *
*   IPObject: IN, pointer to the Irit object to be checked.                  *
*   PObject:  IN, OUT, pointer to object to be updated.                      *
*                                                                            *
* RETURN VALUE:                                                              *
*   int:    Boolean, zero if check fails                                     *
*****************************************************************************/
static int VertexHasUVAttrAux(IPObjectStruct *IPObject, ObjectStruct *PObject)
{
    IPPolygonStruct *Poly;
    IPVertexStruct *Vertex;
    RealType u, v;

    PObject -> text.uMin = PObject -> text.vMin =  IRIT_INFNTY;
    PObject -> text.uMax = PObject -> text.vMax = -IRIT_INFNTY;
    
    for (Poly = IPObject -> U.Pl; Poly; Poly = Poly -> Pnext)
        for (Vertex = Poly -> PVertex; Vertex != NULL; Vertex = Vertex -> Pnext)
            if (!VertexGetUVAttrAux(Vertex, &u, &v))
                return FALSE;
	    else {
	        MINM(PObject -> text.uMin, u);
	        MAXM(PObject -> text.uMax, u);
	        MINM(PObject -> text.vMin, v);
	        MAXM(PObject -> text.vMax, v);
	    }
    return TRUE;
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Computes average of the vertices points of the polygon object.           *
*                                                                            *
* PARAMETERS:                                                                *
*   Poly:    IN, pointer to the Irit polygon object.                         *
*   p:       OUT, result average point.                                      *
*                                                                            *
* RETURN VALUE:                                                              *
*   void                                                                     *
*****************************************************************************/
static void PolyAveragePoint(IPPolygonStruct *Poly, PointType p)
{
    IPVertexStruct *v;
    unsigned int
        NVertices = 0;

    PT_CLEAR(p);
    for (v = Poly -> PVertex; v; v = v -> Pnext, ++NVertices)
        PT_ADD(p, p, v -> Coord);
    PT_SCALE(p, 1.0 / NVertices);
    MatMultVecby4by4(p, p, Context.InvMat);
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Create a flat object and initialize it from polygon and object data.     *
*   That includes scan line and interpolation algorithm data initialization. *
*                                                                            *
* PARAMETERS:                                                                *
*   Poly:     IN, pointer to Irit polygon object.                            *
*   o:        IN, pointer to Object which contains a flat and stores various *
*             charactarisitics common to every polygon in the object.        *
*                                                                            *
* RETURN VALUE:                                                              *
*   FlatStruct *:  Flat object initalized for father processing or NULL if   *
*                  polygon is not suitable.                                  *
*****************************************************************************/
static FlatStruct *FlatCreate(IPPolygonStruct *Poly, ObjectStruct *o)
{
    int e, j,
	xMax = 0,
	xMin = 0;
    EdgeStruct *PEdge, First;
    IPVertexStruct *v;
    FlatStruct *f;
    PointType p;
    NormalType n;

    if (APX_EQ(Poly -> Plane[X], 0) && /* Do not create flat for the polygon */
        APX_EQ(Poly -> Plane[Y], 0) && /* with zero length normal.           */
        APX_EQ(Poly -> Plane[Z], 0))
        return NULL;

    if (Options.BackFace && IsPolyBackfaced(Poly))
        return NULL;                /* Skip back side polygons if user asks. */

    f = MALLOC(FlatStruct, 1);                           /* Allocate memory. */
    f -> object = o;                          /* Connect to container object */
    f -> poly = Poly;                          /* and to the source polygon. */

    /* Count edges and min-max dimensions for the polygon. */
    for (f -> nEdges = 0, v = Poly -> PVertex; v != NULL; v = v -> Pnext) {
        if (++f -> nEdges == 1) {
	    xMin = xMax = REAL_TO_INT(v -> Coord[X]);
            f -> yMin = f -> yMax = REAL_TO_INT(v -> Coord[Y]);
	}
        MINM(f -> yMin, REAL_TO_INT(v -> Coord[Y]));
        MAXM(f -> yMax, REAL_TO_INT(v -> Coord[Y]));
	MINM(xMin, REAL_TO_INT(v -> Coord[X]));
	MAXM(xMax, REAL_TO_INT(v -> Coord[X]));
    }
    if (f -> nEdges < 3) {          /* We have no deal with lines or points. */
        FREE(f);
        return NULL;
    }
    /* We have no deal with flats out of image rectangle. */
    if ((f -> yMax <= 0) ||
	(f -> yMin >= Options.YSize) ||
	(xMax <= 0) ||
	(xMin >= Options.XSize)) { 
        FREE(f);
        return NULL;
    }
    
    MAXM(f -> yMin, 0);    /* Flat actually starts not below zero scan line. */
    
    /* Do not forget to update global characteristics. */
    MAXM(Context.MaxEdges, f -> nEdges);

    /* In FLAT model we evalute everything with respect to the average point.*/
    if (Options.ShadeModel == FLAT) {
        PolyAveragePoint(f -> poly, p);
        PT_COPY(n, Poly -> Plane);
        PT_NORMALIZE(n);
    }
    f -> edge = MALLOC(EdgeStruct, f -> nEdges);

    /* Obtain and initialize Flat's vertices current(inital) characteristics */
    /* which are scan line algorithm values, and interpolants such as normal,*/
    /* intensivity, homogeneous coordinate...				     */
    for (v = Poly -> PVertex, e = 0; e < f -> nEdges; e++, v = v -> Pnext) {
        PEdge = &f -> edge[e];
        PEdge -> x = REAL_TO_INT(v -> Coord[X]);
        PEdge -> yMin = REAL_TO_INT(v -> Coord[Y]);
        PEdge -> value.z = v -> Coord[Z];
        PEdge -> value.w = AttrGetRealAttrib(v -> Attrs, "_1/W");
        if (o -> text.type == TEXTURE_TYPE_RSTR ||
	    o -> text.type == TEXTURE_TYPE_SRF) {
            VertexGetUVAttrAux(v, &PEdge -> value.u, &PEdge -> value.v);
	    PEdge -> value.u = (PEdge -> value.u - o -> text.uMin) /
					    (o -> text.uMax - o -> text.uMin);
	    PEdge -> value.v = (PEdge -> value.v - o -> text.vMin) /
					    (o -> text.vMax - o -> text.vMin);
            PEdge -> value.u *= PEdge -> value.w;
            PEdge -> value.v *= PEdge -> value.w;
        }
        PT_COPY(PEdge -> value.n, v -> Normal);
        PT_SCALE(PEdge -> value.n, PEdge -> value.w);
        switch (Options.ShadeModel) {
            case GOURAUD:
                PEdge -> value.i = MALLOC(IntensivityStruct, Context.Lights.n);
                PEdge -> dValue.i = MALLOC(IntensivityStruct, Context.Lights.n);
                for (j = 0; j < Context.Lights.n; ++j) {
                    MatMultVecby4by4(p, v -> Coord, Context.InvMat);
                    LightIntensivity(p,
				     v -> Normal,
				     &Context.Lights.src[j],
				     o,
				     &PEdge -> value.i[j]);
                    PEdge -> value.i[j].diff *= PEdge -> value.w;
                    PEdge -> value.i[j].spec *= PEdge -> value.w;
                }
                break;
            case FLAT:
                PEdge -> value.i = MALLOC(IntensivityStruct, Context.Lights.n);
                PEdge -> dValue.i = NULL;
                for (j = 0; j < Context.Lights.n; ++j)
                    LightIntensivity(p,
				     n,
				     &Context.Lights.src[j],
				     o,
				     &PEdge -> value.i[j]);
                break;
            default:
                PEdge -> value.i = PEdge -> dValue.i = NULL;
        }
    }

    /* Create and initalize interpolation values data structure. */
    First = f -> edge[0];
    First.value.i = (Options.ShadeModel != PHONG) ?
                         MALLOC(IntensivityStruct, Context.Lights.n) : NULL;
    InterpolCopy(&First.value, &f -> edge -> value);
    for (e = 0; e < f -> nEdges; ++e) {
        RealType dy;
        EdgeStruct *Next;

        PEdge = &f -> edge[e];
        Next = (e + 1 == f -> nEdges) ? &First : PEdge + 1;
        dy = PEdge -> dy = Next -> yMin - PEdge -> yMin;
        InterpolDelta(&PEdge -> dValue, &Next -> value, &PEdge -> value, dy);
        if (PEdge -> dy < 0) {
            PEdge -> dx = PEdge -> x - Next -> x;
            PEdge -> x = Next -> x;
            PEdge -> yMin = Next -> yMin;
            InterpolCopy(&PEdge -> value, &Next -> value);
        }
	else
            PEdge -> dx = Next -> x - PEdge -> x;
        PEdge -> inc = PEdge -> dy = ABS(PEdge -> dy);

	/* Increment edge to start from 0 scan line. */
	if (PEdge -> yMin < 0) {
	    int y,
	        yMax = MIN(0, PEdge -> yMin + PEdge -> dy);
	    
	    for (y = PEdge -> yMin; y < yMax; ++y) 
	         PolyEdgeIncr(PEdge);
	}
    }
    return f;
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Creates Object and initialize different attributes from the Irit Object: *
*   color, specularity, transparancy, texture image, volumetric texture.     *
*                                                                            *
* PARAMETERS:                                                                *
*   o:       IN, pointer to the Irit object, containing necessary attributes *
*                                                                            *
* RETURN VALUE:                                                              *
*   ObjectStruct *: created object                                           *
*****************************************************************************/
static ObjectStruct *ObjectCreate(IPObjectStruct *o)
{
    IPObjectStruct *PSrf;
    ObjectStruct
	*PObject = MALLOC(ObjectStruct, 1);
    int r, g, b;
    char *p;

    if (Options.ZDepth) {
        PObject -> text.type = TEXTURE_TYPE_NONE;
        PObject -> text.image = NULL;
        PObject -> text.srf = NULL;
        return PObject;
    }

    /* Initialize object's color attribute. */
    if (AttrGetObjectRGBColor(o, &r, &g, &b)) {
        PObject -> color[R] = r;
        PObject -> color[G] = g;
        PObject -> color[B] = b;
        PT_SCALE(PObject -> color, 1. / 0xff);
    }
    else
        PT_COPY(PObject -> color, Colors[AttrGetObjectColor(o)]);

    PObject -> noShade
        = AttrGetObjectIntAttrib(o, "_NO_SHADE") != IP_ATTR_BAD_INT; 
    
    /* Initialize object's specularity attribute. */
    PObject -> power = AttrGetObjectIntAttrib(o, "SRF_COSINE");
    if (PObject -> power == IP_ATTR_BAD_INT)
        PObject -> power = COSINE_DEFAULT;

    PObject -> text.type = TEXTURE_TYPE_NONE;

    /* Initialize object's texture image attribute. */
    if ((p = AttrGetObjectStrAttrib(o, "PTEXTURE")) != NULL) {
        PObject -> text.type = TEXTURE_TYPE_RSTR;
        if ((PObject -> text.image = ImageLoadImage(p)) == NULL) {
	    fprintf(stderr,
		    "Error: undefined texture image \"%s\"\n", p);
	    exit(1);
	}
	VertexHasUVAttrAux(o, PObject);     /* Update the UV Min Max bounds. */
    }
    else
        PObject -> text.image = NULL;

    /* Initialize object's surface texture attribute. */
    if ((PSrf = AttrGetObjectObjAttrib(o, "STEXTURE")) != NULL &&
	IP_IS_SRF_OBJ(PSrf)) {
	double Min, Max;

        PObject -> text.type = TEXTURE_TYPE_SRF;
        PObject -> text.srf = PSrf -> U.Srfs;

	VertexHasUVAttrAux(o, PObject);     /* Update the UV Min Max bounds. */

	CagdSrfDomain(PObject -> text.srf,
		      &PObject -> text.srfParamDomain[0][0],
		      &PObject -> text.srfParamDomain[0][1],
		      &PObject -> text.srfParamDomain[1][0],
		      &PObject -> text.srfParamDomain[1][1]);
	PObject -> text.srfParamDomain[0][2] =
	    PObject -> text.srfParamDomain[0][1] -
	        PObject -> text.srfParamDomain[0][0];
	PObject -> text.srfParamDomain[1][2] =
	    PObject -> text.srfParamDomain[1][1] -
	        PObject -> text.srfParamDomain[1][0];

	if ((p = AttrGetObjectStrAttrib(o, "STEXTURE_BOUND")) != NULL &&
	    (sscanf(p, "%lf %lf", &Min, &Max) == 2 ||
	     sscanf(p, "%lf,%lf", &Min, &Max) == 2)) {
	    PObject -> text.srfScaleMinMax[0] = Min;
	    PObject -> text.srfScaleMinMax[1] = Max;
	}
	else {
	    CagdBBoxStruct BBox;

	    if (p != NULL)
		fprintf(stderr, "Warning: wrong TEXTURE_BOUND format\n");

	    CagdSrfBBox(PObject -> text.srf, &BBox);

	    PObject -> text.srfScaleMinMax[0] = BBox.Min[0];
	    PObject -> text.srfScaleMinMax[1] = BBox.Max[0];
	}

	PObject -> text.srfFunc = STEXTURE_FUNC_NONE;
	if ((p = AttrGetObjectStrAttrib(o, "STEXTURE_FUNC")) != NULL) {
	    if (stricmp(p, "sqrt") == 0)
	        PObject -> text.srfFunc = STEXTURE_FUNC_SQRT;
	    else if (stricmp(p, "abs") == 0)
	        PObject -> text.srfFunc = STEXTURE_FUNC_ABS;
	    else
	        fprintf(stderr,
			"Warning: undefined STEXTURE function \"%s\"\n", p);
	}

	if ((p = AttrGetObjectStrAttrib(o, "STEXTURE_SCALE")) != NULL)
	    PObject -> text.srfScale = ImageLoadImage(p);
	else
	    PObject -> text.srfScale = NULL;
    }
    else
        PObject -> text.srf = NULL;

    /* Initialize object's volumetric texture attribute. */
    if ((p = AttrGetObjectStrAttrib(o, "TEXTURE")) != NULL) {
        char
	    *tString = p;
        char tName[0xff];
        ProcTextureStruct *t;

        PObject -> text.tScale[0] =
	    PObject -> text.tScale[1] =
	        PObject -> text.tScale[2] = 1;
#ifdef IRIT_DOUBLE
	if (sscanf(tString, "%[^,], %lf %lf %lf",
#else
	if (sscanf(tString, "%[^,], %f %f %f",
#endif /* IRIT_DOUBLE */
		   tName, &PObject -> text.tScale[0],
		          &PObject -> text.tScale[1],
		          &PObject -> text.tScale[2]) == 4) {
	    for (t = ProcTextures;
		 t -> name && stricmp(t -> name, tName);
		 t++);
	    if (!(PObject -> text.vTexture = t -> vTexture))
	        fprintf(stderr, "Warning: unknown texture \"%s\"\n", tName);
	    else
	        PObject -> text.type = TEXTURE_TYPE_PROC;
	}
#ifdef IRIT_DOUBLE
	else if (sscanf(tString, "%[^,], %lf",
#else
        else if (sscanf(tString, "%[^,], %f",
#endif /* IRIT_DOUBLE */
			tName, &PObject -> text.tScale[0]) == 2) {
	    PObject -> text.tScale[1] = PObject -> text.tScale[0];
	    PObject -> text.tScale[2] = PObject -> text.tScale[0];
	    for (t = ProcTextures;
		 t -> name && stricmp(t -> name, tName);
		 t++);
	    if (!(PObject -> text.vTexture = t -> vTexture))
	        fprintf(stderr, "Warning: unknown texture \"%s\"\n", tName);
	    else
	        PObject -> text.type = TEXTURE_TYPE_PROC;
	}
	else {
	    PObject -> text.vTexture = NULL;
	    fprintf(stderr, "Warning: wrong TEXTURE format\n");
        }

	if ((p = AttrGetObjectStrAttrib(o, "TEXTURE_COLOR")) != NULL) {
	    int Clr[3];

	    if (sscanf(p, "%d,%d,%d", &Clr[0], &Clr[1], &Clr[2]) != 3 &&
	        sscanf(p, "%d %d %d", &Clr[0], &Clr[1], &Clr[2]) != 3) {
	        fprintf(stderr, "Warning: RGB expected in TEXTURE_COLOR attribute\n");
		PObject -> text.Color.r =
		    PObject -> text.Color.g =
			PObject -> text.Color.b = 255;
	    }
	    else {
		PObject -> text.Color.r = Clr[0];
		PObject -> text.Color.g = Clr[1];
		PObject -> text.Color.b = Clr[2];
	    }
	}
	else {
	    PObject -> text.Color.r =
		PObject -> text.Color.g =
		    PObject -> text.Color.b = 255;
	}

	if ((p = AttrGetObjectStrAttrib(o, "TEXTURE_WIDTH")) != NULL) {
#ifdef IRIT_DOUBLE
	    if (sscanf(p, "%lf",
#else
	    if (sscanf(p, "%f",
#endif /* IRIT_DOUBLE */
		       &PObject -> text.Width) != 1) {
	        fprintf(stderr, "Warning: Width expected in TEXTURE_WIDTH attribute\n");
		PObject -> text.Width = 0.1;
	    }
	}
	else {
	    PObject -> text.Width = 0.1;
	}
    }
    else
        PObject -> text.vTexture = NULL;

    /* Initialize object's transparency attribute. */
    if (Options.Transp) {
        PObject -> transp = AttrGetObjectRealAttrib(o, "TRANSP");
        if (!IN(PObject -> transp, 0.0, 1.0)) {
            if (PObject -> transp < IP_ATTR_BAD_REAL)
                fprintf(stderr, "Warning: transparency out of range, set to default\n");
            PObject -> transp = TRANSP_DEFAULT;
        }
    }
    return PObject;
}

/*****************************************************************************
* DESCRIPTION:                                                               M
*   For each polygon in all objects creates linked list of container Flat    M
*   objects and Object objects.                                              M
*                                                                            *
* PARAMETERS:                                                                M
*   Objects:    IN, linked list of Irit objects.                             M
*                                                                            *
* RETURN VALUE:                                                              M
*   FlatStruct *:    doubly linked list of Flat objects.                     M
*                                                                            M
* KEYWORDS:                                                                  M
*   GatherFlats, flat                                                        M
*****************************************************************************/
FlatStruct *GatherFlats(IPObjectStruct *Objects)
{
    FlatStruct *f,
	*PFlat = NULL;

    GATHERING_FLATS_MESSAGE();

    for (; Objects; Objects = Objects -> Pnext)
        if (IP_IS_POLY_OBJ(Objects) && !IP_IS_POLYLINE_OBJ(Objects)) {
            IPPolygonStruct *Poly;
            ObjectStruct
		*o = ObjectCreate(Objects);

            for (Poly = Objects -> U.Pl; Poly; Poly = Poly -> Pnext)
                if ((f = FlatCreate(Poly, o)) != NULL) {
                    f -> next = PFlat;
                    PFlat = f;
                }
        }

    if (Context.MaxEdges == 0) {
	fprintf(stderr,
		"Error: Failed to find geometry in input data, aborting\n");
	exit(2);
    }

    return PFlat;
}

/*****************************************************************************
* DESCRIPTION:                                                               M
*   Creates bucket array, where every entry (one for each scan line) is a    M
*   header of the doubly linked list of the Flat objects starting (having    M
*   minimal Y coordinate) at that scan line (list is circular!).             M
*                                                                            *
* PARAMETERS:                                                                M
*   PFlat:   IN OUT, linked list of Flat objects.                            M
*                                                                            *
* RETURN VALUE:                                                              M
*   FlatStruct *: array of buckets.                                          M
*                                                                            *
* KEYWORDS:                                                                  M
*   BucketSortFlats, scan line, flat                                         M
*****************************************************************************/
FlatStruct *BucketSortFlats(FlatStruct *PFlat)
{
    FlatStruct
	*Slot = MALLOC(FlatStruct, Options.YSize);
    int y;

    SORTING_MESSAGE();

    /* Initialize every slot to be an empty circular doubly linked list. */
    for (y = 0; y < Options.YSize; y++)
        Slot[y].prev = Slot[y].next = &Slot[y];
                                             
    while (PFlat) {                         /* Bucket sort Flat linked list. */
        FlatStruct
	    *f = PFlat;

        PFlat = PFlat -> next;
        f -> next = Slot[y = f -> yMin].next;
        f -> next -> prev = f;
        f -> prev = &Slot[y];
        Slot[y].next = f;
    }
    return Slot;
}