Subversion Repositories Kolibri OS

/*

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.

*/

// d_polyset.c: routines for drawing sets of polygons sharing the same

// texture (used for Alias models)

#include "quakedef.h"

#include "r_local.h"

#include "d_local.h"

// TODO: put in span spilling to shrink list size

// !!! if this is changed, it must be changed in d_polysa.s too !!!

#define DPS_MAXSPANS			MAXHEIGHT+1

									// 1 extra for spanpackage that marks end

// !!! if this is changed, it must be changed in asm_draw.h too !!!

typedef struct {

	void			*pdest;

	short			*pz;

	int				count;

	byte			*ptex;

	int				sfrac, tfrac, light, zi;

} spanpackage_t;

typedef struct {

	int		isflattop;

	int		numleftedges;

	int		*pleftedgevert0;

	int		*pleftedgevert1;

	int		*pleftedgevert2;

	int		numrightedges;

	int		*prightedgevert0;

	int		*prightedgevert1;

	int		*prightedgevert2;

} edgetable;

int	r_p0[6], r_p1[6], r_p2[6];

byte		*d_pcolormap;

int			d_aflatcolor;

int			d_xdenom;

edgetable	*pedgetable;

edgetable	edgetables[12] = {

	{0, 1, r_p0, r_p2, NULL, 2, r_p0, r_p1, r_p2 },

	{0, 2, r_p1, r_p0, r_p2,   1, r_p1, r_p2, NULL},

	{1, 1, r_p0, r_p2, NULL, 1, r_p1, r_p2, NULL},

	{0, 1, r_p1, r_p0, NULL, 2, r_p1, r_p2, r_p0 },

	{0, 2, r_p0, r_p2, r_p1,   1, r_p0, r_p1, NULL},

	{0, 1, r_p2, r_p1, NULL, 1, r_p2, r_p0, NULL},

	{0, 1, r_p2, r_p1, NULL, 2, r_p2, r_p0, r_p1 },

	{0, 2, r_p2, r_p1, r_p0,   1, r_p2, r_p0, NULL},

	{0, 1, r_p1, r_p0, NULL, 1, r_p1, r_p2, NULL},

	{1, 1, r_p2, r_p1, NULL, 1, r_p0, r_p1, NULL},

	{1, 1, r_p1, r_p0, NULL, 1, r_p2, r_p0, NULL},

	{0, 1, r_p0, r_p2, NULL, 1, r_p0, r_p1, NULL},

};

// FIXME: some of these can become statics

int				a_sstepxfrac, a_tstepxfrac, r_lstepx, a_ststepxwhole;

int				r_sstepx, r_tstepx, r_lstepy, r_sstepy, r_tstepy;

int				r_zistepx, r_zistepy;

int				d_aspancount, d_countextrastep;

spanpackage_t			*a_spans;

spanpackage_t			*d_pedgespanpackage;

static int				ystart;

byte					*d_pdest, *d_ptex;

short					*d_pz;

int						d_sfrac, d_tfrac, d_light, d_zi;

int						d_ptexextrastep, d_sfracextrastep;

int						d_tfracextrastep, d_lightextrastep, d_pdestextrastep;

int						d_lightbasestep, d_pdestbasestep, d_ptexbasestep;

int						d_sfracbasestep, d_tfracbasestep;

int						d_ziextrastep, d_zibasestep;

int						d_pzextrastep, d_pzbasestep;

typedef struct {

	int		quotient;

	int		remainder;

} adivtab_t;

static adivtab_t	adivtab[32*32] = {

#include "adivtab.h"

};

byte	*skintable[MAX_LBM_HEIGHT];

int		skinwidth;

byte	*skinstart;

void D_PolysetDrawSpans8 (spanpackage_t *pspanpackage);

void D_PolysetCalcGradients (int skinwidth);

void D_DrawSubdiv (void);

void D_DrawNonSubdiv (void);

void D_PolysetRecursiveTriangle (int *p1, int *p2, int *p3);

void D_PolysetSetEdgeTable (void);

void D_RasterizeAliasPolySmooth (void);

void D_PolysetScanLeftEdge (int height);

#if	!id386

/*

================

D_PolysetDraw

================

*/

void D_PolysetDraw (void)

{

	spanpackage_t	spans[DPS_MAXSPANS + 1 +

			((CACHE_SIZE - 1) / sizeof(spanpackage_t)) + 1];

						// one extra because of cache line pretouching

	a_spans = (spanpackage_t *)

			(((long)&spans[0] + CACHE_SIZE - 1) & ~(CACHE_SIZE - 1));

	if (r_affinetridesc.drawtype)

	{

		D_DrawSubdiv ();

	}

	else

	{

		D_DrawNonSubdiv ();

	}

}

/*

================

D_PolysetDrawFinalVerts

================

*/

void D_PolysetDrawFinalVerts (finalvert_t *fv, int numverts)

{

	int		i, z;

	short	*zbuf;

	for (i=0 ; i

	{

	// valid triangle coordinates for filling can include the bottom and

	// right clip edges, due to the fill rule; these shouldn't be drawn

		if ((fv->v[0] < r_refdef.vrectright) &&

			(fv->v[1] < r_refdef.vrectbottom))

		{

			z = fv->v[5]>>16;

			zbuf = zspantable[fv->v[1]] + fv->v[0];

			if (z >= *zbuf)

			{

				int		pix;

				*zbuf = z;

				pix = skintable[fv->v[3]>>16][fv->v[2]>>16];

				pix = ((byte *)acolormap)[pix + (fv->v[4] & 0xFF00) ];

				d_viewbuffer[d_scantable[fv->v[1]] + fv->v[0]] = pix;

			}

		}

	}

}

/*

================

D_DrawSubdiv

================

*/

void D_DrawSubdiv (void)

{

	mtriangle_t		*ptri;

	finalvert_t		*pfv, *index0, *index1, *index2;

	int				i;

	int				lnumtriangles;

	pfv = r_affinetridesc.pfinalverts;

	ptri = r_affinetridesc.ptriangles;

	lnumtriangles = r_affinetridesc.numtriangles;

	for (i=0 ; i

	{

		index0 = pfv + ptri[i].vertindex[0];

		index1 = pfv + ptri[i].vertindex[1];

		index2 = pfv + ptri[i].vertindex[2];

		if (((index0->v[1]-index1->v[1]) *

			 (index0->v[0]-index2->v[0]) -

			 (index0->v[0]-index1->v[0]) *

			 (index0->v[1]-index2->v[1])) >= 0)

		{

			continue;

		}

		d_pcolormap = &((byte *)acolormap)[index0->v[4] & 0xFF00];

		if (ptri[i].facesfront)

		{

			D_PolysetRecursiveTriangle(index0->v, index1->v, index2->v);

		}

		else

		{

			int		s0, s1, s2;

			s0 = index0->v[2];

			s1 = index1->v[2];

			s2 = index2->v[2];

			if (index0->flags & ALIAS_ONSEAM)

				index0->v[2] += r_affinetridesc.seamfixupX16;

			if (index1->flags & ALIAS_ONSEAM)

				index1->v[2] += r_affinetridesc.seamfixupX16;

			if (index2->flags & ALIAS_ONSEAM)

				index2->v[2] += r_affinetridesc.seamfixupX16;

			D_PolysetRecursiveTriangle(index0->v, index1->v, index2->v);

			index0->v[2] = s0;

			index1->v[2] = s1;

			index2->v[2] = s2;

		}

	}

}

/*

================

D_DrawNonSubdiv

================

*/

void D_DrawNonSubdiv (void)

{

	mtriangle_t		*ptri;

	finalvert_t		*pfv, *index0, *index1, *index2;

	int				i;

	int				lnumtriangles;

	pfv = r_affinetridesc.pfinalverts;

	ptri = r_affinetridesc.ptriangles;

	lnumtriangles = r_affinetridesc.numtriangles;

	for (i=0 ; i

	{

		index0 = pfv + ptri->vertindex[0];

		index1 = pfv + ptri->vertindex[1];

		index2 = pfv + ptri->vertindex[2];

		d_xdenom = (index0->v[1]-index1->v[1]) *

				(index0->v[0]-index2->v[0]) -

				(index0->v[0]-index1->v[0])*(index0->v[1]-index2->v[1]);

		if (d_xdenom >= 0)

		{

			continue;

		}

		r_p0[0] = index0->v[0];		// u

		r_p0[1] = index0->v[1];		// v

		r_p0[2] = index0->v[2];		// s

		r_p0[3] = index0->v[3];		// t

		r_p0[4] = index0->v[4];		// light

		r_p0[5] = index0->v[5];		// iz

		r_p1[0] = index1->v[0];

		r_p1[1] = index1->v[1];

		r_p1[2] = index1->v[2];

		r_p1[3] = index1->v[3];

		r_p1[4] = index1->v[4];

		r_p1[5] = index1->v[5];

		r_p2[0] = index2->v[0];

		r_p2[1] = index2->v[1];

		r_p2[2] = index2->v[2];

		r_p2[3] = index2->v[3];

		r_p2[4] = index2->v[4];

		r_p2[5] = index2->v[5];

		if (!ptri->facesfront)

		{

			if (index0->flags & ALIAS_ONSEAM)

				r_p0[2] += r_affinetridesc.seamfixupX16;

			if (index1->flags & ALIAS_ONSEAM)

				r_p1[2] += r_affinetridesc.seamfixupX16;

			if (index2->flags & ALIAS_ONSEAM)

				r_p2[2] += r_affinetridesc.seamfixupX16;

		}

		D_PolysetSetEdgeTable ();

		D_RasterizeAliasPolySmooth ();

	}

}

/*

================

D_PolysetRecursiveTriangle

================

*/

void D_PolysetRecursiveTriangle (int *lp1, int *lp2, int *lp3)

{

	int		*temp;

	int		d;

	int		new[6];

	int		z;

	short	*zbuf;

	d = lp2[0] - lp1[0];

	if (d < -1 || d > 1)

		goto split;

	d = lp2[1] - lp1[1];

	if (d < -1 || d > 1)

		goto split;

	d = lp3[0] - lp2[0];

	if (d < -1 || d > 1)

		goto split2;

	d = lp3[1] - lp2[1];

	if (d < -1 || d > 1)

		goto split2;

	d = lp1[0] - lp3[0];

	if (d < -1 || d > 1)

		goto split3;

	d = lp1[1] - lp3[1];

	if (d < -1 || d > 1)

	{

split3:

		temp = lp1;

		lp1 = lp3;

		lp3 = lp2;

		lp2 = temp;

		goto split;

	}

	return;			// entire tri is filled

split2:

	temp = lp1;

	lp1 = lp2;

	lp2 = lp3;

	lp3 = temp;

split:

// split this edge

	new[0] = (lp1[0] + lp2[0]) >> 1;

	new[1] = (lp1[1] + lp2[1]) >> 1;

	new[2] = (lp1[2] + lp2[2]) >> 1;

	new[3] = (lp1[3] + lp2[3]) >> 1;

	new[5] = (lp1[5] + lp2[5]) >> 1;

// draw the point if splitting a leading edge

	if (lp2[1] > lp1[1])

		goto nodraw;

	if ((lp2[1] == lp1[1]) && (lp2[0] < lp1[0]))

		goto nodraw;

	z = new[5]>>16;

	zbuf = zspantable[new[1]] + new[0];

	if (z >= *zbuf)

	{

		int		pix;

		*zbuf = z;

		pix = d_pcolormap[skintable[new[3]>>16][new[2]>>16]];

		d_viewbuffer[d_scantable[new[1]] + new[0]] = pix;

	}

nodraw:

// recursively continue

	D_PolysetRecursiveTriangle (lp3, lp1, new);

	D_PolysetRecursiveTriangle (lp3, new, lp2);

}

#endif	// !id386

/*

================

D_PolysetUpdateTables

================

*/

void D_PolysetUpdateTables (void)

{

	int		i;

	byte	*s;

	if (r_affinetridesc.skinwidth != skinwidth ||

		r_affinetridesc.pskin != skinstart)

	{

		skinwidth = r_affinetridesc.skinwidth;

		skinstart = r_affinetridesc.pskin;

		s = skinstart;

		for (i=0 ; i

			skintable[i] = s;

	}

}

#if	!id386

/*

===================

D_PolysetScanLeftEdge

====================

*/

void D_PolysetScanLeftEdge (int height)

{

	do

	{

		d_pedgespanpackage->pdest = d_pdest;

		d_pedgespanpackage->pz = d_pz;

		d_pedgespanpackage->count = d_aspancount;

		d_pedgespanpackage->ptex = d_ptex;

		d_pedgespanpackage->sfrac = d_sfrac;

		d_pedgespanpackage->tfrac = d_tfrac;

	// FIXME: need to clamp l, s, t, at both ends?

		d_pedgespanpackage->light = d_light;

		d_pedgespanpackage->zi = d_zi;

		d_pedgespanpackage++;

		errorterm += erroradjustup;

		if (errorterm >= 0)

		{

			d_pdest += d_pdestextrastep;

			d_pz += d_pzextrastep;

			d_aspancount += d_countextrastep;

			d_ptex += d_ptexextrastep;

			d_sfrac += d_sfracextrastep;

			d_ptex += d_sfrac >> 16;

			d_sfrac &= 0xFFFF;

			d_tfrac += d_tfracextrastep;

			if (d_tfrac & 0x10000)

			{

				d_ptex += r_affinetridesc.skinwidth;

				d_tfrac &= 0xFFFF;

			}

			d_light += d_lightextrastep;

			d_zi += d_ziextrastep;

			errorterm -= erroradjustdown;

		}

		else

		{

			d_pdest += d_pdestbasestep;

			d_pz += d_pzbasestep;

			d_aspancount += ubasestep;

			d_ptex += d_ptexbasestep;

			d_sfrac += d_sfracbasestep;

			d_ptex += d_sfrac >> 16;

			d_sfrac &= 0xFFFF;

			d_tfrac += d_tfracbasestep;

			if (d_tfrac & 0x10000)

			{

				d_ptex += r_affinetridesc.skinwidth;

				d_tfrac &= 0xFFFF;

			}

			d_light += d_lightbasestep;

			d_zi += d_zibasestep;

		}

	} while (--height);

}

#endif	// !id386

/*

===================

D_PolysetSetUpForLineScan

====================

*/

void D_PolysetSetUpForLineScan(fixed8_t startvertu, fixed8_t startvertv,

		fixed8_t endvertu, fixed8_t endvertv)

{

	double		dm, dn;

	int			tm, tn;

	adivtab_t	*ptemp;

// TODO: implement x86 version

	errorterm = -1;

	tm = endvertu - startvertu;

	tn = endvertv - startvertv;

	if (((tm <= 16) && (tm >= -15)) &&

		((tn <= 16) && (tn >= -15)))

	{

		ptemp = &adivtab[((tm+15) << 5) + (tn+15)];

		ubasestep = ptemp->quotient;

		erroradjustup = ptemp->remainder;

		erroradjustdown = tn;

	}

	else

	{

		dm = (double)tm;

		dn = (double)tn;

		FloorDivMod (dm, dn, &ubasestep, &erroradjustup);

		erroradjustdown = dn;

	}

}

#if	!id386

/*

================

D_PolysetCalcGradients

================

*/

void D_PolysetCalcGradients (int skinwidth)

{

	float	xstepdenominv, ystepdenominv, t0, t1;

	float	p01_minus_p21, p11_minus_p21, p00_minus_p20, p10_minus_p20;

	p00_minus_p20 = r_p0[0] - r_p2[0];

	p01_minus_p21 = r_p0[1] - r_p2[1];

	p10_minus_p20 = r_p1[0] - r_p2[0];

	p11_minus_p21 = r_p1[1] - r_p2[1];

	xstepdenominv = 1.0 / (float)d_xdenom;

	ystepdenominv = -xstepdenominv;

// ceil () for light so positive steps are exaggerated, negative steps

// diminished,  pushing us away from underflow toward overflow. Underflow is

// very visible, overflow is very unlikely, because of ambient lighting

	t0 = r_p0[4] - r_p2[4];

	t1 = r_p1[4] - r_p2[4];

	r_lstepx = (int)

			ceil((t1 * p01_minus_p21 - t0 * p11_minus_p21) * xstepdenominv);

	r_lstepy = (int)

			ceil((t1 * p00_minus_p20 - t0 * p10_minus_p20) * ystepdenominv);

	t0 = r_p0[2] - r_p2[2];

	t1 = r_p1[2] - r_p2[2];

	r_sstepx = (int)((t1 * p01_minus_p21 - t0 * p11_minus_p21) *

			xstepdenominv);

	r_sstepy = (int)((t1 * p00_minus_p20 - t0* p10_minus_p20) *

			ystepdenominv);

	t0 = r_p0[3] - r_p2[3];

	t1 = r_p1[3] - r_p2[3];

	r_tstepx = (int)((t1 * p01_minus_p21 - t0 * p11_minus_p21) *

			xstepdenominv);

	r_tstepy = (int)((t1 * p00_minus_p20 - t0 * p10_minus_p20) *

			ystepdenominv);

	t0 = r_p0[5] - r_p2[5];

	t1 = r_p1[5] - r_p2[5];

	r_zistepx = (int)((t1 * p01_minus_p21 - t0 * p11_minus_p21) *

			xstepdenominv);

	r_zistepy = (int)((t1 * p00_minus_p20 - t0 * p10_minus_p20) *

			ystepdenominv);

#if	id386

	a_sstepxfrac = r_sstepx << 16;

	a_tstepxfrac = r_tstepx << 16;

#else

	a_sstepxfrac = r_sstepx & 0xFFFF;

	a_tstepxfrac = r_tstepx & 0xFFFF;

#endif

	a_ststepxwhole = skinwidth * (r_tstepx >> 16) + (r_sstepx >> 16);

}

#endif	// !id386

#if 0

byte gelmap[256];

void InitGel (byte *palette)

{

	int		i;

	int		r;

	for (i=0 ; i<256 ; i++)

	{

//		r = (palette[i*3]>>4);

		r = (palette[i*3] + palette[i*3+1] + palette[i*3+2])/(16*3);

		gelmap[i] = /* 64 */ 0 + r;

	}

}

#endif

#if	!id386

/*

================

D_PolysetDrawSpans8

================

*/

void D_PolysetDrawSpans8 (spanpackage_t *pspanpackage)

{

	int		lcount;

	byte	*lpdest;

	byte	*lptex;

	int		lsfrac, ltfrac;

	int		llight;

	int		lzi;

	short	*lpz;

	do

	{

		lcount = d_aspancount - pspanpackage->count;

		errorterm += erroradjustup;

		if (errorterm >= 0)

		{

			d_aspancount += d_countextrastep;

			errorterm -= erroradjustdown;

		}

		else

		{

			d_aspancount += ubasestep;

		}

		if (lcount)

		{

			lpdest = pspanpackage->pdest;

			lptex = pspanpackage->ptex;

			lpz = pspanpackage->pz;

			lsfrac = pspanpackage->sfrac;

			ltfrac = pspanpackage->tfrac;

			llight = pspanpackage->light;

			lzi = pspanpackage->zi;

			do

			{

				if ((lzi >> 16) >= *lpz)

				{

					*lpdest = ((byte *)acolormap)[*lptex + (llight & 0xFF00)];

// gel mapping					*lpdest = gelmap[*lpdest];

					*lpz = lzi >> 16;

				}

				lpdest++;

				lzi += r_zistepx;

				lpz++;

				llight += r_lstepx;

				lptex += a_ststepxwhole;

				lsfrac += a_sstepxfrac;

				lptex += lsfrac >> 16;

				lsfrac &= 0xFFFF;

				ltfrac += a_tstepxfrac;

				if (ltfrac & 0x10000)

				{

					lptex += r_affinetridesc.skinwidth;

					ltfrac &= 0xFFFF;

				}

			} while (--lcount);

		}

		pspanpackage++;

	} while (pspanpackage->count != -999999);

}

#endif	// !id386

/*

================

D_PolysetFillSpans8

================

*/

void D_PolysetFillSpans8 (spanpackage_t *pspanpackage)

{

	int				color;

// FIXME: do z buffering

	color = d_aflatcolor++;

	while (1)

	{

		int		lcount;

		byte	*lpdest;

		lcount = pspanpackage->count;

		if (lcount == -1)

			return;

		if (lcount)

		{

			lpdest = pspanpackage->pdest;

			do

			{

				*lpdest++ = color;

			} while (--lcount);

		}

		pspanpackage++;

	}

}

/*

================

D_RasterizeAliasPolySmooth

================

*/

void D_RasterizeAliasPolySmooth (void)

{

	int				initialleftheight, initialrightheight;

	int				*plefttop, *prighttop, *pleftbottom, *prightbottom;

	int				working_lstepx, originalcount;

	plefttop = pedgetable->pleftedgevert0;

	prighttop = pedgetable->prightedgevert0;

	pleftbottom = pedgetable->pleftedgevert1;

	prightbottom = pedgetable->prightedgevert1;

	initialleftheight = pleftbottom[1] - plefttop[1];

	initialrightheight = prightbottom[1] - prighttop[1];

//

// set the s, t, and light gradients, which are consistent across the triangle

// because being a triangle, things are affine

//

	D_PolysetCalcGradients (r_affinetridesc.skinwidth);

//

// rasterize the polygon

//

//

// scan out the top (and possibly only) part of the left edge

//

	d_pedgespanpackage = a_spans;

	ystart = plefttop[1];

	d_aspancount = plefttop[0] - prighttop[0];

	d_ptex = (byte *)r_affinetridesc.pskin + (plefttop[2] >> 16) +

			(plefttop[3] >> 16) * r_affinetridesc.skinwidth;

#if	id386

	d_sfrac = (plefttop[2] & 0xFFFF) << 16;

	d_tfrac = (plefttop[3] & 0xFFFF) << 16;

#else

	d_sfrac = plefttop[2] & 0xFFFF;

	d_tfrac = plefttop[3] & 0xFFFF;

#endif

	d_light = plefttop[4];

	d_zi = plefttop[5];

	d_pdest = (byte *)d_viewbuffer +

			ystart * screenwidth + plefttop[0];

	d_pz = d_pzbuffer + ystart * d_zwidth + plefttop[0];

	if (initialleftheight == 1)

	{

		d_pedgespanpackage->pdest = d_pdest;

		d_pedgespanpackage->pz = d_pz;

		d_pedgespanpackage->count = d_aspancount;

		d_pedgespanpackage->ptex = d_ptex;

		d_pedgespanpackage->sfrac = d_sfrac;

		d_pedgespanpackage->tfrac = d_tfrac;

	// FIXME: need to clamp l, s, t, at both ends?

		d_pedgespanpackage->light = d_light;

		d_pedgespanpackage->zi = d_zi;

		d_pedgespanpackage++;

	}

	else

	{

		D_PolysetSetUpForLineScan(plefttop[0], plefttop[1],

							  pleftbottom[0], pleftbottom[1]);

	#if	id386

		d_pzbasestep = (d_zwidth + ubasestep) << 1;

		d_pzextrastep = d_pzbasestep + 2;

	#else

		d_pzbasestep = d_zwidth + ubasestep;

		d_pzextrastep = d_pzbasestep + 1;

	#endif

		d_pdestbasestep = screenwidth + ubasestep;

		d_pdestextrastep = d_pdestbasestep + 1;

	// TODO: can reuse partial expressions here

	// for negative steps in x along left edge, bias toward overflow rather than

	// underflow (sort of turning the floor () we did in the gradient calcs into

	// ceil (), but plus a little bit)

		if (ubasestep < 0)

			working_lstepx = r_lstepx - 1;

		else

			working_lstepx = r_lstepx;

		d_countextrastep = ubasestep + 1;

		d_ptexbasestep = ((r_sstepy + r_sstepx * ubasestep) >> 16) +

				((r_tstepy + r_tstepx * ubasestep) >> 16) *

				r_affinetridesc.skinwidth;

	#if	id386

		d_sfracbasestep = (r_sstepy + r_sstepx * ubasestep) << 16;

		d_tfracbasestep = (r_tstepy + r_tstepx * ubasestep) << 16;

	#else

		d_sfracbasestep = (r_sstepy + r_sstepx * ubasestep) & 0xFFFF;

		d_tfracbasestep = (r_tstepy + r_tstepx * ubasestep) & 0xFFFF;

	#endif

		d_lightbasestep = r_lstepy + working_lstepx * ubasestep;

		d_zibasestep = r_zistepy + r_zistepx * ubasestep;

		d_ptexextrastep = ((r_sstepy + r_sstepx * d_countextrastep) >> 16) +

				((r_tstepy + r_tstepx * d_countextrastep) >> 16) *

				r_affinetridesc.skinwidth;

	#if	id386

		d_sfracextrastep = (r_sstepy + r_sstepx*d_countextrastep) << 16;

		d_tfracextrastep = (r_tstepy + r_tstepx*d_countextrastep) << 16;

	#else

		d_sfracextrastep = (r_sstepy + r_sstepx*d_countextrastep) & 0xFFFF;

		d_tfracextrastep = (r_tstepy + r_tstepx*d_countextrastep) & 0xFFFF;

	#endif

		d_lightextrastep = d_lightbasestep + working_lstepx;

		d_ziextrastep = d_zibasestep + r_zistepx;

		D_PolysetScanLeftEdge (initialleftheight);

	}

//

// scan out the bottom part of the left edge, if it exists

//

	if (pedgetable->numleftedges == 2)

	{

		int		height;

		plefttop = pleftbottom;

		pleftbottom = pedgetable->pleftedgevert2;

		height = pleftbottom[1] - plefttop[1];

// TODO: make this a function; modularize this function in general

		ystart = plefttop[1];

		d_aspancount = plefttop[0] - prighttop[0];

		d_ptex = (byte *)r_affinetridesc.pskin + (plefttop[2] >> 16) +

				(plefttop[3] >> 16) * r_affinetridesc.skinwidth;

		d_sfrac = 0;

		d_tfrac = 0;

		d_light = plefttop[4];

		d_zi = plefttop[5];

		d_pdest = (byte *)d_viewbuffer + ystart * screenwidth + plefttop[0];

		d_pz = d_pzbuffer + ystart * d_zwidth + plefttop[0];

		if (height == 1)

		{

			d_pedgespanpackage->pdest = d_pdest;

			d_pedgespanpackage->pz = d_pz;

			d_pedgespanpackage->count = d_aspancount;

			d_pedgespanpackage->ptex = d_ptex;

			d_pedgespanpackage->sfrac = d_sfrac;

			d_pedgespanpackage->tfrac = d_tfrac;

		// FIXME: need to clamp l, s, t, at both ends?

			d_pedgespanpackage->light = d_light;

			d_pedgespanpackage->zi = d_zi;

			d_pedgespanpackage++;

		}

		else

		{

			D_PolysetSetUpForLineScan(plefttop[0], plefttop[1],

								  pleftbottom[0], pleftbottom[1]);

			d_pdestbasestep = screenwidth + ubasestep;

			d_pdestextrastep = d_pdestbasestep + 1;

	#if	id386

			d_pzbasestep = (d_zwidth + ubasestep) << 1;

			d_pzextrastep = d_pzbasestep + 2;

	#else

			d_pzbasestep = d_zwidth + ubasestep;

			d_pzextrastep = d_pzbasestep + 1;

	#endif

			if (ubasestep < 0)

				working_lstepx = r_lstepx - 1;

			else

				working_lstepx = r_lstepx;

			d_countextrastep = ubasestep + 1;

			d_ptexbasestep = ((r_sstepy + r_sstepx * ubasestep) >> 16) +

					((r_tstepy + r_tstepx * ubasestep) >> 16) *

					r_affinetridesc.skinwidth;

	#if	id386

			d_sfracbasestep = (r_sstepy + r_sstepx * ubasestep) << 16;

			d_tfracbasestep = (r_tstepy + r_tstepx * ubasestep) << 16;

	#else

			d_sfracbasestep = (r_sstepy + r_sstepx * ubasestep) & 0xFFFF;

			d_tfracbasestep = (r_tstepy + r_tstepx * ubasestep) & 0xFFFF;

	#endif

			d_lightbasestep = r_lstepy + working_lstepx * ubasestep;

			d_zibasestep = r_zistepy + r_zistepx * ubasestep;

			d_ptexextrastep = ((r_sstepy + r_sstepx * d_countextrastep) >> 16) +

					((r_tstepy + r_tstepx * d_countextrastep) >> 16) *

					r_affinetridesc.skinwidth;

	#if	id386

			d_sfracextrastep = ((r_sstepy+r_sstepx*d_countextrastep) & 0xFFFF)<<16;

			d_tfracextrastep = ((r_tstepy+r_tstepx*d_countextrastep) & 0xFFFF)<<16;

	#else

			d_sfracextrastep = (r_sstepy+r_sstepx*d_countextrastep) & 0xFFFF;

			d_tfracextrastep = (r_tstepy+r_tstepx*d_countextrastep) & 0xFFFF;

	#endif

			d_lightextrastep = d_lightbasestep + working_lstepx;

			d_ziextrastep = d_zibasestep + r_zistepx;

			D_PolysetScanLeftEdge (height);

		}

	}

// scan out the top (and possibly only) part of the right edge, updating the

// count field

	d_pedgespanpackage = a_spans;

	D_PolysetSetUpForLineScan(prighttop[0], prighttop[1],

						  prightbottom[0], prightbottom[1]);

	d_aspancount = 0;

	d_countextrastep = ubasestep + 1;

	originalcount = a_spans[initialrightheight].count;

	a_spans[initialrightheight].count = -999999; // mark end of the spanpackages

	D_PolysetDrawSpans8 (a_spans);

// scan out the bottom part of the right edge, if it exists

	if (pedgetable->numrightedges == 2)

	{

		int				height;

		spanpackage_t	*pstart;

		pstart = a_spans + initialrightheight;

		pstart->count = originalcount;

		d_aspancount = prightbottom[0] - prighttop[0];

		prighttop = prightbottom;

		prightbottom = pedgetable->prightedgevert2;

		height = prightbottom[1] - prighttop[1];

		D_PolysetSetUpForLineScan(prighttop[0], prighttop[1],

							  prightbottom[0], prightbottom[1]);

		d_countextrastep = ubasestep + 1;

		a_spans[initialrightheight + height].count = -999999;

											// mark end of the spanpackages

		D_PolysetDrawSpans8 (pstart);

	}

}

/*

================

D_PolysetSetEdgeTable

================

*/

void D_PolysetSetEdgeTable (void)

{

	int			edgetableindex;

	edgetableindex = 0;	// assume the vertices are already in

						//  top to bottom order

//

// determine which edges are right & left, and the order in which

// to rasterize them

//

	if (r_p0[1] >= r_p1[1])

	{

		if (r_p0[1] == r_p1[1])

		{

			if (r_p0[1] < r_p2[1])

				pedgetable = &edgetables[2];

			else

				pedgetable = &edgetables[5];

			return;

		}

		else

		{

			edgetableindex = 1;

		}

	}

	if (r_p0[1] == r_p2[1])

	{

		if (edgetableindex)

			pedgetable = &edgetables[8];

		else

			pedgetable = &edgetables[9];

		return;

	}

	else if (r_p1[1] == r_p2[1])

	{

		if (edgetableindex)

			pedgetable = &edgetables[10];

		else

			pedgetable = &edgetables[11];

		return;

	}

	if (r_p0[1] > r_p2[1])

		edgetableindex += 2;

	if (r_p1[1] > r_p2[1])

		edgetableindex += 4;

	pedgetable = &edgetables[edgetableindex];

}

#if 0

void D_PolysetRecursiveDrawLine (int *lp1, int *lp2)

{

	int		d;

	int		new[6];

	int 	ofs;

	d = lp2[0] - lp1[0];

	if (d < -1 || d > 1)

		goto split;

	d = lp2[1] - lp1[1];

	if (d < -1 || d > 1)

		goto split;

	return;	// line is completed

split:

// split this edge

	new[0] = (lp1[0] + lp2[0]) >> 1;

	new[1] = (lp1[1] + lp2[1]) >> 1;

	new[5] = (lp1[5] + lp2[5]) >> 1;

	new[2] = (lp1[2] + lp2[2]) >> 1;

	new[3] = (lp1[3] + lp2[3]) >> 1;

	new[4] = (lp1[4] + lp2[4]) >> 1;

// draw the point

	ofs = d_scantable[new[1]] + new[0];

	if (new[5] > d_pzbuffer[ofs])

	{

		int		pix;

		d_pzbuffer[ofs] = new[5];

		pix = skintable[new[3]>>16][new[2]>>16];

//		pix = ((byte *)acolormap)[pix + (new[4] & 0xFF00)];

		d_viewbuffer[ofs] = pix;

	}

// recursively continue

	D_PolysetRecursiveDrawLine (lp1, new);

	D_PolysetRecursiveDrawLine (new, lp2);

}

void D_PolysetRecursiveTriangle2 (int *lp1, int *lp2, int *lp3)

{

	int		d;

	int		new[4];

	d = lp2[0] - lp1[0];

	if (d < -1 || d > 1)

		goto split;

	d = lp2[1] - lp1[1];

	if (d < -1 || d > 1)

		goto split;

	return;

split:

// split this edge

	new[0] = (lp1[0] + lp2[0]) >> 1;

	new[1] = (lp1[1] + lp2[1]) >> 1;

	new[5] = (lp1[5] + lp2[5]) >> 1;

	new[2] = (lp1[2] + lp2[2]) >> 1;

	new[3] = (lp1[3] + lp2[3]) >> 1;

	new[4] = (lp1[4] + lp2[4]) >> 1;

	D_PolysetRecursiveDrawLine (new, lp3);

// recursively continue

	D_PolysetRecursiveTriangle (lp1, new, lp3);

	D_PolysetRecursiveTriangle (new, lp2, lp3);

}

#endif