r_bsp.c

/*
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.

*/
// r_bsp.c

#include "quakedef.h"
#include "r_local.h"

//
// current entity info
//
qboolean    insubmodel;
entity_t    *currententity;
vec3_t      modelorg, base_modelorg;
                // modelorg is the viewpoint reletive to
                // the currently rendering entity
vec3_t      r_entorigin;  // the currently rendering entity in world
                // coordinates

float     entity_rotation[3][3];

vec3_t      r_worldmodelorg;

int       r_currentbkey;

typedef enum {touchessolid, drawnode, nodrawnode} solidstate_t;

#define MAX_BMODEL_VERTS  500     // 6K
#define MAX_BMODEL_EDGES  1000    // 12K

static mvertex_t  *pbverts;
static bedge_t    *pbedges;
static int      numbverts, numbedges;

static mvertex_t  *pfrontenter, *pfrontexit;

static qboolean   makeclippededge;

#if defined(M68KASM) || defined(PPCASM)
extern void R_RotateBmodel (void);
#endif
#ifdef M68KASM
extern void R_RecursiveWorldNode (mnode_t *node, int clipflags);
#endif

//===========================================================================

/*
================
R_EntityRotate
================
*/
void R_EntityRotate (vec3_t vec)
{
  vec3_t  tvec;

  VectorCopy (vec, tvec);
  vec[0] = DotProduct (entity_rotation[0], tvec);
  vec[1] = DotProduct (entity_rotation[1], tvec);
  vec[2] = DotProduct (entity_rotation[2], tvec);
}


#if !defined(M68KASM) && !defined(PPCASM)
/*
================
R_RotateBmodel
================
*/
void R_RotateBmodel (void)
{
  float angle, s, c, temp1[3][3], temp2[3][3], temp3[3][3];

// TODO: should use a look-up table
// TODO: should really be stored with the entity instead of being reconstructed
// TODO: could cache lazily, stored in the entity
// TODO: share work with R_SetUpAliasTransform

// yaw
  angle = currententity->angles[YAW];   
  angle = angle * M_PI*2 / 360;
  s = sin(angle);
  c = cos(angle);

  temp1[0][0] = c;
  temp1[0][1] = s;
  temp1[0][2] = 0;
  temp1[1][0] = -s;
  temp1[1][1] = c;
  temp1[1][2] = 0;
  temp1[2][0] = 0;
  temp1[2][1] = 0;
  temp1[2][2] = 1;


// pitch
  angle = currententity->angles[PITCH];   
  angle = angle * M_PI*2 / 360;
  s = sin(angle);
  c = cos(angle);

  temp2[0][0] = c;
  temp2[0][1] = 0;
  temp2[0][2] = -s;
  temp2[1][0] = 0;
  temp2[1][1] = 1;
  temp2[1][2] = 0;
  temp2[2][0] = s;
  temp2[2][1] = 0;
  temp2[2][2] = c;

  R_ConcatRotations (temp2, temp1, temp3);

// roll
  angle = currententity->angles[ROLL];    
  angle = angle * M_PI*2 / 360;
  s = sin(angle);
  c = cos(angle);

  temp1[0][0] = 1;
  temp1[0][1] = 0;
  temp1[0][2] = 0;
  temp1[1][0] = 0;
  temp1[1][1] = c;
  temp1[1][2] = s;
  temp1[2][0] = 0;
  temp1[2][1] = -s;
  temp1[2][2] = c;

  R_ConcatRotations (temp1, temp3, entity_rotation);

//
// rotate modelorg and the transformation matrix
//
  R_EntityRotate (modelorg);
  R_EntityRotate (vpn);
  R_EntityRotate (vright);
  R_EntityRotate (vup);

  R_TransformFrustum ();
}
#endif


/*
================
R_RecursiveClipBPoly
================
*/
void R_RecursiveClipBPoly (bedge_t *pedges, mnode_t *pnode, msurface_t *psurf)
{
  bedge_t   *psideedges[2], *pnextedge, *ptedge;
  int     i, side, lastside;
  float   dist, frac, lastdist;
  mplane_t  *splitplane, tplane;
  mvertex_t *pvert, *plastvert, *ptvert;
  mnode_t   *pn;

  psideedges[0] = psideedges[1] = NULL;

  makeclippededge = false;

// transform the BSP plane into model space
// FIXME: cache these?
  splitplane = pnode->plane;
  tplane.dist = splitplane->dist -
      DotProduct(r_entorigin, splitplane->normal);
  tplane.normal[0] = DotProduct (entity_rotation[0], splitplane->normal);
  tplane.normal[1] = DotProduct (entity_rotation[1], splitplane->normal);
  tplane.normal[2] = DotProduct (entity_rotation[2], splitplane->normal);

// clip edges to BSP plane
  for ( ; pedges ; pedges = pnextedge)
  {
    pnextedge = pedges->pnext;

  // set the status for the last point as the previous point
  // FIXME: cache this stuff somehow?
    plastvert = pedges->v[0];
    lastdist = DotProduct (plastvert->position, tplane.normal) -
           tplane.dist;

    if (lastdist > 0)
      lastside = 0;
    else
      lastside = 1;

    pvert = pedges->v[1];

    dist = DotProduct (pvert->position, tplane.normal) - tplane.dist;

    if (dist > 0)
      side = 0;
    else
      side = 1;

    if (side != lastside)
    {
    // clipped
      if (numbverts >= MAX_BMODEL_VERTS)
        return;

    // generate the clipped vertex
      frac = lastdist / (lastdist - dist);
      ptvert = &pbverts[numbverts++];
      ptvert->position[0] = plastvert->position[0] +
          frac * (pvert->position[0] -
          plastvert->position[0]);
      ptvert->position[1] = plastvert->position[1] +
          frac * (pvert->position[1] -
          plastvert->position[1]);
      ptvert->position[2] = plastvert->position[2] +
          frac * (pvert->position[2] -
          plastvert->position[2]);

    // split into two edges, one on each side, and remember entering
    // and exiting points
    // FIXME: share the clip edge by having a winding direction flag?
      if (numbedges >= (MAX_BMODEL_EDGES - 1))
      {
        Con_Printf ("Out of edges for bmodel\n");
        return;
      }

      ptedge = &pbedges[numbedges];
      ptedge->pnext = psideedges[lastside];
      psideedges[lastside] = ptedge;
      ptedge->v[0] = plastvert;
      ptedge->v[1] = ptvert;

      ptedge = &pbedges[numbedges + 1];
      ptedge->pnext = psideedges[side];
      psideedges[side] = ptedge;
      ptedge->v[0] = ptvert;
      ptedge->v[1] = pvert;

      numbedges += 2;

      if (side == 0)
      {
      // entering for front, exiting for back
        pfrontenter = ptvert;
        makeclippededge = true;
      }
      else
      {
        pfrontexit = ptvert;
        makeclippededge = true;
      }
    }
    else
    {
    // add the edge to the appropriate side
      pedges->pnext = psideedges[side];
      psideedges[side] = pedges;
    }
  }

// if anything was clipped, reconstitute and add the edges along the clip
// plane to both sides (but in opposite directions)
  if (makeclippededge)
  {
    if (numbedges >= (MAX_BMODEL_EDGES - 2))
    {
      Con_Printf ("Out of edges for bmodel\n");
      return;
    }

    ptedge = &pbedges[numbedges];
    ptedge->pnext = psideedges[0];
    psideedges[0] = ptedge;
    ptedge->v[0] = pfrontexit;
    ptedge->v[1] = pfrontenter;

    ptedge = &pbedges[numbedges + 1];
    ptedge->pnext = psideedges[1];
    psideedges[1] = ptedge;
    ptedge->v[0] = pfrontenter;
    ptedge->v[1] = pfrontexit;

    numbedges += 2;
  }

// draw or recurse further
  for (i=0 ; i<2 ; i++)
  {
    if (psideedges[i])
    {
    // draw if we've reached a non-solid leaf, done if all that's left is a
    // solid leaf, and continue down the tree if it's not a leaf
      pn = pnode->children[i];

    // we're done with this branch if the node or leaf isn't in the PVS
      if (pn->visframe == r_visframecount)
      {
        if (pn->contents < 0)
        {
          if (pn->contents != CONTENTS_SOLID)
          {
            r_currentbkey = ((mleaf_t *)pn)->key;
            R_RenderBmodelFace (psideedges[i], psurf);
          }
        }
        else
        {
          R_RecursiveClipBPoly (psideedges[i], pnode->children[i],
                    psurf);
        }
      }
    }
  }
}


/*
================
R_DrawSolidClippedSubmodelPolygons
================
*/
void R_DrawSolidClippedSubmodelPolygons (model_t *pmodel)
{
  int     i, j, lindex;
  vec_t   dot;
  msurface_t  *psurf;
  int     numsurfaces;
  mplane_t  *pplane;
  static mvertex_t bverts[MAX_BMODEL_VERTS];  /* phx */
  static bedge_t   bedges[MAX_BMODEL_EDGES], *pbedge;  /* phx */
  medge_t   *pedge, *pedges;

// FIXME: use bounding-box-based frustum clipping info?

  psurf = &pmodel->surfaces[pmodel->firstmodelsurface];
  numsurfaces = pmodel->nummodelsurfaces;
  pedges = pmodel->edges;

  for (i=0 ; i<numsurfaces ; i++, psurf++)
  {
  // find which side of the node we are on
    pplane = psurf->plane;

    dot = DotProduct (modelorg, pplane->normal) - pplane->dist;

  // draw the polygon
    if (((psurf->flags & SURF_PLANEBACK) && (dot < -BACKFACE_EPSILON)) ||
      (!(psurf->flags & SURF_PLANEBACK) && (dot > BACKFACE_EPSILON)))
    {
    // FIXME: use bounding-box-based frustum clipping info?

    // copy the edges to bedges, flipping if necessary so always
    // clockwise winding
    // FIXME: if edges and vertices get caches, these assignments must move
    // outside the loop, and overflow checking must be done here
      pbverts = bverts;
      pbedges = bedges;
      numbverts = numbedges = 0;

      if (psurf->numedges > 0)
      {
        pbedge = &bedges[numbedges];
        numbedges += psurf->numedges;

        for (j=0 ; j<psurf->numedges ; j++)
        {
           lindex = pmodel->surfedges[psurf->firstedge+j];

          if (lindex > 0)
          {
            pedge = &pedges[lindex];
            pbedge[j].v[0] = &r_pcurrentvertbase[pedge->v[0]];
            pbedge[j].v[1] = &r_pcurrentvertbase[pedge->v[1]];
          }
          else
          {
            lindex = -lindex;
            pedge = &pedges[lindex];
            pbedge[j].v[0] = &r_pcurrentvertbase[pedge->v[1]];
            pbedge[j].v[1] = &r_pcurrentvertbase[pedge->v[0]];
          }

          pbedge[j].pnext = &pbedge[j+1];
        }

        pbedge[j-1].pnext = NULL; // mark end of edges

        R_RecursiveClipBPoly (pbedge, currententity->topnode, psurf);
      }
      else
      {
        Sys_Error ("no edges in bmodel");
      }
    }
  }
}


/*
================
R_DrawSubmodelPolygons
================
*/
void R_DrawSubmodelPolygons (model_t *pmodel, int clipflags)
{
  int     i;
  vec_t   dot;
  msurface_t  *psurf;
  int     numsurfaces;
  mplane_t  *pplane;

// FIXME: use bounding-box-based frustum clipping info?

  psurf = &pmodel->surfaces[pmodel->firstmodelsurface];
  numsurfaces = pmodel->nummodelsurfaces;

  for (i=0 ; i<numsurfaces ; i++, psurf++)
  {
  // find which side of the node we are on
    pplane = psurf->plane;

    dot = DotProduct (modelorg, pplane->normal) - pplane->dist;

  // draw the polygon
    if (((psurf->flags & SURF_PLANEBACK) && (dot < -BACKFACE_EPSILON)) ||
      (!(psurf->flags & SURF_PLANEBACK) && (dot > BACKFACE_EPSILON)))
    {
      r_currentkey = ((mleaf_t *)currententity->topnode)->key;

    // FIXME: use bounding-box-based frustum clipping info?
      R_RenderFace (psurf, clipflags);
    }
  }
}


#ifndef M68KASM
/*
================
R_RecursiveWorldNode
================
*/
void R_RecursiveWorldNode (mnode_t *node, int clipflags)
{
  int     i, c, side, *pindex;
  vec3_t    acceptpt, rejectpt;
  mplane_t  *plane;
  msurface_t  *surf, **mark;
  mleaf_t   *pleaf;
  double    d, dot;

  if (node->contents == CONTENTS_SOLID)
    return;   // solid

  if (node->visframe != r_visframecount)
    return;

// cull the clipping planes if not trivial accept
// FIXME: the compiler is doing a lousy job of optimizing here; it could be
//  twice as fast in ASM
  if (clipflags)
  {
    for (i=0 ; i<4 ; i++)
    {
      if (! (clipflags & (1<<i)) )
        continue; // don't need to clip against it

    // generate accept and reject points
    // FIXME: do with fast look-ups or integer tests based on the sign bit
    // of the floating point values

      pindex = pfrustum_indexes[i];

      rejectpt[0] = (float)node->minmaxs[pindex[0]];
      rejectpt[1] = (float)node->minmaxs[pindex[1]];
      rejectpt[2] = (float)node->minmaxs[pindex[2]];
      
      d = DotProduct (rejectpt, view_clipplanes[i].normal);
      d -= view_clipplanes[i].dist;

      if (d <= 0)
        return;

      acceptpt[0] = (float)node->minmaxs[pindex[3+0]];
      acceptpt[1] = (float)node->minmaxs[pindex[3+1]];
      acceptpt[2] = (float)node->minmaxs[pindex[3+2]];

      d = DotProduct (acceptpt, view_clipplanes[i].normal);
      d -= view_clipplanes[i].dist;

      if (d >= 0)
        clipflags &= ~(1<<i); // node is entirely on screen
    }
  }
  
// if a leaf node, draw stuff
  if (node->contents < 0)
  {
    pleaf = (mleaf_t *)node;

    mark = pleaf->firstmarksurface;
    c = pleaf->nummarksurfaces;

    if (c)
    {
      do
      {
        (*mark)->visframe = r_framecount;
        mark++;
      } while (--c);
    }

  // deal with model fragments in this leaf
    if (pleaf->efrags)
    {
      R_StoreEfrags (&pleaf->efrags);
    }

    pleaf->key = r_currentkey;
    r_currentkey++;   // all bmodels in a leaf share the same key
  }
  else
  {
  // node is just a decision point, so go down the apropriate sides

  // find which side of the node we are on
    plane = node->plane;

    switch (plane->type)
    {
    case PLANE_X:
      dot = modelorg[0] - plane->dist;
      break;
    case PLANE_Y:
      dot = modelorg[1] - plane->dist;
      break;
    case PLANE_Z:
      dot = modelorg[2] - plane->dist;
      break;
    default:
      dot = DotProduct (modelorg, plane->normal) - plane->dist;
      break;
    }
  
    if (dot >= 0)
      side = 0;
    else
      side = 1;

  // recurse down the children, front side first
    R_RecursiveWorldNode (node->children[side], clipflags);

  // draw stuff
    c = node->numsurfaces;

    if (c)
    {
      surf = cl.worldmodel->surfaces + node->firstsurface;

      if (dot < -BACKFACE_EPSILON)
      {
        do
        {
          if ((surf->flags & SURF_PLANEBACK) &&
            (surf->visframe == r_framecount))
          {
            if (r_drawpolys)
            {
              if (r_worldpolysbacktofront)
              {
                if (numbtofpolys < MAX_BTOFPOLYS)
                {
                  pbtofpolys[numbtofpolys].clipflags =
                      clipflags;
                  pbtofpolys[numbtofpolys].psurf = surf;
                  numbtofpolys++;
                }
              }
              else
              {
                R_RenderPoly (surf, clipflags);
              }
            }
            else
            {
              R_RenderFace (surf, clipflags);
            }
          }

          surf++;
        } while (--c);
      }
      else if (dot > BACKFACE_EPSILON)
      {
        do
        {
          if (!(surf->flags & SURF_PLANEBACK) &&
            (surf->visframe == r_framecount))
          {
            if (r_drawpolys)
            {
              if (r_worldpolysbacktofront)
              {
                if (numbtofpolys < MAX_BTOFPOLYS)
                {
                  pbtofpolys[numbtofpolys].clipflags =
                      clipflags;
                  pbtofpolys[numbtofpolys].psurf = surf;
                  numbtofpolys++;
                }
              }
              else
              {
                R_RenderPoly (surf, clipflags);
              }
            }
            else
            {
              R_RenderFace (surf, clipflags);
            }
          }

          surf++;
        } while (--c);
      }

    // all surfaces on the same node share the same sequence number
      r_currentkey++;
    }

  // recurse down the back side
    R_RecursiveWorldNode (node->children[!side], clipflags);
  }
}
#endif


/*
================
R_RenderWorld
================
*/
void R_RenderWorld (void)
{
  int     i;
  model_t   *clmodel;
  static btofpoly_t  btofpolys[MAX_BTOFPOLYS]; /* phx */

  pbtofpolys = btofpolys;

  currententity = &cl_entities[0];
  VectorCopy (r_origin, modelorg);
  clmodel = currententity->model;
  r_pcurrentvertbase = clmodel->vertexes;

  R_RecursiveWorldNode (clmodel->nodes, 15);

// if the driver wants the polygons back to front, play the visible ones back
// in that order
  if (r_worldpolysbacktofront)
  {
    for (i=numbtofpolys-1 ; i>=0 ; i--)
    {
      R_RenderPoly (btofpolys[i].psurf, btofpolys[i].clipflags);
    }
  }
}