ref: 96bb3bfc57aa0844308b4e0c8a21facf9eab6690
dir: /src/heretic/r_bsp.c/
//
// Copyright(C) 1993-1996 Id Software, Inc.
// Copyright(C) 1993-2008 Raven Software
// Copyright(C) 2005-2014 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.
//
// R_bsp.c
#include "doomdef.h"
#include "i_system.h"
#include "m_bbox.h"
#include "i_system.h"
#include "r_local.h"
seg_t *curline;
side_t *sidedef;
line_t *linedef;
sector_t *frontsector, *backsector;
drawseg_t drawsegs[MAXDRAWSEGS], *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, last;
} cliprange_t;
// We must expand MAXSEGS to the theoretical limit of the number of solidsegs
// that can be generated in a scene by the DOOM engine. This was determined by
// Lee Killough during BOOM development to be a function of the screensize.
// The simplest thing we can do, other than fix this bug, is to let the game
// render overage and then bomb out by detecting the overflow after the
// fact. -haleyjd
//#define MAXSEGS 32
#define MAXSEGS (SCREENWIDTH / 2 + 1)
cliprange_t solidsegs[MAXSEGS], *newend; // newend is one past the last valid seg
void R_ClipSolidWallSegment(int first, int last)
{
cliprange_t *next, *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);
start->first = first; // adjust the clip size
}
if (last <= start->last)
return; // bottom contained in start
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
start->last = next->last; // adjust the clip size
goto crunch;
}
}
// there is a fragment after *next
R_StoreWallRange(next->last + 1, last);
start->last = last; // adjust the clip size
// remove start+1 to next from the clip list,
// because start now covers their area
crunch:
if (next == start)
return; // post just extended past the bottom of one post
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
===============================================================================
*/
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);
}
if (last <= start->last)
return; // bottom contained in start
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, x2;
angle_t angle1, angle2, span, 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;
if (span >= ANG180)
return; // back side
rw_angle1 = angle1; // global angle needed by segcalc
angle1 -= viewangle;
angle2 -= viewangle;
tspan = angle1 + clipangle;
if (tspan > 2 * clipangle)
{
tspan -= 2 * clipangle;
if (tspan >= span)
return; // totally off the left edge
angle1 = clipangle;
}
tspan = clipangle - angle2;
if (tspan > 2 * clipangle)
{
tspan -= 2 * clipangle;
if (tspan >= span)
return; // totally off the left edge
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];
if (x1 == x2)
return; // does not cross a pixel
backsector = line->backsector;
if (!backsector)
goto clipsolid; // single sided line
if (backsector->ceilingheight <= frontsector->floorheight
|| backsector->floorheight >= frontsector->ceilingheight)
goto clipsolid; // closed door
if (backsector->ceilingheight != frontsector->ceilingheight
|| backsector->floorheight != frontsector->floorheight)
goto clippass; // window
// reject empty lines used for triggers and special events
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
=
= 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, boxy, boxpos;
fixed_t x1, y1, x2, y2;
angle_t angle1, angle2, span, tspan;
cliprange_t *start;
int sx1, 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;
if (span >= ANG180)
return true; // sitting on a line
tspan = angle1 + clipangle;
if (tspan > 2 * clipangle)
{
tspan -= 2 * clipangle;
if (tspan >= span)
return false; // totally off the left edge
angle1 = clipangle;
}
tspan = clipangle - angle2;
if (tspan > 2 * clipangle)
{
tspan -= 2 * clipangle;
if (tspan >= span)
return false; // totally off the left edge
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];
if (sx1 == sx2)
return false; // does not cross a pixel
sx2--;
start = solidsegs;
while (start->last < sx2)
start++;
if (sx1 >= start->first && sx2 <= start->last)
return false; // the clippost contains the new span
return true;
}
/*
================
=
= R_Subsector
=
= Draw one or more 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,
frontsector->special);
else
floorplane = NULL;
if (frontsector->ceilingheight > viewz
|| frontsector->ceilingpic == skyflatnum)
ceilingplane = R_FindPlane(frontsector->ceilingheight,
frontsector->ceilingpic,
frontsector->lightlevel, 0);
else
ceilingplane = NULL;
R_AddSprites(frontsector);
while (count--)
{
R_AddLine(line);
line++;
}
// check for solidsegs overflow - extremely unsatisfactory!
if(newend > &solidsegs[32])
I_Error("R_Subsector: solidsegs overflow (vanilla may crash here)\n");
}
/*
===============================================================================
=
= RenderBSPNode
=
===============================================================================
*/
void R_RenderBSPNode(int bspnum)
{
node_t *bsp;
int side;
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);
R_RenderBSPNode(bsp->children[side]); // recursively divide front space
if (R_CheckBBox(bsp->bbox[side ^ 1])) // possibly divide back space
R_RenderBSPNode(bsp->children[side ^ 1]);
}