From 66a2cc66d7504c9b64e1c461e62ad2a9d964fa95 Mon Sep 17 00:00:00 2001 From: Simon Howard Date: Sat, 23 Jul 2005 16:19:41 +0000 Subject: Initial revision Subversion-branch: /trunk/chocolate-doom Subversion-revision: 4 --- src/r_bsp.c | 583 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 583 insertions(+) create mode 100644 src/r_bsp.c (limited to 'src/r_bsp.c') diff --git a/src/r_bsp.c b/src/r_bsp.c new file mode 100644 index 00000000..5189cefb --- /dev/null +++ b/src/r_bsp.c @@ -0,0 +1,583 @@ +// Emacs style mode select -*- C++ -*- +//----------------------------------------------------------------------------- +// +// $Id: r_bsp.c 4 2005-07-23 16:19:41Z fraggle $ +// +// 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$ +// Revision 1.1 2005/07/23 16:19:42 fraggle +// Initial revision +// +// +// DESCRIPTION: +// BSP traversal, handling of LineSegs for rendering. +// +//----------------------------------------------------------------------------- + + +static const char +rcsid[] = "$Id: r_bsp.c 4 2005-07-23 16:19:41Z fraggle $"; + + +#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]); +} + + -- cgit v1.2.3