Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 581 lines (458 sloc) 11.197 kb
4eb368a @tbradshaw The DOOM sources as originally released on December 23, 1997
tbradshaw authored
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
Something went wrong with that request. Please try again.