![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to r_bsp.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [DOOM] / doom|
Return to r_bsp.c CVS log | Up to [DOOM] / doom |
1.1.1.3 ! root 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: //----------------------------------------------------------------------------- 1.1 root 23: 24: 1.1.1.3 ! root 25: static const char ! 26: rcsid[] = "$Id: r_bsp.c,v 1.4 1997/02/03 22:45:12 b1 Exp $"; 1.1 root 27: 28: 1.1.1.3 ! root 29: #include "doomdef.h" 1.1 root 30: 1.1.1.3 ! root 31: #include "m_bbox.h" 1.1 root 32: 1.1.1.3 ! root 33: #include "i_system.h" 1.1 root 34: 1.1.1.3 ! root 35: #include "r_main.h" ! 36: #include "r_plane.h" ! 37: #include "r_things.h" 1.1 root 38: 1.1.1.3 ! root 39: // State. ! 40: #include "doomstat.h" ! 41: #include "r_state.h" 1.1 root 42: 1.1.1.3 ! root 43: //#include "r_local.h" 1.1 root 44: 45: 46: 1.1.1.3 ! root 47: seg_t* curline; ! 48: side_t* sidedef; ! 49: line_t* linedef; ! 50: sector_t* frontsector; ! 51: sector_t* backsector; 1.1.1.2 root 52: 1.1.1.3 ! root 53: drawseg_t drawsegs[MAXDRAWSEGS]; ! 54: drawseg_t* ds_p; 1.1.1.2 root 55: 56: 1.1.1.3 ! root 57: void ! 58: R_StoreWallRange ! 59: ( int start, ! 60: int stop ); 1.1.1.2 root 61: 62: 1.1 root 63: 64: 1.1.1.3 ! root 65: // ! 66: // R_ClearDrawSegs ! 67: // ! 68: void R_ClearDrawSegs (void) 1.1 root 69: { 1.1.1.3 ! root 70: ds_p = drawsegs; ! 71: } 1.1 root 72: 73: 1.1.1.2 root 74: 1.1.1.3 ! root 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; 1.1.1.2 root 86: 87: 1.1.1.3 ! root 88: #define MAXSEGS 32 1.1.1.2 root 89: 1.1.1.3 ! root 90: // newend is one past the last valid seg ! 91: cliprange_t* newend; ! 92: cliprange_t solidsegs[MAXSEGS]; 1.1 root 93: 94: 95: 96: 1.1.1.3 ! root 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 ) 1.1 root 107: { 1.1.1.3 ! root 108: cliprange_t* next; ! 109: cliprange_t* start; 1.1 root 110: 1.1.1.3 ! root 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: 1.1 root 177: 1.1.1.3 ! root 178: while (next++ != newend) ! 179: { ! 180: // Remove a post. ! 181: *++start = *next; ! 182: } 1.1.1.2 root 183: 1.1.1.3 ! root 184: newend = start+1; ! 185: } 1.1 root 186: 187: 188: 189: // 1.1.1.3 ! root 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: } 1.1 root 239: 1.1.1.2 root 240: 1.1 root 241: 242: // 1.1.1.3 ! root 243: // R_ClearClipSegs 1.1 root 244: // 1.1.1.3 ! root 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: } 1.1 root 253: 1.1.1.3 ! root 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; 1.1.1.2 root 325: 1.1.1.3 ! root 326: // Closed door. ! 327: if (backsector->ceilingheight <= frontsector->floorheight 1.1 root 328: || backsector->floorheight >= frontsector->ceilingheight) 1.1.1.3 ! root 329: goto clipsolid; 1.1.1.2 root 330: 1.1.1.3 ! root 331: // Window. ! 332: if (backsector->ceilingheight != frontsector->ceilingheight 1.1 root 333: || backsector->floorheight != frontsector->floorheight) 1.1.1.3 ! root 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 1.1 root 342: && backsector->floorpic == frontsector->floorpic 343: && backsector->lightlevel == frontsector->lightlevel 344: && curline->sidedef->midtexture == 0) 1.1.1.3 ! root 345: { 1.1 root 346: return; 1.1.1.3 ! root 347: } ! 348: ! 349: ! 350: clippass: ! 351: R_ClipPassWallSegment (x1, x2-1); ! 352: return; ! 353: ! 354: clipsolid: ! 355: R_ClipSolidWallSegment (x1, x2-1); 1.1 root 356: } 357: 358: 1.1.1.3 ! root 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] = 1.1 root 366: { 1.1.1.3 ! root 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: }; 1.1.1.2 root 379: 1.1 root 380: 1.1.1.3 ! root 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; 1.1.1.2 root 432: 1.1.1.3 ! root 433: // Sitting on a line? ! 434: if (span >= ANG180) ! 435: return true; ! 436: ! 437: tspan = angle1 + clipangle; 1.1.1.2 root 438: 1.1.1.3 ! root 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: } 1.1.1.2 root 485: 1.1.1.3 ! root 486: return true; ! 487: } 1.1 root 488: 489: 1.1.1.2 root 490: 1.1 root 491: // 1.1.1.3 ! root 492: // R_Subsector ! 493: // Determine floor/ceiling planes. ! 494: // Add sprites of things in sector. ! 495: // Draw one or more line segments. 1.1.1.2 root 496: // 1.1 root 497: void R_Subsector (int num) 498: { 1.1.1.3 ! root 499: int count; ! 500: seg_t* line; ! 501: subsector_t* sub; ! 502: 1.1 root 503: #ifdef RANGECHECK 1.1.1.3 ! root 504: if (num>=numsubsectors) ! 505: I_Error ("R_Subsector: ss %i with numss = %i", ! 506: num, ! 507: numsubsectors); 1.1 root 508: #endif 509: 1.1.1.3 ! root 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: } 1.1 root 542: } 543: 544: 545: 1.1.1.2 root 546: 1.1 root 547: // 1.1.1.3 ! root 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; 1.1.1.2 root 556: 1.1.1.3 ! root 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]); 1.1 root 578: } 579: 580:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.