home *** CD-ROM | disk | FTP | other *** search
/ Enigma Amiga Life 113 / EnigmaAmiga113CD.iso / software / sviluppo / quake_src / r_bsp.c < prev    next >
Encoding:
C/C++ Source or Header  |  2000-06-17  |  16.1 KB  |  684 lines
  1. /*
  2. Copyright (C) 1996-1997 Id Software, Inc.
  3.  
  4. This program is free software; you can redistribute it and/or
  5. modify it under the terms of the GNU General Public License
  6. as published by the Free Software Foundation; either version 2
  7. of the License, or (at your option) any later version.
  8.  
  9. This program is distributed in the hope that it will be useful,
  10. but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
  12.  
  13. See the GNU General Public License for more details.
  14.  
  15. You should have received a copy of the GNU General Public License
  16. along with this program; if not, write to the Free Software
  17. Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  18.  
  19. */
  20. // r_bsp.c
  21.  
  22. #include "quakedef.h"
  23. #include "r_local.h"
  24.  
  25. //
  26. // current entity info
  27. //
  28. qboolean    insubmodel;
  29. entity_t    *currententity;
  30. vec3_t      modelorg, base_modelorg;
  31.                 // modelorg is the viewpoint reletive to
  32.                 // the currently rendering entity
  33. vec3_t      r_entorigin;  // the currently rendering entity in world
  34.                 // coordinates
  35.  
  36. float     entity_rotation[3][3];
  37.  
  38. vec3_t      r_worldmodelorg;
  39.  
  40. int       r_currentbkey;
  41.  
  42. typedef enum {touchessolid, drawnode, nodrawnode} solidstate_t;
  43.  
  44. #define MAX_BMODEL_VERTS  500     // 6K
  45. #define MAX_BMODEL_EDGES  1000    // 12K
  46.  
  47. static mvertex_t  *pbverts;
  48. static bedge_t    *pbedges;
  49. static int      numbverts, numbedges;
  50.  
  51. static mvertex_t  *pfrontenter, *pfrontexit;
  52.  
  53. static qboolean   makeclippededge;
  54.  
  55. #if defined(M68KASM) || defined(PPCASM)
  56. extern void R_RotateBmodel (void);
  57. #endif
  58. #ifdef M68KASM
  59. extern void R_RecursiveWorldNode (mnode_t *node, int clipflags);
  60. #endif
  61.  
  62. //===========================================================================
  63.  
  64. /*
  65. ================
  66. R_EntityRotate
  67. ================
  68. */
  69. void R_EntityRotate (vec3_t vec)
  70. {
  71.   vec3_t  tvec;
  72.  
  73.   VectorCopy (vec, tvec);
  74.   vec[0] = DotProduct (entity_rotation[0], tvec);
  75.   vec[1] = DotProduct (entity_rotation[1], tvec);
  76.   vec[2] = DotProduct (entity_rotation[2], tvec);
  77. }
  78.  
  79.  
  80. #if !defined(M68KASM) && !defined(PPCASM)
  81. /*
  82. ================
  83. R_RotateBmodel
  84. ================
  85. */
  86. void R_RotateBmodel (void)
  87. {
  88.   float angle, s, c, temp1[3][3], temp2[3][3], temp3[3][3];
  89.  
  90. // TODO: should use a look-up table
  91. // TODO: should really be stored with the entity instead of being reconstructed
  92. // TODO: could cache lazily, stored in the entity
  93. // TODO: share work with R_SetUpAliasTransform
  94.  
  95. // yaw
  96.   angle = currententity->angles[YAW];   
  97.   angle = angle * M_PI*2 / 360;
  98.   s = sin(angle);
  99.   c = cos(angle);
  100.  
  101.   temp1[0][0] = c;
  102.   temp1[0][1] = s;
  103.   temp1[0][2] = 0;
  104.   temp1[1][0] = -s;
  105.   temp1[1][1] = c;
  106.   temp1[1][2] = 0;
  107.   temp1[2][0] = 0;
  108.   temp1[2][1] = 0;
  109.   temp1[2][2] = 1;
  110.  
  111.  
  112. // pitch
  113.   angle = currententity->angles[PITCH];   
  114.   angle = angle * M_PI*2 / 360;
  115.   s = sin(angle);
  116.   c = cos(angle);
  117.  
  118.   temp2[0][0] = c;
  119.   temp2[0][1] = 0;
  120.   temp2[0][2] = -s;
  121.   temp2[1][0] = 0;
  122.   temp2[1][1] = 1;
  123.   temp2[1][2] = 0;
  124.   temp2[2][0] = s;
  125.   temp2[2][1] = 0;
  126.   temp2[2][2] = c;
  127.  
  128.   R_ConcatRotations (temp2, temp1, temp3);
  129.  
  130. // roll
  131.   angle = currententity->angles[ROLL];    
  132.   angle = angle * M_PI*2 / 360;
  133.   s = sin(angle);
  134.   c = cos(angle);
  135.  
  136.   temp1[0][0] = 1;
  137.   temp1[0][1] = 0;
  138.   temp1[0][2] = 0;
  139.   temp1[1][0] = 0;
  140.   temp1[1][1] = c;
  141.   temp1[1][2] = s;
  142.   temp1[2][0] = 0;
  143.   temp1[2][1] = -s;
  144.   temp1[2][2] = c;
  145.  
  146.   R_ConcatRotations (temp1, temp3, entity_rotation);
  147.  
  148. //
  149. // rotate modelorg and the transformation matrix
  150. //
  151.   R_EntityRotate (modelorg);
  152.   R_EntityRotate (vpn);
  153.   R_EntityRotate (vright);
  154.   R_EntityRotate (vup);
  155.  
  156.   R_TransformFrustum ();
  157. }
  158. #endif
  159.  
  160.  
  161. /*
  162. ================
  163. R_RecursiveClipBPoly
  164. ================
  165. */
  166. void R_RecursiveClipBPoly (bedge_t *pedges, mnode_t *pnode, msurface_t *psurf)
  167. {
  168.   bedge_t   *psideedges[2], *pnextedge, *ptedge;
  169.   int     i, side, lastside;
  170.   float   dist, frac, lastdist;
  171.   mplane_t  *splitplane, tplane;
  172.   mvertex_t *pvert, *plastvert, *ptvert;
  173.   mnode_t   *pn;
  174.  
  175.   psideedges[0] = psideedges[1] = NULL;
  176.  
  177.   makeclippededge = false;
  178.  
  179. // transform the BSP plane into model space
  180. // FIXME: cache these?
  181.   splitplane = pnode->plane;
  182.   tplane.dist = splitplane->dist -
  183.       DotProduct(r_entorigin, splitplane->normal);
  184.   tplane.normal[0] = DotProduct (entity_rotation[0], splitplane->normal);
  185.   tplane.normal[1] = DotProduct (entity_rotation[1], splitplane->normal);
  186.   tplane.normal[2] = DotProduct (entity_rotation[2], splitplane->normal);
  187.  
  188. // clip edges to BSP plane
  189.   for ( ; pedges ; pedges = pnextedge)
  190.   {
  191.     pnextedge = pedges->pnext;
  192.  
  193.   // set the status for the last point as the previous point
  194.   // FIXME: cache this stuff somehow?
  195.     plastvert = pedges->v[0];
  196.     lastdist = DotProduct (plastvert->position, tplane.normal) -
  197.            tplane.dist;
  198.  
  199.     if (lastdist > 0)
  200.       lastside = 0;
  201.     else
  202.       lastside = 1;
  203.  
  204.     pvert = pedges->v[1];
  205.  
  206.     dist = DotProduct (pvert->position, tplane.normal) - tplane.dist;
  207.  
  208.     if (dist > 0)
  209.       side = 0;
  210.     else
  211.       side = 1;
  212.  
  213.     if (side != lastside)
  214.     {
  215.     // clipped
  216.       if (numbverts >= MAX_BMODEL_VERTS)
  217.         return;
  218.  
  219.     // generate the clipped vertex
  220.       frac = lastdist / (lastdist - dist);
  221.       ptvert = &pbverts[numbverts++];
  222.       ptvert->position[0] = plastvert->position[0] +
  223.           frac * (pvert->position[0] -
  224.           plastvert->position[0]);
  225.       ptvert->position[1] = plastvert->position[1] +
  226.           frac * (pvert->position[1] -
  227.           plastvert->position[1]);
  228.       ptvert->position[2] = plastvert->position[2] +
  229.           frac * (pvert->position[2] -
  230.           plastvert->position[2]);
  231.  
  232.     // split into two edges, one on each side, and remember entering
  233.     // and exiting points
  234.     // FIXME: share the clip edge by having a winding direction flag?
  235.       if (numbedges >= (MAX_BMODEL_EDGES - 1))
  236.       {
  237.         Con_Printf ("Out of edges for bmodel\n");
  238.         return;
  239.       }
  240.  
  241.       ptedge = &pbedges[numbedges];
  242.       ptedge->pnext = psideedges[lastside];
  243.       psideedges[lastside] = ptedge;
  244.       ptedge->v[0] = plastvert;
  245.       ptedge->v[1] = ptvert;
  246.  
  247.       ptedge = &pbedges[numbedges + 1];
  248.       ptedge->pnext = psideedges[side];
  249.       psideedges[side] = ptedge;
  250.       ptedge->v[0] = ptvert;
  251.       ptedge->v[1] = pvert;
  252.  
  253.       numbedges += 2;
  254.  
  255.       if (side == 0)
  256.       {
  257.       // entering for front, exiting for back
  258.         pfrontenter = ptvert;
  259.         makeclippededge = true;
  260.       }
  261.       else
  262.       {
  263.         pfrontexit = ptvert;
  264.         makeclippededge = true;
  265.       }
  266.     }
  267.     else
  268.     {
  269.     // add the edge to the appropriate side
  270.       pedges->pnext = psideedges[side];
  271.       psideedges[side] = pedges;
  272.     }
  273.   }
  274.  
  275. // if anything was clipped, reconstitute and add the edges along the clip
  276. // plane to both sides (but in opposite directions)
  277.   if (makeclippededge)
  278.   {
  279.     if (numbedges >= (MAX_BMODEL_EDGES - 2))
  280.     {
  281.       Con_Printf ("Out of edges for bmodel\n");
  282.       return;
  283.     }
  284.  
  285.     ptedge = &pbedges[numbedges];
  286.     ptedge->pnext = psideedges[0];
  287.     psideedges[0] = ptedge;
  288.     ptedge->v[0] = pfrontexit;
  289.     ptedge->v[1] = pfrontenter;
  290.  
  291.     ptedge = &pbedges[numbedges + 1];
  292.     ptedge->pnext = psideedges[1];
  293.     psideedges[1] = ptedge;
  294.     ptedge->v[0] = pfrontenter;
  295.     ptedge->v[1] = pfrontexit;
  296.  
  297.     numbedges += 2;
  298.   }
  299.  
  300. // draw or recurse further
  301.   for (i=0 ; i<2 ; i++)
  302.   {
  303.     if (psideedges[i])
  304.     {
  305.     // draw if we've reached a non-solid leaf, done if all that's left is a
  306.     // solid leaf, and continue down the tree if it's not a leaf
  307.       pn = pnode->children[i];
  308.  
  309.     // we're done with this branch if the node or leaf isn't in the PVS
  310.       if (pn->visframe == r_visframecount)
  311.       {
  312.         if (pn->contents < 0)
  313.         {
  314.           if (pn->contents != CONTENTS_SOLID)
  315.           {
  316.             r_currentbkey = ((mleaf_t *)pn)->key;
  317.             R_RenderBmodelFace (psideedges[i], psurf);
  318.           }
  319.         }
  320.         else
  321.         {
  322.           R_RecursiveClipBPoly (psideedges[i], pnode->children[i],
  323.                     psurf);
  324.         }
  325.       }
  326.     }
  327.   }
  328. }
  329.  
  330.  
  331. /*
  332. ================
  333. R_DrawSolidClippedSubmodelPolygons
  334. ================
  335. */
  336. void R_DrawSolidClippedSubmodelPolygons (model_t *pmodel)
  337. {
  338.   int     i, j, lindex;
  339.   vec_t   dot;
  340.   msurface_t  *psurf;
  341.   int     numsurfaces;
  342.   mplane_t  *pplane;
  343.   static mvertex_t bverts[MAX_BMODEL_VERTS];  /* phx */
  344.   static bedge_t   bedges[MAX_BMODEL_EDGES], *pbedge;  /* phx */
  345.   medge_t   *pedge, *pedges;
  346.  
  347. // FIXME: use bounding-box-based frustum clipping info?
  348.  
  349.   psurf = &pmodel->surfaces[pmodel->firstmodelsurface];
  350.   numsurfaces = pmodel->nummodelsurfaces;
  351.   pedges = pmodel->edges;
  352.  
  353.   for (i=0 ; i<numsurfaces ; i++, psurf++)
  354.   {
  355.   // find which side of the node we are on
  356.     pplane = psurf->plane;
  357.  
  358.     dot = DotProduct (modelorg, pplane->normal) - pplane->dist;
  359.  
  360.   // draw the polygon
  361.     if (((psurf->flags & SURF_PLANEBACK) && (dot < -BACKFACE_EPSILON)) ||
  362.       (!(psurf->flags & SURF_PLANEBACK) && (dot > BACKFACE_EPSILON)))
  363.     {
  364.     // FIXME: use bounding-box-based frustum clipping info?
  365.  
  366.     // copy the edges to bedges, flipping if necessary so always
  367.     // clockwise winding
  368.     // FIXME: if edges and vertices get caches, these assignments must move
  369.     // outside the loop, and overflow checking must be done here
  370.       pbverts = bverts;
  371.       pbedges = bedges;
  372.       numbverts = numbedges = 0;
  373.  
  374.       if (psurf->numedges > 0)
  375.       {
  376.         pbedge = &bedges[numbedges];
  377.         numbedges += psurf->numedges;
  378.  
  379.         for (j=0 ; j<psurf->numedges ; j++)
  380.         {
  381.            lindex = pmodel->surfedges[psurf->firstedge+j];
  382.  
  383.           if (lindex > 0)
  384.           {
  385.             pedge = &pedges[lindex];
  386.             pbedge[j].v[0] = &r_pcurrentvertbase[pedge->v[0]];
  387.             pbedge[j].v[1] = &r_pcurrentvertbase[pedge->v[1]];
  388.           }
  389.           else
  390.           {
  391.             lindex = -lindex;
  392.             pedge = &pedges[lindex];
  393.             pbedge[j].v[0] = &r_pcurrentvertbase[pedge->v[1]];
  394.             pbedge[j].v[1] = &r_pcurrentvertbase[pedge->v[0]];
  395.           }
  396.  
  397.           pbedge[j].pnext = &pbedge[j+1];
  398.         }
  399.  
  400.         pbedge[j-1].pnext = NULL; // mark end of edges
  401.  
  402.         R_RecursiveClipBPoly (pbedge, currententity->topnode, psurf);
  403.       }
  404.       else
  405.       {
  406.         Sys_Error ("no edges in bmodel");
  407.       }
  408.     }
  409.   }
  410. }
  411.  
  412.  
  413. /*
  414. ================
  415. R_DrawSubmodelPolygons
  416. ================
  417. */
  418. void R_DrawSubmodelPolygons (model_t *pmodel, int clipflags)
  419. {
  420.   int     i;
  421.   vec_t   dot;
  422.   msurface_t  *psurf;
  423.   int     numsurfaces;
  424.   mplane_t  *pplane;
  425.  
  426. // FIXME: use bounding-box-based frustum clipping info?
  427.  
  428.   psurf = &pmodel->surfaces[pmodel->firstmodelsurface];
  429.   numsurfaces = pmodel->nummodelsurfaces;
  430.  
  431.   for (i=0 ; i<numsurfaces ; i++, psurf++)
  432.   {
  433.   // find which side of the node we are on
  434.     pplane = psurf->plane;
  435.  
  436.     dot = DotProduct (modelorg, pplane->normal) - pplane->dist;
  437.  
  438.   // draw the polygon
  439.     if (((psurf->flags & SURF_PLANEBACK) && (dot < -BACKFACE_EPSILON)) ||
  440.       (!(psurf->flags & SURF_PLANEBACK) && (dot > BACKFACE_EPSILON)))
  441.     {
  442.       r_currentkey = ((mleaf_t *)currententity->topnode)->key;
  443.  
  444.     // FIXME: use bounding-box-based frustum clipping info?
  445.       R_RenderFace (psurf, clipflags);
  446.     }
  447.   }
  448. }
  449.  
  450.  
  451. #ifndef M68KASM
  452. /*
  453. ================
  454. R_RecursiveWorldNode
  455. ================
  456. */
  457. void R_RecursiveWorldNode (mnode_t *node, int clipflags)
  458. {
  459.   int     i, c, side, *pindex;
  460.   vec3_t    acceptpt, rejectpt;
  461.   mplane_t  *plane;
  462.   msurface_t  *surf, **mark;
  463.   mleaf_t   *pleaf;
  464.   double    d, dot;
  465.  
  466.   if (node->contents == CONTENTS_SOLID)
  467.     return;   // solid
  468.  
  469.   if (node->visframe != r_visframecount)
  470.     return;
  471.  
  472. // cull the clipping planes if not trivial accept
  473. // FIXME: the compiler is doing a lousy job of optimizing here; it could be
  474. //  twice as fast in ASM
  475.   if (clipflags)
  476.   {
  477.     for (i=0 ; i<4 ; i++)
  478.     {
  479.       if (! (clipflags & (1<<i)) )
  480.         continue; // don't need to clip against it
  481.  
  482.     // generate accept and reject points
  483.     // FIXME: do with fast look-ups or integer tests based on the sign bit
  484.     // of the floating point values
  485.  
  486.       pindex = pfrustum_indexes[i];
  487.  
  488.       rejectpt[0] = (float)node->minmaxs[pindex[0]];
  489.       rejectpt[1] = (float)node->minmaxs[pindex[1]];
  490.       rejectpt[2] = (float)node->minmaxs[pindex[2]];
  491.       
  492.       d = DotProduct (rejectpt, view_clipplanes[i].normal);
  493.       d -= view_clipplanes[i].dist;
  494.  
  495.       if (d <= 0)
  496.         return;
  497.  
  498.       acceptpt[0] = (float)node->minmaxs[pindex[3+0]];
  499.       acceptpt[1] = (float)node->minmaxs[pindex[3+1]];
  500.       acceptpt[2] = (float)node->minmaxs[pindex[3+2]];
  501.  
  502.       d = DotProduct (acceptpt, view_clipplanes[i].normal);
  503.       d -= view_clipplanes[i].dist;
  504.  
  505.       if (d >= 0)
  506.         clipflags &= ~(1<<i); // node is entirely on screen
  507.     }
  508.   }
  509.   
  510. // if a leaf node, draw stuff
  511.   if (node->contents < 0)
  512.   {
  513.     pleaf = (mleaf_t *)node;
  514.  
  515.     mark = pleaf->firstmarksurface;
  516.     c = pleaf->nummarksurfaces;
  517.  
  518.     if (c)
  519.     {
  520.       do
  521.       {
  522.         (*mark)->visframe = r_framecount;
  523.         mark++;
  524.       } while (--c);
  525.     }
  526.  
  527.   // deal with model fragments in this leaf
  528.     if (pleaf->efrags)
  529.     {
  530.       R_StoreEfrags (&pleaf->efrags);
  531.     }
  532.  
  533.     pleaf->key = r_currentkey;
  534.     r_currentkey++;   // all bmodels in a leaf share the same key
  535.   }
  536.   else
  537.   {
  538.   // node is just a decision point, so go down the apropriate sides
  539.  
  540.   // find which side of the node we are on
  541.     plane = node->plane;
  542.  
  543.     switch (plane->type)
  544.     {
  545.     case PLANE_X:
  546.       dot = modelorg[0] - plane->dist;
  547.       break;
  548.     case PLANE_Y:
  549.       dot = modelorg[1] - plane->dist;
  550.       break;
  551.     case PLANE_Z:
  552.       dot = modelorg[2] - plane->dist;
  553.       break;
  554.     default:
  555.       dot = DotProduct (modelorg, plane->normal) - plane->dist;
  556.       break;
  557.     }
  558.   
  559.     if (dot >= 0)
  560.       side = 0;
  561.     else
  562.       side = 1;
  563.  
  564.   // recurse down the children, front side first
  565.     R_RecursiveWorldNode (node->children[side], clipflags);
  566.  
  567.   // draw stuff
  568.     c = node->numsurfaces;
  569.  
  570.     if (c)
  571.     {
  572.       surf = cl.worldmodel->surfaces + node->firstsurface;
  573.  
  574.       if (dot < -BACKFACE_EPSILON)
  575.       {
  576.         do
  577.         {
  578.           if ((surf->flags & SURF_PLANEBACK) &&
  579.             (surf->visframe == r_framecount))
  580.           {
  581.             if (r_drawpolys)
  582.             {
  583.               if (r_worldpolysbacktofront)
  584.               {
  585.                 if (numbtofpolys < MAX_BTOFPOLYS)
  586.                 {
  587.                   pbtofpolys[numbtofpolys].clipflags =
  588.                       clipflags;
  589.                   pbtofpolys[numbtofpolys].psurf = surf;
  590.                   numbtofpolys++;
  591.                 }
  592.               }
  593.               else
  594.               {
  595.                 R_RenderPoly (surf, clipflags);
  596.               }
  597.             }
  598.             else
  599.             {
  600.               R_RenderFace (surf, clipflags);
  601.             }
  602.           }
  603.  
  604.           surf++;
  605.         } while (--c);
  606.       }
  607.       else if (dot > BACKFACE_EPSILON)
  608.       {
  609.         do
  610.         {
  611.           if (!(surf->flags & SURF_PLANEBACK) &&
  612.             (surf->visframe == r_framecount))
  613.           {
  614.             if (r_drawpolys)
  615.             {
  616.               if (r_worldpolysbacktofront)
  617.               {
  618.                 if (numbtofpolys < MAX_BTOFPOLYS)
  619.                 {
  620.                   pbtofpolys[numbtofpolys].clipflags =
  621.                       clipflags;
  622.                   pbtofpolys[numbtofpolys].psurf = surf;
  623.                   numbtofpolys++;
  624.                 }
  625.               }
  626.               else
  627.               {
  628.                 R_RenderPoly (surf, clipflags);
  629.               }
  630.             }
  631.             else
  632.             {
  633.               R_RenderFace (surf, clipflags);
  634.             }
  635.           }
  636.  
  637.           surf++;
  638.         } while (--c);
  639.       }
  640.  
  641.     // all surfaces on the same node share the same sequence number
  642.       r_currentkey++;
  643.     }
  644.  
  645.   // recurse down the back side
  646.     R_RecursiveWorldNode (node->children[!side], clipflags);
  647.   }
  648. }
  649. #endif
  650.  
  651.  
  652. /*
  653. ================
  654. R_RenderWorld
  655. ================
  656. */
  657. void R_RenderWorld (void)
  658. {
  659.   int     i;
  660.   model_t   *clmodel;
  661.   static btofpoly_t  btofpolys[MAX_BTOFPOLYS]; /* phx */
  662.  
  663.   pbtofpolys = btofpolys;
  664.  
  665.   currententity = &cl_entities[0];
  666.   VectorCopy (r_origin, modelorg);
  667.   clmodel = currententity->model;
  668.   r_pcurrentvertbase = clmodel->vertexes;
  669.  
  670.   R_RecursiveWorldNode (clmodel->nodes, 15);
  671.  
  672. // if the driver wants the polygons back to front, play the visible ones back
  673. // in that order
  674.   if (r_worldpolysbacktofront)
  675.   {
  676.     for (i=numbtofpolys-1 ; i>=0 ; i--)
  677.     {
  678.       R_RenderPoly (btofpolys[i].psurf, btofpolys[i].clipflags);
  679.     }
  680.   }
  681. }
  682.  
  683.  
  684.