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