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