Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  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.