1
2 //**************************************************************************
3 //**
4 //** r_bsp.c : Heretic 2 : Raven Software, Corp.
5 //**
6 //** $RCSfile: r_bsp.c,v $
7 //** $Revision: 1.2 $
8 //** $Date: 95/07/13 15:17:10 $
9 //** $Author: cjr $
10 //**
11 //**************************************************************************
12
13 #include "h2def.h"
14 #include "r_local.h"
15
16 seg_t *curline;
17 side_t *sidedef;
18 line_t *linedef;
19 sector_t *frontsector, *backsector;
20
21 drawseg_t drawsegs[MAXDRAWSEGS], *ds_p;
22
23 void R_StoreWallRange (int start, int stop);
24
25 /*
26 ====================
27 =
28 = R_ClearDrawSegs
29 =
30 ====================
31 */
32
R_ClearDrawSegs(void)33 void R_ClearDrawSegs (void)
34 {
35 ds_p = drawsegs;
36 }
37
38 //=============================================================================
39
40
41 /*
42 ===============================================================================
43 =
44 = ClipWallSegment
45 =
46 = Clips the given range of columns and includes it in the new clip list
47 ===============================================================================
48 */
49
50 typedef struct
51 {
52 int first, last;
53 } cliprange_t;
54
55 #define MAXSEGS 32
56
57 cliprange_t solidsegs[MAXSEGS], *newend; // newend is one past the last valid seg
58
59
R_ClipSolidWallSegment(int first,int last)60 void R_ClipSolidWallSegment (int first, int last)
61 {
62 cliprange_t *next, *start;
63
64 // find the first range that touches the range (adjacent pixels are touching)
65 start = solidsegs;
66 while (start->last < first-1)
67 start++;
68
69 if (first < start->first)
70 {
71 if (last < start->first-1)
72 { // post is entirely visible (above start), so insert a new clippost
73 R_StoreWallRange (first, last);
74 next = newend;
75 newend++;
76 while (next != start)
77 {
78 *next = *(next-1);
79 next--;
80 }
81 next->first = first;
82 next->last = last;
83 return;
84 }
85
86 // there is a fragment above *start
87 R_StoreWallRange (first, start->first - 1);
88 start->first = first; // adjust the clip size
89 }
90
91 if (last <= start->last)
92 return; // bottom contained in start
93
94 next = start;
95 while (last >= (next+1)->first-1)
96 {
97 // there is a fragment between two posts
98 R_StoreWallRange (next->last + 1, (next+1)->first - 1);
99 next++;
100 if (last <= next->last)
101 { // bottom is contained in next
102 start->last = next->last; // adjust the clip size
103 goto crunch;
104 }
105 }
106
107 // there is a fragment after *next
108 R_StoreWallRange (next->last + 1, last);
109 start->last = last; // adjust the clip size
110
111
112 // remove start+1 to next from the clip list,
113 // because start now covers their area
114 crunch:
115 if (next == start)
116 return; // post just extended past the bottom of one post
117
118 while (next++ != newend) // remove a post
119 *++start = *next;
120 newend = start+1;
121 }
122
123 /*
124 ===============================================================================
125 =
126 = R_ClipPassWallSegment
127 =
128 = Clips the given range of columns, but does not includes it in the clip list
129 ===============================================================================
130 */
131
R_ClipPassWallSegment(int first,int last)132 void R_ClipPassWallSegment (int first, int last)
133 {
134 cliprange_t *start;
135
136 // find the first range that touches the range (adjacent pixels are touching)
137 start = solidsegs;
138 while (start->last < first-1)
139 start++;
140
141 if (first < start->first)
142 {
143 if (last < start->first-1)
144 { // post is entirely visible (above start)
145 R_StoreWallRange (first, last);
146 return;
147 }
148
149 // there is a fragment above *start
150 R_StoreWallRange (first, start->first - 1);
151 }
152
153 if (last <= start->last)
154 return; // bottom contained in start
155
156 while (last >= (start+1)->first-1)
157 {
158 // there is a fragment between two posts
159 R_StoreWallRange (start->last + 1, (start+1)->first - 1);
160 start++;
161 if (last <= start->last)
162 return;
163 }
164
165 // there is a fragment after *next
166 R_StoreWallRange (start->last + 1, last);
167 }
168
169
170
171 /*
172 ====================
173 =
174 = R_ClearClipSegs
175 =
176 ====================
177 */
178
R_ClearClipSegs(void)179 void R_ClearClipSegs (void)
180 {
181 solidsegs[0].first = -0x7fffffff;
182 solidsegs[0].last = -1;
183 solidsegs[1].first = viewwidth;
184 solidsegs[1].last = 0x7fffffff;
185 newend = solidsegs+2;
186 }
187
188
189 //=============================================================================
190
191 /*
192 ======================
193 =
194 = R_AddLine
195 =
196 = Clips the given segment and adds any visible pieces to the line list
197 =
198 ======================
199 */
200
R_AddLine(seg_t * line)201 void R_AddLine (seg_t *line)
202 {
203 int x1, x2;
204 angle_t angle1, angle2, span, tspan;
205
206 #ifdef __NeXT__
207 RD_DrawLineCheck (line);
208 #endif
209 curline = line;
210
211 // OPTIMIZE: quickly reject orthogonal back sides
212
213 angle1 = R_PointToAngle (line->v1->x, line->v1->y);
214 angle2 = R_PointToAngle (line->v2->x, line->v2->y);
215
216 //
217 // clip to view edges
218 // OPTIMIZE: make constant out of 2*clipangle (FIELDOFVIEW)
219 span = angle1 - angle2;
220 if (span >= ANG180)
221 return; // back side
222
223 rw_angle1 = angle1; // global angle needed by segcalc
224 angle1 -= viewangle;
225 angle2 -= viewangle;
226
227 tspan = angle1 + clipangle;
228 if (tspan > 2*clipangle)
229 {
230 tspan -= 2*clipangle;
231 if (tspan >= span)
232 return; // totally off the left edge
233 angle1 = clipangle;
234 }
235 tspan = clipangle - angle2;
236 if (tspan > 2*clipangle)
237 {
238 tspan -= 2*clipangle;
239 if (tspan >= span)
240 return; // totally off the left edge
241 angle2 = -clipangle;
242 }
243
244 //
245 // the seg is in the view range, but not necessarily visible
246 //
247 angle1 = (angle1+ANG90)>>ANGLETOFINESHIFT;
248 angle2 = (angle2+ANG90)>>ANGLETOFINESHIFT;
249 x1 = viewangletox[angle1];
250 x2 = viewangletox[angle2];
251 if (x1 == x2)
252 return; // does not cross a pixel
253
254 backsector = line->backsector;
255
256 if (!backsector)
257 goto clipsolid; // single sided line
258
259 if (backsector->ceilingheight <= frontsector->floorheight
260 || backsector->floorheight >= frontsector->ceilingheight)
261 goto clipsolid; // closed door
262
263 if (backsector->ceilingheight != frontsector->ceilingheight
264 || backsector->floorheight != frontsector->floorheight)
265 goto clippass; // window
266
267 // reject empty lines used for triggers and special events
268 if (backsector->ceilingpic == frontsector->ceilingpic
269 && backsector->floorpic == frontsector->floorpic
270 && backsector->lightlevel == frontsector->lightlevel
271 && backsector->special == frontsector->special
272 && curline->sidedef->midtexture == 0)
273 return;
274
275 clippass:
276 R_ClipPassWallSegment (x1, x2-1);
277 return;
278
279 clipsolid:
280 R_ClipSolidWallSegment (x1, x2-1);
281 }
282
283 //============================================================================
284
285
286 /*
287 ===============================================================================
288 =
289 = R_CheckBBox
290 =
291 = Returns true if some part of the bbox might be visible
292 =
293 ===============================================================================
294 */
295
296 int checkcoord[12][4] = {
297 {3,0, 2,1},
298 {3,0, 2,0},
299 {3,1, 2,0},
300 {0},
301 {2,0, 2,1},
302 {0,0,0,0},
303 {3,1, 3,0},
304 {0},
305 {2,0, 3,1},
306 {2,1, 3,1},
307 {2,1, 3,0} };
308
309
R_CheckBBox(fixed_t * bspcoord)310 boolean R_CheckBBox (fixed_t *bspcoord)
311 {
312 int boxx, boxy, boxpos;
313 fixed_t x1, y1, x2, y2;
314 angle_t angle1, angle2, span, tspan;
315 cliprange_t *start;
316 int sx1, sx2;
317
318 #ifdef __NeXT__
319 RD_DrawBBox (bspcoord);
320 #endif
321
322 // find the corners of the box that define the edges from current viewpoint
323 if (viewx <= bspcoord[BOXLEFT])
324 boxx = 0;
325 else if (viewx < bspcoord[BOXRIGHT])
326 boxx = 1;
327 else
328 boxx = 2;
329
330 if (viewy >= bspcoord[BOXTOP])
331 boxy = 0;
332 else if (viewy > bspcoord[BOXBOTTOM])
333 boxy = 1;
334 else
335 boxy = 2;
336
337 boxpos = (boxy<<2)+boxx;
338 if (boxpos == 5)
339 return true;
340
341 x1 = bspcoord[checkcoord[boxpos][0]];
342 y1 = bspcoord[checkcoord[boxpos][1]];
343 x2 = bspcoord[checkcoord[boxpos][2]];
344 y2 = bspcoord[checkcoord[boxpos][3]];
345
346
347 #ifdef __NeXT__
348 // RD_DisplayLine (x1, y1, x2, y2, 0.1);
349 #endif
350
351 //
352 // check clip list for an open space
353 //
354 angle1 = R_PointToAngle (x1, y1) - viewangle;
355 angle2 = R_PointToAngle (x2, y2) - viewangle;
356
357 span = angle1 - angle2;
358 if (span >= ANG180)
359 return true; // sitting on a line
360 tspan = angle1 + clipangle;
361 if (tspan > 2*clipangle)
362 {
363 tspan -= 2*clipangle;
364 if (tspan >= span)
365 return false; // totally off the left edge
366 angle1 = clipangle;
367 }
368 tspan = clipangle - angle2;
369 if (tspan > 2*clipangle)
370 {
371 tspan -= 2*clipangle;
372 if (tspan >= span)
373 return false; // totally off the left edge
374 angle2 = -clipangle;
375 }
376
377
378 // find the first clippost that touches the source post (adjacent pixels are touching)
379 angle1 = (angle1+ANG90)>>ANGLETOFINESHIFT;
380 angle2 = (angle2+ANG90)>>ANGLETOFINESHIFT;
381 sx1 = viewangletox[angle1];
382 sx2 = viewangletox[angle2];
383 if (sx1 == sx2)
384 return false; // does not cross a pixel
385 sx2--;
386
387 start = solidsegs;
388 while (start->last < sx2)
389 start++;
390 if (sx1 >= start->first && sx2 <= start->last)
391 return false; // the clippost contains the new span
392
393 return true;
394 }
395
396
397 /*
398 ================
399 =
400 = R_Subsector
401 =
402 = Draw one or more segments
403 ================
404 */
405
R_Subsector(int num)406 void R_Subsector (int num)
407 {
408 int count;
409 seg_t *line;
410 subsector_t *sub;
411 int polyCount;
412 seg_t **polySeg;
413
414 #ifdef RANGECHECK
415 if (num>=numsubsectors)
416 I_Error ("R_Subsector: ss %i with numss = %i",num, numsubsectors);
417 #endif
418
419 sscount++;
420 sub = &subsectors[num];
421 frontsector = sub->sector;
422 count = sub->numlines;
423 line = &segs[sub->firstline];
424
425 if(frontsector->floorheight < viewz)
426 {
427 floorplane = R_FindPlane(frontsector->floorheight,
428 frontsector->floorpic, frontsector->lightlevel,
429 frontsector->special);
430 }
431 else
432 {
433 floorplane = NULL;
434 }
435
436 if(frontsector->ceilingheight > viewz
437 || frontsector->ceilingpic == skyflatnum)
438 {
439 ceilingplane = R_FindPlane(frontsector->ceilingheight,
440 frontsector->ceilingpic, frontsector->lightlevel, 0);
441 }
442 else
443 {
444 ceilingplane = NULL;
445 }
446
447 R_AddSprites(frontsector);
448 if(sub->poly)
449 { // Render the polyobj in the subsector first
450 polyCount = sub->poly->numsegs;
451 polySeg = sub->poly->segs;
452 while(polyCount--)
453 {
454 R_AddLine(*polySeg++);
455 }
456 }
457 while (count--)
458 {
459 R_AddLine (line);
460 line++;
461 }
462 }
463
464
465 /*
466 ===============================================================================
467 =
468 = RenderBSPNode
469 =
470 ===============================================================================
471 */
472
R_RenderBSPNode(int bspnum)473 void R_RenderBSPNode (int bspnum)
474 {
475 node_t *bsp;
476 int side;
477
478 if (bspnum & NF_SUBSECTOR)
479 {
480 if (bspnum == -1)
481 R_Subsector (0);
482 else
483 R_Subsector (bspnum&(~NF_SUBSECTOR));
484 return;
485 }
486
487 bsp = &nodes[bspnum];
488
489 #ifdef __NeXT__
490 RD_DrawNodeLine (bsp);
491 #endif
492
493 //
494 // decide which side the view point is on
495 //
496 side = R_PointOnSide (viewx, viewy, bsp);
497
498 R_RenderBSPNode (bsp->children[side]); // recursively divide front space
499
500 if (R_CheckBBox (bsp->bbox[side^1])) // possibly divide back space
501 R_RenderBSPNode (bsp->children[side^1]);
502 }
503
504
505