```/// 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

//
//   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; }

// This will be used later.
{
}

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.
//
}

// Tell interpolation objects to advance in y direction.
//

// 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;
}
```