/*
Copyright (C) 1996-1997 Id Software, Inc.

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.

*/
#include "quakedef.h"

static  hull_t    box_hull;
static  dclipnode_t box_clipnodes[6];
static  mplane_t  box_planes[6];

extern  vec3_t player_mins;
extern  vec3_t player_maxs;

/*
===================
PM_InitBoxHull

Set up the planes and clipnodes so that the six floats of a bounding box
can just be stored out and get a proper hull_t structure.
===================
*/
void PM_InitBoxHull (void)
{
  int   i;
  int   side;

  box_hull.clipnodes = box_clipnodes;
  box_hull.planes = box_planes;
  box_hull.firstclipnode = 0;
  box_hull.lastclipnode = 5;

  for (i=0 ; i<6 ; i++)
  {
    box_clipnodes[i].planenum = i;
    
    side = i&1;
    
    box_clipnodes[i].children[side] = CONTENTS_EMPTY;
    if (i != 5)
      box_clipnodes[i].children[side^1] = i + 1;
    else
      box_clipnodes[i].children[side^1] = CONTENTS_SOLID;
    
    box_planes[i].type = i>>1;
    box_planes[i].normal[i>>1] = 1;
  }
  
}


/*
===================
PM_HullForBox

To keep everything totally uniform, bounding boxes are turned into small
BSP trees instead of being compared directly.
===================
*/
hull_t  *PM_HullForBox (vec3_t mins, vec3_t maxs)
{
  box_planes[0].dist = maxs[0];
  box_planes[1].dist = mins[0];
  box_planes[2].dist = maxs[1];
  box_planes[3].dist = mins[1];
  box_planes[4].dist = maxs[2];
  box_planes[5].dist = mins[2];

  return &box_hull;
}


/*
==================
PM_HullPointContents

==================
*/
int PM_HullPointContents (hull_t *hull, int num, vec3_t p)
{
  float   d;
  dclipnode_t *node;
  mplane_t  *plane;

  while (num >= 0)
  {
    if (num < hull->firstclipnode || num > hull->lastclipnode)
      Sys_Error ("PM_HullPointContents: bad node number");
  
    node = hull->clipnodes + num;
    plane = hull->planes + node->planenum;
    
    if (plane->type < 3)
      d = p[plane->type] - plane->dist;
    else
      d = DotProduct (plane->normal, p) - plane->dist;
    if (d < 0)
      num = node->children[1];
    else
      num = node->children[0];
  }
  
  return num;
}

/*
==================
PM_PointContents

==================
*/
int PM_PointContents (vec3_t p)
{
  float   d;
  dclipnode_t *node;
  mplane_t  *plane;
  hull_t    *hull;
  int     num;

  hull = &pmove.physents[0].model->hulls[0];

  num = hull->firstclipnode;

  while (num >= 0)
  {
    if (num < hull->firstclipnode || num > hull->lastclipnode)
      Sys_Error ("PM_HullPointContents: bad node number");
  
    node = hull->clipnodes + num;
    plane = hull->planes + node->planenum;
    
    if (plane->type < 3)
      d = p[plane->type] - plane->dist;
    else
      d = DotProduct (plane->normal, p) - plane->dist;
    if (d < 0)
      num = node->children[1];
    else
      num = node->children[0];
  }
  
  return num;
}

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

LINE TESTING IN HULLS

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

// 1/32 epsilon to keep floating point happy
#define DIST_EPSILON  (0.03125)

/*
==================
PM_RecursiveHullCheck

==================
*/
qboolean PM_RecursiveHullCheck (hull_t *hull, int num, float p1f, float p2f, vec3_t p1, vec3_t p2, pmtrace_t *trace)
{
  dclipnode_t *node;
  mplane_t  *plane;
  float   t1, t2;
  float   frac;
  int     i;
  vec3_t    mid;
  int     side;
  float   midf;

// check for empty
  if (num < 0)
  {
    if (num != CONTENTS_SOLID)
    {
      trace->allsolid = false;
      if (num == CONTENTS_EMPTY)
        trace->inopen = true;
      else
        trace->inwater = true;
    }
    else
      trace->startsolid = true;
    return true;    // empty
  }

  if (num < hull->firstclipnode || num > hull->lastclipnode)
    Sys_Error ("PM_RecursiveHullCheck: bad node number");

//
// find the point distances
//
  node = hull->clipnodes + num;
  plane = hull->planes + node->planenum;

  if (plane->type < 3)
  {
    t1 = p1[plane->type] - plane->dist;
    t2 = p2[plane->type] - plane->dist;
  }
  else
  {
    t1 = DotProduct (plane->normal, p1) - plane->dist;
    t2 = DotProduct (plane->normal, p2) - plane->dist;
  }
  
#if 1
  if (t1 >= 0 && t2 >= 0)
    return PM_RecursiveHullCheck (hull, node->children[0], p1f, p2f, p1, p2, trace);
  if (t1 < 0 && t2 < 0)
    return PM_RecursiveHullCheck (hull, node->children[1], p1f, p2f, p1, p2, trace);
#else
  if ( (t1 >= DIST_EPSILON && t2 >= DIST_EPSILON) || (t2 > t1 && t1 >= 0) )
    return PM_RecursiveHullCheck (hull, node->children[0], p1f, p2f, p1, p2, trace);
  if ( (t1 <= -DIST_EPSILON && t2 <= -DIST_EPSILON) || (t2 < t1 && t1 <= 0) )
    return PM_RecursiveHullCheck (hull, node->children[1], p1f, p2f, p1, p2, trace);
#endif

// put the crosspoint DIST_EPSILON pixels on the near side
  if (t1 < 0)
    frac = (t1 + DIST_EPSILON)/(t1-t2);
  else
    frac = (t1 - DIST_EPSILON)/(t1-t2);
  if (frac < 0)
    frac = 0;
  if (frac > 1)
    frac = 1;
    
  midf = p1f + (p2f - p1f)*frac;
  for (i=0 ; i<3 ; i++)
    mid[i] = p1[i] + frac*(p2[i] - p1[i]);

  side = (t1 < 0);

// move up to the node
  if (!PM_RecursiveHullCheck (hull, node->children[side], p1f, midf, p1, mid, trace) )
    return false;

#ifdef PARANOID
  if (PM_HullPointContents (pm_hullmodel, mid, node->children[side])
  == CONTENTS_SOLID)
  {
    Con_Printf ("mid PointInHullSolid\n");
    return false;
  }
#endif
  
  if (PM_HullPointContents (hull, node->children[side^1], mid)
  != CONTENTS_SOLID)
// go past the node
    return PM_RecursiveHullCheck (hull, node->children[side^1], midf, p2f, mid, p2, trace);
  
  if (trace->allsolid)
    return false;   // never got out of the solid area
    
//==================
// the other side of the node is solid, this is the impact point
//==================
  if (!side)
  {
    VectorCopy (plane->normal, trace->plane.normal);
    trace->plane.dist = plane->dist;
  }
  else
  {
    VectorSubtract (vec3_origin, plane->normal, trace->plane.normal);
    trace->plane.dist = -plane->dist;
  }

  while (PM_HullPointContents (hull, hull->firstclipnode, mid)
  == CONTENTS_SOLID)
  { // shouldn't really happen, but does occasionally
    frac -= 0.1;
    if (frac < 0)
    {
      trace->fraction = midf;
      VectorCopy (mid, trace->endpos);
      Con_DPrintf ("backup past 0\n");
      return false;
    }
    midf = p1f + (p2f - p1f)*frac;
    for (i=0 ; i<3 ; i++)
      mid[i] = p1[i] + frac*(p2[i] - p1[i]);
  }

  trace->fraction = midf;
  VectorCopy (mid, trace->endpos);

  return false;
}


/*
================
PM_TestPlayerPosition

Returns false if the given player position is not valid (in solid)
================
*/
qboolean PM_TestPlayerPosition (vec3_t pos)
{
  int     i;
  physent_t *pe;
  vec3_t    mins, maxs, test;
  hull_t    *hull;

  for (i=0 ; i< pmove.numphysent ; i++)
  {
    pe = &pmove.physents[i];
  // get the clipping hull
    if (pe->model)
      hull = &pmove.physents[i].model->hulls[1];
    else
    {
      VectorSubtract (pe->mins, player_maxs, mins);
      VectorSubtract (pe->maxs, player_mins, maxs);
      hull = PM_HullForBox (mins, maxs);
    }

    VectorSubtract (pos, pe->origin, test);

    if (PM_HullPointContents (hull, hull->firstclipnode, test) == CONTENTS_SOLID)
      return false;
  }

  return true;
}

/*
================
PM_PlayerMove
================
*/
pmtrace_t PM_PlayerMove (vec3_t start, vec3_t end)
{
  pmtrace_t   trace, total;
  vec3_t    offset;
  vec3_t    start_l, end_l;
  hull_t    *hull;
  int     i;
  physent_t *pe;
  vec3_t    mins, maxs;

// fill in a default trace
  memset (&total, 0, sizeof(pmtrace_t));
  total.fraction = 1;
  total.ent = -1;
  VectorCopy (end, total.endpos);

  for (i=0 ; i< pmove.numphysent ; i++)
  {
    pe = &pmove.physents[i];
  // get the clipping hull
    if (pe->model)
      hull = &pmove.physents[i].model->hulls[1];
    else
    {
      VectorSubtract (pe->mins, player_maxs, mins);
      VectorSubtract (pe->maxs, player_mins, maxs);
      hull = PM_HullForBox (mins, maxs);
    }

  // PM_HullForEntity (ent, mins, maxs, offset);
  VectorCopy (pe->origin, offset);

    VectorSubtract (start, offset, start_l);
    VectorSubtract (end, offset, end_l);

  // fill in a default trace
    memset (&trace, 0, sizeof(pmtrace_t));
    trace.fraction = 1;
    trace.allsolid = true;
//    trace.startsolid = true;
    VectorCopy (end, trace.endpos);

  // trace a line through the apropriate clipping hull
    PM_RecursiveHullCheck (hull, hull->firstclipnode, 0, 1, start_l, end_l, &trace);

    if (trace.allsolid)
      trace.startsolid = true;
    if (trace.startsolid)
      trace.fraction = 0;

  // did we clip the move?
    if (trace.fraction < total.fraction)
    {
      // fix trace up by the offset
      VectorAdd (trace.endpos, offset, trace.endpos);
      total = trace;
      total.ent = i;
    }

  }

  return total;
}