![[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: //
1.1.1.5 ! root 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.
1.1.1.3 root 11: //
1.1.1.5 ! root 12: // The source is distributed in the hope that it will be useful,
1.1.1.3 root 13: // but WITHOUT ANY WARRANTY; without even the implied warranty of
1.1.1.5 ! root 14: // FITNESS FOR A PARTICULAR PURPOSE. See the DOOM Source Code License
! 15: // for more details.
1.1.1.3 root 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.1.5 ! root 44: char MsgText[256];
! 45: void WriteDebug(char *);
1.1 root 46:
47:
1.1.1.3 root 48: seg_t* curline;
49: side_t* sidedef;
50: line_t* linedef;
51: sector_t* frontsector;
52: sector_t* backsector;
1.1.1.2 root 53:
1.1.1.3 root 54: drawseg_t drawsegs[MAXDRAWSEGS];
55: drawseg_t* ds_p;
1.1.1.2 root 56:
57:
1.1.1.3 root 58: void
59: R_StoreWallRange
60: ( int start,
61: int stop );
1.1.1.2 root 62:
63:
1.1 root 64:
65:
1.1.1.3 root 66: //
67: // R_ClearDrawSegs
68: //
69: void R_ClearDrawSegs (void)
1.1 root 70: {
1.1.1.3 root 71: ds_p = drawsegs;
72: }
1.1 root 73:
74:
1.1.1.2 root 75:
1.1.1.3 root 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;
1.1.1.2 root 87:
88:
1.1.1.3 root 89: #define MAXSEGS 32
1.1.1.2 root 90:
1.1.1.3 root 91: // newend is one past the last valid seg
92: cliprange_t* newend;
93: cliprange_t solidsegs[MAXSEGS];
1.1 root 94:
95:
96:
97:
1.1.1.3 root 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 )
1.1 root 108: {
1.1.1.3 root 109: cliprange_t* next;
110: cliprange_t* start;
1.1 root 111:
1.1.1.3 root 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:
1.1 root 178:
1.1.1.3 root 179: while (next++ != newend)
180: {
181: // Remove a post.
182: *++start = *next;
183: }
1.1.1.2 root 184:
1.1.1.3 root 185: newend = start+1;
186: }
1.1 root 187:
188:
189:
190: //
1.1.1.3 root 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: //
1.1.1.5 ! root 197: void R_ClipPassWallSegment( int first, int last )
! 198: {
1.1.1.3 root 199: cliprange_t* start;
200:
201: // Find the first range that touches the range
202: // (adjacent pixels are touching).
203: start = solidsegs;
204: while (start->last < first-1)
1.1.1.5 ! root 205: start++;
1.1.1.3 root 206:
207: if (first < start->first)
1.1.1.5 ! root 208: {
! 209: if (last < start->first-1)
! 210: {
! 211: // Post is entirely visible (above start).
! 212: R_StoreWallRange (first, last);
! 213: return;
! 214: }
1.1.1.3 root 215:
1.1.1.5 ! root 216: // There is a fragment above *start.
! 217: R_StoreWallRange (first, start->first - 1);
! 218: }
1.1.1.3 root 219:
220: // Bottom contained in start?
221: if (last <= start->last)
1.1.1.5 ! root 222: return;
1.1.1.3 root 223:
224: while (last >= (start+1)->first-1)
1.1.1.5 ! root 225: {
! 226: // There is a fragment between two posts.
! 227: R_StoreWallRange (start->last + 1, (start+1)->first - 1);
! 228: start++;
! 229:
! 230: if (last <= start->last)
! 231: return;
! 232: }
1.1.1.3 root 233:
234: // There is a fragment after *next.
235: R_StoreWallRange (start->last + 1, last);
236: }
1.1 root 237:
1.1.1.2 root 238:
1.1 root 239:
240: //
1.1.1.3 root 241: // R_ClearClipSegs
1.1 root 242: //
1.1.1.3 root 243: void R_ClearClipSegs (void)
244: {
1.1.1.5 ! root 245: solidsegs[0].first = -(0x7fffffff);
1.1.1.3 root 246: solidsegs[0].last = -1;
247: solidsegs[1].first = viewwidth;
248: solidsegs[1].last = 0x7fffffff;
249: newend = solidsegs+2;
250: }
1.1 root 251:
1.1.1.3 root 252: //
253: // R_AddLine
254: // Clips the given segment
255: // and adds any visible pieces to the line list.
256: //
257: void R_AddLine (seg_t* line)
1.1.1.5 ! root 258: {
1.1.1.3 root 259: int x1;
260: int x2;
261: angle_t angle1;
262: angle_t angle2;
263: angle_t span;
264: angle_t tspan;
265:
266: curline = line;
267:
268: // OPTIMIZE: quickly reject orthogonal back sides.
269: angle1 = R_PointToAngle (line->v1->x, line->v1->y);
270: angle2 = R_PointToAngle (line->v2->x, line->v2->y);
271:
272: // Clip to view edges.
273: // OPTIMIZE: make constant out of 2*clipangle (FIELDOFVIEW).
274: span = angle1 - angle2;
275:
276: // Back side? I.e. backface culling?
277: if (span >= ANG180)
1.1.1.5 ! root 278: {
! 279: //WriteDebug("Back face culled...\n");
! 280: return;
! 281: }
1.1.1.3 root 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)
1.1.1.5 ! root 290: {
! 291: tspan -= 2*clipangle;
1.1.1.3 root 292:
1.1.1.5 ! root 293: // Totally off the left edge?
! 294: if (tspan >= span)
! 295: {
! 296: //WriteDebug("Off the left edge...\n");
! 297: return;
! 298: }
1.1.1.3 root 299:
1.1.1.5 ! root 300: angle1 = clipangle;
! 301: }
1.1.1.3 root 302: tspan = clipangle - angle2;
303: if (tspan > 2*clipangle)
1.1.1.5 ! root 304: {
! 305: tspan -= 2*clipangle;
1.1.1.3 root 306:
1.1.1.5 ! root 307: // Totally off the left edge?
! 308: if (tspan >= span)
! 309: {
! 310: //WriteDebug("Off the left edge...\n");
! 311: return;
! 312: }
! 313: angle2 = (clipangle * -1);
! 314: }
1.1.1.3 root 315:
316: // The seg is in the view range,
317: // but not necessarily visible.
318: angle1 = (angle1+ANG90)>>ANGLETOFINESHIFT;
319: angle2 = (angle2+ANG90)>>ANGLETOFINESHIFT;
320: x1 = viewangletox[angle1];
321: x2 = viewangletox[angle2];
322:
323: // Does not cross a pixel?
324: if (x1 == x2)
1.1.1.5 ! root 325: {
! 326: //WriteDebug("No pixel spanned...\n");
! 327: return;
! 328: }
1.1.1.3 root 329:
330: backsector = line->backsector;
331:
332: // Single sided line?
333: if (!backsector)
1.1.1.5 ! root 334: {
! 335: //WriteDebug("Wall...\n");
! 336: goto clipsolid;
! 337: }
1.1.1.2 root 338:
1.1.1.3 root 339: // Closed door.
1.1.1.5 ! root 340: if (backsector->ceilingheight <= frontsector->floorheight || backsector->floorheight >= frontsector->ceilingheight)
! 341: {
! 342: //WriteDebug("Closed door...\n");
! 343: goto clipsolid;
! 344: }
1.1.1.2 root 345:
1.1.1.3 root 346: // Window.
1.1.1.5 ! root 347: if (backsector->ceilingheight != frontsector->ceilingheight || backsector->floorheight != frontsector->floorheight)
! 348: {
! 349: //WriteDebug("Window (portal)...\n");
! 350: goto clippass;
! 351: }
1.1.1.3 root 352:
1.1.1.5 ! root 353: // Reject empty lines used for triggers and special events.
1.1.1.3 root 354: // Identical floor and ceiling on both sides,
355: // identical light levels on both sides,
356: // and no middle texture.
1.1.1.5 ! root 357: if (backsector->ceilingpic == frontsector->ceilingpic && backsector->floorpic == frontsector->floorpic &&
! 358: backsector->lightlevel == frontsector->lightlevel && curline->sidedef->midtexture == 0)
! 359: {
! 360: //WriteDebug("Trip line...\n");
! 361: return;
! 362: }
1.1.1.3 root 363:
1.1.1.5 ! root 364: clippass:
! 365: R_ClipPassWallSegment (x1, x2-1);
! 366: return;
1.1.1.3 root 367:
1.1.1.5 ! root 368: clipsolid:
! 369: R_ClipSolidWallSegment (x1, x2-1);
! 370: return;
! 371: }
1.1 root 372:
373:
1.1.1.3 root 374: //
375: // R_CheckBBox
376: // Checks BSP node/subtree bounding box.
377: // Returns true
378: // if some part of the bbox might be visible.
379: //
380: int checkcoord[12][4] =
1.1 root 381: {
1.1.1.3 root 382: {3,0,2,1},
383: {3,0,2,0},
384: {3,1,2,0},
385: {0},
386: {2,0,2,1},
387: {0,0,0,0},
388: {3,1,3,0},
389: {0},
390: {2,0,3,1},
391: {2,1,3,1},
392: {2,1,3,0}
393: };
1.1.1.2 root 394:
1.1 root 395:
1.1.1.3 root 396: boolean R_CheckBBox (fixed_t* bspcoord)
397: {
398: int boxx;
399: int boxy;
400: int boxpos;
401:
402: fixed_t x1;
403: fixed_t y1;
404: fixed_t x2;
405: fixed_t y2;
406:
407: angle_t angle1;
408: angle_t angle2;
409: angle_t span;
410: angle_t tspan;
411:
412: cliprange_t* start;
413:
414: int sx1;
415: int sx2;
416:
417: // Find the corners of the box
418: // that define the edges from current viewpoint.
419: if (viewx <= bspcoord[BOXLEFT])
420: boxx = 0;
421: else if (viewx < bspcoord[BOXRIGHT])
422: boxx = 1;
423: else
424: boxx = 2;
425:
426: if (viewy >= bspcoord[BOXTOP])
427: boxy = 0;
428: else if (viewy > bspcoord[BOXBOTTOM])
429: boxy = 1;
430: else
431: boxy = 2;
432:
433: boxpos = (boxy<<2)+boxx;
434: if (boxpos == 5)
435: return true;
436:
437: x1 = bspcoord[checkcoord[boxpos][0]];
438: y1 = bspcoord[checkcoord[boxpos][1]];
439: x2 = bspcoord[checkcoord[boxpos][2]];
440: y2 = bspcoord[checkcoord[boxpos][3]];
441:
442: // check clip list for an open space
443: angle1 = R_PointToAngle (x1, y1) - viewangle;
444: angle2 = R_PointToAngle (x2, y2) - viewangle;
445:
446: span = angle1 - angle2;
1.1.1.2 root 447:
1.1.1.3 root 448: // Sitting on a line?
449: if (span >= ANG180)
450: return true;
451:
452: tspan = angle1 + clipangle;
1.1.1.2 root 453:
1.1.1.3 root 454: if (tspan > 2*clipangle)
455: {
456: tspan -= 2*clipangle;
457:
458: // Totally off the left edge?
459: if (tspan >= span)
460: return false;
461:
462: angle1 = clipangle;
463: }
464: tspan = clipangle - angle2;
465: if (tspan > 2*clipangle)
466: {
467: tspan -= 2*clipangle;
468:
469: // Totally off the left edge?
470: if (tspan >= span)
471: return false;
472:
1.1.1.5 ! root 473: angle2 = (clipangle * -1);
1.1.1.3 root 474: }
475:
476:
477: // Find the first clippost
478: // that touches the source post
479: // (adjacent pixels are touching).
480: angle1 = (angle1+ANG90)>>ANGLETOFINESHIFT;
481: angle2 = (angle2+ANG90)>>ANGLETOFINESHIFT;
482: sx1 = viewangletox[angle1];
483: sx2 = viewangletox[angle2];
484:
485: // Does not cross a pixel.
486: if (sx1 == sx2)
487: return false;
488: sx2--;
489:
490: start = solidsegs;
491: while (start->last < sx2)
492: start++;
493:
494: if (sx1 >= start->first
495: && sx2 <= start->last)
496: {
497: // The clippost contains the new span.
498: return false;
499: }
1.1.1.2 root 500:
1.1.1.3 root 501: return true;
502: }
1.1 root 503:
504:
1.1.1.2 root 505:
1.1 root 506: //
1.1.1.3 root 507: // R_Subsector
508: // Determine floor/ceiling planes.
509: // Add sprites of things in sector.
510: // Draw one or more line segments.
1.1.1.2 root 511: //
1.1 root 512: void R_Subsector (int num)
513: {
1.1.1.3 root 514: int count;
515: seg_t* line;
516: subsector_t* sub;
517:
1.1 root 518: #ifdef RANGECHECK
1.1.1.5 ! root 519: if (num >= numsubsectors)
! 520: I_Error ("R_Subsector: ss %i with numss = %i", num, numsubsectors);
1.1 root 521: #endif
522:
1.1.1.3 root 523: sscount++;
524: sub = &subsectors[num];
525: frontsector = sub->sector;
526: count = sub->numlines;
527: line = &segs[sub->firstline];
528:
529: if (frontsector->floorheight < viewz)
1.1.1.5 ! root 530: {
! 531: floorplane = R_FindPlane (frontsector->floorheight, frontsector->floorpic, frontsector->lightlevel);
! 532: }
1.1.1.3 root 533: else
1.1.1.5 ! root 534: floorplane = NULL;
! 535:
! 536: if (frontsector->ceilingheight > viewz || frontsector->ceilingpic == skyflatnum)
! 537: {
! 538: ceilingplane = R_FindPlane (frontsector->ceilingheight, frontsector->ceilingpic, frontsector->lightlevel);
! 539: }
1.1.1.3 root 540: else
1.1.1.5 ! root 541: ceilingplane = NULL;
1.1.1.3 root 542:
543: R_AddSprites (frontsector);
544:
545: while (count--)
1.1.1.5 ! root 546: {
! 547: R_AddLine (line);
! 548: line++;
! 549: }
! 550: }
1.1 root 551:
552:
553:
1.1.1.2 root 554:
1.1 root 555: //
1.1.1.3 root 556: // RenderBSPNode
557: // Renders all subsectors below a given node,
558: // traversing subtree recursively.
559: // Just call with BSP root.
560: void R_RenderBSPNode (int bspnum)
1.1.1.5 ! root 561: {
1.1.1.3 root 562: node_t* bsp;
563: int side;
1.1.1.2 root 564:
1.1.1.3 root 565: // Found a subsector?
566: if (bspnum & NF_SUBSECTOR)
1.1.1.5 ! root 567: {
! 568: if (bspnum == -1)
! 569: R_Subsector (0);
! 570: else
! 571: R_Subsector (bspnum&(~NF_SUBSECTOR));
! 572: return;
! 573: }
1.1.1.3 root 574:
575: bsp = &nodes[bspnum];
576:
577: // Decide which side the view point is on.
1.1.1.5 ! root 578: side = R_PointOnSide(viewx, viewy, bsp);
1.1.1.3 root 579:
580: // Recursively divide front space.
581: R_RenderBSPNode (bsp->children[side]);
582:
583: // Possibly divide back space.
584: if (R_CheckBBox (bsp->bbox[side^1]))
585: R_RenderBSPNode (bsp->children[side^1]);
1.1 root 586: }
587:
588:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.