///////////////////////////////////////////////////////////////////////////////
/// @file OctreeGeometry.cpp
///
/// @brief Ability to handle geometry in an octree
///
/// @author Assassin
///
/// This file is the intellectual property of Novus Delta, LLC.. Usage of the
/// contents of this file is subject to the Destiny3D Member License which
/// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
///
/// This file is distributed "AS IS" without warranty of any kind.  Novus
/// Delta, LLC. does not guarantee the fitness of the contents of this file
/// for any particular purpose.
///
/// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
///
/// <hr>
///                                 Change History
/// <hr>
///
/// @date Jan 2003
/// @author Assassin
/// @remarks Creation
///
///////////////////////////////////////////////////////////////////////////////

#include "BrushOctree.hpp"

// the following copyright notice is in regards to the intersect_RayTriangle function

// Copyright 2001, softSurfer (www.softsurfer.com)
// This code may be freely used and modified for any purpose
// providing that this copyright notice is included with it.
// SoftSurfer makes no warranty for this code, and cannot be held
// liable for any real or imagined damage resulting from its use.
// Users of this code must verify correctness for their application.

// Assume that classes are already given for the objects:
//    Point and Vector with
//        coordinates {float x, y, z;}
//        operators for:
//            == to test equality
//            != to test inequality
//            (Vector)0 = (0,0,0)         (null vector)
//            Point  = Point ± Vector
//            Vector = Point - Point
//            Vector = Scalar * Vector    (scalar product)
//            Vector = Vector * Vector    (cross product)
//    Line and Ray and Segment with defining points {Point P0, P1;}
//        (a Line is infinite, Rays and Segments start at P0)
//        (a Ray extends beyond P1, but a Segment ends at P1)
//    Plane with a point and a normal {Point V0; Vector n;}
//    Triangle with defining vertices {Point V0, V1, V2;}
//    Polyline and Polygon with n vertices {int n; Point *V;}
//        (a Polygon has V[n]=V[0])
//===================================================================

/*
#define SMALL_NUM  0.00000001 // anything that avoids division overflow
// dot product (3D) which allows vector operations in arguments
#define dot(u,v)   ((u).x * (v).x + (u).y * (v).y + (u).z * (v).z)

// intersect_RayTriangle(): intersect a ray with a 3D triangle
//    Input:  a ray R, and a triangle T
//    Output: *I = intersection point (when it exists)
//    Return: -1 = triangle is degenerate (a segment or point)
//             0 = disjoint (no intersect)
//             1 = intersect in unique point I1
//             2 = are in the same plane
int
intersect_RayTriangle( Ray R, Triangle T, Point* I )
{
    Vector    u, v, n;             // triangle vectors
    Vector    dir, w0, w;          // ray vectors
    float     r, a, b;             // params to calc ray-plane intersect
	
    // get triangle edge vectors and plane normal
    u = T.V1 - T.V0;
    v = T.V2 - T.V0;
    n = u * v;             // cross product
    if (n == (Vector)0)            // triangle is degenerate
        return -1;                 // do not deal with this case
	
    dir = R.P1 - R.P0;             // ray direction vector
    w0 = R.P0 - T.V0;
    a = dot(n,w0);
    b = dot(n,dir);
    if (fabs(b) < SMALL_NUM) {     // ray is parallel to triangle plane
        if (a == 0)                // ray lies in triangle plane
            return 2;
        else return 0;             // ray disjoint from plane
    }
	
    // get intersect point of ray with triangle plane
    r = -a / b;
    if (r < 0.0)                   // ray goes away from triangle
        return 0;                  // => no intersect
    // for a segment, also test if (r > 1.0) => no intersect
	
    *I = R.P0 + r * dir;           // intersect point of ray and plane
	
    // is I inside T?
    float    uu, uv, vv, wu, wv, D;
    uu = dot(u,u);
    uv = dot(u,v);
    vv = dot(v,v);
    w = *I - T.V0;
    wu = dot(w,u);
    wv = dot(w,v);
    D = uv * uv - uu * vv;
	
    // get and test parametric coords
    float s, t;
    s = (uv * wv - vv * wu) / D;
    if (s < 0.0 || s > 1.0)        // I is outside T
        return 0;
    t = (uv * wu - uu * wv) / D;
    if (t < 0.0 || (s + t) > 1.0)  // I is outside T
        return 0;
	
    return 1;                      // I is in T
}
*/

//static
char deBrushOctree::FrontmostOctNodeCorner(const deVec3d & norm)
{
#pragma warning (push)
#pragma warning (disable : 4244)
	char retval = 0;
	// gets corner that will be pointed at if the normal was pointing from the middle of the node
#pragma todo(look at the assembly for this and see if its worth the obfuscation)
	retval +=   (norm.x > 0); // +1 if positive x
	retval += 2*(norm.y > 0); // +2 if positive y
	retval += 4*(norm.z > 0); // +4 if positive z
	// ==0 falls onto the Min side
	return retval;
#pragma warning (pop)
}

//static
void deBrushOctree::OctNodeCorner(const OctNode* node, const char Corner, deVec3d & vec)
{
	//                   true (1)      false (0)
	vec.x = (Corner%2)   ? node->Max.x : node->Min.x;
	vec.y = (Corner%4>=2)? node->Max.y : node->Min.y;
	vec.z = (Corner>=4)  ? node->Max.z : node->Min.z;
}

//static
void deBrushOctree::OctNodeMidPoint(const OctNode* node, const char MidPoint, deVec3d & vec)
{
	OctNodeCenter(node, vec);
	switch (MidPoint)
	{
	case 0: vec.x = node->Min.x; break;
	case 1: vec.x = node->Max.x; break;
	case 2: vec.y = node->Min.y; break;
	case 3: vec.y = node->Max.y; break;
	case 4: vec.z = node->Min.z; break;
	case 5: vec.z = node->Max.z; break;
	default:
		DE_ASSERT(MidPoint >= 0 && MidPoint < 6);
		break;
	}
}

//static
deBoolean deBrushOctree::OctNodeIntersectsPlane(OctNode *node, const dePlane & plane)
{
	if (!node)
		DEBUGRETURN(deFALSE, "OctNodeIntersectsPlane: node was NULL");
	
	char FrontmostCorner;
	deVec3d vec;
	FrontmostCorner = FrontmostOctNodeCorner(plane.Norm);
	// get the point that's "highest" over the plane
	OctNodeCorner(node, FrontmostCorner, vec);
	if (deGeometry::PointOnPlaneFront(vec, plane.Norm, plane.Dist))
	{
		// get the "lowest" point and compare it with the inverse of the plane
		OctNodeCorner(node, (u8)(7-FrontmostCorner), vec);
		if (deGeometry::PointOnPlaneBack(vec, plane.Norm, plane.Dist))
		{
			return deTRUE;
		}
	}
	return deFALSE;
}

deBrushOctree::OctNode* deBrushOctree::GetSmallestNodeForAABB(const deAABB & bbox)
{
#pragma todo (test me)
	OctNode*	node = m_Root;
	OctNode*	prevnode = NULL;
	deVec3d		center;
	BYTE		child;

	while (node)
	{
		prevnode = node;
		child = 0x07;
		OctNodeCenter(node, center);
		if (bbox.Min.x <= center.x && bbox.Max.x > center.x)
			return node;
		else
		{
			if (bbox.Max.x <= center.x)
				child &= 0x06;
		}
		if (bbox.Min.y <= center.y && bbox.Max.y > center.y)
			return node;
		else
		{
			if (bbox.Max.y <= center.y)
				child &= 0x05;
		}
		if (bbox.Min.z <= center.z && bbox.Max.z > center.z)
			return node;
		else
		{
			if (bbox.Max.z <= center.z)
				child &= 0x03;
		}

		node = node->Children[child];
	}
	return prevnode;
}

//    Return:
//             0 = disjoint (no intersect)
//             1 = intersect inside triangle
//             3 = hit U edge
//             5 = hit V edge
//             7 = hit far edge
char PointInTri(const deVec3d & v0, const deVec3d & u, const deVec3d & v, const deVec3d & pt)
{
	// is Res inside T?
	deVec3d		w;
	deDouble	uu, uv, vv, wu, wv, D;
	uu = Vec3d_Dot(u,u);
	uv = Vec3d_Dot(u,v);
	vv = Vec3d_Dot(v,v);
	w = pt;
	w -= v0;
	wu = Vec3d_Dot(w,u);
	wv = Vec3d_Dot(w,v);
	D = uv * uv - uu * vv;

	// get and test parametric coords
	deDouble	s, t;
	s = (uv * wv - vv * wu) / D;
	if (s < 0.0 || s > 1.0)			// Res is outside T
		return 0;
	t = (uv * wu - uu * wv) / D;
	if (t < 0.0 || (s + t) > 1.0)	// Res is outside T
		return 0;
	if (s == 0.0)
		return 3;
	if (t == 0.0)
		return 5;
	if (s+t == 1.0)
		return 7;
	
	return 1;						// Res is in T
}

deBoolean deBrushOctree::PolyPlaneIntersect(const deVec3d & norm, const deDouble & dist, const deIndexedPoly * poly, deVec3d* & ResPair)
{
	// if the planes are parallel, they can't intersect
	if (Vec3d_Compare(norm, poly->Normal) || Vec3d_CompareOpposite(norm, poly->Normal))
		return deFALSE;	

	const int NumVerts = poly->NumVerts;
	bool *Front, *Back;
	int i;

	Front = new bool[NumVerts];
	Back = new bool[NumVerts];
	
	// if all the points of one poly are on one side of the other poly's plane
	// then they can't intersect
	{
		deDouble d;
		int NumFront, NumBack;

		NumFront = NumBack = 0;

		for (i = 0; i < NumVerts; ++i)
		{
			// distance from plane to point
			d = Vec3d_Dot(m_Positions[poly->PosIndices[i]], norm);
			if (d > dist)
			{
				NumFront++;
				Front[i] = true;
				Front[i] = false;
			}
			else if (d < dist)
			{
				NumBack++;
				Back[i] = true;
				Back[i] = false;
			}
			else
			{
				Front[i] = false;
				Back[i] = false;
			}
		}

		// either an edge/point is resting on the plane, or all points are on one side
		if (NumFront == 0 || NumBack == 0)
			goto intersect_false;
	}

	{
		int ResultIndex, j;
		bool LastWasFront=Front[0], LastWasBack=Back[0];
		deDouble Percent;

		ResultIndex = 0;

		for (i = 0; i < NumVerts; ++i)
		{
			j = (i+1)%NumVerts;
			if (Front[j])
			{
				// if this is on front, and last was on back, there was an intersection
				if (LastWasBack)
				{
					deGeometry::PlaneLineIntersect(norm, dist, m_Positions[poly->PosIndices[i]], m_Positions[poly->PosIndices[j]], 
						ResPair[ResultIndex], Percent);
					ResultIndex++;
				}
				LastWasFront = true;
				LastWasBack = false;
			}
			else if (Back[j])
			{
				// if this is on back, and last was on front, there was an intersection
				if (LastWasFront)
				{
					deGeometry::PlaneLineIntersect(norm, dist, m_Positions[poly->PosIndices[i]], m_Positions[poly->PosIndices[j]], 
						ResPair[ResultIndex], Percent);
					ResultIndex++;
				}
				LastWasFront = false;
				LastWasBack = true;
			}
			else
			{
				// if this point lies on the plane, it's an intersection point
				ResPair[ResultIndex] = m_Positions[poly->PosIndices[j]];
				ResultIndex++;
				LastWasFront = false;
				LastWasBack = false;
			}
			// bail out now if we've got both intersections
			if (ResultIndex >= 2)
				break;
		}
	}

	delete[] Front;
	delete[] Back;
	return deTRUE;

intersect_false:
	delete[] Front;
	delete[] Back;
	return deFALSE;
}

//    Return:
//            -2 = are in the same plane
//            -1 = triangle is degenerate (a segment or point)
//             0 = disjoint (no intersect)
//             1 = intersect internally and can split
//             2 = intersect internally and can split
//             3 = intersect along an edge, mutually unsplittable
#define PARALLEL_PLANES			(-2)
#define DEGENERATE_TRIANGLE		(-1)
#define NO_INTERSECTION			(0)
#define INTERSECT_AND_SPLIT		(1)
#define INTERSECT_EDGE_SPLIT	(2)
#define INTERSECT_NO_SPLIT		(3)
deBoolean deBrushOctree::PolyPolyIntersect(const deIndexedPoly * p1, const deIndexedPoly * p2)
{
#ifdef _DEBUG
	{
		// check the integrity of the normals
		deVec3d v0, v1, v2;

#pragma todo (check that these normals are facing the right way)

		deVec3d norm1, norm2;
		norm1 = p1->Normal;
		norm2 = p2->Normal;

		v0 = m_Positions[p1->PosIndices[0]];
		v1 = m_Positions[p1->PosIndices[1]];
		v2 = m_Positions[p1->PosIndices[2]];
		v1 -= v0;
		v2 -= v0;
		Vec3d_Cross(v1,v2,v0);
		Vec3d_Normalize(v0);
		DE_ASSERT(Vec3d_Dot(m_Positions[p1->PosIndices[0]], v0) == p1->Dist);
		DE_ASSERT(Vec3d_Compare(norm1, v0));

		v0 = m_Positions[p2->PosIndices[0]];
		v1 = m_Positions[p2->PosIndices[1]];
		v2 = m_Positions[p2->PosIndices[2]];
		v1 -= v0;
		v2 -= v0;
		Vec3d_Cross(v1,v2,v0);
		Vec3d_Normalize(v0);
		DE_ASSERT(Vec3d_Dot(m_Positions[p2->PosIndices[0]], v0) == p2->Dist);
		DE_ASSERT(Vec3d_Compare(norm2, v0));
	}
#endif

	deVec3d Results[4];
	{
		deVec3d * ResultPair;
		ResultPair = &(Results[0]);
		if (!PolyPlaneIntersect(p1->Normal, p1->Dist, p2, ResultPair))
			return 0;
		ResultPair = &(Results[2]);
		if (!PolyPlaneIntersect(p2->Normal, p2->Dist, p1, ResultPair))
			return 0;
	}
	{
		// this code block finds the intersection area
		// if the lowest high point is higher than the highest low point, intersection = true
		deVec3d dir;
		dir = Results[1];
		dir -= Results[0];
		double x,y,z, minval, maxval, temp;
		x = fabs(dir.x);
		y = fabs(dir.y);
		z = fabs(dir.z);
		if (x > y)
		{
			if (x > z)
			{
				minval = min(Results[0].x, Results[1].x);
				temp = min(Results[2].x, Results[3].x);
				minval = max(minval, temp);
				maxval = max(Results[0].x, Results[1].x);
				temp = max(Results[2].x, Results[3].x);
				maxval = min(maxval, temp);
			}
			else
			{
				minval = min(Results[0].z, Results[1].z);
				temp = min(Results[2].z, Results[3].z);
				minval = max(minval, temp);
				maxval = max(Results[0].z, Results[1].z);
				temp = max(Results[2].z, Results[3].z);
				maxval = min(maxval, temp);
			}
		}
		else
		{
			if (y > z)
			{
				minval = min(Results[0].y, Results[1].y);
				temp = min(Results[2].y, Results[3].y);
				minval = max(minval, temp);
				maxval = max(Results[0].y, Results[1].y);
				temp = max(Results[2].y, Results[3].y);
				maxval = min(maxval, temp);
			}
			else
			{
				minval = min(Results[0].z, Results[1].z);
				temp = min(Results[2].z, Results[3].z);
				minval = max(minval, temp);
				maxval = max(Results[0].z, Results[1].z);
				temp = max(Results[2].z, Results[3].z);
				maxval = min(maxval, temp);
			}
		}
		if (minval <= maxval)
			return deTRUE;
		else
			return deFALSE;
	}
}

struct index_triple { u16 pos, norm, mat;};
deBoolean deBrushOctree::SplitPoly(const deIndexedPoly * input, deIndexedPoly* & out1, deIndexedPoly* & out2)
// fill values in for m_SplittingPlane before calling this
{
	if (input->PosIndices == NULL || input->NumVerts < 3)
		DEBUGRETURN(deFALSE, "SplitPoly: invalid polygon");
	
	long i, j, NumVerts;
	u16 VertIndex;
	deBoolean LastWasFront;
	deDouble Percent;
	deTArray<index_triple> fronts, backs;
//	deTArray<long> frontpos, backpos;
//	deTArray<long> frontnorm, backnorm;
//	deTArray<long> frontmat, backmat;
	
	LastWasFront = deGeometry::PointOnPlaneFront(m_Positions[input->PosIndices[0]], m_SplittingPlane.Norm, m_SplittingPlane.Dist);
	if (LastWasFront)
	{
		fronts.IncrementSizeQuick(deFALSE, j);
		fronts[j].pos = input->PosIndices[0];
		fronts[j].norm= input->NormIndices[0];
		fronts[j].mat = input->MatIndices[0];
	}
	else
	{
		backs.IncrementSizeQuick(deFALSE, j);
		backs[j].pos = input->PosIndices[0];
		backs[j].norm= input->NormIndices[0];
		backs[j].mat = input->MatIndices[0];
	}
	// loop through all the verts of input
	NumVerts = input->NumVerts;
	for (i = 0; i < NumVerts; ++i)
	{
		j = (i+1)%NumVerts;
		// if the current point is on the same side as the previous, just keep going
		// if the current point is on the other side, split the edge and add the split vertex to both out1 and out2
		if (deGeometry::PointOnPlaneFront(m_Positions[input->PosIndices[j]], m_SplittingPlane.Norm, m_SplittingPlane.Dist))
		{
			if (LastWasFront)
			{
				fronts.IncrementSizeQuick(deFALSE, j);
				fronts[j].pos = input->PosIndices[i];
				fronts[j].norm= input->NormIndices[i];
				fronts[j].mat = input->MatIndices[i];
			}
			else
			{
				LastWasFront = deTRUE;
				goto split_edge;
			}
		}
		else
		{
			if (!LastWasFront)
			{
				backs.IncrementSizeQuick(deFALSE, j);
				backs[j].pos = input->PosIndices[i];
				backs[j].norm= input->NormIndices[i];
				backs[j].mat = input->MatIndices[i];
			}
			else
			{
				LastWasFront = deFALSE;
				goto split_edge;
			}
		}
		continue;
	split_edge:
		// SplitEdge*** uses a hashtable to index the same vertex when splitting things
		// the splitting plane is cached in m_SplittingNorm and m_SplittingDist
		{
			HashEdge Edge(input->PosIndices[i], input->PosIndices[j]);
			long k;

			backs.IncrementSizeQuick(deFALSE, j);
			fronts.IncrementSizeQuick(deFALSE, k);

			VertIndex = SplitEdgePos(Edge, Percent);
			backs[j].pos = VertIndex;
			fronts[k].pos = VertIndex;
			
			VertIndex = SplitEdgeNorm(Edge, Percent);
			backs[j].norm = VertIndex;
			fronts[k].norm = VertIndex;
			
			VertIndex = SplitEdgeMat(Edge, Percent);
			backs[j].mat = VertIndex;
			fronts[k].mat = VertIndex;
		}
	}

	// if one of the arrays has no points, the poly wasn't split
	if (fronts.Length() == 0 || backs.Length() == 0)
	{
		out1 = out2 = NULL;
		return deFALSE;
	}

	{
		if (!AddPolyGetRef(out1) || out1 == NULL)
			return deFALSE;
		if (!AddPolyGetRef(out2) || out2 == NULL)
		{
			RemovePoly(out1);
			return deFALSE;
		}
		
		out1->TextureIndex = input->TextureIndex;
		out2->TextureIndex = input->TextureIndex;
		out1->Normal = input->Normal;
		out2->Normal = input->Normal;
		out1->Dist = input->Dist;
		out2->Dist = input->Dist;

		if (!RemovePoly(input))
		{
			RemovePoly(out1);
			RemovePoly(out2);
			return deFALSE;
		}
	}

	
	// give the output polygons the right number of vertices
	out1->Resize(fronts.Length());
	out2->Resize(backs.Length());

	// put all the indices into the polygons
	for (i = 0; i < out1->NumVerts; ++i)
	{
		out1->PosIndices[i] = fronts[i].pos;
		out1->NormIndices[i] = fronts[i].norm;
		out1->MatIndices[i] = fronts[i].mat;
	}
	
	for (i = 0; i < out2->NumVerts; ++i)
	{
		out2->PosIndices[i] = backs[i].pos;
		out2->NormIndices[i] = backs[i].norm;
		out2->MatIndices[i] = backs[i].mat;
	}
	
	return deTRUE;
}

u16 deBrushOctree::SplitEdgePos(const HashEdge & Edge, deDouble & Percent)
{
	{
		// look for whether this vertex has already been generated
		u16* pRetVal;
		pRetVal = m_SplitPosHash.FindElement(Edge);
		if (pRetVal)
			return *pRetVal;
	}
	// if this vertex hasn't already been calculated, figure it out
	{
		deVec3d Result;
		u16 Index16;
		// intersect the plane
		deGeometry::PlaneLineIntersect(m_SplittingPlane.Norm, m_SplittingPlane.Dist, m_Positions[Edge.index1()], m_Positions[Edge.index2()], Result, Percent);
		{
			long index;
			m_Positions.IncrementSizeQuick(deFALSE, index);
			// make sure no overflow (debug only)
			DE_ASSERT(index < 65536);
			Index16 = (u16)(index);
		}
		// store the new vertex
		m_Positions[Index16] = Result;
		// and remember the index to it
		m_SplitPosHash.AddElement(Index16,Edge);
		return Index16;
	}
}

#pragma todo(figure out if this is gonna cause problems with shared normals that arent on the same edge)
// might be necessary to enforce a rule about faces can only share a normal if the normal matches a shared position
// or else the hash table might return an invalid result
/*        _____
        /|     |  front and back planes have same normal
       / |     |  plane slicing through their shared edges differently
      /  |_____|  hash table would look up same value for both and would be wrong
_____/ _-|_____|
_____|-  /
     |  /
     | /
_____|/
*/
u16 deBrushOctree::SplitEdgeNorm(const HashEdge & Edge, const deDouble & Percent)
{
	// a face can use the same normal all across its face
	u16 index1 = Edge.index1();
	u16 index2 = Edge.index2();
	if (index1 == index2)
		return index1;
	{
		// look for whether this vertex has already been generated
		u16* pRetVal;
		pRetVal = m_SplitNormHash.FindElement(Edge);
		if (pRetVal)
			return *pRetVal;
	}
	// if this vertex hasn't already been calculated, figure it out
	{
		deVec3d Norm1, Norm2;
		u16 Index16;
		Norm1 = m_Normals[index1];
		Norm1 *= Percent;
		Norm2 = m_Normals[index2];
		Norm2 *= (1.0 - Percent);
		Norm1 += Norm2;
		{
			long index;
			m_Normals.IncrementSizeQuick(deFALSE, index);
			// make sure no overflow (debug only)
			DE_ASSERT(index < 65536);
			Index16 = (u16)(index);
		}
		// store the new normal
		m_Normals[Index16] = Norm1;
		// and remember the index to it
		m_SplitNormHash.AddElement(Index16,Edge);
		return Index16;
	}
}

u16 deBrushOctree::SplitEdgeMat(const HashEdge & Edge, const deDouble & Percent)
{
	// a face can use the same material all across its face
	u16 index1 = Edge.index1();
	u16 index2 = Edge.index2();
	if (index1 == index2)
		return index1;
	{
		// look for whether this vertex has already been generated
		u16* pRetVal;
		pRetVal = m_SplitNormHash.FindElement(Edge);
		if (pRetVal)
			return *pRetVal;
	}
	// if this vertex hasn't already been calculated, figure it out
	{
		u16 Index16;
		{
			long index;
			m_Normals.IncrementSizeQuick(deFALSE, index);
			// make sure no overflow (debug only)
			DE_ASSERT(index < 65536);
			Index16 = (u16)(index);
		}
		// and remember the index to it
		m_SplitNormHash.AddElement(Index16,Edge);
		// store the new data
		{
			deARGB newcolor;
			deDouble InterpolatedValue;
			InterpolatedValue = ((m_VertMats[index1].Diffuse>>24)&0xff)*Percent + ((m_VertMats[index1].Diffuse>>24)&0xff)*(1.0-Percent);
			newcolor = int (InterpolatedValue + 0.5) << 24;
			InterpolatedValue = ((m_VertMats[index1].Diffuse>>16)&0xff)*Percent + ((m_VertMats[index1].Diffuse>>16)&0xff)*(1.0-Percent);
			newcolor = int (InterpolatedValue + 0.5) << 16;
			InterpolatedValue = ((m_VertMats[index1].Diffuse>> 8)&0xff)*Percent + ((m_VertMats[index1].Diffuse>> 8)&0xff)*(1.0-Percent);
			newcolor = int (InterpolatedValue + 0.5) << 8;
			InterpolatedValue = ((m_VertMats[index1].Diffuse    )&0xff)*Percent + ((m_VertMats[index1].Diffuse    )&0xff)*(1.0-Percent);
			newcolor = int (InterpolatedValue + 0.5);
			m_VertMats[Index16].Diffuse = newcolor;
		}
		{
			m_VertMats[Index16].UV = m_VertMats[index1].UV;
			m_VertMats[Index16].UV *= (deFloat)Percent;
			deTexCoord newcoord;
			newcoord = m_VertMats[index2].UV;
			newcoord *= (1.0f-(deFloat)Percent);
			m_VertMats[Index16].UV += newcoord;
		}
		return Index16;
	}
}

