Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | Download | RSS feed

  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.