base/r_bsp.c

   1
   2 //**************************************************************************
   3 //**
   4 //** r_bsp.c : Heretic 2 : Raven Software, Corp.
   5 //**
   6 //** $RCSfile$
   7 //** $Revision$
   8 //** $Date$
   9 //** $Author$
  10 //**
  11 //**************************************************************************
  12
  13 #include "h2def.h"
  14 #include "r_local.h"
  15
  16 seg_t           *curline;
  17 side_t          *sidedef;
  18 line_t          *linedef;
  19 sector_t        *frontsector, *backsector;
  20
  21 drawseg_t       drawsegs[MAXDRAWSEGS], *ds_p;
  22
  23 void R_StoreWallRange (int start, int stop);
  24
  25 /*
  26 ====================
  27 =
  28 = R_ClearDrawSegs
  29 =
  30 ====================
  31 */
  32
  33 void R_ClearDrawSegs (void)
  34 {
  35         ds_p = drawsegs;
  36 }
  37
  38 //=============================================================================
  39
  40
  41 /*
  42 ===============================================================================
  43 =
  44 = ClipWallSegment
  45 =
  46 = Clips the given range of columns and includes it in the new clip list
  47 ===============================================================================
  48 */
  49
  50 typedef struct
  51 {
  52         int     first, last;
  53 } cliprange_t;
  54
  55 #define MAXSEGS 32
  56
  57 cliprange_t     solidsegs[MAXSEGS], *newend;    // newend is one past the last valid seg
  58
  59
  60 void R_ClipSolidWallSegment (int first, int last)
  61 {
  62         cliprange_t     *next, *start;
  63
  64 // find the first range that touches the range (adjacent pixels are touching)
  65         start = solidsegs;
  66         while (start->last < first-1)
  67                 start++;
  68
  69         if (first < start->first)
  70         {
  71                 if (last < start->first-1)
  72                 {       // post is entirely visible (above start), so insert a new clippost
  73                         R_StoreWallRange (first, last);
  74                         next = newend;
  75                         newend++;
  76                         while (next != start)
  77                         {
  78                                 *next = *(next-1);
  79                                 next--;
  80                         }
  81                         next->first = first;
  82                         next->last = last;
  83                         return;
  84                 }
  85
  86           // there is a fragment above *start
  87                 R_StoreWallRange (first, start->first - 1);
  88                 start->first = first;           // adjust the clip size
  89         }
  90
  91         if (last <= start->last)
  92                 return;                 // bottom contained in start
  93
  94         next = start;
  95         while (last >= (next+1)->first-1)
  96         {
  97                 // there is a fragment between two posts
  98                 R_StoreWallRange (next->last + 1, (next+1)->first - 1);
  99                 next++;
 100                 if (last <= next->last)
 101                 {       // bottom is contained in next
 102                         start->last = next->last;       // adjust the clip size
 103                         goto crunch;
 104                 }
 105         }
 106
 107         // there is a fragment after *next
 108         R_StoreWallRange (next->last + 1, last);
 109         start->last = last;             // adjust the clip size
 110
 111
 112 // remove start+1 to next from the clip list,
 113 // because start now covers their area
 114 crunch:
 115         if (next == start)
 116                 return;                 // post just extended past the bottom of one post
 117
 118         while (next++ != newend)        // remove a post
 119                 *++start = *next;
 120         newend = start+1;
 121 }
 122
 123 /*
 124 ===============================================================================
 125 =
 126 = R_ClipPassWallSegment
 127 =
 128 = Clips the given range of columns, but does not includes it in the clip list
 129 ===============================================================================
 130 */
 131
 132 void R_ClipPassWallSegment (int first, int last)
 133 {
 134         cliprange_t      *start;
 135
 136 // find the first range that touches the range (adjacent pixels are touching)
 137         start = solidsegs;
 138         while (start->last < first-1)
 139                 start++;
 140
 141         if (first < start->first)
 142         {
 143                 if (last < start->first-1)
 144                 {       // post is entirely visible (above start)
 145                         R_StoreWallRange (first, last);
 146                         return;
 147                 }
 148
 149           // there is a fragment above *start
 150                 R_StoreWallRange (first, start->first - 1);
 151         }
 152
 153         if (last <= start->last)
 154                 return;                 // bottom contained in start
 155
 156         while (last >= (start+1)->first-1)
 157         {
 158                 // there is a fragment between two posts
 159                 R_StoreWallRange (start->last + 1, (start+1)->first - 1);
 160                 start++;
 161                 if (last <= start->last)
 162                         return;
 163         }
 164
 165         // there is a fragment after *next
 166         R_StoreWallRange (start->last + 1, last);
 167 }
 168
 169
 170
 171 /*
 172 ====================
 173 =
 174 = R_ClearClipSegs
 175 =
 176 ====================
 177 */
 178
 179 void R_ClearClipSegs (void)
 180 {
 181         solidsegs[0].first = -0x7fffffff;
 182         solidsegs[0].last = -1;
 183         solidsegs[1].first = viewwidth;
 184         solidsegs[1].last = 0x7fffffff;
 185         newend = solidsegs+2;
 186 }
 187
 188
 189 //=============================================================================
 190
 191 /*
 192 ======================
 193 =
 194 = R_AddLine
 195 =
 196 = Clips the given segment and adds any visible pieces to the line list
 197 =
 198 ======================
 199 */
 200
 201 void R_AddLine (seg_t *line)
 202 {
 203         int                     x1, x2;
 204         angle_t         angle1, angle2, span, tspan;
 205
 206 #ifdef __NeXT__
 207         RD_DrawLineCheck (line);
 208 #endif
 209         curline = line;
 210
 211 // OPTIMIZE: quickly reject orthogonal back sides
 212
 213         angle1 = R_PointToAngle (line->v1->x, line->v1->y);
 214         angle2 = R_PointToAngle (line->v2->x, line->v2->y);
 215
 216 //
 217 // clip to view edges
 218 // OPTIMIZE: make constant out of 2*clipangle (FIELDOFVIEW)
 219         span = angle1 - angle2;
 220         if (span >= ANG180)
 221                 return;         // back side
 222
 223         rw_angle1 = angle1;             // global angle needed by segcalc
 224         angle1 -= viewangle;
 225         angle2 -= viewangle;
 226
 227         tspan = angle1 + clipangle;
 228         if (tspan > 2*clipangle)
 229         {
 230                 tspan -= 2*clipangle;
 231                 if (tspan >= span)
 232                         return; // totally off the left edge
 233                 angle1 = clipangle;
 234         }
 235         tspan = clipangle - angle2;
 236         if (tspan > 2*clipangle)
 237         {
 238                 tspan -= 2*clipangle;
 239                 if (tspan >= span)
 240                         return; // totally off the left edge
 241                 angle2 = -clipangle;
 242         }
 243
 244 //
 245 // the seg is in the view range, but not necessarily visible
 246 //
 247         angle1 = (angle1+ANG90)>>ANGLETOFINESHIFT;
 248         angle2 = (angle2+ANG90)>>ANGLETOFINESHIFT;
 249         x1 = viewangletox[angle1];
 250         x2 = viewangletox[angle2];
 251         if (x1 == x2)
 252                 return;                         // does not cross a pixel
 253
 254         backsector = line->backsector;
 255
 256         if (!backsector)
 257                 goto clipsolid;         // single sided line
 258
 259         if (backsector->ceilingheight <= frontsector->floorheight
 260         || backsector->floorheight >= frontsector->ceilingheight)
 261                 goto clipsolid;         // closed door
 262
 263         if (backsector->ceilingheight != frontsector->ceilingheight
 264         || backsector->floorheight != frontsector->floorheight)
 265                 goto clippass;          // window
 266
 267 // reject empty lines used for triggers and special events
 268         if (backsector->ceilingpic == frontsector->ceilingpic
 269         && backsector->floorpic == frontsector->floorpic
 270         && backsector->lightlevel == frontsector->lightlevel
 271         && backsector->special == frontsector->special
 272         && curline->sidedef->midtexture == 0)
 273                 return;
 274
 275 clippass:
 276         R_ClipPassWallSegment (x1, x2-1);
 277         return;
 278
 279 clipsolid:
 280         R_ClipSolidWallSegment (x1, x2-1);
 281 }
 282
 283 //============================================================================
 284
 285
 286 /*
 287 ===============================================================================
 288 =
 289 = R_CheckBBox
 290 =
 291 = Returns true if some part of the bbox might be visible
 292 =
 293 ===============================================================================
 294 */
 295
 296 int     checkcoord[12][4] = {
 297 {3,0, 2,1},
 298 {3,0, 2,0},
 299 {3,1, 2,0},
 300 {0},
 301 {2,0, 2,1},
 302 {0,0,0,0},
 303 {3,1, 3,0},
 304 {0},
 305 {2,0, 3,1},
 306 {2,1, 3,1},
 307 {2,1, 3,0} };
 308
 309
 310 boolean R_CheckBBox (fixed_t *bspcoord)
 311 {
 312         int                     boxx, boxy, boxpos;
 313         fixed_t         x1, y1, x2, y2;
 314         angle_t         angle1, angle2, span, tspan;
 315         cliprange_t     *start;
 316         int                     sx1, sx2;
 317
 318 #ifdef __NeXT__
 319         RD_DrawBBox (bspcoord);
 320 #endif
 321
 322 // find the corners of the box that define the edges from current viewpoint
 323         if (viewx <= bspcoord[BOXLEFT])
 324                 boxx = 0;
 325         else if (viewx < bspcoord[BOXRIGHT])
 326                 boxx = 1;
 327         else
 328                 boxx = 2;
 329
 330         if (viewy >= bspcoord[BOXTOP])
 331                 boxy = 0;
 332         else if (viewy > bspcoord[BOXBOTTOM])
 333                 boxy = 1;
 334         else
 335                 boxy = 2;
 336
 337         boxpos = (boxy<<2)+boxx;
 338         if (boxpos == 5)
 339                 return true;
 340
 341         x1 = bspcoord[checkcoord[boxpos][0]];
 342         y1 = bspcoord[checkcoord[boxpos][1]];
 343         x2 = bspcoord[checkcoord[boxpos][2]];
 344         y2 = bspcoord[checkcoord[boxpos][3]];
 345
 346
 347 #ifdef __NeXT__
 348 //      RD_DisplayLine (x1, y1, x2, y2, 0.1);
 349 #endif
 350
 351 //
 352 // check clip list for an open space
 353 //
 354         angle1 = R_PointToAngle (x1, y1) - viewangle;
 355         angle2 = R_PointToAngle (x2, y2) - viewangle;
 356
 357         span = angle1 - angle2;
 358         if (span >= ANG180)
 359                 return true;    // sitting on a line
 360         tspan = angle1 + clipangle;
 361         if (tspan > 2*clipangle)
 362         {
 363                 tspan -= 2*clipangle;
 364                 if (tspan >= span)
 365                         return false;   // totally off the left edge
 366                 angle1 = clipangle;
 367         }
 368         tspan = clipangle - angle2;
 369         if (tspan > 2*clipangle)
 370         {
 371                 tspan -= 2*clipangle;
 372                 if (tspan >= span)
 373                         return false;   // totally off the left edge
 374                 angle2 = -clipangle;
 375         }
 376
 377
 378 // find the first clippost that touches the source post (adjacent pixels are touching)
 379         angle1 = (angle1+ANG90)>>ANGLETOFINESHIFT;
 380         angle2 = (angle2+ANG90)>>ANGLETOFINESHIFT;
 381         sx1 = viewangletox[angle1];
 382         sx2 = viewangletox[angle2];
 383         if (sx1 == sx2)
 384                 return false;                           // does not cross a pixel
 385         sx2--;
 386
 387         start = solidsegs;
 388         while (start->last < sx2)
 389                 start++;
 390         if (sx1 >= start->first && sx2 <= start->last)
 391                 return false;   // the clippost contains the new span
 392
 393         return true;
 394 }
 395
 396
 397 /*
 398 ================
 399 =
 400 = R_Subsector
 401 =
 402 = Draw one or more segments
 403 ================
 404 */
 405
 406 void R_Subsector (int num)
 407 {
 408         int                     count;
 409         seg_t           *line;
 410         subsector_t     *sub;
 411         int polyCount;
 412         seg_t **polySeg;
 413
 414 #ifdef RANGECHECK
 415         if (num>=numsubsectors)
 416                 I_Error ("R_Subsector: ss %i with numss = %i",num, numsubsectors);
 417 #endif
 418
 419         sscount++;
 420         sub = &subsectors[num];
 421         frontsector = sub->sector;
 422         count = sub->numlines;
 423         line = &segs[sub->firstline];
 424
 425         if(frontsector->floorheight < viewz)
 426         {
 427                 floorplane = R_FindPlane(frontsector->floorheight,
 428                         frontsector->floorpic, frontsector->lightlevel,
 429                         frontsector->special);
 430         }
 431         else
 432         {
 433                 floorplane = NULL;
 434         }
 435
 436         if(frontsector->ceilingheight > viewz
 437                 || frontsector->ceilingpic == skyflatnum)
 438         {
 439                 ceilingplane = R_FindPlane(frontsector->ceilingheight,
 440                         frontsector->ceilingpic, frontsector->lightlevel, 0);
 441         }
 442         else
 443         {
 444                 ceilingplane = NULL;
 445         }
 446
 447         R_AddSprites(frontsector);
 448         if(sub->poly)
 449         { // Render the polyobj in the subsector first
 450                 polyCount = sub->poly->numsegs;
 451                 polySeg = sub->poly->segs;
 452                 while(polyCount--)
 453                 {
 454                         R_AddLine(*polySeg++);
 455                 }
 456         }
 457         while (count--)
 458         {
 459                 R_AddLine (line);
 460                 line++;
 461         }
 462 }
 463
 464
 465 /*
 466 ===============================================================================
 467 =
 468 = RenderBSPNode
 469 =
 470 ===============================================================================
 471 */
 472
 473 void R_RenderBSPNode (int bspnum)
 474 {
 475         node_t          *bsp;
 476         int                     side;
 477
 478         if (bspnum & NF_SUBSECTOR)
 479         {
 480                 if (bspnum == -1)
 481                         R_Subsector (0);
 482                 else
 483                         R_Subsector (bspnum&(~NF_SUBSECTOR));
 484                 return;
 485         }
 486
 487         bsp = &nodes[bspnum];
 488
 489 #ifdef __NeXT__
 490         RD_DrawNodeLine (bsp);
 491 #endif
 492
 493 //
 494 // decide which side the view point is on
 495 //
 496         side = R_PointOnSide (viewx, viewy, bsp);
 497
 498         R_RenderBSPNode (bsp->children[side]); // recursively divide front space
 499
 500         if (R_CheckBBox (bsp->bbox[side^1]))    // possibly divide back space
 501                 R_RenderBSPNode (bsp->children[side^1]);
 502 }
 503
 504