home *** CD-ROM | disk | FTP | other *** search
/ Amiga Format CD 28 / amigaformatcd28.iso / -websites- / amidoom / adoom_src-0.7.lha / ADoom_src / r_bsp.c < prev    next >
C/C++ Source or Header  |  1997-12-27  |  11KB  |  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.