sys/src/games/doom/r_bsp.c

   1 // Emacs style mode select   -*- C++ -*-
   2 //-----------------------------------------------------------------------------
   3 //
   4 // $Id:$
   5 //
   6 // Copyright (C) 1993-1996 by id Software, Inc.
   7 //
   8 // This source is available for distribution and/or modification
   9 // only under the terms of the DOOM Source Code License as
  10 // published by id Software. All rights reserved.
  11 //
  12 // The source is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // FITNESS FOR A PARTICULAR PURPOSE. See the DOOM Source Code License
  15 // for more details.
  16 //
  17 // $Log:$
  18 //
  19 // DESCRIPTION:
  20 //      BSP traversal, handling of LineSegs for rendering.
  21 //
  22 //-----------------------------------------------------------------------------
  23
  24
  25 static const char
  26 rcsid[] = "$Id: r_bsp.c,v 1.4 1997/02/03 22:45:12 b1 Exp $";
  27
  28
  29 #include "doomdef.h"
  30
  31 #include "m_bbox.h"
  32
  33 #include "i_system.h"
  34
  35 #include "r_main.h"
  36 #include "r_plane.h"
  37 #include "r_things.h"
  38
  39 // State.
  40 #include "doomstat.h"
  41 #include "r_state.h"
  42
  43 //#include "r_local.h"
  44
  45
  46
  47 seg_t*          curline;
  48 side_t*         sidedef;
  49 line_t*         linedef;
  50 sector_t*       frontsector;
  51 sector_t*       backsector;
  52
  53 drawseg_t       drawsegs[MAXDRAWSEGS];
  54 drawseg_t*      ds_p;
  55
  56
  57 void
  58 R_StoreWallRange
  59 ( int   start,
  60   int   stop );
  61
  62
  63
  64
  65 //
  66 // R_ClearDrawSegs
  67 //
  68 void R_ClearDrawSegs (void)
  69 {
  70     ds_p = drawsegs;
  71 }
  72
  73
  74
  75 //
  76 // ClipWallSegment
  77 // Clips the given range of columns
  78 // and includes it in the new clip list.
  79 //
  80 typedef struct
  81 {
  82     int first;
  83     int last;
  84
  85 } cliprange_t;
  86
  87
  88 #define MAXSEGS         32
  89
  90 // newend is one past the last valid seg
  91 cliprange_t*    newend;
  92 cliprange_t     solidsegs[MAXSEGS];
  93
  94
  95
  96
  97 //
  98 // R_ClipSolidWallSegment
  99 // Does handle solid walls,
 100 //  e.g. single sided LineDefs (middle texture)
 101 //  that entirely block the view.
 102 //
 103 void
 104 R_ClipSolidWallSegment
 105 ( int                   first,
 106   int                   last )
 107 {
 108     cliprange_t*        next;
 109     cliprange_t*        start;
 110
 111     // Find the first range that touches the range
 112     //  (adjacent pixels are touching).
 113     start = solidsegs;
 114     while (start->last < first-1)
 115         start++;
 116
 117     if (first < start->first)
 118     {
 119         if (last < start->first-1)
 120         {
 121             // Post is entirely visible (above start),
 122             //  so insert a new clippost.
 123             R_StoreWallRange (first, last);
 124             next = newend;
 125             newend++;
 126
 127             while (next != start)
 128             {
 129                 *next = *(next-1);
 130                 next--;
 131             }
 132             next->first = first;
 133             next->last = last;
 134             return;
 135         }
 136
 137         // There is a fragment above *start.
 138         R_StoreWallRange (first, start->first - 1);
 139         // Now adjust the clip size.
 140         start->first = first;
 141     }
 142
 143     // Bottom contained in start?
 144     if (last <= start->last)
 145         return;
 146
 147     next = start;
 148     while (last >= (next+1)->first-1)
 149     {
 150         // There is a fragment between two posts.
 151         R_StoreWallRange (next->last + 1, (next+1)->first - 1);
 152         next++;
 153
 154         if (last <= next->last)
 155         {
 156             // Bottom is contained in next.
 157             // Adjust the clip size.
 158             start->last = next->last;
 159             goto crunch;
 160         }
 161     }
 162
 163     // There is a fragment after *next.
 164     R_StoreWallRange (next->last + 1, last);
 165     // Adjust the clip size.
 166     start->last = last;
 167
 168     // Remove start+1 to next from the clip list,
 169     // because start now covers their area.
 170   crunch:
 171     if (next == start)
 172     {
 173         // Post just extended past the bottom of one post.
 174         return;
 175     }
 176
 177
 178     while (next++ != newend)
 179     {
 180         // Remove a post.
 181         *++start = *next;
 182     }
 183
 184     newend = start+1;
 185 }
 186
 187
 188
 189 //
 190 // R_ClipPassWallSegment
 191 // Clips the given range of columns,
 192 //  but does not includes it in the clip list.
 193 // Does handle windows,
 194 //  e.g. LineDefs with upper and lower texture.
 195 //
 196 void
 197 R_ClipPassWallSegment
 198 ( int   first,
 199   int   last )
 200 {
 201     cliprange_t*        start;
 202
 203     // Find the first range that touches the range
 204     //  (adjacent pixels are touching).
 205     start = solidsegs;
 206     while (start->last < first-1)
 207         start++;
 208
 209     if (first < start->first)
 210     {
 211         if (last < start->first-1)
 212         {
 213             // Post is entirely visible (above start).
 214             R_StoreWallRange (first, last);
 215             return;
 216         }
 217
 218         // There is a fragment above *start.
 219         R_StoreWallRange (first, start->first - 1);
 220     }
 221
 222     // Bottom contained in start?
 223     if (last <= start->last)
 224         return;
 225
 226     while (last >= (start+1)->first-1)
 227     {
 228         // There is a fragment between two posts.
 229         R_StoreWallRange (start->last + 1, (start+1)->first - 1);
 230         start++;
 231
 232         if (last <= start->last)
 233             return;
 234     }
 235
 236     // There is a fragment after *next.
 237     R_StoreWallRange (start->last + 1, last);
 238 }
 239
 240
 241
 242 //
 243 // R_ClearClipSegs
 244 //
 245 void R_ClearClipSegs (void)
 246 {
 247     solidsegs[0].first = -0x7fffffff;
 248     solidsegs[0].last = -1;
 249     solidsegs[1].first = viewwidth;
 250     solidsegs[1].last = 0x7fffffff;
 251     newend = solidsegs+2;
 252 }
 253
 254 //
 255 // R_AddLine
 256 // Clips the given segment
 257 // and adds any visible pieces to the line list.
 258 //
 259 void R_AddLine (seg_t*  line)
 260 {
 261     int                 x1;
 262     int                 x2;
 263     angle_t             angle1;
 264     angle_t             angle2;
 265     angle_t             span;
 266     angle_t             tspan;
 267
 268     curline = line;
 269
 270     // OPTIMIZE: quickly reject orthogonal back sides.
 271     angle1 = R_PointToAngle (line->v1->x, line->v1->y);
 272     angle2 = R_PointToAngle (line->v2->x, line->v2->y);
 273
 274     // Clip to view edges.
 275     // OPTIMIZE: make constant out of 2*clipangle (FIELDOFVIEW).
 276     span = angle1 - angle2;
 277
 278     // Back side? I.e. backface culling?
 279     if (span >= ANG180)
 280         return;
 281
 282     // Global angle needed by segcalc.
 283     rw_angle1 = angle1;
 284     angle1 -= viewangle;
 285     angle2 -= viewangle;
 286
 287     tspan = angle1 + clipangle;
 288     if (tspan > 2*clipangle)
 289     {
 290         tspan -= 2*clipangle;
 291
 292         // Totally off the left edge?
 293         if (tspan >= span)
 294             return;
 295
 296         angle1 = clipangle;
 297     }
 298     tspan = clipangle - angle2;
 299     if (tspan > 2*clipangle)
 300     {
 301         tspan -= 2*clipangle;
 302
 303         // Totally off the left edge?
 304         if (tspan >= span)
 305             return;
 306         angle2 = -clipangle;
 307     }
 308
 309     // The seg is in the view range,
 310     // but not necessarily visible.
 311     angle1 = (angle1+ANG90)>>ANGLETOFINESHIFT;
 312     angle2 = (angle2+ANG90)>>ANGLETOFINESHIFT;
 313     x1 = viewangletox[angle1];
 314     x2 = viewangletox[angle2];
 315
 316     // Does not cross a pixel?
 317     if (x1 == x2)
 318         return;
 319
 320     backsector = line->backsector;
 321
 322     // Single sided line?
 323     if (!backsector)
 324         goto clipsolid;
 325
 326     // Closed door.
 327     if (backsector->ceilingheight <= frontsector->floorheight
 328         || backsector->floorheight >= frontsector->ceilingheight)
 329         goto clipsolid;
 330
 331     // Window.
 332     if (backsector->ceilingheight != frontsector->ceilingheight
 333         || backsector->floorheight != frontsector->floorheight)
 334         goto clippass;
 335
 336     // Reject empty lines used for triggers
 337     //  and special events.
 338     // Identical floor and ceiling on both sides,
 339     // identical light levels on both sides,
 340     // and no middle texture.
 341     if (backsector->ceilingpic == frontsector->ceilingpic
 342         && backsector->floorpic == frontsector->floorpic
 343         && backsector->lightlevel == frontsector->lightlevel
 344         && curline->sidedef->midtexture == 0)
 345     {
 346         return;
 347     }
 348
 349
 350   clippass:
 351     R_ClipPassWallSegment (x1, x2-1);
 352     return;
 353
 354   clipsolid:
 355     R_ClipSolidWallSegment (x1, x2-1);
 356 }
 357
 358
 359 //
 360 // R_CheckBBox
 361 // Checks BSP node/subtree bounding box.
 362 // Returns true
 363 //  if some part of the bbox might be visible.
 364 //
 365 int     checkcoord[12][4] =
 366 {
 367     {3,0,2,1},
 368     {3,0,2,0},
 369     {3,1,2,0},
 370     {0},
 371     {2,0,2,1},
 372     {0,0,0,0},
 373     {3,1,3,0},
 374     {0},
 375     {2,0,3,1},
 376     {2,1,3,1},
 377     {2,1,3,0}
 378 };
 379
 380
 381 boolean R_CheckBBox (fixed_t*   bspcoord)
 382 {
 383     int                 boxx;
 384     int                 boxy;
 385     int                 boxpos;
 386
 387     fixed_t             x1;
 388     fixed_t             y1;
 389     fixed_t             x2;
 390     fixed_t             y2;
 391
 392     angle_t             angle1;
 393     angle_t             angle2;
 394     angle_t             span;
 395     angle_t             tspan;
 396
 397     cliprange_t*        start;
 398
 399     int                 sx1;
 400     int                 sx2;
 401
 402     // Find the corners of the box
 403     // that define the edges from current viewpoint.
 404     if (viewx <= bspcoord[BOXLEFT])
 405         boxx = 0;
 406     else if (viewx < bspcoord[BOXRIGHT])
 407         boxx = 1;
 408     else
 409         boxx = 2;
 410
 411     if (viewy >= bspcoord[BOXTOP])
 412         boxy = 0;
 413     else if (viewy > bspcoord[BOXBOTTOM])
 414         boxy = 1;
 415     else
 416         boxy = 2;
 417
 418     boxpos = (boxy<<2)+boxx;
 419     if (boxpos == 5)
 420         return true;
 421
 422     x1 = bspcoord[checkcoord[boxpos][0]];
 423     y1 = bspcoord[checkcoord[boxpos][1]];
 424     x2 = bspcoord[checkcoord[boxpos][2]];
 425     y2 = bspcoord[checkcoord[boxpos][3]];
 426
 427     // check clip list for an open space
 428     angle1 = R_PointToAngle (x1, y1) - viewangle;
 429     angle2 = R_PointToAngle (x2, y2) - viewangle;
 430
 431     span = angle1 - angle2;
 432
 433     // Sitting on a line?
 434     if (span >= ANG180)
 435         return true;
 436
 437     tspan = angle1 + clipangle;
 438
 439     if (tspan > 2*clipangle)
 440     {
 441         tspan -= 2*clipangle;
 442
 443         // Totally off the left edge?
 444         if (tspan >= span)
 445             return false;
 446
 447         angle1 = clipangle;
 448     }
 449     tspan = clipangle - angle2;
 450     if (tspan > 2*clipangle)
 451     {
 452         tspan -= 2*clipangle;
 453
 454         // Totally off the left edge?
 455         if (tspan >= span)
 456             return false;
 457
 458         angle2 = -clipangle;
 459     }
 460
 461
 462     // Find the first clippost
 463     //  that touches the source post
 464     //  (adjacent pixels are touching).
 465     angle1 = (angle1+ANG90)>>ANGLETOFINESHIFT;
 466     angle2 = (angle2+ANG90)>>ANGLETOFINESHIFT;
 467     sx1 = viewangletox[angle1];
 468     sx2 = viewangletox[angle2];
 469
 470     // Does not cross a pixel.
 471     if (sx1 == sx2)
 472         return false;
 473     sx2--;
 474
 475     start = solidsegs;
 476     while (start->last < sx2)
 477         start++;
 478
 479     if (sx1 >= start->first
 480         && sx2 <= start->last)
 481     {
 482         // The clippost contains the new span.
 483         return false;
 484     }
 485
 486     return true;
 487 }
 488
 489
 490
 491 //
 492 // R_Subsector
 493 // Determine floor/ceiling planes.
 494 // Add sprites of things in sector.
 495 // Draw one or more line segments.
 496 //
 497 void R_Subsector (int num)
 498 {
 499     int                 count;
 500     seg_t*              line;
 501     subsector_t*        sub;
 502
 503 #ifdef RANGECHECK
 504     if (num>=numsubsectors)
 505         I_Error ("R_Subsector: ss %i with numss = %i",
 506                  num,
 507                  numsubsectors);
 508 #endif
 509
 510     sscount++;
 511     sub = &subsectors[num];
 512     frontsector = sub->sector;
 513     count = sub->numlines;
 514     line = &segs[sub->firstline];
 515
 516     if (frontsector->floorheight < viewz)
 517     {
 518         floorplane = R_FindPlane (frontsector->floorheight,
 519                                   frontsector->floorpic,
 520                                   frontsector->lightlevel);
 521     }
 522     else
 523         floorplane = NULL;
 524
 525     if (frontsector->ceilingheight > viewz
 526         || frontsector->ceilingpic == skyflatnum)
 527     {
 528         ceilingplane = R_FindPlane (frontsector->ceilingheight,
 529                                     frontsector->ceilingpic,
 530                                     frontsector->lightlevel);
 531     }
 532     else
 533         ceilingplane = NULL;
 534
 535     R_AddSprites (frontsector);
 536
 537     while (count--)
 538     {
 539         R_AddLine (line);
 540         line++;
 541     }
 542 }
 543
 544
 545
 546
 547 //
 548 // RenderBSPNode
 549 // Renders all subsectors below a given node,
 550 //  traversing subtree recursively.
 551 // Just call with BSP root.
 552 void R_RenderBSPNode (int bspnum)
 553 {
 554     node_t*     bsp;
 555     int         side;
 556
 557     // Found a subsector?
 558     if (bspnum & NF_SUBSECTOR)
 559     {
 560         if (bspnum == -1)
 561             R_Subsector (0);
 562         else
 563             R_Subsector (bspnum&(~NF_SUBSECTOR));
 564         return;
 565     }
 566
 567     bsp = &nodes[bspnum];
 568
 569     // Decide which side the view point is on.
 570     side = R_PointOnSide (viewx, viewy, bsp);
 571
 572     // Recursively divide front space.
 573     R_RenderBSPNode (bsp->children[side]);
 574
 575     // Possibly divide back space.
 576     if (R_CheckBBox (bsp->bbox[side^1]))
 577         R_RenderBSPNode (bsp->children[side^1]);
 578 }
 579
 580