/********************************************************************
 * File: Scene.cpp
 * Author: Keith Schwarz (htiek@cs.stanford.edu)
 *
 * Implementation of the Scene object, which represents a renderable
 * scene.  The actual rendering code is contained here.
 */
#include "Scene.h"
#include <stdexcept>
#include <cmath>
#include <limits>
#include <cassert>
using namespace std;

/* Ctor just sets everything to the default value. */
Copper3D::Scene::Scene() {
}

/* Dtor does nothing; objects should handle that themselves. */
Copper3D::Scene::~Scene() {
}

void Copper3D::Scene::addElement(const Ptr<SceneElement>& elem) {
	/* Check that this element isn't NULL. */
	if (!elem)
		throw invalid_argument("Attempted to add a null element to a scene.");

	/* Check that the model exists. */
	if (mModels.count(elem->modelName()) == 0)
		throw invalid_argument("No model has name \"" + elem->modelName() + "\" in this scene.");

	/* Check that the element doesn't already exist. */
	if (mElements.count(elem->name()) != 0)
		throw invalid_argument("A scene element with name \"" + elem->name() + "\" already exists in this scene.");

	/* Add the element! */
	mElements[elem->name()] = elem;
}

Copper3D::Ptr<Copper3D::SceneElement> Copper3D::Scene::element(const string& name) {
	/* Look up the element, returning it if found and failing otherwise. */
	map<string, Ptr<SceneElement> >::iterator result = mElements.find(name);
	return result != mElements.end()? result->second : NULL;
}

/* Removes an element. */
void Copper3D::Scene::removeElement(const string& name) {
	mElements.erase(name);
}

/* After basic sanity checks, adds a model to the scene. */
void Copper3D::Scene::addModel(const Ptr<Model>& model) {
	/* Null-check. */
	if (!model)
		throw invalid_argument("Attempted to add a null model to the scene.");

	/* Now, check that we don't already have a model of this name. */
	if (mModels.count(model->name()) != 0)
		throw invalid_argument("A model with name \"" + model->name() + "\" already exists");

	/* Add the model! */
	mModels[model->name()] = model;
}

Copper3D::Ptr<Copper3D::Model> Copper3D::Scene::model(const string& name) {
	/* Look up the model, returning it if found and failing otherwise. */
	map<string, Ptr<Model> >::iterator result = mModels.find(name);
	return result != mModels.end()? result->second : NULL;
}

/* Removes a model.  This also removes any elements using that model. */
void Copper3D::Scene::removeModel(const string& name) {
	/* Wipe out the model. */
	mModels.erase(name);

	/* Wipe out all element using the model. */
	map<string, Ptr<SceneElement> >::iterator elemItr = mElements.begin();
	while (elemItr != mElements.end()) {
		/* Remove it if the model name matches. */
		if (elemItr->second->modelName() == name)
			mElements.erase(elemItr++);
		else ++elemItr;
	}
}

/* Set/get the camera. */
Copper3D::Camera Copper3D::Scene::camera() const {
	return mCamera;
}
void Copper3D::Scene::setCamera(const Camera& camera) {
	mCamera = camera;
}

/* Set/get the display. */
Copper3D::Ptr<Copper3D::Display> Copper3D::Scene::display() {
	return mDisplay;
}
void Copper3D::Scene::setDisplay(const Ptr<Display>& disp) {
	mDisplay = disp;
}

/* Factory. */
Copper3D::Scene* Copper3D::Scene::New() {
	return new Scene;
}

/* Helper function which returns a 4x4 matrix that projects points in space onto the
 * xy-parallel plane passing through z = 1.  This matrix works by transforming
 * points of the form (x, y, z, 1) into points (x, y, z, z).  This is equivalent
 * to setting them to (x/z, y/z, 1, 1).  The matrix is
 *
 * | 1 0 0 0 |
 * | 0 1 0 0 |
 * | 0 0 1 0 |
 * | 0 0 1 0 |
 */
static Matrix<4, 4> ProjectToScreenMatrix() {
	Matrix<4, 4> result = Identity<4, double>();
	result[3][3] = 0.0;
	result[3][2] = 1.0;
	return result;
}

/* A matrix which inverts the camera transform.  If the camera has orientation
 * r, u, t and position x, y, z, then we want to invert the translation to get
 * back to the origin, and the invert the orientation transform.
 *
 * To get back to the origin, we use this matrix:
 *
 * |1 0 0 -x|
 * |0 1 0 -y|
 * |0 0 1 -z|
 * |0 0 0  1|
 *
 * Now, the matrix for the camera transform is
 *
 * |r0 u0 t0 0|
 * |r1 u1 t1 0|
 * |r2 u2 t2 0|
 * | 0  0  0 1|
 *
 * Since this matrix is orthogonal, its inverse is its transpose:
 *
 * |r0 r1 r2 0|
 * |u0 u1 u2 0|
 * |t0 t1 t2 0|
 * | 0  0  0 1|
 *
 * Our matrix is the product of these two.
 */
static Matrix<4, 4> InvertCameraMatrix(const Copper3D::Camera& c) {
	/* Build the reorientation matrix. */
	Matrix<4, 4> reorient;
	reorient[3][0] = reorient[3][1] = reorient[3][2] = 0.0;
	reorient[0][3] = reorient[1][3] = reorient[2][3] = 0.0;
	reorient[3][3] = 1.0;

	Copper3D::Orientation o = c.orientation();
	copy(o.r().begin(), o.r().end(), reorient.row_begin(0));
	copy(o.u().begin(), o.u().end(), reorient.row_begin(1));
	copy(o.t().begin(), o.t().end(), reorient.row_begin(2));

	/* Build the translate matrix. */
	Matrix<4, 4> translate = Identity<4, double>();
	translate[0][3] = -c.position()[0];
	translate[1][3] = -c.position()[1];
	translate[2][3] = -c.position()[2];

	/* First translate, then reorient. */
	return reorient * translate;
}

/* Given a vector (x, y, z), returns the vector (x, y, z, 1) */
static Vector<4> WidenVector(const Vector<3>& v) {
	Vector<4> result;
	copy(v.begin(), v.end(), result.begin());
	result[3] = 1.0;

	return result;
}

/* Rounds a floating-point value. */
static int Round(double val) {
	/* Add 0.5 to value and take the floor. */
	return int(floor(val + 0.5));
}

/* Draws a steep line (slope > 1) by marching up the y values and computing where the
 * x values should be.
 */
static void PlotSteepLine(const Copper3D::Ptr<Copper3D::Display>& display,
					      int x0, int y0,
					      int x1, int y1) {
	/* Ensure that y0 <= y1 */
	if (y0 > y1) {
		swap(x0, x1);
		swap(y0, y1);
	}

	double slope = double(x1 - x0) / double(y1 - y0);
	double currX = x0;

	for (int y = y0; y <= y1; ++y, currX += slope) {
		int x = Round(currX);
		if (x >= 0 && y >= 0 && x < display->width() && y < display->height())
			display->plotPixel(x, y, Copper3D::Color(1.0f, 1.0f, 1.0f));
	}
}

/* Draws a shallow line (|slope| <= 1) by marching up the x values and computing where the
 * y values should be.
 */
static void PlotShallowLine(const Copper3D::Ptr<Copper3D::Display>& display,
				 	        int x0, int y0,
					        int x1, int y1) {
	/* Ensure that x0 <= x1 */
	if (x0 > x1) {
		swap(x0, x1);
		swap(y0, y1);
	}

	double slope = double(y1 - y0) / double(x1 - x0);
	double currY = y0;

	for (int x = x0; x <= x1; ++x, currY += slope) {
		int y = Round(currY);
		if (x >= 0 && y >= 0 && x < display->width() && y < display->height())
			display->plotPixel(x, y, Copper3D::Color(1.0f, 1.0f, 1.0f));
	}
}

/* Draws a line between two points using only pixel-plotting as a primitive. */
static void DrawLine(const Copper3D::Ptr<Copper3D::Display>& display,
					 int x0, int y0,
					 int x1, int y1) {
	/* There are four possible cases:
	 *
	 * 1 <  slope
	 * 0 <= slope <= 1
	 * -1 <= slope < 0
	 * slope < -1
	 *
	 * If we're in the middle two cases, then the line will consist of several horizontal
	 * bars.  If we're in the first or fourth case.  We'll thus divvy this up into one
	 * of several routines to actually handle the plotting.
	 */
	int dx = abs(x0 - x1);
	int dy = abs(y0 - y1);

	if (dy > dx) // Slope > 1 or Slope < 1
		PlotSteepLine(display, x0, y0, x1, y1);
	else
		PlotShallowLine(display, x0, y0, x1, y1);
}

/* Renders a line. */
static void RenderLine(vector< Vector<4> > points,
					   const Copper3D::Ptr<Copper3D::Display> display,
					   size_t origin, size_t destination) {
	/* The final points need to be scaled by their homogenous component. */
	double x0 = points[origin][0] / points[origin][3];
	double y0 = points[origin][1] / points[origin][3];

	double x1 = points[destination][0] / points[destination][3];
	double y1 = points[destination][1] / points[destination][3];

	/* Invert y, since the screen grows downward instead of upward. */
	y0 *= -1.0;
	y1 *= -1.0;

	/* Translate from [-1, 1]x[-1, 1] to [0, 0] x [2, 2] */
	x0 += 1.0;
	y0 += 1.0;
	x1 += 1.0;
	y1 += 1.0;

	/* Scale from [0, 0] x [2, 2] to [0, 0] x [2, 2] */
	x0 *= display->width() / 2;
	y0 *= display->height() / 2;
	x1 *= display->width() / 2;
	y1 *= display->height() / 2;

	/* Now that we have the positions, plot the line. */
	DrawLine(display, x0, y0, x1, y1);
}

/* Gives a matrix that converts a point in model space to a point in actual space.
 * If we are given an orientation, this corresponds to:
 * 1. Transforming the basis to point in that orientation
 * 2. Translating the points to the proper location.
 *
 * This first matrix is
 *
 * |r0 u0 t0 0|
 * |r1 u1 t1 0|
 * |r2 u2 t2 0|
 * | 0  0  0 1|
 *
 * This second matrix is
 *
 * |1 0 0 x|
 * |0 1 0 y|
 * |0 0 1 z|
 * |0 0 0 1|
 */
Matrix<4, 4> ModelToWorld(const Copper3D::Ptr<Copper3D::SceneElement>& element) {
	Copper3D::Orientation o = element->orientation();
	Vector<3> position = element->position();

	/* Build the translate matrix. */
	Matrix<4, 4> translate = Identity<4, double>();
	translate[0][3] = position[0];
	translate[1][3] = position[1];
	translate[2][3] = position[2];

	/* Build the reorient matrix.  We build it transposed and then
	 * transpose it at the end.
	 */
	Matrix<4, 4> reorient;
	reorient[3][0] = reorient[3][1] = reorient[3][2] = 0.0;
	reorient[0][3] = reorient[1][3] = reorient[2][3] = 0.0;
	reorient[3][3] = 1.0;

	copy(o.r().begin(), o.r().end(), reorient.row_begin(0));
	copy(o.u().begin(), o.u().end(), reorient.row_begin(1));
	copy(o.t().begin(), o.t().end(), reorient.row_begin(2));

	/* Reorient, then translate. */
	return translate * Transpose(reorient);
}
static void DrawTriangle(const vector< Vector<4> >& screenPoints,
						 const vector< Vector<4> >& rawPoints,
						 const Copper3D::Ptr<Copper3D::Display>& display,
						 const Copper3D::Triangle& triangle)
{
	RenderLine(screenPoints, display, triangle.v0(), triangle.v1());
	RenderLine(screenPoints, display, triangle.v1(), triangle.v2());
	RenderLine(screenPoints, display, triangle.v2(), triangle.v0());
}

/* The actual code for rendering a scene.  This works as follows:
 * 1. Compute the world-to-screen transform.
 * 2. For each scene element:
 *    1. Compute the model-to-world transform.
 *    2. Transform all points using the composition of this transform
 *       and the world-to-screen transform.
 *    3. Render all the triangles in the model under the new coordinate
 *       system.
 */
void Copper3D::Scene::render() {
	/* Make sure we have somewhere to write. */
	if (!display())
		throw runtime_error("No display attached to the scene!");

	display()->clear();

	/* Get the matrix to invert the camera. */
	Matrix<4, 4> invertCamera = InvertCameraMatrix(camera());

	/* Render each element. */
	for (map<string, Ptr<SceneElement> >::iterator itr = mElements.begin();
		 itr != mElements.end(); ++itr) {
		Ptr<Model> elementModel = model(itr->second->modelName());

		/* Widen the model points from 3-space to 4-homogeneous space. */
		vector< Vector<4> > widePoints(elementModel->numPoints());
		transform(elementModel->point_begin(), elementModel->point_end(), // Model points
			      widePoints.begin(), // Store in widePoints
				  WidenVector); // Widening the vectors

		/* Get the transform matrix to put everything in place. */
		Matrix<4, 4> transformMatrix = invertCamera * ModelToWorld(itr->second);

		/* Transform each point. */
		for (size_t i = 0; i < widePoints.size(); ++i)
			widePoints[i] = transformMatrix * widePoints[i];

		/* We now have points in the canonical orientation.  The next step is
		 * to compute where they appear on-screen.
		 */
		Matrix<4, 4> projectionMatrix = ProjectToScreenMatrix();
		vector< Vector<4> > screenPoints(widePoints.size());
		for (size_t i = 0; i < widePoints.size(); ++i)
			screenPoints[i] = projectionMatrix * widePoints[i];

		/* Iterate over the triangles and render those worth rendering. */
		for (Model::triangle_iterator tri = elementModel->triangle_begin();
			 tri != elementModel->triangle_end(); ++tri)
			DrawTriangle(screenPoints, widePoints, display(), *tri);
	}
	display()->display();
}