0,0 → 1,580 |
// 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" |
|
|
|
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]); |
} |
|
|