• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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