1 /*
2 sw32_redge.c
3
4 (description)
5
6 Copyright (C) 1996-1997 Id Software, Inc.
7
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.
12
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
16
17 See the GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to:
21
22 Free Software Foundation, Inc.
23 59 Temple Place - Suite 330
24 Boston, MA 02111-1307, USA
25
26 */
27 #ifdef HAVE_CONFIG_H
28 # include "config.h"
29 #endif
30
31 #define NH_DEFINE
32 #include "namehack.h"
33
34 #include "QF/render.h"
35 #include "QF/sound.h"
36
37 #include "d_ifacea.h"
38 #include "r_internal.h"
39 #include "vid_internal.h"
40
41 /*
42 FIXME
43 the complex cases add new polys on most lines, so dont optimize for
44 keeping them the same have multiple free span lists to try to get better
45 coherence ? low depth complexity-- 1 to 3 or so this breaks spans at every
46 edge, even hidden ones (bad)
47
48 have a sentinal at both ends?
49 */
50
51 edge_t *sw32_auxedges;
52 edge_t *sw32_r_edges, *sw32_edge_p, *sw32_edge_max;
53
54 surf_t *sw32_surfaces, *sw32_surface_p, *sw32_surf_max;
55
56 /*
57 surfaces are generated in back to front order by the bsp, so if a surf
58 pointer is greater than another one, it should be drawn in front
59 sw32_surfaces[1] is the background, and is used as the active surface stack
60 */
61
62 edge_t *sw32_newedges[MAXHEIGHT];
63 edge_t *sw32_removeedges[MAXHEIGHT];
64
65 static espan_t *span_p, *max_span_p;
66
67 int sw32_r_currentkey;
68
69
70 static int current_iv;
71
72 static int edge_head_u_shift20, edge_tail_u_shift20;
73
74 static void (*pdrawfunc) (void);
75
76 static edge_t edge_head;
77 static edge_t edge_tail;
78 static edge_t edge_aftertail;
79 static edge_t edge_sentinel;
80
81 static float fv;
82
83 static void
R_DrawCulledPolys(void)84 R_DrawCulledPolys (void)
85 {
86 surf_t *s;
87 msurface_t *pface;
88
89 currententity = &r_worldentity;
90
91 if (sw32_r_worldpolysbacktofront) {
92 for (s = sw32_surface_p - 1; s > &sw32_surfaces[1]; s--) {
93 if (!s->spans)
94 continue;
95
96 if (!(s->flags & SURF_DRAWBACKGROUND)) {
97 pface = (msurface_t *) s->data;
98 sw32_R_RenderPoly (pface, 15);
99 }
100 }
101 } else {
102 for (s = &sw32_surfaces[1]; s < sw32_surface_p; s++) {
103 if (!s->spans)
104 continue;
105
106 if (!(s->flags & SURF_DRAWBACKGROUND)) {
107 pface = (msurface_t *) s->data;
108 sw32_R_RenderPoly (pface, 15);
109 }
110 }
111 }
112 }
113
114 void
sw32_R_BeginEdgeFrame(void)115 sw32_R_BeginEdgeFrame (void)
116 {
117 int v;
118
119 sw32_edge_p = sw32_r_edges;
120 sw32_edge_max = &sw32_r_edges[sw32_r_numallocatededges];
121
122 sw32_surface_p = &sw32_surfaces[2]; // background is surface 1,
123 // surface 0 is a dummy
124 sw32_surfaces[1].spans = NULL; // no background spans yet
125 sw32_surfaces[1].flags = SURF_DRAWBACKGROUND;
126
127 // put the background behind everything in the world
128 pdrawfunc = sw32_R_GenerateSpans;
129 sw32_surfaces[1].key = 0x7FFFFFFF;
130 sw32_r_currentkey = 0;
131
132 // FIXME: set with memset
133 for (v = r_refdef.vrect.y; v < r_refdef.vrectbottom; v++) {
134 sw32_newedges[v] = sw32_removeedges[v] = NULL;
135 }
136 }
137
138 /*
139 sw32_R_InsertNewEdges
140
141 Adds the edges in the linked list edgestoadd, adding them to the edges
142 in the linked list edgelist. edgestoadd is assumed to be sorted on u,
143 and non-empty (this is actually sw32_newedges[v]). edgelist is assumed to
144 be sorted on u, with a sentinel at the end (actually, this is the
145 active edge table starting at edge_head.next).
146 */
147 void
sw32_R_InsertNewEdges(edge_t * edgestoadd,edge_t * edgelist)148 sw32_R_InsertNewEdges (edge_t *edgestoadd, edge_t *edgelist)
149 {
150 edge_t *next_edge;
151
152 do {
153 next_edge = edgestoadd->next;
154 edgesearch:
155 if (edgelist->u >= edgestoadd->u)
156 goto addedge;
157 edgelist = edgelist->next;
158 if (edgelist->u >= edgestoadd->u)
159 goto addedge;
160 edgelist = edgelist->next;
161 if (edgelist->u >= edgestoadd->u)
162 goto addedge;
163 edgelist = edgelist->next;
164 if (edgelist->u >= edgestoadd->u)
165 goto addedge;
166 edgelist = edgelist->next;
167 goto edgesearch;
168
169 // insert edgestoadd before edgelist
170 addedge:
171 edgestoadd->next = edgelist;
172 edgestoadd->prev = edgelist->prev;
173 edgelist->prev->next = edgestoadd;
174 edgelist->prev = edgestoadd;
175 } while ((edgestoadd = next_edge) != NULL);
176 }
177
178 void
sw32_R_RemoveEdges(edge_t * pedge)179 sw32_R_RemoveEdges (edge_t *pedge)
180 {
181
182 do {
183 pedge->next->prev = pedge->prev;
184 pedge->prev->next = pedge->next;
185 } while ((pedge = pedge->nextremove) != NULL);
186 }
187
188 void
sw32_R_StepActiveU(edge_t * pedge)189 sw32_R_StepActiveU (edge_t *pedge)
190 {
191 edge_t *pnext_edge, *pwedge;
192
193 while (1) {
194 nextedge:
195 pedge->u += pedge->u_step;
196 if (pedge->u < pedge->prev->u)
197 goto pushback;
198 pedge = pedge->next;
199
200 pedge->u += pedge->u_step;
201 if (pedge->u < pedge->prev->u)
202 goto pushback;
203 pedge = pedge->next;
204
205 pedge->u += pedge->u_step;
206 if (pedge->u < pedge->prev->u)
207 goto pushback;
208 pedge = pedge->next;
209
210 pedge->u += pedge->u_step;
211 if (pedge->u < pedge->prev->u)
212 goto pushback;
213 pedge = pedge->next;
214
215 goto nextedge;
216
217 pushback:
218 if (pedge == &edge_aftertail)
219 return;
220
221 // push it back to keep it sorted
222 pnext_edge = pedge->next;
223
224 // pull the edge out of the edge list
225 pedge->next->prev = pedge->prev;
226 pedge->prev->next = pedge->next;
227
228 // find out where the edge goes in the edge list
229 pwedge = pedge->prev->prev;
230
231 while (pwedge->u > pedge->u) {
232 pwedge = pwedge->prev;
233 }
234
235 // put the edge back into the edge list
236 pedge->next = pwedge->next;
237 pedge->prev = pwedge;
238 pedge->next->prev = pedge;
239 pwedge->next = pedge;
240
241 pedge = pnext_edge;
242 if (pedge == &edge_tail)
243 return;
244 }
245 }
246
247 static void
R_CleanupSpan(void)248 R_CleanupSpan (void)
249 {
250 surf_t *surf;
251 int iu;
252 espan_t *span;
253
254 // now that we've reached the right edge of the screen, we're done with any
255 // unfinished surfaces, so emit a span for whatever's on top
256 surf = sw32_surfaces[1].next;
257 iu = edge_tail_u_shift20;
258 if (iu > surf->last_u) {
259 span = span_p++;
260 span->u = surf->last_u;
261 span->count = iu - span->u;
262 span->v = current_iv;
263 span->pnext = surf->spans;
264 surf->spans = span;
265 }
266 // reset spanstate for all surfaces in the surface stack
267 do {
268 surf->spanstate = 0;
269 surf = surf->next;
270 } while (surf != &sw32_surfaces[1]);
271 }
272
273 static void
R_TrailingEdge(surf_t * surf,edge_t * edge)274 R_TrailingEdge (surf_t *surf, edge_t *edge)
275 {
276 espan_t *span;
277 int iu;
278
279 // don't generate a span if this is an inverted span, with the end edge
280 // preceding the start edge (that is, we haven't seen the start edge yet)
281 if (--surf->spanstate == 0) {
282 if (surf == sw32_surfaces[1].next) {
283 // emit a span (current top going away)
284 iu = edge->u >> 20;
285 if (iu > surf->last_u) {
286 span = span_p++;
287 span->u = surf->last_u;
288 span->count = iu - span->u;
289 span->v = current_iv;
290 span->pnext = surf->spans;
291 surf->spans = span;
292 }
293 // set last_u on the surface below
294 surf->next->last_u = iu;
295 }
296
297 surf->prev->next = surf->next;
298 surf->next->prev = surf->prev;
299 }
300 }
301
302 static void
R_LeadingEdge(edge_t * edge)303 R_LeadingEdge (edge_t *edge)
304 {
305 espan_t *span;
306 surf_t *surf, *surf2;
307 int iu;
308 double fu, newzi, testzi, newzitop, newzibottom;
309
310 if (edge->surfs[1]) {
311 // it's adding a new surface in, so find the correct place
312 surf = &sw32_surfaces[edge->surfs[1]];
313
314 // don't start a span if this is an inverted span, with the end edge
315 // preceding the start edge (that is, we've already seen the end edge)
316 if (++surf->spanstate == 1) {
317 surf2 = sw32_surfaces[1].next;
318
319 if (surf->key < surf2->key)
320 goto newtop;
321
322 // if it's two surfaces on the same plane, the one that's already
323 // active is in front, so keep going unless it's a bmodel
324 if (surf->insubmodel && (surf->key == surf2->key)) {
325 // must be two bmodels in the same leaf; sort on 1/z
326 fu = (float) (edge->u - 0xFFFFF) * (1.0 / 0x100000);
327 newzi = surf->d_ziorigin + fv * surf->d_zistepv +
328 fu * surf->d_zistepu;
329 newzibottom = newzi * 0.99;
330
331 testzi = surf2->d_ziorigin + fv * surf2->d_zistepv +
332 fu * surf2->d_zistepu;
333
334 if (newzibottom >= testzi) {
335 goto newtop;
336 }
337
338 newzitop = newzi * 1.01;
339 if (newzitop >= testzi) {
340 if (surf->d_zistepu >= surf2->d_zistepu) {
341 goto newtop;
342 }
343 }
344 }
345
346 continue_search:
347
348 do {
349 surf2 = surf2->next;
350 } while (surf->key > surf2->key);
351
352 if (surf->key == surf2->key) {
353 // if it's two surfaces on the same plane, the already active
354 // one is in front, so keep going unless it's a bmodel
355 if (!surf->insubmodel)
356 goto continue_search;
357
358 // must be two bmodels in the same leaf; sort on 1/z
359 fu = (float) (edge->u - 0xFFFFF) * (1.0 / 0x100000);
360 newzi = surf->d_ziorigin + fv * surf->d_zistepv +
361 fu * surf->d_zistepu;
362 newzibottom = newzi * 0.99;
363
364 testzi = surf2->d_ziorigin + fv * surf2->d_zistepv +
365 fu * surf2->d_zistepu;
366
367 if (newzibottom >= testzi) {
368 goto gotposition;
369 }
370
371 newzitop = newzi * 1.01;
372 if (newzitop >= testzi) {
373 if (surf->d_zistepu >= surf2->d_zistepu) {
374 goto gotposition;
375 }
376 }
377
378 goto continue_search;
379 }
380
381 goto gotposition;
382
383 newtop:
384 // emit a span (obscures current top)
385 iu = edge->u >> 20;
386
387 if (iu > surf2->last_u) {
388 span = span_p++;
389 span->u = surf2->last_u;
390 span->count = iu - span->u;
391 span->v = current_iv;
392 span->pnext = surf2->spans;
393 surf2->spans = span;
394 }
395 // set last_u on the new span
396 surf->last_u = iu;
397
398 gotposition:
399 // insert before surf2
400 surf->next = surf2;
401 surf->prev = surf2->prev;
402 surf2->prev->next = surf;
403 surf2->prev = surf;
404 }
405 }
406 }
407
408 void
sw32_R_GenerateSpans(void)409 sw32_R_GenerateSpans (void)
410 {
411 edge_t *edge;
412 surf_t *surf;
413
414 // clear active surfaces to just the background surface
415 sw32_surfaces[1].next = sw32_surfaces[1].prev = &sw32_surfaces[1];
416 sw32_surfaces[1].last_u = edge_head_u_shift20;
417
418 // generate spans
419 for (edge = edge_head.next; edge != &edge_tail; edge = edge->next) {
420 if (edge->surfs[0]) {
421 // it has a left surface, so a surface is going away for this span
422 surf = &sw32_surfaces[edge->surfs[0]];
423
424 R_TrailingEdge (surf, edge);
425
426 if (!edge->surfs[1])
427 continue;
428 }
429
430 R_LeadingEdge (edge);
431 }
432
433 R_CleanupSpan ();
434 }
435
436 /*
437 R_ScanEdges
438
439 Input:
440 sw32_newedges[] array
441 this has links to edges, which have links to surfaces
442
443 Output:
444 Each surface has a linked list of its visible spans
445 */
446 void
sw32_R_ScanEdges(void)447 sw32_R_ScanEdges (void)
448 {
449 int iv, bottom;
450 byte basespans[MAXSPANS * sizeof (espan_t) + CACHE_SIZE];
451 espan_t *basespan_p;
452 surf_t *s;
453
454 basespan_p = (espan_t *)
455 ((intptr_t) (basespans + CACHE_SIZE - 1) & ~(CACHE_SIZE - 1));
456 max_span_p = &basespan_p[MAXSPANS - r_refdef.vrect.width];
457
458 span_p = basespan_p;
459
460 // clear active edges to just the background edges around the whole screen
461 // FIXME: most of this needs to be set up only once
462 edge_head.u = r_refdef.vrect.x << 20;
463 edge_head_u_shift20 = edge_head.u >> 20;
464 edge_head.u_step = 0;
465 edge_head.prev = NULL;
466 edge_head.next = &edge_tail;
467 edge_head.surfs[0] = 0;
468 edge_head.surfs[1] = 1;
469
470 edge_tail.u = (r_refdef.vrectright << 20) + 0xFFFFF;
471 edge_tail_u_shift20 = edge_tail.u >> 20;
472 edge_tail.u_step = 0;
473 edge_tail.prev = &edge_head;
474 edge_tail.next = &edge_aftertail;
475 edge_tail.surfs[0] = 1;
476 edge_tail.surfs[1] = 0;
477
478 edge_aftertail.u = -1; // force a move
479 edge_aftertail.u_step = 0;
480 edge_aftertail.next = &edge_sentinel;
481 edge_aftertail.prev = &edge_tail;
482
483 // FIXME: do we need this now that we clamp x in r_draw.c?
484 edge_sentinel.u = 32767 << 16; // make sure nothing sorts past this
485 edge_sentinel.prev = &edge_aftertail;
486
487 // process all scan lines
488 bottom = r_refdef.vrectbottom - 1;
489
490 for (iv = r_refdef.vrect.y; iv < bottom; iv++) {
491 current_iv = iv;
492 fv = (float) iv;
493
494 // mark that the head (background start) span is pre-included
495 sw32_surfaces[1].spanstate = 1;
496
497 if (sw32_newedges[iv]) {
498 sw32_R_InsertNewEdges (sw32_newedges[iv], edge_head.next);
499 }
500
501 (*pdrawfunc) ();
502
503 // flush the span list if we can't be sure we have enough spans left
504 // for the next scan
505 if (span_p > max_span_p) {
506 VID_UnlockBuffer ();
507 S_ExtraUpdate (); // don't let sound get messed up if going slow
508 VID_LockBuffer ();
509
510 if (sw32_r_drawculledpolys)
511 R_DrawCulledPolys ();
512 else
513 sw32_D_DrawSurfaces ();
514
515 // clear the surface span pointers
516 for (s = &sw32_surfaces[1]; s < sw32_surface_p; s++)
517 s->spans = NULL;
518
519 span_p = basespan_p;
520 }
521
522 if (sw32_removeedges[iv])
523 sw32_R_RemoveEdges (sw32_removeedges[iv]);
524
525 if (edge_head.next != &edge_tail)
526 sw32_R_StepActiveU (edge_head.next);
527 }
528
529 // do the last scan (no need to step or sort or remove on the last scan)
530 current_iv = iv;
531 fv = (float) iv;
532
533 // mark that the head (background start) span is pre-included
534 sw32_surfaces[1].spanstate = 1;
535
536 if (sw32_newedges[iv])
537 sw32_R_InsertNewEdges (sw32_newedges[iv], edge_head.next);
538
539 (*pdrawfunc) ();
540
541 // draw whatever's left in the span list
542 if (sw32_r_drawculledpolys)
543 R_DrawCulledPolys ();
544 else
545 sw32_D_DrawSurfaces ();
546 }
547