//-----------------------------------------------------------------------------
//
//  $Logfile:: /Source/gl_tesselate.c                                          $
// $Revision:: 3                                                               $
//   $Author:: Burgermac                                                       $
//     $Date:: 8/8/01 4:46 PM                                                  $
//
// Copyright (C) 1998 by Ritual Entertainment, Inc.
// All rights reserved.
//
// This source is may not be distributed and/or modified without
// expressly written permission by Ritual Entertainment, Inc.
//
// DESCRIPTION:
// Model tesselation stuff
//

#include "gl_local.h"

static int           tesselate_max_tris;
static int           tesselate_min_size;
static int           tesselate_max_size;
static int           tesselate_flags;
static triangle_t    *tesselate_tris;
static int           tesselate_num_tris;
static vec3_t        tesselate_origin;
static qboolean      tesselate_region;
static int           tesselate_flag_count;

/*
====================
AddTesselatedTriangle
====================
*/
static qboolean AddTesselatedTriangle (triangle_t *tri)
{
	if (tesselate_num_tris < tesselate_max_tris)
	{
		tesselate_flag_count += tesselate_flags;
		if (tesselate_flag_count < 254)
			return true;

		while (tesselate_flag_count >= 254)
			tesselate_flag_count -= 254;

		tesselate_tris[tesselate_num_tris++] = *tri;
		return true;
	}
	return false;
}

/*
====================
SubdivideTriangle
====================
*/
static qboolean SubdivideTriangles (triangle_t *tri)
{
	int i, j;
	vec3_t mins, maxs, delta;
	float *v, size;
	float s_max, s_min, t_max, t_min;
	qboolean ret;

	// reset mins
	mins[0] = 9999;
	mins[1] = 9999;
	mins[2] = 9999;
	s_min = 9999;
	t_min = 9999;

	// reset maxs
	maxs[0] = -9999;
	maxs[1] = -9999;
	maxs[2] = -9999;
	s_max = -9999;
	t_max = -9999;

	//find mins and maxs of this surface
	for (i = 0; i < 3; i++)
	{
		v = tri->verts[i];
		for (j = 0; j < 3; j++)
		{
			if (v[j] < mins[j]) mins[j] = v[j];
			if (v[j] > maxs[j]) maxs[j] = v[j];
		}
		if (v[3] < s_min) s_min = v[3];
		if (v[3] > s_max) s_max = v[3];
		if (v[4] < t_min) t_min = v[4];
		if (v[4] > t_max) t_max = v[4];
	}
	VectorSubtract(maxs, mins, delta);
	size = VectorLength(delta);

	//
	// see if we need to chop it down again
	//
	if (size > tesselate_max_size)
	{
		vec3_t center,light;
		float centers, centert;
		triangle_t newtris[2];
		int largestaxis = 0;
		int firstvert, secondvert, othervert;
		triangle_t *newtri;

		for (i = 1; i < 3; i++)
		{
			if (delta[i] > delta[largestaxis])
				largestaxis = i;
		}

		firstvert = secondvert = -1;
		othervert = 0;
		for (i = 0; i < 3; i++)
		{
			if (tri->verts[i][largestaxis] == mins[largestaxis] && firstvert == -1)
				firstvert = i;
			else if (tri->verts[i][largestaxis] == maxs[largestaxis] && secondvert == -1)
				secondvert = i;
			else
				othervert = i;
		}
		for (i = 0; i < 3; i++)
		{
			center[i] = (tri->verts[firstvert][i] + tri->verts[secondvert][i]) * 0.5;
			light[i] = (tri->verts[firstvert][5+i] + tri->verts[secondvert][5+i]) * 0.5;
		}
		centers = (tri->verts[firstvert][3] + tri->verts[secondvert][3]) * 0.5;
		centert = (tri->verts[firstvert][4] + tri->verts[secondvert][4]) * 0.5;
		newtri = &newtris[0];
		newtri->texture = tri->texture;
		newtri->alpha = tri->alpha;
		newtri->surftype = tri->surftype;
		newtri->flags = tri->flags;
		memcpy(newtri->verts[0], tri->verts[firstvert], TRI_VERT_SIZE*sizeof(float));
		memcpy(newtri->verts[2], tri->verts[othervert], TRI_VERT_SIZE*sizeof(float));
		VectorCopy(center, newtri->verts[1]);
		newtri->verts[1][3] = centers;
		newtri->verts[1][4] = centert;
		VectorCopy(light, (&newtri->verts[1][5]));
		ret = SubdivideTriangles(newtri);

		newtri = &newtris[1];
		newtri->texture = tri->texture;
		newtri->alpha = tri->alpha;
		newtri->surftype = tri->surftype;
		newtri->flags = tri->flags;
		memcpy(newtri->verts[0], tri->verts[secondvert], TRI_VERT_SIZE*sizeof(float));
		memcpy(newtri->verts[2], tri->verts[othervert], TRI_VERT_SIZE*sizeof(float));
		VectorCopy(center, newtri->verts[1]);
		newtri->verts[1][3] = centers;
		newtri->verts[1][4] = centert;
		VectorCopy(light, (&newtri->verts[1][5]));
		ret = SubdivideTriangles(newtri);
	}
	else
	{
		if (size < tesselate_min_size)
			return true;
		if (tesselate_region)
		{
			vec3_t mid;
			vec3_t dist;

			VectorScale(delta, 0.5f, mid);
			VectorAdd(mid, mins, mid);
			VectorSubtract(mid, tesselate_origin, dist);
			if (VectorLength(dist) > tesselate_max_size)
				return true;
		}
		return AddTesselatedTriangle(tri);
	}
	return ret;
}


/*
====================
SubdividePolygonIntoTriangles
====================
*/
static void SubdividePolygonIntoTriangles (msurface_t *surf, glpoly_t *poly, qboolean use_first)
{
	int i, j;
	float *v;
	float center[5];
	vec3_t mins, maxs;
	float s_max, s_min, t_max, t_min;
	#define GL_SUBDIV_MAX_NEWPOLYS 10
	triangle_t newtris[GL_SUBDIV_MAX_NEWPOLYS];
	triangle_t *newtri;

	// reset mins
	mins[0] = 9999;
	mins[1] = 9999;
	mins[2] = 9999;
	s_min = 9999;
	t_min = 9999;

	// reset maxs
	maxs[0] = -9999;
	maxs[1] = -9999;
	maxs[2] = -9999;
	s_max = -9999;
	t_max = -9999;

	//find mins and maxs of this surface
	for (i = 0; i < poly->numverts; i++)
	{
		v = poly->verts[i];
		for (j = 0; j < 3; j++)
		{
			if (v[j] < mins[j]) mins[j] = v[j];
			if (v[j] > maxs[j]) maxs[j] = v[j];
		}
		if (v[3] < s_min) s_min = v[3];
		if (v[3] > s_max) s_max = v[3];
		if (v[4] < t_min) t_min = v[4];
		if (v[4] > t_max) t_max = v[4];
	}

	for (i = 0; i < 3; i++)
	{
		center[i] = (maxs[i] + mins[i]) * 0.5;
	}
	center[3] = (s_max + s_min) * 0.5;
	center[4] = (t_max + t_min) * 0.5;

	for (i = 0; i < poly->numverts; i++)
	{
		int kk;
		vec3_t color;

		if (i == GL_SUBDIV_MAX_NEWPOLYS)
			return;

		newtri = &newtris[i];
		if (use_first)
			newtri->texture = (void *)surf->first_texinfo->image;
		else
			newtri->texture = (void *)surf->texinfo->image;
		newtri->surftype = SURFACETYPE_FROM_FLAGS(surf->texinfo->flags);
		newtri->flags = (surf->texinfo->flags & SURF_MASKED)? TRI_MASKED : 0;
		if (surf->texinfo->surf->translucence > 0)
			newtri->alpha = 1.0f - surf->texinfo->surf->translucence;
		else
			newtri->alpha = 1.0f;
		j = (i + 1) % poly->numverts;
		for (kk = 0; kk < 5; kk++)
		{
			newtri->verts[0][kk] = poly->verts[i][kk];
			newtri->verts[1][kk] = center[kk];
			newtri->verts[2][kk] = poly->verts[j][kk];
		}
		R_GetSurfaceColorAtST(surf, newtri->verts[0][3], newtri->verts[0][4], color);
		newtri->verts[0][5] = color[0];
		newtri->verts[0][6] = color[1];
		newtri->verts[0][7] = color[2];
		R_GetSurfaceColorAtST(surf, newtri->verts[1][3], newtri->verts[1][4], color);
		newtri->verts[1][5] = color[0];
		newtri->verts[1][6] = color[1];
		newtri->verts[1][7] = color[2];
		R_GetSurfaceColorAtST(surf, newtri->verts[2][3], newtri->verts[2][4], color);
		newtri->verts[2][5] = color[0];
		newtri->verts[2][6] = color[1];
		newtri->verts[2][7] = color[2];

		SubdivideTriangles(newtri);
	}
}

/*
====================
TesselateBrushModel
====================
*/
static void TesselateBrushModel (struct model_t *mdl)
{
	int i;
	msurface_t *psurf;

	psurf = &mdl->surfaces[mdl->firstmodelsurface];

	//
	// Tesselate each surface
	//
	for (i = 0; i < mdl->nummodelsurfaces; i++, psurf++)
	{
		if (psurf->texinfo->flags & SURF_NODRAW)
			continue;
		SubdividePolygonIntoTriangles(psurf, psurf->polys, false);
	}
}

/*
====================
CreateTrianglesFromTexinfo
====================
*/
static void CreateTrianglesFromTexinfo (entity_t *ent)
{
	const char *name;
	triangle_t newtri;
	mtexinfo_t *tex;
	msurface_t *surf;
	vec3_t shadelight;
	vec3_t dir, u, v;
	float verts[4][5];
	int i, j;
	int kk;

	name = (const char *)ent->skin;
	if (!name)
		return;

	//
	// find the texinfo
	//
	tex = NULL;/* silence compiler */
	for (i = 0; i < ent->model->numtexinfo; i++)
	{
		tex = &ent->model->texinfo[i];
		if (!strcmp(name, tex->surf->groupname))
			break;
	}
	if (i == ent->model->numtexinfo || !tex)
		return;

	if (!VectorLength(tesselate_origin))
	{
		// Find all the surfaces that use this texinfo.
		surf = NULL;/* silence compiler */
		for (j = 0; j < ent->model->numsurfaces; j++)
		{
			surf = &ent->model->surfaces[j];
			if (surf->texinfo == tex || surf->first_texinfo == tex)
				break;
		}
		if (j == ent->model->numsurfaces || !surf)
			return;

		if (surf->texinfo == tex)
			SubdividePolygonIntoTriangles(surf, surf->polys, false);
		else
			SubdividePolygonIntoTriangles(surf, surf->polys, true);
		return;
	}

	R_LightPoint (ent->origin, shadelight, false);

	newtri.texture = (void *)tex->image;
	newtri.surftype = SURFACETYPE_FROM_FLAGS(tex->flags);
	newtri.flags = (tex->flags & SURF_MASKED)? TRI_MASKED : 0;
	if (tex->surf->translucence > 0)
		newtri.alpha = 1.0f - tex->surf->translucence;
	else
		newtri.alpha = 1.0f;

	VectorCopy(ent->angles, dir);
	PerpendicularVector(u, dir);
	CrossProduct(u, dir, v);

	for (i = 0; i < 3; i++)
	{
		verts[0][i] = ent->origin[i] - ((tesselate_max_size/2) * u[i]) - ((tesselate_max_size/2) * v[i]);
		verts[1][i] = ent->origin[i] - ((tesselate_max_size/2) * u[i]) + ((tesselate_max_size/2) * v[i]);
		verts[2][i] = ent->origin[i] + ((tesselate_max_size/2) * u[i]) - ((tesselate_max_size/2) * v[i]);
		verts[3][i] = ent->origin[i] + ((tesselate_max_size/2) * u[i]) + ((tesselate_max_size/2) * v[i]);
	}
	for (i = 0; i < 4; i++)
	{
		verts[i][3] = DotProduct (verts[i], tex->vecs[0]) + tex->vecs[0][3];
		verts[i][3] /= tex->image->width;

		verts[i][4] = DotProduct (verts[i], tex->vecs[1]) + tex->vecs[1][3];
		verts[i][4] /= tex->image->height;
	}
	for (kk = 0; kk < 5; kk++)
	{
		newtri.verts[0][kk] = verts[0][kk];
		newtri.verts[1][kk] = verts[1][kk];
		newtri.verts[2][kk] = verts[2][kk];
	}
	VectorCopy(shadelight, (&newtri.verts[0][5]));
	VectorCopy(shadelight, (&newtri.verts[1][5]));
	VectorCopy(shadelight, (&newtri.verts[2][5]));

	SubdivideTriangles(&newtri);

	for (kk = 0; kk < 5; kk++)
	{
		newtri.verts[0][kk] = verts[1][kk];
		newtri.verts[1][kk] = verts[3][kk];
		newtri.verts[2][kk] = verts[2][kk];
	}

	SubdivideTriangles(&newtri);
}

/*
=================
SINMDL_Tesselate_ScaleAndRotateVerts
=================
*/
static void SINMDL_Tesselate_ScaleAndRotateVerts (int nverts, dtrivertx_t *v, float *lerp, float scale[3], float offset[3], float trans[3][3])
{
	int i;
	vec3_t temp;

	for (i = 0; i < nverts; i++, v++, lerp += 4)
	{
		lerp[0] = offset[0] + (v->v[0]*scale[0]);
		lerp[1] = offset[1] + (v->v[1]*scale[1]);
		lerp[2] = offset[2] + (v->v[2]*scale[2]);
		VectorCopy(lerp, temp);
		lerp[0] = DotProduct(temp, (trans[0]));
		lerp[1] = DotProduct(temp, (trans[1]));
		lerp[2] = DotProduct(temp, (trans[2]));
	}
}

/*
=================
SINMDL_TesselateModel

=================
*/
static void SINMDL_TesselateModel (entity_t *ent)
{
	int i, j, l;
	dsinmdl_t *pmdl;
	dsinanimdef_t *panimdef;
	dsintriframe_t *pframe;
	dsingroup_t *pgroup;
	dsinbasemdl_t *currentbase;
	dtrivertx_t *currentverts;
	dsinanim_t *currentanim;
	dsintriframe_t *currentframe;
	dsinstvert_t *pstverts;
	triangle_t new_tri;
	int rendergroups[32];
	vec3_t voffset, vscale, origin, shadelight;
	vec3_t forward, right, up;
	float trans[3][3];
	image_t *skin;
	int anim, frame, skinnum;
	float currentscale;

	anim = ent->anim;
	frame = ent->frame;
	skinnum = ent->skinnum;
	currentscale = ent->scale;

	pmdl = ri.SINMDL_GetDef((int)(intptr_t)ent->model->extradata);
	if (!pmdl)
		return;

	// get current base
	if (pmdl->base_handle >= 0)
		currentbase = ri.SINMDL_GetBaseModel(pmdl->base_handle);
	else
		return;

	pstverts = (dsinstvert_t *) ((byte *)currentbase + currentbase->ofs_st);
	// get current anim
	if (anim >= pmdl->num_anims || anim < 0)
		anim %= pmdl->num_anims;

	panimdef = (dsinanimdef_t *) ((byte *)pmdl + pmdl->ofs_animdefs[anim]);
	if (panimdef->handle >= 0)
		currentanim = ri.SINMDL_GetAnim(panimdef->handle);
	else
		return;

	// get current frame
	if (frame >= currentanim->num_frames || frame < 0)
		frame %= currentanim->num_frames;

	// point to the data
	pframe = (dsintriframe_t *) ((byte *)currentanim + currentanim->ofs_frames);
	currentframe = &pframe[frame];
	currentverts = (dtrivertx_t *) ((byte *)currentframe + currentframe->ofs_verts);

	//
	// grab lighting
	//

	//
	// we offset this a bit to account for slopes
	//
	VectorCopy(ent->origin, origin);
	origin[2] += 16;
	R_LightPoint (origin, shadelight, false);

	if (ent->flags & RF_LIGHTOFFSET)
	{ // minimum light adjustment
		for (i = 0; i < 3; i++)
		{
			float min;
			min = shadelight[i] / 3.0f;
			shadelight[i] += ((float)ent->lightofs/127.0f);
			if (shadelight[i] < min)
				shadelight[i] = min;
			if (shadelight[i] > 1)
				shadelight[i] = 1;
		}
	}
	//
	// resolve rendering flags
	// grab the flags from the current entity and add the ones from the baseframe as well
	//
	memset(rendergroups, 0, sizeof(rendergroups));
	pgroup = (dsingroup_t *) ((byte *)pmdl + pmdl->ofs_groups);
	for (i = 0; i < pmdl->num_groups; i++, pgroup++)
	{
		for (j = 0; j < pgroup->num_subgroups; j++)
		{
			int index;
			index = pgroup->subgroups[j].basegroupnum;
			rendergroups[index] = pgroup->subgroups[j].flags;
		}
	}

	AngleVectors(ent->angles, forward, right, up);
	for (i = 0; i < 3; i++)
	{
		trans[i][0] = forward[i];
		trans[i][1] = -right[i];
		trans[i][2] = up[i];
	}

	for (i = 0; i < 3; i++)
	{
		voffset[i] = (currentframe->translate[i] + pmdl->load_origin[i]) * currentscale * pmdl->load_scale;
		vscale[i] = currentframe->scale[i] * currentscale * pmdl->load_scale;
	}
	SINMDL_Tesselate_ScaleAndRotateVerts(currentbase->num_xyz, currentverts, s_lerped[0], vscale, voffset, trans);

	for (i = 0; i < currentbase->num_groups; i++)
	{
		dsintrigroup_t *pgroup;
		dsintriangle_t *ptris;

		pgroup = &currentbase->groups[i];
		ptris = (dsintriangle_t *) ((byte *)pgroup + pgroup->ofs_tris);

		if (rendergroups[i] & MDL_GROUP_NODRAW)
			continue;

		// custom player skin
		if (ent->flags & RF_CUSTOMSKIN)
		{
			if (ent->skin)
				skin = ent->skin;
			else
				skin = ent->model->skins[0];

			// Check if this is a damage skin
			if ((rendergroups[i]&0x3) == 1)
				skin = ent->damageskin;
		}
		else
		{
			j = skinnum + (rendergroups[i]&0x3);
			if (j >= MAX_MD2SKINS)
				skin = ent->model->skins[0];
			else
			{
				skin = ent->model->skins[j];
				if (!skin)
					skin = ent->model->skins[0];
			}
		}

		for (l = 0; l < pgroup->num_tris; l++)
		{
			for (j = 0; j < 3; j++)
			{
				VectorCopy(s_lerped[ptris[l].index_xyz[j]], new_tri.verts[j]);
				new_tri.verts[j][3] = pstverts[ptris[l].index_st[j]].s;
				new_tri.verts[j][4] = pstverts[ptris[l].index_st[j]].t;
				VectorCopy(shadelight, (&new_tri.verts[j][5]));
			}
			new_tri.texture = (void *)skin;
			new_tri.flags = (rendergroups[i] & MDL_GROUP_MASKED)? TRI_MASKED : 0;
			if (rendergroups[i] & MDL_GROUP_TRANSLUCENT_33)
				new_tri.alpha = 0.66f;
			else if (rendergroups[i] & MDL_GROUP_TRANSLUCENT_66)
				new_tri.alpha = 0.33f;
			else
				new_tri.alpha = 1.0f;
			new_tri.surftype = (rendergroups[i]>>8)&0xf;
			if (!SubdivideTriangles(&new_tri))
				return;
		}
	}
}

int GL_TesselateModel (entity_t *ent, triangle_t *tris, int max_tris, int min_size, int max_size, int flags, const vec3_t origin)
{
	tesselate_num_tris = 0;
	tesselate_tris = tris;
	tesselate_max_tris = max_tris;
	tesselate_min_size = min_size;
	tesselate_max_size = max_size;
	tesselate_flags = flags;
	tesselate_flag_count = 0;
	tesselate_region = false;
	VectorCopy(origin, tesselate_origin);

	if (!ent->model)
		ent->model = r_worldmodel;

	switch (ent->model->type)
	{
	case mod_brush:
		if (ent->model == r_worldmodel)
			CreateTrianglesFromTexinfo(ent);
		else
			TesselateBrushModel(ent->model);
		break;
	case mod_sinmdl:
		if (VectorLength(origin))
		{
			tesselate_region = true;
			VectorSubtract(tesselate_origin, ent->origin, tesselate_origin);
		}
		SINMDL_TesselateModel (ent);
		break;
	default:
		break;
	}
	return tesselate_num_tris;
}

/*
===============
GL_DrawTriangle
===============
*/
static void GL_DrawTriangle (triangle_t *p)
{
	float *v;
	int i, j;

	qglPushMatrix();

	qglTranslatef(p->origin[0], p->origin[1], p->origin[2]);

	qglRotatef(p->angles[1], 0, 0, 1);
	qglRotatef(p->angles[0], 0, 1, 0);
	qglRotatef(p->angles[2], 1, 0, 0);

	if (p->texture)
		GL_BindImage ((image_t *)p->texture);

	v = &p->verts[0][0];
	qglBegin (GL_TRIANGLES);
	for (j = 0; j < p->num_tris; j++)
	{
		for (i = 0; i < 3; i++, v+= TRI_VERT_SIZE)
		{
			qglColor4f (v[5], v[6], v[7], p->alpha);
			qglTexCoord2f (v[3], v[4]);
			qglVertex3fv (v);
		}
	}
	qglEnd ();

	qglPopMatrix ();
}

/*
===============
R_DrawTriangles
===============
*/
void R_DrawTriangles (void)
{
	int i;
	int lastflags = -1;
	triangle_t **p;
	triangle_t *tri;

	GL_TexEnv (GL_MODULATE);
	for (i = 0, p = r_newrefdef.triangles; i < r_newrefdef.num_triangles; i++, p++)
	{
		tri = *p;
		if (tri->flags != lastflags)
		{
			if (tri->flags & TRI_TWOSIDED) {
				qglDisable (GL_CULL_FACE);
			} else {
				qglEnable (GL_CULL_FACE);
			}
			if (tri->alpha < 1) {
				qglDepthMask (GL_FALSE);		// no z buffering
				qglEnable (GL_BLEND);
			} else {
				qglDepthMask (1);		// back to normal Z buffering
				qglDisable (GL_BLEND);
			}
		}
		GL_DrawTriangle(tri);
	}
	qglEnable (GL_CULL_FACE);
	qglDepthMask (1);		// back to normal Z buffering
	qglDisable (GL_BLEND);
	qglColor4f (1,1,1,1);
	GL_TexEnv (GL_REPLACE);
}
