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