/* Span based drawing tools V1.13 12/9/04
   See spandraw.h for docs
   Copyright 2008 Jeffrey Lee
   This file is part of WOUM.
   WOUM 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 3 of the License, or
   (at your option) any later version.
   WOUM 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 WOUM.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef _SPANDRAW_C
#define _SPANDRAW_C

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

/*#define AMDL_DEBUG*/

#include "spandraw.h"
#include "error.h"

/* Row list stuff */

typedef struct {
	int lx,rx; /* Left, right points (inclusive) */
	invz iz; /* 1/Z value of lx */
} row;

static row *rows = 0;
static int numrows = 0; /* To check whether the mode has changed since the last use */
static int rowmin,rowmax; /* Min,max rows written to */

static void allocrows()
{
	if (rows)
		free(rows);
	numrows = span_lines;
	rows = malloc(sizeof(row)*numrows);
}

/* Temp verticies and arrays used during clipping */

static vec16 intvecs[16]; /* Temporary verticies */
static int intvecpos; /* Next free location in intvecs */
static vec16 *cvert1[MAXVERT+16]; /* Temp vertex ptr arrays */
static vec16 *cvert2[MAXVERT+16];
static int cvertpos; /* Current pos in current array */

#define ABS(x) ((x) < 0 ? (-x) : (x))
/* Clipping code */

/* Big macro */
#define CLIPCODE(FROM,TO,DIM,POS,OFFCMP,ONCMP) \
cvertpos = 0;\
for (pos=0;pos<nvert;pos++)\
{\
	next = pos+1;\
	if (next == nvert)\
		next = 0;\
	if (FROM[pos]->DIM ONCMP POS)\
	{\
		TO[cvertpos++] = FROM[pos];\
		if (FROM[next]->DIM OFFCMP POS)\
		{\
			vec16_fmoveto ## DIM(FROM[pos],FROM[next],POS,&intvecs[intvecpos]);\
			TO[cvertpos++] = &intvecs[intvecpos++];\
		}\
	}\
	else if (FROM[next]->DIM ONCMP POS)\
	{\
		vec16_fmoveto ## DIM(FROM[pos],FROM[next],POS,&intvecs[intvecpos]);\
		TO[cvertpos++] = &intvecs[intvecpos++];\
	}\
	if (intvecpos >= 15)\
		error("intvecpos overflow");\
	if (cvertpos >= MAXVERT+16)\
		error("cvertpos overflow");\
}\
nvert = cvertpos;
/* Perspective clipping code */
#define PCLIPCODE(FROM,TO,DIM,SIGN,NEG,ODIM) \
cvertpos = 0;\
for (pos=0;pos<nvert;pos++)\
{\
	next = pos+1;\
	if (next == nvert)\
		next = 0;\
	if (SIGN(FROM[pos]->DIM) <= FROM[pos]->z)\
	{\
		TO[cvertpos++] = FROM[pos];\
		if (SIGN(FROM[next]->DIM) > FROM[next]->z)\
		{\
			if (SIGN(FROM[next]->DIM) < FROM[next]->z + 256)\
			{\
				intvecs[intvecpos].x = FROM[next]->x;\
				intvecs[intvecpos].y = FROM[next]->y;\
				intvecs[intvecpos].z = FROM[next]->z;\
				intvecs[intvecpos].DIM = SIGN FROM[next]->z;\
			}\
			else\
			vec16_pmoveto ## DIM(FROM[pos],FROM[next],NEG,&intvecs[intvecpos]);\
			TO[cvertpos++] = &intvecs[intvecpos++];\
		}\
	}\
	else if (SIGN(FROM[next]->DIM) <= FROM[next]->z)\
	{\
		if (SIGN(FROM[pos]->DIM) < FROM[pos]->z + 256)\
		{\
			intvecs[intvecpos].x = FROM[pos]->x;\
			intvecs[intvecpos].y = FROM[pos]->y;\
			intvecs[intvecpos].z = FROM[pos]->z;\
			intvecs[intvecpos].DIM = SIGN FROM[pos]->z;\
		}\
		else\
		vec16_pmoveto ## DIM(FROM[pos],FROM[next],NEG,&intvecs[intvecpos]);\
		TO[cvertpos++] = &intvecs[intvecpos++];\
	}\
	if (intvecpos >= 15)\
		error("intvecpos overflow");\
	if (cvertpos >= MAXVERT+16)\
		error("cvertpos overflow");\
}\
nvert = cvertpos;

static void clip(int nvert,vec16 **verts)
{
	/* Perform X, Y and Z clipping on the polygon given */
	/* Returns results in cvert2, with cvertpos as the number of verticies */
	int pos,next;
	f1616 mx,my;
	mx = f1616_FromInt(span_width-1);
	my = f1616_FromInt(span_lines-1);
	if (intvecpos < 0)
		intvecpos = -intvecpos; /* Revert flag state, to preserve current vectors */
	else
		intvecpos = 0; /* Else no internal vectors used */
	/* X=0 clipping */
	CLIPCODE(verts,cvert1,x,0,<,>=)
	/* X=screen width */
	CLIPCODE(cvert1,cvert2,x,mx,>,<=)
	/* Y=0 */
	CLIPCODE(cvert2,cvert1,y,0,<,>=)
	/* Y=screen height */
	CLIPCODE(cvert1,cvert2,y,my,>,<=)
	/* Z=CLOSEST_Z */
	CLIPCODE(cvert2,cvert1,z,CLOSEST_Z,<,>=)
	/* Z=FARTHEST_Z */
	CLIPCODE(cvert1,cvert2,z,FARTHEST_Z,>,<=)
	/* Brute force clipping to ensure all points are valid
	   Problem doesn't seem to lie in this code though, so this should be OK */
#ifdef PARANOID
	for (pos=0;pos<nvert;pos++)
	{
		if (cvert2[pos]->x < 0)
		{
			warning("LX");
			cvert2[pos]->x = 0; /* Safe to modify, since any points remaining outside are ones which we (attempted to) clip earlier */
		}
		else if (cvert2[pos]->x > mx)
		{
			warning("RX");
			cvert2[pos]->x = mx;
		}
		if (cvert2[pos]->y < 0)
		{
			warning("TY");
			cvert2[pos]->y = 0;
		}
		else if (cvert2[pos]->y > my)
		{
			warning("BY");
			cvert2[pos]->y = my;
		}
		/* Z clipping is only decorative, so don't bother checking it */
	}
#endif
}

/* Polygon insertion */

/* Return gradient - steps of o per s (int or float) */
#define GRAD(oa,ob,s) (s ? (ob-oa)/s : 0)

/* Insert a series of entries for a left hand edge */
static void sel_insert(vec16 *a,vec16 *b,invz *iz,invz izpx,invz izpy)
{
	int x,y,x2,xd,yd,xdir; /* General vars needed */
	int err,einc,eover,mlen; /* Error values and main line length */
	y = a->y >> 16;
	yd = (b->y >> 16)-y;
	if (yd <= 0)
	{
		if (yd == 0)
			*iz += ((b->x >> 16)-(a->x >> 16))*izpx; /* Ensure polys with flat tops are done properly */
		return; /* Horizontal or upside down */
	}
	/* Else valid */
	x = a->x >> 16;
	x2 = b->x >> 16;
	xd = x2-x;
	if (xd < 0)
	{
		xdir = -1;
		xd = -xd;
		izpx = -izpx;
	}
	else
		xdir = 1;
	if (rowmin>y) /* Adjust min/max values */
		rowmin=y;
	if (rowmax<y+yd)
		rowmax=y+yd;
	if (xd>=yd)
	{
		/* X major */
		mlen = xd/yd;
		eover = 2*yd;
		einc = 2*(xd-mlen*yd); /* (xd % yd)*2 */
		err = 0; /* This needs adjusting! */
		while (yd--)
		{
			err += einc;
			if (err >= eover)
			{
				err -= eover;
				x+=xdir; /* Extra pixel */
				*iz+=izpx;
			}
			x+=xdir*mlen;
			*iz+=mlen*izpx;
			/* Now place entry */
			rows[y].lx = x;
			rows[y++].iz = *iz;
			*iz+=izpy; /* Move down a line */
		}
	}
	else
	{
		/* Y major */
		if (xd)
		{
			mlen = yd/xd;
			eover = 2*xd;
			einc = 2*(yd-mlen*xd);
		}
		else
		{
			einc = 0; /* Handle vertical lines */
			eover = 1;
			mlen = yd;
			xd++; /* Ensure it runs through once */
		}
		err = 0;
		while (xd--)
		{
			err += einc;
			x2 = mlen; /* temp var */
			if (err >= eover)
			{
				err -= eover;
				x2++;
			}
			while (x2--)
			{
				rows[y].lx = x;
				rows[y++].iz = *iz;
				*iz+=izpy;
			}
			x+=xdir; /* Move across */
			*iz+=izpx;
		}
	}
}

/* Insert a series of entries for a right hand edge */
static void ser_insert(vec16 *a,vec16 *b)
{
	int x,y,x2,xd,yd,xdir; /* General vars needed */
	int err,einc,eover,mlen; /* Error values and main line length */
	y = a->y >> 16;
	yd = (b->y >> 16)-y;
	if (yd <= 0)
		return; /* Horizontal or upside down */
	/* Else valid */
	x = (a->x >> 16)-1;
	x2 = (b->x >> 16)-1;
	xd = x2-x;
	if (xd < 0)
	{
		xdir = -1;
		xd = -xd;
	}
	else
		xdir = 1;
	if (rowmin>y) /* Adjust min/max values */
		rowmin=y;
	if (rowmax<y+yd)
		rowmax=y+yd;
	if (xd>=yd)
	{
		/* X major */
		mlen = xd/yd;
		eover = 2*yd;
		einc = 2*(xd-mlen*yd);
		err = 0; /* This needs adjusting! */
		while (yd--)
		{
			err += einc;
			if (err >= eover)
			{
				err -= eover;
				x+=xdir;
			}
			x+=xdir*mlen;
			/* Now place entry */
			rows[y++].rx = x;
		}
	}
	else
	{
		/* Y major */
		if (xd)
		{
			mlen = yd/xd;
			eover = 2*xd;
			einc = 2*(yd-mlen*xd);
		}
		else
		{
			einc = 0; /* Handle vertical lines */
			eover = 1;
			mlen = yd;
			xd++; /* Ensure it runs through once */
		}
		err = 0;
		while (xd--)
		{
			err += einc;
			if (err >= eover)
			{
				err -= eover;
				rows[y++].rx = x;
			}
			x2 = mlen; /* temp var */
			while (x2--)
				rows[y++].rx = x;
			x+=xdir; /* Move across */
		}
	}
}

/* Version of vec<x>_toplane that returns a long long vector, to avoid overflows */
typedef struct {
	signed long long x,y,z; /* 34.30 format */
} vecll;

#define X1 ((signed long long) v1->x)
#define X2 ((signed long long) v2->x)
#define X3 ((signed long long) v3->x)
#define Y1 ((signed long long) v1->y)
#define Y2 ((signed long long) v2->y)
#define Y3 ((signed long long) v3->y)
#define Z1 ((signed long long) v1->z)
#define Z2 ((signed long long) v2->z)
#define Z3 ((signed long long) v3->z)

#define SH(X) ((X) >> 2)

static f4816 _toplane(vec16 *v1,vec16 *v2,vec16 *v3,vecll *p)
{
	if ((v1->z == v2->z) && (v1->z == v3->z))
		p->x = p->y = 0; /* Flat poly */
	else
	{
		p->x = SH(Y1*(Z2-Z3)) + SH(Y2*(Z3-Z1)) + SH(Y3*(Z1-Z2));
		p->y = SH(Z1*(X2-X3)) + SH(Z2*(X3-X1)) + SH(Z3*(X1-X2));
	}
	p->z = SH(X1*(Y2-Y3)) + SH(X2*(Y3-Y1)) + SH(X3*(Y1-Y2));
	return -(f4816_mul(X1,(Y2*Z3 - Y3*Z2) >> 16)
	       + f4816_mul(X2,(Y3*Z1 - Y1*Z3) >> 16)
	       + f4816_mul(X3,(Y1*Z2 - Y2*Z1) >> 16));
}

#undef SH

#undef X1
#undef X2
#undef X3
#undef Y1
#undef Y2
#undef Y3
#undef Z1
#undef Z2
#undef Z3

/* This code assumes perspective projection! */

#include "amdl.h"

/*#define amdl_vert(M,C,V) amdl_ ## M ## (C,"{%f,%f,%f}",((float) (V)->x)/65536,((float) (V)->y)/65536,((float) (V)->z)/65536)*/
#define amdl_vert(M,C,V) amdl_ ## M ## (C,"{%08x,%08x,%08x}",(V)->x,(V)->y,(V)->z)
#define amdl_verts(M,C,V) for (cvertpos=0;cvertpos<nvert;cvertpos++) amdl_vert(M,C,V[cvertpos])

int span_addpoly(int nvert,vec16 **verts,int col,tmat16 *tran)
{
	/* General point/line/poly add code */
	/* 1. perform modelview transformation on verticies
	   2. calculate plane equation if polygon
	   3. do backfacing check
	   4. perform x,y,z clipping on verticies
	   5. perform perspective
	   6. scale up to viewport
	   7. find topmost vertex, to use as z anchor
	   8. branch off if point or line
	   9. calculate z gradients
	   10. add edges to row list
	   11. add row-by-row to span buffer
	*/
	vec16 verts2[nvert]; /* Array of verticies we are allowed to modify */
	int pos,next; /* Used during clipping code */
	f1616 mx,my; /* Max X and Y locations used during clipping */
	vecll nrm; /* Polygon normal */
	invz izpx,izpy,z; /* Z change per X & Y, z anchor */
	int top,y; /* Topmost vertex, and current y in scan conversion */
	int tmp,clipflags; /* temp value and clipping-needed flags */
	vec16 **curv,**nextv,**tempv; /* pointers to the vertex arrays in use */
#define CF_LX 1
#define CF_RX 2
#define CF_TY 4
#define CF_BY 8
#define CF_NZ 16
#define CF_FZ 32
	f4816 d;
	tmp = nvert; /* Cache original number of verticies (since clipping code may turn lines into polys) */
	clipflags = 0;
	/* Step 1 */
	if (tran)
		for (pos=0;pos<nvert;pos++)
		{
			tmat16_dotprod(tran,verts[pos],&(verts2[pos]));
			cvert2[pos] = &(verts2[pos]);
			if (cvert2[pos]->z < CLOSEST_Z)
				clipflags |= CF_NZ;
			else if (cvert2[pos]->z > FARTHEST_Z)
				clipflags |= CF_FZ;
		}
	else
		for (pos=0;pos<nvert;pos++)
		{
			verts2[pos] = *(verts[pos]); /* No transformation (Still need to copy vec though) */
			cvert2[pos] = &(verts2[pos]);
			if (cvert2[pos]->z < CLOSEST_Z)
				clipflags |= CF_NZ;
			else if (cvert2[pos]->z > FARTHEST_Z)
				clipflags |= CF_FZ;
		}
	/* Steps 2, 3 */
	if (tmp > 2)
	{
		d = _toplane(cvert2[0],cvert2[1],cvert2[2],&nrm); /* First 3 points should be valid as no clipping has occured yet */
		if (d > 0)
			return SPAN_WRONGWAYROUND;
	}
	else
		d = 0;
#ifdef AMDL_DEBUG
	amdl_abs(13,"---");
	amdl_verts(abs,13,cvert2);
	amdl_vert(abs,14,&nrm);
/*	amdl_abs(15,"%f",((float) d)/65536);*/
	amdl_abs(15,"%016llx",d);
#endif
	/* Step 4 */
	intvecpos = 0;
	curv = cvert2;
	nextv = cvert1;
	/* Z=CLOSEST_Z */
	if (clipflags & CF_NZ)
	{
		CLIPCODE(curv,nextv,z,CLOSEST_Z,<,>=) /* Shouldn't cause x/y clipping to be required */
		tempv=curv; curv=nextv; nextv=tempv;
#ifdef AMDL_DEBUG
		amdl_abs(18,"---");
		amdl_verts(abs,18,curv);
#endif
	}
	/* Z=FARTHEST_Z */
	if (clipflags & CF_FZ)
	{
		CLIPCODE(curv,nextv,z,FARTHEST_Z,>,<=)
		tempv=curv; curv=nextv; nextv=tempv;
#ifdef AMDL_DEBUG
		amdl_abs(19,"---");
		amdl_verts(abs,19,curv);
#endif
	}
	/* Perspective clipping against X/Y
	   Can only check this after the Z clipping, because negative Z values
	   are too tricky to catch */
	for (pos=0;pos<nvert;pos++)
	{
		if (curv[pos]->x > curv[pos]->z)
			clipflags |= CF_RX;
		else if (-curv[pos]->x > curv[pos]->z)
			clipflags |= CF_LX;
		if (curv[pos]->y > curv[pos]->z)
			clipflags |= CF_BY;
		else if (-curv[pos]->y > curv[pos]->z)
			clipflags |= CF_TY;
	}
	if (clipflags & CF_RX)
	{
		PCLIPCODE(curv,nextv,x,+,0,y)
		tempv=curv; curv=nextv; nextv=tempv;
#ifdef AMDL_DEBUG
		amdl_abs(20,"---");
		amdl_verts(abs,20,curv);
#endif
	}
	if (clipflags & CF_LX)
	{
		PCLIPCODE(curv,nextv,x,-,1,y)
		tempv=curv; curv=nextv; nextv=tempv;
#ifdef AMDL_DEBUG
		amdl_abs(21,"---");
		amdl_verts(abs,21,curv);
#endif
	}
	if (clipflags & CF_BY)
	{
		PCLIPCODE(curv,nextv,y,+,0,x)
		tempv=curv; curv=nextv; nextv=tempv;
#ifdef AMDL_DEBUG
		amdl_abs(22,"---");
		amdl_verts(abs,22,curv);
#endif
	}
	if (clipflags & CF_TY)
	{
		PCLIPCODE(curv,nextv,y,-,1,x)
		curv=nextv;
#ifdef AMDL_DEBUG
		amdl_abs(23,"---");
		amdl_verts(abs,23,curv);
#endif
	}
	if (nvert <= 0)
		return SPAN_OFFSCREEN;
	if (curv != cvert2)
		for (pos=0;pos<nvert;pos++)
			cvert2[pos] = cvert1[pos]; /* Ensure we're using cvert2, to simplify following code */
	/* Steps 5,6,7 */
	mx = f1616_FromInt(span_width); /* Absolute maximum */
	my = f1616_FromInt(span_lines);
	top = 0;
	for (pos=0;pos<nvert;pos++)
	{
		cvert2[pos]->x = (f1616_div(cvert2[pos]->x,cvert2[pos]->z)+0x10000)*(span_width/2); /* [+1,-1] to [span_width,0] */
		cvert2[pos]->y = (f1616_div(cvert2[pos]->y,cvert2[pos]->z)+0x10000)*(span_lines/2);
		if (cvert2[pos]->x > mx) /* Perspective clipping code appears to cause a problem or two */
			cvert2[pos]->x = mx;
		if (cvert2[pos]->y > my)
			cvert2[pos]->y = my;
		if (cvert2[pos]->y < cvert2[top]->y)
			top = pos;
	}
#ifdef AMDL_DEBUG
	amdl_abs(24,"---");
	amdl_verts(abs,24,cvert2);
#endif
	/* Step 8 */
	if (tmp == 1)
		return span_addpart(cvert2[0],col);
	if (tmp == 2)
	{
		intvecpos = -1; /* Special flag state to prevent addline doing clipping, since we've already done it */
		return span_addline(cvert2[0],cvert2[1],col);
	}
	/* Step 9 */
	izpx = calc_izgrad(((int) INVZ_ACCURACY)/0x4000,span_width,&d,&nrm.x);
	izpy = calc_izgrad(((int) INVZ_ACCURACY)/0x4000,span_lines,&d,&nrm.y);
#ifdef AMDL_DEBUG
	amdl_abs(16,"%08x",izpx);
	amdl_abs(17,"%08x",izpy);
#endif
#ifdef PARANOID
	for (pos=0;pos<nvert;pos++)
	{
		if (cvert2[pos]->x < 0)
		{
			warning("LX");
			cvert2[pos]->x = 0;
		}
		else if (cvert2[pos]->x > mx)
		{
			warning("RX");
			cvert2[pos]->x = mx;
		}
		if (cvert2[pos]->y < 0)
		{
			warning("TY");
			cvert2[pos]->y = 0;
		}
		else if (cvert2[pos]->y > my)
		{
			warning("BY");
			cvert2[pos]->y = my;
		}
		/* Z clipping is only decorative, so don't bother checking it */
	}
#endif
	/* Step 10 */
	rowmin = span_lines;
	rowmax = 0;
	if (numrows != span_lines)
		allocrows();
	/* Need to add all edges, in both directions, starting from 'top' */
	/* This is a bit wasteful since each edge should only fall onto one side, so half the number of calls made are wasted */
	/* Add right edges */
	for (y=top;y<nvert-1;y++)
		ser_insert(cvert2[y],cvert2[y+1]); /* top --> nvert */
	ser_insert(cvert2[nvert-1],cvert2[0]); /* nvert --> 0 */
	for (y=0;y<top;y++)
		ser_insert(cvert2[y],cvert2[y+1]); /* 0 --> top */
	/* Add left edges */
	z = F16_TO_INVZ(cvert2[top]->z);
	for (y=top;y>0;y--)
		sel_insert(cvert2[y],cvert2[y-1],&z,izpx,izpy); /* top --> 0 */
	sel_insert(cvert2[0],cvert2[nvert-1],&z,izpx,izpy); /* 0 --> nvert */
	for (y=nvert-1;y>top;y--)
		sel_insert(cvert2[y],cvert2[y-1],&z,izpx,izpy); /* nvert --> top */
	/* Step 11 */
	y = rowmin; /* Start at this height */
	pos = SPAN_OCCLUDED; /* Default return code */
	while (y<rowmax) /* While not at end of list */
	{
#ifdef PARANOID
		if (y >= span_lines)
		{
			warning("Off bottom (%d)",y);
			return SPAN_OFFSCREEN;
		}
		if (y < 0)
			warning("Off top (%d)",y);
		else
#endif
		if (span_add(rows[y].lx,rows[y].rx,rows[y].iz,izpx,col,y) == SPAN_OK)
			pos = SPAN_OK;
		y++;
	}
	return pos;
}

#undef CLIPCODE
#undef PCLIPCODE

/* Particle insertion */

int span_addpart(vec16 *a,int col)
{
	/* Just add as 1-length span */
	if ((a->x < 0) || (a->x >= f1616_FromInt(span_width)))
		return SPAN_OFFSCREEN;
	if ((a->y < 0) || (a->y >= f1616_FromInt(span_lines)))
		return SPAN_OFFSCREEN;
	if ((a->z < CLOSEST_Z) || (a->z >= FARTHEST_Z))
		return SPAN_OFFSCREEN;
	return span_add(f1616_ToInt(a->x),f1616_ToInt(a->x),F16_TO_INVZ(a->z),0,col,f1616_ToInt(a->y));
}

/* Line insertion */

static inline int span_addline_seg(int *x,int y,int len,int dir,invz *iz,invz izgrad,int col)
{
	int rt;
	if (len < 1)
		return SPAN_WRONGWAYROUND;
	if (dir == 1)
	{
		rt = span_add(*x,(*x)+(len-1),*iz,izgrad,col,y);
		*x += len;
		*iz += len*izgrad;
	}
	else
	{
		rt = span_add((*x)-(len-1),*x,(*iz)+((len-1)*izgrad),izgrad,col,y);
		*x -= len;
		*iz += len*izgrad; /* Should be correct */
	}
	return rt;
}

static inline int span_addvline_seg(int x,int *y,int len,invz *iz,invz izgrad,int col)
{
	int rt = SPAN_WRONGWAYROUND;
	int rt2;
	while (len-- > 0)
	{
		rt2 = span_add(x,x,*iz,izgrad,col,(*y)++);
		*iz += izgrad;
		if (rt2 < rt)
			rt = rt2;
	}
	return rt;
}

int span_addline(vec16 *a,vec16 *b,int col)
{
	vec16 *tmp;
	int x,y,x2,y2,xd,yd; /* Integer versions of coords and deltas */
	int xdir,einc,eover,err; /* X advance dir, error inc, error overflow, error val */
	int mlen,ilen,flen; /* Main, initial and final lengths */
	invz izgrad; /* Z gradient per major unit */
	invz iz; /* Current Z val */
	int rt,rt2; /* Running return code value */
	/* Try normal poly clipping code */
	if (intvecpos >= 0) /* ... but not if <0, since that means clipping has been done already and the points are already cvert2[0] and cvert2[1] */
	{
		cvert2[0] = a; /* Rely on clip not using cvert2 for 1st clipping op */
		cvert2[1] = b;
		clip(2,cvert2);
		if (cvertpos < 2) /* Don't check for >2 since the clipping code does add extra verticies */
			return SPAN_WRONGWAYROUND;
		a = cvert2[0];
		b = cvert2[1];
	}
	else
		intvecpos = 0; /* Reset flag */
	if (b->y < a->y)
	{
		tmp = a;
		a = b;
		b = tmp;
	}
	x = f1616_ToInt(a->x);
	y = f1616_ToInt(a->y);
	x2 = f1616_ToInt(b->x);
	y2 = f1616_ToInt(b->y);
	xd = x2-x;
	yd = y2-y;
	if (xd == 0)
	{
		/* Vertical */
		iz = F16_TO_INVZ(a->z); /* Because vline changes this */
		return span_addvline_seg(x,&y,yd,&iz,GRAD(iz,F16_TO_INVZ(b->z),yd),col);
	}
	if (xd < 0)
	{
		xdir = -1;
		xd = -xd;
	}
	else
		xdir = 1;
	if (yd == 0)
	{
		/* Horizontal */
		iz = F16_TO_INVZ(a->z);
		return span_addline_seg(&x,y,xd,xdir,&iz,GRAD(iz,F16_TO_INVZ(b->z),xd),col);
	}
	/* Else some kind of diagonal */
	if (xd > yd)
	{
		/* X major */
		einc = (xd % yd)*2;
		eover = 2*yd;
		err = einc/2;
		mlen = xd/yd;
		ilen = mlen/2 + 1;
		flen = ilen;
		iz = F16_TO_INVZ(a->z);
		izgrad = GRAD(iz,F16_TO_INVZ(b->z),xd);
		if (((mlen & 1) == 0) && (einc == 0))
			ilen--;
		else if (mlen & 1)
			err += eover/2;
		rt = span_addline_seg(&x,y++,ilen,xdir,&iz,izgrad,col);
		yd--;
		while (yd>0)
		{
			err += einc;
			if (err >= eover)
			{
				rt2 = span_addline_seg(&x,y++,mlen+1,xdir,&iz,izgrad,col);
				err -= eover;
			}
			else
				rt2 = span_addline_seg(&x,y++,mlen,xdir,&iz,izgrad,col);
			yd--;
			if (rt2 < rt)
				rt = rt2;
		}
		rt2 = span_addline_seg(&x,y,flen,xdir,&iz,izgrad,col);
		return (rt<rt2?rt:rt2);
	}
	/* Else Y major */
	einc = (yd % xd)*2;
	eover = 2*xd;
	err = einc/2;
	mlen = yd/xd;
	ilen = mlen/2 + 1;
	flen = ilen;
	iz = F16_TO_INVZ(a->z);
	izgrad = GRAD(iz,F16_TO_INVZ(b->z),yd);
	if (((mlen & 1) == 0) && (einc == 0))
		ilen--;
	else if (mlen & 1)
		err += eover/2;
	rt = span_addvline_seg(x,&y,ilen,&iz,izgrad,col);
	x+=xdir;
	xd--;
	while (xd>0)
	{
		err += einc;
		if (err >= eover)
		{
			rt2 = span_addvline_seg(x,&y,mlen+1,&iz,izgrad,col);
			err -= eover;
		}
		else
			rt2 = span_addvline_seg(x,&y,mlen,&iz,izgrad,col);
		x+=xdir;
		xd--;
		if (rt2 < rt)
			rt = rt2;
	}
	rt2 = span_addvline_seg(x,&y,flen,&iz,izgrad,col);
	return (rt<rt2?rt:rt2);
}

#undef GRAD

/* Rectangle insertion */

int span_addrect(int lx,int rx,int ty,int by,f1616 z,int col)
{
	int iz;
	int rc;
	/* Perform clipping */
	if (lx < 0)
		lx = 0;
	else if (lx >= span_width)
		return SPAN_OFFSCREEN;
	if (rx >= span_width)
		rx = span_width-1;
	else if (rx < 0)
		return SPAN_OFFSCREEN;
	if (ty < 0)
		ty = 0;
	else if (ty >= span_lines)
		return SPAN_OFFSCREEN;
	if (by >= span_lines)
		by = span_lines-1;
	else if (by < 0)
		return SPAN_OFFSCREEN;
	/* Ignore Z clipping since this function may be used to set up areas to redraw/not redraw (and hence require close z values) */
	if ((lx > rx) || (ty > by))
		return SPAN_WRONGWAYROUND;
	iz = F16_TO_INVZ(z);
	rc = SPAN_OCCLUDED;
	while (ty <= by)
		if (span_add(lx,rx,iz,0,col,ty++) == SPAN_OK)
			rc = SPAN_OK;
	return rc;
}

/* Circle insertion */

int span_addcirc(int x,int y,f1616 z,int radius,int col)
{
	int yoff,xoff,tmp,iz;
	int rc;
	/* Perform simple Z clipping */
	if (z < CLOSEST_Z)
		return SPAN_OFFSCREEN;
	if (z > FARTHEST_Z)
		return SPAN_OFFSCREEN;
	yoff = -radius;
	iz = F16_TO_INVZ(z);
	if (y+yoff < 0) /* Clip to top of screen */
		yoff = -y;
	rc = SPAN_OCCLUDED;
	while ((yoff <= radius) && (y+yoff < span_lines)) /* Clip to circle & top of screen */
	{
		xoff = int_sqrt(((radius*radius)-(yoff*yoff))*4)/2; /* Increase the accuracy a bit, since int_sqrt is a bit poor atm */
		tmp = x-xoff; /* Left pos */
		xoff = x+xoff; /* Right pos */
		/* X clipping */
		if (tmp < 0)
			tmp = 0;
		if (xoff >= span_width)
			xoff = span_width-1;
		if (tmp <= xoff)
			if (span_add(tmp,xoff,iz,0,col,y+yoff) == SPAN_OK)
				rc = SPAN_OK;
		yoff++;
	}
	return rc;
}

#endif
