home *** CD-ROM | disk | FTP | other *** search
/ Magazyn Amiga 14 / MA_Cover_14.iso / source / c / q1source_amy / qw / client / r_bsp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1999-12-21  |  14.5 KB  |  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 = &r_worldentity;
  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.