/* 3rd (5th or 6th, actually) attempt, this time using barycentric coordinates with proper edge-clamping */

void yTraceTriangleLightmap_3( dsurface_t *ds, drawVert_t *dv[ 3 ], int luxelsWidth, int luxelsHeight, float *luxels, traceWork_t *tw )
{
	int			i, j, x, y, mins[ 2 ], maxs[ 2 ];
	bVert_t		bv[ 3 ];
	double		ib, it;
	float		fx, fy, bary[ 3 ], clamp[ 3 ], lm[ 2 ], dist[ 2 ];
	int			a, b, c;
	vec3_t		origin, normal;
	float		*luxel;
	
	
	/* create bverts from the drawverts */
	mins[ 0 ] = mins[ 1 ] = 99999;
	maxs[ 0 ] = maxs[ 1 ] = -99999;
	for( i = 0; i < 3; i++ )
	{
		/* copy the relevant data */
		VectorCopy( dv[ i ]->xyz, bv[ i ].xyz );
		VectorCopy( dv[ i ]->normal, bv[ i ].normal );
		bv[ i ].lm[ 0 ] = dv[ i ]->lightmap[ 0 ] * luxelsWidth;
		bv[ i ].lm[ 1 ] = dv[ i ]->lightmap[ 1 ] * luxelsHeight;
		
		/* expand bounds */
		for( j = 0; j < 2; j++ )
		{
			if( (bv[ i ].lm[ j ] - 0.5) < mins[ j ] )
				mins[ j ] = (bv[ i ].lm[ j ] - 0.5);
			if( (bv[ i ].lm[ j ] + 0.5) > maxs[ j ] )
				maxs[ j ] = (bv[ i ].lm[ j ] + 0.5);
		}
	}
	
	/* clamp bounds */
	if( mins[ 0 ] < 0 )
		mins[ 0 ] = 0;
	if( mins[ 1 ] < 0 )
		mins[ 1 ] = 0;
	if( maxs[ 0 ] > (luxelsWidth - 1) )
		maxs[ 0 ] = (luxelsWidth - 1);
	if( maxs[ 1 ] > (luxelsHeight - 1) )
		maxs[ 1 ] = (luxelsHeight - 1);
	
	/* calculate inverse baricentric divisor */
	ib = 1.0 / ((bv[ 1 ].lm[ 0 ] - bv[ 0 ].lm[ 0 ]) * (bv[ 2 ].lm[ 1 ] - bv[ 0 ].lm[ 1 ]) -
				(bv[ 2 ].lm[ 0 ] - bv[ 0 ].lm[ 0 ]) * (bv[ 1 ].lm[ 1 ] - bv[ 0 ].lm[ 1 ]));
	
	/* rasterize the triangle */
	for( y = mins[ 1 ]; y <= maxs[ 1 ]; y++ )
	{
		for( x = mins[ 0 ]; x <= maxs[ 0 ]; x++ )
		{
			/* make floating point coords */
			fx = 0.5 + x;
			fy = 0.5 + y;
			
			/* calculate barycentric coordinates for this sample (fixme: optimize this) */
			bary[ 0 ] = ib * ((bv[ 1 ].lm[ 0 ] - fx) * (bv[ 2 ].lm[ 1 ] - fy) -
							  (bv[ 2 ].lm[ 0 ] - fx) * (bv[ 1 ].lm[ 1 ] - fy));
			bary[ 1 ] = ib * ((bv[ 2 ].lm[ 0 ] - fx) * (bv[ 0 ].lm[ 1 ] - fy) -
							  (bv[ 0 ].lm[ 0 ] - fx) * (bv[ 2 ].lm[ 1 ] - fy));
			bary[ 2 ] = ib * ((bv[ 0 ].lm[ 0 ] - fx) * (bv[ 1 ].lm[ 1 ] - fy) -
							  (bv[ 1 ].lm[ 0 ] - fx) * (bv[ 0 ].lm[ 1 ] - fy));
			
			/* make positive edge flags */
			a = (bary[ 0 ] > 0);
			b = (bary[ 1 ] > 0);
			c = (bary[ 2 ] > 0);
			
			/* make clamped barycentric coords */
			if( a && b && c )
				VectorCopy( bary, clamp );		/* fully inside triangle */
			else if( !a && !b && !c )			/* this case should never happen */
				continue;
			else if( !b && !c )
				VectorSet( clamp, 1.0, 0, 0 );	/* clamp to a */
			else if( !a && !c )
				VectorSet( clamp, 0, 1.0, 0 );	/* clamp to b */
			else if( !a && !b )
				VectorSet( clamp, 0, 0, 1.0 );	/* clamp to c */
			
			else if( !a )
				VectorSet( clamp, 0, bary[ 1 ] + bary[ 0 ] * 0.5, bary[ 2 ] + bary[ 0 ] * 0.5 );
			
			else if( !b )
				VectorSet( clamp, bary[ 0 ] + bary[ 1 ] * 0.5, 0, bary[ 2 ] + bary[ 1 ] * 0.5 );

			else if( !c )
				VectorSet( clamp, bary[ 0 ] + bary[ 2 ] * 0.5, bary[ 1 ] + bary[ 2 ] * 0.5, 0 );
			
			
			/* renormalize the clamped coordinate */
			it = (clamp[ 0 ] + clamp[ 1 ] + clamp[ 2 ]);
			it = 1.0 / it;
			VectorScale( clamp, it, clamp );
			
			/* calculate clamped lightmap coordinates */
			lm[ 0 ] = lm[ 1 ] = 0;
			for( i = 0; i < 3; i++ )
			{
				lm[ 0 ] += clamp[ i ] * bv[ i ].lm[ 0 ];
				lm[ 1 ] += clamp[ i ] * bv[ i ].lm[ 1 ];
			}
			
			/* if the two coordinates are further than the diagonal of one luxel apart, then bail */
			dist[ 0 ] = lm[ 0 ] - fx;
			dist[ 1 ] = lm[ 1 ] - fy;
			dist[ 0 ] *= dist[ 0 ];
			dist[ 1 ] *= dist[ 1 ];
			it = sqrt( dist[ 0 ] + dist[ 1 ] );
			if( it > 8.0 )
			{
				/* find luxel */
				luxel = luxels + (((y * luxelsWidth) + x) * 3);
				
				/* store out-of gamut value */
				if( luxel[ 0 ] || luxel[ 1 ] || luxel[ 2 ] )
					continue;
				/* debugging code */
				if( it < 2 )
					printf( "b[%1.2f %1.2f %1.2f] c[%1.2f %1.2f %1.2f] xy[%3d %3d] lm[%3.1f %3.1f] %2.1f\n",
						bary[ 0 ], bary[ 1 ], bary[ 2 ], clamp[ 0 ], clamp[ 1 ], clamp[ 2 ], x, y, lm[ 0 ], lm[ 1 ], it );
				luxel[ 0 ] = 255;
				luxel[ 1 ] = 255;
				luxel[ 2 ] = 255;
				continue;
			}
			
			/* calculate xyz and normal for this sample */
			VectorClear( origin );
			VectorClear( normal );
			for( i = 0; i < 3; i++ )
			{
				for( j = 0; j < 3; j++ )
				{
					origin[ j ] += clamp[ i ] * bv[ i ].xyz[ j ];
					normal[ j ] += clamp[ i ] * bv[ i ].normal[ j ];
				}
			}
			
			/* legitimize this sample */
			if( VectorNormalize( normal, normal ) )
			{
				/* find luxel */
				luxel = luxels + (((y * luxelsWidth) + x) * 3);
				
				/* get light for this sample */
				if( normalmap )
				{
					luxel[ 0 ] = normal[ 0 ] > 0 ? normal[ 0 ] * 255 : 1;
					luxel[ 1 ] = normal[ 1 ] > 0 ? normal[ 1 ] * 255 : 1;
					luxel[ 2 ] = normal[ 2 ] > 0 ? normal[ 2 ] * 255 : 1;
				}
				else
				{
					//LightingAtSample( cluster, ydv->xyz, ydv->normal, NULL, sample, testOcclusion, forceSunLight, tw );
					/* fixme: replace this hot pink shit */
					luxel[ 0 ] = 255;
					luxel[ 1 ] = 0;
					luxel[ 2 ] = 255;
				}
			}
		}
	}
}




/* second attempt, based on code i wrote back in 1997... */

/* this version has precision issues with nearly horizontal edges */

typedef struct tlVert_s
{
	vec3_t		origin;
	vec3_t		normal;
	float		lm[ 2 ];	/* in [0,luxelsWidth] or [0,luxelsHeight] range */
}
tlVert_t;

typedef struct tlEdge_s
{
	tlVert_t	start, end, delta;
}
tlEdge_t;


void TLVertAdd( tlVert_t *a, tlVert_t *b, tlVert_t *out )
{
	VectorAdd( a->origin, b->origin, out->origin );
	VectorAdd( a->normal, b->normal, out->normal );
	out->lm[ 0 ] = a->lm[ 0 ] + b->lm[ 0 ];
	out->lm[ 1 ] = a->lm[ 1 ] + b->lm[ 1 ];
}



void yTraceTriangleLightmap_2( dsurface_t *ds, drawVert_t *dv[ 3 ], int luxelsWidth, int luxelsHeight, float *luxels, traceWork_t *tw )
{
	int			i, t;
	tlVert_t	cursor, left, right, delta;
	tlEdge_t	edges[ 3 ], *edge;
	tlEdge_t	*leftEdge, *rightEdge, *oddEdge;
	float		min, max;
	
	
	
	/* fill out the edges */
	min = 99999;
	max = -99999;
	edge = edges;
	for( i = 0; i < 3; i++ )
	{
		int		start, end;
		float	height, gradient;
		
		
		/* do some setup */
		start = i;
		end = (i + 1) % 3;
		height = (dv[ end ]->lightmap[ 1 ] - dv[ start ]->lightmap[ 1 ]) * luxelsHeight;
		
		/* classify edge */
		if( height > 0 )
			gradient = 1.0 / height;	/* up -> down */
		if( height < 0 )
		{
			t = start;
			start = end;
			end = t;
			height = -height;
			gradient = 1.0 / height;	/* down -> up */
		}
		else
			gradient = 0;				/* horizontal edge */
		
		/* store start */
		VectorCopy( dv[ start ]->xyz, edge->start.origin );
		VectorCopy( dv[ start ]->normal, edge->start.normal );
		edge->start.lm[ 0 ] = dv[ start ]->lightmap[ 0 ] * luxelsWidth;
		edge->start.lm[ 1 ] = dv[ start ]->lightmap[ 1 ] * luxelsHeight;
		
		/* store end */
		VectorCopy( dv[ end ]->xyz, edge->end.origin );
		VectorCopy( dv[ end ]->normal, edge->end.normal );
		edge->end.lm[ 0 ] = dv[ end ]->lightmap[ 0 ] * luxelsWidth;
		edge->end.lm[ 1 ] = dv[ end ]->lightmap[ 1 ] * luxelsHeight;
		
		/* calc delta against lm[ 1 ] */
		VectorSubtract( edge->end.origin, edge->start.origin, edge->delta.origin );
		VectorScale( edge->delta.origin, gradient, edge->delta.origin );
		VectorSubtract( edge->end.normal, edge->start.normal, edge->delta.normal );
		VectorScale( edge->delta.normal, gradient, edge->delta.normal );
		edge->delta.lm[ 0 ] = (edge->end.lm[ 0 ] - edge->start.lm[ 0 ]) * gradient;
		edge->delta.lm[ 1 ] = Q_rint( height );
		
		/* stretch bounds */
		if( edge->start.lm[ 1 ] < min )
			min = edge->start.lm[ 1 ];
		if( edge->end.lm[ 1 ] > max )
			max = edge->end.lm[ 1 ];
		
		/* next edge->.. */
		edge++;
	}
	
	/* find odd edge out */
	oddEdge = NULL;
	printf( "%3.3f ", min );
	for( i = 0; i < 3; i++ )
	{
		if( edges[ i ].delta.lm[ 1 ] == 0 || (edges[ i ].start.lm[ 1 ] - min) > 0.0001 )
		{
			oddEdge = &edges[ i ];
			leftEdge = &edges[ (i + 1) % 3 ];
			rightEdge = &edges[ (i + 2) % 3 ];
			break;
		}
	}
	if( oddEdge == NULL )
	{
		leftEdge = &edges[ 0 ];
		rightEdge = &edges[ 1 ];
	}
	
	/* find initial left/right edges */
	//leftEdge = (oddEdge > edges ? oddEdge - 1 : edges);
	//rightEdge = (oddEdge < (edges + 2) ? oddEdge + 1 : edges);
	
	/* swap left and right based on slope & non-identical starting points */
	if( (leftEdge->start.lm[ 0 ] > rightEdge->start.lm[ 0 ]) ||
		(leftEdge->start.lm[ 0 ] == rightEdge->start.lm[ 0 ] && leftEdge->delta.lm[ 0 ] > rightEdge->delta.lm[ 0 ]) )
	{
		edge = leftEdge;
		leftEdge = rightEdge;
		rightEdge = edge;
	}
	
	/* rasterize the triangle */
	left = leftEdge->start;
	right = rightEdge->start;
	while( left.lm[ 1 ] < max )
	{
		float	width = right.lm[ 0 ] - left.lm[ 0 ], gradient = 1.0 / width;

		/* calc delta against lm[ 0 ] */
		VectorSubtract( right.origin, left.origin, delta.origin );
		VectorScale( delta.origin, gradient, delta.origin );
		VectorSubtract( right.normal, left.normal, delta.normal );
		VectorScale( edge->delta.normal, gradient, edge->delta.normal );
		delta.lm[ 0 ] = 1.0;
		delta.lm[ 1 ] = 0;
		
		/* rasterize the scanline */
		cursor = left;
		while( cursor.lm[ 0 ] < right.lm[ 0 ] )
		{
			vec3_t	normal;
			float	*luxel;
			int		lx, ly;
			
			
			/* legitimize this sample */
			if( VectorNormalize( cursor.normal, normal ) )
			{
				/* find luxel coords */
				lx = cursor.lm[ 0 ];
				ly = cursor.lm[ 1 ];
				luxel = luxels + (((ly * luxelsWidth) + lx) * 3);
				
				/* get light for this sample */
				if( normalmap )
				{
					luxel[ 0 ] = normal[ 0 ] > 0 ? normal[ 0 ] * 255 : 0;
					luxel[ 1 ] = normal[ 1 ] > 0 ? normal[ 1 ] * 255 : 0;
					luxel[ 2 ] = normal[ 2 ] > 0 ? normal[ 2 ] * 255 : 0;
				}
				else
				{
					/* fixme: replace this hot pink shit */
					luxel[ 0 ] = lx;
					luxel[ 1 ] = cursor.lm[ 1 ] - min;
					luxel[ 2 ] = 0;
				}
					//LightingAtSample( cluster, ydv->xyz, ydv->normal, NULL, sample, testOcclusion, forceSunLight, tw );
			}
			
			/* add delta */
			TLVertAdd( &cursor, &delta, &cursor );
		}
		
		/* add edge deltas to left and right */
		TLVertAdd( &left, &leftEdge->delta, &left );
		TLVertAdd( &right, &rightEdge->delta, &right );
		
		/* check for end-of edge */
		if( left.lm[ 1 ] >= leftEdge->end.lm[ 1 ] )
			leftEdge = oddEdge;
			
		if( right.lm[ 1 ] >= rightEdge->end.lm[ 1 ] )
			rightEdge = oddEdge;
		
		/* check for null case */
		if( leftEdge == NULL || rightEdge == NULL )
			break;
	}
	
	
	/*

	// original code, circa 1997

	
	// raster setup
	leftX = edge[ leftEdge ].startX;
	rightX = edge[ rightEdge ].startX;
	
	x = leftX >> SHIFT_AMOUNT;
	y = topY >> SHIFT_AMOUNT;
	
	bottomY >>= SHIFT_AMOUNT;			// re-shift the bottomY for the top->bottom raster loop
	
	
	// rasterize the fucker
	while( y < bottomY )
	{
		// set up initial pointers
		ptrOffset = y * data->rowBytes;
		ptrOffset += x << 1;
		
		rightXInt = rightX >> SHIFT_AMOUNT;
			
		destPixel = data->pixels + (ptrOffset >> 1) - 1;
		endRowPixel = destPixel + (rightXInt - x);
		
		
		// ****************************** begin inner loop ************************
		
		// draw a pixel row
		while( destPixel < endRowPixel )
		{	
			// draw the pixel
			*++destPixel = color;
		}
		
		// ******************************* end inner loop *************************
		
		
		
		// check edge ends
		if( y == edge[ leftEdge ].endY >> SHIFT_AMOUNT )
			leftEdge = oddEdge;
			
		if( y == edge[ rightEdge ].endY >> SHIFT_AMOUNT )
			rightEdge = oddEdge;
		
		
		// increment the edges
		leftX += edge[ leftEdge ].rowDx;
		rightX += edge[ rightEdge ].rowDx;
		
		x = leftX >> SHIFT_AMOUNT;
		
		// increment y
		++y;
	}*/
}










/* first attempt follows */



/*
yLerpDrawVertAmount()
variation on a theme from mesh.c
(doesn't normalize the normal)
*/

void yLerpDrawVertAmount( drawVert_t *a, drawVert_t *b, float amount, drawVert_t *out )
{
	out->xyz[0] = a->xyz[0] + amount * (b->xyz[0] - a->xyz[0]);
	out->xyz[1] = a->xyz[1] + amount * (b->xyz[1] - a->xyz[1]);
	out->xyz[2] = a->xyz[2] + amount * (b->xyz[2] - a->xyz[2]);

	out->st[0] = a->st[0] + amount * (b->st[0] - a->st[0]);
	out->st[1] = a->st[1] + amount * (b->st[1] - a->st[1]);

	out->lightmap[0] = a->lightmap[0] + amount * (b->lightmap[0] - a->lightmap[0]);
	out->lightmap[1] = a->lightmap[1] + amount * (b->lightmap[1] - a->lightmap[1]);

	out->color[0] = a->color[0] + amount * (b->color[0] - a->color[0]);
	out->color[1] = a->color[1] + amount * (b->color[1] - a->color[1]);
	out->color[2] = a->color[2] + amount * (b->color[2] - a->color[2]);
	out->color[3] = a->color[3] + amount * (b->color[3] - a->color[3]);

	out->normal[0] = a->normal[0] + amount * (b->normal[0] - a->normal[0]);
	out->normal[1] = a->normal[1] + amount * (b->normal[1] - a->normal[1]);
	out->normal[2] = a->normal[2] + amount * (b->normal[2] - a->normal[2]);
}


typedef struct drawEdge_s
{
	drawVert_t	*start, *end;
	double		centroid, stride;
}
drawEdge_t;

#define DEGENERATE_EPSILON	0.00001


void yTraceTriangleLightmap_1( dsurface_t *ds, drawVert_t *dv[ 3 ], int luxelsWidth, int luxelsHeight, float *luxels, traceWork_t *tw )
{
	int			i, lx, ly;
	double		x, y, yMin, f, xStride, yStride, stride;
	float		*luxel;
	drawVert_t	cursor, left, right;
	drawEdge_t	edges[ 3 ], *leftEdge, *rightEdge;
	int			numEdges;
	
	
	/* build a list of edges */
	yMin = 99999;
	numEdges = 0;
	for( i = 0; i < 3; i++ )
	{
		/* build an edges */
		edges[ numEdges ].start = dv[ i ];
		edges[ numEdges ].end = dv[ (i + 1) % 3 ];
		
		/* detect degenerate triangle */
		if( fabs( edges[ numEdges ].start->lightmap[ 0 ] - edges[ numEdges ].end->lightmap[ 0 ] ) < DEGENERATE_EPSILON &&
			fabs( edges[ numEdges ].start->lightmap[ 1 ] - edges[ numEdges ].end->lightmap[ 1 ] ) < DEGENERATE_EPSILON )
			return;
		
		/* sort verts low->high */
		if( edges[ numEdges ].end->lightmap[ 1 ] < edges[ numEdges ].start->lightmap[ 1 ] )
		{
			drawVert_t	*temp = edges[ numEdges ].start;
			edges[ numEdges ].start = edges[ numEdges ].end;
			edges[ numEdges ].end = temp;
		}
		
		/* is this a flat edge? */
		if( fabs( edges[ numEdges ].start->lightmap[ 1 ] - edges[ numEdges ].end->lightmap[ 1 ] ) < DEGENERATE_EPSILON )
			continue;
		
		/* find lowest y */
		if( edges[ numEdges ].start->lightmap[ 1 ] < yMin )
			yMin = edges[ numEdges ].start->lightmap[ 1 ];
		
		/* valid edges */
		edges[ numEdges ].centroid = (double) 0.5 * (edges[ numEdges ].start->lightmap[ 0 ] + edges[ numEdges ].end->lightmap[ 0 ]);
		edges[ numEdges ].stride = (double) 1.0 / (edges[ numEdges ].end->lightmap[ 1 ] - edges[ numEdges ].start->lightmap[ 1 ]);
		numEdges++;
	}
	
	/* bail on < 2 edges */
	if( numEdges < 2 )
		return;
	
	/* scanline convert the triangle */
	xStride = (1.0 / luxelsWidth);
	yStride = (1.0 / luxelsHeight);
	y = yMin;
	while( 1 )
	{
		/* find left and right edges for the y value */
		leftEdge = rightEdge = NULL;
		for( i = 0; i < numEdges; i++ )
		{
			if( y >= edges[ i ].start->lightmap[ 1 ] && y <= edges[ i ].end->lightmap[ 1 ] )
			{
				if( leftEdge == NULL )
					leftEdge = &edges[ i ];
				else
				{
					rightEdge = &edges[ i ];
					break;
				}
			}
		}
		
		/* done with the triangle */
		if( leftEdge == NULL || rightEdge == NULL )
			break;
		
		/* sort edges left->right */
		if( rightEdge->centroid < leftEdge->centroid  )
		{
			drawEdge_t	*temp = rightEdge;
			rightEdge = leftEdge;
			leftEdge = temp;
		}
		
		/* for given y value, create left and right interpolated verts */
		f = leftEdge->stride * (y - leftEdge->start->lightmap[ 1 ]);
		yLerpDrawVertAmount( leftEdge->start, leftEdge->end, f, &left );
		f = rightEdge->stride * (y - rightEdge->start->lightmap[ 1 ]);
		yLerpDrawVertAmount( rightEdge->start, rightEdge->end, f, &right );
		stride = (double) 1.0 / (right.lightmap[ 0 ] - left.lightmap[ 0 ]);

		/* walk the scanline */
		x = left.lightmap[ 0 ];
		do
		{
			/* for a given x value, create a midpoint */
			f = stride * (y - left.lightmap[ 0 ]);
			yLerpDrawVertAmount( &left, &right, f, &cursor );
			
			/* idiot check */
			if( VectorNormalize( cursor.normal, cursor.normal ) )
			{
				/* find luxel coords */
				lx = x * luxelsWidth;
				ly = y * luxelsWidth;
				luxel = luxels + (((ly * luxelsWidth) + lx) * 3);

				/* get light for this sample */
				if( normalmap )
				{
					luxel[ 0 ] = cursor.normal[ 0 ] > 0 ? cursor.normal[ 0 ] * 255 : 0;
					luxel[ 1 ] = cursor.normal[ 1 ] > 0 ? cursor.normal[ 1 ] * 255 : 0;
					luxel[ 2 ] = cursor.normal[ 2 ] > 0 ? cursor.normal[ 2 ] * 255 : 0;
				}
				else
					luxel[ 0 ] = 255, luxel[ 1 ] = 0, luxel[ 2 ] = 255;	/* fixme: replace this hot pink shit */
					//LightingAtSample( cluster, ydv->xyz, ydv->normal, NULL, sample, testOcclusion, forceSunLight, tw );
			}
				
			/* iterate x */
			x += xStride;
		}
		while( x < right.lightmap[ 0 ] + xStride );
		
		/* iterate y */
		y += yStride;
	}
}