/*;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;  Real 2 SuperReal 3D engine   (Z sorted Gourand)                      ;
;                                                                       ;
;	Z                                                               ;
;	|                                                               ;
;	|                                                               ;
;	|                                                               ;
;	|                                                               ;
;	|______ X                                                       ;
;       /                                                               ;
;      /                                                                ;
;     /                                                                 ;
;    /                                                                  ;
;   Y                                                                   ;
;                                                                       ;
;  calc_normals((char *)&prism1_data);                                  ;
;  paint_world((char *)&prism1_data);                                   ;
;                                                                       ;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;*/
#define TW 640


extern "C" long sine(long value);
extern "C" long cose(long value);
extern "C" long sqrt(long value);
extern "C" void write_line(long addr,long x_len,long Crun,long Crun_grad);

/*;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;                                                                       ;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;*/
struct tvector
{
  long x;
  long y;
  long z;
};

struct ttrifacet
{
  char colour;
  tvector p1;
  tvector p2;
  tvector p3;
  tvector n1;
  tvector n2;
  tvector n3;
  tvector mean;
};

#define SCREEN_X      640
#define SCREEN_Y      480

#define X_WINDOW_SIZE 640
#define Y_WINDOW_SIZE 480

long poly_l_clip = 0;
long poly_r_clip = X_WINDOW_SIZE;
long poly_t_clip = 0;
long poly_b_clip = Y_WINDOW_SIZE;

struct tg3d_info
{
  long NO_OF_SIDES;
  tvector lightsource;
  tvector vangles;
  long scale;
  long xpos;
  long ypos;
};

tg3d_info *g3d_info;

/*;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;                                                                       ;
; Blitter component stuff                                               ;
;                                                                       ;
; some of this code is based on dave stampe 91 code                     ;
;                                                                       ;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;*/
long old_l_incr_t,old_r_incr_t,old_cl_incr_t,old_cr_incr_t;

struct tGvector
{
  long c;
  long x;
  long y;
};

#define HOLD_OFF      0
#define HOLD_LEFT     1
#define HOLD_RIGHT    2

long compute_XYslope(tGvector P1, tGvector P2)
{
  long slope = ((P2.x - P1.x) << 16) / (P2.y - P1.y);
  return slope;
}

long compute_Zgrad(long z1, long z2, long run)
{
  long slope = ((z2 - z1) << 16) / run;
  return slope;
}

/*;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;                                                        ;
;WITH Z Clipping (Gourand shaded)                        ;
;                                                        ;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;*/
void GZ_trapezoid(long x1,long x2,long l_incr,long r_incr,
                  long y1,long y3,
                  long c1,long c2,long cl_incr,long cr_incr,
                  long hold,long screen_width)
{
  long line,vline,zline,height,l_incr_t,r_incr_t,xl,xr,
       cl_incr_t,cr_incr_t,cl,cr;

  height = y3 - y1;
  if(hold == HOLD_OFF)
  {
    l_incr_t = x1 << 16;
    r_incr_t = x2 << 16;

    cl_incr_t = c1 << 16;
    cr_incr_t = c2 << 16;

  }
  else
  {
    if(hold == HOLD_LEFT)
    {
      l_incr_t = old_l_incr_t;
      r_incr_t = x2 << 16;

      cl_incr_t = old_cl_incr_t;
      cr_incr_t = c2 << 16;
    }
    else
    {
      r_incr_t = old_r_incr_t;
      l_incr_t = x1 << 16;

      cr_incr_t = old_cr_incr_t;
      cl_incr_t = c1 << 16;
    }
  }

  if(y3 < poly_t_clip)
  {
    old_l_incr_t = l_incr_t += l_incr * height;
    old_r_incr_t = r_incr_t += r_incr * height;

    old_cl_incr_t = cl_incr_t += cl_incr * height;
    old_cr_incr_t = cr_incr_t += cr_incr * height;
    return;
  }

  if(y1 < poly_t_clip)
  {
    long t_clip_d = poly_t_clip - y1;
    height -= t_clip_d;
    vline = poly_t_clip;
    l_incr_t += l_incr * t_clip_d;
    r_incr_t += r_incr * t_clip_d;

    cl_incr_t += cl_incr * t_clip_d;
    cr_incr_t += cr_incr * t_clip_d;
  }
  else
  {
    vline = y1;
  }
  vline = vline * SCREEN_X;

  if(y3 > poly_b_clip)
  {
    height -= y3 - poly_b_clip;
  }

  for(line = 0;line < height; line++)
  {
    xl = l_incr_t >> 16;
    xr = r_incr_t >> 16;

    cl = cl_incr_t >> 16;
    cr = cr_incr_t >> 16;

    if(xr > poly_l_clip)
    {
      if(xl < poly_r_clip)
      {
        if(xl < poly_l_clip)
        {
          xl = poly_l_clip;
        }
        if(xr > poly_r_clip)
        {
          xr = poly_r_clip;
        }

        long Crun = cl_incr_t;
        long x_diff = xr - xl + 2;
        long Crun_grad = 0;
        if(x_diff)
        {
          Crun_grad = compute_Zgrad(cl,cr,x_diff);
        }

        write_line(vline+xl,xr - xl,Crun,Crun_grad);
      }
    }

    vline += screen_width;
    l_incr_t += l_incr;
    r_incr_t += r_incr;

    cl_incr_t += cl_incr;
    cr_incr_t += cr_incr;
 }
  old_l_incr_t = l_incr_t;
  old_r_incr_t = r_incr_t;

  old_cl_incr_t = cl_incr_t;
  old_cr_incr_t = cr_incr_t;
}

/*;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;                                              ;
; 3-SIDED POLYGON DRAW AND FILL                ;
;                                              ;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;*/
void Gourand_poly3(tGvector P1,tGvector P2,tGvector P3)
{
  register long i;
  tGvector temp_v;
  long s12,s23,s13,cs12,cs23,cs13;
  long h_temp;
  i = poly_r_clip;
  if(!( P1.x<=i || P2.x<=i || P3.x<=i )) return;
  i = poly_l_clip;
  if(!( P1.x>=i || P2.x>=i || P3.x>=i )) return;
  i = poly_b_clip;
  if(!( P1.y<=i || P2.y<=i || P3.y<=i )) return;
  i = poly_t_clip;
  if(!( P1.y>=i || P2.y>=i || P3.y>=i )) return;
  if(P2.y<P1.y) /* sort by vert pos'n */
  {
    temp_v = P1;
    P1 = P2;
    P2 = temp_v;
  }
  if(P3.y<P1.y)
  {
    temp_v = P1;
    P1 = P3;
    P3 = temp_v;
  }
  if(P3.y<P2.y)
  {
    temp_v = P2;
    P2 = P3;
    P3 = temp_v;
  }
  if(P3.y<poly_t_clip || P1.y>poly_b_clip) return; /* all above or below clip area */
  if(P1.y==P2.y&&P2.y==P3.y) return;
  if(P1.y==P2.y) /* case = 2 (flat top) */
  {
    if(P2.x<P1.x)
    {
      temp_v = P1;
      P1 = P2;
      P2 = temp_v;
    }
    s13 = compute_XYslope(P1,P3);
    s23 = compute_XYslope(P2,P3);

    h_temp = P3.y - P1.y;
    cs13 = compute_Zgrad(P1.c,P3.c,h_temp);
    cs23 = compute_Zgrad(P2.c,P3.c,h_temp);

    GZ_trapezoid(P1.x,P2.x,s13,s23,
                 P1.y,P3.y,
                 P1.c,P2.c,cs13,cs23,
                 HOLD_OFF,TW);
  }
  else if(P2.y==P3.y) /* case = 1 (flat bottom)*/
  {
    if(P3.x<P2.x)
    {
      temp_v = P2;
      P2 = P3;
      P3 = temp_v;
    }
    s12 = compute_XYslope(P1,P2);
    s13 = compute_XYslope(P1,P3);

    h_temp = P3.y - P1.y;

    cs12 = compute_Zgrad(P1.c,P2.c,h_temp);
    cs13 = compute_Zgrad(P1.c,P3.c,h_temp);

    GZ_trapezoid(P1.x,P1.x,s12,s13,
                 P1.y,P3.y,
                 P1.c,P1.c,cs12,cs13,
                 HOLD_OFF,TW);
  }
  else
  {
    s12 = compute_XYslope(P1,P2);
    s13 = compute_XYslope(P1,P3);
    s23 = compute_XYslope(P2,P3);

    cs12 = compute_Zgrad(P1.c,P2.c,(P2.y - P1.y));
    cs13 = compute_Zgrad(P1.c,P3.c,(P3.y - P1.y));
    cs23 = compute_Zgrad(P2.c,P3.c,(P3.y - P2.y));
    if(s12 > s13) /* case = 4 (3rd point on right) */
    {
      GZ_trapezoid(P1.x,P1.x,s13,s12,
                   P1.y,P2.y,
                   P1.c,P1.c,cs13,cs12,
                   HOLD_OFF,TW);
      GZ_trapezoid(  -1,P2.x,s13,s23,
                   P2.y,P3.y,
                     -1,P2.c,cs13,cs23,
                   HOLD_LEFT,TW);
    }
    else        /* case = 3 (3rd point on left)  */
    {
      GZ_trapezoid(P1.x,P1.x,s12,s13,
                   P1.y,P2.y,
                   P1.c,P1.c,cs12,cs13,
                   HOLD_OFF,TW);
      GZ_trapezoid(P2.x,  -1,s23,s13,
                   P2.y,P3.y,
                   P2.c,  -1,cs23,cs13,
                   HOLD_RIGHT,TW);
    }
  }
}

/*;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;                                                                       ;
; coorindator                                                           ;
;                                                                       ;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;*/
struct tfacet_sort {
  char *index;
  long Z_average;
};

struct ttranstrifacet
{
  tGvector p1;
  tGvector p2;
  tGvector p3;
};

tfacet_sort *facet_sort;
ttranstrifacet *transformed;
tvector n_lightsource;

#define ROTATE_SF 9
void rotate(tvector S, tvector A, tvector *R)
{
  long Xt,Yt,Zt;
  Yt = ((S.y * cose(A.x)) >> ROTATE_SF) - ((S.z * sine(A.x)) >> ROTATE_SF);
  Zt = ((S.y * sine(A.x)) >> ROTATE_SF) + ((S.z * cose(A.x)) >> ROTATE_SF);
  Xt = ((S.x * cose(A.y)) >> ROTATE_SF) - ((Zt * sine(A.y)) >> ROTATE_SF);
  R->z = ((S.x * sine(A.y)) >> ROTATE_SF) + ((Zt * cose(A.y)) >> ROTATE_SF);
  R->x = ((Xt * cose(A.z)) >> ROTATE_SF)  - ((Yt * sine(A.z)) >> ROTATE_SF);
  R->y = ((Xt * sine(A.z)) >> ROTATE_SF)  + ((Yt * cose(A.z)) >> ROTATE_SF);
}

void project(tvector S, long scale, long *x, long *y)
{
  long fy;
  fy = S.y+scale;
  if(fy != 0)
  {
    *x = ((S.x << 8) / fy) + g3d_info->xpos;
    *y = ((S.z << 8) / fy) + g3d_info->ypos;
  }
  else
  {
    *x = S.x + g3d_info->xpos;
    *y = S.z + g3d_info->ypos;
  }
}

tvector calc_vertnormal(tvector vertice)
{
  tvector normal;
  long length = sqrt(vertice.x * vertice.x +
                     vertice.y * vertice.y +
                     vertice.z * vertice.z);
  normal.x = (vertice.x << 7) / length;
  normal.y = (vertice.y << 7) / length;
  normal.z = (vertice.z << 7) / length;
  return normal;
}

extern "C" void calc_normals(char *data_ptr,tg3d_info *info_ptr)
{
  int facet_no;
  ttrifacet *tridata;

  g3d_info = info_ptr;
  tridata = (ttrifacet *)data_ptr;

  for(facet_no = 0;facet_no < g3d_info->NO_OF_SIDES;facet_no++)
  {
    tridata->n1 = calc_vertnormal(tridata->p1);
    tridata->n2 = calc_vertnormal(tridata->p2);
    tridata->n3 = calc_vertnormal(tridata->p3);
    tridata++;

    if((!tridata->mean.x) && (!tridata->mean.y) && (!tridata->mean.z))
    {
      tridata->mean.x = (tridata->p1.x +
                         tridata->p2.x +
                         tridata->p3.x) >> 1;

      tridata->mean.y = (tridata->p1.y +
                         tridata->p2.y +
                         tridata->p3.y) >> 1;

      tridata->mean.z = (tridata->p1.z +
                         tridata->p2.z +
                         tridata->p3.z) >> 1;
    }
  }
  n_lightsource = calc_vertnormal(g3d_info->lightsource);
}

char threed_pal_base;
char threed_pal_size;

long calc_colour(tvector nvectice,tvector nlightsource,long base_colour)
{
  long dotproduct = (((nvectice.x * nlightsource.x) +
                      (nvectice.y * nlightsource.y) +
	              (nvectice.z * nlightsource.z)) >> 8);
  if(dotproduct < 0) dotproduct = 0;
  if(dotproduct > (threed_pal_size - 1)) dotproduct = (threed_pal_size - 1);
  return threed_pal_base + (base_colour * threed_pal_size) + dotproduct;
}

/*;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;                                                                       ;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;*/
void qsort(long l, long r)
{
  long i, j, x;
  tfacet_sort y;

  i = l;
  j = r;
  x = (facet_sort[(l + r) >> 1].Z_average);
  do
  {
    while(facet_sort[i].Z_average < x) i++;
    while(x < facet_sort[j].Z_average) j--;
    if(i <= j)
    {
      y = facet_sort[i];
      facet_sort[i] = facet_sort[j];
      facet_sort[j] = y;
      i++;
      j--;
    }
  } while (i <= j);
  if(l < j) qsort(l, j);
  if(i < r) qsort(i, r);
}

/*;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;                                                                       ;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;*/
extern "C" void paint_world(char *data_ptr,tg3d_info *info_ptr)
{
  int facet_no;
  ttrifacet *tridata;
  ttranstrifacet *tridata2;
  tvector vrotated;

  g3d_info = info_ptr;
  tridata = (ttrifacet *)data_ptr;
  tridata2 = (ttranstrifacet *)transformed;

  for(facet_no = 0;facet_no < g3d_info->NO_OF_SIDES;facet_no++)
  {
    facet_sort[facet_no].index = (char *)tridata2;

    rotate(tridata->mean,g3d_info->vangles,&vrotated);
    facet_sort[facet_no].Z_average = vrotated.y;

    rotate(tridata->p1,g3d_info->vangles,&vrotated);
    project(vrotated,g3d_info->scale,&tridata2->p1.x,&tridata2->p1.y);
    rotate(tridata->n1,g3d_info->vangles,&vrotated);
    tridata2->p1.c = calc_colour(vrotated,n_lightsource,tridata->colour);

    rotate(tridata->p2,g3d_info->vangles,&vrotated);
    project(vrotated,g3d_info->scale,&tridata2->p2.x,&tridata2->p2.y);
    rotate(tridata->n2,g3d_info->vangles,&vrotated);
    tridata2->p2.c = calc_colour(vrotated,n_lightsource,tridata->colour);

    rotate(tridata->p3,g3d_info->vangles,&vrotated);
    project(vrotated,g3d_info->scale,&tridata2->p3.x,&tridata2->p3.y);
    rotate(tridata->n3,g3d_info->vangles,&vrotated);
    tridata2->p3.c = calc_colour(vrotated,n_lightsource,tridata->colour);

    tridata++;
    tridata2++;
  }
  qsort(0,g3d_info->NO_OF_SIDES - 1);

  for(facet_no = g3d_info->NO_OF_SIDES-1;facet_no >= 0;facet_no--)
  {
    tridata2 = (ttranstrifacet *)facet_sort[facet_no].index;
    Gourand_poly3(tridata2->p1,tridata2->p2,tridata2->p3);
  }
}
