home *** CD-ROM | disk | FTP | other *** search
/ ST-Computer Leser-CD 2000 January / LCD_01_2000.iso / games / doom / pmdoom / src / r_bsp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1999-12-17  |  12.0 KB  |  581 lines
  1. /*  Emacs style mode select   -*- C++ -*-  */
  2. /* ----------------------------------------------------------------------------- */
  3. /*  */
  4. /*  $Id:$ */
  5. /*  */
  6. /*  Copyright (C) 1993-1996 by id Software, Inc. */
  7. /*  */
  8. /*  This source is available for distribution and/or modification */
  9. /*  only under the terms of the DOOM Source Code License as */
  10. /*  published by id Software. All rights reserved. */
  11. /*  */
  12. /*  The source is distributed in the hope that it will be useful, */
  13. /*  but WITHOUT ANY WARRANTY; without even the implied warranty of */
  14. /*  FITNESS FOR A PARTICULAR PURPOSE. See the DOOM Source Code License */
  15. /*  for more details. */
  16. /*  */
  17. /*  $Log:$ */
  18. /*  */
  19. /*  DESCRIPTION: */
  20. /*     BSP traversal, handling of LineSegs for rendering. */
  21. /*  */
  22. /* ----------------------------------------------------------------------------- */
  23.  
  24.  
  25. static const char
  26. rcsid[] = "$Id: r_bsp.c,v 1.4 1997/02/03 22:45:12 b1 Exp $";
  27.  
  28.  
  29. #include "doomdef.h"
  30.  
  31. #include "m_bbox.h"
  32.  
  33. #include "i_system.h"
  34.  
  35. #include "r_main.h"
  36. #include "r_plane.h"
  37. #include "r_things.h"
  38.  
  39. /*  State. */
  40. #include "doomstat.h"
  41. #include "r_state.h"
  42.  
  43. /* #include "r_local.h" */
  44.  
  45.  
  46.  
  47. seg_t*        curline;
  48. side_t*        sidedef;
  49. line_t*        linedef;
  50. sector_t*    frontsector;
  51. sector_t*    backsector;
  52.  
  53. drawseg_t    drawsegs[MAXDRAWSEGS];
  54. drawseg_t*    ds_p;
  55.  
  56.  
  57. void
  58. R_StoreWallRange
  59. ( int    start,
  60.   int    stop );
  61.  
  62.  
  63.  
  64.  
  65. /*  */
  66. /*  R_ClearDrawSegs */
  67. /*  */
  68. void R_ClearDrawSegs (void)
  69. {
  70.     ds_p = drawsegs;
  71. }
  72.  
  73.  
  74.  
  75. /*  */
  76. /*  ClipWallSegment */
  77. /*  Clips the given range of columns */
  78. /*  and includes it in the new clip list. */
  79. /*  */
  80. typedef    struct
  81. {
  82.     int    first;
  83.     int last;
  84.     
  85. } cliprange_t;
  86.  
  87.  
  88. #define MAXSEGS        32
  89.  
  90. /*  newend is one past the last valid seg */
  91. cliprange_t*    newend;
  92. cliprange_t    solidsegs[MAXSEGS];
  93.  
  94.  
  95.  
  96.  
  97. /*  */
  98. /*  R_ClipSolidWallSegment */
  99. /*  Does handle solid walls, */
  100. /*   e.g. single sided LineDefs (middle texture) */
  101. /*   that entirely block the view. */
  102. /*   */
  103. void
  104. R_ClipSolidWallSegment
  105. ( int            first,
  106.   int            last )
  107. {
  108.     cliprange_t*    next;
  109.     cliprange_t*    start;
  110.  
  111.     /*  Find the first range that touches the range */
  112.     /*   (adjacent pixels are touching). */
  113.     start = solidsegs;
  114.     while (start->last < first-1)
  115.     start++;
  116.  
  117.     if (first < start->first)
  118.     {
  119.     if (last < start->first-1)
  120.     {
  121.         /*  Post is entirely visible (above start), */
  122.         /*   so insert a new clippost. */
  123.         R_StoreWallRange (first, last);
  124.         next = newend;
  125.         newend++;
  126.         
  127.         while (next != start)
  128.         {
  129.         *next = *(next-1);
  130.         next--;
  131.         }
  132.         next->first = first;
  133.         next->last = last;
  134.         return;
  135.     }
  136.         
  137.     /*  There is a fragment above *start. */
  138.     R_StoreWallRange (first, start->first - 1);
  139.     /*  Now adjust the clip size. */
  140.     start->first = first;    
  141.     }
  142.  
  143.     /*  Bottom contained in start? */
  144.     if (last <= start->last)
  145.     return;            
  146.         
  147.     next = start;
  148.     while (last >= (next+1)->first-1)
  149.     {
  150.     /*  There is a fragment between two posts. */
  151.     R_StoreWallRange (next->last + 1, (next+1)->first - 1);
  152.     next++;
  153.     
  154.     if (last <= next->last)
  155.     {
  156.         /*  Bottom is contained in next. */
  157.         /*  Adjust the clip size. */
  158.         start->last = next->last;    
  159.         goto crunch;
  160.     }
  161.     }
  162.     
  163.     /*  There is a fragment after *next. */
  164.     R_StoreWallRange (next->last + 1, last);
  165.     /*  Adjust the clip size. */
  166.     start->last = last;
  167.     
  168.     /*  Remove start+1 to next from the clip list, */
  169.     /*  because start now covers their area. */
  170.   crunch:
  171.     if (next == start)
  172.     {
  173.     /*  Post just extended past the bottom of one post. */
  174.     return;
  175.     }
  176.     
  177.  
  178.     while (next++ != newend)
  179.     {
  180.     /*  Remove a post. */
  181.     *++start = *next;
  182.     }
  183.  
  184.     newend = start+1;
  185. }
  186.  
  187.  
  188.  
  189. /*  */
  190. /*  R_ClipPassWallSegment */
  191. /*  Clips the given range of columns, */
  192. /*   but does not includes it in the clip list. */
  193. /*  Does handle windows, */
  194. /*   e.g. LineDefs with upper and lower texture. */
  195. /*  */
  196. void
  197. R_ClipPassWallSegment
  198. ( int    first,
  199.   int    last )
  200. {
  201.     cliprange_t*    start;
  202.  
  203.     /*  Find the first range that touches the range */
  204.     /*   (adjacent pixels are touching). */
  205.     start = solidsegs;
  206.     while (start->last < first-1)
  207.     start++;
  208.  
  209.     if (first < start->first)
  210.     {
  211.     if (last < start->first-1)
  212.     {
  213.         /*  Post is entirely visible (above start). */
  214.         R_StoreWallRange (first, last);
  215.         return;
  216.     }
  217.         
  218.     /*  There is a fragment above *start. */
  219.     R_StoreWallRange (first, start->first - 1);
  220.     }
  221.  
  222.     /*  Bottom contained in start? */
  223.     if (last <= start->last)
  224.     return;            
  225.         
  226.     while (last >= (start+1)->first-1)
  227.     {
  228.     /*  There is a fragment between two posts. */
  229.     R_StoreWallRange (start->last + 1, (start+1)->first - 1);
  230.     start++;
  231.     
  232.     if (last <= start->last)
  233.         return;
  234.     }
  235.     
  236.     /*  There is a fragment after *next. */
  237.     R_StoreWallRange (start->last + 1, last);
  238. }
  239.  
  240.  
  241.  
  242. /*  */
  243. /*  R_ClearClipSegs */
  244. /*  */
  245. void R_ClearClipSegs (void)
  246. {
  247.     solidsegs[0].first = -0x7fffffff;
  248.     solidsegs[0].last = -1;
  249.     solidsegs[1].first = viewwidth;
  250.     solidsegs[1].last = 0x7fffffff;
  251.     newend = solidsegs+2;
  252. }
  253.  
  254. /*  */
  255. /*  R_AddLine */
  256. /*  Clips the given segment */
  257. /*  and adds any visible pieces to the line list. */
  258. /*  */
  259. void R_AddLine (seg_t*    line)
  260. {
  261.     int            x1;
  262.     int            x2;
  263.     angle_t        angle1;
  264.     angle_t        angle2;
  265.     angle_t        span;
  266.     angle_t        tspan;
  267.     
  268.     curline = line;
  269.  
  270.     /*  OPTIMIZE: quickly reject orthogonal back sides. */
  271.     angle1 = R_PointToAngle (line->v1->x, line->v1->y);
  272.     angle2 = R_PointToAngle (line->v2->x, line->v2->y);
  273.     
  274.     /*  Clip to view edges. */
  275.     /*  OPTIMIZE: make constant out of 2*clipangle (FIELDOFVIEW). */
  276.     span = angle1 - angle2;
  277.     
  278.     /*  Back side? I.e. backface culling? */
  279.     if (span >= ANG180)
  280.     return;        
  281.  
  282.     /*  Global angle needed by segcalc. */
  283.     rw_angle1 = angle1;
  284.     angle1 -= viewangle;
  285.     angle2 -= viewangle;
  286.     
  287.     tspan = angle1 + clipangle;
  288.     if (tspan > 2*clipangle)
  289.     {
  290.     tspan -= 2*clipangle;
  291.  
  292.     /*  Totally off the left edge? */
  293.     if (tspan >= span)
  294.         return;
  295.     
  296.     angle1 = clipangle;
  297.     }
  298.     tspan = clipangle - angle2;
  299.     if (tspan > 2*clipangle)
  300.     {
  301.     tspan -= 2*clipangle;
  302.  
  303.     /*  Totally off the left edge? */
  304.     if (tspan >= span)
  305.         return;    
  306.     angle2 = -clipangle;
  307.     }
  308.     
  309.     /*  The seg is in the view range, */
  310.     /*  but not necessarily visible. */
  311.     angle1 = (angle1+ANG90)>>ANGLETOFINESHIFT;
  312.     angle2 = (angle2+ANG90)>>ANGLETOFINESHIFT;
  313.     x1 = viewangletox[angle1];
  314.     x2 = viewangletox[angle2];
  315.  
  316.     /*  Does not cross a pixel? */
  317.     if (x1 == x2)
  318.     return;                
  319.     
  320.     backsector = line->backsector;
  321.  
  322.     /*  Single sided line? */
  323.     if (!backsector)
  324.     goto clipsolid;        
  325.  
  326.     /*  Closed door. */
  327.     if (backsector->ceilingheight <= frontsector->floorheight
  328.     || backsector->floorheight >= frontsector->ceilingheight)
  329.     goto clipsolid;        
  330.  
  331.     /*  Window. */
  332.     if (backsector->ceilingheight != frontsector->ceilingheight
  333.     || backsector->floorheight != frontsector->floorheight)
  334.     goto clippass;    
  335.         
  336.     /*  Reject empty lines used for triggers */
  337.     /*   and special events. */
  338.     /*  Identical floor and ceiling on both sides, */
  339.     /*  identical light levels on both sides, */
  340.     /*  and no middle texture. */
  341.     if (backsector->ceilingpic == frontsector->ceilingpic
  342.     && backsector->floorpic == frontsector->floorpic
  343.     && backsector->lightlevel == frontsector->lightlevel
  344.     && curline->sidedef->midtexture == 0)
  345.     {
  346.     return;
  347.     }
  348.     
  349.                 
  350.   clippass:
  351.     R_ClipPassWallSegment (x1, x2-1);    
  352.     return;
  353.         
  354.   clipsolid:
  355.     R_ClipSolidWallSegment (x1, x2-1);
  356. }
  357.  
  358.  
  359. /*  */
  360. /*  R_CheckBBox */
  361. /*  Checks BSP node/subtree bounding box. */
  362. /*  Returns true */
  363. /*   if some part of the bbox might be visible. */
  364. /*  */
  365. int    checkcoord[12][4] =
  366. {
  367.     {3,0,2,1},
  368.     {3,0,2,0},
  369.     {3,1,2,0},
  370.     {0},
  371.     {2,0,2,1},
  372.     {0,0,0,0},
  373.     {3,1,3,0},
  374.     {0},
  375.     {2,0,3,1},
  376.     {2,1,3,1},
  377.     {2,1,3,0}
  378. };
  379.  
  380.  
  381. boolean R_CheckBBox (fixed_t*    bspcoord)
  382. {
  383.     int            boxx;
  384.     int            boxy;
  385.     int            boxpos;
  386.  
  387.     fixed_t        x1;
  388.     fixed_t        y1;
  389.     fixed_t        x2;
  390.     fixed_t        y2;
  391.     
  392.     angle_t        angle1;
  393.     angle_t        angle2;
  394.     angle_t        span;
  395.     angle_t        tspan;
  396.     
  397.     cliprange_t*    start;
  398.  
  399.     int            sx1;
  400.     int            sx2;
  401.     
  402.     /*  Find the corners of the box */
  403.     /*  that define the edges from current viewpoint. */
  404.     if (viewx <= bspcoord[BOXLEFT])
  405.     boxx = 0;
  406.     else if (viewx < bspcoord[BOXRIGHT])
  407.     boxx = 1;
  408.     else
  409.     boxx = 2;
  410.         
  411.     if (viewy >= bspcoord[BOXTOP])
  412.     boxy = 0;
  413.     else if (viewy > bspcoord[BOXBOTTOM])
  414.     boxy = 1;
  415.     else
  416.     boxy = 2;
  417.         
  418.     boxpos = (boxy<<2)+boxx;
  419.     if (boxpos == 5)
  420.     return true;
  421.     
  422.     x1 = bspcoord[checkcoord[boxpos][0]];
  423.     y1 = bspcoord[checkcoord[boxpos][1]];
  424.     x2 = bspcoord[checkcoord[boxpos][2]];
  425.     y2 = bspcoord[checkcoord[boxpos][3]];
  426.     
  427.     /*  check clip list for an open space */
  428.     angle1 = R_PointToAngle (x1, y1) - viewangle;
  429.     angle2 = R_PointToAngle (x2, y2) - viewangle;
  430.     
  431.     span = angle1 - angle2;
  432.  
  433.     /*  Sitting on a line? */
  434.     if (span >= ANG180)
  435.     return true;
  436.     
  437.     tspan = angle1 + clipangle;
  438.  
  439.     if (tspan > 2*clipangle)
  440.     {
  441.     tspan -= 2*clipangle;
  442.  
  443.     /*  Totally off the left edge? */
  444.     if (tspan >= span)
  445.         return false;    
  446.  
  447.     angle1 = clipangle;
  448.     }
  449.     tspan = clipangle - angle2;
  450.     if (tspan > 2*clipangle)
  451.     {
  452.     tspan -= 2*clipangle;
  453.  
  454.     /*  Totally off the left edge? */
  455.     if (tspan >= span)
  456.         return false;
  457.     
  458.     angle2 = -clipangle;
  459.     }
  460.  
  461.  
  462.     /*  Find the first clippost */
  463.     /*   that touches the source post */
  464.     /*   (adjacent pixels are touching). */
  465.     angle1 = (angle1+ANG90)>>ANGLETOFINESHIFT;
  466.     angle2 = (angle2+ANG90)>>ANGLETOFINESHIFT;
  467.     sx1 = viewangletox[angle1];
  468.     sx2 = viewangletox[angle2];
  469.  
  470.     /*  Does not cross a pixel. */
  471.     if (sx1 == sx2)
  472.     return false;            
  473.     sx2--;
  474.     
  475.     start = solidsegs;
  476.     while (start->last < sx2)
  477.     start++;
  478.     
  479.     if (sx1 >= start->first
  480.     && sx2 <= start->last)
  481.     {
  482.     /*  The clippost contains the new span. */
  483.     return false;
  484.     }
  485.  
  486.     return true;
  487. }
  488.  
  489.  
  490.  
  491. /*  */
  492. /*  R_Subsector */
  493. /*  Determine floor/ceiling planes. */
  494. /*  Add sprites of things in sector. */
  495. /*  Draw one or more line segments. */
  496. /*  */
  497. void R_Subsector (int num)
  498. {
  499.     int            count;
  500.     seg_t*        line;
  501.     subsector_t*    sub;
  502.     
  503. #ifdef RANGECHECK
  504.     if (num>=numsubsectors)
  505.     I_Error ("R_Subsector: ss %i with numss = %i",
  506.          num,
  507.          numsubsectors);
  508. #endif
  509.  
  510.     sscount++;
  511.     sub = &subsectors[num];
  512.     frontsector = sub->sector;
  513.     count = sub->numlines;
  514.     line = &segs[sub->firstline];
  515.  
  516.     if (frontsector->floorheight < viewz)
  517.     {
  518.     floorplane = R_FindPlane (frontsector->floorheight,
  519.                   frontsector->floorpic,
  520.                   frontsector->lightlevel);
  521.     }
  522.     else
  523.     floorplane = NULL;
  524.     
  525.     if (frontsector->ceilingheight > viewz 
  526.     || frontsector->ceilingpic == skyflatnum)
  527.     {
  528.     ceilingplane = R_FindPlane (frontsector->ceilingheight,
  529.                     frontsector->ceilingpic,
  530.                     frontsector->lightlevel);
  531.     }
  532.     else
  533.     ceilingplane = NULL;
  534.         
  535.     R_AddSprites (frontsector);    
  536.  
  537.     while (count--)
  538.     {
  539.     R_AddLine (line);
  540.     line++;
  541.     }
  542. }
  543.  
  544.  
  545.  
  546.  
  547. /*  */
  548. /*  RenderBSPNode */
  549. /*  Renders all subsectors below a given node, */
  550. /*   traversing subtree recursively. */
  551. /*  Just call with BSP root. */
  552. void R_RenderBSPNode (int bspnum)
  553. {
  554.     node_t*    bsp;
  555.     int        side;
  556.  
  557.     /*  Found a subsector? */
  558.     if (bspnum & NF_SUBSECTOR)
  559.     {
  560.     if (bspnum == -1)            
  561.         R_Subsector (0);
  562.     else
  563.         R_Subsector (bspnum&(~NF_SUBSECTOR));
  564.     return;
  565.     }
  566.         
  567.     bsp = &nodes[bspnum];
  568.     
  569.     /*  Decide which side the view point is on. */
  570.     side = R_PointOnSide (viewx, viewy, bsp);
  571.  
  572.     /*  Recursively divide front space. */
  573.     R_RenderBSPNode (bsp->children[side]); 
  574.  
  575.     /*  Possibly divide back space. */
  576.     if (R_CheckBBox (bsp->bbox[side^1]))    
  577.     R_RenderBSPNode (bsp->children[side^1]);
  578. }
  579.  
  580.  
  581.