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