![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to r_edge.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Quake] / quakeworld / client|
Return to r_edge.c CVS log | Up to [Quake] / quakeworld / client |
1.1 root 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: */
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: */
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: */
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: */
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: */
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: */
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: */
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: */
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: */
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: */
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: */
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: */
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:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.