path: root/third-party/Opcode/Ice/IceIndexedTriangle.cpp

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Contains a handy indexed triangle class.
 *	\file		IceIndexedTriangle.cpp
 *	\author		Pierre Terdiman
 *	\date		January, 17, 2000
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Precompiled Header
#include "StdAfx.h"

using namespace IceMaths;

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Contains an indexed triangle class.
 *
 *	\class		Triangle
 *	\author		Pierre Terdiman
 *	\version	1.0
 *	\date		08.15.98
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Flips the winding order.
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void IndexedTriangle::Flip()
{
	Swap(mVRef[1], mVRef[2]);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Computes the triangle area.
 *	\param		verts	[in] the list of indexed vertices
 *	\return		the area
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
float IndexedTriangle::Area(const IcePoint* verts)	const
{
	if(!verts)	return 0.0f;
	const IcePoint& p0 = verts[0];
	const IcePoint& p1 = verts[1];
	const IcePoint& p2 = verts[2];
	return ((p0-p1)^(p0-p2)).Magnitude() * 0.5f;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Computes the triangle perimeter.
 *	\param		verts	[in] the list of indexed vertices
 *	\return		the perimeter
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
float IndexedTriangle::Perimeter(const IcePoint* verts)	const
{
	if(!verts)	return 0.0f;
	const IcePoint& p0 = verts[0];
	const IcePoint& p1 = verts[1];
	const IcePoint& p2 = verts[2];
	return		p0.Distance(p1)
			+	p0.Distance(p2)
			+	p1.Distance(p2);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Computes the triangle compacity.
 *	\param		verts	[in] the list of indexed vertices
 *	\return		the compacity
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
float IndexedTriangle::Compacity(const IcePoint* verts) const
{
	if(!verts)	return 0.0f;
	float P = Perimeter(verts);
	if(P==0.0f)	return 0.0f;
	return (4.0f*PI*Area(verts)/(P*P));
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Computes the triangle normal.
 *	\param		verts	[in] the list of indexed vertices
 *	\param		normal	[out] the computed normal
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void IndexedTriangle::Normal(const IcePoint* verts, IcePoint& normal)	const
{
	if(!verts)	return;

	const IcePoint& p0 = verts[mVRef[0]];
	const IcePoint& p1 = verts[mVRef[1]];
	const IcePoint& p2 = verts[mVRef[2]];
	normal = ((p2-p1)^(p0-p1)).Normalize();
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Computes the triangle denormalized normal.
 *	\param		verts	[in] the list of indexed vertices
 *	\param		normal	[out] the computed normal
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void IndexedTriangle::DenormalizedNormal(const IcePoint* verts, IcePoint& normal)	const
{
	if(!verts)	return;

	const IcePoint& p0 = verts[mVRef[0]];
	const IcePoint& p1 = verts[mVRef[1]];
	const IcePoint& p2 = verts[mVRef[2]];
	normal = ((p2-p1)^(p0-p1));
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Computes the triangle center.
 *	\param		verts	[in] the list of indexed vertices
 *	\param		center	[out] the computed center
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void IndexedTriangle::Center(const IcePoint* verts, IcePoint& center)	const
{
	if(!verts)	return;

	const IcePoint& p0 = verts[mVRef[0]];
	const IcePoint& p1 = verts[mVRef[1]];
	const IcePoint& p2 = verts[mVRef[2]];
	center = (p0+p1+p2)*INV3;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Computes the centered normal
 *	\param		verts	[in] the list of indexed vertices
 *	\param		normal	[out] the computed centered normal
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void IndexedTriangle::CenteredNormal(const IcePoint* verts, IcePoint& normal)	const
{
	if(!verts)	return;

	const IcePoint& p0 = verts[mVRef[0]];
	const IcePoint& p1 = verts[mVRef[1]];
	const IcePoint& p2 = verts[mVRef[2]];
	IcePoint Center = (p0+p1+p2)*INV3;
	normal = Center + ((p2-p1)^(p0-p1)).Normalize();
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Computes a random point within the triangle.
 *	\param		verts	[in] the list of indexed vertices
 *	\param		normal	[out] the computed centered normal
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void IndexedTriangle::RandomPoint(const IcePoint* verts, IcePoint& random)	const
{
	if(!verts)	return;

	// Random barycentric coords
	float Alpha	= UnitRandomFloat();
	float Beta	= UnitRandomFloat();
	float Gamma	= UnitRandomFloat();
	float OneOverTotal = 1.0f / (Alpha + Beta + Gamma);
	Alpha	*= OneOverTotal;
	Beta	*= OneOverTotal;
	Gamma	*= OneOverTotal;

	const IcePoint& p0 = verts[mVRef[0]];
	const IcePoint& p1 = verts[mVRef[1]];
	const IcePoint& p2 = verts[mVRef[2]];
	random = Alpha*p0 + Beta*p1 + Gamma*p2;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Computes backface culling.
 *	\param		verts	[in] the list of indexed vertices
 *	\param		source	[in] source point (in local space) from which culling must be computed
 *	\return		true if the triangle is visible from the source point
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
bool IndexedTriangle::IsVisible(const IcePoint* verts, const IcePoint& source)	const
{
	// Checkings
	if(!verts)	return false;

	const IcePoint& p0 = verts[mVRef[0]];
	const IcePoint& p1 = verts[mVRef[1]];
	const IcePoint& p2 = verts[mVRef[2]];

	// Compute denormalized normal
	IcePoint Normal = (p2 - p1)^(p0 - p1);

	// Backface culling
	return (Normal | source) >= 0.0f;

// Same as:
//	IcePlane PL(verts[mVRef[0]], verts[mVRef[1]], verts[mVRef[2]]);
//	return PL.Distance(source) > PL.d;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Computes backface culling.
 *	\param		verts	[in] the list of indexed vertices
 *	\param		source	[in] source point (in local space) from which culling must be computed
 *	\return		true if the triangle is visible from the source point
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
bool IndexedTriangle::BackfaceCulling(const IcePoint* verts, const IcePoint& source)	const
{
	// Checkings
	if(!verts)	return false;

	const IcePoint& p0 = verts[mVRef[0]];
	const IcePoint& p1 = verts[mVRef[1]];
	const IcePoint& p2 = verts[mVRef[2]];

	// Compute base
//	IcePoint Base = (p0 + p1 + p2)*INV3;

	// Compute denormalized normal
	IcePoint Normal = (p2 - p1)^(p0 - p1);

	// Backface culling
//	return (Normal | (source - Base)) >= 0.0f;
	return (Normal | (source - p0)) >= 0.0f;

// Same as: (but a bit faster)
//	IcePlane PL(verts[mVRef[0]], verts[mVRef[1]], verts[mVRef[2]]);
//	return PL.Distance(source)>0.0f;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Computes the occlusion potential of the triangle.
 *	\param		verts	[in] the list of indexed vertices
 *	\param		source	[in] source point (in local space) from which occlusion potential must be computed
 *	\return		the occlusion potential
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
float IndexedTriangle::ComputeOcclusionPotential(const IcePoint* verts, const IcePoint& view)	const
{
	if(!verts)	return 0.0f;
	// Occlusion potential: -(A * (N|V) / d^2)
	// A = polygon area
	// N = polygon normal
	// V = view vector
	// d = distance viewpoint-center of polygon

	float A = Area(verts);
	IcePoint N;	Normal(verts, N);
	IcePoint C;	Center(verts, C);
	float d = view.Distance(C);
	return -(A*(N|view))/(d*d);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Replaces a vertex reference with another one.
 *	\param		oldref	[in] the vertex reference to replace
 *	\param		newref	[in] the new vertex reference
 *	\return		true if success, else false if the input vertex reference doesn't belong to the triangle
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
bool IndexedTriangle::ReplaceVertex(udword oldref, udword newref)
{
			if(mVRef[0]==oldref)	{ mVRef[0] = newref; return true; }
	else	if(mVRef[1]==oldref)	{ mVRef[1] = newref; return true; }
	else	if(mVRef[2]==oldref)	{ mVRef[2] = newref; return true; }
	return false;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Checks whether the triangle is degenerate or not. A degenerate triangle has two common vertex references. This is a zero-area triangle.
 *	\return		true if the triangle is degenerate
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
bool IndexedTriangle::IsDegenerate()	const
{
	if(mVRef[0]==mVRef[1])	return true;
	if(mVRef[1]==mVRef[2])	return true;
	if(mVRef[2]==mVRef[0])	return true;
	return false;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Checks whether the input vertex reference belongs to the triangle or not.
 *	\param		ref		[in] the vertex reference to look for
 *	\return		true if the triangle contains the vertex reference
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
bool IndexedTriangle::HasVertex(udword ref)	const
{
	if(mVRef[0]==ref)	return true;
	if(mVRef[1]==ref)	return true;
	if(mVRef[2]==ref)	return true;
	return false;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Checks whether the input vertex reference belongs to the triangle or not.
 *	\param		ref		[in] the vertex reference to look for
 *	\param		index	[out] the corresponding index in the triangle
 *	\return		true if the triangle contains the vertex reference
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
bool IndexedTriangle::HasVertex(udword ref, udword* index)	const
{
	if(mVRef[0]==ref)	{ *index = 0;	return true; }
	if(mVRef[1]==ref)	{ *index = 1;	return true; }
	if(mVRef[2]==ref)	{ *index = 2;	return true; }
	return false;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Finds an edge in a tri, given two vertex references.
 *	\param		vref0	[in] the edge's first vertex reference
 *	\param		vref1	[in] the edge's second vertex reference
 *	\return		the edge number between 0 and 2, or 0xff if input refs are wrong.
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
ubyte IndexedTriangle::FindEdge(udword vref0, udword vref1)	const
{
			if(mVRef[0]==vref0 && mVRef[1]==vref1)	return 0;
	else	if(mVRef[0]==vref1 && mVRef[1]==vref0)	return 0;
	else	if(mVRef[0]==vref0 && mVRef[2]==vref1)	return 1;
	else	if(mVRef[0]==vref1 && mVRef[2]==vref0)	return 1;
	else	if(mVRef[1]==vref0 && mVRef[2]==vref1)	return 2;
	else	if(mVRef[1]==vref1 && mVRef[2]==vref0)	return 2;
	return 0xff;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Gets the last reference given the first two.
 *	\param		vref0	[in] the first vertex reference
 *	\param		vref1	[in] the second vertex reference
 *	\return		the last reference, or INVALID_ID if input refs are wrong.
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
udword IndexedTriangle::OppositeVertex(udword vref0, udword vref1)	const
{
			if(mVRef[0]==vref0 && mVRef[1]==vref1)	return mVRef[2];
	else	if(mVRef[0]==vref1 && mVRef[1]==vref0)	return mVRef[2];
	else	if(mVRef[0]==vref0 && mVRef[2]==vref1)	return mVRef[1];
	else	if(mVRef[0]==vref1 && mVRef[2]==vref0)	return mVRef[1];
	else	if(mVRef[1]==vref0 && mVRef[2]==vref1)	return mVRef[0];
	else	if(mVRef[1]==vref1 && mVRef[2]==vref0)	return mVRef[0];
	return INVALID_ID;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Gets the three sorted vertex references according to an edge number.
 *	edgenb = 0	=> edge 0-1, returns references 0, 1, 2
 *	edgenb = 1	=> edge 0-2, returns references 0, 2, 1
 *	edgenb = 2	=> edge 1-2, returns references 1, 2, 0
 *
 *	\param		edgenb	[in] the edge number, 0, 1 or 2
 *	\param		vref0	[out] the returned first vertex reference
 *	\param		vref1	[out] the returned second vertex reference
 *	\param		vref2	[out] the returned third vertex reference
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void IndexedTriangle::GetVRefs(ubyte edgenb, udword& vref0, udword& vref1, udword& vref2) const
{
	if(edgenb==0)
	{
		vref0 = mVRef[0];
		vref1 = mVRef[1];
		vref2 = mVRef[2];
	}
	else if(edgenb==1)
	{
		vref0 = mVRef[0];
		vref1 = mVRef[2];
		vref2 = mVRef[1];
	}
	else if(edgenb==2)
	{
		vref0 = mVRef[1];
		vref1 = mVRef[2];
		vref2 = mVRef[0];
	}
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Computes the triangle's smallest edge length.
 *	\param		verts	[in] the list of indexed vertices
 *	\return		the smallest edge length
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
float IndexedTriangle::MinEdgeLength(const IcePoint* verts)	const
{
	if(!verts)	return 0.0f;

	float Min = MAX_FLOAT;
	float Length01 = verts[0].Distance(verts[1]);
	float Length02 = verts[0].Distance(verts[2]);
	float Length12 = verts[1].Distance(verts[2]);
	if(Length01 < Min)	Min = Length01;
	if(Length02 < Min)	Min = Length02;
	if(Length12 < Min)	Min = Length12;
	return Min;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Computes the triangle's largest edge length.
 *	\param		verts	[in] the list of indexed vertices
 *	\return		the largest edge length
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
float IndexedTriangle::MaxEdgeLength(const IcePoint* verts)	const
{
	if(!verts)	return 0.0f;

	float Max = MIN_FLOAT;
	float Length01 = verts[0].Distance(verts[1]);
	float Length02 = verts[0].Distance(verts[2]);
	float Length12 = verts[1].Distance(verts[2]);
	if(Length01 > Max)	Max = Length01;
	if(Length02 > Max)	Max = Length02;
	if(Length12 > Max)	Max = Length12;
	return Max;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Computes a point on the triangle according to the stabbing information.
 *	\param		verts		[in] the list of indexed vertices
 *	\param		u,v			[in] point's barycentric coordinates
 *	\param		pt			[out] point on triangle
 *	\param		nearvtx		[out] index of nearest vertex
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void IndexedTriangle::ComputePoint(const IcePoint* verts, float u, float v, IcePoint& pt, udword* nearvtx)	const
{
	// Checkings
	if(!verts)	return;

	// Get face in local or global space
	const IcePoint& p0 = verts[mVRef[0]];
	const IcePoint& p1 = verts[mVRef[1]];
	const IcePoint& p2 = verts[mVRef[2]];

	// Compute point coordinates
	pt = (1.0f - u - v)*p0 + u*p1 + v*p2;

	// Compute nearest vertex if needed
	if(nearvtx)
	{
		// Compute distance vector
		IcePoint d(p0.SquareDistance(pt),	// Distance^2 from vertex 0 to point on the face
				p1.SquareDistance(pt),	// Distance^2 from vertex 1 to point on the face
				p2.SquareDistance(pt));	// Distance^2 from vertex 2 to point on the face

		// Get smallest distance
		*nearvtx = mVRef[d.SmallestAxis()];
	}
}

	//**************************************
	// Angle between two vectors (in radians)
	// we use this formula
	// uv = |u||v| cos(u,v)
	// u  ^ v  = w
	// |w| = |u||v| |sin(u,v)|
	//**************************************
	float Angle(const IcePoint& u, const IcePoint& v)
	{
		float NormU = u.Magnitude();	// |u|
		float NormV = v.Magnitude();	// |v|
		float Product = NormU*NormV;	// |u||v|
		if(Product==0.0f)	return 0.0f;
		float OneOverProduct = 1.0f / Product;

		// Cosinus
		float Cosinus = (u|v) * OneOverProduct;

		// Sinus
		IcePoint w = u^v;
		float NormW = w.Magnitude();

		float AbsSinus = NormW * OneOverProduct;

		// Remove degeneracy
		if(AbsSinus > 1.0f) AbsSinus = 1.0f;
		if(AbsSinus < -1.0f) AbsSinus = -1.0f;

		if(Cosinus>=0.0f)	return asinf(AbsSinus);
		else				return (PI-asinf(AbsSinus));
	}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Computes the angle between two triangles.
 *	\param		tri		[in] the other triangle
 *	\param		verts	[in] the list of indexed vertices
 *	\return		the angle in radians
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
float IndexedTriangle::Angle(const IndexedTriangle& tri, const IcePoint* verts)	const
{
	// Checkings
	if(!verts)	return 0.0f;

	// Compute face normals
	IcePoint n0, n1;
	Normal(verts, n0);
	tri.Normal(verts, n1);

	// Compute angle
	float dp = n0|n1;
	if(dp>1.0f)		return 0.0f;
	if(dp<-1.0f)	return PI;
	return acosf(dp);

//	return ::Angle(n0,n1);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Checks a triangle is the same as another one.
 *	\param		tri		[in] the other triangle
 *	\return		true if same triangle
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
bool IndexedTriangle::Equal(const IndexedTriangle& tri) const
{
	// Test all vertex references
	return (HasVertex(tri.mVRef[0]) && 
			HasVertex(tri.mVRef[1]) &&
			HasVertex(tri.mVRef[2]));
}