/*
Copyright (C) 1996-2001 Id Software, Inc.
Copyright (C) 2002-2009 John Fitzgibbons and others
Copyright (C) 2010-2014 QuakeSpasm developers

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 GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

*/
// gl_mesh.c: triangle model functions

#include "q_defs.h"


/*
=================================================================

ALIAS MODEL DISPLAY LIST GENERATION

=================================================================
*/

qmodel_t        *aliasmodel;
aliashdr_t      *paliashdr;

int32_t         used[8192]; // bool

// the command list holds counts and s/t values that are valid for
// every frame
int32_t         commands[8192];
int32_t         numcommands;

// all frames will have their vertexes rearranged and expanded
// so they are in the order expected by the command list
int32_t         vertexorder[8192];
int32_t         numorder;

int32_t         allverts, alltris;

int32_t         stripverts[128];
int32_t         striptris[128];
int32_t         stripcount;

/*
================
StripLength
================
*/
int32_t StripLength(int32_t starttri, int32_t startv)
{
	int32_t                 m1, m2;
	int32_t                 j;
	mtriangle_t     *last, *check;
	int32_t                 k;

	used[starttri] = 2;

	last = &triangles[starttri];

	stripverts[0] = last->vertindex[(startv) % 3];
	stripverts[1] = last->vertindex[(startv + 1) % 3];
	stripverts[2] = last->vertindex[(startv + 2) % 3];

	striptris[0] = starttri;
	stripcount = 1;

	m1 = last->vertindex[(startv + 2) % 3];
	m2 = last->vertindex[(startv + 1) % 3];

	// look for a matching triangle
nexttri:
	for(j = starttri + 1, check = &triangles[starttri + 1] ; j < pheader->numtris ; j++, check++)
	{
		if(check->facesfront != last->facesfront)
			continue;
		for(k = 0 ; k < 3 ; k++)
		{
			if(check->vertindex[k] != m1)
				continue;
			if(check->vertindex[(k + 1) % 3 ] != m2)
				continue;

			// this is the next part of the fan

			// if we can't use this triangle, this tristrip is done
			if(used[j])
				goto done;

			// the new edge
			if(stripcount & 1)
				m2 = check->vertindex[(k + 2) % 3 ];
			else
				m1 = check->vertindex[(k + 2) % 3 ];

			stripverts[stripcount + 2] = check->vertindex[(k + 2) % 3 ];
			striptris[stripcount] = j;
			stripcount++;

			used[j] = 2;
			goto nexttri;
		}
	}
done:

	// clear the temp used flags
	for(j = starttri + 1 ; j < pheader->numtris ; j++)
		if(used[j] == 2)
			used[j] = 0;

	return stripcount;
}

/*
===========
FanLength
===========
*/
int32_t FanLength(int32_t starttri, int32_t startv)
{
	int32_t         m1, m2;
	int32_t         j;
	mtriangle_t     *last, *check;
	int32_t         k;

	used[starttri] = 2;

	last = &triangles[starttri];

	stripverts[0] = last->vertindex[(startv) % 3];
	stripverts[1] = last->vertindex[(startv + 1) % 3];
	stripverts[2] = last->vertindex[(startv + 2) % 3];

	striptris[0] = starttri;
	stripcount = 1;

	m1 = last->vertindex[(startv + 0) % 3];
	m2 = last->vertindex[(startv + 2) % 3];


	// look for a matching triangle
nexttri:
	for(j = starttri + 1, check = &triangles[starttri + 1] ; j < pheader->numtris ; j++, check++)
	{
		if(check->facesfront != last->facesfront)
			continue;
		for(k = 0 ; k < 3 ; k++)
		{
			if(check->vertindex[k] != m1)
				continue;
			if(check->vertindex[(k + 1) % 3 ] != m2)
				continue;

			// this is the next part of the fan

			// if we can't use this triangle, this tristrip is done
			if(used[j])
				goto done;

			// the new edge
			m2 = check->vertindex[(k + 2) % 3 ];

			stripverts[stripcount + 2] = m2;
			striptris[stripcount] = j;
			stripcount++;

			used[j] = 2;
			goto nexttri;
		}
	}
done:

	// clear the temp used flags
	for(j = starttri + 1 ; j < pheader->numtris ; j++)
		if(used[j] == 2)
			used[j] = 0;

	return stripcount;
}


/*
================
BuildTris

Generate a list of trifans or strips
for the model, which holds for all frames
================
*/
void BuildTris(void)
{
	int32_t         i, j, k;
	int32_t         startv;
	float   s, t;
	int32_t         len, bestlen, besttype;
	int32_t         bestverts[1024];
	int32_t         besttris[1024];
	int32_t         type;

	//
	// build tristrips
	//
	numorder = 0;
	numcommands = 0;
	memset(used, 0, sizeof(used));
	for(i = 0; i < pheader->numtris; i++)
	{
		// pick an unused triangle and start the trifan
		if(used[i])
			continue;

		bestlen = 0;
		besttype = 0;
		for(type = 0 ; type < 2 ; type++)
//	type = 1;
		{
			for(startv = 0; startv < 3; startv++)
			{
				if(type == 1)
					len = StripLength(i, startv);
				else
					len = FanLength(i, startv);
				if(len > bestlen)
				{
					besttype = type;
					bestlen = len;
					for(j = 0; j < bestlen + 2; j++)
						bestverts[j] = stripverts[j];
					for(j = 0; j < bestlen; j++)
						besttris[j] = striptris[j];
				}
			}
		}

		// mark the tris on the best strip as used
		for(j = 0; j < bestlen; j++)
			used[besttris[j]] = 1;

		if(besttype == 1)
			commands[numcommands++] = (bestlen + 2);
		else
			commands[numcommands++] = -(bestlen + 2);

		for(j = 0; j < bestlen + 2; j++)
		{
			int32_t         tmp;

			// emit a vertex into the reorder buffer
			k = bestverts[j];
			vertexorder[numorder++] = k;

			// emit s/t coords into the commands stream
			s = stverts[k].s;
			t = stverts[k].t;
			if(!triangles[besttris[0]].facesfront && stverts[k].onseam)
				s += pheader->skinwidth / 2;    // on back side
			s = (s + 0.5) / pheader->skinwidth;
			t = (t + 0.5) / pheader->skinheight;

			//      *(float *)&commands[numcommands++] = s;
			//      *(float *)&commands[numcommands++] = t;
			// NOTE: 4 == sizeof(int32_t)
			//         == sizeof(float)
			memcpy(&tmp, &s, 4);
			commands[numcommands++] = tmp;
			memcpy(&tmp, &t, 4);
			commands[numcommands++] = tmp;
		}
	}

	commands[numcommands++] = 0;            // end of list marker

	Con_DPrintf2("%3" PRIi32 " tri %3" PRIi32 " vert %3" PRIi32 " cmd\n", pheader->numtris, numorder, numcommands);

	allverts += numorder;
	alltris += pheader->numtris;
}

static void GL_MakeAliasModelDisplayLists_VBO(void);
static void GLMesh_LoadVertexBuffer(qmodel_t *m, const aliashdr_t *hdr);

/*
================
GL_MakeAliasModelDisplayLists
================
*/
void GL_MakeAliasModelDisplayLists(qmodel_t *m, aliashdr_t *hdr)
{
	int32_t         i, j;
	int32_t                 *cmds;
	trivertx_t      *verts;
	float   hscale, vscale; //johnfitz -- padded skins
	int32_t         count; //johnfitz -- precompute texcoords for padded skins
	int32_t         *loadcmds; //johnfitz

	//johnfitz -- padded skins
	hscale = (float)hdr->skinwidth / (float)TexMgr_PadConditional(hdr->skinwidth);
	vscale = (float)hdr->skinheight / (float)TexMgr_PadConditional(hdr->skinheight);
	//johnfitz

	aliasmodel = m;
	paliashdr = hdr;        // (aliashdr_t *)Mod_Extradata (m);

//johnfitz -- generate meshes
	Con_DPrintf2("meshing %s...\n", m->name);
	BuildTris();

	// save the data out

	paliashdr->poseverts = numorder;

	cmds = Hunk_AllocName(numcommands * 4, __func__);
	paliashdr->commands = (byte *)cmds - (byte *)paliashdr;

	//johnfitz -- precompute texcoords for padded skins
	loadcmds = commands;
	while(1)
	{
		*cmds++ = count = *loadcmds++;

		if(!count)
			break;

		if(count < 0)
			count = -count;

		do
		{
			*(float *)cmds++ = hscale * (*(float *)loadcmds++);
			*(float *)cmds++ = vscale * (*(float *)loadcmds++);
		}
		while(--count);
	}
	//johnfitz

	verts = Hunk_AllocName(paliashdr->numposes * paliashdr->poseverts * sizeof(trivertx_t), __func__);
	paliashdr->posedata = (byte *)verts - (byte *)paliashdr;
	for(i = 0 ; i < paliashdr->numposes ; i++)
		for(j = 0 ; j < numorder ; j++)
			*verts++ = poseverts[i][vertexorder[j]];

	// ericw
	GL_MakeAliasModelDisplayLists_VBO();
}

uint32_t r_meshindexbuffer = 0;
uint32_t r_meshvertexbuffer = 0;

/*
================
GL_MakeAliasModelDisplayLists_VBO

Saves data needed to build the VBO for this model on the hunk. Afterwards this
is copied to Mod_Extradata.

Original code by MH from RMQEngine
================
*/
void GL_MakeAliasModelDisplayLists_VBO(void)
{
	int32_t i, j;
	int32_t maxverts_vbo;
	trivertx_t *verts;
	uint16_t *indexes;
	aliasmesh_t *desc;

	if(!gl_glsl_alias_able)
		return;

	// first, copy the verts onto the hunk
	verts = Hunk_AllocName(paliashdr->numposes * paliashdr->numverts * sizeof(trivertx_t), __func__);
	paliashdr->vertexes = (byte *)verts - (byte *)paliashdr;
	for(i = 0 ; i < paliashdr->numposes ; i++)
		for(j = 0 ; j < paliashdr->numverts ; j++)
			verts[i * paliashdr->numverts + j] = poseverts[i][j];

	// there can never be more than this number of verts and we just put them all on the hunk
	maxverts_vbo = pheader->numtris * 3;
	desc = Hunk_AllocName(sizeof(aliasmesh_t) * maxverts_vbo, __func__);

	// there will always be this number of indexes
	indexes = Hunk_AllocName(sizeof(uint16_t) * maxverts_vbo, __func__);

	pheader->indexes = (intptr_t) indexes - (intptr_t) pheader;
	pheader->meshdesc = (intptr_t) desc - (intptr_t) pheader;
	pheader->numindexes = 0;
	pheader->numverts_vbo = 0;

	for(i = 0; i < pheader->numtris; i++)
	{
		for(j = 0; j < 3; j++)
		{
			int32_t v;

			// index into hdr->vertexes
			uint16_t vertindex = triangles[i].vertindex[j];

			// basic s/t coords
			int32_t s = stverts[vertindex].s;
			int32_t t = stverts[vertindex].t;

			// check for back side and adjust texcoord s
			if(!triangles[i].facesfront && stverts[vertindex].onseam) s += pheader->skinwidth / 2;

			// see does this vert already exist
			for(v = 0; v < pheader->numverts_vbo; v++)
			{
				// it could use the same xyz but have different s and t
				if(desc[v].vertindex == vertindex && (int32_t) desc[v].st[0] == s && (int32_t) desc[v].st[1] == t)
				{
					// exists; emit an index for it
					indexes[pheader->numindexes++] = v;

					// no need to check any more
					break;
				}
			}

			if(v == pheader->numverts_vbo)
			{
				// doesn't exist; emit a new vert and index
				indexes[pheader->numindexes++] = pheader->numverts_vbo;

				desc[pheader->numverts_vbo].vertindex = vertindex;
				desc[pheader->numverts_vbo].st[0] = s;
				desc[pheader->numverts_vbo++].st[1] = t;
			}
		}
	}

	// upload immediately
	GLMesh_LoadVertexBuffer(aliasmodel, pheader);
}

#define NUMVERTEXNORMALS         162
extern  float   r_avertexnormals[NUMVERTEXNORMALS][3];

/*
================
GLMesh_LoadVertexBuffer

Upload the given alias model's mesh to a VBO

Original code by MH from RMQEngine
================
*/
static void GLMesh_LoadVertexBuffer(qmodel_t *m, const aliashdr_t *hdr)
{
	int32_t totalvbosize = 0;
	const aliasmesh_t *desc;
	const int16_t *indexes;
	const trivertx_t *trivertexes;
	byte *vbodata;
	int32_t f;

	if(!gl_glsl_alias_able)
		return;

// count the sizes we need

	// ericw -- RMQEngine stored these vbo*ofs values in aliashdr_t, but we must not
	// mutate Mod_Extradata since it might be reloaded from disk, so I moved them to qmodel_t
	// (test case: roman1.bsp from arwop, 64mb heap)
	m->vboindexofs = 0;

	m->vboxyzofs = 0;
	totalvbosize += (hdr->numposes * hdr->numverts_vbo * sizeof(meshxyz_t));  // ericw -- what RMQEngine called nummeshframes is called numposes in QuakeSpasm

	m->vbostofs = totalvbosize;
	totalvbosize += (hdr->numverts_vbo * sizeof(meshst_t));

	if(!hdr->numindexes) return;
	if(!totalvbosize) return;

// grab the pointers to data in the extradata

	desc = (aliasmesh_t *)((byte *) hdr + hdr->meshdesc);
	indexes = (int16_t *)((byte *) hdr + hdr->indexes);
	trivertexes = (trivertx_t *)((byte *)hdr + hdr->vertexes);

// upload indices buffer

	GL_DeleteBuffersFunc(1, &m->meshindexesvbo);
	GL_GenBuffersFunc(1, &m->meshindexesvbo);
	GL_BindBufferFunc(GL_ELEMENT_ARRAY_BUFFER, m->meshindexesvbo);
	GL_BufferDataFunc(GL_ELEMENT_ARRAY_BUFFER, hdr->numindexes * sizeof(uint16_t), indexes, GL_STATIC_DRAW);

// create the vertex buffer (empty)

	vbodata = (byte *) malloc(totalvbosize);
	memset(vbodata, 0, totalvbosize);

// fill in the vertices at the start of the buffer
	for(f = 0; f < hdr->numposes; f++)  // ericw -- what RMQEngine called nummeshframes is called numposes in QuakeSpasm
	{
		int32_t v;
		meshxyz_t *xyz = (meshxyz_t *)(vbodata + (f * hdr->numverts_vbo * sizeof(meshxyz_t)));
		const trivertx_t *tv = trivertexes + (hdr->numverts * f);

		for(v = 0; v < hdr->numverts_vbo; v++)
		{
			trivertx_t trivert = tv[desc[v].vertindex];

			xyz[v].xyz[0] = trivert.v[0];
			xyz[v].xyz[1] = trivert.v[1];
			xyz[v].xyz[2] = trivert.v[2];
			xyz[v].xyz[3] = 1;      // need w 1 for 4 byte vertex compression

			// map the normal coordinates in [-1..1] to [-127..127] and store in an uint8_t.
			// this introduces some error (less than 0.004), but the normals were very coarse
			// to begin with
			xyz[v].normal[0] = 127 * r_avertexnormals[trivert.lightnormalindex][0];
			xyz[v].normal[1] = 127 * r_avertexnormals[trivert.lightnormalindex][1];
			xyz[v].normal[2] = 127 * r_avertexnormals[trivert.lightnormalindex][2];
			xyz[v].normal[3] = 0;   // unused; for 4-byte alignment
		}
	}

// fill in the ST coords at the end of the buffer
	{
		meshst_t *st;
		float hscale, vscale;

		//johnfitz -- padded skins
		hscale = (float)hdr->skinwidth / (float)TexMgr_PadConditional(hdr->skinwidth);
		vscale = (float)hdr->skinheight / (float)TexMgr_PadConditional(hdr->skinheight);
		//johnfitz

		st = (meshst_t *)(vbodata + m->vbostofs);
		for(f = 0; f < hdr->numverts_vbo; f++)
		{
			st[f].st[0] = hscale * ((float) desc[f].st[0] + 0.5f) / (float) hdr->skinwidth;
			st[f].st[1] = vscale * ((float) desc[f].st[1] + 0.5f) / (float) hdr->skinheight;
		}
	}

// upload vertexes buffer
	GL_DeleteBuffersFunc(1, &m->meshvbo);
	GL_GenBuffersFunc(1, &m->meshvbo);
	GL_BindBufferFunc(GL_ARRAY_BUFFER, m->meshvbo);
	GL_BufferDataFunc(GL_ARRAY_BUFFER, totalvbosize, vbodata, GL_STATIC_DRAW);

	free(vbodata);

// invalidate the cached bindings
	GL_ClearBufferBindings();
}

/*
================
GLMesh_LoadVertexBuffers

Loop over all precached alias models, and upload each one to a VBO.
================
*/
void GLMesh_LoadVertexBuffers(void)
{
	int32_t j;
	qmodel_t *m;
	const aliashdr_t *hdr;

	if(!gl_glsl_alias_able)
		return;

	for(j = 1; j < MAX_MODELS; j++)
	{
		if(!(m = cl.model_precache[j])) break;
		if(m->type != mod_alias) continue;

		hdr = (const aliashdr_t *) Mod_Extradata(m);

		GLMesh_LoadVertexBuffer(m, hdr);
	}
}

/*
================
GLMesh_DeleteVertexBuffers

Delete VBOs for all loaded alias models
================
*/
void GLMesh_DeleteVertexBuffers(void)
{
	int32_t j;
	qmodel_t *m;

	if(!gl_glsl_alias_able)
		return;

	for(j = 1; j < MAX_MODELS; j++)
	{
		if(!(m = cl.model_precache[j])) break;
		if(m->type != mod_alias) continue;

		GL_DeleteBuffersFunc(1, &m->meshvbo);
		m->meshvbo = 0;

		GL_DeleteBuffersFunc(1, &m->meshindexesvbo);
		m->meshindexesvbo = 0;
	}

	GL_ClearBufferBindings();
}