summaryrefslogtreecommitdiffhomepage
path: root/Opcode/Ice/IceIndexedTriangle.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'Opcode/Ice/IceIndexedTriangle.cpp')
-rw-r--r--Opcode/Ice/IceIndexedTriangle.cpp1096
1 files changed, 548 insertions, 548 deletions
diff --git a/Opcode/Ice/IceIndexedTriangle.cpp b/Opcode/Ice/IceIndexedTriangle.cpp
index 58687cd..3e74cbb 100644
--- a/Opcode/Ice/IceIndexedTriangle.cpp
+++ b/Opcode/Ice/IceIndexedTriangle.cpp
@@ -1,548 +1,548 @@
-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
-/**
- * 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]));
-}
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ * 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]));
+}