//-------------------------------------------------------------------
//	opaqueit.cpp			   
//
//	This prototype employs principles of perspective projection
//	to build and draw a wireframe model of a torus described by 
//	the parametric equations	
//
//			x = (C + A cos u) cos v
//			y = A sin u
//			z = (C + A cos u) sin v
//
//	where  C  denotes the radius from the center of the torus's
//	hole to the center of the torus's tube, and  A  denotes the 
//	radius of the torus's tube (hence this torus is azimuthally 
//	symmetric about the y-axis).  Only the visible faces of the 
//	polygon mesh are drawn; then the order in which those faces  
//	are filled with a solid color is farthest-to-nearest (i.e., 
//	the so-called "Painter's Algorithm"), so that visible faces 
//	closer to the viewer will 'cover up' the ones further away.
//
//	  compile using: $ g++ opaqueit.cpp int86.cpp -o opaqueit 
//	  execute using: $ ./opaqueit  (or: $ ./opaqueit <anyarg>)
//
//	programmer: ALLAN CRUSE
//	written on: 24 DEC 2005
//	revised on: 28 DEC 2005 -- option shows Painter's Algorithm
//	revised on: 20 MAR 2011 -- for Gateway laptop's Radeon GPU
//-------------------------------------------------------------------

#include <stdio.h>	// for printf(), perror() 
#include <fcntl.h>	// for open() 
#include <stdlib.h>	// for exit() 
#include <unistd.h>	// for lseek() 
#include <string.h>	// for memcpy(), memset()
#include <math.h>	// for sqrt(), fabs(), sin(), cos()
#include <time.h>	// for usleep()
#include <sys/mman.h>	// for mmap() 
#include <sys/ioctl.h>	// for ioctl()

#define VRAM_BASE 	0x80000000
#define GET_CRTC_START_ADDRESS	0
#define PI		3.14159

const unsigned int	hpitch = 1024;
const unsigned int	maxcol = 1024;
const unsigned int	maxrow = 768;
unsigned int		*fb;

unsigned int	Screensave[ hpitch * maxrow ];

const int	hres = 640, vres = 480;
int		above = 40;
int		below = above + vres;
int		ledge = (maxcol - hres) / 2;
int		redge = (ledge + hres);

int  demo_mode;

// function prototypes
void create_the_model_vertices( void );
void create_the_model_polygons( void );
void compute_faceplane_normals( void );
void perform_faceplane_sorting( void );
void setup_the_view_parameters( void );
void render_the_wireframe_view( void );
void render_the_solidfill_view( void );


int main( int argc, char **argv )
{
	// set flag to activate Painter's Algorithm demo
	demo_mode = ( argc > 1 );	

	// prepare the problem data
	create_the_model_vertices();
	create_the_model_polygons();
	compute_faceplane_normals();
	perform_faceplane_sorting();
	setup_the_view_parameters();

	// memory-map the display-memory into user-space
	int	vd = open( "/dev/vram", O_RDWR ); 
	if ( vd < 0 ) { perror( "/dev/vram" ); exit(1); }
	int	size = lseek( vd, 0, SEEK_END ); 
	int	prot = PROT_READ | PROT_WRITE; 
	int	flag = MAP_FIXED | MAP_SHARED; 
	void	*mm = (void *)VRAM_BASE;
	if ( mmap( mm, size, prot, flag, vd, 0 ) == MAP_FAILED )
		{ perror( "mmap" ); exit(1); } 

	// obtain the frame-buffer's offset
	unsigned int	crtc_start_address = 0;
	if ( ioctl( vd, GET_CRTC_START_ADDRESS, &crtc_start_address ) < 0 )
		{ perror( "ioctl" ); exit(1); }
	unsigned int	fb_offset = crtc_start_address & 0x3FFFFFFF;
	printf( "\n FRAME_BUFFER_OFFSET = 0x%08X \n", fb_offset );
	fb = (unsigned int *)( VRAM_BASE + fb_offset );
	
	// save the screen-image to be restored later 
	memcpy( Screensave, &fb[0], sizeof( Screensave ) );

	// erase the screen
	memset( &fb[ 24 * hpitch ], 0x00, 2112 * hpitch );
	
	// draw screen border 
	int	x = ledge, y = above, color = 0xFFFFFF; 
	do { fb[ y * hpitch + x ] = color; ++x; } while ( x < redge-1 ); 
	do { fb[ y * hpitch + x ] = color; ++y; } while ( y < below-1 ); 
	do { fb[ y * hpitch + x ] = color; --x; } while ( x > ledge+0 ); 
	do { fb[ y * hpitch + x ] = color; --y; } while ( y > above+0 ); 
	getchar();
	
	// show the torus
	render_the_wireframe_view();
	getchar();
	render_the_solidfill_view();
	getchar();

	
	// recover the saved screen-image
	memcpy( &fb[0], Screensave, sizeof( Screensave ) );
}

#define N	32
#define MAXVERT N*N
typedef float scalar_t;
typedef struct	{ scalar_t  x, y, z; } vector_t;
typedef struct  { int  vert[ 4 ]; vector_t base, perp; } face_t;
typedef struct	{ 
		int  numverts; vector_t  vert[ MAXVERT ]; 
		int  numquads; face_t  quad[ MAXVERT ]; 
		} model_t;

int facesort[ N*N ];

const scalar_t A = 1.0;
const scalar_t C = 2.0;
const scalar_t theta = 2*PI/N;  

vector_t eye = { 6.0, 6.5, 8.0 };
model_t  world, view;

scalar_t transX = hres/2, transY = vres/2;
scalar_t scaleX = vres/8, scaleY = -vres/8; 

void normalize( vector_t &v )
{
	scalar_t	norm = sqrt( v.x*v.x + v.y*v.y + v.z*v.z );
	if ( norm != 0.0 ) { v.x /= norm; v.y /= norm; v.z /= norm; }
}

scalar_t dot_product( vector_t a, vector_t b )
{
	return	a.x * b.x + a.y * b.y + a.z * b.z;
}

void vector_fromto( vector_t from, vector_t to, vector_t &v )
{
	v.x = to.x - from.x;
	v.y = to.y - from.y;
	v.z = to.z - from.z;
}

void cross_product( vector_t a, vector_t b, vector_t &c )
{
	c.x = a.y * b.z - b.y * a.z;
	c.y = a.z * b.x - b.z * a.x;
	c.z = a.x * b.y - b.x * a.y;
}

void create_the_model_vertices( void )
{
	// we will employ parametric equations for our torus
	// our outer loop subdivides the circle that generates
	// the torus tube into  N  equal-width sectors
	// our inner loop subdivides the circle that generates
	// the torus hole into  N  equal-width sectors
	vector_t	vertex;	
	for (int i = 0; i < N; i++)
		{
		scalar_t	mu = i * theta;
		scalar_t	rx = (C + A*cos( mu ));
		vertex.y = A*sin( mu );
		for (int j = 0; j < N; j++)
			{
			scalar_t	nu = j * theta;
			vertex.x = rx * cos( nu );
			vertex.z = rx * sin( nu );
			world.vert[ i*N + j ] = vertex;
			}	
		}
	world.numverts = N*N;
}

void create_the_model_polygons( void )
{
	for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
		{
		int	ii = (i+1)%N;
		int	jj = (j+1)%N;
		int	v0 = i * N + j;
		int	v1 = ii * N + j;
		int	v2 = ii * N + jj;
		int	v3 = i * N + jj;
		world.quad[ v0 ].vert[ 0 ] = v0;
		world.quad[ v0 ].vert[ 1 ] = v1;
		world.quad[ v0 ].vert[ 2 ] = v2;
		world.quad[ v0 ].vert[ 3 ] = v3;
		}
	world.numquads = N*N;
}

void setup_the_view_parameters( void )
{
	vector_t	vrp = { 0, 0, 0 };
	vector_t	vup = { 0, 1, 0 };
	vector_t	vpn;
	vector_fromto( vrp, eye, vpn );

	vector_t	u, v, n = vpn;
	normalize( n );
	cross_product( vup, n, u );
	normalize( u );
	cross_product( n, u, v );
	normalize( v );

	// transform vertices of the model to camera coordinates
	view = world;
	for (int i = 0; i < view.numverts; i++)
		{
		vector_t	p;
		vector_fromto( vrp, world.vert[ i ], p );
		view.vert[ i ].x = dot_product( u, p );	
		view.vert[ i ].y = dot_product( v, p );	
		view.vert[ i ].z = dot_product( n, p );	
		}

	// compute distance from viewer's eye to the viewplane
	vector_t	eo;
	vector_fromto( eye, vrp, eo );
	scalar_t	eyedist = sqrt( dot_product( eo, eo ) );
	
	// perform the perspective projection
	for (int i = 0; i < view.numverts; i++)
		{
		vector_t	vertex = view.vert[ i ];
		scalar_t	hittime = 1.0/( 1.0 - vertex.z / eyedist );
		vertex.x *= hittime;
		vertex.y *= hittime;
		vertex.z *= 0.0;
		view.vert[ i ] = vertex;
		}
}

void compute_faceplane_normals( void )
{
	for (int i = 0; i < world.numquads; i++)   
		{
		face_t	quad = world.quad[ i ];
		
		// set base equal to centroid
		vector_t  cent = { 0, 0, 0 };
		for (int j = 0; j < 4; j++)
			{
			vector_t  vertex = world.vert[ quad.vert[j] ];
			cent.x += vertex.x;	
			cent.y += vertex.y;	
			cent.z += vertex.z;	
			}
		cent.x /= 4;
		cent.y /= 4;
		cent.z /= 4;
		world.quad[ i ].base = cent;

		// set perp equal to consequtive edge cross-product
		vector_t	v0 = world.vert[ quad.vert[0] ];
		vector_t	v1 = world.vert[ quad.vert[1] ];
		vector_t	v2 = world.vert[ quad.vert[2] ];
		vector_t	e1, e2, nn;
		vector_fromto( v0, v1, e1 );
		vector_fromto( v1, v2, e2 );
		cross_product( e1, e2, nn );
		normalize( nn );
		world.quad[ i ].perp = nn;
		}
}		

void perform_faceplane_sorting( void )
{
	// initialize the facesort list
	for (int i = 0; i < world.numquads; i++) facesort[ i ] = i;

	// now sort in decreasing order of face's distance from eye
	for (int i = 1; i < world.numquads; i++)
		for (int j = 0; j < i; j++)
			{
			int	u = facesort[ i ];
			int	v = facesort[ j ];

			face_t	quad_i = world.quad[ u ];
			face_t	quad_j = world.quad[ v ];
			
			vector_t	ri, rj;
			vector_fromto( quad_i.base, eye, ri );
			vector_fromto( quad_j.base, eye, rj );

			scalar_t  dist_i = sqrt( dot_product( ri, ri ) );
			scalar_t  dist_j = sqrt( dot_product( rj, rj ) );

			if ( dist_i > dist_j )
				{
				facesort[ i ] = v;
				facesort[ j ] = u;
				} 
			}
}

void draw_pixel( int x, int y, int color )
{
	if (( x < 1 )||( x >= hres-1 )) return;
	if (( y < 1 )||( y >= vres-1 )) return;
	fb[ (y+ above) * hpitch + (x + ledge) ] = color;
}

void exchange( int &x1, int &y1, int &x2, int &y2 )
{
	int	xx, yy;

	xx = x2; x2 = x1; x1 = xx; yy = y2; y2 = y1; y1 = yy;
}

void octant_odd( int x1, int y1, int x2, int y2, int color )
{
	// make sure x1 <= x2
	if ( x1 > x2 ) exchange( x1, y1, x2, y2 );

	int	xinc = ( x2 > x1 ) ? 1 : -1;
	int	yinc = ( y2 > y1 ) ? 1 : -1;

	int	dx = (x2 - x1)*xinc;
	int	dy = (y2 - y1)*yinc;
	int	errorterm = -dx;
	for (int x = x1, y = y1; x <= x2; x++)
		{
		draw_pixel( x, y, color );
		errorterm += (dy+dy);
		if ( errorterm >= 0 )
			{
			y += yinc;
			errorterm -= (dx+dx);
			}
		} 
}

void octant_even( int x1, int y1, int x2, int y2, int color )
{
	// make sure y1 <= y2
	if ( y1 > y2 ) exchange( x1, y1, x2, y2 );

	int	xinc = ( x2 > x1 ) ? 1 : -1;
	int	yinc = ( y2 > y1 ) ? 1 : -1;

	int	dx = (x2 - x1)*xinc;
	int	dy = (y2 - y1)*yinc;
	int	errorterm = -dy;
	for (int x = x1, y = y1; y <= y2; y++)
		{
		draw_pixel( x, y, color );
		errorterm += (dx+dx);
		if ( errorterm >= 0 )
			{
			x += xinc;
			errorterm -= (dy+dy);
			}
		} 
}

void draw_line( int x1, int y1, int x2, int y2, int color )
{
	// use the Bresenham Algorithm
	int	deltaX = ( x1 < x2 ) ? x2-x1 : x1-x2;
	int	deltaY = ( y1 < y2 ) ? y2-y1 : y1-y2;

	if ( deltaX > deltaY ) octant_odd( x1, y1, x2, y2, color );
	else	octant_even( x1, y1, x2, y2, color );
}

void do_quad_draw( face_t quad, int color )
{
	for (int j = 0; j < 4; j++)
		{
		int	k = (j+1)%4;
		vector_t	p0 = view.vert[ quad.vert[ j ] ];
		vector_t	p1 = view.vert[ quad.vert[ k ] ];
			
		int	x0 = (int)( p0.x * scaleX + transX );
		int	y0 = (int)( p0.y * scaleY + transY );
		int	x1 = (int)( p1.x * scaleX + transX );
		int	y1 = (int)( p1.y * scaleY + transY );
		draw_line( x0, y0, x1, y1, color );
		}
}

int face_is_visible( face_t quad, vector_t eye )
{
	vector_t	rr, nn = quad.perp;
	vector_fromto( quad.base, eye, rr );
	if ( dot_product( rr, nn ) <= 0.0 ) return 0;
	else return	1;
}

void render_the_wireframe_view( void )
{
	int	color = 0xFFFF00;
	for (int i = 0; i < view.numquads; i++)   // view.numquads
		{
		face_t	quad = view.quad[ i ];

		if ( face_is_visible( quad, eye ) ) 
			do_quad_draw( quad, color );
		}
}

//---------------------  Polygon-fill Algorithm  ---------------------

typedef struct Node { int x; Node *next; } Node;
typedef Node *NodePtr;
const int maxnode = 2 * vres;
Node pool[ maxnode ];
NodePtr bucket[ vres ];
int used = 0;

void initialize_buckets( void )
{
	for (int i = 0; i < vres; i++) bucket[ i ] = NULL;
}

NodePtr newnode( void )
{
	if ( used < maxnode ) return &pool[ used++ ];
	else	return NULL;
}

int is_between( int y1, int y2, int y3 )
{
	// returns true if  y1 < y2 < y3  or  y1 > y2 > y3
	return	(( y1 < y2 )&&( y2 < y3 ))||(( y1 > y2 )&&( y2 > y3 ));
}

void insert_pixel( int x, int y )
{
	// make sure y-coordinate is within bucket array-bounds
	if (( y < 0 )||( y >= vres )) return;

	NodePtr	p = newnode();
	if ( p == NULL ) exit( 1 );	// TODO: Fix this exit

	// add the pixel x-coordinate to the appropriate linked list
	p->x = x;
	p->next = bucket[ y ];		// front of the linked list
	bucket[ y ] = p;

	// maintain the bucket linked list in sorted order 
	NodePtr	q = p->next;
	while ( q != NULL )
		{
		if ( p->x > q->x ) 	// out-of-order
			{ int tmp = p->x; p->x = q->x; q->x = tmp; }
		p = p->next;
		q = p->next;
		}
}

void insert_edge( vector_t p1, vector_t p2 )
{
	int	x1 = (int)( p1.x * scaleX + transX );
	int	y1 = (int)( p1.y * scaleY + transY );
	int	x2 = (int)( p2.x * scaleX + transX );
	int	y2 = (int)( p2.y * scaleY + transY );

	int	xinc = ( x1 > x2 ) ? -1 : 1;
	int	yinc = ( y1 > y2 ) ? -1 : 1;

	int	dx = ( x2 - x1 )*xinc;	 
	int	dy = ( y2 - y1 )*yinc;	 

	int	x = x1, y = y1, e = 2*dx - dy;
	insert_pixel( x, y );
	while ( y != y2 )
		{
		if ( e >= 0 ) do { x += xinc; e -= 2*dy; } while ( e >= 0 );
		e += 2*dx;
		y += yinc;
		insert_pixel( x, y );
		}
}		

void do_scan_conversion( face_t quad )
{
	initialize_buckets();
	used = 0;

	for (int j = 0; j < 4; j++)
		{
		int	k = (j+1)%4;
		vector_t  p1 = view.vert[ quad.vert[j] ];
		vector_t  p2 = view.vert[ quad.vert[k] ];
		insert_edge( p1, p2 );
		}

	// do an extra insertion when a quad's vertex is 
	// vertically between any two adjacent vertices
	for (int j = 0; j < 4; j++)
		{
		int	k = (j+1)%4;
		int	l = (j+2)%4;
		vector_t  p1 = view.vert[ quad.vert[j] ];
		vector_t  p2 = view.vert[ quad.vert[k] ];
		vector_t  p3 = view.vert[ quad.vert[l] ];
		int	y1 = (int)( p1.y * scaleY + transY );
		int	y2 = (int)( p2.y * scaleY + transY );
		int	x2 = (int)( p2.x * scaleX + transX );
		int	y3 = (int)( p3.y * scaleY + transY );
		if ( is_between( y1, y2, y3 ) ) insert_pixel( x2, y2 );
		}
}

void do_quad_fill( face_t quad, int color )
{
	do_scan_conversion( quad );
	
	for (int y = 0; y < vres; y++)
		if ( bucket[ y ] != NULL ) 
			{
			NodePtr  p = bucket[y];
			NodePtr  q = p->next;
			while (( p != NULL )&&( q != NULL ))
				{
				for (int x = p->x; x <= q->x; x++)
					draw_pixel( x, y, color );
				p = q->next;
				if ( p != NULL ) q = p->next;
				else	q = NULL;
				}
			} 		
}

void render_the_solidfill_view( void )
{
	int	fillcolor = 0x7F7F7F, drawcolor = 0;
	for (int i = 0; i < view.numquads; i++)
		{
		face_t	quad = view.quad[ facesort[i] ];
		if ( face_is_visible( quad, eye ) ) 
			{
			do_quad_fill( quad, fillcolor );
			do_quad_draw( quad, drawcolor );
			// users can supply any command-line argument
			// to see how the "Painter's Algorithm" works
			if ( demo_mode ) usleep( 20000 ); 
			}
		}		
}