// Emacs style mode select -*- C++ -*- //----------------------------------------------------------------------------- // // $Id: r_bsp.c 8 2005-07-23 16:44:57Z fraggle $ // // 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. // // $Log$ // Revision 1.2 2005/07/23 16:44:56 fraggle // Update copyright to GNU GPL // // Revision 1.1.1.1 2005/07/23 16:19:42 fraggle // Initial import // // // DESCRIPTION: // BSP traversal, handling of LineSegs for rendering. // //----------------------------------------------------------------------------- static const char rcsid[] = "$Id: r_bsp.c 8 2005-07-23 16:44:57Z 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]); }