// Copyright (C) 1996 Keith Whitwell.
// This file may only be copied under the terms of the GNU Library General
// Public License - see the file COPYING in the lib3d distribution.

#include <Lib3d/Model.H>
#include <Lib3d/Light.H>
#include <Lib3d/internals/Material.H>
#include <Lib3d/FlatPipeline.H>
#include <Lib3d/ColourRamp.H>
#include <minmax.h>


FlatPipeline::ClipFunc FlatPipeline::Intersect[] = { 
    intersectZ1,
    intersectZ2,
    intersectY1,
    intersectY2,
    intersectX1,
    intersectX2 
};

extern float D;

FlatPipeline::FlatPipeline()
    : thisFrame(0),
      renderFlags(0),
      sizeNpool(256),
      npool(new Flat_NormalData[sizeNpool]),
      nrVpool(0),
      sizeVpool(256),
      vpool(new Flat_VertexData[sizeVpool]),
      nrLMpool(0),
      sizeLMpool(256),
      lmpool(new Flat_LightMaterialData[sizeLMpool]),
      nrLNpool(0),
      sizeLNpool(256),
      lnpool(new Flat_LightNormalData[sizeLNpool]),
      nrMNpool(0),
      sizeMNpool(256),
      mnpool(new Flat_MaterialNormalData[sizeMNpool]),
      sizeMpool(8),
      mpool(new Flat_MaterialData[sizeMpool]),
      nrPpool(0),
      sizePpool(256),
      ppool(new Flat_PolygonData[sizePpool]),
      pv(new (PipelineData*)[MAX_CLIPPED_VERTICES])
{
}

FlatPipeline::~FlatPipeline()
{
    delete npool;
    delete vpool;
    delete lmpool;
    delete lnpool;
    delete mnpool;
    delete mpool;
    delete ppool;
    delete pv;
}

void
FlatPipeline::registerModel(  Model& model )
{
    stitchModel( model );

    // Ensure we have room for temporary vertices.

    uint maxVertices = nrVertices + MAX_CLIPPED_VERTICES;
    if (sizeVpool < maxVertices) {
	while ((sizeVpool *= 2) < maxVertices);
	delete [] vpool;
	vpool = new Flat_VertexData[sizeVpool];
    }

    if (sizeMpool < nrMaterials) {
	while ((sizeMpool *= 2) < nrMaterials);
	delete [] mpool;
	mpool = new Flat_MaterialData[sizeMpool];
    }

    if (sizePpool < nrPolygons) {
	while ((sizePpool *= 2) < nrPolygons);
	delete [] ppool;
	ppool = new Flat_PolygonData[sizePpool];
    }

    if (sizeNpool < nrPolygonNormals) {
	while ((sizeNpool *= 2) < nrPolygonNormals);
	delete [] npool;
	npool = new Flat_NormalData[sizeNpool];
    }
}

void 
FlatPipeline::expand( uint nrLights )
{
    nrLMpool = nrMaterials * nrLights;
    if (sizeLMpool < nrLMpool ) {
	while ((sizeLMpool *= 2) < nrLMpool );
	delete [] lmpool;
	lmpool = new Flat_LightMaterialData[sizeLMpool];
    }

    nrLNpool = nrPolygonNormals * nrLights;
    if (sizeLNpool < nrLNpool ) {
	while ((sizeLNpool *= 2) < nrLNpool );
	delete [] lnpool;
	lnpool = new Flat_LightNormalData[sizeLNpool];
    }
}


void 
FlatPipeline::render(Model &model,
		     Viewport &viewport, 
		     const Light *lights, 
		     uint nrLights,
		     uint clipPlanes,
		     uint flags)
{
    stitchModel(model);
    expand(nrLights);

    // The pipeline proper.

    renderFlags = flags;
    thisFrame++;
    have_backface_info = false;
    clip = false;

    if ( !clipPlanes ) {
	transform( viewport );
    } else if ( !transformForClipping( viewport ) ) {
	return;
    }

    if (!clip) {
	using_lit_normals =  (nrLights && 
			      (nrPolygonNormals*nrMaterials*2 < nrPolygons));
	// using_lit_normals = 0;
	if (using_lit_normals) {
	    cullBackFaces();	
	    calculateLightData( viewport, lights, nrLights );
	    renderPolygons( viewport, nrLights ); 
	} else {
	    calculateLightData( viewport, lights, nrLights );
	    cullAndRenderPolygons( viewport, nrLights ); // cheaper cull
	}
    } else {
	using_lit_normals = (nrLights &&
			     (nrPolygonNormals*nrMaterials < nrPolygons));
	// using_lit_normals = 0;
	cullBackFaces();	
	calculateLightData( viewport, lights, nrLights );
	clipAndRenderPolygons( viewport, nrLights );
    }

    viewport.setDirty( xmin, ymin, xmax, ymax );
}


void
FlatPipeline::calculateLightData(Viewport &viewport, 
				 const Light *light, 
				 uint nrLights )
{
    if_debug {
       debug() << " nrLights:" << nrLights
	       << " uniformDiffuse: "<<((renderFlags & uniformDiffuse)?"y":"n")
 	       << " using_lit_normals: " << (using_lit_normals?"y":"n")
	       << " have_backface_info: " << (have_backface_info?"y":"n")
	       << endlog;
    }

    if (renderFlags & uniformDiffuse) {
	calculateIntensityData( viewport, light, nrLights );
    } else {
	calculateRGBData( viewport, light, nrLights );
    }
}
 

void 
FlatPipeline::calculateRGBData(Viewport &viewport,
			       const Light *light,
			       uint nrLights)
{
    //	if_lighting_change
    Flat_MaterialData *m = mpool;
    const Material *mat = materials;
    Flat_LightMaterialData *lm = lmpool;
    for (uint i = 0 ; i < nrMaterials ; i++ ) {
	m->ambient.assign(0,0,0);
	const Light *l = light;
	while (l) {
	    const Vector3 &a = l->getAmbient();
	    m->ambient.v[R] += mat->ambient.v[R] * a.v[R];
	    m->ambient.v[G] += mat->ambient.v[G] * a.v[G];
	    m->ambient.v[B] += mat->ambient.v[B] * a.v[B];
	    
	    const Vector3 &ld = l->getDiffuse();
	    const Vector3 &md = mat->diffuse;
	    lm->diffuse.v[R] = md.v[R] * ld.v[R];
	    lm->diffuse.v[G] = md.v[G] * ld.v[G];
	    lm->diffuse.v[B] = md.v[B] * ld.v[B];
	    
	    lm++;
	    l = l->getNextLight();
	}
	m++;
	mat++;
    }

    
    // if_lighting_change_or_object_change 

    const Light *l = light;
    Flat_LightNormalData *ln = lnpool;
    int idx = 0;
    Vector3 pov;

    if (have_backface_info) {
	while (l) {
	    pov.mul_T( *objectToCvv_T, l->getCvvPov() );
	    pov.normalize();	
	    // skip the normalize when obTocvvT is angle preserving.
	    
	    for (uint i = 0 ; i < nrPolygonNormals ; i++, ln++ ) {
		if (npool[i].front == thisFrame) {
		    ln->dotprod = dot( polygonNormals[i].model, pov );
		}
	    }
	    
	    l = l->getNextLight();
	    idx++;
	}

	if (using_lit_normals) {

	    nrMNpool = nrMaterials * nrPolygonNormals;
	    if (sizeMNpool < nrMNpool ) {
		while ((sizeMNpool *= 2) < nrMNpool );
		delete [] mnpool;
		mnpool = new Flat_MaterialNormalData[sizeMNpool];
	    }

	    
	    Flat_MaterialNormalData *mn = mnpool;
	    Flat_MaterialData *mp = mpool;
	    Flat_LightMaterialData *lm = lmpool;
	    Flat_NormalData *nn = npool;

	    uint i = nrMaterials;
	    do {
		Flat_LightNormalData *ln = lnpool;    
		uint n = nrPolygonNormals;
		do {
		    if (nn->front == thisFrame) {
			Vector3 colour(mp->ambient);
			Flat_LightNormalData *lnn = ln;    
			Flat_LightMaterialData *lmm = lm;
			uint l = nrLights;
			do {
			    float dp = lnn->dotprod;
			    if (dp > 0) {
				colour.v[R] += lmm->diffuse.v[R] * dp;
				colour.v[G] += lmm->diffuse.v[G] * dp;
				colour.v[B] += lmm->diffuse.v[B] * dp;
			    }
			    lmm++;
			    lnn += nrPolygonNormals;
			} while (--l);
			
			uint r = min(uint(255.0 * colour.v[R]), uint(255));
			uint g = min(uint(255.0 * colour.v[G]), uint(255));
			uint b = min(uint(255.0 * colour.v[B]), uint(255));
			
			mn->colour = viewport.getColour(r,g,b);
		    }
		    mn++;
		    ln++;
		    nn++;
		} while (--n);
		mp++;
		lm += nrLights;
	    } while (--i);
	}
    } else {
	while (l) {
	    pov.mul_T( *objectToCvv_T, l->getCvvPov() );
	    pov.normalize();	
	    // skip the normalize when obTocvvT is angle preserving.
	    
	    for (uint i = 0 ; i < nrPolygonNormals ; i++, ln++ ) {
		ln->dotprod = dot( polygonNormals[i].model, pov );
	    }
	    
	    l = l->getNextLight();
	    idx++;
	}

	
	if (using_lit_normals) {

	    nrMNpool = nrMaterials * nrPolygonNormals;
	    if (sizeMNpool < nrMNpool ) {
		while ((sizeMNpool *= 2) < nrMNpool );
		delete [] mnpool;
		mnpool = new Flat_MaterialNormalData[sizeMNpool];
	    }

	    
	    Flat_MaterialNormalData *mn = mnpool;
	    Flat_MaterialData *mp = mpool;
	    Flat_LightMaterialData *lm = lmpool;
	    Flat_NormalData *nn = npool;

	    uint i = nrMaterials;
	    do {
		Flat_LightNormalData *ln = lnpool;    
		uint n = nrPolygonNormals;
		do {
		    Vector3 colour(mp->ambient);
		    Flat_LightNormalData *lnn = ln;    
		    Flat_LightMaterialData *lmm = lm;
		    uint l = nrLights;
		    do {
			float dp = lnn->dotprod;
			if (dp > 0) {
			    colour.v[R] += lmm->diffuse.v[R] * dp;
			    colour.v[G] += lmm->diffuse.v[G] * dp;
			    colour.v[B] += lmm->diffuse.v[B] * dp;
			}
			lmm++;
			lnn += nrPolygonNormals;
		    } while (--l);
		    
		    uint r = min(uint(255.0 * colour.v[R]), uint(255));
		    uint g = min(uint(255.0 * colour.v[G]), uint(255));
		    uint b = min(uint(255.0 * colour.v[B]), uint(255));
		    mn->colour = viewport.getColour(r,g,b);

		    mn++;
		    ln++;
		    nn++;
		} while (--n);
		mp++;
		lm += nrLights;
	    } while (--i);
	}
    }
}

void 
FlatPipeline::calculateIntensityRamps(Viewport &viewport,
				      const Light *light,
				      uint nrLights)
{ 
    Material *m = materials;
    for (uint i = 0 ; i < nrMaterials ; i++ ) {
	if (m->ramp == 0) m->ramp = new ColourRamp;
	if (nrLights) {
	    Vector3 amb;
	    Vector3 dif;
	    amb.assign(0,0,0);
	    const Light *l = light;
	    do {
		Vector3 tmp(l->getAmbient());
		tmp.scale(m->Ka);
		amb.add( tmp );
		l = l->getNextLight();
	    } while(l);
	    amb.scale(255.0);
	    amb.clamp(255.0);
	    
	    dif.assign( light->getDiffuse() );
	    dif.scale( 255.0 );
	    dif.scale( m->diffuse );
	    m->ramp->build( viewport, amb, dif );
	} else {
	    Vector3 tmp;
	    tmp.scale(m->colour, 255.0);
	    m->ramp->fallback( viewport, tmp );
	}
	    
	m++;
    }
}


void 
FlatPipeline::calculateIntensityData(Viewport &viewport,
				     const Light *light,
				     uint nrLights)
{
    if (renderFlags & lightColourChange || materials[0].ramp == 0) {
	calculateIntensityRamps(viewport, light, nrLights);
    }
    
    uint i = nrPolygonNormals; 
    Flat_NormalData *n = npool;
    do {
	n->sumDotProd = 0.0;
	n++;
    } while (--i);
	
    if (nrLights) {
	const Light *l = light;
	Vector3 pov;

	while (l) {
	    pov.mul_T( *objectToCvv_T, l->getCvvPov() );
	    pov.normalize();	
	    
	    Flat_NormalData *n = npool;
	    const Normal *nn = polygonNormals;
	    uint i = nrPolygonNormals; 
	    if (have_backface_info) {
		do {
		    if (n->front == thisFrame) {
			float dp = dot(nn->model,pov);
			if (dp > 0) n->sumDotProd += dp;
		    }
		    n++;
		    nn++;
		} while (--i);
	    } else {
		do {
		    float dp = dot(nn->model,pov);
		    if (dp > 0) n->sumDotProd += dp;
		    n++;
		    nn++;
		} while (--i);
	    }	    
	    l = l->getNextLight();
	}

	Flat_NormalData *n = npool;
	uint i = nrPolygonNormals; 
	do {
	    n->intensity = min(uint(255), uint(n->sumDotProd * 255.0));
	    n++;
	} while (--i);
    }
}

inline
uint 
FlatPipeline::lightPolygon(const Polygon &poly, 
			   Viewport &viewport, 
			   uint nrLights )
{
    if (renderFlags & uniformDiffuse) {
	return materials[poly.material].ramp->
	    getColour(npool[poly.normal].intensity);
    } else {
	if (using_lit_normals) {
	    return mnpool[poly.normal+nrPolygonNormals*poly.material].colour;
	} else {
	    Vector3 colour;
	    colour.assign(mpool[poly.material].ambient);
	    
	    Flat_LightMaterialData *lm = &lmpool[ poly.material * nrLights ];
	    Flat_LightNormalData *ln = &lnpool[ poly.normal ];    
	    
	    uint l = nrLights;
	    do {
		float dp = ln->dotprod;
		if (dp > 0) {
		    colour.v[R] += lm->diffuse.v[R] * dp;
		    colour.v[G] += lm->diffuse.v[G] * dp;
		    colour.v[B] += lm->diffuse.v[B] * dp;
		}
		lm++;
		ln += nrPolygonNormals;
	    } while (--l);

	    uint r = min(uint(255.0 * colour.v[R]), uint(255));
	    uint g = min(uint(255.0 * colour.v[G]), uint(255));
	    uint b = min(uint(255.0 * colour.v[B]), uint(255));
	    return viewport.getColour(r,g,b);
	}
    }
}

void
FlatPipeline::cullBackFaces()
{
    Vector3 tmp;
    const Polygon *poly = polygons;
    Flat_PolygonData *pd = ppool;

    have_backface_info = true;
    int i = nrPolygons;
    do {
	tmp.sub(vertices[poly->vertex0].model, *objectViewPos);
	if (dot(tmp, polygonNormals[poly->normal].model) < 0) {	    
	    pd->backface = true;
	} else {
	    npool[poly->normal].front = thisFrame;
	    pd->backface = false;
	}
	pd++;
	poly++;
    } while (--i);
}






// Transform for rendering without clipping
void
FlatPipeline::transform( Viewport &viewport )
{
    Flat_VertexData *vp = vpool;
    const Vertex *v = vertices;
    int j = nrVertices; 
    nrVpool = j;

    // Transform the first vertex here.

    vp->device.project( *objectToDevice, v->model );
    xmax = vp->device.v[X];
    xmin = vp->device.v[X];
    ymax = vp->device.v[Y];
    ymin = vp->device.v[Y];
    vp++;
    v++;
    j--;

    // Transform the remaining vertices.

    do {
	vp->device.project( *objectToDevice, v->model );
	if (xmax < vp->device.v[X]) {
	    xmax = vp->device.v[X];
	} 
	if (xmin > vp->device.v[X]) {
	    xmin = vp->device.v[X];
	} 
	if (ymax < vp->device.v[Y]) {
	    ymax = vp->device.v[Y];
	} 
	if (ymin > vp->device.v[Y]) {
	    ymin = vp->device.v[Y];
	} 
	vp++;
	v++;
    } while (--j);

    viewport.setDirty( xmin, ymin, xmax, ymax );
}

// Render
void
FlatPipeline::renderPolygons( Viewport &viewport, uint nrLights )
{
    for (int j = nrPolygons ; j-- ;  ) {
        const Polygon &poly = polygons[j];
	if (!ppool[j].backface) {
	    pv[0] = &vpool[poly.vertex0];
	    pv[1] = &vpool[poly.vertex1];
	    pv[2] = &vpool[poly.vertex2];

	    uint colour = lightPolygon(poly, viewport, nrLights);
	    viewport.flatTriangleZb(pv, colour);
	}
    }
}

void
FlatPipeline::cullAndRenderPolygons( Viewport &viewport, uint nrLights )
{
    for (int j = nrPolygons ; j-- ;  ) {
        const Polygon &poly = polygons[j];

	pv[0] = &vpool[poly.vertex0];
	pv[1] = &vpool[poly.vertex1];
	pv[2] = &vpool[poly.vertex2];
	
	bool cw =(   ((pv[1]->device.v[1] - pv[0]->device.v[1]) *
		      (pv[2]->device.v[0] - pv[0]->device.v[0]))
		  >= ((pv[1]->device.v[0] - pv[0]->device.v[0]) *
		      (pv[2]->device.v[1] - pv[0]->device.v[1])));

	if (cw) {
	    uint colour = lightPolygon(poly, viewport, nrLights);
	    viewport.flatTriangleZb(pv, colour);
	}
    }
}


// Transform for clipping
bool
FlatPipeline::transformForClipping( Viewport & )
{
    Flat_VertexData *vp = vpool;
    const Vertex *v = vertices;
    int j = nrVertices; 
    nrVpool = j;
    uint in = 0;
    uint all_oc = 0x3f;

    xmax = 0;
    xmin = 10000;		// arbitary bignum.
    ymax = 0;
    ymin = 10000;

#define NUMBITS	   sizeof(int)*8
#define v(x)	   *(int *) &(x)                        // fint(x) 
#define s(x)	   (((unsigned int)(x)) >> (NUMBITS-1)) // sign bit
#define a(x)	   ((x) & ~(1 << (NUMBITS-1)))	        // fint(abs(x))

    float one = 1.0;
    int i_one = v(one);
    int i_D = v(D);

    do {

#if 1
	// Adapted from graphics gems IV.

	vp->cvv.v[Z] = float((objectToCvv->v[2][0] * v->model.v[0]) +
			     (objectToCvv->v[2][1] * v->model.v[1]) +
			     (objectToCvv->v[2][2] * v->model.v[2]) + 
			     (objectToCvv->v[2][3]));

	uint oc;
	int iz = v(vp->cvv.v[Z]);
	int abs_z = a(iz);
	int s_iz = s(iz);

	vp->cvv.v[X] = float((objectToCvv->v[0][0] * v->model.v[0]) +
			     (objectToCvv->v[0][1] * v->model.v[1]) +
			     (objectToCvv->v[0][2] * v->model.v[2]) + 
			     (objectToCvv->v[0][3]));

	// Compare Z against D and 1.0

	oc  = (s(i_one - abs_z) & s_iz);       
	oc |= (s(abs_z - i_D) | s_iz) << 1;

	vp->cvv.v[Y] = float((objectToCvv->v[1][0] * v->model.v[0]) +
			     (objectToCvv->v[1][1] * v->model.v[1]) +
			     (objectToCvv->v[1][2] * v->model.v[2]) + 
			     (objectToCvv->v[1][3]));

	// Compare X and Z
	int ix = v(vp->cvv.v[X]);
	int diff_x = s(abs_z - a(ix));
	int tx = s(ix) + 4;
	oc |= diff_x << tx;          // oc |= 0, 0x04, or 0x08 

	// Compare Y and Z

	int iy = v(vp->cvv.v[Y]);
	int diff_y = s(abs_z - a(iy));
	int ty = s(iy) + 2;
	oc |= diff_y << ty;	  // oc |= 0, 0x10, or 0x20 
	vp->outcodes = oc;

#else
	vp->cvv.mul( *objectToCvv, v->model );
	uint outcodes = 0;
	if (vp->cvv.v[Z] >= 1.0) outcodes |= 0x01;
	if (vp->cvv.v[Z] <= D) outcodes |= 0x02;  
	if (vp->cvv.v[Y] >= vp->cvv.v[Z])  outcodes |= 0x04;
	if (vp->cvv.v[Y] <= -vp->cvv.v[Z]) outcodes |= 0x08;
	if (vp->cvv.v[X] >= vp->cvv.v[Z])  outcodes |= 0x10;
	if (vp->cvv.v[X] <= -vp->cvv.v[Z]) outcodes |= 0x20;

	vp->outcodes = outcodes;
#endif

	all_oc &= vp->outcodes;
	if ( !vp->outcodes ) {
	    in++;
	    vp->device.project( *cvvToDevice, vp->cvv );
	    if (xmax < vp->device.v[X]) {
		xmax = vp->device.v[X];
	    } 
	    if (xmin > vp->device.v[X]) {
		xmin = vp->device.v[X];
	    } 
	    if (ymax < vp->device.v[Y]) {
		ymax = vp->device.v[Y];
	    } 
	    if (ymin > vp->device.v[Y]) {
		ymin = vp->device.v[Y];
	    } 
	}
	vp++;
	v++;
    } while (--j);

    clip = (in != nrVertices);

    return all_oc == 0;     //in != 0; 
}


// Clip and Render
void
FlatPipeline::clipAndRenderPolygons( Viewport &viewport, uint nrLights )
{
    const Polygon *poly = polygons;
    Flat_PolygonData *pp = ppool;
    int j = nrPolygons;

    do {
	if (!pp->backface) {
	    
	    // optimistic - good for teapot program, but what about
	    // real usage?
	    
	    pv[0] = &vpool[poly->vertex0];
	    uint oc0 = vpool[poly->vertex0].outcodes;
	    pv[1] = &vpool[poly->vertex1];
	    uint oc1 = vpool[poly->vertex1].outcodes;
	    pv[2] = &vpool[poly->vertex2];
	    uint oc2 = vpool[poly->vertex2].outcodes;

	    if ((oc0&oc1&oc2) == 0) {
		uint intersections = oc0|oc1|oc2;
		uint colour = lightPolygon(*poly, viewport, nrLights);

		if (intersections == 0) {
		    viewport.flatTriangleZb(pv, colour);
		} else {
		    uint nr = nrVpool;
		    if (clipPolygon(*poly, intersections))
			viewport.flatPolygonZb(nrClippedVertices, pv, colour);
		    nrVpool = nr;	
		}
	    }
	}
	poly++;
	pp++;
    } while (--j);
}


void
FlatPipeline::intersectZ1( const Vector3& a, const Vector3& b, Vector3 &out )
{
    // Intersect all four components with Z=1
    Vector3 d;
    d.sub(b,a);
    float t = (1-a.v[Z]) / d.v[Z];
    out.v[X] = a.v[X] + t*d.v[X];
    out.v[Y] = a.v[Y] + t*d.v[Y];
    out.v[Z] = 1;
}


void
FlatPipeline::intersectZ2( const Vector3& a, const Vector3& b, Vector3 &out )
{
    // Intersect all four components with Z=::D 
    Vector3 d;
    d.sub(b,a);
    float t = (::D-a.v[Z]) / d.v[Z];
    out.v[X] = a.v[X] + t*d.v[X];
    out.v[Y] = a.v[Y] + t*d.v[Y];
    out.v[Z] = ::D;
}

void
FlatPipeline::intersectY1( const Vector3& a, const Vector3& b, Vector3 &out )
{
    // Intersect with Y=Z
    Vector3 d;
    d.sub(b,a);
    float t = (a.v[Y]-a.v[Z]) / (d.v[Z]-d.v[Y]);
    out.v[X] = a.v[X] + t*d.v[X];
    out.v[Z] = out.v[Y] = a.v[Y] + t*d.v[Y];
}

void
FlatPipeline::intersectY2( const Vector3& a, const Vector3& b, Vector3 &out )
{
    // Intersect with Y=-Z 
    Vector3 d;
    d.sub(b,a);
    float t = - (a.v[Y]+a.v[Z]) / (d.v[Z]+d.v[Y]);
    out.v[X] = a.v[X] + t*d.v[X];
    out.v[Z] = - (out.v[Y] = a.v[Y] + t*d.v[Y]);
}

void
FlatPipeline::intersectX1( const Vector3& a, const Vector3& b, Vector3 &out )
{
    // Intersect with X=Z 
    Vector3 d;
    d.sub(b,a);
    float t = (a.v[X]-a.v[Z]) / (d.v[Z]-d.v[X]);
    out.v[Y] = a.v[Y] + t*d.v[Y];
    out.v[Z] = out.v[X] = a.v[X] + t*d.v[X];
}

void
FlatPipeline::intersectX2( const Vector3& a, const Vector3& b, Vector3 &out )
{
    // Intersect with X=-Z 
    Vector3 d;
    d.sub(b,a);
    float t = -(a.v[X]+a.v[Z]) / (d.v[Z]+d.v[X]);
    out.v[Y] = a.v[Y] + t*d.v[Y];
    out.v[Z] = - (out.v[X] = a.v[X] + t*d.v[X]);
}


// Clipping in the truncated pyramid CVV.
//
//
bool
FlatPipeline::clipPolygon(const Polygon &poly, uint intersections )
{
    Flat_VertexData *tmp_pool[MAX_CLIPPED_VERTICES];
    Flat_VertexData **from = tmp_pool;
    Flat_VertexData **to = (Flat_VertexData **)pv;

    int fromCount = 3;
    from[0] = &vpool[poly.vertex0];
    from[1] = &vpool[poly.vertex1];
    from[2] = &vpool[poly.vertex2];

    int cb = 1;
    int plane = 0;


    for (; plane < 6; plane++, cb *= 2) {

	if ((cb & intersections) == 0) continue;

	int toCount = 0;
 	int j = fromCount-1; 
	int i = 0; 
	int flagJ = from[j]->outcodes & cb;

	do {
	    int flagI = from[i]->outcodes & cb;

	    if (flagI ^ flagJ) {
		// Edge crosses plane.
		to[toCount] = &vpool[nrVpool++];
		(*Intersect[plane])(from[i]->cvv, 
				    from[j]->cvv,
				    to[toCount]->cvv);

		/*
		cout << "Plane " << plane << ": " << toCount << " is " 
		     << to[toCount]->cvv << endl;
		*/

		to[toCount]->outcodes = to[toCount]->cvv.computeOutcodes(D);
		toCount++;
	    } 
	    if (!flagI) {
		// Vertex is inside plane.
		to[toCount++] = from[i];

		/*
		cout << "Plane " << plane << ": " << (toCount-1) << " is " 
		     << to[toCount-1]->cvv << endl;
		*/
	    }

	    flagJ = flagI;
	    j = i++;

	} while ( i < fromCount );

 	if (toCount == 0) return false;

	fromCount = toCount;
	Flat_VertexData **tmp = from;
	from = to;
	to = tmp;
    }

    // Transform new vertices to device space.  The others are already
    // done.
    //
    for (int i = 0 ; i < fromCount ; i++ ) {
	Flat_VertexData &v = *from[i];
	pv[i] = from[i];
	v.device.project( *cvvToDevice, v.cvv );

	// cout << "Projected " << i << " is " << v.device << endl;

	if (xmax < v.device.v[X]) {
	    xmax = v.device.v[X];
	} 
	if (xmin > v.device.v[X]) {
	    xmin = v.device.v[X];
	} 
	if (ymax < v.device.v[Y]) {
	    ymax = v.device.v[Y];
	} 
	if (ymin > v.device.v[Y]) {
	    ymin = v.device.v[Y];
	} 
    }

    nrClippedVertices = fromCount;

    return true;
}