text: // Emacs style mode select   -*- C++ -*- 
  //-----------------------------------------------------------------------------
  //
  // $Id:$
  //
  // Copyright (C) 1993-1996 by id Software, Inc.
  //
  // This source is available for distribution and/or modification
  // only under the terms of the DOOM Source Code License as
  // published by id Software. All rights reserved.
  //
  // The source is distributed in the hope that it will be useful,
  // but WITHOUT ANY WARRANTY; without even the implied warranty of
  // FITNESS FOR A PARTICULAR PURPOSE. See the DOOM Source Code License
  // for more details.
  //
  // $Log:$
  //
  // DESCRIPTION:
  //	BSP traversal, handling of LineSegs for rendering.
  //
  //-----------------------------------------------------------------------------
  
  
  static const char
  rcsid[] = "$Id: r_bsp.c,v 1.4 1997/02/03 22:45:12 b1 Exp $";
  
  
  #include "doomdef.h"
  
  #include "m_bbox.h"
  
  #include "i_system.h"
  
  #include "r_main.h"
  #include "r_plane.h"
  #include "r_things.h"
  
  // State.
  #include "doomstat.h"
  #include "r_state.h"
  
  //#include "r_local.h"
  
  
  
  __attribute__((section(".ram7")))
  seg_t*		curline;
  __attribute__((section(".ram7")))
  side_t*		sidedef;
  __attribute__((section(".ram7")))
  line_t*		linedef;
  __attribute__((section(".ram7")))
  sector_t*	frontsector;
  __attribute__((section(".ram7")))
  sector_t*	backsector;
  
  __attribute__((section(".ram7")))
  drawseg_t	drawsegs[MAXDRAWSEGS];
  __attribute__((section(".ram7")))
  drawseg_t*	ds_p;
  
  
  void
  R_StoreWallRange
  ( int	start,
    int	stop );
  
  
  
  
  //
  // R_ClearDrawSegs
  //
  void R_ClearDrawSegs (void)
  {
      ds_p = drawsegs;
  }
  
  
  
  //
  // ClipWallSegment
  // Clips the given range of columns
  // and includes it in the new clip list.
  //
  typedef	struct
  {
      int	first;
      int last;
      
  } cliprange_t;
  
  
  #define MAXSEGS		32
  
  // newend is one past the last valid seg
  cliprange_t*	newend;
  cliprange_t	solidsegs[MAXSEGS];
  
  
  
  
  //
  // R_ClipSolidWallSegment
  // Does handle solid walls,
  //  e.g. single sided LineDefs (middle texture)
  //  that entirely block the view.
  // 
  void
  R_ClipSolidWallSegment
  ( int			first,
    int			last )
  {
      cliprange_t*	next;
      cliprange_t*	start;
  
      // Find the first range that touches the range
      //  (adjacent pixels are touching).
      start = solidsegs;
      while (start->last < first-1)
  	start++;
  
      if (first < start->first)
      {
  	if (last < start->first-1)
  	{
  	    // Post is entirely visible (above start),
  	    //  so insert a new clippost.
  	    R_StoreWallRange (first, last);
  	    next = newend;
  	    newend++;
  	    
  	    while (next != start)
  	    {
  		*next = *(next-1);
  		next--;
  	    }
  	    next->first = first;
  	    next->last = last;
  	    return;
  	}
  		
  	// There is a fragment above *start.
  	R_StoreWallRange (first, start->first - 1);
  	// Now adjust the clip size.
  	start->first = first;	
      }
  
      // Bottom contained in start?
      if (last <= start->last)
  	return;			
  		
      next = start;
      while (last >= (next+1)->first-1)
      {
  	// There is a fragment between two posts.
  	R_StoreWallRange (next->last + 1, (next+1)->first - 1);
  	next++;
  	
  	if (last <= next->last)
  	{
  	    // Bottom is contained in next.
  	    // Adjust the clip size.
  	    start->last = next->last;	
  	    goto crunch;
  	}
      }
  	
      // There is a fragment after *next.
      R_StoreWallRange (next->last + 1, last);
      // Adjust the clip size.
      start->last = last;
  	
      // Remove start+1 to next from the clip list,
      // because start now covers their area.
    crunch:
      if (next == start)
      {
  	// Post just extended past the bottom of one post.
  	return;
      }
      
  
      while (next++ != newend)
      {
  	// Remove a post.
  	*++start = *next;
      }
  
      newend = start+1;
  }
  
  
  
  //
  // R_ClipPassWallSegment
  // Clips the given range of columns,
  //  but does not includes it in the clip list.
  // Does handle windows,
  //  e.g. LineDefs with upper and lower texture.
  //
  void
  R_ClipPassWallSegment
  ( int	first,
    int	last )
  {
      cliprange_t*	start;
  
      // Find the first range that touches the range
      //  (adjacent pixels are touching).
      start = solidsegs;
      while (start->last < first-1)
  	start++;
  
      if (first < start->first)
      {
  	if (last < start->first-1)
  	{
  	    // Post is entirely visible (above start).
  	    R_StoreWallRange (first, last);
  	    return;
  	}
  		
  	// There is a fragment above *start.
  	R_StoreWallRange (first, start->first - 1);
      }
  
      // Bottom contained in start?
      if (last <= start->last)
  	return;			
  		
      while (last >= (start+1)->first-1)
      {
  	// There is a fragment between two posts.
  	R_StoreWallRange (start->last + 1, (start+1)->first - 1);
  	start++;
  	
  	if (last <= start->last)
  	    return;
      }
  	
      // There is a fragment after *next.
      R_StoreWallRange (start->last + 1, last);
  }
  
  
  
  //
  // R_ClearClipSegs
  //
  void R_ClearClipSegs (void)
  {
      solidsegs[0].first = -0x7fffffff;
      solidsegs[0].last = -1;
      solidsegs[1].first = viewwidth;
      solidsegs[1].last = 0x7fffffff;
      newend = solidsegs+2;
  }
  
  //
  // R_AddLine
  // Clips the given segment
  // and adds any visible pieces to the line list.
  //
  void R_AddLine (seg_t*	line)
  {
      int			x1;
      int			x2;
      angle_t		angle1;
      angle_t		angle2;
      angle_t		span;
      angle_t		tspan;
      
      curline = line;
  
      // OPTIMIZE: quickly reject orthogonal back sides.
      angle1 = R_PointToAngle (line->v1->x, line->v1->y);
      angle2 = R_PointToAngle (line->v2->x, line->v2->y);
      
      // Clip to view edges.
      // OPTIMIZE: make constant out of 2*clipangle (FIELDOFVIEW).
      span = angle1 - angle2;
      
      // Back side? I.e. backface culling?
      if (span >= ANG180)
  	return;		
  
      // Global angle needed by segcalc.
      rw_angle1 = angle1;
      angle1 -= viewangle;
      angle2 -= viewangle;
  	
      tspan = angle1 + clipangle;
      if (tspan > 2*clipangle)
      {
  	tspan -= 2*clipangle;
  
  	// Totally off the left edge?
  	if (tspan >= span)
  	    return;
  	
  	angle1 = clipangle;
      }
      tspan = clipangle - angle2;
      if (tspan > 2*clipangle)
      {
  	tspan -= 2*clipangle;
  
  	// Totally off the left edge?
  	if (tspan >= span)
  	    return;	
  	angle2 = -clipangle;
      }
      
      // The seg is in the view range,
      // but not necessarily visible.
      angle1 = (angle1+ANG90)>>ANGLETOFINESHIFT;
      angle2 = (angle2+ANG90)>>ANGLETOFINESHIFT;
      x1 = viewangletox[angle1];
      x2 = viewangletox[angle2];
  
      // Does not cross a pixel?
      if (x1 == x2)
  	return;				
  	
      backsector = line->backsector;
  
      // Single sided line?
      if (!backsector)
  	goto clipsolid;		
  
      // Closed door.
      if (backsector->ceilingheight <= frontsector->floorheight
  	|| backsector->floorheight >= frontsector->ceilingheight)
  	goto clipsolid;		
  
      // Window.
      if (backsector->ceilingheight != frontsector->ceilingheight
  	|| backsector->floorheight != frontsector->floorheight)
  	goto clippass;	
  		
      // Reject empty lines used for triggers
      //  and special events.
      // Identical floor and ceiling on both sides,
      // identical light levels on both sides,
      // and no middle texture.
      if (backsector->ceilingpic == frontsector->ceilingpic
  	&& backsector->floorpic == frontsector->floorpic
  	&& backsector->lightlevel == frontsector->lightlevel
  	&& curline->sidedef->midtexture == 0)
      {
  	return;
      }
      
  				
    clippass:
      R_ClipPassWallSegment (x1, x2-1);	
      return;
  		
    clipsolid:
      R_ClipSolidWallSegment (x1, x2-1);
  }
  
  
  //
  // R_CheckBBox
  // Checks BSP node/subtree bounding box.
  // Returns true
  //  if some part of the bbox might be visible.
  //
  int	checkcoord[12][4] =
  {
      {3,0,2,1},
      {3,0,2,0},
      {3,1,2,0},
      {0},
      {2,0,2,1},
      {0,0,0,0},
      {3,1,3,0},
      {0},
      {2,0,3,1},
      {2,1,3,1},
      {2,1,3,0}
  };
  
  
  boolean R_CheckBBox (fixed_t*	bspcoord)
  {
      int			boxx;
      int			boxy;
      int			boxpos;
  
      fixed_t		x1;
      fixed_t		y1;
      fixed_t		x2;
      fixed_t		y2;
      
      angle_t		angle1;
      angle_t		angle2;
      angle_t		span;
      angle_t		tspan;
      
      cliprange_t*	start;
  
      int			sx1;
      int			sx2;
      
      // Find the corners of the box
      // that define the edges from current viewpoint.
      if (viewx <= bspcoord[BOXLEFT])
  	boxx = 0;
      else if (viewx < bspcoord[BOXRIGHT])
  	boxx = 1;
      else
  	boxx = 2;
  		
      if (viewy >= bspcoord[BOXTOP])
  	boxy = 0;
      else if (viewy > bspcoord[BOXBOTTOM])
  	boxy = 1;
      else
  	boxy = 2;
  		
      boxpos = (boxy<<2)+boxx;
      if (boxpos == 5)
  	return true;
  	
      x1 = bspcoord[checkcoord[boxpos][0]];
      y1 = bspcoord[checkcoord[boxpos][1]];
      x2 = bspcoord[checkcoord[boxpos][2]];
      y2 = bspcoord[checkcoord[boxpos][3]];
      
      // check clip list for an open space
      angle1 = R_PointToAngle (x1, y1) - viewangle;
      angle2 = R_PointToAngle (x2, y2) - viewangle;
  	
      span = angle1 - angle2;
  
      // Sitting on a line?
      if (span >= ANG180)
  	return true;
      
      tspan = angle1 + clipangle;
  
      if (tspan > 2*clipangle)
      {
  	tspan -= 2*clipangle;
  
  	// Totally off the left edge?
  	if (tspan >= span)
  	    return false;	
  
  	angle1 = clipangle;
      }
      tspan = clipangle - angle2;
      if (tspan > 2*clipangle)
      {
  	tspan -= 2*clipangle;
  
  	// Totally off the left edge?
  	if (tspan >= span)
  	    return false;
  	
  	angle2 = -clipangle;
      }
  
  
      // Find the first clippost
      //  that touches the source post
      //  (adjacent pixels are touching).
      angle1 = (angle1+ANG90)>>ANGLETOFINESHIFT;
      angle2 = (angle2+ANG90)>>ANGLETOFINESHIFT;
      sx1 = viewangletox[angle1];
      sx2 = viewangletox[angle2];
  
      // Does not cross a pixel.
      if (sx1 == sx2)
  	return false;			
      sx2--;
  	
      start = solidsegs;
      while (start->last < sx2)
  	start++;
      
      if (sx1 >= start->first
  	&& sx2 <= start->last)
      {
  	// The clippost contains the new span.
  	return false;
      }
  
      return true;
  }
  
  
  
  //
  // R_Subsector
  // Determine floor/ceiling planes.
  // Add sprites of things in sector.
  // Draw one or more line segments.
  //
  void R_Subsector (int num)
  {
      int			count;
      seg_t*		line;
      subsector_t*	sub;
  	
  #ifdef RANGECHECK
      if (num>=numsubsectors)
  	I_Error ("R_Subsector: ss %i with numss = %i",
  		 num,
  		 numsubsectors);
  #endif
  
      sscount++;
      sub = &subsectors[num];
      frontsector = sub->sector;
      count = sub->numlines;
      line = &segs[sub->firstline];
  
      if (frontsector->floorheight < viewz)
      {
  	floorplane = R_FindPlane (frontsector->floorheight,
  				  frontsector->floorpic,
  				  frontsector->lightlevel);
      }
      else
  	floorplane = NULL;
      
      if (frontsector->ceilingheight > viewz 
  	|| frontsector->ceilingpic == skyflatnum)
      {
  	ceilingplane = R_FindPlane (frontsector->ceilingheight,
  				    frontsector->ceilingpic,
  				    frontsector->lightlevel);
      }
      else
  	ceilingplane = NULL;
  		
      R_AddSprites (frontsector);	
  
      while (count--)
      {
  	R_AddLine (line);
  	line++;
      }
  }
  
  
  
  
  //
  // RenderBSPNode
  // Renders all subsectors below a given node,
  //  traversing subtree recursively.
  // Just call with BSP root.
  void R_RenderBSPNode (int bspnum)
  {
      node_t*	bsp;
      int		side;
  
      // Found a subsector?
      if (bspnum & NF_SUBSECTOR)
      {
  	if (bspnum == -1)			
  	    R_Subsector (0);
  	else
  	    R_Subsector (bspnum&(~NF_SUBSECTOR));
  	return;
      }
  		
      bsp = &nodes[bspnum];
      
      // Decide which side the view point is on.
      side = R_PointOnSide (viewx, viewy, bsp);
  
      // Recursively divide front space.
      R_RenderBSPNode (bsp->children[side]); 
  
      // Possibly divide back space.
      if (R_CheckBBox (bsp->bbox[side^1]))	
  	R_RenderBSPNode (bsp->children[side^1]);
  }
  
  
  