// 3D Demonstration (24/11/99)
// Written by Harvey Cotton for Borland C++ 3.0

// How the engine works:
// (1) Object is defined by a set of points local to its origin. These are its local coordinates.
// (2) Each object is defined as vertices and polygons (quads). Polygons are defined top-left to top-right and bottom-left to bottom-right.
// (3) The object's local points are transformed by rotation, scale & translation. This creates its world coordinates.
// (4) The object's world coordinates (represented as a matrix) is multiplied by the camera matrix to create it camera coordinates.
// (5) The final transformation converts the 3d points to 2d points for representation on the screen,
//     using new_x=x*distance_from_camera/z and new_y=y*distance_from_camera/z.
// (6) Finally each object undergoes hidden surface removal, which eliminates polygons that are facing away from the camera.
//     Since each polygon is defined as left to right and top to bottom, the equation (x1-x2)*(y3-y2)-(y1-y2)*(x3-x2) can be used.
//     This equation compares the dx and dy of the points on the polygon, so that if the result is positive the polygon is visible, else it is invisible.

// What hasn't been implemented:
// * Clipping. To check whether the object lies outside the view. Also, Z clipping since vertices with z<1 are behind the camera.
//   This also bypasses the divide by zero error.
// * Z-sorting. This is relatively straightforward. Take the average Z value for every polygon that is rendered and sort from nearest to furthest.
// * Ambient lighting. A simple RGB value applied combined with every polygon.
//   Not really possible in this case, because this stupid graphics driver only supports 16 colours.
// * Diffuse lighting. This is simply the cosine between the normal of the polygon (direction the face is pointing) and the light source.
// * Specular lighting. Used to make objects appear shiny. The cosine between the light flected off the surface and the viewer.
// * Collision detection. Probably a bounding box test followed by a volume overlap test. I haven't looked into this yet.
// * Perspective correct texture mapping. 
// * Gouraud shading. Blending of colours between vertices. Very processor intensive, but looks nice.
// * Bilinear filtering. Average out all the pixels on the screen, which essentially softens the picture and makes things look less blocky.
//   E.g.    1/5
//       1/5 1/5 1/5
//           1/5

// Possible changes:
// * Stick to triangles instead of quads. This allows for more complex shapes and are easier to deal with.
// * Use a better compiler, either 32-bit dos or Windows and rewrite code in object-orientated C++.
//   All graphics routines in C++ 3.0 are 16-bit so there is potential overflow problems.
// * Replace all floating point with fixed point arithmetic.
//   Probably not necessary with other compilers. Necessary with this one.
// * Redo the matrixes. The column on the very right is never used - wastage.
// * Rewrite each function to work on its own rather than rely on others. Maybe in assembly (if i knew any).
// * Allow the engine to load in dxf files, so that I can design the objects in Studio Max than by hand!

// ******************************************************************* Headers

#include <iostream.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <graphics.h>
#include <math.h>
#include <dos.h>

// ********************************************************************* Notes

/*
COLOUR
======
0   BLACK
1   BLUE
2   GREEN
3   CYAN
4   RED
5   MAGENTA
6   BROWN
7   LIGHTGRAY
8   DARKGRAY
9   LIGHTBLUE
10  LIGHTGREEN
11  LIGHTCYAN
12  LIGHTRED
13  LIGHTMAGENTA
14  YELLOW
15  WHITE
128 BLINK


COORDINATE SYSTEM
=================
  y
  |   z
  |  /
  | /
  |/
  +------x
*/

// ******************************************************************* Defines

#define DIST	256	// Viewing distance

// ******************************************************************* Structs

typedef double MATRIX [4][4];

typedef struct VECTOR
{
	double vx,vy,vz,pad;
};

typedef struct POLYGON
{
	int ref [4];		// reference to vertex which makes the quad
	int colour;		// colour of quad
};

typedef struct OBJECT
{
	VECTOR	vertex	[64];	// number of vertices
	POLYGON polygon [64];	// references to vertices to form quads
	MATRIX	transform;	// Object transformation matrix
	int	npol;		// number of polygons
};

// ******************************************************************* Globals

MATRIX	camera;		// Camera position and orientation
float	FCOS [361];	// Cos look-up table
float	FSIN [361];	// Sin look-up table
short	PAGE;		// Page flipping

// ****************************************************************** Graphics

void InitialiseGraphics (int gdriver,int gmode)
{
	// Load & initiate graphics mode
	initgraph(&gdriver, &gmode, "");
	if (graphresult()!=grOk) exit(1);
	sleep(2);
	setbkcolor(BLACK);
	cleardevice();

	// Build look-up tables
	for(short index=0; index<361; index++)
	{
		FCOS[index]=cos(index*3.14159/180);
		FSIN[index]=sin(index*3.14159/180);
	}
}

int GetKey ()
{
	if (kbhit())
	{
		int key=getch();
		if (key==0) key=getch()+128;
		return key;
	}
	else return 0;
}

void double_buffer ()
{
	setvisualpage(PAGE);
	setactivepage(PAGE=1-PAGE);
	while(inp(0x3DA) & 0x08);
	while(!(inp(0x3DA) & 0x08));
	cleardevice();
}

void DrawCircle (short x,short y,short r,char colour)
{
	register short index;

	for(index=0; index<=360; index++)
		putpixel(x+r*FCOS[index],y+r*FSIN[index],colour);
}

// Draw a line fast using Bresenham's algorithm
void DrawLine (short x1,short y1,short x2,short y2,char colour)
{
	register short	dx=x2-x1,
			dy=y2-y1,
			xinc,
			yinc,
			decision=0,
			index=0;

	if (dx>=0) // find x direction
	{
		xinc=1; // moving right
	}
	else
	{
		xinc=-1; // moving left
		dx=-dx; // absolute dx
	}

	if (dy>=0) // find y direction
	{
		yinc=1; // moving down
	}
	else
	{
		yinc=-1; // moving up
		dy=-dy; // absolute dy
	}

	if (dx>dy) // find which delta is greater
	{
		for(;index<=dx;index++) // draw line
		{
			putpixel(x1,y1,colour); // plot pixel

			decision+=dy; // adjust decision variable

			if (decision>dx) // if decision overflows
			{
				decision-=dx; // reset decision variable
				y1+=yinc; // move point to next line
			}

			x1+=xinc; // next pixel
		}
	}
	else
	{
		for(;index<=dy;index++) // draw line
		{
			putpixel(x1,y1,colour); // plot pixel

			decision+=dx; // adjust decision variable

			if (decision>0) // if decision overflows
			{
				decision-=dy; // reset decision variable
				x1+=xinc; // move point to next line
			}

			y1+=yinc; // next pixel
		}
	}

	// Add boundary clipping
	// x_clip = (dy/dx) * (y_boundary - y1) + x1
	// y_clip = (dy/dx) * (x_boundary - x1) + y1
}

// ******************************************************************** Matrix

void MatrixIdentity (MATRIX &m)
{
	register short i,j;

	for (i=0; i<4; i++)
	{
		for (j=0; j<4; j++)
		{

			if (i==j) m[i][j]=1;
			else m[i][j]=0;
		}
	}
}

void MatrixMultiply (MATRIX &result,MATRIX &m1,MATRIX &m2)
{
	register short i,j,k;
	register float sum;

	for (i=0; i<4; i++)
	{
		for (j=0; j<4; j++)
		{
			sum=0;

			for (k=0; k<4; k++)
				sum+=m1[i][k]*m2[k][j];

			result[i][j]=sum;
		}
	}
}

void MatrixTranslate (MATRIX &m,double x,double y,double z)
{
	MatrixIdentity(m);
	m[3][0]=x;
	m[3][1]=y;
	m[3][2]=z;
}

void MatrixRotate (MATRIX &m,double rx,double ry,double rz)
{
	MATRIX temp,rotate_x,rotate_y,rotate_z;

	MatrixIdentity(rotate_x);
	MatrixIdentity(rotate_y);
	MatrixIdentity(rotate_z);

	rotate_z[0][0]=FCOS[rz];
	rotate_z[0][1]=FSIN[rz];
	rotate_z[1][0]=-FSIN[rz];
	rotate_z[1][1]=FCOS[rz];

	rotate_y[0][0]=FCOS[ry];
	rotate_y[0][2]=FSIN[ry];
	rotate_y[2][0]=-FSIN[ry];
	rotate_y[2][2]=FCOS[ry];

	rotate_x[1][1]=FCOS[rx];
	rotate_x[1][2]=-FSIN[rx];
	rotate_x[2][1]=FSIN[rx];
	rotate_x[2][2]=FCOS[rx];

	MatrixMultiply(temp,rotate_y,rotate_x);
	MatrixMultiply(m,temp,rotate_z);
}

void MatrixScale (MATRIX &m,double sx,double sy,double sz)
{
	MatrixIdentity(m);
	m[0][0]=sx;
	m[1][1]=sy;
	m[2][2]=sz;
}

void MatrixAll (MATRIX &m,double x,double y,double z,short rx,short ry,short rz,double sx,double sy,double sz)
{
	MATRIX temp,rotate,scale,translate;

	// Rotate, scale then translate
	MatrixIdentity(m);
	MatrixRotate(rotate,rx,ry,rz);
	MatrixScale(scale,sx,sy,sz);
	MatrixTranslate(translate,x,y,z);

	// Combine transformations
	MatrixMultiply(temp,rotate,scale);
	MatrixMultiply(m,temp,translate);
}

// *************************************************************** 3d graphics

void InitialiseObject (OBJECT &object,short npol,long x,long y,long z)
{
	MatrixTranslate(object.transform,x,y,z);
	object.npol=npol;
}

void SetCamera (long x,long y,long z,short rx,short ry,short rz)
{
	MATRIX temp,temp2,rotate_x,rotate_y,rotate_z;

	MatrixIdentity(rotate_x);
	MatrixIdentity(rotate_y);
	MatrixIdentity(rotate_z);

	rotate_z[0][0]=-FCOS[rz];
	rotate_z[0][1]=-FSIN[rz];
	rotate_z[1][0]=FSIN[rz];
	rotate_z[1][1]=-FCOS[rz];

	rotate_y[0][0]=-FCOS[ry];
	rotate_y[0][2]=-FSIN[ry];
	rotate_y[2][0]=FSIN[ry];
	rotate_y[2][2]=-FCOS[ry];

	rotate_x[1][1]=-FCOS[rx];
	rotate_x[1][2]=FSIN[rx];
	rotate_x[2][1]=-FSIN[rx];
	rotate_x[2][2]=-FCOS[rx];

	MatrixMultiply(temp,rotate_y,rotate_x);
	MatrixMultiply(temp2,temp,rotate_z);
	MatrixTranslate(temp,-x,-y,-z);
	MatrixMultiply(camera,temp,temp2);
}

void SetVertex (VECTOR &vertex,long x,long y,long z)
{
	vertex.vx=x;
	vertex.vy=y;
	vertex.vz=z;
}

void SetPolygon (POLYGON &polygon,int v1,int v2,int v3,int v4,char colour)
{
	polygon.ref[0]=v1;
	polygon.ref[1]=v2;
	polygon.ref[2]=v3;
	polygon.ref[3]=v4;
	polygon.colour=colour;
}

void RenderObject (OBJECT &object)
{
	int index;
	int poly[10];		// Single quad
	MATRIX temp,temp2;	// Transformation

	// First test to see if object is in front of camera
	MatrixMultiply(temp,object.transform,camera);
	if (temp[3][2]<1) return;

	// Render object
	for(index=0; index<object.npol; index++)
	{
		// Transform each vertex
		MatrixTranslate(temp,object.vertex[object.polygon[index].ref[0]].vx,object.vertex[object.polygon[index].ref[0]].vy,object.vertex[object.polygon[index].ref[0]].vz);
		MatrixMultiply(temp2,temp,object.transform);
		MatrixMultiply(temp,temp2,camera);
		poly[0]=320+((temp[3][0]*DIST)/(temp[3][2])); //x1
		poly[1]=175-((temp[3][1]*DIST)/(temp[3][2])); //y1

		MatrixTranslate(temp,object.vertex[object.polygon[index].ref[1]].vx,object.vertex[object.polygon[index].ref[1]].vy,object.vertex[object.polygon[index].ref[1]].vz);
		MatrixMultiply(temp2,temp,object.transform);
		MatrixMultiply(temp,temp2,camera);
		poly[2]=320+((temp[3][0]*DIST)/(temp[3][2])); //x2
		poly[3]=175-((temp[3][1]*DIST)/(temp[3][2])); //y2

		MatrixTranslate(temp,object.vertex[object.polygon[index].ref[3]].vx,object.vertex[object.polygon[index].ref[3]].vy,object.vertex[object.polygon[index].ref[3]].vz);
		MatrixMultiply(temp2,temp,object.transform);
		MatrixMultiply(temp,temp2,camera);
		poly[4]=320+((temp[3][0]*DIST)/(temp[3][2])); //x4
		poly[5]=175-((temp[3][1]*DIST)/(temp[3][2])); //y4

		MatrixTranslate(temp,object.vertex[object.polygon[index].ref[2]].vx,object.vertex[object.polygon[index].ref[2]].vy,object.vertex[object.polygon[index].ref[2]].vz);
		MatrixMultiply(temp2,temp,object.transform);
		MatrixMultiply(temp,temp2,camera);
		poly[6]=320+((temp[3][0]*DIST)/(temp[3][2])); //x3
		poly[7]=175-((temp[3][1]*DIST)/(temp[3][2])); //y3

		poly[8]=poly[0];
		poly[9]=poly[1];

		// Check to see if the polygon is visible and draw it
		if ((poly[0]-poly[2])*(poly[7]-poly[3])-(poly[1]-poly[3])*(poly[6]-poly[2])>=0)
		{
			setcolor(object.polygon[index].colour);
			setfillstyle(SOLID_FILL,object.polygon[index].colour);
			fillpoly(4,poly);
		}
	}
}


void RenderLine3d (long x1,long y1,long z1,long x2,long y2,long z2,char colour)
{
	MATRIX temp,temp2;

	// First point
	MatrixTranslate(temp,x1,y1,z1);
	MatrixMultiply(temp2,temp,camera);
	x1=320+((temp2[3][0]*DIST)/(temp2[3][2]));
	y1=175-((temp2[3][1]*DIST)/(temp2[3][2]));

	// Second point
	MatrixTranslate(temp,x2,y2,z2);
	MatrixMultiply(temp2,temp,camera);
	x2=320+((temp2[3][0]*DIST)/(temp2[3][2]));
	y2=175-((temp2[3][1]*DIST)/(temp2[3][2]));

	// Draw the line
	setcolor(colour);
	line(x1,y1,x2,y2);
}

// ********************************************************************** Main

void main ()
{
	InitialiseGraphics(VGA,VGAMED);

	// ***** Define some primitives *****

	OBJECT shape1;
	InitialiseObject(shape1,6,0,0,0);
	SetVertex(shape1.vertex[0], -100, -100, 100);
	SetVertex(shape1.vertex[1], 100, -100, 100);
	SetVertex(shape1.vertex[2], 100, -100, -100);
	SetVertex(shape1.vertex[3], -100, -100, -100);
	SetVertex(shape1.vertex[4], -100, 100, 100);
	SetVertex(shape1.vertex[5], 100, 100, 100);
	SetVertex(shape1.vertex[6], 100, 100, -100);
	SetVertex(shape1.vertex[7], -100, 100, -100);
	SetPolygon(shape1.polygon[0], 0,1,3,2, RED);
	SetPolygon(shape1.polygon[1], 2,1,6,5, GREEN);
	SetPolygon(shape1.polygon[2], 3,2,7,6, BLUE);
	SetPolygon(shape1.polygon[3], 0,3,4,7, YELLOW);
	SetPolygon(shape1.polygon[4], 1,0,5,4, CYAN);
	SetPolygon(shape1.polygon[5], 7,6,4,5, MAGENTA);

	OBJECT shape2;
	InitialiseObject(shape2,5,0,0,0);
	SetVertex(shape2.vertex[0],-100,-100,100);
	SetVertex(shape2.vertex[1],100,-100,100);
	SetVertex(shape2.vertex[2],-100,-100,-100);
	SetVertex(shape2.vertex[3],100,-100,-100);
	SetVertex(shape2.vertex[4],0,100,0);
	SetPolygon(shape2.polygon[0], 2,3,0,1, RED);
	SetPolygon(shape2.polygon[1], 2,4,3,4, GREEN);
	SetPolygon(shape2.polygon[2], 3,4,1,4, BLUE);
	SetPolygon(shape2.polygon[3], 1,4,0,4, YELLOW);
	SetPolygon(shape2.polygon[4], 0,4,2,4, MAGENTA);

	OBJECT shape3;
	InitialiseObject(shape3,8,0,0,0);
	SetVertex(shape3.vertex[0],-100,0,100);
	SetVertex(shape3.vertex[1],100,0,100);
	SetVertex(shape3.vertex[2],-100,0,-100);
	SetVertex(shape3.vertex[3],100,0,-100);
	SetVertex(shape3.vertex[4],0,200,0);
	SetVertex(shape3.vertex[5],0,-200,0);
	SetPolygon(shape3.polygon[0], 2,4,3,4, RED);
	SetPolygon(shape3.polygon[1], 3,4,1,4, GREEN);
	SetPolygon(shape3.polygon[2], 1,4,0,4, BLUE);
	SetPolygon(shape3.polygon[3], 0,4,2,4, MAGENTA);
	SetPolygon(shape3.polygon[4], 3,5,2,5, YELLOW);
	SetPolygon(shape3.polygon[5], 1,5,3,5, LIGHTBLUE);
	SetPolygon(shape3.polygon[6], 0,5,1,5, LIGHTGREEN);
	SetPolygon(shape3.polygon[7], 2,5,0,5, LIGHTRED);

	OBJECT shape4;
	InitialiseObject(shape4,6,0,0,0);
	SetVertex(shape4.vertex[0], -100, -200, 100);
	SetVertex(shape4.vertex[1], 100, -200, 100);
	SetVertex(shape4.vertex[2], 100, -200, -100);
	SetVertex(shape4.vertex[3], -100, -200, -100);
	SetVertex(shape4.vertex[4], -100, 200, 100);
	SetVertex(shape4.vertex[5], 100, 200, 100);
	SetVertex(shape4.vertex[6], 100, 200, -100);
	SetVertex(shape4.vertex[7], -100, 200, -100);
	SetPolygon(shape4.polygon[0], 0,1,3,2, LIGHTBLUE);
	SetPolygon(shape4.polygon[1], 2,1,6,5, LIGHTGREEN);
	SetPolygon(shape4.polygon[2], 3,2,7,6, CYAN);
	SetPolygon(shape4.polygon[3], 0,3,4,7, YELLOW);
	SetPolygon(shape4.polygon[4], 1,0,5,4, MAGENTA);
	SetPolygon(shape4.polygon[5], 7,6,4,5, RED);

	// ***** Parameters *****

	int input=0,temp=0,x=0,y=500,z=-400,rx=335,ry=0,rz=0;
	float scale=0.5,scale_inc=0.005;
	char *str;

	// ***** Main loop (exits on ESC) *****

	while(input!=27)
	{
		double_buffer();

		// ***** Get user key input *****

		input=GetKey();
		if (input==200) { rx--; if (rx<0) rx+=360; }
		if (input==208) { rx++; if (rx>360) rx-=360; }
		if (input==203) { ry--; if (ry<0) ry+=360; }
		if (input==205) { ry++; if (ry>360) ry-=360; }
		if (input==199) y+=5;
		if (input==207) y-=5;
		if (input==211) x-=5;
		if (input==209) x+=5;

		// ***** Animate objects *****

		temp=(temp+1)%360; // Spin objects

		scale+=scale_inc; if (scale<0.4 || scale>0.6) scale_inc=-scale_inc; // Scale cubes

		// ***** Configure camera *****

		SetCamera(x,y,z, rx,ry,0);

		// ***** Render grid *****

		RenderLine3d(-500,0,1000, 500,0,1000, LIGHTGREEN);
		RenderLine3d(-500,0,0, 500,0,0, LIGHTGREEN);
		RenderLine3d(-500,0,1000, -500,0,0, LIGHTGREEN);
		RenderLine3d(500,0,1000, 500,0,0, LIGHTGREEN);
		RenderLine3d(-500,0,250, 500,0,250, LIGHTGREEN);
		RenderLine3d(-500,0,500, 500,0,500, LIGHTGREEN);
		RenderLine3d(-500,0,750, 500,0,750, LIGHTGREEN);
		RenderLine3d(-250,0,1000, -250,0,0, LIGHTGREEN);
		RenderLine3d(0,0,1000, 0,0,0, LIGHTGREEN);
		RenderLine3d(250,0,1000, 250,0,0, LIGHTGREEN);

		// ***** Render shapes *****

		MatrixAll(shape4.transform, 0,100,1000, 0,temp,temp, scale,scale,scale); RenderObject(shape4);
		MatrixAll(shape2.transform, -500,100,500, temp,0,temp, scale,scale,scale); RenderObject(shape2);
		MatrixAll(shape3.transform, 500,100,500, temp,0,temp, scale,scale,scale); RenderObject(shape3);
		MatrixAll(shape1.transform, 0,100,0, temp,temp,0, scale,scale,scale); RenderObject(shape1);

		// ***** Display camera information *****

		setcolor(WHITE);
		outtextxy(5,5,"Camera : arrow keys,home,end,del,pgdn");
		outtextxy(5,15,"xyz:");
		outtextxy(5,25,"pyr:");
		str=itoa(x,str,10); outtextxy(50,15,str);
		str=itoa(y,str,10); outtextxy(100,15,str);
		str=itoa(z,str,10); outtextxy(150,15,str);
		str=itoa(rx,str,10); outtextxy(50,25,str);
		str=itoa(ry,str,10); outtextxy(100,25,str);
		str=itoa(rz,str,10); outtextxy(150,25,str);

		// ***** Draw a border around the screen *****

		rectangle(0,0,639,349);
	}

	// Clean up and exit
	closegraph();
	exit(1);
}