//-----------------------------------------------------------------------------
//
//  $Logfile:: /Source/cl_pred.c                                              $
// $Revision:: 4                                                              $
//   $Author:: Burgermac                                                      $
//     $Date:: 8/8/01 4:48 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:
//

#include "client.h"
#include "sinmdl.h"
#include "linklist.h"

#ifdef __USEA3D
#include "sin_a3d.h"
#include "A3DWrapperDP.h"
#endif

/*
===================
CL_CheckPredictionError
===================
*/
void CL_CheckPredictionError (void)
{
	int		frame;
	int		delta[3];
	int		i;
	int		len;

	if (!cl_predict->value || (cl.frame.playerstate.pmove.pm_flags & PMF_NO_PREDICTION))
		return;

	// calculate the last usercmd_t we sent that the server has processed
	frame = cls.netchan.incoming_acknowledged;
	frame &= (CMD_BACKUP-1);

	// compare what the server returned with what we had predicted it to be
	VectorSubtract (cl.frame.playerstate.pmove.origin, cl.predicted_origins[frame], delta);

	// save the prediction error for interpolation
	len = abs(delta[0]) + abs(delta[1]) + abs(delta[2]);
	if (len > 640)	// 80 world units
	{	// a teleport or something
		VectorClear (cl.prediction_error);
	}
	else
	{
		if (cl_showmiss->value && (delta[0] || delta[1] || delta[2]) )
			Com_Printf ("prediction miss on %i: %i\n", cl.frame.serverframe,
			delta[0] + delta[1] + delta[2]);

		VectorCopy (cl.frame.playerstate.pmove.origin, cl.predicted_origins[frame]);

		// save for error itnerpolation
		for (i=0 ; i<3 ; i++)
			cl.prediction_error[i] = delta[i]*0.125;
	}
}

typedef struct clipent_s
{
	entity_state_t * ent;
	trace_t trace;
	struct clipent_s *prev;
	struct clipent_s *next;
} clipent_t;

static clipent_t *clip_freelist;
static clipent_t *clip_candidatelist;

void CL_PredictRelease(void)
{
	clipent_t *WorkPtr;
	clipent_t *Next;
	clipent_t *Root;
	WorkPtr = clip_freelist;
	if (WorkPtr)
	{
		clip_freelist = 0;
		Root = WorkPtr;
		do
		{
			Next = WorkPtr->next;
			free(WorkPtr);
			WorkPtr = Next;
		} while (WorkPtr!=Root);
	}
	WorkPtr = clip_candidatelist;
	if (WorkPtr)
	{
		clip_candidatelist = 0;
		Root = WorkPtr;
		do {
			Next = WorkPtr->next;
			free(WorkPtr);
			WorkPtr = Next;
		} while (WorkPtr!=Root);
	}
}

/*
====================
CL_FreeClipCandidates
====================
*/
static void CL_FreeClipCandidates( void )
{
	clipent_t *next, *clip;

	if (clip_candidatelist ) {
		if ( !clip_freelist ) {
			LL_New( clip_freelist, clipent_t, next, prev );
		}
		for ( clip = clip_candidatelist->next; clip != clip_candidatelist; clip = next ) {
			next = clip->next;
			LL_Remove( clip, next, prev );
			LL_Add( clip_freelist, clip, next, prev );
		}
	}
}

/*
====================
CL_AddClipCandidate
====================
*/
static void CL_AddClipCandidate( entity_state_t * ent, trace_t * trace )
{
	clipent_t * clip;

	if ( !clip_candidatelist ) {
		LL_New( clip_candidatelist, clipent_t, next, prev );
	}
	if ( clip_freelist && clip_freelist->next != clip_freelist ) {
		clip = clip_freelist->next;
		LL_Remove( clip, next, prev );
	} else {
		LL_New( clip, clipent_t, next, prev );
	}
	clip->ent = ent;
	clip->trace = *trace;
	LL_SortedInsertion( clip_candidatelist, clip, next, prev, clipent_t, trace.fraction );
}

/*
====================
CL_ClipMoveToEntities

====================
*/
void CL_ClipMoveToEntities ( vec3_t start,const vec3_t mins,const vec3_t maxs, vec3_t end, trace_t *tr
							, int contents_mask, qboolean fulltrace, int passentnum)
{
	int			i, x, y, zd, zu;
	trace_t		trace;
	int			headnode;
	const vec_t	*angles;/* vec3_t */
	entity_state_t	*ent;
	int			num;
	cmodel_t		*cmodel;
	vec3_t		bmins, bmaxs;

	for (i=0 ; i<cl.frame.num_entities ; i++) {
		num = (cl.frame.parse_entities + i)&(MAX_PARSE_ENTITIES-1);
		ent = &cl_parse_entities[num];

		if (!ent->solid)
			continue;

		if ( ( ent->number == 1 ) || ( ent->number == 2 ) ) {
			gravityaxis_t grav;

			grav = gravity_axis[ EFFECTS_TO_GRAVITYAXIS( ent->effects ) ];

			// encoded bbox
			x = (ent->solid & 255);
			y = ((ent->solid>>8) & 255);
			zd = (8*((ent->solid>>16) & 63) - 128) * grav.sign;
			zu = (((ent->solid>>22) & 511) - 64) * grav.sign;

			bmins[ grav.x ] = -x;
			bmaxs[ grav.x ] = x;
			bmins[ grav.y ] = -y;
			bmaxs[ grav.y ] = y;
			bmins[ grav.z ] = zd;
			bmaxs[ grav.z ] = zu;
		}

		if (ent->number == passentnum)
			continue;

		if (ent->solid == 31) {	// special value for bmodel
			cmodel = cl.model_clip[ent->modelindex];
			if (!cmodel)
				continue;
			headnode = cmodel->headnode;
			angles = ent->angles;
		} else {
			gravityaxis_t grav;

			grav = gravity_axis[ EFFECTS_TO_GRAVITYAXIS( ent->effects ) ];
			// encoded bbox
			x = (ent->solid & 255);
			y = ((ent->solid>>8) & 255);
			zd = (8*((ent->solid>>16) & 63) - 128)*grav.sign;
			zu = (((ent->solid>>22) & 511) - 64)*grav.sign;

			bmins[ grav.x ] = -x;
			bmaxs[ grav.x ] = x;
			bmins[ grav.y ] = -y;
			bmaxs[ grav.y ] = y;
			bmins[ grav.z ] = zd;
			bmaxs[ grav.z ] = zu;

			headnode = CM_HeadnodeForBox (bmins, bmaxs);
			angles = vec3_origin;	// boxes don't rotate
		}

		if (tr->allsolid) {
			CL_FreeClipCandidates();
			return;
		}

		trace = CM_TransformedBoxTrace (start, end,
			mins, maxs, headnode,  contents_mask,
			ent->origin, angles);

		if (trace.allsolid || trace.startsolid || trace.fraction < tr->fraction) {
			if ( fulltrace && ent ) {
				trace.ent = (struct edict_s *)(intptr_t)ent->number;
				CL_AddClipCandidate( ent, &trace );
			} else {
				trace.ent = (struct edict_s *)(intptr_t)ent->number;
				if (tr->startsolid) {
					*tr = trace;
					tr->startsolid = true;
				} else {
					*tr = trace;
				}
			}
		} else if (trace.startsolid) {
			tr->startsolid = true;
		}
	}
	if ( fulltrace && clip_candidatelist ) {
		int defhandle;
		sinmdl_intersection_t *intersect;
		clipent_t *clipent;

		for ( clipent = clip_candidatelist->next; clipent != clip_candidatelist; clipent = clipent->next ) {
			ent = clipent->ent;
			defhandle = re.SINMDL_GetDefHandle( cl.model_draw[ ent->modelindex ] );
			if (defhandle >= 0) {
				AnglesToMat( ent->angles, ent->mat );
				intersect = SINMDL_RayIntersect(defhandle,
					ent->anim,ent->frame,
					ent->scale,ent->origin,
					ent->mat,start,
					end,1);
				if (intersect) {
					vec3_t delta;
					float len;
					*tr = clipent->trace;
					tr->intersect = *intersect;
					VectorSubtract( intersect->position, start, delta );
					len = VectorLength( delta );
					VectorCopy( intersect->normal, tr->plane.normal );
					VectorMA( start, len, tr->dir, tr->endpos );
					break;
				}
			} else {
				*tr = clipent->trace;
				break;
			}
		}
		CL_FreeClipCandidates();
	}
}

/*
================
CL_PMTrace
================
*/
static trace_t CL_PMTrace (vec3_t start,const vec3_t mins,const vec3_t maxs, vec3_t end)
{
	trace_t	t;
	vec3_t mins2;
	vec3_t maxs2;

	// check against world
	t = CM_BoxTrace (start, end, mins, maxs, 0, MASK_PLAYERSOLID);
	if (t.fraction < 1.0)
		t.ent = (struct edict_s *)1;

	// check all other solid models

	// The server expands the bounding box, so we have to do it on the client so that
	// the prediction is correct
	mins2[ 0 ] = mins[ 0 ] - 1;
	mins2[ 1 ] = mins[ 1 ] - 1;
	mins2[ 2 ] = mins[ 2 ] - 1;
	maxs2[ 0 ] = maxs[ 0 ] + 1;
	maxs2[ 1 ] = maxs[ 1 ] + 1;
	maxs2[ 2 ] = maxs[ 2 ] + 1;
	CL_ClipMoveToEntities (start, mins2, maxs2, end, &t, MASK_PLAYERSOLID, false, cl.playernum+1);

	return t;
}

// 2015 code
/*
================
CL_PMBikeTrace
================
*/
static trace_t     CL_PMBikeTrace (vec3_t start,const vec3_t mins,const vec3_t maxs, vec3_t end)
{
	trace_t t;
	vec3_t mins2;
	vec3_t maxs2;

	// check against world
	t = CM_BoxTrace ( start, end, mins, maxs, 0, MASK_SOLID );
	if (t.fraction < 1.0)
		t.ent = (struct edict_s *)1;

	// check all other solid models
	// The server expands the bounding box, so we have to do it on the client so that
	// the prediction is correct
	mins2[ 0 ] = mins[ 0 ] - 1;
	mins2[ 1 ] = mins[ 1 ] - 1;
	mins2[ 2 ] = mins[ 2 ] - 1;
	maxs2[ 0 ] = maxs[ 0 ] + 1;
	maxs2[ 1 ] = maxs[ 1 ] + 1;
	maxs2[ 2 ] = maxs[ 2 ] + 1;
	CL_ClipMoveToEntities ( start, mins2, maxs2, end, &t, MASK_SOLID, false, cl.playernum+1 );

	return t;
}

/*
====================
CL_ClipMoveToPlayer

====================
*/
void CL_ClipMoveToPlayer( vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, trace_t *tr, int contents_mask, qboolean fulltrace )
{
	int x, y, zd, zu;
	trace_t trace;
	int headnode;
	const vec_t *angles;/* vec3_t */
	entity_state_t *ent;
	cmodel_t *cmodel;
	vec3_t bmins, bmaxs;

	ent = &cl_entities[ cl.playernum+1].current;

	if (!ent->solid)
		return;

	if (ent->solid == 31)
	{       // special value for bmodel
		cmodel = cl.model_clip[ent->modelindex];
		if (!cmodel)
			return;
		headnode = cmodel->headnode;
		angles = ent->angles;
	}
	else
	{
		gravityaxis_t grav;

		grav = gravity_axis[ EFFECTS_TO_GRAVITYAXIS( ent->effects ) ];

		// encoded bbox
		x = (ent->solid & 255);
		y = ((ent->solid>>8) & 255);
		zd = ( 8*((ent->solid>>16) & 63) - 128 ) * grav.sign;
		zu = ( ((ent->solid>>22) & 511) - 64 ) * grav.sign;

		bmins[ grav.x ] = -x;
		bmaxs[ grav.x ] = x;
		bmins[ grav.y ] = -y;
		bmaxs[ grav.y ] = y;
		bmins[ grav.z ] = zd;
		bmaxs[ grav.z ] = zu;

		headnode = CM_HeadnodeForBox ( bmins, bmaxs );
		angles = vec3_origin;	// boxes don't rotate
	}

	if (tr->allsolid)
		return;

	trace = CM_TransformedBoxTrace ( start, end,
	                                 mins, maxs, headnode,  contents_mask,
	                                 ent->origin, angles );

	if (trace.allsolid || trace.startsolid ||   trace.fraction < tr->fraction)
	{
		if ( fulltrace && ent )
		{
			int defhandle;
			sinmdl_intersection_t *intersect;

			defhandle = re.SINMDL_GetDefHandle( cl.model_draw[ ent->modelindex ] );
			if (defhandle >= 0)
			{
				AnglesToMat( ent->angles, ent->mat );
				intersect = SINMDL_RayIntersect(defhandle, ent->anim, ent->frame, ent->scale, ent->origin, ent->mat, start, end, 1);
				if (intersect)
				{
					vec3_t delta;
					float len;
					trace.ent = (struct edict_s *)(intptr_t)ent->number;
					*tr = trace;
					tr->intersect = *intersect;
					VectorSubtract( intersect->position, start, delta );
					len = VectorLength( delta );
					VectorCopy( intersect->normal, tr->plane.normal );
					VectorMA( start, len, tr->dir, tr->endpos );
				}
			}
			else
			{
				*tr = trace;
			}
		}
		else
		{
			trace.ent = (struct edict_s *)(intptr_t)ent->number;
			if (tr->startsolid)
			{
				*tr = trace;
				tr->startsolid = true;
			}
			else
				*tr = trace;
		}
	}
	else if (trace.startsolid)
		tr->startsolid = true;
}


/*
================
CL_GenericTrace
================
*/
trace_t CL_GenericTrace (vec3_t start,const vec3_t mins,const vec3_t maxs, vec3_t end, int contents_mask, qboolean fulltrace, int passent)
{
	trace_t t;

	t.ent = NULL;

	if (cl.map_sequence_number != map_sequence_number) {
		return t;
	}

	// check against world
	t = CM_BoxTrace ( start, end, mins, maxs, 0, contents_mask );
	//if (t.fraction < 1.0)
	//	t.ent = (struct edict_s *)1;

	// check all other solid models
	CL_ClipMoveToEntities ( start, mins, maxs, end, &t, contents_mask, fulltrace, passent );
	return t;
}

/*
================
CL_WorldTrace
================
*/
trace_t		CL_WorldTrace (const vec3_t start,const vec3_t mins,const vec3_t maxs,const vec3_t end, int contents_mask)
{
	trace_t t;
	t.ent = NULL;

	if (cl.map_sequence_number != map_sequence_number)
	{
		return t;
	}
	// check against world
	t = CM_BoxTrace ( start, end, mins, maxs, 0, contents_mask );
//	if (t.fraction < 1.0)
//		t.ent = (struct edict_s *)1;

	return t;
}

int		CL_PMpointcontents (vec3_t point)
{
	int			i;
	entity_state_t	*ent;
	int			num;
	cmodel_t		*cmodel;
	int			contents;

	if (cl.map_sequence_number != map_sequence_number)
	{
		return 0;
	}

	contents = CM_PointContents (point, 0);

	for (i=0 ; i<cl.frame.num_entities ; i++)
	{
		num = (cl.frame.parse_entities + i)&(MAX_PARSE_ENTITIES-1);
		ent = &cl_parse_entities[num];

		if (ent->solid != 31) // special value for bmodel
			continue;

		cmodel = cl.model_clip[ent->modelindex];
		if (!cmodel)
			continue;

		contents |= CM_TransformedPointContents (point, cmodel->headnode, ent->origin, ent->angles);
	}

	return contents;
}

/*
=================
CL_PredictMovement

Sets cl.predicted_origin and cl.predicted_angles
=================
*/

void CL_PredictMovement (void)
{
	int		ack, current;
	int		frame;
	int		oldframe;
	usercmd_t	*cmd;
	pmove_t		pm;
	int		i;
	int		step;
	int		oldz;

#ifdef SPLIT_NETWORK_FRAME
	static int	last_step_frame = 0;
#endif

	if (cls.state != ca_active)
		return;

	if (cl_paused->value)
		return;

	if (cl.map_sequence_number != map_sequence_number)
	{
		return;
	}

	if (!cl_predict->value || (cl.frame.playerstate.pmove.pm_flags & PMF_NO_PREDICTION))
	{	// just set angles
		for (i=0; i<3; i++)
		{
			cl.predicted_angles[i] = cl.viewangles[i] + SHORT2ANGLE( cl.frame.playerstate.pmove.delta_angles[i] );
		}
		return;
	}

	ack = cls.netchan.incoming_acknowledged;
	current = cls.netchan.outgoing_sequence;

	// if we are too far out of date, just freeze
	if (current - ack >= CMD_BACKUP)
	{
		if (cl_showmiss->value)
			Com_Printf ("exceeded CMD_BACKUP\n");
		return;
	}

	// copy current state to pmove
	memset(&pm, 0, sizeof(pm));
	if(cl.frame.playerstate.pmove.pm_type == PM_ONBIKE)
		pm.trace = CL_PMBikeTrace;
	else
		pm.trace = CL_PMTrace;
	pm.pointcontents = CL_PMpointcontents;
	
	pm.s = cl.frame.playerstate.pmove;

//	SCR_DebugGraph (current - ack - 1, 0);

	frame = 0;

#ifdef SPLIT_NETWORK_FRAME
	if (cl_async->value)
	{
		// run frames
		while (++ack <= current)
		{
			frame = ack & (CMD_BACKUP-1);
			cmd = &cl.cmds[frame];

			if (!cmd->msec) // Ignore 'null' usercmd entries
				continue;

			pm.cmd = *cmd;
			Pmove (&pm);

		  // save for debug checking
			VectorCopy (pm.s.origin, cl.predicted_origins[frame]);
		}

		oldframe = (ack-2) & (CMD_BACKUP-1);
		oldz = cl.predicted_origins[oldframe][2];
		step = pm.s.origin[2] - oldz;
		if (last_step_frame != current && step > 63 && step < 160 && (pm.s.pm_flags & PMF_ON_GROUND) )
		{
			cl.predicted_step = step * 0.125;
			cl.predicted_step_time = cls.realtime - cls.netFrametime * 500;
			last_step_frame = current;
		}
	}
	else
	{
#endif
		// run frames
		while (++ack < current)
		{
			frame = ack & (CMD_BACKUP-1);
			cmd = &cl.cmds[frame];

			pm.cmd = *cmd;
			Pmove (&pm);

			// save for debug checking
			VectorCopy (pm.s.origin, cl.predicted_origins[frame]);
		}

		oldframe = (ack-2) & (CMD_BACKUP-1);
		oldz = cl.predicted_origins[oldframe][2];
		step = pm.s.origin[2] - oldz;
		if (step > 63 && step < 160 && (pm.s.pm_flags & PMF_ON_GROUND) )
		{
			cl.predicted_step = step * 0.125;
			cl.predicted_step_time = cls.realtime - cls.netFrametime * 500;
		}
#ifdef SPLIT_NETWORK_FRAME
	}
#endif

	// copy results out for rendering
	cl.predicted_origin[0] = pm.s.origin[0]*0.125;
	cl.predicted_origin[1] = pm.s.origin[1]*0.125;
	cl.predicted_origin[2] = pm.s.origin[2]*0.125;

	VectorCopy (pm.viewangles, cl.predicted_angles);

#ifdef __USEA3D
	if (snd_isa3d)
	{
		// In order to properly play underwater effects, 
		// the following line needs to be updated to 
		// return true when Blade is underwater.
		if (pm.waterlevel > 2)
			hA3D_SetEnvironment (A3D_ENV_WATER);
		else
		hA3D_SetEnvironment (A3D_ENV_AIR);
	}
#endif
}
