'From Squeak 2.3 of January 14, 1999 on 21 April 1999 at 2:00:01 am'!
"Change Set:		B3DFixup-ar
Date:			21 April 1999
Author:			Andreas Raab

This change set includes a fix to the primitive clipping code and a good speedup (30-50%) of the rasterizer C code."!


!B3DClipperPlugin methodsFor: 'clipping' stamp: 'ar 4/21/1999 01:26'!
interpolateFrom: last to: next at: t into: out
	"Interpolate the primitive vertices last/next at the parameter t"
	| delta rgbaLast lastValue rgbaNext nextValue newValue x y z w w2 flags |
	self var: #last declareC:'float *last'.
	self var: #next declareC:'float *next'.
	self var: #out declareC:'float *out'.
	self var: #t declareC: 'double t'.
	self var: #delta declareC: 'double delta'.
	self var: #rgbaLast declareC:'unsigned int rgbaLast'.
	self var: #rgbaNext declareC:'unsigned int rgbaNext'.
	self var: #lastValue declareC:'unsigned int lastValue'.
	self var: #nextValue declareC:'unsigned int nextValue'.
	self var: #newValue declareC:'unsigned int newValue'.
	self var: #x declareC:'double x'.
	self var: #y declareC:'double y'.
	self var: #z declareC:'double z'.
	self var: #w declareC:'double w'.
	self var: #w2 declareC:'double w2'.
	"Interpolate raster position"
	delta _ (next at: PrimVtxRasterPosX) - (last at: PrimVtxRasterPosX).
	x _ (last at: PrimVtxRasterPosX) + (delta * t).
	out at: PrimVtxRasterPosX put: (self cCoerce: x to: 'float').
	delta _ (next at: PrimVtxRasterPosY) - (last at: PrimVtxRasterPosY).
	y _ (last at: PrimVtxRasterPosY) + (delta * t).
	out at: PrimVtxRasterPosY put: (self cCoerce: y to: 'float').
	delta _ (next at: PrimVtxRasterPosZ) - (last at: PrimVtxRasterPosZ).
	z _ (last at: PrimVtxRasterPosZ) + (delta * t).
	out at: PrimVtxRasterPosZ put: (self cCoerce: z to: 'float').
	delta _ (next at: PrimVtxRasterPosW) - (last at: PrimVtxRasterPosW).
	w _ (last at: PrimVtxRasterPosW) + (delta * t).
	out at: PrimVtxRasterPosW put: (self cCoerce: w to: 'float').
	"Determine new clipFlags"
	w2 _ 0.0 - w.
	flags _ 0.
	x >= w2 ifTrue:[flags _ flags bitOr: InLeftBit] ifFalse:[flags _ flags bitOr: OutLeftBit].
	x <= w ifTrue:[flags _ flags bitOr: InRightBit] ifFalse:[flags _ flags bitOr: OutRightBit].
	y >= w2 ifTrue:[flags _ flags bitOr: InBottomBit] ifFalse:[flags _ flags bitOr: OutBottomBit].
	y <= w ifTrue:[flags _ flags bitOr: InTopBit] ifFalse:[flags _ flags bitOr: OutTopBit].
	z >= w2 ifTrue:[flags _ flags bitOr: InFrontBit] ifFalse:[flags _ flags bitOr: OutFrontBit].
	z <= w ifTrue:[flags _ flags bitOr: InBackBit] ifFalse:[flags _ flags bitOr: OutBackBit].
	(self cCoerce: out to: 'int *') at: PrimVtxClipFlags put: flags.

	"Interpolate color"
	rgbaLast _ (self cCoerce: last to:'unsigned int *') at: PrimVtxColor32.
	lastValue _ rgbaLast bitAnd: 255. rgbaLast _ rgbaLast >> 8.
	rgbaNext _ (self cCoerce: next to: 'unsigned int *') at: PrimVtxColor32.
	nextValue _ rgbaNext bitAnd: 255. rgbaNext _ rgbaNext >> 8.
	delta _ (self cCoerce: (nextValue - lastValue) to:'int') * t.
	newValue _ (lastValue + delta) asInteger.

	lastValue _ rgbaLast bitAnd: 255. rgbaLast _ rgbaLast >> 8.
	nextValue _ rgbaNext bitAnd: 255. rgbaNext _ rgbaNext >> 8.
	delta _ (self cCoerce: (nextValue - lastValue) to:'int') * t.
	newValue _ newValue + ((lastValue + delta) asInteger << 8).

	lastValue _ rgbaLast bitAnd: 255. rgbaLast _ rgbaLast >> 8.
	nextValue _ rgbaNext bitAnd: 255. rgbaNext _ rgbaNext >> 8.
	delta _ (self cCoerce: (nextValue - lastValue) to:'int') * t.
	newValue _ newValue + ((lastValue + delta) asInteger << 16).

	lastValue _ rgbaLast bitAnd: 255.
	nextValue _ rgbaNext bitAnd: 255.
	delta _ (self cCoerce: (nextValue - lastValue) to:'int') * t.
	newValue _ newValue + ((lastValue + delta) asInteger << 24).

	(self cCoerce: out to:'unsigned int*') at: PrimVtxColor32 put: newValue.

	"Interpolate texture coordinates"
	delta _ (next at: PrimVtxTexCoordU) - (last at: PrimVtxTexCoordU).
	out at: PrimVtxTexCoordU put: (self cCoerce: (last at: PrimVtxTexCoordU) + (delta * t) to:'float').
	delta _ (next at: PrimVtxTexCoordV) - (last at: PrimVtxTexCoordV).
	out at: PrimVtxTexCoordV put: (self cCoerce: (last at: PrimVtxTexCoordV) + (delta * t) to:'float').
! !


!B3DRasterizerPlugin class methodsFor: 'C source code' stamp: 'ar 4/21/1999 01:58'!
b3dDrawC
^'/****************************************************************************
*   PROJECT: Balloon 3D Graphics Subsystem for Squeak
*   FILE:    b3dDraw.c
*   CONTENT: Pixel drawing functions for the B3D rasterizer
*
*   AUTHOR:  Andreas Raab (ar)
*   ADDRESS: Walt Disney Imagineering, Glendale, CA
*   EMAIL:   andreasr@wdi.disney.com
*   RCSID:   $Id$
*
*   NOTES:  LOTS of stuff missing here...
*
*	- A note on RGBA interpolation:
*	For low polygon models it makes sense to compute both, the left and
*	the right attribute value if there might be any overflow at all.
*	Since we''re usually drawing many pixels in a row we can clamp the
*	left and right value and thus be safe during the interpolation stage.
*
*****************************************************************************/
#include "b3d.h"

#define rasterPosX rasterPos[0]
#define rasterPosY rasterPos[1]

#define redValue   color[RED_INDEX]
#define greenValue color[GREEN_INDEX]
#define blueValue  color[BLUE_INDEX]
#define alphaValue color[ALPHA_INDEX]

/* The following defines the maximum number of pixels 
   we treat in one loop. This value should be carefully
   chosen: Setting it high will increase speed for larger
   polygons but reduce speed for smaller ones. Setting
   it low will do the opposite. Also, since I''m assuming
   a smart compiler, the code size will probably increase
   with this number (if loops are unrolled by the compiler).

   The current value of 5 should be a good median (32 pixels
   are processed at most and we''ll have the overhead of 5
   tests for a one-pixel polygon).
*/
#define MAX_PIXEL_SHIFT 5


/* USE_MULTBL: Replace up a couple of multiplications by table lookups.
	On PowerPC, the lookup seems to be slightly slower.
	On Intel, the lookup is way faster.
*/
#ifndef USE_MULTBL
# ifdef __POWERPC__
#  define USE_MULTBL 0
# else
#  define USE_MULTBL 1
# endif
#endif

/* Clamp the given value */
#define CLAMP(value, min, max)\
	if((value) < (min)) (value) = (min); \
	else if((value) > (max)) (value) = (max);

/* Clamp a set of fixed point RGB values */
#define CLAMP_RGB(r,g,b) \
	CLAMP(r,B3D_FixedHalf, (255 << B3D_IntToFixedShift) + B3D_FixedHalf)\
	CLAMP(g,B3D_FixedHalf, (255 << B3D_IntToFixedShift) + B3D_FixedHalf)\
	CLAMP(b,B3D_FixedHalf, (255 << B3D_IntToFixedShift) + B3D_FixedHalf)


#ifdef DEBUG_ATTR
double attrValueAt(B3DPrimitiveFace *face, B3DPrimitiveAttribute *attr, double xValue, double yValue)
{
	return 
		(attr->value +
			((xValue - face->v0->rasterPosX) * attr->dvdx) +
			((yValue - face->v0->rasterPosY) * attr->dvdy));
}
#else
#define attrValueAt(face,attr,xValue,yValue) \
		((attr)->value + \
			(((double)(xValue) - (face)->v0->rasterPosX) * (attr)->dvdx) + \
			(((double)(yValue) - (face)->v0->rasterPosY) * (attr)->dvdy))
#endif


#define SETUP_RGB \
	rValue = (int)(attrValueAt(face, attr, floatX, floatY) * B3D_FloatToFixed); \
	deltaR = (int) (attr->dvdx * B3D_FloatToFixed);  \
	attr = attr->next; \
	gValue = (int)(attrValueAt(face, attr, floatX, floatY) * B3D_FloatToFixed);\
	deltaG = (int) (attr->dvdx * B3D_FloatToFixed); \
	attr = attr->next; \
	bValue = (int)(attrValueAt(face, attr, floatX, floatY) * B3D_FloatToFixed); \
	deltaB = (int) (attr->dvdx * B3D_FloatToFixed); \
	attr = attr->next;\
	CLAMP_RGB(rValue, gValue, bValue);

#define SETUP_STW \
	wValue = attrValueAt(face, attr, floatX, floatY); \
	wDelta = attr->dvdx; \
	attr = attr->next; \
	sValue = attrValueAt(face, attr, floatX, floatY); \
	sDelta = attr->dvdx; \
	attr = attr->next; \
	tValue = attrValueAt(face, attr, floatX, floatY); \
	tDelta = attr->dvdx; \
	attr = attr->next;

#define STEP_STW \
	sValue += sDelta;\
	tValue += tDelta;\
	wValue += wDelta;


/* Load the four neighbouring texels into tex00, tex01, tex10, and tex11 */
#define LOAD_4_RGB_TEXEL_32(fixedS, fixedT, texture) \
{\
	int sIndex, tIndex;\
\
	if(texture->sMask) {\
		sIndex = (fixedS >> B3D_FixedToIntShift) & texture->sMask;\
	} else {\
		sIndex = (fixedS >> B3D_FixedToIntShift) % texture->width;\
	}\
	if(texture->tMask) {\
		tIndex = (fixedT >> B3D_FixedToIntShift) & texture->tMask;\
	} else {\
		tIndex = (fixedT >> B3D_FixedToIntShift) % texture->height;\
	}\
	/* Load the 4 texels, wrapping if necessary */\
	tex00 = (struct b3dPixelColor *) texture->data + (tIndex * texture->width) + sIndex;\
	tex01 = tex00 + 1;\
	tex10 = tex00 + texture->width;\
	tex11 = tex10 + 1;\
	if(sIndex+1 == texture->width) {\
		tex01 -= texture->width;\
		tex11 -= texture->width;\
	}\
	if(tIndex+1 == texture->height) {\
		int tsize = texture->height * texture->width;\
		tex10 -= tsize;\
		tex11 -= tsize;\
	}\
}


#if USE_MULTBL /* Use a 16x256 table for lookups */

unsigned short MULTBL[17][256];

static int multblInit = 0;

static void MULTBL_Init(void)
{
	int i,j;
	for(i=0;i<17;i++)
		for(j=0; j<256; j++)
			MULTBL[i][j] = (i*j) >> 4;
	multblInit = 1;
}

#define INIT_MULTBL { if (!!multblInit) MULTBL_Init(); }

#define DO_RGB_INTERPOLATION(sf, si, tf, ti) \
	tr = (MULTBL[ti][(MULTBL[si][tex00->redValue] + MULTBL[sf][tex01->redValue])] + \
			MULTBL[tf][(MULTBL[si][tex10->redValue] + MULTBL[sf][tex11->redValue])]);\
	tg = (MULTBL[ti][(MULTBL[si][tex00->greenValue] + MULTBL[sf][tex01->greenValue])] + \
			MULTBL[tf][(MULTBL[si][tex10->greenValue] + MULTBL[sf][tex11->greenValue])]);\
	tb = (MULTBL[ti][(MULTBL[si][tex00->blueValue] + MULTBL[sf][tex01->blueValue])] + \
			MULTBL[tf][(MULTBL[si][tex10->blueValue] + MULTBL[sf][tex11->blueValue])]);

#define DO_RGBA_INTERPOLATION(sf, si, tf, ti)\
	tr = (MULTBL[ti][(MULTBL[si][tex00->redValue] + MULTBL[sf][tex01->redValue])] + \
			MULTBL[tf][(MULTBL[si][tex10->redValue] + MULTBL[sf][tex11->redValue])]);\
	tg = (MULTBL[ti][(MULTBL[si][tex00->greenValue] + MULTBL[sf][tex01->greenValue])] + \
			MULTBL[tf][(MULTBL[si][tex10->greenValue] + MULTBL[sf][tex11->greenValue])]);\
	tb = (MULTBL[ti][(MULTBL[si][tex00->blueValue] + MULTBL[sf][tex01->blueValue])] + \
			MULTBL[tf][(MULTBL[si][tex10->blueValue] + MULTBL[sf][tex11->blueValue])]); \
	ta = (MULTBL[ti][(MULTBL[si][tex00->alphaValue] + MULTBL[sf][tex01->alphaValue])] + \
			MULTBL[tf][(MULTBL[si][tex10->alphaValue] + MULTBL[sf][tex11->alphaValue])]);

#else

#define INIT_MULTBL

#define DO_RGB_INTERPOLATION(sf, si, tf, ti) \
	tr = (ti * (si * tex00->redValue + sf * tex01->redValue) +\
			tf * (si * tex10->redValue + sf * tex11->redValue)) >> 8;\
	tg = (ti * (si * tex00->greenValue + sf * tex01->greenValue) +\
			tf * (si * tex10->greenValue + sf * tex11->greenValue)) >> 8;\
	tb = (ti * (si * tex00->blueValue + sf * tex01->blueValue) +\
			tf * (si * tex10->blueValue + sf * tex11->blueValue)) >> 8;\

#define DO_RGBA_INTERPOLATION(sf, si, tf, ti) \
	tr = (ti * (si * tex00->redValue + sf * tex01->redValue) +\
			tf * (si * tex10->redValue + sf * tex11->redValue)) >> 8;\
	tg = (ti * (si * tex00->greenValue + sf * tex01->greenValue) +\
			tf * (si * tex10->greenValue + sf * tex11->greenValue)) >> 8;\
	tb = (ti * (si * tex00->blueValue + sf * tex01->blueValue) +\
			tf * (si * tex10->blueValue + sf * tex11->blueValue)) >> 8;\
	ta = (ti * (si * tex00->alphaValue + sf * tex01->alphaValue) +\
			tf * (si * tex10->alphaValue + sf * tex11->alphaValue)) >> 8;

#endif /* No MULTBL */

#define INTERPOLATE_RGB_TEXEL(fixedS, fixedT)\
{	int sf, si, tf, ti;\
	sf = (fixedS >> (B3D_FixedToIntShift - 4)) & 15; si = 16 - sf;\
	tf = (fixedT >> (B3D_FixedToIntShift - 4)) & 15; ti = 16 - tf;\
	DO_RGB_INTERPOLATION(sf, si, tf, ti)\
}

void b3dNoDraw     (int leftX, int rightX, int yValue, B3DPrimitiveFace *face);
void b3dDrawRGB    (int leftX, int rightX, int yValue, B3DPrimitiveFace *face);
void b3dDrawRGBA   (int leftX, int rightX, int yValue, B3DPrimitiveFace *face);
void b3dDrawSTW    (int leftX, int rightX, int yValue, B3DPrimitiveFace *face);
void b3dDrawSTWA   (int leftX, int rightX, int yValue, B3DPrimitiveFace *face);
void b3dDrawSTWRGB (int leftX, int rightX, int yValue, B3DPrimitiveFace *face);
void b3dDrawSTWARGB(int leftX, int rightX, int yValue, B3DPrimitiveFace *face);

b3dPixelDrawer B3D_FILL_FUNCTIONS[B3D_MAX_ATTRIBUTES] = {
	b3dNoDraw,      /* No attributes */
	b3dDrawRGB,     /* B3D_FACE_RGB */
	b3dNoDraw,      /* B3D_FACE_ALPHA -- IGNORED!!!!!! */
	b3dDrawRGBA,    /* B3D_FACE_RGB | B3D_FACE_ALPHA */
	b3dDrawSTW,     /* B3D_FACE_STW */
	b3dDrawSTWRGB,  /* B3D_FACE_STW | B3D_FACE_RGB */
	b3dDrawSTWA,    /* B3D_FACE_STW | B3D_FACE_ALPHA */
	b3dDrawSTWARGB  /* B3D_FACE_STW | B3D_FACE_RGB | B3D_FACE_ALPHA */
};

void b3dNoDraw(int leftX, int rightX, int yValue, B3DPrimitiveFace *face)
{
	if(b3dDebug)
		b3dAbort("b3dNoDraw called!!");
}

void b3dDrawRGBFlat(int leftX, int rightX, int yValue, B3DPrimitiveFace *face)
{
	struct b3dPixelColor { B3DPrimitiveColor color; } pv, *bits;
	int rValue, gValue, bValue;
	int deltaR, deltaG, deltaB;


	{
		B3DPrimitiveAttribute *attr = face->attributes;
		/* Ughh ... I''m having a sampling problem somewhere.
		   In theory, the faces should be sampled *exactly* at integer
		   values (the necessary offset should be done before) so that
		   we always sample inside the triangle. For some reason that
		   doesn''t quite work yet and that''s why here is the strange
		   0.5 offset and the awful lot of tests. At some time I''ll
		   review this but for now I have more important things to do.
		*/
		double floatX = leftX;
		double floatY = yValue+0.5;

		if(b3dDebug)
			if(!!attr) b3dAbort("face has no RGB attributes");

		SETUP_RGB;
	}

	bits = (struct b3dPixelColor *) currentState->spanBuffer;
	pv.redValue   = (unsigned char) (rValue >> B3D_FixedToIntShift);
	pv.greenValue = (unsigned char) (gValue >> B3D_FixedToIntShift);
	pv.blueValue  = (unsigned char) (bValue >> B3D_FixedToIntShift);
	pv.alphaValue = 255;

	while(leftX <= rightX) {
		bits[leftX++] = pv;
	}
}

void b3dDrawRGB(int leftX, int rightX, int yValue, B3DPrimitiveFace *face)
{
	struct b3dPixelColor { B3DPrimitiveColor color; } pv, *bits;
	int rValue, gValue, bValue;
	int deltaR, deltaG, deltaB;
	int deltaX, pixelShift;

	{
		B3DPrimitiveAttribute *attr = face->attributes;
		/* Ughh ... I''m having a sampling problem somewhere.
		   In theory, the faces should be sampled *exactly* at integer
		   values (the necessary offset should be done before) so that
		   we always sample inside the triangle. For some reason that
		   doesn''t quite work yet and that''s why here is the strange
		   0.5 offset and the awful lot of tests. At some time I''ll
		   review this but for now I have more important things to do.
		*/
		double floatX = leftX;
		double floatY = yValue+0.5;

		if(b3dDebug)
			if(!!attr) b3dAbort("face has no RGB attributes");

		SETUP_RGB;
	}

	bits = (struct b3dPixelColor *) currentState->spanBuffer;
	pv.alphaValue = 255;

	/*	Reduce the overhead of clamping by precomputing 
		the deltas for each power of two step. A good question here
		is whether or not it is a good idea to do 2 pixels by this... */
	deltaX = rightX - leftX + 1;

	/* Now do all the powers of two except the last one pixel */
	/* Note: A smart compiler (== gcc) should unroll the following loop */
	for(pixelShift= MAX_PIXEL_SHIFT; pixelShift> 0; pixelShift--) {
		int nPixels = 1 << pixelShift;
		/* Note: The ''if'' here is possible since 
		   we have dealt with huge polys above */
		while(deltaX >= nPixels) {	
			{	/* Compute right most values of color interpolation */
				int maxR = rValue + (deltaR << pixelShift);
				int maxG = gValue + (deltaG << pixelShift);
				int maxB = bValue + (deltaB << pixelShift);
				/* Clamp those guys */
				CLAMP_RGB(maxR, maxG, maxB);
				/* And compute the actual delta */
				deltaR = (maxR - rValue) >> pixelShift;
				deltaG = (maxG - gValue) >> pixelShift;
				deltaB = (maxB - bValue) >> pixelShift;
			}
			/* Do the inner loop */
			{	int n = nPixels;
				while(n--) {
					pv.redValue   = (unsigned char) (rValue >> B3D_FixedToIntShift);
					pv.greenValue = (unsigned char) (gValue >> B3D_FixedToIntShift);
					pv.blueValue  = (unsigned char) (bValue >> B3D_FixedToIntShift);
					bits[leftX++] = pv;
					rValue += deltaR;
					gValue += deltaG;
					bValue += deltaB;
				}
			}
			/* Finally, adjust the number of pixels left */
			deltaX -= nPixels;
		}
	}
	/* The last pixel is done separately */
	if(deltaX) {
		pv.redValue   = (unsigned char) (rValue >> B3D_FixedToIntShift);
		pv.greenValue = (unsigned char) (gValue >> B3D_FixedToIntShift);
		pv.blueValue  = (unsigned char) (bValue >> B3D_FixedToIntShift);
		bits[leftX++] = pv;
	}
}

void b3dDrawSTWRGB(int leftX, int rightX, int yValue, B3DPrimitiveFace *face)
{
	struct b3dPixelColor { B3DPrimitiveColor color; } pv, *bits, *tex00, *tex10, *tex01, *tex11;
	double sValue, tValue, wValue, sDelta, tDelta, wDelta, oneOverW;
	int rValue, gValue, bValue;
	int deltaR, deltaG, deltaB;
	int tr, tg, tb, ta;
	int fixedLeftS, fixedRightS, fixedLeftT, fixedRightT, fixedDeltaS, fixedDeltaT;
	int deltaX, pixelShift;

	B3DTexture *texture = face->texture;

	INIT_MULTBL;

	if(!!texture || 0) {
		/* If no texture simply draw RGB */
		b3dDrawRGB(leftX, rightX, yValue, face);
		return;
	}
	if(texture->depth < 16 && (texture->cmSize < (1 << texture->depth)))
		return; /* Colormap not installed */

	{
		B3DPrimitiveAttribute *attr = face->attributes;
		/* See above */
		double floatX = leftX;
		double floatY = yValue+0.5;

		if(b3dDebug)
			if(!!attr) b3dAbort("face has no RGB attributes");

		SETUP_RGB;
		SETUP_STW;
	}

	tr = tg = tb = ta = 255;

	bits = (struct b3dPixelColor *) currentState->spanBuffer;
	pv.alphaValue = 255;

	/*	VERY Experimental: Reduce the overhead of clamping
		as well as division by W by precomputing the deltas 
		for each power of two step */
	deltaX = rightX - leftX + 1;
	if(wValue) oneOverW = 1.0 / wValue;
	else oneOverW = 0.0;
	fixedLeftS = (int) (sValue * oneOverW * (texture->width << B3D_IntToFixedShift));
	fixedLeftT = (int) (tValue * oneOverW * (texture->height << B3D_IntToFixedShift));

	for(pixelShift = MAX_PIXEL_SHIFT; pixelShift > 0; pixelShift--) {
		int nPixels = 1 << pixelShift;
		while(deltaX >= nPixels) {
			{	/* Compute right most values of color interpolation */
				int maxR = rValue + (deltaR << pixelShift);
				int maxG = gValue + (deltaG << pixelShift);
				int maxB = bValue + (deltaB << pixelShift);
				/* Clamp those guys */
				CLAMP_RGB(maxR, maxG, maxB);
				/* And compute the actual delta */
				deltaR = (maxR - rValue) >> pixelShift;
				deltaG = (maxG - gValue) >> pixelShift;
				deltaB = (maxB - bValue) >> pixelShift;
			}
			/* Compute the RIGHT s/t values (the left ones are kept from the last loop) */
			wValue += wDelta * nPixels;
			sValue += sDelta * nPixels;
			tValue += tDelta * nPixels;
			if(wValue) oneOverW = 1.0 / wValue;
			else oneOverW = 0.0;
			fixedRightS = (int) (sValue * oneOverW * (texture->width << B3D_IntToFixedShift));
			fixedDeltaS = (fixedRightS - fixedLeftS) >> pixelShift;
			fixedRightT = (int) (tValue * oneOverW * (texture->height << B3D_IntToFixedShift));
			fixedDeltaT = (fixedRightT - fixedLeftT) >> pixelShift;
			/* Do the inner loop */
			{	int n = nPixels;
				while(n--) {
					/* Do the texture load ... hmm ... there should be a way
					   to avoid loading the texture on each pixel... 
					   On the other hand, the texture load does not seem
					   too expensive if compared with the texture interpolation.
					*/
					LOAD_4_RGB_TEXEL_32(fixedLeftS, fixedLeftT, texture);
					/* Do the interpolation based on tex00, tex01, tex10, tex11.
					   THIS seems to be one of the real bottlenecks here...
					*/
					INTERPOLATE_RGB_TEXEL(fixedLeftS, fixedLeftT);
#if USE_MULTBL
					pv.redValue   = (unsigned char) (MULTBL[rValue >> (B3D_FixedToIntShift+4)][tr]);
					pv.greenValue = (unsigned char) (MULTBL[gValue >> (B3D_FixedToIntShift+4)][tg]);
					pv.blueValue  = (unsigned char) (MULTBL[bValue >> (B3D_FixedToIntShift+4)][tb]);
#else
					pv.redValue   = (unsigned char) ((tr * rValue) >> (B3D_FixedToIntShift + 8));
					pv.greenValue = (unsigned char) ((tg * gValue) >> (B3D_FixedToIntShift + 8));
					pv.blueValue  = (unsigned char) ((tb * bValue) >> (B3D_FixedToIntShift + 8));
#endif
					bits[leftX++] = pv;
					rValue += deltaR;
					gValue += deltaG;
					bValue += deltaB;
					fixedLeftS += fixedDeltaS;
					fixedLeftT += fixedDeltaT;
				}
			}
			/* Finally, adjust the number of pixels left and update s/t */
			deltaX -= nPixels;
			fixedLeftS = fixedRightS;
			fixedLeftT = fixedRightT;
		}
	}
	/* The last pixel is done separately */
	if(deltaX) {
		/* Do the texture load */
		LOAD_4_RGB_TEXEL_32(fixedLeftS, fixedLeftT, texture);
		/* Do the interpolation */
		INTERPOLATE_RGB_TEXEL(fixedLeftS, fixedLeftT);
#if USE_MULTBL
		pv.redValue   = (unsigned char) (MULTBL[rValue >> (B3D_FixedToIntShift+4)][tr]);
		pv.greenValue = (unsigned char) (MULTBL[gValue >> (B3D_FixedToIntShift+4)][tg]);
		pv.blueValue  = (unsigned char) (MULTBL[bValue >> (B3D_FixedToIntShift+4)][tb]);
#else
		pv.redValue   = (unsigned char) ((tr * rValue) >> (B3D_FixedToIntShift + 8));
		pv.greenValue = (unsigned char) ((tg * gValue) >> (B3D_FixedToIntShift + 8));
		pv.blueValue  = (unsigned char) ((tb * bValue) >> (B3D_FixedToIntShift + 8));
#endif
		bits[leftX++] = pv;
	}
}

void b3dDrawSTWARGB(int leftX, int rightX, int yValue, B3DPrimitiveFace *face)
{
	/* not yet implemented */
}

void b3dDrawRGBA(int leftX, int rightX, int yValue, B3DPrimitiveFace *face)
{
	/* not yet implemented */
}

void b3dDrawSTW(int leftX, int rightX, int yValue, B3DPrimitiveFace *face)
{
	/* not yet implemented */
}

void b3dDrawSTWA(int leftX, int rightX, int yValue, B3DPrimitiveFace *face)
{
	/* not yet implemented */
}
'! !

!B3DRasterizerPlugin class methodsFor: 'C source code' stamp: 'ar 4/21/1999 00:31'!
b3dInitC
^'/****************************************************************************
*   PROJECT: Balloon 3D Graphics Subsystem for Squeak
*   FILE:    b3dInit.c
*   CONTENT: Initialization functions for the B3D rasterizer
*
*   AUTHOR:  Andreas Raab (ar)
*   ADDRESS: Walt Disney Imagineering, Glendale, CA
*   EMAIL:   andreasr@wdi.disney.com
*   RCSID:   $Id$
*
*   NOTES:
*
*
*****************************************************************************/
#include <string.h>
#include "b3d.h"

#define b3dCompensateWindowPos 1

/* helpers */
#define rasterPosX rasterPos[0]
#define rasterPosY rasterPos[1]
#define rasterPosZ rasterPos[2]
#define rasterPosW rasterPos[3]

#define windowPosX windowPos[0]
#define windowPosY windowPos[1]

#define texCoordS texCoord[0]
#define texCoordT texCoord[1]

/*************************************************************/
/*************************************************************/
/*************************************************************/
int b3dInitializeEdgeAllocator(void* base, int length)
{
	B3DEdgeAllocList *list = (B3DEdgeAllocList*) base;
	if(length < sizeof(B3DEdgeAllocList))
		return B3D_GENERIC_ERROR;
	list->magic = B3D_EDGE_ALLOC_MAGIC;
	list->This = base;
	list->max = (length - sizeof(B3DEdgeAllocList)) / sizeof(B3DPrimitiveEdge) + 1;
	list->size = 0;
	list->nFree = list->max;
	list->firstFree = NULL;
	return B3D_NO_ERROR;
}

int b3dInitializeFaceAllocator(void* base, int length)
{
	B3DFaceAllocList *list = (B3DFaceAllocList*) base;
	if(length < sizeof(B3DFaceAllocList))
		return B3D_GENERIC_ERROR;
	list->magic = B3D_FACE_ALLOC_MAGIC;
	list->This = base;
	list->max = (length - sizeof(B3DFaceAllocList)) / sizeof(B3DPrimitiveFace) + 1;
	list->size = 0;
	list->nFree = list->max;
	list->firstFree = NULL;
	return B3D_NO_ERROR;
}

int b3dInitializeAttrAllocator(void* base, int length)
{
	B3DAttrAllocList *list = (B3DAttrAllocList*) base;
	if(length < sizeof(B3DAttrAllocList))
		return B3D_GENERIC_ERROR;
	list->magic = B3D_ATTR_ALLOC_MAGIC;
	list->This = base;
	list->max = (length - sizeof(B3DAttrAllocList)) / sizeof(B3DPrimitiveAttribute) + 1;
	list->size = 0;
	list->nFree = list->max;
	list->firstFree = NULL;
	return B3D_NO_ERROR;
}

int b3dInitializeEdgeList(void* base, int length)
{
	B3DPrimitiveEdgeList *list = (B3DPrimitiveEdgeList*) base;
	if(length < sizeof(B3DPrimitiveEdgeList))
		return B3D_GENERIC_ERROR;
	list->magic = B3D_EDGE_LIST_MAGIC;
	list->This = base;
	list->max = (length - sizeof(B3DPrimitiveEdgeList)) / sizeof(B3DPrimitiveEdge*) + 1;
	list->size = 0;
	return B3D_NO_ERROR;
}

int b3dInitializeAET(void* base, int length)
{
	B3DActiveEdgeTable *aet = (B3DActiveEdgeTable *) base;
	if(length < sizeof(B3DActiveEdgeTable))
		return B3D_GENERIC_ERROR;
	aet->magic = B3D_AET_MAGIC;
	aet->This = base;
	aet->max = (length - sizeof(B3DActiveEdgeTable)) / sizeof(B3DPrimitiveEdge*) + 1;
	aet->size = 0;
	aet->leftEdge = aet->rightEdge = NULL;
	aet->lastIntersection = &aet->tempEdge0;
	aet->nextIntersection = &aet->tempEdge1;
	return B3D_NO_ERROR;
}

int b3dInitializeFillList(void* base, int length)
{
	B3DFillList *list = (B3DFillList*) base;
	if(length < sizeof(B3DFillList))
		return B3D_GENERIC_ERROR;
	list->magic = B3D_FILL_LIST_MAGIC;
	list->This = base;
	list->firstFace = list->lastFace = NULL;
	return B3D_NO_ERROR;
}

/*************************************************************/
/*************************************************************/
/*************************************************************/

/* b3dMapObjectVertices:
	 Map all the vertices of the given object into the designated viewport.
*/
void b3dMapObjectVertices(B3DPrimitiveObject *obj, B3DPrimitiveViewport *vp)
{
	double xScale, yScale, xOfs, yOfs;
	int minX, minY, maxX, maxY;
	double minZ, maxZ;
	B3DPrimitiveVertex *vtx;
	int i;

	xOfs = (vp->x0 + vp->x1) * 0.5 - 0.5;
	yOfs = (vp->y0 + vp->y1) * 0.5 - 0.5;
	xScale = (vp->x1 - vp->x0) * 0.5;
	yScale = (vp->y1 - vp->y0) * -0.5;

	minX = minY = maxX = maxY = 0x7FFFFFFF;
	minZ = maxZ = 0.0;
	vtx = obj->vertices + 1;
	for(i=1; i < obj->nVertices; i++, vtx++)
	{
		double x,y,z,w;
		int scaledX, scaledY;

		w = vtx->rasterPosW;
		if(w) w = 1.0 / w;
		x = vtx->rasterPosX * w * xScale + xOfs;
		y = vtx->rasterPosY * w * yScale + yOfs;
		z = vtx->rasterPosZ * w;

		if(!!b3dCompensateWindowPos) {
			vtx->rasterPosX = (float)x;
			vtx->rasterPosY = (float)y;
		}
		vtx->rasterPosZ = (float)z;
		vtx->rasterPosW = (float)w;

		scaledX = (int) (x * B3D_FloatToFixed);
		scaledY = (int) (y * B3D_FloatToFixed);

		vtx->windowPosX = scaledX;
		vtx->windowPosY = scaledY;
		if(b3dCompensateWindowPos) {
			vtx->rasterPosX = (float) (scaledX * B3D_FixedToFloat);
			vtx->rasterPosY = (float) (scaledY * B3D_FixedToFloat);
		}
		/* Update min/max */
		if(i == 1) {
			minX = maxX = scaledX;
			minY = maxY = scaledY;
			minZ = maxZ = z;
		} else {
			if(scaledX < minX) minX = scaledX;
			else if(scaledX > maxX) maxX = scaledX;
			if(scaledY < minY) minY = scaledY;
			else if(scaledY > maxY) maxY = scaledY;
			if(z < minZ) minZ = z;
			else if(z > maxZ) maxZ = z;
		}

	}

	obj->minX = minX >> B3D_FixedToIntShift;
	obj->maxX = maxX >> B3D_FixedToIntShift;
	obj->minY = minY >> B3D_FixedToIntShift;
	obj->maxY = maxY >> B3D_FixedToIntShift;
	obj->minZ = (float)minZ;
	obj->maxZ = (float)maxZ;
}

/* b3dSetupVertexOrder:
     Setup the ordering of the vertices in each face so that
	   v0 sorts before v1 sorts before v2.
	 Gather some stats on how much locally sorted and invalid
	 faces the object includes.
*/

void b3dSetupVertexOrder(B3DPrimitiveObject *obj)
{
	B3DInputFace *face;
	int i, nSorted, nInvalid;
	B3DPrimitiveVertex *vtx, *lastTopVtx, *newTopVtx;

	face = obj->faces;
	vtx = obj->vertices;
	nSorted = nInvalid = 0;
	lastTopVtx = NULL;
	for(i=0;i<obj->nFaces; i++,face++)
	{
		B3DPrimitiveVertex *vtx0, *vtx1, *vtx2;
		int idx0, idx1, idx2;
		idx0 = face->i0;
		idx1 = face->i1;
		idx2 = face->i2;
		if(0 == (idx0 && idx1 && idx2)) {
			nInvalid++;
			continue;
		}
		vtx0 = vtx + idx0;
		vtx1 = vtx + idx1;
		vtx2 = vtx + idx2;
		if(vtxSortsBefore(vtx0,vtx1))
		{
			if(vtxSortsBefore(vtx1,vtx2)) { 
				face->i0 = idx0; 
				face->i1 = idx1; 
				face->i2 = idx2; 
			} else if(vtxSortsBefore(vtx0,vtx2)) {
				face->i0 = idx0;
				face->i1 = idx2;
				face->i2 = idx1;
			} else {
				face->i0 = idx2;
				face->i1 = idx0;
				face->i2 = idx1;
			}
		} else if(vtxSortsBefore(vtx0, vtx2)) {
			face->i0 = idx1;
			face->i1 = idx0;
			face->i2 = idx2;
		} else if(vtxSortsBefore(vtx1, vtx2)) {
			face->i0 = idx1;
			face->i1 = idx2;
			face->i2 = idx0;
		} else {
			face->i0 = idx2;
			face->i1 = idx1;
			face->i2 = idx0;
		}

		if(b3dDebug) {
			vtx0 = vtx + face->i0;
			vtx1 = vtx + face->i1;
			vtx2 = vtx + face->i2;
			if( !!vtxSortsBefore(vtx0, vtx1) || 
				!!vtxSortsBefore(vtx0, vtx2) || 
				!!vtxSortsBefore(vtx1, vtx2))
					b3dAbort("Vertex order problem");
		}

		/* Experimental: Try to estimate how many faces are already sorted. */
		newTopVtx = vtx + face->i0;
		if(lastTopVtx)
			if(vtxSortsBefore(lastTopVtx, newTopVtx)) nSorted++;
		lastTopVtx = newTopVtx;
	}

	obj->nSortedFaces = nSorted;
	obj->nInvalidFaces = nInvalid;
}

/* b3dSortInitialFaces:
     Sort the faces of the given object according to the given sort order.
	 Note: It is assumed that the vertex order of the faces has been setup
	       before.
*/

void b3dQuickSortInitialFaces(B3DPrimitiveObject *obj, int i, int j)
{
	B3DInputFace tmp, *faces = obj->faces;
	int ij, k, l, n;
	B3DPrimitiveVertex *di, *dj, *dij, *tt, *vtx = obj->vertices;

	n = j + 1 - i;
	if(n <= 1) return;
	/* Sort di,dj. */
	di = vtx + faces[i].i0;
	dj = vtx + faces[j].i0;
	if(!!vtxSortsBefore(di,dj))
	{
		tmp = faces[i]; faces[i] = faces[j]; faces[j] = tmp;
		tt = di; di = dj; dj = tt;
	}

	if(n <= 2) return;

	/* More than two elements. */
	ij = (i+j) >> 1; /* ij is the midpoint of i and j. */
	dij = vtx + faces[ij].i0;
	/* Sort di,dij,dj.  Make dij be their median. */
	if(vtxSortsBefore(di, dij)) {/* i.e. should di precede dij? */
		if(!!vtxSortsBefore(dij, dj)) {/* i.e., should dij precede dj?*/
			tmp = faces[j]; faces[j] = faces[ij]; faces[ij] = tmp;
			dij = dj;
		}
	} else { /* i.e. di should come after dij */
		tmp = faces[i]; faces[i] = faces[ij]; faces[ij] = tmp;
		dij = di;
	}

	if(n <= 3) return;

	/* More than three elements.
	Find k>i and l<j such that dk,dij,dl are in reverse order.
	Swap k and l.  Repeat this procedure until k and l pass each other.*/
	k = i;
	l = j;

	while(k <= l) {
		while(k <= --l && (vtxSortsBefore(dij, vtx + faces[l].i0)));
		while(++k <= l && (vtxSortsBefore(vtx + faces[k].i0, dij)));
		if(k <= l) {
			tmp = faces[k];
			faces[k] = faces[l];
			faces[l] = tmp;
		}
	}
	/* Now l<k (either 1 or 2 less), and di through dl are all less than or equal to dk
	through dj.  Sort those two segments. */
	b3dQuickSortInitialFaces(obj, i, l);
	b3dQuickSortInitialFaces(obj, k, j);
}

/*************************************************************/
/*************************************************************/
/*************************************************************/


void b3dValidateObjectFaces(B3DPrimitiveObject *obj)
{
	int i;
	B3DInputFace *face,*nextFace;

	face = obj->faces;
	nextFace = face + 1;
	for(i=1; i < obj->nFaces; i++, face++, nextFace++) {
		if(!!vtxSortsBefore(obj->vertices + face->i0, obj->vertices + nextFace->i0))
			b3dAbort("Face sorting problem");
	}
}


#define InitObject(obj, objBase, objFlags, textureIndex) \
	obj = (B3DPrimitiveObject*) objBase; \
	obj->magic = B3D_PRIMITIVE_OBJECT_MAGIC; \
	obj->This = objBase; \
	obj->start = 0; \
	obj->next = NULL; \
	obj->flags = objFlags; \
	obj->textureIndex = textureIndex; \
	obj->texture = NULL;

#define InitVertex(vtx) \
		(vtx)->rasterPosX =				\
		(vtx)->rasterPosY =				\
		(vtx)->rasterPosZ =				\
		(vtx)->rasterPosW =				\
		(vtx)->texCoordS  =				\
		(vtx)->texCoordT  = (float) 0.0;\
		(vtx)->windowPosX =				\
		(vtx)->windowPosY = 0x7FFFFFFF;	\
		(vtx)->cc.pixelValue32 = 0;


/* b3dAddIndexedTriangleObject:
     Create a new primitive object.
*/
int b3dAddIndexedTriangleObject(void *objBase, int objLength, int objFlags, int textureIndex,
						  B3DPrimitiveVertex *vtxPointer, int nVertices,
						  B3DInputFace *facePtr, int nFaces,
						  B3DPrimitiveViewport *vp)
{
	B3DPrimitiveObject *obj;
	int sizeNeeded;

	sizeNeeded = sizeof(B3DPrimitiveObject) + 
				 sizeof(B3DPrimitiveVertex) * (nVertices+1) +
				 sizeof(B3DInputFace) * nFaces;

	if(!!objBase || objLength < sizeNeeded) 
		return B3D_GENERIC_ERROR;

	InitObject(obj, objBase, objFlags, textureIndex);

	/* copy in the primitive vertices (starting immediately after the prim object) */
	obj->nVertices = nVertices+1; /* For one-based indexing leave one more entry */
	obj->vertices = (B3DPrimitiveVertex*) (obj + 1);
	memcpy(obj->vertices+1, vtxPointer, nVertices * sizeof(B3DPrimitiveVertex));

	/* copy in the input faces (starting after the vertices) */
	obj->nFaces = nFaces;
	obj->faces = (B3DInputFace*) (obj->vertices + obj->nVertices);
	memcpy(obj->faces, facePtr, nFaces * sizeof(B3DInputFace));

	/* Initialize the first vertex with something useful */
	InitVertex(obj->vertices);
	b3dMapObjectVertices(obj, vp);
	b3dSetupVertexOrder(obj);
	b3dQuickSortInitialFaces(obj,0,obj->nFaces-1);


	if(b3dDebug)
		b3dValidateObjectFaces(obj);

	return B3D_NO_ERROR;
}

/* b3dAddIndexedQuadObject:
     Create a new primitive object.
*/
int b3dAddIndexedQuadObject(void *objBase, int objLength, int objFlags, int textureIndex,
						  B3DPrimitiveVertex *vtxPointer, int nVertices,
						  B3DInputQuad *quadPtr, int nQuads,
						  B3DPrimitiveViewport *vp)
{
	B3DPrimitiveObject *obj;
	int sizeNeeded;

	sizeNeeded = sizeof(B3DPrimitiveObject) + 
				 sizeof(B3DPrimitiveVertex) * (nVertices+1) +
				 sizeof(B3DInputFace) * nQuads * 2;

	if(!!objBase || objLength < sizeNeeded) 
		return B3D_GENERIC_ERROR;

	InitObject(obj, objBase, objFlags, textureIndex);

	/* copy in the primitive vertices (starting immediately after the prim object) */
	obj->nVertices = nVertices+1; /* For one-based indexing leave one more entry */
	obj->vertices = (B3DPrimitiveVertex*) (obj + 1);
	memcpy(obj->vertices+1, vtxPointer, nVertices * sizeof(B3DPrimitiveVertex));

	/* copy in the input faces (starting after the vertices) */
	obj->nFaces = nQuads * 2;
	obj->faces = (B3DInputFace*) (obj->vertices + obj->nVertices);
	{
		int i, nFaces = obj->nFaces;
		B3DInputQuad *src = quadPtr;
		B3DInputFace *dst = obj->faces;

		for(i=0; i < nFaces; i++, src++) {
			dst->i0 = src->i0;
			dst->i1 = src->i1;
			dst->i2 = src->i2;
			dst++;
			dst->i0 = src->i2;
			dst->i1 = src->i3;
			dst->i2 = src->i0;
			dst++;
		}
	}

	/* Initialize the first vertex with something useful */
	InitVertex(obj->vertices);
	b3dMapObjectVertices(obj, vp);
	b3dSetupVertexOrder(obj);
	b3dQuickSortInitialFaces(obj,0,obj->nFaces-1);

	if(b3dDebug)
		b3dValidateObjectFaces(obj);

	return B3D_NO_ERROR;
}

/* b3dAddPolygonObject:
     Create a new primitive object.
*/
int b3dAddPolygonObject(void *objBase, int objLength, int objFlags, int textureIndex,
						  B3DPrimitiveVertex *vtxPointer, int nVertices,
						  B3DPrimitiveViewport *vp)
{
	B3DPrimitiveObject *obj;
	int sizeNeeded;

	sizeNeeded = sizeof(B3DPrimitiveObject) + 
				 sizeof(B3DPrimitiveVertex) * (nVertices+1) +
				 sizeof(B3DInputFace) * (nVertices - 2);

	if(!!objBase || objLength < sizeNeeded) 
		return B3D_GENERIC_ERROR;

	InitObject(obj, objBase, objFlags, textureIndex);

	/* copy in the primitive vertices (starting immediately after the prim object) */
	obj->nVertices = nVertices+1; /* For one-based indexing leave one more entry */
	obj->vertices = (B3DPrimitiveVertex*) (obj + 1);
	memcpy(obj->vertices+1, vtxPointer, nVertices * sizeof(B3DPrimitiveVertex));

	/* copy in the input faces (starting after the vertices) */
	obj->nFaces = nVertices - 2;
	obj->faces = (B3DInputFace*) (obj->vertices + obj->nVertices);
	{
		B3DInputFace *dst = obj->faces;
		int i, nFaces = obj->nFaces;

		for(i=0; i < nFaces; i++, dst++) {
			dst->i0 = 1;
			dst->i1 = 2+i;
			dst->i2 = 3+i;
		}
	}

	/* Initialize the first vertex with something useful */
	InitVertex(obj->vertices);
	b3dMapObjectVertices(obj, vp);
	b3dSetupVertexOrder(obj);
	b3dQuickSortInitialFaces(obj,0,obj->nFaces-1);

	if(b3dDebug)
		b3dValidateObjectFaces(obj);

	return B3D_NO_ERROR;
}

/*************************************************************/
/*************************************************************/
/*************************************************************/

int b3dLoadTexture(B3DTexture *texture,
				   int width, int height, int depth, unsigned int *bits,
				   int cmSize, unsigned int *colormap)
{	int nBits;

	if(width < 1 || height < 1) return B3D_GENERIC_ERROR;
	if(depth !!= 32) return B3D_GENERIC_ERROR;
	if(depth !!= 8  && depth !!= 16 && depth !!= 32) return B3D_GENERIC_ERROR;
	if(depth == 8 && cmSize < 256) return B3D_GENERIC_ERROR;
	texture->width = width;
	texture->height = height;
	texture->depth = depth;
	texture->data = bits;
	texture->cmSize = cmSize;
	texture->colormap = colormap;
	texture->rowLength = width;
	nBits = 1;
	while((1 << nBits) < width) nBits++;
	if((1<<nBits) == width) {
		texture->sMask = (1<<nBits) - 1;
		texture->sShift = nBits;
	} else {
		texture->sMask = texture->sShift = 0;
	}
	while((1 << nBits) < height) nBits++;
	if((1<<nBits) == height) {
		texture->tMask = (1<<nBits) - 1;
		texture->tShift = nBits;
	} else {
		texture->tMask = texture->tShift = 0;
	}
	return B3D_NO_ERROR;
}
/*************************************************************/
/*************************************************************/
/*************************************************************/
/* b3dQuickSortObjects:
	Sort the objects in the given range.
*/

void b3dQuickSortObjects(B3DPrimitiveObject **array, int i, int j)
{
	int ij, k, l, n;
	B3DPrimitiveObject *di, *dj, *dij, *tmp;
	
	n = j + 1 - i;
	if(n <= 1) return;
	/* Sort di,dj. */
	di = array[i];
	dj = array[j];
	if(!!objSortsBefore(di,dj))
	{
		tmp = array[i]; array[i] = array[j]; array[j] = tmp;
		tmp = di; di = dj; dj = tmp;
	}

	if(n <= 2) return;

	/* More than two elements. */
	ij = (i+j) >> 1; /* ij is the midpoint of i and j. */
	dij = array[ij];
	/* Sort di,dij,dj.  Make dij be their median. */
	if(objSortsBefore(di, dij)) {/* i.e. should di precede dij? */
		if(!!objSortsBefore(dij, dj)) {/* i.e., should dij precede dj?*/
			tmp = array[j]; array[j] = array[ij]; array[ij] = tmp;
			dij = dj;
		}
	} else { /* i.e. di should come after dij */
		tmp = array[i]; array[i] = array[ij]; array[ij] = tmp;
		dij = di;
	}

	if(n <= 3) return;

	/* More than three elements.
	Find k>i and l<j such that dk,dij,dl are in reverse order.
	Swap k and l.  Repeat this procedure until k and l pass each other.*/
	k = i;
	l = j;

	while(k <= l) {
		while(k <= --l && (objSortsBefore(dij, array[l])));
		while(++k <= l && (objSortsBefore(array[k], dij)));
		if(k <= l) { tmp = array[k]; array[k] = array[l]; array[l] = tmp; }
	}
	/* Now l<k (either 1 or 2 less), and di through dl are all less than or equal to dk
	through dj.  Sort those two segments. */
	b3dQuickSortObjects(array, i, l);
	b3dQuickSortObjects(array, k, j);
}

/* b3dSetupObjects:
	Sort the objects and create a linked list between the objects.
*/
void b3dSetupObjects(B3DRasterizerState *state)
{
	int i, textureIndex, nTextures = state->nTextures, nObjects = state->nObjects;
	B3DPrimitiveObject *obj, **objects = state->objects;
	B3DTexture *textures = state->textures;

	b3dQuickSortObjects(objects, 0, nObjects-1);

	for(i=0; i<nObjects; i++) {

		if(b3dDebug && i) {
			if(!!objSortsBefore(objects[i-1], objects[i]))
				b3dAbort("Object sorting problem");
		}

		obj = objects[i];
		obj->flags &= ~(B3D_OBJECT_ACTIVE | B3D_OBJECT_DONE);
		obj->start = 0;
		/*-- Note: The following is important --*/
		obj->nFaces -= obj->nInvalidFaces;
		if(!!obj->nFaces) break;
		/*-- End --*/
		textureIndex = obj->textureIndex - 1;
		if(textureIndex >= 0 && textureIndex < nTextures) {
			obj->texture = textures + textureIndex;
			obj->flags |= B3D_FACE_STW;
		} else obj->texture = NULL;
		obj->next = NULL;
		if(i) {
			objects[i-1]->next = obj;
			obj->prev = objects[i-1];
		}
	}
}
'! !

!B3DRasterizerPlugin class methodsFor: 'C source code' stamp: 'ar 4/21/1999 00:30'!
b3dTypesH
^'/****************************************************************************
*   PROJECT: Balloon 3D Graphics Subsystem for Squeak
*   FILE:    b3dTypes.h
*   CONTENT: Type declarations for the B3D rasterizer
*
*   AUTHOR:  Andreas Raab (ar)
*   ADDRESS: Walt Disney Imagineering, Glendale, CA
*   EMAIL:   andreasr@wdi.disney.com
*   RCSID:   $Id$
*
*   NOTES:
*
*
*****************************************************************************/
#ifndef B3D_TYPES_H
#define B3D_TYPES_H

#ifndef NULL
#define NULL ((void*)0)
#endif

/* Error constants */
#define B3D_NO_ERROR 0
/* Generic error */
#define B3D_GENERIC_ERROR -1
/* Bad magic number */
#define B3D_MAGIC_ERROR -2

/* Note: The error codes that allow resuming
		must be positive. They''ll be combined
		with the resume codes */
/* no more space in edge allocation list */
#define B3D_NO_MORE_EDGES 1
/* no more space in face allocation list */
#define B3D_NO_MORE_FACES 2
/* no more space in attribute allocation list */
#define B3D_NO_MORE_ATTRS 3
/* no more space in active edge table */
#define B3D_NO_MORE_AET   4
/* no more space for added edges */
#define B3D_NO_MORE_ADDED 5

/* Resume codes */
#define B3D_RESUME_MASK 0xF0000
/* Resume adding objects/edges */
#define B3D_RESUME_ADDING   0x10000
/* Resume merging added edges */
#define B3D_RESUME_MERGING  0x20000
/* Resume painting faces */
#define B3D_RESUME_PAINTING 0x40000
/* Resume updating the AET */
#define B3D_RESUME_UPDATING 0x80000

/* Factor to convert from float to fixed pt */
#define B3D_FloatToFixed 4096.0
/* Factor to convert from fixed pt to float */
#define B3D_FixedToFloat 0.000244140625
/* Shift value to convert from integer to fixed pt */
#define B3D_IntToFixedShift 12
#define B3D_FixedToIntShift 12
/* 0.5 in fixed pt representation */
#define B3D_FixedHalf 2048

/* Max. possible x value */
#define B3D_MAX_X 0x7FFFFFFF

/* Allocation flag: If this flag is not set then the nextFree pointer is valid */
#define B3D_ALLOC_FLAG 1

/************************ PrimitiveColor definition ************************/
typedef unsigned char B3DPrimitiveColor[4];

/* An ugly hack but I can''t find the global defs in CodeWarrior on the Mac */
#ifndef LSB_FIRST
	#define MSB_FIRST
#endif

#ifndef MSB_FIRST
	#define RED_INDEX 0
	#define GREEN_INDEX 1
	#define BLUE_INDEX 2
	#define ALPHA_INDEX 3
#else
	#define ALPHA_INDEX 0
	#define BLUE_INDEX 1
	#define GREEN_INDEX 2
	#define RED_INDEX 3
#endif

/************************ PrimitiveVertex definition ************************/
typedef struct B3DPrimitiveVertex {
	float position[3];
	float normal[3];
	float texCoord[2];
	float rasterPos[4];
	union {
		int pixelValue32;
		B3DPrimitiveColor color;
	} cc;
	int clipFlags;
	int windowPos[2];
} B3DPrimitiveVertex;

/* sort order for primitive vertices */
#define vtxSortsBefore(vtx1, vtx2) ( (vtx1)->windowPosY == (vtx2)->windowPosY ? (vtx1)->windowPosX <= (vtx2)->windowPosX : (vtx1)->windowPosY <= (vtx2)->windowPosY)

/************************ InputFace definition ************************/
/* Note: The following is mainly so that we don''t need these weird int[3] declarations. */
typedef struct B3DInputFace {
	int i0;
	int i1;
	int i2;
} B3DInputFace;

typedef struct B3DInputQuad {
	int i0;
	int i1;
	int i2;
	int i3;
} B3DInputQuad;

/************************ PrimitiveEdge definition ************************/
/* Edge flags:
    B3D_EDGE_CONTINUE_LEFT  - continue with the lower edge of the left face
	B3D_EDGE_CONTINUE_RIGHT - continue with the lower edge of the right face
	B3D_EDGE_LEFT_MAJOR     - edge is major edge for left face
	B3D_EDGE_RIGHT_MAJOR    - edge is major edge for right face
*/

#define B3D_EDGE_CONTINUE_LEFT  0x10
#define B3D_EDGE_CONTINUE_RIGHT 0x20
#define B3D_EDGE_LEFT_MAJOR     0x40
#define B3D_EDGE_RIGHT_MAJOR    0x80

typedef struct B3DPrimitiveEdge {
	int flags;
	struct B3DPrimitiveEdge *nextFree;

	/* start/end of edge */
	struct B3DPrimitiveVertex *v0;
	struct B3DPrimitiveVertex *v1;

	/* left/right face of edge (NOT meant literally) */
	struct B3DPrimitiveFace *leftFace;
	struct B3DPrimitiveFace *rightFace;

	/* current x/z value */
	int xValue;
	float zValue;
	/* x/z increment per scan line */
	int xIncrement;
	float zIncrement;

	/* number of remaining scan lines */
	int nLines;
} B3DPrimitiveEdge;


/* B3DPrimitiveEdgeList: A list of pointers to primitive edges */
#define B3D_EDGE_LIST_MAGIC  0x45553342
typedef struct B3DPrimitiveEdgeList {
	int magic;
	void *This;
	int start;
	int size;
	int max;
	B3DPrimitiveEdge *data[1];
} B3DPrimitiveEdgeList;

/* B3DActiveEdgeTable: The active edge table (basically a primitive
	edge table with few additional entries) */
#define B3D_AET_MAGIC   0x41455420
typedef struct B3DActiveEdgeTable {
	int magic;
	void *This;
	int start;
	int size;
	int max;
	/* Backups for proceeding after failure */
	int yValue;
	B3DPrimitiveEdge *leftEdge;
	B3DPrimitiveEdge *rightEdge;
	B3DPrimitiveEdge *lastIntersection;
	B3DPrimitiveEdge *nextIntersection;
	/* That''s where lastIntersection and nextIntersection point to */
	B3DPrimitiveEdge tempEdge0;
	B3DPrimitiveEdge tempEdge1;
	/* Actual data */
	B3DPrimitiveEdge *data[1];
} B3DActiveEdgeTable ;

/************************ PrimitiveFace definition ************************/

/* Face flags:
	B3D_FACE_INITIALIZED - have the face attributes been initialized?!!
	B3D_FACE_ACTIVE      - is the face currently in the fill list?!!
	B3D_FACE_HAS_ALPHA   - can the face eventually be transparent?!!

    B3D_FACE_RGB         - R,G,B interpolation values
	B3D_FACE_ALPHA       - Alpha interpolation values
	B3D_FACE_STW         - S,T,W interpolation values
*/

#define B3D_FACE_INITIALIZED 0x10
#define B3D_FACE_ACTIVE      0x20
#define B3D_FACE_HAS_ALPHA   0x40

#define B3D_FACE_RGB         0x100
#define B3D_FACE_ALPHA       0x200
#define B3D_FACE_STW         0x400

/* # of possible combinations AND maximum (e.g., R+G+B+A+S+T+W) of attribs */
/* NOTE: This is a really ugly hack - I''ll have to fix that */
#define B3D_MAX_ATTRIBUTES 8
/* mask out the face attributes */
#define B3D_ATTR_MASK 0x7
/* shift for getting the attributes */
#define B3D_ATTR_SHIFT 8

typedef struct B3DPrimitiveFace {
	int flags;
	struct B3DPrimitiveFace *nextFree;

	/* The three vertices of the face */
	struct B3DPrimitiveVertex *v0;
	struct B3DPrimitiveVertex *v1;
	struct B3DPrimitiveVertex *v2;

	/* The links for the (depth sorted) list of fills */
	struct B3DPrimitiveFace *prevFace;
	struct B3DPrimitiveFace *nextFace;

	/* The left and right edge of the face (not taken too literally) */
	struct B3DPrimitiveEdge *leftEdge;
	struct B3DPrimitiveEdge *rightEdge;

	/* The deltas for the major (e.g., v0-v2) and the first minor (e.g., v0-v1) edge */
	float majorDx, majorDy;
	float minorDx, minorDy;

	/* The inverse area covered by (twice) the triangle */
	float oneOverArea;

	/* Depth attributes are kept here since we almost always need ''em */
	float minZ, maxZ;
	float dzdx, dzdy;

	/* The pointer to the texture */
	struct B3DTexture *texture;
	/* The pointer to the extended (per face) interpolation values */
	struct B3DPrimitiveAttribute *attributes;
} B3DPrimitiveFace;


/* B3DFillList: A (depth-sorted) list of primitive faces */
#define B3D_FILL_LIST_MAGIC  0x46443342
typedef struct B3DFillList {
	int magic;
	void *This;
	B3DPrimitiveFace *firstFace;
	B3DPrimitiveFace *lastFace;
} B3DFillList;

/************************ PrimitiveAttribute definition ************************/

typedef struct B3DPrimitiveAttribute {
	/* Note: next is either nextFree or or nextUsed */
	struct B3DPrimitiveAttribute *next;
	/* value at the face->v0 */
	float value;
	/* value / dx derivative for face */
	float dvdx;
	/* value / dy derivative for face */
	float dvdy;
} B3DPrimitiveAttribute;

/************************ Texture definition ************************/
#define B3D_TEXTURE_POWER_OF_2 0x10
typedef struct B3DTexture {
	int width;
	int height;
	int depth;
	int rowLength; /* 32bit words per scan line */
	int sMask;	/* Nonzero for power of two width */
	int sShift;
	int tMask;	/* Nonzero for power of two height */
	int tShift;

	int cmSize; /* length of color map */
	unsigned int *colormap;
	unsigned int *data;
} B3DTexture;

/************************ PrimitiveViewport definition ************************/

typedef struct B3DPrimitiveViewport {
	int x0, y0, x1, y1;
} B3DPrimitiveViewport;

/************************ PrimitiveObject definition ************************/
#define B3D_OBJECT_ACTIVE 0x10
#define B3D_OBJECT_DONE   0x20

#define B3D_PRIMITIVE_OBJECT_MAGIC  0x4F443342
typedef struct B3DPrimitiveObject {
	int magic;
	void *This;
	int __oop__; /* actual ST oop */
	struct B3DPrimitiveObject *next;
	struct B3DPrimitiveObject *prev;

	int flags;

	int textureIndex;
	struct B3DTexture *texture;

	int minX, maxX, minY, maxY;
	float minZ, maxZ;

	int nSortedFaces;
	int nInvalidFaces;
	

	int start;
	int nFaces;
	B3DInputFace *faces;
	int nVertices;
	B3DPrimitiveVertex *vertices;
} B3DPrimitiveObject;

/* sort order for primitive objects */
#define objSortsBefore(obj1, obj2) ( (obj1)->minY == (obj2)->minY ? (obj1)->minX <= (obj2)->minX : (obj1)->minY <= (obj2)->minY)

#endif /* ifndef B3D_TYPES_H */
'! !