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