base/r_bsp.c

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