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