quake/src/WinQuake/r_edge.cpp - platform/external/quake - Git at Google

 /*
 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 ();
 }
	/*
	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 ();
	}