Renegade/Code/ww3d2/intersec.inl

/*
**	Command & Conquer Renegade(tm)
**	Copyright 2025 Electronic Arts Inc.
**
**	This program is free software: you can redistribute it and/or modify
**	it under the terms of the GNU General Public License as published by
**	the Free Software Foundation, either version 3 of the License, or
**	(at your option) any later version.
**
**	This program is distributed in the hope that it will be useful,
**	but WITHOUT ANY WARRANTY; without even the implied warranty of
**	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
**	GNU General Public License for more details.
**
**	You should have received a copy of the GNU General Public License
**	along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#if defined(_MSC_VER)
#pragma once
#endif

#ifndef INTERSEC_INL
#define INTERSEC_INL

#include "camera.h"


/// debug code that will be tossed

#ifdef DEBUG_NORMALS

#include "d:/g/app/main/debug_o.h"

inline bool Verify_Normal(Vector3 &Normal, Vector3 &loc1, Vector3 &loc2, Vector3 &loc3)
{

	double d1 = Vector3::Dot_Product(Normal, loc1);
	double d2 = Vector3::Dot_Product(Normal, loc2);
	double d3 = Vector3::Dot_Product(Normal, loc3);

	double e1 = d1 - d2;
	double e2 = d2 - d3;
	double e3 = d3 - d1;
	
	if((fabs(e1) > 0.001) || (fabs(e2) > 0.001) || (fabs(e3) > 0.001)) {
		Debug.Print("----------\n");
		Debug.Print("dots", Vector3(d1,d2,d3));
		Debug.Print("err", Vector3(e1,e2,e3));
		return false;
	}
	return true;
}

inline void Verify_Normal2(Vector3 &Normal, Vector3 &loc1, Vector3 &loc2, Vector3 &loc3)
{
	Vector3 v1 = loc2 - loc1;
	Vector3 v2 = loc3 - loc1;
	Vector3 normal = Vector3::Cross_Product(v1,v2);
	normal.Normalize();
	if(!Verify_Normal(Normal, loc1,loc2,loc3)) {
		Vector3 diff = Normal - normal;
		if(Verify_Normal(normal, loc1,loc2,loc3)) {
			Debug.Print("calculated worked.\n");

		}
	}
//	Normal = normal;
}

#endif

//// end of debug code to toss

/*
**	Determine the ray that corresponds to the specified screen coordinates with respect 
** to the camera location, direction and projection information.
*/

inline void IntersectionClass::Get_Screen_Ray(float screen_x, float screen_y, const LayerClass &Layer)
{

	// copy screen coords to member data
	ScreenX = screen_x;
	ScreenY = screen_y;

	// extract needed pointers from the world
	CameraClass *camera = Layer.Camera;

	// determine the ray corresponding to the camera and distance to projection plane
	Matrix3D camera_matrix = camera->Get_Transform();
	Vector3 camera_location  = camera->Get_Position();

	// the projected ray has the same origin as the camera
	*RayLocation = camera_location; 

// these 6 lines worked for SR 1.1
// build the projected screen vector
// float x_offset = width / (float)Scene->width; // render width in pixels divided by display width in pixels = ratio of displayed area
// float y_offset = height / (float)Scene->height;
//	float zmod = Scene->perspective;
//	float xmod = ((ScreenX / x_offset) * width  - xmid - Scene->xstart) * zmod  * 16384.0f/ (Scene->axratio * 128.0f);
//	float ymod = ((ScreenY / y_offset) * height - ymid - Scene->ystart) * zmod  * 16384.0f/ (Scene->ayratio * 128.0f);

	// determine the location of the screen coordinate in camera-model space
	const ViewportClass &viewport = camera->Get_Viewport();

//	float aspect = camera->Get_Aspect_Ratio();

	Vector2 min,max;
	camera->Get_View_Plane(min,max);
	float xscale = (max.X - min.X);
	float yscale = (max.Y - min.Y);

	float zmod = -1.0; // Scene->vpd; // Note: view plane distance is now always 1.0 from the camera
	float xmod = (-ScreenX + 0.5 + viewport.Min.X) * zmod * xscale;// / aspect;
	float ymod = (ScreenY - 0.5 - viewport.Min.Y) * zmod * yscale;// * aspect;

//	float xmod = (ScreenX - 0.5 - viewport.Min.X) * zmod / Scene->axratio;
//	float ymod = (ScreenY - 0.5 - viewport.Min.Y) * zmod / Scene->ayratio;

// sr1.2
//	float xmod = (ScreenX - 0.5 - Scene->xstart) * zmod / Scene->axratio;
//	float ymod = (ScreenY - 0.5 - Scene->ystart) * zmod / Scene->ayratio;
// sr1.1
//	float xmod = x_offset * zmod; //projection_width;
//	float ymod = y_offset * zmod; //projection_height;

	// transform the screen coordinates by the camera's matrix into world coordinates.
	float x = zmod * camera_matrix[0][2] + xmod * camera_matrix[0][0] + ymod * camera_matrix[0][1];
	float y = zmod * camera_matrix[1][2] + xmod * camera_matrix[1][0] + ymod * camera_matrix[1][1];
	float z = zmod * camera_matrix[2][2] + xmod * camera_matrix[2][0] + ymod * camera_matrix[2][1];

	RayDirection->Set(x,y,z);
	RayDirection->Normalize();

	// set the maximum intersection distance to the back clipping plane
	MaxDistance =  camera->Get_Depth();
	//Max_Distance =  Scene->zstop * Scene->depth;

}

/*
**	This is the Point_In_Polygon_Z low level function, optimized for use by _Intersect_Triangles_Z.
**	If it is inside, it will adjust the Z value of the point to be on the triangle plane.
*/
inline bool IntersectionClass::_Point_In_Polygon_Z(
	Vector3 &Point, 
	Vector3 &Corner1,
	Vector3 &Corner2,
	Vector3 &Corner3
) 
{
// these defines could be variables if support for other axis were neccessary
#define AXIS_1 0
#define AXIS_2 1
#define AXIS_3 2

	double u0 = Point[AXIS_1] - Corner1[AXIS_1]; 
	double v0 = Point[AXIS_2] - Corner1[AXIS_2];

	// determine the 2d vectors on the dominant plane from the first vertex to the other two
	double u1 = Corner2[AXIS_1] - Corner1[AXIS_1]; 
	double v1 = Corner2[AXIS_2] - Corner1[AXIS_2];
	double u2 = Corner3[AXIS_1] - Corner1[AXIS_1]; 
	double v2 = Corner3[AXIS_2] - Corner1[AXIS_2];

	double alpha, beta;
	bool intersect = false; 

	// calculate alpha and beta as normalized (0..1) percentages across the 2d projected triangle
	// and do bounds checking (sum <= 1)  to determine whether or not the triangle intersection occurs.

	if (u1 == 0.0f)    {
	  beta = u0 / u2;			// beta is the percentage down the edge Corner1->Corner3
	  if ((beta >= 0.0f) && (beta <= 1.0f)) {		// make sure it's within the edge segment
			alpha = (v0 - beta * v2) / v1;	 // alpha is the percentage down the edge Corner1->Corner2

			// if alpha is valid & the sum of alpha & beta is <= 1 then it's within the triangle
			// note:       0.00001 added after testing an intersection of a square in the middle indicated
			// an error of 0.0000001350, apparently due to roundoff.
			intersect = ((alpha >= 0.0) && ((alpha + beta) <= 1.0)); 
	  }
	} else {
	  beta = (v0 * u1 - u0 * v1) / (v2 * u1 - u2 * v1);
	  if ((beta >= 0.0) && (beta <= 1.0)) {
			alpha = (u0 - beta * u2) / u1;
			intersect = ((alpha >= 0.0) && ((alpha + beta) <= 1.0));
	  }
	}

	// if it is inside, adjust the Z value to sit upon the triangle plane.
	if(intersect) {
		float u3 = Corner2[AXIS_3] - Corner1[AXIS_3];
		float v3 = Corner3[AXIS_3] - Corner1[AXIS_3];

		Point[AXIS_3] = u3 * alpha + v3 * beta + Corner1[AXIS_3];
	}

	return intersect;
}

/*
**	Another way to access the Point_In_Polygon function
**
*/
inline bool IntersectionClass::_Point_In_Polygon_Z(
	Vector3 &Point, 
	Vector3 Corners[3]
) 
{
	return _Point_In_Polygon_Z(Point, Corners[0], Corners[1], Corners[2]);
}

/*
**	This is the general purpose Point_In_Polygon low level function. It can be called directly if you know
**	the dominant projection axes, such as in the case of 2d intersecion with heightfields.
*/
inline bool IntersectionClass::_Point_In_Polygon(
	Vector3 &Point, 
	Vector3 &loc1, 
	Vector3 &loc2, 
	Vector3 &loc3, 
	int axis_1, 
	int axis_2,
	float &Alpha,
	float &Beta) 
{

	double u0 = Point[axis_1] - loc1[axis_1]; 
	double v0 = Point[axis_2] - loc1[axis_2];

	// determine the 2d vectors on the dominant plane from the first vertex to the other two
	double u1 = loc2[axis_1] - loc1[axis_1]; 
	double v1 = loc2[axis_2] - loc1[axis_2];
	double u2 = loc3[axis_1] - loc1[axis_1]; 
	double v2 = loc3[axis_2] - loc1[axis_2];

	double alpha, beta;
	bool intersect = false; 

	// calculate alpha and beta as normalized (0..1) percentages across the 2d projected triangle
	// and do bounds checking (sum <= 1)  to determine whether or not the triangle intersection occurs.

#ifdef DEBUG_NORMALS
	bool debugmode = false;
	if(FinalResult->Alpha == 777) {
		debugmode = true;
	}
#endif

	if (u1 == 0.0f)    {
	  Beta = beta = u0 / u2;			// beta is the percentage down the edge loc1->loc3
	  if ((beta >= 0.0f) && (beta <= 1.0f)) {		// make sure it's within the edge segment
			Alpha = alpha = (v0 - beta * v2) / v1;	 // alpha is the percentage down the edge loc1->loc2

			// if alpha is valid & the sum of alpha & beta is <= 1 then it's within the triangle
			// note:       0.00001 added after testing an intersection of a square in the middle indicated
			// an error of 0.0000001350, apparently due to roundoff.
			intersect = ((alpha >= 0.0) && ((alpha + beta) <= 1.0)); 
	  }
	} else {
	  Beta = beta = (v0 * u1 - u0 * v1) / (v2 * u1 - u2 * v1);
	  if ((beta >= 0.0) && (beta <= 1.0)) {
			Alpha = alpha = (u0 - beta * u2) / u1;
			intersect = ((alpha >= 0.0) && ((alpha + beta) <= 1.0));
	  }
	}

#ifdef DEBUG_NORMALS
	if(debugmode) {
		Debug.Print("Intersect", intersect);
		Debug.Print("Normal ", Normal);		
		Debug.Print("Point 1", loc1);		
		Debug.Print("Point 2", loc2);		
		Debug.Print("Point 3", loc3);		
		Debug.Print("Inter  ", FinalResult->Intersection);
		Debug.Print("a/b", (float) alpha, (float) beta);
		Debug.Print("sum", (float) alpha + (float) beta);
		Debug.Print("diff", (float) (alpha - beta));
		float d1 = Vector3::Dot_Product(Normal, loc1);
		float d2 = Vector3::Dot_Product(Normal, loc2);
		float d3 = Vector3::Dot_Product(Normal, loc3);

		float e1 = d1 - d2;
		float e2 = d2 - d3;
		float e3 = d3 - d1;

		Debug.Print("dots", Vector3(d1,d2,d3));
		Debug.Print("err", Vector3(e1,e2,e3));
	}
#endif


	return intersect;
}

/*
**	This version calls the base form using member data from the FinalResult struct for 
**	some of it's arguments.
*/
inline bool IntersectionClass::_Point_In_Polygon(
	IntersectionResultClass *FinalResult, 
	Vector3 &loc1, 
	Vector3 &loc2, 
	Vector3 &loc3, 
	int axis_1, 
	int axis_2) 
{
	return (FinalResult->Intersects = _Point_In_Polygon(	FinalResult->Intersection, loc1, loc2, loc3, 
								axis_1, axis_2, FinalResult->Alpha, FinalResult->Beta));
}

/*
**	This version determines the dominant plane of the 3d triangle to be point-in-poly tested
**	and then calls the next form of _Point_In_Polygon
*/
inline bool IntersectionClass::_Point_In_Polygon(IntersectionResultClass *FinalResult, Vector3 &Normal, Vector3 &loc1, Vector3 &loc2, Vector3 &loc3) {

	// first, find the dominant axis and use the plane perpendicular to it as defined by axis_1, axis_2
	int axis_1, axis_2;
	_Find_Polygon_Dominant_Plane(Normal, axis_1, axis_2);

	return _Point_In_Polygon(FinalResult, loc1, loc2, loc3, axis_1, axis_2);
}


/*
**	Determine the Z distance to the specified polygon.
*/
inline float IntersectionClass::Plane_Z_Distance(Vector3 &PlaneNormal, Vector3 &PlanePoint) 
{
	// do a parallel check
	float divisor = (PlaneNormal[0] *(*RayDirection)[0] + PlaneNormal[1] *(*RayDirection)[1] + PlaneNormal[2] * (*RayDirection)[2]);
	if(divisor == 0) return false; // parallel

	// determine distance to plane
	double d = - (PlanePoint[0] * PlaneNormal[0] + PlanePoint[1] * PlaneNormal[1] + PlanePoint[2] * PlaneNormal[2]);

	float value = - (d + PlaneNormal[0] * (*RayLocation)[0] + PlaneNormal[1] *  (*RayLocation)[1] + PlaneNormal[2] * (*RayLocation)[2]) / divisor;

	return value;
}

/*
**	This function will find the z elevation for the passed Vector3 whose x/y components
**	are defined, using the specified vertex & surface normal to determine the correct value
*/
inline float IntersectionClass::_Get_Z_Elevation(
	Vector3 &Point, 
	Vector3 &PlanePoint, 
	Vector3 &PlaneNormal)
{
	
	// do a parallel check
	if(PlaneNormal[2] == 0) return false;

	// determine distance to plane
	double d = - (PlanePoint[0] * PlaneNormal[0] + PlanePoint[1] * PlaneNormal[1] + PlanePoint[2] * PlaneNormal[2]);

	float value = - (d + PlaneNormal[0] * Point[0] + PlaneNormal[1] *  Point[1] ) / PlaneNormal[2];

	return value;
}

/*
**	Optimized intersection test that only considers the x/y component of the intersection object
**	and will determine the intersection location down the Z axis.
*/
inline bool IntersectionClass::Intersect_Polygon_Z(IntersectionResultClass *Result, Vector3 &PolygonNormal, Vector3 &v1, Vector3 &v2, Vector3 &v3)
{

	Result->Range = Plane_Z_Distance(PolygonNormal, v1);
	(Result->Intersection)[0] = (*RayLocation)[0];
	(Result->Intersection)[1] = (*RayLocation)[1];
	(Result->Intersection)[2] = (*RayLocation)[2] - Result->Range;
	return _Point_In_Polygon(Result, PolygonNormal, v1, v2, v3);
}


/*
**	Scale the normalized direction ray to the distance of intersection
*/
void IntersectionClass::Calculate_Intersection(IntersectionResultClass *Result)
{
	(Result->Intersection)[0] = (*RayLocation)[0] + (*RayDirection)[0] * Result->Range;
	(Result->Intersection)[1] = (*RayLocation)[1] + (*RayDirection)[1] * Result->Range;
	(Result->Intersection)[2] = (*RayLocation)[2] + (*RayDirection)[2] * Result->Range;
}

/*
**	Plane intersection test that assumes a normalized RayDirection. Only determines if 
**	plane is parallel and if not, the range to it (which may be negative or beyond MaxRange).
**	It doesn't determine point of intersection either.
*/
inline bool IntersectionClass::Intersect_Plane_Quick(IntersectionResultClass *Result, Vector3 &PlaneNormal, Vector3 &PlanePoint) 
{
	// do a parallel check
	float divisor = (PlaneNormal[0] *(*RayDirection)[0] + PlaneNormal[1] *(*RayDirection)[1] + PlaneNormal[2] * (*RayDirection)[2]);
	if(divisor == 0) return false; // parallel

	// determine distance to plane
	float d = - (PlanePoint[0] * PlaneNormal[0] + PlanePoint[1] * PlaneNormal[1] + PlanePoint[2] * PlaneNormal[2]);
	Result->Range = - (d + PlaneNormal[0] * (*RayLocation)[0] + PlaneNormal[1] *  (*RayLocation)[1] + PlaneNormal[2] *  (*RayLocation)[2])  / divisor;

	return true;
}

/*
**	Determine if the specified ray will intersect the plane; returns false for planes 
**	parallel and behind ray origin.
**	Sets Range to the distance from the ray location to the intersection. 
**	Note: Range is undefined if an intersection didn't occur.
*/
inline bool IntersectionClass::Intersect_Plane(IntersectionResultClass *Result, Vector3 &PlaneNormal, Vector3 &PlanePoint) {
								 
	// normalize the ray direction
	RayDirection->Normalize();

	// call the quick test routine
	if(!Intersect_Plane_Quick(Result, PlaneNormal, PlanePoint)) return false;

	// check to make sure it's not behind the ray's origin
	if(Result->Range <= 0) return false; 

	// check to make sure it's not beyond max distance
	if(Result->Range > MaxDistance) return false;

	// determine point of intersection
	Calculate_Intersection(Result);

	return true;
}



/*
**	Return the index of the largest normal component 0..2
**	used by Find_Triangle_Dominant_Plane()
*/
inline int IntersectionClass::_Largest_Normal_Index(Vector3 &v)
{
	float x = fabsf(v[0]);
	float y = fabsf(v[1]);
	float z = fabsf(v[2]);
	if(x > y) {
		if(x > z) {
			return 0; // x > y && x > z --> x is the max
		}
		return 2; // x > y && !(x > z) --> z is the max
	}
	if(y > z) 
		return 1; //  x <= y && y > z --> y is the max
	return 2; // y > x &&  y > z --> z is the max
}

/*
** Use the Polygon's currently defined surface normal to determine it's dominant axis.
** Axis_1 and Axis_2 are set to the indices of the two axis that define the dominant plane.
*/
inline void IntersectionClass::_Find_Polygon_Dominant_Plane(Vector3 &Normal, int &Axis_1, int &Axis_2)
{
	switch (_Largest_Normal_Index(Normal)) 
	{
	case 0: 
		// Dominant is the X axis
		Axis_1 = 2;
		Axis_2 = 1;
		break;
	case 1: 
		// Dominant is the Y axis
		Axis_1 = 2;
		Axis_2 = 0;
		break;
	case 2: 
		// Dominant is the Z axis
		Axis_1 = 0;
		Axis_2 = 1;
		break;
	}
}

/*
**	Returns true if ray intersects polygon.
**	Changes passed Intersection argument to location of intersection if it occurs, 
**	and sets Range to the distance from the ray location to the intersection.
**	If Interpolated_Normal is specified it will interpolate the surface normal based 
**	on the vertex normals.
*/
inline bool IntersectionClass::Intersect_Polygon(IntersectionResultClass *Result, Vector3 &PolygonNormal, Vector3 &v1, Vector3 &v2, Vector3 &v3)
{
	// first check to see if it hits the plane; determine plane normal and find point on plane (from a vertex)
	
#ifdef DEBUG_NORMALS
	Verify_Normal2(PolygonNormal, v1,v2,v3);
#endif

	if(Intersect_Plane(Result, PolygonNormal, v1)) {
		// then check to see if it it actually intersects the polygon. 
		return _Point_In_Polygon(Result, PolygonNormal, v1, v2, v3);
	}
	// doesn't even hit the plane, return false.
	return false;
}

/*
**	This version will calc the normal for the polygon before calling
**	a lower form of Intersect_Polygon
*/
inline bool IntersectionClass::Intersect_Polygon(IntersectionResultClass *Result, Vector3 &v1, Vector3 &v2, Vector3 &v3)
{
	Vector3 vec1 = v2 - v1;
	Vector3 vec2 = v3 - v1;
	Vector3 normal = Vector3::Cross_Product(vec1, vec2);

	return Intersect_Polygon(Result, normal, v1,v2,v3);
}


// called after Interpolate_Intersection_Normal.
// transform the intersection and the normal from model coords into world coords
inline void IntersectionClass::Transform_Model_To_World_Coords(IntersectionResultClass *FinalResult) {
	FinalResult->Intersection = FinalResult->ModelMatrix * FinalResult->Intersection + FinalResult->ModelLocation;
	if(IntersectionNormal != 0) {
		Vector3 normal(*IntersectionNormal);
		*IntersectionNormal = FinalResult->ModelMatrix * normal; 
	}
}



bool IntersectionClass::Intersect_Screen_Object(	IntersectionResultClass *Final_Result,
											Vector4 &Area, 
											RenderObjClass *obj)
{
	if(Final_Result->Intersects =  ((ScreenX >= Area[0]) && (ScreenX <= Area[2]) && (ScreenY >= Area[1]) && (ScreenY <= Area[3]))) {
		Final_Result->IntersectionType = IntersectionResultClass::GENERIC;
		Final_Result->IntersectedRenderObject = obj;
		Final_Result->Range = 0;
		return true;
	}
	return false;
}


/*
**	Determines the point of intersection, if any between the line segments AB and CD. 
**	If an intersection occurs, then the UV values are interpolated along AB.
**	Disregards the Z value and considers only the X/Y data except for determining
**	the Z value of the intersection.
**	This function could be easily modified to support other axes.
* /
void IntersectionClass::_Intersect_Lines_Z(	
	Vector3 &A, 
	Vector3 &B,
	Vector2 &UVStart,
	Vector2 &UVEnd,
	Vector3 &C, 
	Vector3 &D,
	Vector3 ClippedPoints[6], 
	Vector2 ClippedUV[6],
	int &DestIndex)
{
	/*
		Let A,B,C,D be 2-space position vectors.  Then the directed line segments AB & CD are given by:

				AB=A+r(B-A), r in [0,1]
				CD=C+s(D-C), s in [0,1]
		If AB & CD intersect, then

				A+r(B-A)=C+s(D-C), or

				Ax+r(Bx-Ax)=Cx+s(Dx-Cx)
				Ay+r(By-Ay)=Cy+s(Dy-Cy)  for some r,s in [0,1]
		Solving the above for r and s yields

					(Ay-Cy)(Dx-Cx)-(Ax-Cx)(Dy-Cy)
				r = -----------------------------  (eqn 1)
					(Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)
					(Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay)
				s = -----------------------------  (eqn 2)
					(Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)
		Let P be the position vector of the intersection point, then

				P=A+r(B-A) or

				Px=Ax+r(Bx-Ax)
				Py=Ay+r(By-Ay)
		By examining the values of r & s, you can also determine some other limiting conditions:

				If 0<=r<=1 & 0<=s<=1, intersection exists
					r<0 or r>1 or s<0 or s>1 line segments do not intersect
		If the denominator in eqn 1 is zero, AB & CD are parallel

		If the numerator in eqn 1 is also zero, AB & CD are coincident

		If the intersection point of the 2 lines are needed (lines in this context mean infinite lines) regardless whether the two line segments intersect, then

		If r>1, P is located on extension of AB
		If r<0, P is located on extension of BA
		If s>1, P is located on extension of CD
		If s<0, P is located on extension of DC
	* /

	// the numerator is required for all execution routes
	float numerator =   (A[AXIS_2] - C[AXIS_2]) * (D[AXIS_1] - C[AXIS_1]) - (A[AXIS_1] - C[AXIS_1]) * (D[AXIS_2] - C[AXIS_2]);

	// if the denominator is zero, then the segments are parallel.
	float denominator = (B[AXIS_1] - A[AXIS_1]) * (D[AXIS_2] - C[AXIS_2]) - (B[AXIS_2] - A[AXIS_2]) * (D[AXIS_1] - C[AXIS_1]);

	// r & s are percentages through the line segment.
	float r, s;

	// check to see if they are parallel
	if(denominator == 0) {

		// check to see if they are coincident
		// a numerator of zero with a denominator of zero indicates coincident lines.
		if (numerator != 0) {

			// parallel, not coincident lines (and segments) do not intersect.
			return;
		}

		// perform special case for parallel segments

		// determine relative position 0..1 of C and D on one of the 1d vectors of A-B
		float len = B[AXIS_1] - A[AXIS_1];
		float cpos,dpos;

		// if the length of the edge on the first axis is zero, use the other axis instead.
		if(len) {
			len = 1.0 / len;
			cpos = (C[AXIS_1] - A[AXIS_1]) * len;
			dpos = (D[AXIS_1] - A[AXIS_1]) * len;
		} else {
			len = B[AXIS_2] - A[AXIS_2];

			// degenerate triangle test
			if(len == 0)
				return;
			
			len = 1.0 / len;
			cpos = (C[AXIS_2] - A[AXIS_2]) * len;
			dpos = (D[AXIS_2] - A[AXIS_2]) * len;
		}

		// check to see if there's any overlap
		// one of the two pos values must be 0>pos>1 or there is no intersection.
		// this test will ensure that cpos & dpos will not both be outside the same end of the segment.
		if(((cpos < 0) && (dpos < 0)) || ((cpos > 1) && (dpos > 1))) 
			return;

		if(cpos < 0) {
			// C is outside, therefore D is inside or on other side.
			// use the original vertex.
			ClippedPoints[DestIndex] = A;
			ClippedUV[DestIndex++] = UVStart;
		} else if (cpos > 1) {
			// C is outside far side, therefore D is inside or on other side.
			// use the far vertex.
			ClippedPoints[DestIndex] = B;
			ClippedUV[DestIndex++] = UVEnd;
		} else {
			// C is inside.
			// Use C as the vertex, and interpolate the UV coords.
			ClippedPoints[DestIndex] = C;
			ClippedUV[DestIndex++] = (UVEnd - UVStart) * cpos + UVStart;
		}

		if(dpos < 0) {
			// D is outside near vertex, therefore C is inside or outside far vertex
			// use near vertex
			ClippedPoints[DestIndex] = A;
			ClippedUV[DestIndex++] = UVStart;
		} else if (dpos > 1) {
			// D is outside far vertex, therefore C is inside or outside the near vertex.
			// use the far vertex.
			ClippedPoints[DestIndex] = B;
			ClippedUV[DestIndex++] = UVEnd;
		} else {
			// D is inside.
			// Use D as the vertex, and interpolate the UV coords.
			ClippedPoints[DestIndex] = D;
			ClippedUV[DestIndex++] = (UVEnd - UVStart) * dpos + UVStart;
		}
		return;

	} 

	// determine the percentage into the line segments that the intersection occurs.
	// an intersection of segments will produce r & s values between 0 & 1.
	denominator = 1.0 / denominator;
	r = numerator * denominator;

	numerator = (A[AXIS_2] - C[AXIS_2]) * (B[AXIS_1] - A[AXIS_1]) - (A[AXIS_1] - C[AXIS_1]) * (B[AXIS_2] - A[AXIS_2]);
	s = numerator * denominator;

	// determine if the line intersect within the defined segments.
	if((0.0 <= r) && (r <= 1.0) && (0.0 <= s) && (s <= 1.0)) {

		// they intersect.
		// determine intersection point 
		Vector3 v = D - C;
//		float len = v.Length();
		ClippedPoints[DestIndex] = C + v * s;
		
		// interpolate UV values
		Vector2 uv = UVEnd - UVStart;
//		len = uv.Length();
		ClippedUV[DestIndex++] = UVStart + uv * r;
	}
}

/*
	A failed attempt to use a graphics gem vol 2 example


	// Compute a1, b1, c1, where line joining points 1 and 2
    // is "a1 x  +  b1 y  +  c1  =  0".
	float a1 = B[AXIS_2] - A[AXIS_2];
	float b1 = B[AXIS_1] - A[AXIS_1];
	float c1 = B[AXIS_2] * A[AXIS_1] - A[AXIS_1] * B[AXIS_2];

	// Compute r3 & r4, the sign values
    float r3 = a1 * C[AXIS_1] + b1 * C[AXIS_2] + c1;
    float r4 = a1 * D[AXIS_1] + b1 * D[AXIS_2] + c1;

	// Check signs of r3 and r4.  If both point 3 and point 4 lie on
    // same side of line 1, the line segments do not intersect.
    if ( r3 != 0 && r4 != 0 && (((r3 < 0) && (r4 < 0)) || ((r3 > 0) && (r4 > 0)))
        return; // ( DONT_INTERSECT );

    // Compute a2, b2, c2
    float a2 = D[AXIS_2] - C[AXIS_2];
    float b2 = C[AXIS_1] - D[AXIS_1];
    float c2 = D[AXIS_1] * C[AXIS_2] - C[AXIS_1] * D[AXIS_2];

    // Compute r1 and r2
    float r1 = a2 * A[AXIS_1] + b2 * A[AXIS_2] + c2;
    float r2 = a2 * B[AXIS_1] + b2 * B[AXIS_2] + c2;

    // Check signs of r1 and r2.  If both point 1 and point 2 lie
    // on same side of second line segment, the line segments do
    // not intersect.
    if ( r1 != 0 && r2 != 0 && (((r1 < 0) && (r2 < 0)) || ((r1 > 0) && (r2 > 0))))
        return; // ( DONT_INTERSECT );

    // Line segments intersect: compute intersection point. 
    float denom = a1 * b2 - a2 * b1;
    if ( denom == 0 )
        return; // ( COLLINEAR );

    float offset = denom < 0 ? - denom * 0.5f : denom * 0.5f;

    // The denom/2 is to get rounding instead of truncating.  It
    // is added or subtracted to the numerator, depending upon the
    // sign of the numerator.
 
    float num = b1 * c2 - b2 * c1;
    float x = ( num < 0 ? num - offset : num + offset ) / denom;

    num = a2 * c1 - a1 * c2;
    float y = ( num < 0 ? num - offset : num + offset ) / denom;

	ClippedPoints[DestIndex] = Vector3(x,y,0);
	ClippedUV[DestIndex++] = Vector3
    return; //( DO_INTERSECT );  // lines_intersect
*/

inline bool IntersectionClass::In_Front_Of_Line
(
	const Vector3 & p,			// point to test
	const Vector3 & e0,			// point on edge
	const Vector3 & de			// direction of edge
)
{
	Vector3 dp = p - e0;
	float val = de.X*dp.Y - de.Y*dp.X;
	if (val > 0.0f) {
		return true;
	}
	return false;
}

inline float IntersectionClass::Intersect_Lines
(
	const Vector3 & p0,			// start of line segment
	const Vector3 & p1,			// end of line segment
	const Vector3 & e0,			// point on clipping edge
	const Vector3 & de			// direction of clipping edge
)
{
	float dpx = p1.X - p0.X;
	float dpy = p1.Y - p0.Y;

	float den = de.Y * dpx - de.X * dpy;
	
	if (fabs(den) > WWMATH_EPSILON) {

		float num = p0.Y*de.X - p0.X*de.Y + e0.X*de.Y - e0.Y*de.X;
		float t = num/den;
		if ((t >= 0.0f) && (t <= 1.0f)) {
			return t;
		}
	}

	return 0.0f;
}


#define EMIT(p,uv) OutPoints[outnum] = p; OutUVs[outnum] = uv; outnum++;


inline int IntersectionClass::Clip_Triangle_To_LineXY(	
	int incount,
	Vector3 * InPoints,
	Vector2 * InUVs,
	Vector3 * OutPoints,
	Vector2 * OutUVs,
	const Vector3 & edge_point0,
	const Vector3 & edge_point1
)
{
	Vector3 e0 = edge_point0;
	Vector3 de = edge_point1 - edge_point0;
	
	// number of verts output.
	int outnum = 0;

	// start and end verts of the current edge
	int p0,p1;
	p0 = incount-1;
	
	// intersection temporaries.
	float intersection;
	Vector3 intersection_point;
	Vector2 intersection_uv;

	// loop over each edge in the input polygon
	for (p1=0; p1<incount; p1++) {

		if (In_Front_Of_Line(InPoints[p1],e0,de)) {
			if (In_Front_Of_Line(InPoints[p0],e0,de)) {

				// both inside, emit p1
				EMIT(InPoints[p1],InUVs[p1]);
				
			} else {

				// edge going out->in, emit intersection and endpoint
				intersection = Intersect_Lines(InPoints[p0], InPoints[p1], e0, de);
				intersection_point = (1.0f - intersection) * InPoints[p0] + intersection * InPoints[p1];
				intersection_uv = (1.0f - intersection) * InUVs[p0] + intersection * InUVs[p1];
				EMIT(intersection_point,intersection_uv);
				EMIT(InPoints[p1],InUVs[p1]);
			}
		} else {

			if (In_Front_Of_Line(InPoints[p0], e0, de)) {
				
				// edge going in->out, emit intersection
				intersection = Intersect_Lines(InPoints[p0],InPoints[p1], e0, de);
				intersection_point = (1.0f - intersection) * InPoints[p0] + intersection * InPoints[p1];
				intersection_uv = (1.0f - intersection) * InUVs[p0] + intersection * InUVs[p1];
				EMIT(intersection_point,intersection_uv);

			}

		}

		// move to next edge
		p0 = p1;
	}

	return outnum;
}

inline int IntersectionClass::_Intersect_Triangles_Z(	
	Vector3 ClipPoints[3], 
	Vector3 TrianglePoints[3], 
	Vector2 UV[3],
	Vector3 ClippedPoints[6], 
	Vector2 ClippedUV[6]
)
{
	int count;
	Vector3 tmp_points[6];
	Vector2 tmp_uv[6];
	
	count = Clip_Triangle_To_LineXY(3,TrianglePoints,UV,ClippedPoints,ClippedUV,ClipPoints[0],ClipPoints[1]);
	count = Clip_Triangle_To_LineXY(count,ClippedPoints,ClippedUV,tmp_points,tmp_uv,ClipPoints[1],ClipPoints[2]);
	count = Clip_Triangle_To_LineXY(count,tmp_points,tmp_uv,ClippedPoints,ClippedUV,ClipPoints[2],ClipPoints[0]);
	
	return count;
}

/*
**	This function will fill the passed array with the set of points & uv values that represent
**	the boolean operation of the anding of the ClipPoints with the TrianglePoints. The UV values	
**	provided for the TrianglePoints triangle are used to generate accurate UV values for any
**	new points created by this operation.
**	This function returns the number of vertices it required to define the intersection.
* /
int IntersectionClass::_Intersect_Triangles_Z(	
	Vector3 ClipPoints[3], 
	Vector3 TrianglePoints[3], 
	Vector2 UV[3],
	Vector3 ClippedPoints[6], 
	Vector2 ClippedUV[6]
)
{
	// first, check to see if all triangle points are inside clip area
	// the point in polygon will drop any inside points to the clip triangle plane.
	bool inside[3];

	bool noclip;
	noclip =  inside[0] = _Point_In_Polygon_Z(TrianglePoints[0], ClipPoints);
	noclip &= inside[1] = _Point_In_Polygon_Z(TrianglePoints[1], ClipPoints);
	noclip &= inside[2] = _Point_In_Polygon_Z(TrianglePoints[2], ClipPoints);

	// if all points are inside clip area, then copy the triangle points &
	// UV's to the destination & return 3 (the number of points in the clipped polygon).
	if(noclip) {
		ClippedPoints[0] = TrianglePoints[0];
		ClippedPoints[1] = TrianglePoints[1];
		ClippedPoints[2] = TrianglePoints[2];
		ClippedUV[0] = UV[0];
		ClippedUV[1] = UV[1];
		ClippedUV[2] = UV[2];

		return 3;
	}

	int points = 0;	// number of output polygon points

	//	not all uv triangle points are inside the clip triangle.
	//	Test to see if any clip points are inside the uv triangle
	float alpha, beta;
	if(_Point_In_Polygon(ClipPoints[0], TrianglePoints[0], TrianglePoints[1], TrianglePoints[2], 0, 1, alpha, beta)) {
		ClippedPoints[points] = ClipPoints[0];
		Vector2 uv1 = UV[1] - UV[0];
		Vector2 uv2 = UV[2] - UV[0];
		ClippedUV[points++] = UV[0] + alpha * uv1 + beta * uv2; 
	}

	if(_Point_In_Polygon(ClipPoints[1], TrianglePoints[0], TrianglePoints[1], TrianglePoints[2], 0, 1, alpha, beta)) {
		ClippedPoints[points] = ClipPoints[1];
		Vector2 uv1 = UV[1] - UV[0];
		Vector2 uv2 = UV[2] - UV[0];
		ClippedUV[points++] = UV[0] + alpha * uv1 + beta * uv2; 
	}

	if(_Point_In_Polygon(ClipPoints[2], TrianglePoints[0], TrianglePoints[1], TrianglePoints[2], 0, 1, alpha, beta)) {
		ClippedPoints[points] = ClipPoints[2];
		Vector2 uv1 = UV[1] - UV[0];
		Vector2 uv2 = UV[2] - UV[0];
		ClippedUV[points++] = UV[0] + alpha * uv1 + beta * uv2; 
	}

	// if all 3 clip points are inside the decal triangle then return
	if(points == 3)
		return;

	//	The clip triangle does not fully contain the uv triangle, and the uv triangle
	//	does not fully contain the clip triangle.
	//	Intersect any edge which has at least one outside point with all of the clip edges. 
	//	First, determine which edges to test. Those points that are already clipped (by being inside)
	//	are immediately copied to the clipped point & uv arrays.

	//	these bools indicate which edges of the triangle to be clipped are to be tested.
	bool test_01 = false;
	bool test_02 = false;
	bool test_12 = false;

	if( inside[0] )	{	ClippedPoints[points] = TrianglePoints[0]; ClippedUV[points++] = UV[0];	} 
	else {	test_01 = test_02 = true; } 
	
	if( inside[1] )	{	ClippedPoints[points] = TrianglePoints[1]; ClippedUV[points++] = UV[1];	}
	else {	test_01 = test_12 = true; }

	if( inside[2] )	{	ClippedPoints[points] = TrianglePoints[2]; ClippedUV[points++] = UV[2];}
	else {	test_02 = test_12 = true; }

	//	Now test each indicated segment.
	//	Intersect_2D_Lines will interpolate the clipped UV values if an intersection occurs, and it
	//	will also increment the points variable (passed as a reference).
	//	Any intersections are stored in the passed ClippedPoints array.
	if(test_01) {
		_Intersect_Lines_Z(	TrianglePoints[0], TrianglePoints[1],
							UV[0], UV[1],
							ClipPoints[0], ClipPoints[1],
							ClippedPoints, 
							ClippedUV,
							points);
		_Intersect_Lines_Z(	TrianglePoints[0], TrianglePoints[1],
							UV[0], UV[1],
							ClipPoints[0], ClipPoints[2],
							ClippedPoints, 
							ClippedUV,
							points);
		_Intersect_Lines_Z(	TrianglePoints[0], TrianglePoints[1],
							UV[0], UV[1],
							ClipPoints[1], ClipPoints[2],
							ClippedPoints, 
							ClippedUV,
							points);
	}
	if(test_02) {
		_Intersect_Lines_Z(	TrianglePoints[0], TrianglePoints[2],
							UV[0], UV[2],
							ClipPoints[0], ClipPoints[1],
							ClippedPoints, 
							ClippedUV,
							points);
		_Intersect_Lines_Z(	TrianglePoints[0], TrianglePoints[2],
							UV[0], UV[2],
							ClipPoints[0], ClipPoints[2],
							ClippedPoints, 
							ClippedUV,
							points);
		_Intersect_Lines_Z(	TrianglePoints[0], TrianglePoints[2],
							UV[0], UV[2],
							ClipPoints[1], ClipPoints[2],
							ClippedPoints, 
							ClippedUV,
							points);
	}
	if(test_12) {
		_Intersect_Lines_Z(	TrianglePoints[1], TrianglePoints[2],
							UV[1], UV[2],
							ClipPoints[0], ClipPoints[1],
							ClippedPoints, 
							ClippedUV,
							points);
		_Intersect_Lines_Z(	TrianglePoints[1], TrianglePoints[2],
							UV[1], UV[2],
							ClipPoints[0], ClipPoints[2],
							ClippedPoints, 
							ClippedUV,
							points);
		_Intersect_Lines_Z(	TrianglePoints[1], TrianglePoints[2],
							UV[1], UV[2],
							ClipPoints[1], ClipPoints[2],
							ClippedPoints, 
							ClippedUV,
							points);
	}

	//	If no intersections have occurred, then the triangle must be completely outside
	//	the clipping area.
/*
	//	if it is determined that no intersections have occurred, then copy the clip triangle points
	//	into the destination array and determine the correct UV values for the subset of the
	//	triangle that was clipped.
	if(points == 0) {
		ClippedPoints[0] = ClipPoints[0];
		ClippedPoints[1] = ClipPoints[1];
		ClippedPoints[2] = ClipPoints[2];
		ClippedUV[0] = UV[0];
		ClippedUV[1] = UV[1];
		ClippedUV[2] = UV[2];

		return 3;
	}
* /
	// points will be 0, 3, 4, 5 or 6 
	if(!((points == 0) || (points == 3) || (points == 4) || (points == 5) || (points == 6))) {
		Debug.Print("points", points);
		return 0; //_Intersect_Triangles_Z(	ClipPoints, TrianglePoints, UV, ClippedPoints, ClippedUV);
	}

	return points;

}
*/


#endif