![[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.4 ! root 8: // This program is free software; you can redistribute it and/or
! 9: // modify it under the terms of the GNU General Public License
! 10: // as published by the Free Software Foundation; either version 2
! 11: // of the License, or (at your option) any later version.
1.1.1.3 root 12: //
1.1.1.4 ! root 13: // This program is distributed in the hope that it will be useful,
1.1.1.3 root 14: // but WITHOUT ANY WARRANTY; without even the implied warranty of
1.1.1.4 ! root 15: // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
! 16: // GNU General Public License for more details.
1.1.1.3 root 17: //
18: // $Log:$
19: //
20: // DESCRIPTION:
21: // BSP traversal, handling of LineSegs for rendering.
22: //
23: //-----------------------------------------------------------------------------
1.1 root 24:
25:
1.1.1.3 root 26: static const char
27: rcsid[] = "$Id: r_bsp.c,v 1.4 1997/02/03 22:45:12 b1 Exp $";
1.1 root 28:
29:
1.1.1.3 root 30: #include "doomdef.h"
1.1 root 31:
1.1.1.3 root 32: #include "m_bbox.h"
1.1 root 33:
1.1.1.3 root 34: #include "i_system.h"
1.1 root 35:
1.1.1.3 root 36: #include "r_main.h"
37: #include "r_plane.h"
38: #include "r_things.h"
1.1 root 39:
1.1.1.3 root 40: // State.
41: #include "doomstat.h"
42: #include "r_state.h"
1.1 root 43:
1.1.1.3 root 44: //#include "r_local.h"
1.1 root 45:
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: //
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: }
1.1 root 240:
1.1.1.2 root 241:
1.1 root 242:
243: //
1.1.1.3 root 244: // R_ClearClipSegs
1.1 root 245: //
1.1.1.3 root 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: }
1.1 root 254:
1.1.1.3 root 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;
1.1.1.2 root 326:
1.1.1.3 root 327: // Closed door.
328: if (backsector->ceilingheight <= frontsector->floorheight
1.1 root 329: || backsector->floorheight >= frontsector->ceilingheight)
1.1.1.3 root 330: goto clipsolid;
1.1.1.2 root 331:
1.1.1.3 root 332: // Window.
333: if (backsector->ceilingheight != frontsector->ceilingheight
1.1 root 334: || backsector->floorheight != frontsector->floorheight)
1.1.1.3 root 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
1.1 root 343: && backsector->floorpic == frontsector->floorpic
344: && backsector->lightlevel == frontsector->lightlevel
345: && curline->sidedef->midtexture == 0)
1.1.1.3 root 346: {
1.1 root 347: return;
1.1.1.3 root 348: }
349:
350:
351: clippass:
352: R_ClipPassWallSegment (x1, x2-1);
353: return;
354:
355: clipsolid:
356: R_ClipSolidWallSegment (x1, x2-1);
1.1 root 357: }
358:
359:
1.1.1.3 root 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] =
1.1 root 367: {
1.1.1.3 root 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: };
1.1.1.2 root 380:
1.1 root 381:
1.1.1.3 root 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;
1.1.1.2 root 433:
1.1.1.3 root 434: // Sitting on a line?
435: if (span >= ANG180)
436: return true;
437:
438: tspan = angle1 + clipangle;
1.1.1.2 root 439:
1.1.1.3 root 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: }
1.1.1.2 root 486:
1.1.1.3 root 487: return true;
488: }
1.1 root 489:
490:
1.1.1.2 root 491:
1.1 root 492: //
1.1.1.3 root 493: // R_Subsector
494: // Determine floor/ceiling planes.
495: // Add sprites of things in sector.
496: // Draw one or more line segments.
1.1.1.2 root 497: //
1.1 root 498: void R_Subsector (int num)
499: {
1.1.1.3 root 500: int count;
501: seg_t* line;
502: subsector_t* sub;
503:
1.1 root 504: #ifdef RANGECHECK
1.1.1.3 root 505: if (num>=numsubsectors)
506: I_Error ("R_Subsector: ss %i with numss = %i",
507: num,
508: numsubsectors);
1.1 root 509: #endif
510:
1.1.1.3 root 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: }
1.1 root 543: }
544:
545:
546:
1.1.1.2 root 547:
1.1 root 548: //
1.1.1.3 root 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;
1.1.1.2 root 557:
1.1.1.3 root 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]);
1.1 root 579: }
580:
581:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.