/*****************************************************************************
* Performs polygon scan-converting and applies different rendering effects.  *
******************************************************************************
* (C) Gershon Elber, Technion, Israel Institute of Technology                *
******************************************************************************
* Written by:  Bassarab Dmitri & Plavnik Michael       Ver 0.2, Apr. 1995    *
*****************************************************************************/

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

static int  PolyEdgeCmp(const void *Arg1, const void *Arg2);
static void PutScanLine(int y, ZSlotStruct * z);
static void InsertScanLinePoint(ZSlotStruct *z, InterpolStruct *i,
				FlatStruct *f);

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Increments all interpolation values and coordinate of intersection       *
*   with respect to the next scan line.                                      *
*                                                                            *
* PARAMETERS:                                                                *
*   PEdge:    IN, pointer to the polygon edge on the current scan-line       *
*                                                                            *
* RETURN VALUE:                                                              *
*   void                                                                     *
*****************************************************************************/
void PolyEdgeIncr(EdgeStruct *PEdge)
{
    int Sign = SIGN(PEdge -> dx),
        Numerator = abs(PEdge -> dx),
        Denumerator = PEdge -> dy;

    InterpolIncr(&PEdge -> value, &PEdge -> dValue);

    if (Numerator < Denumerator) {                          /* Slope is > 1. */
        PEdge -> inc += Numerator;
    }
    else {
        PEdge -> x += PEdge -> dx / Denumerator;
        PEdge -> inc += Numerator % Denumerator;
    }
    if (PEdge -> inc > Denumerator) {
        PEdge -> x += Sign;
        PEdge -> inc -= Denumerator;
    }
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Compares X coordinates of two edges.                                     *
*                                                                            *
* PARAMETERS:                                                                *
*   Arg1:     IN, pointer to the first edge.                                 *
*   Arg2:     IN, pointer to the second edge.                                *
*                                                                            *
* RETURN VALUE:                                                              *
*   int:     -1 if X coordinate of the first edge is smaller,                *
*             0 if equal                                                     *
*             1 if greater                                                   *
*****************************************************************************/
static int PolyEdgeCmp(const void *Arg1, const void *Arg2)
{
    return ((CrossStruct *) Arg1) -> x - ((CrossStruct *) Arg2) -> x;
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Transforms data in the current scan line data structure to image         *
*   sound data and passes it to the antialias filter.                        *
*                                                                            *
* PARAMETERS:                                                                *
*   y:       IN, current scan line index.                                    *
*   z:       IN OUT, array representing current scan line data for each X.   *
*                                                                            *
* RETURN VALUE:                                                              *
*   void                                                                     *
*****************************************************************************/
static void PutScanLine(int y, ZSlotStruct *z)
{
    int x;
    ColorType c;
    ZPointStruct *p;
    RealType t;

    if (!Options.ZDepth)
        for (x = 0; x < Options.XSize; x++) {
            PT_CLEAR(z[x].color);
            for (p = z[x].opaque;; p = p -> next) {
                if (p -> flat) {
                    ColorEval(x, y, p, c);
                    if (!Options.Transp) {
                        PT_COPY(z[x].color, c);
                    }
		    else {
                        t = p -> flat -> object -> transp;
                        z[x].color[R] = (1 - t) * c[R] + t * z[x].color[R];
                        z[x].color[G] = (1 - t) * c[G] + t * z[x].color[G];
                        z[x].color[B] = (1 - t) * c[B] + t * z[x].color[B];
                    }
                }
		else {
                    PT_COPY(z[x].color, Options.BackGround);
                }
                if (p == z[x].tail)
                    break;
            }
        }
    AntialiasLine(z);
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   For a polygon point on the current scan line, allocates and inserts into *
*   sorted list data structure element describing it. It is used when trans- *
*   parancy mode is on to store information about all polygons owning the    *
*   same point on the scan line.                                             *
* PARAMETERS:                                                                *
*   z:       IN OUT, pointer to the current point of the scan line.          *
*   i:       IN, interpolation values for the current point.                 *
*   f:       IN, pointer to the polygon owning the currrent point.           *
*                                                                            *
* RETURN VALUE:                                                              *
*   void                                                                     *
*****************************************************************************/
static void InsertScanLinePoint(ZSlotStruct *z, InterpolStruct *i,
				FlatStruct *f)
{
    ZPointStruct *New,
	*p = z -> opaque;

    if (!(i -> z NEAR_THAN p -> value.z))
        return;
    
    for (; (p != z -> tail) && (i -> z NEAR_THAN p -> next -> value.z);
	 p = p -> next);

    if (!z -> tail -> next) {
        New = MALLOC(ZPointStruct, 1);
        if (Options.ShadeModel != PHONG)
            New -> value.i = MALLOC(IntensivityStruct, Context.Lights.n);
    }
    else {
        New = z -> tail -> next;
        z -> tail -> next = New -> next;
    }

    New -> next = p -> next;
    p -> next = New;
    InterpolCopy(&New -> value, i);
    New -> flat = f;

    if (p == z -> tail)
        z -> tail = New;

    if (APX_EQ(f -> object -> transp, 0.))
        z -> opaque = New;
}

/*****************************************************************************
* DESCRIPTION:                                                               M
*   Renderers all scan lines and applys shading model and shadows as reques- M
*   ted. Directs output to the scan line output routine.                     M
*                                                                            *
* PARAMETERS:                                                                M
*   Slot:    IN, pointer to the array of bucket sorted linked list of flats  *
*                                                                            *
* RETURN VALUE:                                                              M
*   void                                                                     M
*                                                                            *
* KEYWORDS:                                                                  M
*   Shader, rendering, scan line                                             M
*****************************************************************************/
void Shader(FlatStruct *Slot)
{
    int x, y, nCross, i;
    EdgeStruct *e;
    CrossStruct
	*Crosses = MALLOC(CrossStruct, Context.MaxEdges);
    ZSlotStruct
	*z = MALLOC(ZSlotStruct, Options.XSize);
    FlatStruct *f, CurSlot;
    InterpolStruct d;

    RENDERING_MESSAGE();

    CurSlot.next = CurSlot.prev = &CurSlot;
    d.i = (Options.ShadeModel == GOURAUD) ?
              MALLOC(IntensivityStruct, Context.Lights.n) :NULL;
    if (Options.ShadeModel != PHONG) {
        for (i = 0; i < Context.MaxEdges; ++i)
            Crosses[i].value.i = MALLOC(IntensivityStruct, Context.Lights.n);
        for (x = 0; x < Options.XSize; ++x)
            z[x].bg.value.i = MALLOC(IntensivityStruct, Context.Lights.n);
    }
    for (x = 0; x < Options.XSize; ++x) {
        z[x].opaque = z[x].tail = &z[x].bg;
        z[x].bg.next = NULL;
        z[x].bg.flat = NULL;
        z[x].bg.value.z = FURTHEST_Z;
    }
    for (y = 0; y < Options.YSize; ++y) {
        if (!Options.Transp)
            for (x = 0; x < Options.XSize; ++x) {
                z[x].bg.value.z = FURTHEST_Z;
                z[x].bg.flat = NULL;
        }
	else
            for (x = 0; x < Options.XSize; ++x)
                z[x].opaque = z[x].tail = &z[x].bg;
        if (Slot[y].next != &Slot[y]) {
            Slot[y].next -> prev = &CurSlot;
            Slot[y].prev -> next = CurSlot.next;
            CurSlot.next -> prev = Slot[y].prev;
            CurSlot.next = Slot[y].next;
        }
        for (f = CurSlot.next; f != &CurSlot; f = f -> next) {
            for (e = f -> edge, nCross = 0;
		 e < (EdgeCPtrType) (f -> edge + f -> nEdges);
		 ++e)
                if (IN(y, e -> yMin, e -> yMin + e -> dy - 1)) {
		    /* [ .. ) rule in Y direction. */
                    Crosses[nCross].x = e -> x;
                    InterpolCopy(&Crosses[nCross++].value, &e -> value);
                    PolyEdgeIncr(e);
                }
            qsort(Crosses, nCross, sizeof(CrossStruct), PolyEdgeCmp);
            for (i = 0; i < nCross; i += 2) {
                RealType
		    dx = (RealType) (Crosses[i + 1].x - Crosses[i].x);

                InterpolDelta(&d, &Crosses[i + 1].value, &Crosses[i].value, dx);
                for (x = Crosses[i].x; x < Crosses[i + 1].x; ++x) {
		    if (IN(x, 0, Options.XSize - 1)) {   /* Inside of image. */
                        if (Options.Transp)
                            InsertScanLinePoint(&z[x], &Crosses[i].value, f);
                        else
		            if (Crosses[i].value.z NEAR_THAN z[x].bg.value.z) {
                                InterpolCopy(&z[x].bg.value, &Crosses[i].value);
                                z[x].bg.flat = f;
			    }
		    }
  		    /* Interpolate inspite of x coordinate can be outside. */
                    InterpolIncr(&Crosses[i].value, &d); 
                }
            }
        }
        if (Options.Shadows)
            for (f = CurSlot.next; f != &CurSlot; f = f -> next)
                ShadowLineInit(f, y);
        PutScanLine(y, z);
        for (f = CurSlot.next; f != &CurSlot; f = f -> next)
            if (f -> yMax == y + 1) {
                f -> prev -> next = f -> next;
                f -> next -> prev = f -> prev;
            }
	    else {
                if (Options.Shadows)
                    ShadowLineIncr(f, y + 1);
            }

    }
    FINAL_MESSAGE();
}