summaryrefslogtreecommitdiff
path: root/src/doom/r_bsp.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/doom/r_bsp.c')
-rw-r--r--src/doom/r_bsp.c581
1 files changed, 581 insertions, 0 deletions
diff --git a/src/doom/r_bsp.c b/src/doom/r_bsp.c
new file mode 100644
index 00000000..47194d96
--- /dev/null
+++ b/src/doom/r_bsp.c
@@ -0,0 +1,581 @@
+// 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]);
+}
+
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-04 22:45:23 +0000