// Copyright (C) 1996 Keith Whitwell.
// This file may only be copied under the terms of the GNU Library General
// Public License - see the file COPYING in the lib3d distribution.


#include "VpNew.H"
#include <Lib3d/Viewport.H>
#include <Lib3d/Texture.H>
#include <Lib3d/ColourRamp.H>
#include <math.h>


// Only works correctly for +ve fixedpoint numbers.
//
inline int Ceil( int Value ) {
    return (Value + UNITY - 1) >> LOG_UNITY;
}

inline void FloorDivMod(int numerator, 
			int denominator, 
			int &floor,
			int &mod )
{
    if (numerator >= 0) {
        floor = numerator / denominator;
        mod = numerator % denominator;
    } else {
        floor = -((-numerator) / denominator);
        mod = (-numerator) % denominator;
        if (mod) {
            floor--; 
	    mod = denominator - mod;
        }
    }
}

inline
edge_major_texture::edge_major_texture(TexturePipelineData * const vertex[], 
				       int Top,
				       int Bottom )
    : incr(1)
{
    float dw_dy;            
    float duw_dy;           
    float dvw_dy;           
    int  dz_dy;            

    // twice the area of the triangle.
    // 
    area = (((vertex[1]->device.v[0] - vertex[2]->device.v[0]) *
	     (vertex[0]->device.v[1] - vertex[2]->device.v[1])) -
	    ((vertex[0]->device.v[0] - vertex[2]->device.v[0]) *
	     (vertex[1]->device.v[1] - vertex[2]->device.v[1])));

    if (area <= 0) {
        return;
    }

    float delta = float(UNITY) / float(area);

    int t1 = (vertex[0]->device.v[1] - vertex[2]->device.v[1]);
    int t2 = (vertex[1]->device.v[1] - vertex[2]->device.v[1]);
    int t3 = (vertex[0]->device.v[0] - vertex[2]->device.v[0]);
    int t4 = (vertex[1]->device.v[0] - vertex[2]->device.v[0]);

    yMin = Ceil(vertex[Top]->device.v[1]);
    int dN = vertex[Bottom]->device.v[1] - vertex[Top]->device.v[1];
    if (!dN) return;
    int dM = vertex[Bottom]->device.v[0] - vertex[Top]->device.v[0];
    
    int Tmp = 
        dM*(UNITY*yMin - vertex[Top]->device.v[1]) +
        dN*(vertex[Top]->device.v[0] + UNITY) - 1;

    denominator = dN*UNITY;
    FloorDivMod(Tmp,denominator,x,error);
    FloorDivMod(dM*UNITY,denominator,xStep,numerator);
    error -= denominator;
    
    dw_dx = delta * (((vertex[1]->w - vertex[2]->w) * t1) -
		     ((vertex[0]->w - vertex[2]->w) * t2));
    dw_dy = delta * (((vertex[0]->w - vertex[2]->w) * t4) -
		     ((vertex[1]->w - vertex[2]->w) * t3));
    
    float yPrestep = _UNITY * (yMin * UNITY - vertex[Top]->device.v[1]);
    float xPrestep = _UNITY * (x * UNITY - vertex[Top]->device.v[0]);
    
    w = vertex[Top]->w + yPrestep * dw_dy + xPrestep * dw_dx;
    wStep = xStep * dw_dx + dw_dy;
    wStepExtra = dw_dx;
    
    duw_dx = delta * (((vertex[1]->uw - vertex[2]->uw) * t1) -
		      ((vertex[0]->uw - vertex[2]->uw) * t2));
    duw_dy = delta * (((vertex[0]->uw - vertex[2]->uw) * t4) -
		      ((vertex[1]->uw - vertex[2]->uw) * t3));

    uw = vertex[Top]->uw + yPrestep * duw_dy + xPrestep * duw_dx;
    uwStep = xStep * duw_dx + duw_dy;
    uwStepExtra = duw_dx;
    
    dvw_dx = delta * (((vertex[1]->vw - vertex[2]->vw) * t1) -
		      ((vertex[0]->vw - vertex[2]->vw) * t2));
    dvw_dy = delta * (((vertex[0]->vw - vertex[2]->vw) * t4) -
		      ((vertex[1]->vw - vertex[2]->vw) * t3));

    vw = vertex[Top]->vw + yPrestep * dvw_dy + xPrestep * dvw_dx;
    vwStep = xStep * dvw_dx + dvw_dy;
    vwStepExtra = dvw_dx;

    dz_dx = int(delta * 
                ((float(vertex[1]->device.v[Z]- vertex[2]->device.v[Z]) * t1) -
                 (float(vertex[0]->device.v[Z]- vertex[2]->device.v[Z]) * t2)));
    dz_dy = int(delta * 
                ((float(vertex[0]->device.v[Z]- vertex[2]->device.v[Z]) * t4) -
		 (float(vertex[1]->device.v[Z]- vertex[2]->device.v[Z]) * t3)));
    
    z = uint(vertex[Top]->device.v[Z] + yPrestep * dz_dy + xPrestep * dz_dx);
    zStep = xStep * dz_dx + dz_dy;
    zStepExtra = dz_dx;
}

inline
edge_major_flat::edge_major_flat(PipelineData * const vertex[],
				 int Top, int Mid, int Bottom)
    : incr(1)
{
    yMin = Ceil(vertex[Top]->device.v[1]);
    int dN = vertex[Bottom]->device.v[1] - vertex[Top]->device.v[1];
    if (!dN) return;

    int dM = vertex[Bottom]->device.v[0] - vertex[Top]->device.v[0];
   
    // This is a bit of a hack - a straight integer calculation is fine until
    // the triangles start to get a little larger, when 
    // (dM = (width*UNITY))*UNITY*UNITY > 2^31.  Reworking as
    // (dM*UNITY/dN)*UNITY looses presiscion and the edges start to cross,
    // which our main loop doesn't tolerate.  So we do a floating point 
    // divide...
    
    xStep = int((dM*float(UNITY*UNITY))/dN);
    
    int t = xStep >> LOG_UNITY;
    x = (t*yMin*UNITY) - 
	(t*vertex[Top]->device.v[1]) +
	((vertex[Top]->device.v[0] + UNITY) * UNITY) - 1;

    z = vertex[Top]->device.v[Z];
    zStep = 0;
    dz_dx = 0;

    int height =  (Ceil(vertex[Bottom]->device.v[Y]) - yMin);
    if (!height) return;
    int height1 = (Ceil(vertex[Mid]->device.v[Y]) - yMin);
    int dz = vertex[Bottom]->device.v[Z] - vertex[Top]->device.v[Z];
    int xi = vertex[Top]->device.v[X] + ((xStep * height1)>>LOG_UNITY);
    int xspan = (vertex[Mid]->device.v[X] - xi) >> LOG_UNITY;
    if (!xspan) return;
    zStep = ((dz<<7) / height)>>7;
    int zi = vertex[Top]->device.v[Z] + (zStep * height1);
    dz_dx = (((vertex[Mid]->device.v[Z] - zi)<<7) / xspan)>>7;
}

#if 1
inline
edge_major_smooth::edge_major_smooth(SmoothPipelineData * const vertex[], 
				     int Top,
				     int,
				     int Bottom )
    : incr(1)
{
    int  dz_dy;            
    int  di_dy;            

    // twice the area of the triangle.
    // 
    area = (((vertex[1]->device.v[0] - vertex[2]->device.v[0]) *
	     (vertex[0]->device.v[1] - vertex[2]->device.v[1])) -
	    ((vertex[0]->device.v[0] - vertex[2]->device.v[0]) *
	     (vertex[1]->device.v[1] - vertex[2]->device.v[1])));

    if (area <= 0) {
        return;
    }

    float delta = float(UNITY) / float(area);

    int t1 = (vertex[0]->device.v[1] - vertex[2]->device.v[1]);
    int t2 = (vertex[1]->device.v[1] - vertex[2]->device.v[1]);
    int t3 = (vertex[0]->device.v[0] - vertex[2]->device.v[0]);
    int t4 = (vertex[1]->device.v[0] - vertex[2]->device.v[0]);

    yMin = Ceil(vertex[Top]->device.v[1]);
    int dN = vertex[Bottom]->device.v[1] - vertex[Top]->device.v[1];
    if (!dN) return;
    int dM = vertex[Bottom]->device.v[0] - vertex[Top]->device.v[0];
    
    int Tmp = 
        dM*(UNITY*yMin - vertex[Top]->device.v[1]) +
        dN*(vertex[Top]->device.v[0] + UNITY) - 1;

    denominator = dN*UNITY;
    FloorDivMod(Tmp,denominator,x,error);
    FloorDivMod(dM*UNITY,denominator,xStep,numerator);
    error -= denominator;
    
    di_dx = int(delta * (((vertex[1]->intensity- vertex[2]->intensity) * t1) -
			 ((vertex[0]->intensity- vertex[2]->intensity) * t2)));
    di_dy = int(delta * (((vertex[0]->intensity- vertex[2]->intensity) * t4) -
			 ((vertex[1]->intensity- vertex[2]->intensity) * t3)));

    float yPrestep = _UNITY * (yMin * UNITY - vertex[Top]->device.v[1]);
    float xPrestep = _UNITY * (x * UNITY - vertex[Top]->device.v[0]);

    i = int(vertex[Top]->intensity + yPrestep * di_dy + xPrestep * di_dx);
    iStep = xStep * di_dx + di_dy;
    iStepExtra = di_dx;

    dz_dx = int(delta * 
                ((float(vertex[1]->device.v[Z]- vertex[2]->device.v[Z]) * t1) -
                 (float(vertex[0]->device.v[Z]- vertex[2]->device.v[Z]) * t2)));
    dz_dy = int(delta * 
                ((float(vertex[0]->device.v[Z]- vertex[2]->device.v[Z]) * t4) -
		 (float(vertex[1]->device.v[Z]- vertex[2]->device.v[Z]) * t3)));
    
    z = uint(vertex[Top]->device.v[Z] + yPrestep * dz_dy + xPrestep * dz_dx);
    zStep = xStep * dz_dx + dz_dy;
    zStepExtra = dz_dx;
}
#else
inline
edge_major_smooth::edge_major_smooth(SmoothPipelineData * const vertex[],
				     int Top, int Mid, int Bottom)
    : incr(1)
{
    area = (((vertex[1]->device.v[0] - vertex[2]->device.v[0]) *
	     (vertex[0]->device.v[1] - vertex[2]->device.v[1])) -
	    ((vertex[0]->device.v[0] - vertex[2]->device.v[0]) *
	     (vertex[1]->device.v[1] - vertex[2]->device.v[1])));

    if (area <= 0) {
        return;
    }

    yMin = Ceil(vertex[Top]->device.v[1]);
    int dN = vertex[Bottom]->device.v[1] - vertex[Top]->device.v[1];
    if (!dN) return;

    int dM = vertex[Bottom]->device.v[0] - vertex[Top]->device.v[0];
   
    xStep = int((dM*float(UNITY*UNITY))/dN);
    
    int t = xStep >> LOG_UNITY;
    x = (t*yMin*UNITY) - 
	(t*vertex[Top]->device.v[1]) +
	((vertex[Top]->device.v[0] + UNITY) * UNITY) - 1;

    z = vertex[Top]->device.v[Z];
    i = vertex[Top]->intensity;
    iStep = 0;
    di_dx = 0;
    zStep = 0;
    dz_dx = 0;

    float yPrestep = _UNITY * (yMin * UNITY - vertex[Top]->device.v[1]);
    float xPrestep = _UNITY * ((x>>LOG_UNITY) - vertex[Top]->device.v[0]);


    int di_dy, dz_dy;

    float delta = float(UNITY) / float(area);

    int t1 = (vertex[0]->device.v[1] - vertex[2]->device.v[1]);
    int t2 = (vertex[1]->device.v[1] - vertex[2]->device.v[1]);
    int t3 = (vertex[0]->device.v[0] - vertex[2]->device.v[0]);
    int t4 = (vertex[1]->device.v[0] - vertex[2]->device.v[0]);

    di_dx = int(delta * (((vertex[1]->intensity - vertex[2]->intensity) * t1) -
			 ((vertex[0]->intensity - vertex[2]->intensity) * t2)));
    di_dy = int(delta * float(UNITY) *
		(((vertex[0]->intensity - vertex[2]->intensity) * t4) -
		 ((vertex[1]->intensity - vertex[2]->intensity) * t3)));

    i = vertex[Top]->intensity;
    if (area > (1<<18)) {
    }
	i += (int(yPrestep * di_dy)>>LOG_UNITY) + int(xPrestep * di_dx) ; 
    iStep = (t * di_dx + di_dy) >> LOG_UNITY;

    /*
    if (i > (1<<16) || i < 0) {
	printf("%d ", i); 
	printf("itop: %d imid: %d ibot: %d\n",
	       vertex[Top]->intensity,
	       vertex[Mid]->intensity,
	       vertex[Bottom]->intensity);
	printf("i: %d iStep: %d  di_dx:%d\n", i, iStep, di_dx);
	printf("area: %d\n", area);
    }
    */

    dz_dx = int(delta * 
                ((float(vertex[1]->device.v[Z]- vertex[2]->device.v[Z]) * t1) -
                 (float(vertex[0]->device.v[Z]- vertex[2]->device.v[Z]) * t2)));
    dz_dy = int(delta * float(UNITY) *
                ((float(vertex[0]->device.v[Z]- vertex[2]->device.v[Z]) * t4) -
		 (float(vertex[1]->device.v[Z]- vertex[2]->device.v[Z]) * t3)));
    z = uint(vertex[Top]->device.v[Z]); // + yPrestep * dz_dy + xPrestep * dz_dx);
    zStep = (t * dz_dx + dz_dy) >> LOG_UNITY;
    //zStepExtra = dz_dx;
}
#endif


inline
edge_minor::edge_minor(const PipelineData &top, 
                       const PipelineData &bottom)
{
    int y = Ceil(top.device.v[1]);
    height = Ceil(bottom.device.v[1]) - y;
    
    if (height) {
        int dN = bottom.device.v[1] - top.device.v[1];
        int dM = bottom.device.v[0] - top.device.v[0];
        
	/*
         * The integer version runs out of precision on larger triangles...
         */
        xStep = int((dM*float(UNITY*UNITY))/dN);

        int t = xStep >> LOG_UNITY;
        x = (t* (y*UNITY - top.device.v[1])) +
            ((top.device.v[0] + UNITY) * UNITY) - 1;
    }
}


inline
edge_minor_step::edge_minor_step(const PipelineData &top, 
				 const PipelineData &bottom)
{
    int y = Ceil(top.device.v[1]);
    height = Ceil(bottom.device.v[1]) - y;
    
    if (height) {
        int dN = bottom.device.v[1] - top.device.v[1];
        int dM = bottom.device.v[0] - top.device.v[0];
    
	int tmp = 
	    dM*(UNITY*y - top.device.v[1]) +
	    dN*(top.device.v[0] + UNITY) - 1;

	denominator = dN*UNITY;
	FloorDivMod(tmp,denominator,x,error);
	FloorDivMod(dM*UNITY,denominator,xStep,numerator);
	error -= denominator;
    }
}


inline void 
edge_major_texture::invert()
{
    vw += (dvw_dx = - dvw_dx);
    uw += (duw_dx = - duw_dx);
    w += (dw_dx = - dw_dx);
    z += (dz_dx = - dz_dx);
    x--;
    incr = -1;
}


inline void 
edge_major_flat::invert()
{
    z += (dz_dx = - dz_dx);
    x -= (UNITY*UNITY);
    incr = -1;
}


inline void 
edge_major_smooth::invert()
{
    z += (dz_dx = - dz_dx);
    i += (di_dx = - di_dx);
    x--;
    incr = -1;
}

inline void 
edge_minor::invert()
{
    x -= (UNITY*UNITY);
}

inline void 
edge_minor_step::invert()
{
    x--;
}


inline void sortVertices(PipelineData *const vertex[],
			  int &top, int &middle, int &bottom,
			  int &type)
{
    int y0 = vertex[0]->device.v[Y];
    int y1 = vertex[1]->device.v[Y];
    int y2 = vertex[2]->device.v[Y];

    if (y0 < y1) {
        if (y2 < y0) {
            top = 2; 
            middle = 0; 
            bottom = 1;
            type = 1;
        } else {
            top = 0;
            if (y1 < y2) {
                middle = 1; 
                bottom = 2;
                type = 1;
            } else {
                middle = 2; 
                bottom = 1;
                type = 0;
            }
        }
    } else {
        if (y2 < y1) {
            top = 2; 
            middle = 1; 
            bottom = 0;
            type = 0;
        } else {
            top = 1;
            if (y0 < y2) {
                middle = 0; 
                bottom = 2;
                type = 0;
            } else {
                middle = 2; 
                bottom = 0;
                type = 1;
            }
        }
    }
}


VpNew::VpNew( Device *device )
    : Viewport( device, UNITY, UNITY )
{
}

VpNew::~VpNew()
{
}

void
VpNew::textureTriangleZb(TexturePipelineData * const vertex[], 
                       const Texture &texture)
{
    int top, middle, bottom;
    int type;
    
    sortVertices((PipelineData *const[])vertex, top, middle, bottom, type);

    edge_major_texture maj(vertex,top,bottom);
    if (maj.area <= 0) return;

    edge_minor_step minor1(*vertex[top],    *vertex[middle]);
    edge_minor_step minor2(*vertex[middle], *vertex[bottom]);

    if (type == 1) {
        maj.invert();
	minor1.invert();
	minor2.invert();
    } 
    
    doTextureTriangleZb(maj, minor1, minor2, texture);
}


void
VpNew::flatTriangleZb(PipelineData * const vertex[], Colour colour)
{
    int top, middle, bottom;
    int type;

    sortVertices((PipelineData *const[])vertex, top, middle, bottom, type);

    edge_major_flat maj(vertex,top,middle,bottom);
    edge_minor minor1(*vertex[top],    *vertex[middle]);
    edge_minor minor2(*vertex[middle], *vertex[bottom]);

    if (type == 1) {
	maj.invert();
	minor1.invert();
	minor2.invert();
    } 


    doFlatTriangleZb(maj, minor1, minor2, colour);
}

void
VpNew::smoothTriangleZb(SmoothPipelineData *const vertex[], 
		      const ColourRamp &ramp )
{
    int top, middle, bottom;
    int type;

    sortVertices((PipelineData *const[])vertex, top, middle, bottom, type);

    edge_major_smooth maj(vertex,top,middle,bottom);

    if (maj.area <= 0) return;
    //if (maj.area > 800000) return;

    edge_minor_step minor1(*vertex[top],    *vertex[middle]);
    edge_minor_step minor2(*vertex[middle], *vertex[bottom]);


    if (type == 1) {
	maj.invert();
	minor1.invert();
	minor2.invert();
    } 


    doSmoothTriangleZb(maj, minor1, minor2, ramp);
}

void 
VpNew::flatPolygonZb(uint nr, 
		   PipelineData * const vertex[], 
		   Colour colour )
{
    if (nr == 3) {
	VpNew::flatTriangleZb( vertex, colour );
    } else {
	PipelineData *a[3];
	
	a[0] = vertex[0];
	a[1] = vertex[1];
	a[2] = vertex[2];
    
	for (uint i = 3 ; i <= nr ; i++ ) {
	    VpNew::flatTriangleZb( a, colour );
	    a[1] = a[2];
	    a[2] = vertex[i];
	}
    }
}

void 
VpNew::smoothPolygonZb(uint nr, 
		     SmoothPipelineData * const vertex[], 
		     const ColourRamp& ramp )
{
    if (nr == 3) {
	VpNew::smoothTriangleZb( vertex, ramp );
    } else {
	SmoothPipelineData *a[3];
	
	a[0] = vertex[0];
	a[1] = vertex[1];
	a[2] = vertex[2];
    
	for (uint i = 3 ; i <= nr ; i++ ) {
	    VpNew::smoothTriangleZb( a, ramp );
	    a[1] = a[2];
	    a[2] = vertex[i];
	}
    }
}


void 
VpNew::texturePolygonZb(uint nr, 
		      TexturePipelineData * const vertex[], 
		      const Texture &texture )
{
    if (nr == 3) {
	VpNew::textureTriangleZb( vertex, texture );
    } else {
	TexturePipelineData *a[3];
	
	a[0] = vertex[0];
	a[1] = vertex[1];
	a[2] = vertex[2];
    
	for (uint i = 3 ; i <= nr ; i++ ) {
	    VpNew::textureTriangleZb( a, texture );
	    a[1] = a[2];
	    a[2] = vertex[i];
	}
    }
}


void 
VpNew::setDirty( int xmin, int ymin, int xmax, int ymax )
{
    int xn = Ceil(xmin);
    int yn = Ceil(ymin);
    int xx = Ceil(xmax);
    int yx = Ceil(ymax);

    // device->setDirty(0,0,319,199);
    // zBuffer->setDirty(0,0,319,199);

    device->setDirty(xn, yn, xx, yx);
    zBuffer->setDirty(xn, yn, xx, yx);
}