/// LSU EE 7700-1 (Sp 2009), Graphics Processors
//
 /// CPU-Only Demo 2: Many Triangles

// $Id:$

 /// Purpose
//
//   Demonstrate how to apply 3D techniques to a list of possibly
//   unrelated primitives (triangles).
//
//   The routine draws a grid of identical triangles pierced by
//   a unique one.
//

 /// To compile and run:
//
//     make
//     demo-2-many-triangles

 /// More Information
//
//   File coord.h on coordinate and matrix objects and operations.


#include <stdio.h>
#include <strings.h>
#include <stdlib.h>
#include <deque>

#include "frame_buffer.h"
#include "coord.h"


 /// Vertex Object
//
// Holds coordinates plus color. In later examples will hold more
// information.
//
class pVertex : public pCoor {
public:
  pVertex(float xp, float yp, float zp):pCoor(xp,yp,zp),color(0xff0000){};
  pVertex(float xp, float yp, float zp, uint32_t color):
    pCoor(xp,yp,zp),color(color){}
  pVertex():pCoor(){};
  int32_t color;
};

 /// Vertex List
//
// Declare vertex list types so that many vertices can easily be
// operated on.
//
typedef std::deque<pVertex*> pVertex_List;
typedef pVertex_List::iterator pVertex_Iterator;

 /// Vertex Sort
//
// Sort three vertices at vertex list iterator position.
//
class pSortVertices {
public:
  pSortVertices(pVertex_Iterator& ci)
  {
    rv_idx = 0;
    for ( int i=0; i<3; i++ ) v[i] = ci[i];
    swap(0,1); swap(0,2); swap(1,2);
  }
  operator pVertex& () { return *v[rv_idx++]; }
private:
  void swap(int a, int b)
  {
    if ( v[a]->y <= v[b]->y ) return;
    pVertex* const t = v[a];  v[a] = v[b];  v[b] = t;
  }
  pVertex* v[3];
  int rv_idx;
};


 /// Interpolation Object
//
// Return x and y values on line connecting two points. Skips
// out-of-range values.
//
// Can be instantiated to advance in +x direction or +y direction.
//
class pInterpolate {
public:

  pInterpolate(pVertex& v0, pVertex& v1, int ymin, int ymax)
  { set(v0, v1, ymin, ymax); }

  void set(pVertex& v0, pVertex& v1, int ymin, int ymax)
  {
    const float y_range = v1.y - v0.y;
    yi_last = ymax < int(v1.y) ? ymax : int(v1.y);
    const float pre_y = float(ymin) - v0.y;
    const bool scissor = pre_y > 0.0;
    yi = scissor ? ymin : int(v0.y);
#define DELTA(item) \
    d_##item = (float(v1.item) - v0.item) / y_range;            \
    item = v0.item + ( scissor ? pre_y * d_##item : 0.0 );
    DELTA(x);
#undef DELTA
  }

  pInterpolate(pInterpolate& v0, pInterpolate& v1, int xmin, int xmax)
  {
    pInterpolate& vmin = v0.x < v1.x ? v0 : v1;
    pInterpolate& vmax = v0.x < v1.x ? v1 : v0;
    const float x_range = vmax.x - vmin.x;
    xi_last = xmax < int(vmax.x) ? xmax : int(vmax.x);
    const float pre_x = float(xmin) - vmin.x;
    const bool scissor = pre_x > 0.0;
    xi = scissor ? xmin : int(vmin.x);
#define DELTA(item) \
    d_##item = (float(vmax.item) - vmin.item) / x_range;        \
    item = vmin.item + ( scissor ? pre_x * d_##item : 0.0 );
    // Note: DELTA not used here. See next demo.
#undef DELTA
  }

  bool keep_going_y() { return yi <= yi_last; }
  bool keep_going_x() { return xi <= xi_last; }

  void advance_y() { advance_common();  x += d_x;  yi++; }
  void advance_x() { advance_common();  xi++; }

  // This will be used later.
  void advance_common()
  {
  }

  float x, d_x;
  int xi, xi_last, yi, yi_last;
};


void
render_many_triangles(pFrame_Buffer &frame_buffer)
{
  // This routine will be called automatically each time the frame
  // buffer needs to be painted.

  ///
  /// Differences With Demo 1 (One Triangle)
  ///

  // Class pVertex is used in place of pCoor to hold coordinates. Vertex
  //  objects (pVertex instances) hold coordinates and other information
  //  associated with a vertex, including in this case, a color.

  // Instead of just one triangle, a grid of triangles is drawn.

  // Triangles are added to a list (vtx_list) and are thereafter
  //  handled uniformly.

  // Transformation and rasterization routines iterate over the vertex
  //  list.

  // The rasterization code now sorts groups of three vertices (rather
  //  than requiring them to be specified in y order).

  // Interpolation objects are used to find coordinates along the
  //  line connecting two vertices. They will later be used to
  //  interpolate not just x- and y- values, but z- values and
  //  color components.


  // Instantiate list of vertices.
  //
  pVertex_List vtx_list;

  //
  // Insert a grid of triangles in the vertex list.
  //

  const int pattern_levels = 30;  // Number of rows (in z direction.)
  const float pattern_width = 10;
  const float pattern_pitch_x = 1;
  const float pattern_half_pitch_x = pattern_pitch_x / 2;
  static float pattern_pitch_y = 0;
  const float pattern_pitch_z = 0.3;

  // Adjust y pitch in response to user input.
  //
  switch ( frame_buffer.keyboard_key ){
  case FB_KEY_UP: pattern_pitch_y += 0.01; break;
  case FB_KEY_DOWN: pattern_pitch_y -= 0.01; break;
  default: break;
  }

  // Message for user. (Magically inserted into frame buffer.)
  //
  frame_buffer.fbprintf("Use arrow keys to tilt road.\n");

  const int32_t color_red = 0xff0000;
  const int32_t color_green = 0xff00;

  float y = 0;
  float z = -1;
  for ( int i = 0; i < pattern_levels; i++ )
    {
      const float next_y = y + pattern_pitch_y;
      const float next_z = z - pattern_pitch_z;
      float x = 0;

      while ( x < pattern_width )
        {

          // Add a red triangle to list.
          //
          vtx_list.push_back( new pVertex( x, y, z, color_red ) );
          x += pattern_half_pitch_x;
          vtx_list.push_back( new pVertex( x, next_y, next_z, color_red ) );
          x += pattern_half_pitch_x;
          vtx_list.push_back( new pVertex( x, y, z, color_red ) );
        }

      y = next_y;
      z = next_z;
    }

  // Add another triangle, a green one that passes through grid.
  //
  vtx_list.push_back( new pVertex( 3, -3, -1, color_green  ) );
  vtx_list.push_back( new pVertex( 0, 5, -5, color_green  ) );
  vtx_list.push_back( new pVertex( 9, 6, -9, color_green ) );

  ///
  /// Rendering Pipeline Starts Here
  ///

  const int win_width = frame_buffer.get_width();
  const int win_height = frame_buffer.get_height();
  int32_t* const f_buffer = frame_buffer.get_buffer();

  // Specify Transformation

  pMatrix_Translate center_eye(-5,-6,-2);
  pMatrix_Frustum frustum(4,5,1,20);
  pMatrix_Translate center_window(1,1,0);
  pMatrix_Scale scale(win_width/2,win_height/2);
  pMatrix transform = scale * center_window * frustum * center_eye;

  ///
  /// Transform Coordinates
  ///
  for ( pVertex_Iterator ci = vtx_list.begin(); ci < vtx_list.end(); ci++ )
    {
      pVertex& v = **ci;  // Get reference to current vertex
      v *= transform;
      v.homogenize();
    }

  ///
  /// Rasterize Primitives
  ///
  for ( pVertex_Iterator ci = vtx_list.begin(); ci < vtx_list.end(); ci += 3 )
    {
      pSortVertices sort(ci); // Sort next 3 items in list.
      pVertex& c0w = sort;    // Coordinate with smallest y.
      pVertex& c1w = sort;
      pVertex& c2w = sort;    // Coordinate with largest y.

      const int32_t color = c0w.color;

      // Instantiate interpolation objects.
      //
      // Each object instantiated with two coordinates and a valid
      // range of y values.  The object will compute x and y along the
      // line connecting those coordinates, skipping y values < 0 or
      // >= win_width.
      //
      pInterpolate interp_02(c0w,c2w,0,win_height-1);
      pInterpolate interp_012(c0w,c1w,0,win_height-1);

      // Compute position (index) in frame buffer of first row to be written.
      //
      int fb_line_idx = interp_02.yi * win_width;

      // Outer Loop: Iterate from smallest y to largest y.
      //
      while ( interp_02.keep_going_y() )
        {

          // If point c1w reached then switch interp_012 to line
          // connecting c1w and c2w.
          //
          if ( ! interp_012.keep_going_y() )
            interp_012.set(c1w,c2w,0,win_height-1);

          // Instantiate x-axis interpolation object using the two
          // y-axis interpolation objects, interp_02 and interp_012.
          // The new object will compute points on the line connecting
          // the current position of interp_02 and interp_012.
          //
          pInterpolate interp_line(interp_02,interp_012,0,win_width-1);

          // Inner Loop: Iterate along x axis.
          //
          while ( interp_line.keep_going_x() )
            {
              const int fb_idx = fb_line_idx + interp_line.xi;
              f_buffer[ fb_idx ] = color;

              // Tell interpolation object to advance in x direction.
              //
              interp_line.advance_x();
            }

          // Tell interpolation objects to advance in y direction.
          //
          interp_02.advance_y();  interp_012.advance_y();

          // Advance the frame buffer index.
          //
          fb_line_idx += win_width;
        }
    }

  // A paint routine is no place for a memory leak!
  //
  for ( pVertex_Iterator ci = vtx_list.begin(); ci < vtx_list.end(); ci++ )
    delete *ci;
}

int
main(int argc, char **argv)
{
  pFrame_Buffer frame_buffer(argc,argv);
  frame_buffer.show(render_many_triangles);
  return 0;
}