Quake: attempt 2duke3d

Change-Id: I4285036e967d7f0722802d43cf2096c808ca5799

1 files changed, 774 insertions, 0 deletions

diff --git a/apps/plugins/sdl/progs/quake/r_edge.c b/apps/plugins/sdl/progs/quake/r_edge.c
new file mode 100644
index 0000000..d434799
--- /dev/null
+++ b/apps/plugins/sdl/progs/quake/r_edge.c
@@ -0,0 +1,774 @@
+/*
+Copyright (C) 1996-1997 Id Software, Inc.
+
+This program is free software; you can redistribute it and/or
+modify it under the terms of the GNU General Public License
+as published by the Free Software Foundation; either version 2
+of the License, or (at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
+
+See the GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+
+*/
+// r_edge.c
+
+#include "quakedef.h"
+#include "r_local.h"
+
+#if 0
+// FIXME
+the complex cases add new polys on most lines, so dont optimize for keeping them the same
+have multiple free span lists to try to get better coherence?
+low depth complexity -- 1 to 3 or so
+
+this breaks spans at every edge, even hidden ones (bad)
+
+have a sentinal at both ends?
+#endif
+
+
+edge_t	*auxedges;
+edge_t	*r_edges, *edge_p, *edge_max;
+
+surf_t	*surfaces, *surface_p, *surf_max;
+
+// surfaces are generated in back to front order by the bsp, so if a surf
+// pointer is greater than another one, it should be drawn in front
+// surfaces[1] is the background, and is used as the active surface stack
+
+edge_t	*newedges[MAXHEIGHT];
+edge_t	*removeedges[MAXHEIGHT];
+
+espan_t	*span_p, *max_span_p;
+
+int		r_currentkey;
+
+extern	int	screenwidth;
+
+int	current_iv;
+
+int	edge_head_u_shift20, edge_tail_u_shift20;
+
+static void (*pdrawfunc)(void);
+
+edge_t	edge_head;
+edge_t	edge_tail;
+edge_t	edge_aftertail;
+edge_t	edge_sentinel;
+
+float	fv;
+
+void R_GenerateSpans (void);
+void R_GenerateSpansBackward (void);
+
+void R_LeadingEdge (edge_t *edge);
+void R_LeadingEdgeBackwards (edge_t *edge);
+void R_TrailingEdge (surf_t *surf, edge_t *edge);
+
+
+//=============================================================================
+
+
+/*
+==============
+R_DrawCulledPolys
+==============
+*/
+void R_DrawCulledPolys (void)
+{
+	surf_t			*s;
+	msurface_t		*pface;
+
+	currententity = &cl_entities[0];
+
+	if (r_worldpolysbacktofront)
+	{
+		for (s=surface_p-1 ; s>&surfaces[1] ; s--)
+		{
+			if (!s->spans)
+				continue;
+
+			if (!(s->flags & SURF_DRAWBACKGROUND))
+			{
+				pface = (msurface_t *)s->data;
+				R_RenderPoly (pface, 15);
+			}
+		}
+	}
+	else
+	{
+		for (s = &surfaces[1] ; s<surface_p ; s++)
+		{
+			if (!s->spans)
+				continue;
+
+			if (!(s->flags & SURF_DRAWBACKGROUND))
+			{
+				pface = (msurface_t *)s->data;
+				R_RenderPoly (pface, 15);
+			}
+		}
+	}
+}
+
+
+/*
+==============
+R_BeginEdgeFrame
+==============
+*/
+void R_BeginEdgeFrame (void)
+{
+	int		v;
+
+	edge_p = r_edges;
+	edge_max = &r_edges[r_numallocatededges];
+
+	surface_p = &surfaces[2];	// background is surface 1,
+								//  surface 0 is a dummy
+	surfaces[1].spans = NULL;	// no background spans yet
+	surfaces[1].flags = SURF_DRAWBACKGROUND;
+
+// put the background behind everything in the world
+	if (r_draworder.value)
+	{
+		pdrawfunc = R_GenerateSpansBackward;
+		surfaces[1].key = 0;
+		r_currentkey = 1;
+	}
+	else
+	{
+		pdrawfunc = R_GenerateSpans;
+		surfaces[1].key = 0x7FFFFFFF;
+		r_currentkey = 0;
+	}
+
+// FIXME: set with memset
+	for (v=r_refdef.vrect.y ; v<r_refdef.vrectbottom ; v++)
+	{
+		newedges[v] = removeedges[v] = NULL;
+	}
+}
+
+
+#if	!id386
+
+/*
+==============
+R_InsertNewEdges
+
+Adds the edges in the linked list edgestoadd, adding them to the edges in the
+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
+sentinel at the end (actually, this is the active edge table starting at
+edge_head.next).
+==============
+*/
+void R_InsertNewEdges (edge_t *edgestoadd, edge_t *edgelist)
+{
+	edge_t	*next_edge;
+
+	do
+	{
+		next_edge = edgestoadd->next;
+edgesearch:
+		if (edgelist->u >= edgestoadd->u)
+			goto addedge;
+		edgelist=edgelist->next;
+		if (edgelist->u >= edgestoadd->u)
+			goto addedge;
+		edgelist=edgelist->next;
+		if (edgelist->u >= edgestoadd->u)
+			goto addedge;
+		edgelist=edgelist->next;
+		if (edgelist->u >= edgestoadd->u)
+			goto addedge;
+		edgelist=edgelist->next;
+		goto edgesearch;
+
+	// insert edgestoadd before edgelist
+addedge:
+		edgestoadd->next = edgelist;
+		edgestoadd->prev = edgelist->prev;
+		edgelist->prev->next = edgestoadd;
+		edgelist->prev = edgestoadd;
+	} while ((edgestoadd = next_edge) != NULL);
+}
+
+#endif	// !id386
+	
+
+#if	!id386
+
+/*
+==============
+R_RemoveEdges
+==============
+*/
+void R_RemoveEdges (edge_t *pedge)
+{
+
+	do
+	{
+		pedge->next->prev = pedge->prev;
+		pedge->prev->next = pedge->next;
+	} while ((pedge = pedge->nextremove) != NULL);
+}
+
+#endif	// !id386
+
+
+#if	!id386
+
+/*
+==============
+R_StepActiveU
+==============
+*/
+void R_StepActiveU (edge_t *pedge)
+{
+	edge_t		*pnext_edge, *pwedge;
+
+	while (1)
+	{
+nextedge:
+		pedge->u += pedge->u_step;
+		if (pedge->u < pedge->prev->u)
+			goto pushback;
+		pedge = pedge->next;
+			
+		pedge->u += pedge->u_step;
+		if (pedge->u < pedge->prev->u)
+			goto pushback;
+		pedge = pedge->next;
+			
+		pedge->u += pedge->u_step;
+		if (pedge->u < pedge->prev->u)
+			goto pushback;
+		pedge = pedge->next;
+			
+		pedge->u += pedge->u_step;
+		if (pedge->u < pedge->prev->u)
+			goto pushback;
+		pedge = pedge->next;
+			
+		goto nextedge;		
+		
+pushback:
+		if (pedge == &edge_aftertail)
+			return;
+			
+	// push it back to keep it sorted		
+		pnext_edge = pedge->next;
+
+	// pull the edge out of the edge list
+		pedge->next->prev = pedge->prev;
+		pedge->prev->next = pedge->next;
+
+	// find out where the edge goes in the edge list
+		pwedge = pedge->prev->prev;
+
+		while (pwedge->u > pedge->u)
+		{
+			pwedge = pwedge->prev;
+		}
+
+	// put the edge back into the edge list
+		pedge->next = pwedge->next;
+		pedge->prev = pwedge;
+		pedge->next->prev = pedge;
+		pwedge->next = pedge;
+
+		pedge = pnext_edge;
+		if (pedge == &edge_tail)
+			return;
+	}
+}
+
+#endif	// !id386
+
+
+/*
+==============
+R_CleanupSpan
+==============
+*/
+void R_CleanupSpan ()
+{
+	surf_t	*surf;
+	int		iu;
+	espan_t	*span;
+
+// now that we've reached the right edge of the screen, we're done with any
+// unfinished surfaces, so emit a span for whatever's on top
+	surf = surfaces[1].next;
+	iu = edge_tail_u_shift20;
+	if (iu > surf->last_u)
+	{
+		span = span_p++;
+		span->u = surf->last_u;
+		span->count = iu - span->u;
+		span->v = current_iv;
+		span->pnext = surf->spans;
+		surf->spans = span;
+	}
+
+// reset spanstate for all surfaces in the surface stack
+	do
+	{
+		surf->spanstate = 0;
+		surf = surf->next;
+	} while (surf != &surfaces[1]);
+}
+
+
+/*
+==============
+R_LeadingEdgeBackwards
+==============
+*/
+void R_LeadingEdgeBackwards (edge_t *edge)
+{
+	espan_t			*span;
+	surf_t			*surf, *surf2;
+	int				iu;
+
+// it's adding a new surface in, so find the correct place
+	surf = &surfaces[edge->surfs[1]];
+
+// don't start a span if this is an inverted span, with the end
+// edge preceding the start edge (that is, we've already seen the
+// end edge)
+	if (++surf->spanstate == 1)
+	{
+		surf2 = surfaces[1].next;
+
+		if (surf->key > surf2->key)
+			goto newtop;
+
+	// if it's two surfaces on the same plane, the one that's already
+	// active is in front, so keep going unless it's a bmodel
+		if (surf->insubmodel && (surf->key == surf2->key))
+		{
+		// must be two bmodels in the same leaf; don't care, because they'll
+		// never be farthest anyway
+			goto newtop;
+		}
+
+continue_search:
+
+		do
+		{
+			surf2 = surf2->next;
+		} while (surf->key < surf2->key);
+
+		if (surf->key == surf2->key)
+		{
+		// if it's two surfaces on the same plane, the one that's already
+		// active is in front, so keep going unless it's a bmodel
+			if (!surf->insubmodel)
+				goto continue_search;
+
+		// must be two bmodels in the same leaf; don't care which is really
+		// in front, because they'll never be farthest anyway
+		}
+
+		goto gotposition;
+
+newtop:
+	// emit a span (obscures current top)
+		iu = edge->u >> 20;
+
+		if (iu > surf2->last_u)
+		{
+			span = span_p++;
+			span->u = surf2->last_u;
+			span->count = iu - span->u;
+			span->v = current_iv;
+			span->pnext = surf2->spans;
+			surf2->spans = span;
+		}
+
+		// set last_u on the new span
+		surf->last_u = iu;
+				
+gotposition:
+	// insert before surf2
+		surf->next = surf2;
+		surf->prev = surf2->prev;
+		surf2->prev->next = surf;
+		surf2->prev = surf;
+	}
+}
+
+
+/*
+==============
+R_TrailingEdge
+==============
+*/
+void R_TrailingEdge (surf_t *surf, edge_t *edge)
+{
+	espan_t			*span;
+	int				iu;
+
+// don't generate a span if this is an inverted span, with the end
+// edge preceding the start edge (that is, we haven't seen the
+// start edge yet)
+	if (--surf->spanstate == 0)
+	{
+		if (surf->insubmodel)
+			r_bmodelactive--;
+
+		if (surf == surfaces[1].next)
+		{
+		// emit a span (current top going away)
+			iu = edge->u >> 20;
+			if (iu > surf->last_u)
+			{
+				span = span_p++;
+				span->u = surf->last_u;
+				span->count = iu - span->u;
+				span->v = current_iv;
+				span->pnext = surf->spans;
+				surf->spans = span;
+			}
+
+		// set last_u on the surface below
+			surf->next->last_u = iu;
+		}
+
+		surf->prev->next = surf->next;
+		surf->next->prev = surf->prev;
+	}
+}
+
+
+#if	!id386
+
+/*
+==============
+R_LeadingEdge
+==============
+*/
+void R_LeadingEdge (edge_t *edge)
+{
+	espan_t			*span;
+	surf_t			*surf, *surf2;
+	int				iu;
+	double			fu, newzi, testzi, newzitop, newzibottom;
+
+	if (edge->surfs[1])
+	{
+	// it's adding a new surface in, so find the correct place
+		surf = &surfaces[edge->surfs[1]];
+
+	// don't start a span if this is an inverted span, with the end
+	// edge preceding the start edge (that is, we've already seen the
+	// end edge)
+		if (++surf->spanstate == 1)
+		{
+			if (surf->insubmodel)
+				r_bmodelactive++;
+
+			surf2 = surfaces[1].next;
+
+			if (surf->key < surf2->key)
+				goto newtop;
+
+		// if it's two surfaces on the same plane, the one that's already
+		// active is in front, so keep going unless it's a bmodel
+			if (surf->insubmodel && (surf->key == surf2->key))
+			{
+			// must be two bmodels in the same leaf; sort on 1/z
+				fu = (float)(edge->u - 0xFFFFF) * (1.0 / 0x100000);
+				newzi = surf->d_ziorigin + fv*surf->d_zistepv +
+						fu*surf->d_zistepu;
+				newzibottom = newzi * 0.99;
+
+				testzi = surf2->d_ziorigin + fv*surf2->d_zistepv +
+						fu*surf2->d_zistepu;
+
+				if (newzibottom >= testzi)
+				{
+					goto newtop;
+				}
+
+				newzitop = newzi * 1.01;
+				if (newzitop >= testzi)
+				{
+					if (surf->d_zistepu >= surf2->d_zistepu)
+					{
+						goto newtop;
+					}
+				}
+			}
+
+continue_search:
+
+			do
+			{
+				surf2 = surf2->next;
+			} while (surf->key > surf2->key);
+
+			if (surf->key == surf2->key)
+			{
+			// if it's two surfaces on the same plane, the one that's already
+			// active is in front, so keep going unless it's a bmodel
+				if (!surf->insubmodel)
+					goto continue_search;
+
+			// must be two bmodels in the same leaf; sort on 1/z
+				fu = (float)(edge->u - 0xFFFFF) * (1.0 / 0x100000);
+				newzi = surf->d_ziorigin + fv*surf->d_zistepv +
+						fu*surf->d_zistepu;
+				newzibottom = newzi * 0.99;
+
+				testzi = surf2->d_ziorigin + fv*surf2->d_zistepv +
+						fu*surf2->d_zistepu;
+
+				if (newzibottom >= testzi)
+				{
+					goto gotposition;
+				}
+
+				newzitop = newzi * 1.01;
+				if (newzitop >= testzi)
+				{
+					if (surf->d_zistepu >= surf2->d_zistepu)
+					{
+						goto gotposition;
+					}
+				}
+
+				goto continue_search;
+			}
+
+			goto gotposition;
+
+newtop:
+		// emit a span (obscures current top)
+			iu = edge->u >> 20;
+
+			if (iu > surf2->last_u)
+			{
+				span = span_p++;
+				span->u = surf2->last_u;
+				span->count = iu - span->u;
+				span->v = current_iv;
+				span->pnext = surf2->spans;
+				surf2->spans = span;
+			}
+
+			// set last_u on the new span
+			surf->last_u = iu;
+				
+gotposition:
+		// insert before surf2
+			surf->next = surf2;
+			surf->prev = surf2->prev;
+			surf2->prev->next = surf;
+			surf2->prev = surf;
+		}
+	}
+}
+
+
+/*
+==============
+R_GenerateSpans
+==============
+*/
+void R_GenerateSpans (void)
+{
+	edge_t			*edge;
+	surf_t			*surf;
+
+	r_bmodelactive = 0;
+
+// clear active surfaces to just the background surface
+	surfaces[1].next = surfaces[1].prev = &surfaces[1];
+	surfaces[1].last_u = edge_head_u_shift20;
+
+// generate spans
+	for (edge=edge_head.next ; edge != &edge_tail; edge=edge->next)
+	{			
+		if (edge->surfs[0])
+		{
+		// it has a left surface, so a surface is going away for this span
+			surf = &surfaces[edge->surfs[0]];
+
+			R_TrailingEdge (surf, edge);
+
+			if (!edge->surfs[1])
+				continue;
+		}
+
+		R_LeadingEdge (edge);
+	}
+
+	R_CleanupSpan ();
+}
+
+#endif	// !id386
+
+
+/*
+==============
+R_GenerateSpansBackward
+==============
+*/
+void R_GenerateSpansBackward (void)
+{
+	edge_t			*edge;
+
+	r_bmodelactive = 0;
+
+// clear active surfaces to just the background surface
+	surfaces[1].next = surfaces[1].prev = &surfaces[1];
+	surfaces[1].last_u = edge_head_u_shift20;
+
+// generate spans
+	for (edge=edge_head.next ; edge != &edge_tail; edge=edge->next)
+	{			
+		if (edge->surfs[0])
+			R_TrailingEdge (&surfaces[edge->surfs[0]], edge);
+
+		if (edge->surfs[1])
+			R_LeadingEdgeBackwards (edge);
+	}
+
+	R_CleanupSpan ();
+}
+
+
+/*
+==============
+R_ScanEdges
+
+Input: 
+newedges[] array
+	this has links to edges, which have links to surfaces
+
+Output:
+Each surface has a linked list of its visible spans
+==============
+*/
+void R_ScanEdges (void)
+{
+	int		iv, bottom;
+	byte	basespans[MAXSPANS*sizeof(espan_t)+CACHE_SIZE];
+	espan_t	*basespan_p;
+	surf_t	*s;
+
+	basespan_p = (espan_t *)
+			((long)(basespans + CACHE_SIZE - 1) & ~(CACHE_SIZE - 1));
+	max_span_p = &basespan_p[MAXSPANS - r_refdef.vrect.width];
+
+	span_p = basespan_p;
+
+// clear active edges to just the background edges around the whole screen
+// FIXME: most of this only needs to be set up once
+	edge_head.u = r_refdef.vrect.x << 20;
+	edge_head_u_shift20 = edge_head.u >> 20;
+	edge_head.u_step = 0;
+	edge_head.prev = NULL;
+	edge_head.next = &edge_tail;
+	edge_head.surfs[0] = 0;
+	edge_head.surfs[1] = 1;
+	
+	edge_tail.u = (r_refdef.vrectright << 20) + 0xFFFFF;
+	edge_tail_u_shift20 = edge_tail.u >> 20;
+	edge_tail.u_step = 0;
+	edge_tail.prev = &edge_head;
+	edge_tail.next = &edge_aftertail;
+	edge_tail.surfs[0] = 1;
+	edge_tail.surfs[1] = 0;
+	
+	edge_aftertail.u = -1;		// force a move
+	edge_aftertail.u_step = 0;
+	edge_aftertail.next = &edge_sentinel;
+	edge_aftertail.prev = &edge_tail;
+
+// FIXME: do we need this now that we clamp x in r_draw.c?
+	edge_sentinel.u = 2000 << 24;		// make sure nothing sorts past this
+	edge_sentinel.prev = &edge_aftertail;
+
+//	
+// process all scan lines
+//
+	bottom = r_refdef.vrectbottom - 1;
+
+	for (iv=r_refdef.vrect.y ; iv<bottom ; iv++)
+	{
+		current_iv = iv;
+		fv = (float)iv;
+
+	// mark that the head (background start) span is pre-included
+		surfaces[1].spanstate = 1;
+
+		if (newedges[iv])
+		{
+			R_InsertNewEdges (newedges[iv], edge_head.next);
+		}
+
+		(*pdrawfunc) ();
+
+	// flush the span list if we can't be sure we have enough spans left for
+	// the next scan
+		if (span_p >= max_span_p)
+		{
+			VID_UnlockBuffer ();
+			S_ExtraUpdate ();	// don't let sound get messed up if going slow
+			VID_LockBuffer ();
+		
+			if (r_drawculledpolys)
+			{
+				R_DrawCulledPolys ();
+			}
+			else
+			{
+				D_DrawSurfaces ();
+			}
+
+		// clear the surface span pointers
+			for (s = &surfaces[1] ; s<surface_p ; s++)
+				s->spans = NULL;
+
+			span_p = basespan_p;
+		}
+
+		if (removeedges[iv])
+			R_RemoveEdges (removeedges[iv]);
+
+		if (edge_head.next != &edge_tail)
+			R_StepActiveU (edge_head.next);
+	}
+
+// do the last scan (no need to step or sort or remove on the last scan)
+
+	current_iv = iv;
+	fv = (float)iv;
+
+// mark that the head (background start) span is pre-included
+	surfaces[1].spanstate = 1;
+
+	if (newedges[iv])
+		R_InsertNewEdges (newedges[iv], edge_head.next);
+
+	(*pdrawfunc) ();
+
+// draw whatever's left in the span list
+	if (r_drawculledpolys)
+		R_DrawCulledPolys ();
+	else
+		D_DrawSurfaces ();
+}
+
+