r_bsp.c

// Emacs style mode select   -*- C++ -*- 
//-----------------------------------------------------------------------------
//
// Copyright(C) 1993-1996 Id Software, Inc.
// Copyright(C) 2005 Simon Howard
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
// 02111-1307, USA.
//
// DESCRIPTION:
//      BSP traversal, handling of LineSegs for rendering.
//
//-----------------------------------------------------------------------------

#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"

seg_t *curline;
side_t *sidedef;
line_t *linedef;
sector_t *frontsector;
sector_t *backsector;

drawseg_t drawsegs[MAXDRAWSEGS];
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]);
}