1/*
2Copyright (C) 1996-1997 Id Software, Inc.
3
4This program is free software; you can redistribute it and/or
5modify it under the terms of the GNU General Public License
6as published by the Free Software Foundation; either version 2
7of the License, or (at your option) any later version.
8
9This program is distributed in the hope that it will be useful,
10but WITHOUT ANY WARRANTY; without even the implied warranty of
11MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12
13See the GNU General Public License for more details.
14
15You should have received a copy of the GNU General Public License
16along with this program; if not, write to the Free Software
17Foundation, 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
27the complex cases add new polys on most lines, so dont optimize for keeping them the same
28have multiple free span lists to try to get better coherence?
29low depth complexity -- 1 to 3 or so
30
31this breaks spans at every edge, even hidden ones (bad)
32
33have a sentinal at both ends?
34#endif
35
36
37edge_t	*auxedges;
38edge_t	*r_edges, *edge_p, *edge_max;
39
40surf_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
46edge_t	*newedges[MAXHEIGHT];
47edge_t	*removeedges[MAXHEIGHT];
48
49espan_t	*span_p, *max_span_p;
50
51int		r_currentkey;
52
53extern	int	screenwidth;
54
55int	current_iv;
56
57int	edge_head_u_shift20, edge_tail_u_shift20;
58
59static void (*pdrawfunc)(void);
60
61edge_t	edge_head;
62edge_t	edge_tail;
63edge_t	edge_aftertail;
64edge_t	edge_sentinel;
65
66float	fv;
67
68void R_GenerateSpans (void);
69void R_GenerateSpansBackward (void);
70
71void R_LeadingEdge (edge_t *edge);
72void R_LeadingEdgeBackwards (edge_t *edge);
73void R_TrailingEdge (surf_t *surf, edge_t *edge);
74
75
76//=============================================================================
77
78
79/*
80==============
81R_DrawCulledPolys
82==============
83*/
84void 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==============
124R_BeginEdgeFrame
125==============
126*/
127void 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==============
165R_InsertNewEdges
166
167Adds the edges in the linked list edgestoadd, adding them to the edges in the
168linked 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
169sentinel at the end (actually, this is the active edge table starting at
170edge_head.next).
171==============
172*/
173void R_InsertNewEdges (edge_t *edgestoadd, edge_t *edgelist)
174{
175	edge_t	*next_edge;
176
177	do
178	{
179		next_edge = edgestoadd->next;
180edgesearch:
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
196addedge:
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==============
211R_RemoveEdges
212==============
213*/
214void 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==============
231R_StepActiveU
232==============
233*/
234void R_StepActiveU (edge_t *pedge)
235{
236	edge_t		*pnext_edge, *pwedge;
237
238	while (1)
239	{
240nextedge:
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
263pushback:
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==============
299R_CleanupSpan
300==============
301*/
302void 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==============
333R_LeadingEdgeBackwards
334==============
335*/
336void 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
364continue_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
384newtop:
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
401gotposition:
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==============
413R_TrailingEdge
414==============
415*/
416void 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==============
457R_LeadingEdge
458==============
459*/
460void 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
513continue_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
555newtop:
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
572gotposition:
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==============
585R_GenerateSpans
586==============
587*/
588void 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==============
624R_GenerateSpansBackward
625==============
626*/
627void 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==============
653R_ScanEdges
654
655Input:
656newedges[] array
657	this has links to edges, which have links to surfaces
658
659Output:
660Each surface has a linked list of its visible spans
661==============
662*/
663void 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