From 0df2cb80cf03d7259746834220d209b306a8c503 Mon Sep 17 00:00:00 2001 From: Simon Howard Date: Thu, 4 Sep 2008 23:15:36 +0000 Subject: Add GPLed Heretic/Hexen source. Subversion-branch: /branches/raven-branch Subversion-revision: 1195 --- src/heretic/r_bsp.c | 474 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 474 insertions(+) create mode 100644 src/heretic/r_bsp.c (limited to 'src/heretic/r_bsp.c') diff --git a/src/heretic/r_bsp.c b/src/heretic/r_bsp.c new file mode 100644 index 00000000..8a52720e --- /dev/null +++ b/src/heretic/r_bsp.c @@ -0,0 +1,474 @@ +// R_bsp.c + +#include "DoomDef.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; + +#define MAXSEGS 32 + +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; + +#ifdef __NeXT__ + RD_DrawLineCheck (line); +#endif + 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; + +#ifdef __NeXT__ + RD_DrawBBox (bspcoord); +#endif + +// 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]]; + + +#ifdef __NeXT__ +// RD_DisplayLine (x1, y1, x2, y2, 0.1); +#endif + +// +// 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++; + } +} + + +/* +=============================================================================== += += 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]; + +#ifdef __NeXT__ + RD_DrawNodeLine (bsp); +#endif + +// +// 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]); +} + + -- cgit v1.2.3