Extras/CDTestFramework/Opcode/Ice/IceTriangle.cpp

   1 /*
   2  *      ICE / OPCODE - Optimized Collision Detection
   3  * http://www.codercorner.com/Opcode.htm
   4  *
   5  * Copyright (c) 2001-2008 Pierre Terdiman,  pierre@codercorner.com
   6
   7 This software is provided 'as-is', without any express or implied warranty.
   8 In no event will the authors be held liable for any damages arising from the use of this software.
   9 Permission is granted to anyone to use this software for any purpose,
  10 including commercial applications, and to alter it and redistribute it freely,
  11 subject to the following restrictions:
  12
  13 1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
  14 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
  15 3. This notice may not be removed or altered from any source distribution.
  16 */
  17 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  18 /**
  19  *      Contains a handy triangle class.
  20  *      \file           IceTriangle.cpp
  21  *      \author         Pierre Terdiman
  22  *      \date           January, 17, 2000
  23  */
  24 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  25
  26 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  27 // Precompiled Header
  28 #include "Stdafx.h"
  29
  30 using namespace Opcode;
  31
  32 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  33 /**
  34  *      Contains a triangle class.
  35  *
  36  *      \class          Tri
  37  *      \author         Pierre Terdiman
  38  *      \version        1.0
  39  *      \date           08.15.98
  40 */
  41 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  42
  43 static sdword VPlaneSideEps(const Point& v, const Plane& plane, float epsilon)
  44 {
  45         // Compute distance from current vertex to the plane
  46         float Dist = plane.Distance(v);
  47         // Compute side:
  48         // 1    = the vertex is on the positive side of the plane
  49         // -1   = the vertex is on the negative side of the plane
  50         // 0    = the vertex is on the plane (within epsilon)
  51         return Dist > epsilon ? 1 : Dist < -epsilon ? -1 : 0;
  52 }
  53
  54 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  55 /**
  56  *      Flips the winding order.
  57  */
  58 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  59 void Triangle::Flip()
  60 {
  61         Point Tmp = mVerts[1];
  62         mVerts[1] = mVerts[2];
  63         mVerts[2] = Tmp;
  64 }
  65
  66 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  67 /**
  68  *      Computes the triangle area.
  69  *      \return         the area
  70  */
  71 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  72 float Triangle::Area() const
  73 {
  74         const Point& p0 = mVerts[0];
  75         const Point& p1 = mVerts[1];
  76         const Point& p2 = mVerts[2];
  77         return ((p0 - p1)^(p0 - p2)).Magnitude() * 0.5f;
  78 }
  79
  80 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  81 /**
  82  *      Computes the triangle perimeter.
  83  *      \return         the perimeter
  84  */
  85 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  86 float Triangle::Perimeter()     const
  87 {
  88         const Point& p0 = mVerts[0];
  89         const Point& p1 = mVerts[1];
  90         const Point& p2 = mVerts[2];
  91         return          p0.Distance(p1)
  92                         +       p0.Distance(p2)
  93                         +       p1.Distance(p2);
  94 }
  95
  96 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  97 /**
  98  *      Computes the triangle compacity.
  99  *      \return         the compacity
 100  */
 101 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 102 float Triangle::Compacity() const
 103 {
 104         float P = Perimeter();
 105         if(P==0.0f)     return 0.0f;
 106         return (4.0f*PI*Area()/(P*P));
 107 }
 108
 109 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 110 /**
 111  *      Computes the triangle normal.
 112  *      \param          normal  [out] the computed normal
 113  */
 114 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 115 void Triangle::Normal(Point& normal) const
 116 {
 117         const Point& p0 = mVerts[0];
 118         const Point& p1 = mVerts[1];
 119         const Point& p2 = mVerts[2];
 120         normal = ((p0 - p1)^(p0 - p2)).Normalize();
 121 }
 122
 123 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 124 /**
 125  *      Computes the triangle denormalized normal.
 126  *      \param          normal  [out] the computed normal
 127  */
 128 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 129 void Triangle::DenormalizedNormal(Point& normal) const
 130 {
 131         const Point& p0 = mVerts[0];
 132         const Point& p1 = mVerts[1];
 133         const Point& p2 = mVerts[2];
 134         normal = ((p0 - p1)^(p0 - p2));
 135 }
 136
 137 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 138 /**
 139  *      Computes the triangle center.
 140  *      \param          center  [out] the computed center
 141  */
 142 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 143 void Triangle::Center(Point& center) const
 144 {
 145         const Point& p0 = mVerts[0];
 146         const Point& p1 = mVerts[1];
 147         const Point& p2 = mVerts[2];
 148         center = (p0 + p1 + p2)*INV3;
 149 }
 150
 151 PartVal Triangle::TestAgainstPlane(const Plane& plane, float epsilon) const
 152 {
 153         bool Pos = false, Neg = false;
 154
 155         // Loop through all vertices
 156         for(udword i=0;i<3;i++)
 157         {
 158                 // Compute side:
 159                 sdword Side = VPlaneSideEps(mVerts[i], plane, epsilon);
 160
 161                                 if (Side < 0)   Neg = true;
 162                 else    if (Side > 0)   Pos = true;
 163         }
 164
 165                         if (!Pos && !Neg)       return TRI_ON_PLANE;
 166         else    if (Pos && Neg)         return TRI_INTERSECT;
 167         else    if (Pos && !Neg)        return TRI_PLUS_SPACE;
 168         else    if (!Pos && Neg)        return TRI_MINUS_SPACE;
 169
 170         // What?!
 171         return TRI_FORCEDWORD;
 172 }
 173
 174 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 175 /**
 176  *      Computes the triangle moment.
 177  *      \param          m       [out] the moment
 178  */
 179 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 180 /*
 181 void Triangle::ComputeMoment(Moment& m)
 182 {
 183         // Compute the area of the triangle
 184         m.mArea = Area();
 185
 186         // Compute the centroid
 187         Center(m.mCentroid);
 188
 189         // Second-order components. Handle zero-area faces.
 190         Point& p = mVerts[0];
 191         Point& q = mVerts[1];
 192         Point& r = mVerts[2];
 193         if(m.mArea==0.0f)
 194         {
 195                 // This triangle has zero area. The second order components would be eliminated with the usual formula, so, for the
 196                 // sake of robustness we use an alternative form. These are the centroid and second-order components of the triangle's vertices.
 197                 m.mCovariance.m[0][0] = (p.x*p.x + q.x*q.x + r.x*r.x);
 198                 m.mCovariance.m[0][1] = (p.x*p.y + q.x*q.y + r.x*r.y);
 199                 m.mCovariance.m[0][2] = (p.x*p.z + q.x*q.z + r.x*r.z);
 200                 m.mCovariance.m[1][1] = (p.y*p.y + q.y*q.y + r.y*r.y);
 201                 m.mCovariance.m[1][2] = (p.y*p.z + q.y*q.z + r.y*r.z);
 202                 m.mCovariance.m[2][2] = (p.z*p.z + q.z*q.z + r.z*r.z);
 203                 m.mCovariance.m[2][1] = m.mCovariance.m[1][2];
 204                 m.mCovariance.m[1][0] = m.mCovariance.m[0][1];
 205                 m.mCovariance.m[2][0] = m.mCovariance.m[0][2];
 206         }
 207         else
 208         {
 209                 const float OneOverTwelve = 1.0f / 12.0f;
 210                 m.mCovariance.m[0][0] = m.mArea * (9.0f * m.mCentroid.x*m.mCentroid.x + p.x*p.x + q.x*q.x + r.x*r.x) * OneOverTwelve;
 211                 m.mCovariance.m[0][1] = m.mArea * (9.0f * m.mCentroid.x*m.mCentroid.y + p.x*p.y + q.x*q.y + r.x*r.y) * OneOverTwelve;
 212                 m.mCovariance.m[1][1] = m.mArea * (9.0f * m.mCentroid.y*m.mCentroid.y + p.y*p.y + q.y*q.y + r.y*r.y) * OneOverTwelve;
 213                 m.mCovariance.m[0][2] = m.mArea * (9.0f * m.mCentroid.x*m.mCentroid.z + p.x*p.z + q.x*q.z + r.x*r.z) * OneOverTwelve;
 214                 m.mCovariance.m[1][2] = m.mArea * (9.0f * m.mCentroid.y*m.mCentroid.z + p.y*p.z + q.y*q.z + r.y*r.z) * OneOverTwelve;
 215                 m.mCovariance.m[2][2] = m.mArea * (9.0f * m.mCentroid.z*m.mCentroid.z + p.z*p.z + q.z*q.z + r.z*r.z) * OneOverTwelve;
 216                 m.mCovariance.m[2][1] = m.mCovariance.m[1][2];
 217                 m.mCovariance.m[1][0] = m.mCovariance.m[0][1];
 218                 m.mCovariance.m[2][0] = m.mCovariance.m[0][2];
 219         }
 220 }
 221 */
 222
 223 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 224 /**
 225  *      Computes the triangle's smallest edge length.
 226  *      \return         the smallest edge length
 227  */
 228 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 229 float Triangle::MinEdgeLength() const
 230 {
 231         float Min = MAX_FLOAT;
 232         float Length01 = mVerts[0].Distance(mVerts[1]);
 233         float Length02 = mVerts[0].Distance(mVerts[2]);
 234         float Length12 = mVerts[1].Distance(mVerts[2]);
 235         if(Length01 < Min)      Min = Length01;
 236         if(Length02 < Min)      Min = Length02;
 237         if(Length12 < Min)      Min = Length12;
 238         return Min;
 239 }
 240
 241 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 242 /**
 243  *      Computes the triangle's largest edge length.
 244  *      \return         the largest edge length
 245  */
 246 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 247 float Triangle::MaxEdgeLength() const
 248 {
 249         float Max = MIN_FLOAT;
 250         float Length01 = mVerts[0].Distance(mVerts[1]);
 251         float Length02 = mVerts[0].Distance(mVerts[2]);
 252         float Length12 = mVerts[1].Distance(mVerts[2]);
 253         if(Length01 > Max)      Max = Length01;
 254         if(Length02 > Max)      Max = Length02;
 255         if(Length12 > Max)      Max = Length12;
 256         return Max;
 257 }
 258
 259 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 260 /**
 261  *      Computes a point on the triangle according to the stabbing information.
 262  *      \param          u,v                     [in] point's barycentric coordinates
 263  *      \param          pt                      [out] point on triangle
 264  *      \param          nearvtx         [out] index of nearest vertex
 265  */
 266 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 267 void Triangle::ComputePoint(float u, float v, Point& pt, udword* nearvtx)       const
 268 {
 269         // Compute point coordinates
 270         pt = (1.0f - u - v)*mVerts[0] + u*mVerts[1] + v*mVerts[2];
 271
 272         // Compute nearest vertex if needed
 273         if(nearvtx)
 274         {
 275                 // Compute distance vector
 276                 Point d(mVerts[0].SquareDistance(pt),   // Distance^2 from vertex 0 to point on the face
 277                                 mVerts[1].SquareDistance(pt),   // Distance^2 from vertex 1 to point on the face
 278                                 mVerts[2].SquareDistance(pt));  // Distance^2 from vertex 2 to point on the face
 279
 280                 // Get smallest distance
 281                 *nearvtx = d.SmallestAxis();
 282         }
 283 }
 284
 285 void Triangle::Inflate(float fat_coeff, bool constant_border)
 286 {
 287         // Compute triangle center
 288         Point TriangleCenter;
 289         Center(TriangleCenter);
 290
 291         // Don't normalize?
 292         // Normalize => add a constant border, regardless of triangle size
 293         // Don't => add more to big triangles
 294         for(udword i=0;i<3;i++)
 295         {
 296                 Point v = mVerts[i] - TriangleCenter;
 297
 298                 if(constant_border)     v.Normalize();
 299
 300                 mVerts[i] += v * fat_coeff;
 301         }
 302 }