/*
	r_edge.c

	$Id: r_edge.c,v 1.10 2007/07/09 21:50:57 sezero Exp $
*/

#include "quakedef.h"
#include "r_local.h"
#include "d_local.h"

/*
	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?
*/

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;

int	current_iv;

int	edge_head_u_shift20, edge_tail_u_shift20;

edge_t	edge_head;
edge_t	edge_tail;
edge_t	edge_aftertail;
edge_t	edge_sentinel;

float	fv;

//static int	show = 0;
int		TransCount;

static void (*pdrawfunc)(void);
static void (*pdrawTfunc)(void);

#if	!id386
long		FoundTrans;		// O.S: FIXME: see d_edge.c
static void R_GenerateSpans (void);
static void R_GenerateTSpans (void);
#else
extern long	FoundTrans;		// O.S: FIXME: see d_edge.c
extern void R_GenerateSpans (void);
extern void R_GenerateTSpans (void);
extern void R_InsertNewEdges (edge_t *edgestoadd, edge_t *edgelist);
extern void R_RemoveEdges (edge_t *pedge);
extern void R_StepActiveU (edge_t *pedge);
#endif
static void R_GenerateSpansBackward (void);
static void R_TrailingEdge (surf_t *surf, edge_t *edge);
static void R_LeadingEdgeBackwards (edge_t *edge);

//=============================================================================


/*
==============
R_DrawCulledPolys
==============
*/
static void R_DrawCulledPolys (void)
{
	surf_t			*s;
	msurface_t		*pface;

	currententity = &r_worldentity;

	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.integer)
	{
		pdrawfunc = R_GenerateSpansBackward;
		pdrawTfunc = R_GenerateTSpans;
		surfaces[1].key = 0;
		r_currentkey = 1;
	}
	else
	{
		pdrawfunc = R_GenerateSpans;
		pdrawTfunc = R_GenerateTSpans;
		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).
==============
*/
static 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);
}

//static qboolean	errorstate;
/*
==============
R_RemoveEdges
==============
*/
static void R_RemoveEdges (edge_t *pedge)
{
	do
	{
		if (!pedge->next || !pedge->prev)
		{
			Con_Printf("Bad!!!!");
		//	errorstate = true;
			break;
		}
		pedge->next->prev = pedge->prev;
		pedge->prev->next = pedge->next;
	} while ((pedge = pedge->nextremove) != NULL);
}

/*
==============
R_StepActiveU
==============
*/
static 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
==============
*/
static void R_CleanupSpan (void)
{
	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 && !(surf->flags & SURF_TRANSLUCENT))
	{
		span = span_p++;
		span->u = surf->last_u;
		span->count = iu - span->u;
		span->v = current_iv;
		span->pnext = surf->spans;
		surf->spans = span;
	//	if (show == 1)
	//		Con_Printf("Cleanup: %d,%d\n",span->u,span->count);
	}
	//else if (surf->flags & SURF_TRANSLUCENT)
	//	FoundTrans = true;

// reset spanstate for all surfaces in the surface stack
	do
	{
		surf->spanstate = 0;
		surf = surf->next;
	} while (surf != &surfaces[1]);
}

#if	!id386

static void R_CleanupSpanT (void)
{
	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 && (surf->flags & SURF_TRANSLUCENT))
	{
		span = span_p++;
		span->u = surf->last_u;
		span->count = iu - span->u;
		span->v = current_iv;
		span->pnext = surf->spans;
		surf->spans = span;
	//	if (show == 1)
	//		Con_Printf("CleanupT: %d,%d\n",span->u,span->count);
	}

// reset spanstate for all surfaces in the surface stack
	do
	{
		surf->spanstate = 0;
		surf = surf->next;
	} while (surf != &surfaces[1]);
}

#endif	// !id386


/*
==============
R_LeadingEdgeBackwards
==============
*/
static 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
==============
*/
static 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 !id386
	if ((surf->flags & SURF_TRANSLUCENT))
	{
		FoundTrans = true;
		// inverted span
		return;
	}
#endif
	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 !id386
			if (iu > surf->last_u)
#else
			if (iu > surf->last_u && !(surf->flags & SURF_TRANSLUCENT))
#endif
			{
				span = span_p++;
				span->u = surf->last_u;
				span->count = iu - span->u;
				span->v = current_iv;
				span->pnext = surf->spans;
				surf->spans = span;
			//	if (show == 1)
			//		Con_Printf("Trailing: %d,%d\n",span->u,span->count);
			}
			//else if (surf->flags & SURF_TRANSLUCENT)
			//	FoundTrans = true;

		// set last_u on the surface below
			surf->next->last_u = iu;
		}

		surf->prev->next = surf->next;
		surf->next->prev = surf->prev;
	}
#if id386
	else
	{
		surf->spanstate = 0;
	}
#endif
}

#if	!id386

static void R_TrailingEdgeT (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 && (surf->flags & SURF_TRANSLUCENT))
			{
				span = span_p++;
				span->u = surf->last_u;
				span->count = iu - span->u;
				span->v = current_iv;
				span->pnext = surf->spans;
				surf->spans = span;
			//	if (show == 1)
			//		Con_Printf("TrailingT: %d,%d\n",span->u,span->count);
			}

		// set last_u on the surface below
			surf->next->last_u = iu;
		}

		surf->prev->next = surf->next;
		surf->next->prev = surf->prev;
	}
}

/*
==============
R_LeadingEdge
==============
*/
static 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]];
		if (surf->flags & SURF_TRANSLUCENT) 
		{
			FoundTrans = true;
		//	if (show == 0)
		//		show = 1;
			return;
		}

	// 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.999;

				testzi = surf2->d_ziorigin +
						fv*surf2->d_zistepv +
						fu*surf2->d_zistepu;

				if (newzibottom >= testzi)
				{
					goto newtop;
				}

				newzitop = newzi * 1.001;
				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.999;

				testzi = surf2->d_ziorigin +
						fv*surf2->d_zistepv +
						fu*surf2->d_zistepu;

				if (newzibottom >= testzi)
				{
					goto gotposition;
				}

				newzitop = newzi * 1.001;
				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 && !(surf2->flags & SURF_TRANSLUCENT))
			{
				span = span_p++;
				span->u = surf2->last_u;
				span->count = iu - span->u;
				span->v = current_iv;
				span->pnext = surf2->spans;
				surf2->spans = span;
			//	if (show == 1)
			//		Con_Printf("Leading: %d,%d\n",span->u,span->count);
			}
			//else if (surf2->flags & SURF_TRANSLUCENT)
			//	FoundTrans = true;

		// 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_LeadingEdgeT
==============
*/
static void R_LeadingEdgeT (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.999;

				testzi = surf2->d_ziorigin +
						fv*surf2->d_zistepv +
						fu*surf2->d_zistepu;

				if (newzibottom >= testzi)
				{
					goto newtop;
				}

				newzitop = newzi * 1.001;
				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.999;

				testzi = surf2->d_ziorigin +
						fv*surf2->d_zistepv +
						fu*surf2->d_zistepu;

				if (newzibottom >= testzi)
				{
					goto gotposition;
				}

				newzitop = newzi * 1.001;
				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 && (surf2->flags & SURF_TRANSLUCENT))
			{
				span = span_p++;
				span->u = surf2->last_u;
				span->count = iu - span->u;
				span->v = current_iv;
				span->pnext = surf2->spans;
				surf2->spans = span;
			//	if (show == 1)
			//		Con_Printf("LeadingT: %d,%d\n",span->u,span->count);
			}

		// 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
==============
*/
static void R_GenerateSpans (void)
{
	edge_t		*edge;
	surf_t		*surf;

	r_bmodelactive = 0;
	FoundTrans = false;	/* FIXME ! */

// 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
// note: edge->surfs[0] is trailing
//	 edge->surfs[1] is leading

	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 ();

#if 0
	if (!FoundTrans)
		return;

// 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_TrailingEdgeT (surf, edge);

			if (!edge->surfs[1])
				continue;
		}

		R_LeadingEdgeT (edge);
	}

	R_CleanupSpanT ();
#endif
/*	if (show == 1)
	{
		show = 2;
		Con_Printf("DONE\n");
	}
*/
}

/*
==============
R_GenerateTSpans
==============
*/
static void R_GenerateTSpans (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_TrailingEdgeT (surf, edge);

			if (!edge->surfs[1])
				continue;
		}

		R_LeadingEdgeT (edge);
	}

	R_CleanupSpanT ();
}

#endif	// !id386


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

static qboolean TransList[SCAN_SIZE];

/*
==============
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 (qboolean Translucent)
{
	int		iv, bottom;
	byte	basespans[MAXSPANS*sizeof(espan_t)+CACHE_SIZE];
	espan_t	*basespan_p;
	surf_t	*s;

	if (Translucent && r_draworder.integer)
		return;

	basespan_p = (espan_t *)
			((intptr_t)(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;

	//show = 0;

	if (!Translucent)
	{
//		memset(TransList,0,sizeof(TransList));
		TransCount = 0;
	}

	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);
		}

		if (!Translucent)
		{
			(*pdrawfunc) ();
			TransList[iv] = FoundTrans;
			TransCount += FoundTrans;
		}
		else if (TransList[iv])
		{
			(*pdrawTfunc) ();
		}

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

		// 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);

	if (!Translucent)
	{
		(*pdrawfunc) ();
		TransList[iv] = FoundTrans;
		TransCount += FoundTrans;
	}
	else if (TransList[iv])
		(*pdrawTfunc) ();

	// draw whatever's left in the span list
	if (r_drawculledpolys)
		R_DrawCulledPolys ();
	else
	{
		D_DrawSurfaces (Translucent);
	}

	//if (!Translucent)
	//	Con_Printf("Trans = %d\n",TransCount);
}