////////////////////////////////////////////////////////////////////////////////
// MeshPolygon.cpp
// Implementation of a class that stores mesh polygons
// Copyright Bjoern Ganster
// Written since 2001
////////////////////////////////////////////////////////////////////////////////

#include "intersections.h"
#include "Mesh.h"
#include "MeshPolygon.h"

#define FILE_NUMBER FILE_NO_MESH_POLYGON_CPP

////////////////////////////////////////////////////////////////////////////////
// Constructor

MeshPolygon::MeshPolygon (size_t pointCount, Mesh* parent, size_t newIndex)
: VirtualClass ("MeshPolygon", MeshPolygonID),
  m_parent(parent),
  m_manText(nullptr),
  mTextured(false)
{
	SET_SCOPE;
	m_manText = NULL;
	isVisible = true;
	PerVertexLighting = false;
	mark = 0;
	mVertexIndices.resize(pointCount);
	RETURN;
}

////////////////////////////////////////////////////////////////////////////////
// Destructor

MeshPolygon::~MeshPolygon ()
{
}

////////////////////////////////////////////////////////////////////////////////
// Set vertex coordinates

void MeshPolygon::setVertexIndex(unsigned int indexInPoly, unsigned int indexInMesh)
{
	if (indexInPoly < mVertexIndices.size() && indexInMesh < m_parent->getVertexCount()) {
        mVertexIndices[indexInPoly] = indexInMesh;
    }
}

////////////////////////////////////////////////////////////////////////////////
// Get index into mesh vertices

unsigned int MeshPolygon::getVertexIndex(size_t indexInPoly) const
{
    if (indexInPoly < mVertexIndices.size()) {
        return mVertexIndices[indexInPoly];
    } else {
        return 0;
    }
}

////////////////////////////////////////////////////////////////////////////////
// Find opposed edges for all edges in the polygon

void MeshPolygon::findOpposedEdges()
{
   // Finding opposed edges works only once all edges of the polygon have been
   // created (otherwise, the next edge, containing the next point, is always
   // missing)
/*   for (unsigned int i = 0; i < m_pointCount; i++) {
      edges[i].FindOpposedEdge ();
   }*/
}

////////////////////////////////////////////////////////////////////////////////
// Render a polygon

/*void MeshPolygon::render(bool skipTransparentPolygons)
{
	if (isVisible) {
		double u, v;
		normal.glNormal();
		glBegin(GL_POLYGON);
		if (PerVertexLighting) {
			for (unsigned int i = 0; i < m_pointCount; i++) {
				//MeshPolygonEdge& edge = edges[i];
				getTexCoords(i, u, v);
				glTexCoord2d(u, v);
				size_t pi = m_pointIndices[i];
				m_parent->glVertex(pi);
			}
		} else {
			glNormal();
			for (unsigned int i = 0; i < m_pointCount; i++) {
				getTexCoords(i, u, v);
				glTexCoord2d(u, v);
				size_t pi = m_pointIndices[i];
				//if (pi < m_parent->getPointCount())
				m_parent->glVertex(pi);
			}
		}
		glEnd();
	}
}*/

void MeshPolygon::render(bool hasTexture, bool useTransformedVertices) const
{
    /*std::vector<double> pointCoords(3*mVertexCount);
    for (size_t i = 0; i < mVertexCount; ++i) {
        auto j = m_pointIndices[i];
        Point3D p;
        m_parent->getPoint(j, p);
        pointCoords[3*i]   = p.x;
        pointCoords[3*i+1] = p.y;
        pointCoords[3*i+2] = p.z;
    }
    
    glVertexPointer (3, GL_DOUBLE, 0, pointCoords.data());

   if (m_textureCoords.size() > 0 && hasTexture) {
      glTexCoordPointer (2, GL_DOUBLE, 0, m_textureCoords.data());
   }*/

	//normal.glNormal();
	(-transformedNormal).glNormal();
	//m_parent->setRenderingBuffers(mIndexInMesh, mVertexCount, mTextured);

	glBegin(GL_POLYGON);
	for (size_t i = 0; i < mVertexIndices.size(); ++i) {
		if (i < mTexCoordIndices.size() && hasTexture) {
			auto ti = mTexCoordIndices[i];
			double u = 0, v = 0;
			m_parent->getTexCoords(ti, u, v);
			glTexCoord2d(u, v);
		}
		auto vi = mVertexIndices[i];
		if (useTransformedVertices) {
			m_parent->glTransformedVertex(vi);
		} else {
			m_parent->glVertex(vi);
		}
	}
	glEnd();
}

// Set texture coordinates for a vertex
void MeshPolygon::setTexCoordIndex (unsigned int indexInPoly, unsigned int indexInMeshTexCoords)
{
	if (indexInPoly < mVertexIndices.size()) {
		if (indexInPoly >= mTexCoordIndices.size()) {
			mTexCoordIndices.resize(mVertexIndices.size());
		}
		mTexCoordIndices[indexInPoly] = indexInMeshTexCoords;
	}
	mTextured = true;
}

// Get texture coordinate index
unsigned int MeshPolygon::getTexCoordIndex(unsigned int indexInPoly) const
{
    if (indexInPoly < mTexCoordIndices.size()) {
        return mTexCoordIndices[indexInPoly];
    } else {
        return 0;
    }
}

// Get vertex coordinates
Point3D MeshPolygon::getVertexCoords(size_t indexInPoly) const
{
	if (m_parent != nullptr) {
		auto vi = getVertexIndex(indexInPoly);
		Point3D p;
		m_parent->getVertex(vi, p);
		return p;
	} else {
		return Point3D();
	}
}

// Get transformed coordinates
Point3D MeshPolygon::getTransformedVertexCoords(size_t indexInPoly, const Matrix& M) const
{
    Point3D p = getVertexCoords(indexInPoly);
    return M.Transform(p);
}


// Set vertex coordinates
/*void MeshPolygon::setVertexCoords (size_t indexInPoly, double x, double y, double z)
{
    if (m_parent != nullptr) {
        m_parent->setVertexCoords(mIndexInMesh, indexInPoly, x, y,z);
        m_parent->setPoliesDirty();
    }
}

// Use mesh vertex for this polygon
void MeshPolygon::useVertex(size_t indexInPoly, size_t indexInMesh)
{
    Point3D p;
    m_parent->getPoint(indexInMesh, p);
    setVertexCoords(indexInPoly, p);
}*/

MeshPolygon* MeshPolygon::copy(const MeshPolygon* otherPoly, Mesh* parent)
{
    if (otherPoly != nullptr) {
		SET_SCOPE;
        MeshPolygon* newPoly = new MeshPolygon(otherPoly->getVertexCount(), parent, 0);
        newPoly->mVertexIndices = otherPoly->mVertexIndices;
        newPoly->mTexCoordIndices = otherPoly->mTexCoordIndices;
        newPoly->mTextured = otherPoly->mTextured;
        newPoly->isVisible = otherPoly->isVisible;
        newPoly->num = otherPoly->num;
        newPoly->mark = otherPoly->mark;
        newPoly->transformedNormal = otherPoly->transformedNormal;
        newPoly->PerVertexLighting = otherPoly->PerVertexLighting;
        newPoly->m_manText = otherPoly->m_manText;
        RETURN newPoly;
    } else {
        return nullptr;
    }
}

// Get the plane containing the polygon
bool MeshPolygon::getPlane(Plane& p) const 
{
	SET_SCOPE;
	if (getVertexCount() >= 3) {
		SET_OP;
		const Mesh* myParent = getParent();
		int indexInMesh0 = getVertexIndex(0);
		Point3D p0 = myParent->getTransformedVertex(indexInMesh0);
		int indexInMesh1 = getVertexIndex(1);
		Point3D p1 = myParent->getTransformedVertex(indexInMesh1);
		int indexInMesh2 = getVertexIndex(2);
		Point3D p2 = myParent->getTransformedVertex(indexInMesh2);
		SET_OP;
		p = Plane(p0, p1, p2);
		RETURN true;
	} else {
		RETURN false;
	}
}

// Get the line segment ls where this polygon intersects a straight line sl
bool MeshPolygon::intersects(const StraightLine& sl, LineSegment& ls) const
{
	SET_SCOPE;
	const Mesh* myParent = getParent();
	if (myParent == nullptr) {
		RETURN false;
	}

	int pointsFound = 0;
	Point3D a, b;

	for (size_t i = 0; i < getVertexCount(); ++i) {
		// interpret every edge as a line segment
		SET_OP;
		auto i1 = getVertexIndex(i);
		auto i2 = getVertexIndex((i+1) % getVertexCount());
		Point3D p1 = myParent->getTransformedVertex(i1);
		Point3D p2 = myParent->getTransformedVertex(i2);
		LineSegment ls(p1, p2);

		// find the point in the middle of that edge and sl
		SET_OP;
		Point3D p;
		ls.findPointBetween(sl, p);
		double dist = ls.distanceTo(p);
		if (dist < 0.001) {
			switch (pointsFound) {
			case 0:
				SET_OP;
				pointsFound = 1;
				a = p;
				break;
			case 1:
				SET_OP;
				pointsFound = 2;
				b = p;
				break;
			default:
				// We already have two points - keep the two furthest apart
				{
					SET_OP;
					double ab = (a-b).length();
					double ap = (a-p).length();
					double bp = (b-p).length();

					if (ap > ab && ap > bp) {
						b = p;
					}
					if (bp > ab && bp > ap) {
						a = p;
					}
				}
				break;
			}
		}
	}

	// Use the gathered data to return a result
	SET_OP;
	switch (pointsFound) {
		case 0:
			RETURN false;
		case 1:
			// Odd case, not sure this will actually happen
			// Proper treatment would require that we pass a point as the result in this case
			ls = LineSegment(a,b);
			RETURN true;
		default:
			ls = LineSegment(a,b);
			RETURN true;
	}
}

// Check for collision with another polygon
// todo: there should be autotests for this
bool MeshPolygon::collides(const MeshPolygon* other) const
{
	SET_SCOPE;
	const Mesh* myParent = getParent();
	const Mesh* otherParent = other->getParent();

	// Form two planes containing both polygons
	Plane myplane, otherPlane;
	if (other == nullptr 
	||  myParent == nullptr
	||  otherParent == nullptr
	||  !getPlane(myplane)
	||  !other->getPlane(otherPlane)) 
	{
		RETURN false;
	}

	// Check the intersection of p1, p2 against the polygons
	StraightLine sl;
	auto intersectionType = myplane.intersects(otherPlane, sl);
	switch (intersectionType) {
		case ObjectsIntersect:
			{
				// Both planes may have a straight line in common
				LineSegment s1, s2;
				if (intersects(sl, s1) && other->intersects(sl, s2)) {
					Point3D intersection;
					double dist = s1.distanceTo(s2);
					double len = s1.length() + s2.length();
					if (dist < 0.01 * len) {
						RETURN true;
					} else { 
						RETURN false;
					}
				} else {
					RETURN false;
				}
			}
		case ObjectsDontIntersect:
			RETURN false;
		case ObjectsParallel:
		default:
			// If the planes are parallel, the polygons are parallel, too
			// in this case, the result could be area surrounded by a new polygon
			// Not sure this case matters right now ...
			RETURN false;
	}
}

// Calculate the center of the polygon

Point3D MeshPolygon::getCenter() const
{
	if (getVertexCount() == 0) {
		return Point3D();
	}

	auto j = getVertexIndex(0);
	Point3D mid = m_parent->getTransformedVertex(j);
	if (getVertexCount() == 1) {
		return mid;
	}

	for (size_t i = 1; i < getVertexCount(); ++i) {
		auto j = getVertexIndex(i);
		Point3D p = m_parent->getTransformedVertex(j);
		mid += p;
	}

	mid = mid / getVertexCount();
	return mid;
}

////////////////////////////////////////////////////////////////////////////////
// Calculate the distance of a point from a polygon

double MeshPolygon::distanceTo(const Point3D& p) const
{
	SET_SCOPE;
	Plane polyPlane;
	if (!getPlane(polyPlane)) {
		RETURN false;
	}

	Point3D mid = getCenter();

	// Form planes from every line segment that are perpendicular to the polygon's plane and contain the respective line segment
	double result = 0.0;
	int outside = 0;
	for (size_t i = 0; i < getVertexCount(); ++i) {
		auto i1 = getVertexIndex(i);
		Point3D p1 = m_parent->getTransformedVertex(i1);
		auto i2 = getVertexIndex((i+1) % getVertexCount());
		Point3D p2 = m_parent->getTransformedVertex(i2);
		Plane edgePlane(p1, p2, p1 + polyPlane.n);

		// If p lies outside one of the planes, calculate the distance from that plane
		double midHalfSpaceTestResult = edgePlane.halfSpaceTest(mid);
		double pHalfSpaceTestResult = edgePlane.halfSpaceTest(p);

		// We cannot be sure of which side is outside, but it is safe to assume the side with the polygon center defines the "insde" of the polygon
		bool isOutside = false;
		if ((midHalfSpaceTestResult >= 0 && pHalfSpaceTestResult < 0.0)
		||  (midHalfSpaceTestResult <= 0 && pHalfSpaceTestResult > 0.0))
		{
			isOutside = true;
		}

		if (isOutside) {
			if (outside == 0) {
				LineSegment ls(p1, p2);
				result = ls.distanceTo(p);
			} else {
				// If there are several planes that p is outside of, we want the minimum distance
				LineSegment ls(p1, p2);
				double candidate = ls.distanceTo(p);
				if (candidate < result) {
					result = candidate;
				}
			}
			++outside;
		}
	} 

	// If p is on the inside of all tested planes, the p's distance from the this is given by p's distance from the polygon's plane
	if (outside == 0) {
		result = polyPlane.halfSpaceTest(p);
	}
	RETURN result;
}

////////////////////////////////////////////////////////////////////////////////
// Assuming that other moves with vector movement, check for collision with other polygon

bool MeshPolygon::collides(const MeshPolygon* other, const Point3D& movement) const
{
	if (other == nullptr) {
		return false;
	}

	SET_SCOPE;
	// Form a line segment ls from each vertex' old and new positions. If ls
	// intersects this polygon, we know there is collision.
	// todo: this doesn't cover all cases. It is possible that there is a collision that would not be detected this way, e.g. if other is larger than this.

	for (size_t i = 0; i < other->getVertexCount(); ++i) {
		auto j = other->getVertexIndex(i);
		Point3D p = other->m_parent->getTransformedVertex(j);
		Point3D q = p + movement;
		LineSegment ls(p, q);
		if (intersectsTransformedPoly(this, ls) == ObjectsIntersect) {
			RETURN true;
		}
	}

	// No intersection found ...
	RETURN false;
}

////////////////////////////////////////////////////////////////////////////////
// If the ray given by origin, dir intersects the Triangle, this function
// returns the distance of the intersection, otherwise, it returns -1

void testProximity (const Triangle& T, const Point3D& origin, 
    const Point3D& dir, MeshPolygon* poly, double& minDistSoFar, Point3D& intersection)
{
	Point3D candidate;
	Ray ray (origin, dir);
	int testResult = ray.intersects (T, candidate);
	double dist = (candidate - origin).length();

	if (testResult == ObjectsIntersect && dist < minDistSoFar) {
		minDistSoFar = dist;
		intersection = candidate;
	}
}

////////////////////////////////////////////////////////////////////////////////
// Test if the ray given by origin, dir intersects ro or one of its childs,
// at a nearer distance than minDistSoFar. If it does, set minDistSoFar,
// and returns the nearest intersected object

RenderableObject* traverseScene (const Point3D& origin, const Point3D& dir, RenderableObject* ro, double& minDistSoFar, Point3D& intersection)
{
	if (ro == nullptr) {
		return nullptr;
	}

	SET_SCOPE;
	RenderableObject* result = nullptr;

	// Test if ro has child objects
	for (unsigned int i = 0; i < ro->getObjectCount(); i++) { 
		RenderableObject* child = ro->getObject (i);
		double newDist = minDistSoFar;
		RenderableObject* candidate = traverseScene (origin, dir, child, newDist, intersection);
		if (newDist < minDistSoFar) {
			result = candidate;
			minDistSoFar = newDist;
		}
	}

	Mesh* mesh = dynamic_cast <Mesh*> (ro);
	if (mesh == NULL) {
		RETURN result;
	}

	Point3D meshMinCoords, meshMaxCoords;
	if (mesh->getMinCoords(meshMinCoords)
	&&  mesh->getMaxCoords(meshMaxCoords))
	{
		Point3D meshMid = 0.5 * (meshMinCoords + meshMaxCoords);
		double meshSize = (meshMaxCoords - meshMinCoords).length();

		if (meshSize == 0) {
			RETURN result;
		}

		Ray ray(origin, dir);
		double distFromRay = ray.distanceTo(meshMid);

		if (distFromRay <= meshSize) {
			// Test the ray given by origin, dir against the polygons in mesh
			for (size_t i = 0; i < mesh->getPolygonCount(); ++i) {
				// represent a polygon with more than 3 vertices as several triangles, regardless of how many vertices there are
				// in the polygon
				MeshPolygon* poly = mesh->getPolygon(i);
				for (size_t j = 1; j+1 < poly->getVertexCount(); ++j) {
					unsigned int p0i = poly->getVertexIndex (0);
					unsigned int p1i = poly->getVertexIndex (j);
					unsigned int p2i = poly->getVertexIndex (j+1);

					Point3D p0 = mesh->getTransformedVertex(p0i);
					Point3D p1 = mesh->getTransformedVertex(p1i);
					Point3D p2 = mesh->getTransformedVertex(p2i);

					Triangle T (p0, p1, p2);
					double newDist = minDistSoFar;
					Point3D intersectionCandidate = intersection;
					testProximity (T, origin, dir, poly, newDist, intersectionCandidate);
					if (newDist < minDistSoFar) {
						result = mesh;
						minDistSoFar = newDist;
						intersection = intersectionCandidate;
					}
				}
			}
		}
	}

	RETURN result;
}

// Get min and max from the transformed coordinates
void MeshPolygon::getTransformedMinMax(Point3D& polyMin, Point3D& polyMax) const
{
	if (getVertexCount() == 0) {
		return;
	}

	SET_SCOPE;
	int indexInMesh = getVertexIndex(0);
	Point3D p = m_parent->getTransformedVertex(indexInMesh);
	polyMin = p;
	polyMax = p;

	SET_OP;
	for (size_t j = 1; j < getVertexCount(); ++j) {
		int indexInMesh = getVertexIndex(j);
		Point3D p = m_parent->getTransformedVertex(indexInMesh);
		polyMin = MinCoords(polyMin, p);
		polyMax = MaxCoords(polyMax, p);
	}

	RETURN;
}

// Get transformed bounding box
BoundingBox MeshPolygon::getTransformedBB() const
{
	Point3D min, max;
	getTransformedMinMax(min, max);
	BoundingBox polyBB(min, max);
	return polyBB;
}

Point3D MeshPolygon::getTransformedNormal() const
{
	return transformedNormal;
}

// Test if the given LineSegment intersects a polygon
IntersectionResult intersectsTransformedPoly(const MeshPolygon* poly, const LineSegment& ls)
{
	Plane polyPlane;
	if (poly->getPlane(polyPlane)) {
		Point3D intersection;
		if (ls.intersects(polyPlane, intersection) == ObjectsIntersect) {
			auto dist = poly->distanceTo(intersection);
			if (dist < 0.001) {
				return ObjectsIntersect;
			}
		}
	}

	return ObjectsDontIntersect;
}
