1 // Emacs style mode select -*- C++ -*-
2 //-----------------------------------------------------------------------------
6 // Copyright (C) 1993-1996 by id Software, Inc.
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.
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
20 // BSP traversal, handling of LineSegs for rendering.
22 //-----------------------------------------------------------------------------
26 rcsid[] = "$Id: r_bsp.c,v 1.4 1997/02/03 22:45:12 b1 Exp $";
43 //#include "r_local.h"
50 sector_t* frontsector;
53 drawseg_t drawsegs[MAXDRAWSEGS];
68 void R_ClearDrawSegs (void)
77 // Clips the given range of columns
78 // and includes it in the new clip list.
90 // newend is one past the last valid seg
92 cliprange_t solidsegs[MAXSEGS];
98 // R_ClipSolidWallSegment
99 // Does handle solid walls,
100 // e.g. single sided LineDefs (middle texture)
101 // that entirely block the view.
104 R_ClipSolidWallSegment
111 // Find the first range that touches the range
112 // (adjacent pixels are touching).
114 while (start->last < first-1)
117 if (first < start->first)
119 if (last < start->first-1)
121 // Post is entirely visible (above start),
122 // so insert a new clippost.
123 R_StoreWallRange (first, last);
127 while (next != start)
137 // There is a fragment above *start.
138 R_StoreWallRange (first, start->first - 1);
139 // Now adjust the clip size.
140 start->first = first;
143 // Bottom contained in start?
144 if (last <= start->last)
148 while (last >= (next+1)->first-1)
150 // There is a fragment between two posts.
151 R_StoreWallRange (next->last + 1, (next+1)->first - 1);
154 if (last <= next->last)
156 // Bottom is contained in next.
157 // Adjust the clip size.
158 start->last = next->last;
163 // There is a fragment after *next.
164 R_StoreWallRange (next->last + 1, last);
165 // Adjust the clip size.
168 // Remove start+1 to next from the clip list,
169 // because start now covers their area.
173 // Post just extended past the bottom of one post.
178 while (next++ != newend)
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.
197 R_ClipPassWallSegment
203 // Find the first range that touches the range
204 // (adjacent pixels are touching).
206 while (start->last < first-1)
209 if (first < start->first)
211 if (last < start->first-1)
213 // Post is entirely visible (above start).
214 R_StoreWallRange (first, last);
218 // There is a fragment above *start.
219 R_StoreWallRange (first, start->first - 1);
222 // Bottom contained in start?
223 if (last <= start->last)
226 while (last >= (start+1)->first-1)
228 // There is a fragment between two posts.
229 R_StoreWallRange (start->last + 1, (start+1)->first - 1);
232 if (last <= start->last)
236 // There is a fragment after *next.
237 R_StoreWallRange (start->last + 1, last);
245 void R_ClearClipSegs (void)
247 solidsegs[0].first = -0x7fffffff;
248 solidsegs[0].last = -1;
249 solidsegs[1].first = viewwidth;
250 solidsegs[1].last = 0x7fffffff;
251 newend = solidsegs+2;
256 // Clips the given segment
257 // and adds any visible pieces to the line list.
259 void R_AddLine (seg_t* line)
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);
274 // Clip to view edges.
275 // OPTIMIZE: make constant out of 2*clipangle (FIELDOFVIEW).
276 span = angle1 - angle2;
278 // Back side? I.e. backface culling?
282 // Global angle needed by segcalc.
287 tspan = angle1 + clipangle;
288 if (tspan > 2*clipangle)
290 tspan -= 2*clipangle;
292 // Totally off the left edge?
298 tspan = clipangle - angle2;
299 if (tspan > 2*clipangle)
301 tspan -= 2*clipangle;
303 // Totally off the left edge?
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];
316 // Does not cross a pixel?
320 backsector = line->backsector;
322 // Single sided line?
327 if (backsector->ceilingheight <= frontsector->floorheight
328 || backsector->floorheight >= frontsector->ceilingheight)
332 if (backsector->ceilingheight != frontsector->ceilingheight
333 || backsector->floorheight != frontsector->floorheight)
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)
351 R_ClipPassWallSegment (x1, x2-1);
355 R_ClipSolidWallSegment (x1, x2-1);
361 // Checks BSP node/subtree bounding box.
363 // if some part of the bbox might be visible.
365 int checkcoord[12][4] =
381 boolean R_CheckBBox (fixed_t* bspcoord)
402 // Find the corners of the box
403 // that define the edges from current viewpoint.
404 if (viewx <= bspcoord[BOXLEFT])
406 else if (viewx < bspcoord[BOXRIGHT])
411 if (viewy >= bspcoord[BOXTOP])
413 else if (viewy > bspcoord[BOXBOTTOM])
418 boxpos = (boxy<<2)+boxx;
422 x1 = bspcoord[checkcoord[boxpos][0]];
423 y1 = bspcoord[checkcoord[boxpos][1]];
424 x2 = bspcoord[checkcoord[boxpos][2]];
425 y2 = bspcoord[checkcoord[boxpos][3]];
427 // check clip list for an open space
428 angle1 = R_PointToAngle (x1, y1) - viewangle;
429 angle2 = R_PointToAngle (x2, y2) - viewangle;
431 span = angle1 - angle2;
433 // Sitting on a line?
437 tspan = angle1 + clipangle;
439 if (tspan > 2*clipangle)
441 tspan -= 2*clipangle;
443 // Totally off the left edge?
449 tspan = clipangle - angle2;
450 if (tspan > 2*clipangle)
452 tspan -= 2*clipangle;
454 // Totally off the left edge?
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];
470 // Does not cross a pixel.
476 while (start->last < sx2)
479 if (sx1 >= start->first
480 && sx2 <= start->last)
482 // The clippost contains the new span.
493 // Determine floor/ceiling planes.
494 // Add sprites of things in sector.
495 // Draw one or more line segments.
497 void R_Subsector (int num)
504 if (num>=numsubsectors)
505 I_Error ("R_Subsector: ss %i with numss = %i",
511 sub = &subsectors[num];
512 frontsector = sub->sector;
513 count = sub->numlines;
514 line = &segs[sub->firstline];
516 if (frontsector->floorheight < viewz)
518 floorplane = R_FindPlane (frontsector->floorheight,
519 frontsector->floorpic,
520 frontsector->lightlevel);
525 if (frontsector->ceilingheight > viewz
526 || frontsector->ceilingpic == skyflatnum)
528 ceilingplane = R_FindPlane (frontsector->ceilingheight,
529 frontsector->ceilingpic,
530 frontsector->lightlevel);
535 R_AddSprites (frontsector);
549 // Renders all subsectors below a given node,
550 // traversing subtree recursively.
551 // Just call with BSP root.
552 void R_RenderBSPNode (int bspnum)
557 // Found a subsector?
558 if (bspnum & NF_SUBSECTOR)
563 R_Subsector (bspnum&(~NF_SUBSECTOR));
567 bsp = &nodes[bspnum];
569 // Decide which side the view point is on.
570 side = R_PointOnSide (viewx, viewy, bsp);
572 // Recursively divide front space.
573 R_RenderBSPNode (bsp->children[side]);
575 // Possibly divide back space.
576 if (R_CheckBBox (bsp->bbox[side^1]))
577 R_RenderBSPNode (bsp->children[side^1]);