/* interp.c */

/*
 * Mesa 3-D graphics library
 * Version:  1.2
 * Copyright (C) 1995  Brian Paul  (brianp@ssec.wisc.edu)
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the Free
 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */


/*
$Id: interp.c,v 1.7 1995/10/23 21:27:54 brianp Exp $

$Log: interp.c,v $
 * Revision 1.7  1995/10/23  21:27:54  brianp
 * new GLubyte interpolation using fixed point arithmetic
 *
 * Revision 1.6  1995/06/12  15:43:57  brianp
 * separate GLint and GLubyte interpolation functions
 *
 * Revision 1.5  1995/06/02  13:58:36  brianp
 * faster gl_interpolate(), tried gl_interpolate_rgba()
 *
 * Revision 1.4  1995/05/22  21:02:41  brianp
 * Release 1.2
 *
 * Revision 1.3  1995/03/17  19:15:21  brianp
 * tried to improve gl_interp_texcoords, not much luck
 *
 * Revision 1.2  1995/03/04  19:29:44  brianp
 * 1.1 beta revision
 *
 * Revision 1.1  1995/02/27  22:20:13  brianp
 * Initial revision
 *
 */


#include "context.h"
#include "macros.h"


/*#define TEST*/


/*
 * Linear integer interpolation:
 * Iterpolate n integer values between y0 and y1 and put into yspan.
 * When finished, yspan[0] = y0, yspan[n-1] = y1, and the rest of
 * yspan[] is filled with interpolated values.
 */
void gl_interpolate_i( GLint n, GLint y0, GLint y1, GLint yspan[] )
{
   switch (n) {
      case 1:
         yspan[0] = y0;
	 return;
      case 2:
         yspan[0] = y0;
         yspan[1] = y1;
	 return;
      case 3:
         yspan[0] = y0;
	 yspan[1] = (y0+y1) >> 1;
         yspan[2] = y1;
	 return;
      default:
	 if (y0==y1) {
	    register GLint i;
	    for (i=0;i<n;i++) {
	       yspan[i] = y0;
	    }
	 }
	 else {
	    register GLint i;
	    register GLint dx, dy;
	    register GLint a, b, d;
	    register GLint y;
	    register GLint qa, qb;
   	    dx = n-1;
	    dy = y1 - y0;
	    qa = dy / dx;
	    dy = dy % dx;
	    if (dy<0) {
	       dy = -dy;
	       qb = qa - 1;
	    }
	    else {
	       qb = qa + 1;
	    }
	    a = dy+dy;   d = a-dx;   b = d-dx;
	    y = y0;
	    for (i=0;i<n;i++) {
	       yspan[i] = y;
	       if (d<0) {
		  d += a;
		  y += qa;
	       }
	       else {
		  d += b;
		  y += qb;
	       }
	    }
	 }
   }
}




void gl_interpolate_ub( GLint n, GLint y0, GLint y1, GLubyte yspan[] )
{
   int i, dy;

   switch (n) {
      case 1:
         yspan[0] = y0;
         return;
      case 2:
         yspan[0] = y0;
         yspan[1] = y1;
         return;
      case 3:
         yspan[0] = y0;
         yspan[1] = (y0+y1) >> 2;
         yspan[2] = y1;
         return;
      default:
         y0 = y0 << 8;
         y1 = y1 << 8;
         dy = (y1-y0) / (n-1);
         for (i=0;i<n;i++) {
            yspan[i] = y0 >> 8;
            y0 += dy;
         }
         return;
   }
}



void gl_interpolate_4ub( GLint n,
                         GLint a0, GLint a1, GLubyte aspan[],
                         GLint b0, GLint b1, GLubyte bspan[],
                         GLint c0, GLint c1, GLubyte cspan[],
                         GLint d0, GLint d1, GLubyte dspan[] )
{
   GLint i, m;
   GLint da, db, dc, dd;

   switch (n) {
      case 1:
         aspan[0] = a0;
         bspan[0] = b0;
         cspan[0] = c0;
         dspan[0] = d0;
	 return;
      case 2:
         aspan[0] = a0;   aspan[1] = a1;
         bspan[0] = b0;   bspan[1] = b1;
         cspan[0] = c0;   cspan[1] = c1;
         dspan[0] = d0;   dspan[1] = d1;
	 return;
      case 3:
         aspan[0] = a0;   aspan[1] = (a0+a1)>>2;   aspan[2] = a1;
         bspan[0] = b0;   bspan[1] = (b0+b1)>>2;   bspan[2] = b1;
         cspan[0] = c0;   cspan[1] = (c0+c1)>>2;   cspan[2] = c1;
         dspan[0] = d0;   dspan[1] = (d0+d1)>>2;   dspan[2] = d1;
         return;
      default:
         a0 = a0 << 8;
         b0 = b0 << 8;
         c0 = c0 << 8;
         d0 = d0 << 8;
         m = n-1;
         da = ((a1<<8)-a0) / m;
         db = ((b1<<8)-b0) / m;
         dc = ((c1<<8)-c0) / m;
         dd = ((d1<<8)-d0) / m;
         for (i=0;i<n;i++) {
            aspan[i] = a0 >> 8;    a0 += da;
            bspan[i] = b0 >> 8;    b0 += db;
            cspan[i] = c0 >> 8;    c0 += dc;
            dspan[i] = d0 >> 8;    d0 += dd;
         }
         return;
   }
}




#ifndef TEST

/*
 * Perform texture coordinate interpolation along a line in window coord-
 * inate space.  Depending on the perspective correction hint we'll either
 * just do simple linear interpolation or interpolation with perspective
 * correction.
 * Input:  n - number of texture coords to produce
 *         eyez0, eyez1 - z coordinate of end points in eye coords
 *         winz0  winz1 - z coordinate of end points in window coords
 *         s0, s1 - S-component of texture coords at end points
 *         t0, t1 - T-component of texture coords at end points
 * Output:  s, t - resulting arrays of S and T texture coordinates
 *          z - interpolated Z component of eye coordinates along the line
 *              (note that z can be a NULL pointer if z isn't needed)
 */
void gl_interp_texcoords( GLuint n,
			  GLfloat eyez0, GLfloat eyez1,
			  GLfloat winz0, GLfloat winz1,
			  GLfloat s0, GLfloat s1,
			  GLfloat t0, GLfloat t1,
			  GLfloat s[], GLfloat t[], GLfloat *z )
{
   /* TODO: the main loop in this function could be optimized with */
   /* forward differences, etc.  However, since texture mapping is */
   /* so expensive, optimizing this might not make a big difference. */

   /* TODO: this function has a terrible problem with numerical error */
   /* under certain conditions, namely when interpolating along a vector */
   /* which is _nearly_ parallel to the viewplane. */

   GLfloat d = CC.ProjectionMatrix[14];
   GLfloat c = CC.ProjectionMatrix[10];
   GLfloat delta_eyez = eyez1 - eyez0;
   GLfloat delta_winz = winz1 - winz0;
   GLfloat delta_s = s1 - s0;
   GLfloat delta_t = t1 - t0;
   GLuint i;

   if (n==1) {
      s[0] = s0;
      t[0] = t0;
      if (z)  z[0] = eyez0;
      return;
   }

   if (CC.Hint.PerspectiveCorrection==GL_NICEST && d!=0.0
       && ABS(delta_eyez)>0.001) {
      /* interpolate with perspective compensation */
      GLfloat q, r, winz, ndcz, eyez;

      for (i=0;i<n;i++) {
	 q = (GLfloat) i / (n-1);
	 winz = (winz0 + q * delta_winz) / (GLfloat) MAX_DEPTH;

	 ndcz = (winz - CC.Viewport.Tz) / CC.Viewport.Sz;

	 eyez = -d / (c+ndcz);

	 r = (eyez - eyez0) / delta_eyez;
	 r = CLAMP( r, 0.0, 1.0 );    /* to catch over/underflow */

	 s[i] = s0 + r * delta_s;
	 t[i] = t0 + r * delta_t;
	 if (z) {
	    z[i] = eyez;
	 }
      }
   }
   else {
      /* simple linear interpolation */
      if (z) {
	 for (i=0;i<n;i++) {
	    GLfloat q = (GLfloat) i / (n-1);
	    s[i] = s0 + q * delta_s;
	    t[i] = t0 + q * delta_t;
	    z[i] = eyez0 + q * delta_eyez;
	 }
      }
      else {
	 for (i=0;i<n;i++) {
	    GLfloat q = (GLfloat) i / (n-1);
	    s[i] = s0 + q * delta_s;
	    t[i] = t0 + q * delta_t;
	 }
      }
   }
}

#endif


#ifdef TEST
static void foo( int n, int red[], int green[], int blue[], int alpha[] )
{

}



#define ITER 700
#define MAX 500

#include "interp.h"

main()
{
   int i, j, n, jj;

   for (i=0;i<ITER;i++) {
      int red[MAX], green[MAX], blue[MAX], alpha[MAX];
      jj = MAX2( 2, i );
      for (j=0;j<jj;j++) {
	 n = j/4+1;

	 GL_INTERPOLATE( n, j, n, red );
	 GL_INTERPOLATE( n, j+3, j*8, green );
	 GL_INTERPOLATE( n, i, j+i*2, blue );
	 GL_INTERPOLATE( n, i, i, alpha );
/*	 gl_interpolate_rgba( n, j, n, red,
	                         j+3, j*8, green,
                                 i, j+i*2, blue,
                                 i, i, alpha );
*/
      }
      foo( n, red, green, blue, alpha );
   }

}

#endif