//**************************************************************************
//**
//**	See jlquake.txt for copyright info.
//**
//**	This program is free software; you can redistribute it and/or
//**  modify it under the terms of the GNU General Public License
//**  as published by the Free Software Foundation; either version 2
//**  of the License, or (at your option) any later version.
//**
//**	This program is distributed in the hope that it will be useful,
//**  but WITHOUT ANY WARRANTY; without even the implied warranty of
//**  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
//**  included (gnu.txt) GNU General Public License for more details.
//**
//**************************************************************************
// tr_marks.c -- polygon projection on the world polygons

// HEADER FILES ------------------------------------------------------------

#include "../client.h"
#include "local.h"

// MACROS ------------------------------------------------------------------

#define MAX_VERTS_ON_POLY		64

#define MARKER_OFFSET			0	// 1

#define SIDE_FRONT	0
#define SIDE_BACK	1
#define SIDE_ON		2

// TYPES -------------------------------------------------------------------

// EXTERNAL FUNCTION PROTOTYPES --------------------------------------------

// PUBLIC FUNCTION PROTOTYPES ----------------------------------------------

// PRIVATE FUNCTION PROTOTYPES ---------------------------------------------

// EXTERNAL DATA DECLARATIONS ----------------------------------------------

// PUBLIC DATA DEFINITIONS -------------------------------------------------

// PRIVATE DATA DEFINITIONS ------------------------------------------------

// CODE --------------------------------------------------------------------

//==========================================================================
//
//	R_ChopPolyBehindPlane
//
//	Out must have space for two more vertexes than in
//
//==========================================================================

static void R_ChopPolyBehindPlane(int numInPoints, vec3_t inPoints[MAX_VERTS_ON_POLY],
	int *numOutPoints, vec3_t outPoints[MAX_VERTS_ON_POLY], 
	vec3_t normal, vec_t dist, vec_t epsilon)
{
	// don't clip if it might overflow
	if (numInPoints >= MAX_VERTS_ON_POLY - 2)
	{
		*numOutPoints = 0;
		return;
	}

	int counts[3];
	counts[0] = counts[1] = counts[2] = 0;

	// determine sides for each point
	float dists[MAX_VERTS_ON_POLY + 4];
	int sides[MAX_VERTS_ON_POLY + 4];
	for (int i = 0; i < numInPoints; i++)
	{
		float dot = DotProduct(inPoints[i], normal);
		dot -= dist;
		dists[i] = dot;
		if (dot > epsilon)
		{
			sides[i] = SIDE_FRONT;
		}
		else if (dot < -epsilon)
		{
			sides[i] = SIDE_BACK;
		}
		else
		{
			sides[i] = SIDE_ON;
		}
		counts[sides[i]]++;
	}
	sides[numInPoints] = sides[0];
	dists[numInPoints] = dists[0];

	*numOutPoints = 0;

	if (!counts[0])
	{
		return;
	}
	if (!counts[1])
	{
		*numOutPoints = numInPoints;
		Com_Memcpy(outPoints, inPoints, numInPoints * sizeof(vec3_t));
		return;
	}

	for (int i = 0; i < numInPoints; i++)
	{
		float* p1 = inPoints[i];
		float* clip = outPoints[*numOutPoints];
		
		if (sides[i] == SIDE_ON)
		{
			VectorCopy(p1, clip);
			(*numOutPoints)++;
			continue;
		}
	
		if (sides[i] == SIDE_FRONT)
		{
			VectorCopy(p1, clip);
			(*numOutPoints)++;
			clip = outPoints[*numOutPoints];
		}

		if (sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i])
		{
			continue;
		}

		// generate a split point
		float* p2 = inPoints[(i + 1) % numInPoints];

		float d = dists[i] - dists[i + 1];
		float dot;
		if (d == 0)
		{
			dot = 0;
		}
		else
		{
			dot = dists[i] / d;
		}

		// clip xyz

		for (int j = 0; j < 3; j++)
		{
			clip[j] = p1[j] + dot * (p2[j] - p1[j]);
		}

		(*numOutPoints)++;
	}
}

//==========================================================================
//
//	R_BoxSurfaces_r
//
//==========================================================================

static void R_BoxSurfaces_r(mbrush46_node_t *node, vec3_t mins, vec3_t maxs,
	surfaceType_t **list, int listsize, int *listlength, vec3_t dir)
{
	// do the tail recursion in a loop
	while (node->contents == -1)
	{
		int s = BoxOnPlaneSide(mins, maxs, node->plane);
		if (s == 1)
		{
			node = node->children[0];
		}
		else if (s == 2)
		{
			node = node->children[1];
		}
		else
		{
			R_BoxSurfaces_r(node->children[0], mins, maxs, list, listsize, listlength, dir);
			node = node->children[1];
		}
	}

	// add the individual surfaces
	mbrush46_surface_t** mark = node->firstmarksurface;
	int c = node->nummarksurfaces;
	while (c--)
	{
		if (*listlength >= listsize)
		{
			break;
		}
		mbrush46_surface_t* surf = *mark;
		// check if the surface has NOIMPACT or NOMARKS set
		if ((surf->shader->surfaceFlags & (BSP46SURF_NOIMPACT | BSP46SURF_NOMARKS)) ||
			(surf->shader->contentFlags & BSP46CONTENTS_FOG))
		{
			surf->viewCount = tr.viewCount;
		}
		// extra check for surfaces to avoid list overflows
		else if (*(surf->data) == SF_FACE)
		{
			// the face plane should go through the box
			int s = BoxOnPlaneSide(mins, maxs, &((srfSurfaceFace_t*)surf->data)->plane);
			if (s == 1 || s == 2)
			{
				surf->viewCount = tr.viewCount;
			}
			else if (DotProduct(((srfSurfaceFace_t*)surf->data)->plane.normal, dir) > -0.5)
			{
				// don't add faces that make sharp angles with the projection direction
				surf->viewCount = tr.viewCount;
			}
		}
		else if (*(surfaceType_t*)(surf->data) != SF_GRID)
		{
			surf->viewCount = tr.viewCount;
		}
		// check the viewCount because the surface may have
		// already been added if it spans multiple leafs
		if (surf->viewCount != tr.viewCount)
		{
			surf->viewCount = tr.viewCount;
			list[*listlength] = (surfaceType_t*)surf->data;
			(*listlength)++;
		}
		mark++;
	}
}

//==========================================================================
//
//	R_AddMarkFragments
//
//==========================================================================

static void R_AddMarkFragments(int numClipPoints, vec3_t clipPoints[2][MAX_VERTS_ON_POLY],
	int numPlanes, vec3_t *normals, float *dists,
	int maxPoints, vec3_t pointBuffer,
	int maxFragments, markFragment_t *fragmentBuffer,
	int *returnedPoints, int *returnedFragments,
	vec3_t mins, vec3_t maxs)
{
	// chop the surface by all the bounding planes of the to be projected polygon
	int pingPong = 0;

	for (int i = 0; i < numPlanes; i++)
	{
		R_ChopPolyBehindPlane(numClipPoints, clipPoints[pingPong],
			&numClipPoints, clipPoints[!pingPong], normals[i], dists[i], 0.5);
		pingPong ^= 1;
		if (numClipPoints == 0)
		{
			break;
		}
	}
	// completely clipped away?
	if (numClipPoints == 0)
	{
		return;
	}

	// add this fragment to the returned list
	if (numClipPoints + (*returnedPoints) > maxPoints)
	{
		return;	// not enough space for this polygon
	}

	markFragment_t* mf = fragmentBuffer + *returnedFragments;
	mf->firstPoint = *returnedPoints;
	mf->numPoints = numClipPoints;
	Com_Memcpy(pointBuffer + (*returnedPoints) * 3, clipPoints[pingPong], numClipPoints * sizeof(vec3_t));

	(*returnedPoints) += numClipPoints;
	(*returnedFragments)++;
}

//==========================================================================
//
//	R_MarkFragments
//
//==========================================================================

int R_MarkFragments(int numPoints, const vec3_t *points, const vec3_t projection,
	int maxPoints, vec3_t pointBuffer, int maxFragments, markFragment_t *fragmentBuffer)
{
	//increment view count for double check prevention
	tr.viewCount++;

	vec3_t projectionDir;
	VectorNormalize2(projection, projectionDir);

	// find all the brushes that are to be considered
	vec3_t mins, maxs;
	ClearBounds(mins, maxs);
	for (int i = 0; i < numPoints; i++)
	{
		AddPointToBounds(points[i], mins, maxs);
		vec3_t temp;
		VectorAdd(points[i], projection, temp);
		AddPointToBounds(temp, mins, maxs);
		// make sure we get all the leafs (also the one(s) in front of the hit surface)
		VectorMA(points[i], -20, projectionDir, temp);
		AddPointToBounds(temp, mins, maxs);
	}

	if (numPoints > MAX_VERTS_ON_POLY)
	{
		numPoints = MAX_VERTS_ON_POLY;
	}
	// create the bounding planes for the to be projected polygon
	vec3_t normals[MAX_VERTS_ON_POLY + 2];
	float dists[MAX_VERTS_ON_POLY + 2];
	for (int i = 0 ; i < numPoints ; i++)
	{
		vec3_t v1, v2;
		VectorSubtract(points[(i + 1) % numPoints], points[i], v1);
		VectorAdd(points[i], projection, v2);
		VectorSubtract(points[i], v2, v2);
		CrossProduct(v1, v2, normals[i]);
		VectorNormalizeFast(normals[i]);
		dists[i] = DotProduct(normals[i], points[i]);
	}

	// add near and far clipping planes for projection
	VectorCopy(projectionDir, normals[numPoints]);
	dists[numPoints] = DotProduct(normals[numPoints], points[0]) - 32;
	VectorCopy(projectionDir, normals[numPoints + 1]);
	VectorInverse(normals[numPoints + 1]);
	dists[numPoints + 1] = DotProduct(normals[numPoints + 1], points[0]) - 20;
	int numPlanes = numPoints + 2;

	int numsurfaces = 0;
	surfaceType_t* surfaces[64];
	R_BoxSurfaces_r(tr.world->nodes, mins, maxs, surfaces, 64, &numsurfaces, projectionDir);
	//assert(numsurfaces <= 64);
	//assert(numsurfaces != 64);

	int returnedPoints = 0;
	int returnedFragments = 0;

	for (int i = 0; i < numsurfaces; i++)
	{
		if (*surfaces[i] == SF_GRID)
		{
			srfGridMesh_t* cv = (srfGridMesh_t*)surfaces[i];
			for (int m = 0 ; m < cv->height - 1; m++)
			{
				for (int n = 0; n < cv->width - 1; n++)
				{
					// We triangulate the grid and chop all triangles within
					// the bounding planes of the to be projected polygon.
					// LOD is not taken into account, not such a big deal though.
					//
					// It's probably much nicer to chop the grid itself and deal
					// with this grid as a normal SF_GRID surface so LOD will
					// be applied. However the LOD of that chopped grid must
					// be synced with the LOD of the original curve.
					// One way to do this; the chopped grid shares vertices with
					// the original curve. When LOD is applied to the original
					// curve the unused vertices are flagged. Now the chopped curve
					// should skip the flagged vertices. This still leaves the
					// problems with the vertices at the chopped grid edges.
					//
					// To avoid issues when LOD applied to "hollow curves" (like
					// the ones around many jump pads) we now just add a 2 unit
					// offset to the triangle vertices.
					// The offset is added in the vertex normal vector direction
					// so all triangles will still fit together.
					// The 2 unit offset should avoid pretty much all LOD problems.

					int numClipPoints = 3;

					bsp46_drawVert_t* dv = cv->verts + m * cv->width + n;

					vec3_t clipPoints[2][MAX_VERTS_ON_POLY];
					VectorCopy(dv[0].xyz, clipPoints[0][0]);
					VectorMA(clipPoints[0][0], MARKER_OFFSET, dv[0].normal, clipPoints[0][0]);
					VectorCopy(dv[cv->width].xyz, clipPoints[0][1]);
					VectorMA(clipPoints[0][1], MARKER_OFFSET, dv[cv->width].normal, clipPoints[0][1]);
					VectorCopy(dv[1].xyz, clipPoints[0][2]);
					VectorMA(clipPoints[0][2], MARKER_OFFSET, dv[1].normal, clipPoints[0][2]);
					// check the normal of this triangle
					vec3_t v1, v2;
					VectorSubtract(clipPoints[0][0], clipPoints[0][1], v1);
					VectorSubtract(clipPoints[0][2], clipPoints[0][1], v2);
					vec3_t normal;
					CrossProduct(v1, v2, normal);
					VectorNormalizeFast(normal);
					if (DotProduct(normal, projectionDir) < -0.1)
					{
						// add the fragments of this triangle
						R_AddMarkFragments(numClipPoints, clipPoints,
							numPlanes, normals, dists,
							maxPoints, pointBuffer,
							maxFragments, fragmentBuffer,
							&returnedPoints, &returnedFragments, mins, maxs);

						if (returnedFragments == maxFragments)
						{
							return returnedFragments;	// not enough space for more fragments
						}
					}

					VectorCopy(dv[1].xyz, clipPoints[0][0]);
					VectorMA(clipPoints[0][0], MARKER_OFFSET, dv[1].normal, clipPoints[0][0]);
					VectorCopy(dv[cv->width].xyz, clipPoints[0][1]);
					VectorMA(clipPoints[0][1], MARKER_OFFSET, dv[cv->width].normal, clipPoints[0][1]);
					VectorCopy(dv[cv->width+1].xyz, clipPoints[0][2]);
					VectorMA(clipPoints[0][2], MARKER_OFFSET, dv[cv->width+1].normal, clipPoints[0][2]);
					// check the normal of this triangle
					VectorSubtract(clipPoints[0][0], clipPoints[0][1], v1);
					VectorSubtract(clipPoints[0][2], clipPoints[0][1], v2);
					CrossProduct(v1, v2, normal);
					VectorNormalizeFast(normal);
					if (DotProduct(normal, projectionDir) < -0.05)
					{
						// add the fragments of this triangle
						R_AddMarkFragments(numClipPoints, clipPoints,
							numPlanes, normals, dists,
							maxPoints, pointBuffer,
							maxFragments, fragmentBuffer,
							&returnedPoints, &returnedFragments, mins, maxs);

						if (returnedFragments == maxFragments)
						{
							return returnedFragments;	// not enough space for more fragments
						}
					}
				}
			}
		}
		else if (*surfaces[i] == SF_FACE)
		{
			srfSurfaceFace_t* surf = (srfSurfaceFace_t*)surfaces[i];
			// check the normal of this face
			if (DotProduct(surf->plane.normal, projectionDir) > -0.5)
			{
				continue;
			}

			int* indexes = (int*)((byte*)surf + surf->ofsIndices);
			for (int k = 0; k < surf->numIndices; k += 3)
			{
				vec3_t clipPoints[2][MAX_VERTS_ON_POLY];
				for (int j = 0; j < 3; j++)
				{
					float* v = surf->points[0] + BRUSH46_VERTEXSIZE * indexes[k + j];
					VectorMA(v, MARKER_OFFSET, surf->plane.normal, clipPoints[0][j]);
				}
				// add the fragments of this face
				R_AddMarkFragments(3 , clipPoints,
					numPlanes, normals, dists,
					maxPoints, pointBuffer,
					maxFragments, fragmentBuffer,
					&returnedPoints, &returnedFragments, mins, maxs);
				if (returnedFragments == maxFragments)
				{
					return returnedFragments;	// not enough space for more fragments
				}
			}
			continue;
		}
		else
		{
			// ignore all other world surfaces
			// might be cool to also project polygons on a triangle soup
			// however this will probably create huge amounts of extra polys
			// even more than the projection onto curves
			continue;
		}
	}
	return returnedFragments;
}

