1 /*
2 Copyright (C) 1996-1997 Id Software, Inc.
3
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License
6 as published by the Free Software Foundation; either version 2
7 of the License, or (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12
13 See the GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
18
19 */
20 // r_edge.c
21
22 #include "quakedef.h"
23 #include "r_local.h"
24
25 #if 0
26 // FIXME
27 the complex cases add new polys on most lines, so dont optimize for keeping them the same
28 have multiple free span lists to try to get better coherence?
29 low depth complexity -- 1 to 3 or so
30
31 this breaks spans at every edge, even hidden ones (bad)
32
33 have a sentinal at both ends?
34 #endif
35
36
37 edge_t *auxedges;
38 edge_t *r_edges, *edge_p, *edge_max;
39
40 surf_t *surfaces, *surface_p, *surf_max;
41
42 // surfaces are generated in back to front order by the bsp, so if a surf
43 // pointer is greater than another one, it should be drawn in front
44 // surfaces[1] is the background, and is used as the active surface stack
45
46 edge_t *newedges[MAXHEIGHT];
47 edge_t *removeedges[MAXHEIGHT];
48
49 espan_t *span_p, *max_span_p;
50
51 int r_currentkey;
52
53 extern int screenwidth;
54
55 int current_iv;
56
57 int edge_head_u_shift20, edge_tail_u_shift20;
58
59 static void (*pdrawfunc)(void);
60
61 edge_t edge_head;
62 edge_t edge_tail;
63 edge_t edge_aftertail;
64 edge_t edge_sentinel;
65
66 float fv;
67
68 void R_GenerateSpans (void);
69 void R_GenerateSpansBackward (void);
70
71 void R_LeadingEdge (edge_t *edge);
72 void R_LeadingEdgeBackwards (edge_t *edge);
73 void R_TrailingEdge (surf_t *surf, edge_t *edge);
74
75
76 //=============================================================================
77
78
79 /*
80 ==============
81 R_DrawCulledPolys
82 ==============
83 */
R_DrawCulledPolys(void)84 void R_DrawCulledPolys (void)
85 {
86 surf_t *s;
87 msurface_t *pface;
88
89 currententity = &r_worldentity;
90
91 if (r_worldpolysbacktofront)
92 {
93 for (s=surface_p-1 ; s>&surfaces[1] ; s--)
94 {
95 if (!s->spans)
96 continue;
97
98 if (!(s->flags & SURF_DRAWBACKGROUND))
99 {
100 pface = (msurface_t *)s->data;
101 R_RenderPoly (pface, 15);
102 }
103 }
104 }
105 else
106 {
107 for (s = &surfaces[1] ; s<surface_p ; s++)
108 {
109 if (!s->spans)
110 continue;
111
112 if (!(s->flags & SURF_DRAWBACKGROUND))
113 {
114 pface = (msurface_t *)s->data;
115 R_RenderPoly (pface, 15);
116 }
117 }
118 }
119 }
120
121
122 /*
123 ==============
124 R_BeginEdgeFrame
125 ==============
126 */
R_BeginEdgeFrame(void)127 void R_BeginEdgeFrame (void)
128 {
129 int v;
130
131 edge_p = r_edges;
132 edge_max = &r_edges[r_numallocatededges];
133
134 surface_p = &surfaces[2]; // background is surface 1,
135 // surface 0 is a dummy
136 surfaces[1].spans = NULL; // no background spans yet
137 surfaces[1].flags = SURF_DRAWBACKGROUND;
138
139 // put the background behind everything in the world
140 if (r_draworder.value)
141 {
142 pdrawfunc = R_GenerateSpansBackward;
143 surfaces[1].key = 0;
144 r_currentkey = 1;
145 }
146 else
147 {
148 pdrawfunc = R_GenerateSpans;
149 surfaces[1].key = 0x7FFFFFFF;
150 r_currentkey = 0;
151 }
152
153 // FIXME: set with memset
154 for (v=r_refdef.vrect.y ; v<r_refdef.vrectbottom ; v++)
155 {
156 newedges[v] = removeedges[v] = NULL;
157 }
158 }
159
160
161 #if !id386
162
163 /*
164 ==============
165 R_InsertNewEdges
166
167 Adds the edges in the linked list edgestoadd, adding them to the edges in the
168 linked list edgelist. edgestoadd is assumed to be sorted on u, and non-empty (this is actually newedges[v]). edgelist is assumed to be sorted on u, with a
169 sentinel at the end (actually, this is the active edge table starting at
170 edge_head.next).
171 ==============
172 */
R_InsertNewEdges(edge_t * edgestoadd,edge_t * edgelist)173 void R_InsertNewEdges (edge_t *edgestoadd, edge_t *edgelist)
174 {
175 edge_t *next_edge;
176
177 do
178 {
179 next_edge = edgestoadd->next;
180 edgesearch:
181 if (edgelist->u >= edgestoadd->u)
182 goto addedge;
183 edgelist=edgelist->next;
184 if (edgelist->u >= edgestoadd->u)
185 goto addedge;
186 edgelist=edgelist->next;
187 if (edgelist->u >= edgestoadd->u)
188 goto addedge;
189 edgelist=edgelist->next;
190 if (edgelist->u >= edgestoadd->u)
191 goto addedge;
192 edgelist=edgelist->next;
193 goto edgesearch;
194
195 // insert edgestoadd before edgelist
196 addedge:
197 edgestoadd->next = edgelist;
198 edgestoadd->prev = edgelist->prev;
199 edgelist->prev->next = edgestoadd;
200 edgelist->prev = edgestoadd;
201 } while ((edgestoadd = next_edge) != NULL);
202 }
203
204 #endif // !id386
205
206
207 #if !id386
208
209 /*
210 ==============
211 R_RemoveEdges
212 ==============
213 */
R_RemoveEdges(edge_t * pedge)214 void R_RemoveEdges (edge_t *pedge)
215 {
216
217 do
218 {
219 pedge->next->prev = pedge->prev;
220 pedge->prev->next = pedge->next;
221 } while ((pedge = pedge->nextremove) != NULL);
222 }
223
224 #endif // !id386
225
226
227 #if !id386
228
229 /*
230 ==============
231 R_StepActiveU
232 ==============
233 */
R_StepActiveU(edge_t * pedge)234 void R_StepActiveU (edge_t *pedge)
235 {
236 edge_t *pnext_edge, *pwedge;
237
238 while (1)
239 {
240 nextedge:
241 pedge->u += pedge->u_step;
242 if (pedge->u < pedge->prev->u)
243 goto pushback;
244 pedge = pedge->next;
245
246 pedge->u += pedge->u_step;
247 if (pedge->u < pedge->prev->u)
248 goto pushback;
249 pedge = pedge->next;
250
251 pedge->u += pedge->u_step;
252 if (pedge->u < pedge->prev->u)
253 goto pushback;
254 pedge = pedge->next;
255
256 pedge->u += pedge->u_step;
257 if (pedge->u < pedge->prev->u)
258 goto pushback;
259 pedge = pedge->next;
260
261 goto nextedge;
262
263 pushback:
264 if (pedge == &edge_aftertail)
265 return;
266
267 // push it back to keep it sorted
268 pnext_edge = pedge->next;
269
270 // pull the edge out of the edge list
271 pedge->next->prev = pedge->prev;
272 pedge->prev->next = pedge->next;
273
274 // find out where the edge goes in the edge list
275 pwedge = pedge->prev->prev;
276
277 while (pwedge->u > pedge->u)
278 {
279 pwedge = pwedge->prev;
280 }
281
282 // put the edge back into the edge list
283 pedge->next = pwedge->next;
284 pedge->prev = pwedge;
285 pedge->next->prev = pedge;
286 pwedge->next = pedge;
287
288 pedge = pnext_edge;
289 if (pedge == &edge_tail)
290 return;
291 }
292 }
293
294 #endif // !id386
295
296
297 /*
298 ==============
299 R_CleanupSpan
300 ==============
301 */
R_CleanupSpan()302 void R_CleanupSpan ()
303 {
304 surf_t *surf;
305 int iu;
306 espan_t *span;
307
308 // now that we've reached the right edge of the screen, we're done with any
309 // unfinished surfaces, so emit a span for whatever's on top
310 surf = surfaces[1].next;
311 iu = edge_tail_u_shift20;
312 if (iu > surf->last_u)
313 {
314 span = span_p++;
315 span->u = surf->last_u;
316 span->count = iu - span->u;
317 span->v = current_iv;
318 span->pnext = surf->spans;
319 surf->spans = span;
320 }
321
322 // reset spanstate for all surfaces in the surface stack
323 do
324 {
325 surf->spanstate = 0;
326 surf = surf->next;
327 } while (surf != &surfaces[1]);
328 }
329
330
331 /*
332 ==============
333 R_LeadingEdgeBackwards
334 ==============
335 */
R_LeadingEdgeBackwards(edge_t * edge)336 void R_LeadingEdgeBackwards (edge_t *edge)
337 {
338 espan_t *span;
339 surf_t *surf, *surf2;
340 int iu;
341
342 // it's adding a new surface in, so find the correct place
343 surf = &surfaces[edge->surfs[1]];
344
345 // don't start a span if this is an inverted span, with the end
346 // edge preceding the start edge (that is, we've already seen the
347 // end edge)
348 if (++surf->spanstate == 1)
349 {
350 surf2 = surfaces[1].next;
351
352 if (surf->key > surf2->key)
353 goto newtop;
354
355 // if it's two surfaces on the same plane, the one that's already
356 // active is in front, so keep going unless it's a bmodel
357 if (surf->insubmodel && (surf->key == surf2->key))
358 {
359 // must be two bmodels in the same leaf; don't care, because they'll
360 // never be farthest anyway
361 goto newtop;
362 }
363
364 continue_search:
365
366 do
367 {
368 surf2 = surf2->next;
369 } while (surf->key < surf2->key);
370
371 if (surf->key == surf2->key)
372 {
373 // if it's two surfaces on the same plane, the one that's already
374 // active is in front, so keep going unless it's a bmodel
375 if (!surf->insubmodel)
376 goto continue_search;
377
378 // must be two bmodels in the same leaf; don't care which is really
379 // in front, because they'll never be farthest anyway
380 }
381
382 goto gotposition;
383
384 newtop:
385 // emit a span (obscures current top)
386 iu = edge->u >> 20;
387
388 if (iu > surf2->last_u)
389 {
390 span = span_p++;
391 span->u = surf2->last_u;
392 span->count = iu - span->u;
393 span->v = current_iv;
394 span->pnext = surf2->spans;
395 surf2->spans = span;
396 }
397
398 // set last_u on the new span
399 surf->last_u = iu;
400
401 gotposition:
402 // insert before surf2
403 surf->next = surf2;
404 surf->prev = surf2->prev;
405 surf2->prev->next = surf;
406 surf2->prev = surf;
407 }
408 }
409
410
411 /*
412 ==============
413 R_TrailingEdge
414 ==============
415 */
R_TrailingEdge(surf_t * surf,edge_t * edge)416 void R_TrailingEdge (surf_t *surf, edge_t *edge)
417 {
418 espan_t *span;
419 int iu;
420
421 // don't generate a span if this is an inverted span, with the end
422 // edge preceding the start edge (that is, we haven't seen the
423 // start edge yet)
424 if (--surf->spanstate == 0)
425 {
426 if (surf->insubmodel)
427 r_bmodelactive--;
428
429 if (surf == surfaces[1].next)
430 {
431 // emit a span (current top going away)
432 iu = edge->u >> 20;
433 if (iu > surf->last_u)
434 {
435 span = span_p++;
436 span->u = surf->last_u;
437 span->count = iu - span->u;
438 span->v = current_iv;
439 span->pnext = surf->spans;
440 surf->spans = span;
441 }
442
443 // set last_u on the surface below
444 surf->next->last_u = iu;
445 }
446
447 surf->prev->next = surf->next;
448 surf->next->prev = surf->prev;
449 }
450 }
451
452
453 #if !id386
454
455 /*
456 ==============
457 R_LeadingEdge
458 ==============
459 */
R_LeadingEdge(edge_t * edge)460 void R_LeadingEdge (edge_t *edge)
461 {
462 espan_t *span;
463 surf_t *surf, *surf2;
464 int iu;
465 double fu, newzi, testzi, newzitop, newzibottom;
466
467 if (edge->surfs[1])
468 {
469 // it's adding a new surface in, so find the correct place
470 surf = &surfaces[edge->surfs[1]];
471
472 // don't start a span if this is an inverted span, with the end
473 // edge preceding the start edge (that is, we've already seen the
474 // end edge)
475 if (++surf->spanstate == 1)
476 {
477 if (surf->insubmodel)
478 r_bmodelactive++;
479
480 surf2 = surfaces[1].next;
481
482 if (surf->key < surf2->key)
483 goto newtop;
484
485 // if it's two surfaces on the same plane, the one that's already
486 // active is in front, so keep going unless it's a bmodel
487 if (surf->insubmodel && (surf->key == surf2->key))
488 {
489 // must be two bmodels in the same leaf; sort on 1/z
490 fu = (float)(edge->u - 0xFFFFF) * (1.0 / 0x100000);
491 newzi = surf->d_ziorigin + fv*surf->d_zistepv +
492 fu*surf->d_zistepu;
493 newzibottom = newzi * 0.99;
494
495 testzi = surf2->d_ziorigin + fv*surf2->d_zistepv +
496 fu*surf2->d_zistepu;
497
498 if (newzibottom >= testzi)
499 {
500 goto newtop;
501 }
502
503 newzitop = newzi * 1.01;
504 if (newzitop >= testzi)
505 {
506 if (surf->d_zistepu >= surf2->d_zistepu)
507 {
508 goto newtop;
509 }
510 }
511 }
512
513 continue_search:
514
515 do
516 {
517 surf2 = surf2->next;
518 } while (surf->key > surf2->key);
519
520 if (surf->key == surf2->key)
521 {
522 // if it's two surfaces on the same plane, the one that's already
523 // active is in front, so keep going unless it's a bmodel
524 if (!surf->insubmodel)
525 goto continue_search;
526
527 // must be two bmodels in the same leaf; sort on 1/z
528 fu = (float)(edge->u - 0xFFFFF) * (1.0 / 0x100000);
529 newzi = surf->d_ziorigin + fv*surf->d_zistepv +
530 fu*surf->d_zistepu;
531 newzibottom = newzi * 0.99;
532
533 testzi = surf2->d_ziorigin + fv*surf2->d_zistepv +
534 fu*surf2->d_zistepu;
535
536 if (newzibottom >= testzi)
537 {
538 goto gotposition;
539 }
540
541 newzitop = newzi * 1.01;
542 if (newzitop >= testzi)
543 {
544 if (surf->d_zistepu >= surf2->d_zistepu)
545 {
546 goto gotposition;
547 }
548 }
549
550 goto continue_search;
551 }
552
553 goto gotposition;
554
555 newtop:
556 // emit a span (obscures current top)
557 iu = edge->u >> 20;
558
559 if (iu > surf2->last_u)
560 {
561 span = span_p++;
562 span->u = surf2->last_u;
563 span->count = iu - span->u;
564 span->v = current_iv;
565 span->pnext = surf2->spans;
566 surf2->spans = span;
567 }
568
569 // set last_u on the new span
570 surf->last_u = iu;
571
572 gotposition:
573 // insert before surf2
574 surf->next = surf2;
575 surf->prev = surf2->prev;
576 surf2->prev->next = surf;
577 surf2->prev = surf;
578 }
579 }
580 }
581
582
583 /*
584 ==============
585 R_GenerateSpans
586 ==============
587 */
R_GenerateSpans(void)588 void R_GenerateSpans (void)
589 {
590 edge_t *edge;
591 surf_t *surf;
592
593 r_bmodelactive = 0;
594
595 // clear active surfaces to just the background surface
596 surfaces[1].next = surfaces[1].prev = &surfaces[1];
597 surfaces[1].last_u = edge_head_u_shift20;
598
599 // generate spans
600 for (edge=edge_head.next ; edge != &edge_tail; edge=edge->next)
601 {
602 if (edge->surfs[0])
603 {
604 // it has a left surface, so a surface is going away for this span
605 surf = &surfaces[edge->surfs[0]];
606
607 R_TrailingEdge (surf, edge);
608
609 if (!edge->surfs[1])
610 continue;
611 }
612
613 R_LeadingEdge (edge);
614 }
615
616 R_CleanupSpan ();
617 }
618
619 #endif // !id386
620
621
622 /*
623 ==============
624 R_GenerateSpansBackward
625 ==============
626 */
R_GenerateSpansBackward(void)627 void R_GenerateSpansBackward (void)
628 {
629 edge_t *edge;
630
631 r_bmodelactive = 0;
632
633 // clear active surfaces to just the background surface
634 surfaces[1].next = surfaces[1].prev = &surfaces[1];
635 surfaces[1].last_u = edge_head_u_shift20;
636
637 // generate spans
638 for (edge=edge_head.next ; edge != &edge_tail; edge=edge->next)
639 {
640 if (edge->surfs[0])
641 R_TrailingEdge (&surfaces[edge->surfs[0]], edge);
642
643 if (edge->surfs[1])
644 R_LeadingEdgeBackwards (edge);
645 }
646
647 R_CleanupSpan ();
648 }
649
650
651 /*
652 ==============
653 R_ScanEdges
654
655 Input:
656 newedges[] array
657 this has links to edges, which have links to surfaces
658
659 Output:
660 Each surface has a linked list of its visible spans
661 ==============
662 */
R_ScanEdges(void)663 void R_ScanEdges (void)
664 {
665 int iv, bottom;
666 byte basespans[MAXSPANS*sizeof(espan_t)+CACHE_SIZE];
667 espan_t *basespan_p;
668 surf_t *s;
669
670 basespan_p = (espan_t *)
671 ((long)(basespans + CACHE_SIZE - 1) & ~(CACHE_SIZE - 1));
672 max_span_p = &basespan_p[MAXSPANS - r_refdef.vrect.width];
673
674 span_p = basespan_p;
675
676 // clear active edges to just the background edges around the whole screen
677 // FIXME: most of this only needs to be set up once
678 edge_head.u = r_refdef.vrect.x << 20;
679 edge_head_u_shift20 = edge_head.u >> 20;
680 edge_head.u_step = 0;
681 edge_head.prev = NULL;
682 edge_head.next = &edge_tail;
683 edge_head.surfs[0] = 0;
684 edge_head.surfs[1] = 1;
685
686 edge_tail.u = (r_refdef.vrectright << 20) + 0xFFFFF;
687 edge_tail_u_shift20 = edge_tail.u >> 20;
688 edge_tail.u_step = 0;
689 edge_tail.prev = &edge_head;
690 edge_tail.next = &edge_aftertail;
691 edge_tail.surfs[0] = 1;
692 edge_tail.surfs[1] = 0;
693
694 edge_aftertail.u = -1; // force a move
695 edge_aftertail.u_step = 0;
696 edge_aftertail.next = &edge_sentinel;
697 edge_aftertail.prev = &edge_tail;
698
699 // FIXME: do we need this now that we clamp x in r_draw.c?
700 edge_sentinel.u = 2000 << 24; // make sure nothing sorts past this
701 edge_sentinel.prev = &edge_aftertail;
702
703 //
704 // process all scan lines
705 //
706 bottom = r_refdef.vrectbottom - 1;
707
708 for (iv=r_refdef.vrect.y ; iv<bottom ; iv++)
709 {
710 current_iv = iv;
711 fv = (float)iv;
712
713 // mark that the head (background start) span is pre-included
714 surfaces[1].spanstate = 1;
715
716 if (newedges[iv])
717 {
718 R_InsertNewEdges (newedges[iv], edge_head.next);
719 }
720
721 (*pdrawfunc) ();
722
723 // flush the span list if we can't be sure we have enough spans left for
724 // the next scan
725 if (span_p > max_span_p)
726 {
727 VID_UnlockBuffer ();
728 S_ExtraUpdate (); // don't let sound get messed up if going slow
729 VID_LockBuffer ();
730
731 if (r_drawculledpolys)
732 R_DrawCulledPolys ();
733 else
734 D_DrawSurfaces ();
735
736 // clear the surface span pointers
737 for (s = &surfaces[1] ; s<surface_p ; s++)
738 s->spans = NULL;
739
740 span_p = basespan_p;
741 }
742
743 if (removeedges[iv])
744 R_RemoveEdges (removeedges[iv]);
745
746 if (edge_head.next != &edge_tail)
747 R_StepActiveU (edge_head.next);
748 }
749
750 // do the last scan (no need to step or sort or remove on the last scan)
751
752 current_iv = iv;
753 fv = (float)iv;
754
755 // mark that the head (background start) span is pre-included
756 surfaces[1].spanstate = 1;
757
758 if (newedges[iv])
759 R_InsertNewEdges (newedges[iv], edge_head.next);
760
761 (*pdrawfunc) ();
762
763 // draw whatever's left in the span list
764 if (r_drawculledpolys)
765 R_DrawCulledPolys ();
766 else
767 D_DrawSurfaces ();
768 }
769
770
771