Extras/HACD/hacdManifoldMesh.cpp

   1 /* Copyright (c) 2011 Khaled Mamou (kmamou at gmail dot com)\r
   2  All rights reserved.\r
   3  \r
   4  \r
   5  Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:\r
   6  \r
   7  1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.\r
   8  \r
   9  2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.\r
  10  \r
  11  3. The names of the contributors may not be used to endorse or promote products derived from this software without specific prior written permission.\r
  12  \r
  13  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\r
  14  */\r
  15 #include "hacdManifoldMesh.h"\r
  16 using namespace std;\r
  17 \r
  18 \r
  19 namespace HACD\r
  20 {    \r
  21     Material::Material(void)\r
  22     {\r
  23         m_diffuseColor.X()  = 0.5;\r
  24         m_diffuseColor.Y()  = 0.5;\r
  25         m_diffuseColor.Z()  = 0.5;\r
  26         m_specularColor.X() = 0.5;\r
  27         m_specularColor.Y() = 0.5;\r
  28         m_specularColor.Z() = 0.5;\r
  29         m_ambientIntensity  = 0.4;\r
  30         m_emissiveColor.X() = 0.0;\r
  31         m_emissiveColor.Y() = 0.0;\r
  32         m_emissiveColor.Z() = 0.0;\r
  33         m_shininess         = 0.4;\r
  34         m_transparency      = 0.0;\r
  35     }\r
  36     \r
  37         TMMVertex::TMMVertex(void)\r
  38         {\r
  39                 m_name = 0;\r
  40         m_id = 0;\r
  41                 m_duplicate = 0;\r
  42                 m_onHull = false;\r
  43                 m_tag = false;\r
  44         }\r
  45         TMMVertex::~TMMVertex(void)\r
  46         {\r
  47         }\r
  48         TMMEdge::TMMEdge(void)\r
  49         {\r
  50         m_id = 0;\r
  51                 m_triangles[0] = m_triangles[1] = m_newFace = 0;\r
  52                 m_vertices[0] = m_vertices[1] = 0;\r
  53         }\r
  54         TMMEdge::~TMMEdge(void)\r
  55         {\r
  56         }\r
  57         TMMTriangle::TMMTriangle(void)\r
  58         {\r
  59         m_id = 0;\r
  60                 for(int i = 0; i < 3; i++)\r
  61                 {\r
  62                         m_edges[i] = 0;\r
  63                         m_vertices[0] = 0;\r
  64                 }\r
  65                 m_visible = false;\r
  66         }\r
  67         TMMTriangle::~TMMTriangle(void)\r
  68         {\r
  69         }\r
  70         TMMesh::TMMesh(void)\r
  71         {\r
  72                 m_barycenter = Vec3<Real>(0,0,0);\r
  73                 m_diag = 1;\r
  74         }\r
  75         TMMesh::~TMMesh(void)\r
  76         {\r
  77         }\r
  78 \r
  79         void TMMesh::Print() \r
  80         {\r
  81                 size_t nV = m_vertices.GetSize();\r
  82                 std::cout << "-----------------------------" << std::endl;\r
  83         std::cout << "vertices (" << nV << ")" << std::endl;\r
  84         for(size_t v = 0; v < nV; v++)\r
  85                 {\r
  86                         const TMMVertex & currentVertex = m_vertices.GetData();\r
  87                         std::cout  << currentVertex.m_id          << ", " \r
  88                                            << currentVertex.m_pos.X() << ", " \r
  89                                            << currentVertex.m_pos.Y() << ", "\r
  90                                            << currentVertex.m_pos.Z() << std::endl;\r
  91                         m_vertices.Next();\r
  92                 }\r
  93     \r
  94 \r
  95                 size_t nE = m_edges.GetSize();\r
  96                 std::cout << "edges (" << nE << ")" << std::endl;\r
  97                 for(size_t e = 0; e < nE; e++)\r
  98                 {\r
  99                         const TMMEdge & currentEdge = m_edges.GetData();\r
 100             const CircularListElement<TMMVertex> * v0 = currentEdge.m_vertices[0];\r
 101             const CircularListElement<TMMVertex> * v1 = currentEdge.m_vertices[1];\r
 102             const CircularListElement<TMMTriangle> * f0 = currentEdge.m_triangles[0];\r
 103             const CircularListElement<TMMTriangle> * f1 = currentEdge.m_triangles[1];\r
 104 \r
 105                         std::cout << "-> (" << v0->GetData().m_name << ", " << v1->GetData().m_name << ")" << std::endl; \r
 106             std::cout << "-> F0 (" << f0->GetData().m_vertices[0]->GetData().m_name << ", " \r
 107                                    << f0->GetData().m_vertices[1]->GetData().m_name << ", "\r
 108                                    << f0->GetData().m_vertices[2]->GetData().m_name <<")" << std::endl; \r
 109             std::cout << "-> F1 (" << f1->GetData().m_vertices[0]->GetData().m_name << ", " \r
 110                                    << f1->GetData().m_vertices[1]->GetData().m_name << ", "\r
 111                                    << f1->GetData().m_vertices[2]->GetData().m_name << ")" << std::endl;                         \r
 112                         m_edges.Next();\r
 113                 }\r
 114                 size_t nT = m_triangles.GetSize();\r
 115                 std::cout << "triangles (" << nT << ")" << std::endl;\r
 116                 for(size_t t = 0; t < nT; t++)\r
 117                 {\r
 118                         const TMMTriangle & currentTriangle = m_triangles.GetData();\r
 119             const CircularListElement<TMMVertex> * v0 = currentTriangle.m_vertices[0];\r
 120             const CircularListElement<TMMVertex> * v1 = currentTriangle.m_vertices[1];\r
 121             const CircularListElement<TMMVertex> * v2 = currentTriangle.m_vertices[2];\r
 122             const CircularListElement<TMMEdge> * e0 = currentTriangle.m_edges[0];\r
 123             const CircularListElement<TMMEdge> * e1 = currentTriangle.m_edges[1];\r
 124             const CircularListElement<TMMEdge> * e2 = currentTriangle.m_edges[2];\r
 125             \r
 126                         std::cout << "-> (" << v0->GetData().m_name << ", " << v1->GetData().m_name << ", "<< v2->GetData().m_name << ")" << std::endl; \r
 127          \r
 128             std::cout << "-> E0 (" << e0->GetData().m_vertices[0]->GetData().m_name << ", " \r
 129                                    << e0->GetData().m_vertices[1]->GetData().m_name << ")" << std::endl; \r
 130             std::cout << "-> E1 (" << e1->GetData().m_vertices[0]->GetData().m_name << ", " \r
 131                                    << e1->GetData().m_vertices[1]->GetData().m_name << ")" << std::endl;\r
 132             std::cout << "-> E2 (" << e2->GetData().m_vertices[0]->GetData().m_name << ", " \r
 133                                    << e2->GetData().m_vertices[1]->GetData().m_name << ")" << std::endl;   \r
 134                         m_triangles.Next();\r
 135                 }   \r
 136         }\r
 137     bool TMMesh::Save(const char *fileName)\r
 138     {\r
 139         std::ofstream fout(fileName);\r
 140         std::cout << "Saving " <<  fileName << std::endl;\r
 141                 if (SaveVRML2(fout))\r
 142                 {\r
 143            fout.close();\r
 144                    return true;\r
 145                 }\r
 146         return false;\r
 147     }\r
 148     bool TMMesh::SaveVRML2(std::ofstream &fout)\r
 149     {\r
 150         return SaveVRML2(fout, Material());\r
 151     }\r
 152     bool TMMesh::SaveVRML2(std::ofstream &fout, const Material & material)\r
 153     {\r
 154         if (fout.is_open()) \r
 155         {\r
 156             size_t nV = m_vertices.GetSize();\r
 157             size_t nT = m_triangles.GetSize();            \r
 158             fout <<"#VRML V2.0 utf8" << std::endl;              \r
 159             fout <<"" << std::endl;\r
 160             fout <<"# Vertices: " << nV << std::endl;           \r
 161             fout <<"# Triangles: " << nT << std::endl;          \r
 162             fout <<"" << std::endl;\r
 163             fout <<"Group {" << std::endl;\r
 164             fout <<"    children [" << std::endl;\r
 165             fout <<"            Shape {" << std::endl;\r
 166             fout <<"                    appearance Appearance {" << std::endl;\r
 167             fout <<"                            material Material {" << std::endl;\r
 168             fout <<"                                    diffuseColor "      << material.m_diffuseColor.X()      << " " \r
 169                                                             << material.m_diffuseColor.Y()      << " "\r
 170                                                             << material.m_diffuseColor.Z()      << std::endl;  \r
 171             fout <<"                                    ambientIntensity "  << material.m_ambientIntensity      << std::endl;\r
 172             fout <<"                                    specularColor "     << material.m_specularColor.X()     << " " \r
 173                                                             << material.m_specularColor.Y()     << " "\r
 174                                                             << material.m_specularColor.Z()     << std::endl; \r
 175             fout <<"                                    emissiveColor "     << material.m_emissiveColor.X()     << " " \r
 176                                                             << material.m_emissiveColor.Y()     << " "\r
 177                                                             << material.m_emissiveColor.Z()     << std::endl; \r
 178             fout <<"                                    shininess "         << material.m_shininess             << std::endl;\r
 179             fout <<"                                    transparency "      << material.m_transparency          << std::endl;\r
 180             fout <<"                            }" << std::endl;\r
 181             fout <<"                    }" << std::endl;\r
 182             fout <<"                    geometry IndexedFaceSet {" << std::endl;\r
 183             fout <<"                            ccw TRUE" << std::endl;\r
 184             fout <<"                            solid TRUE" << std::endl;\r
 185             fout <<"                            convex TRUE" << std::endl;\r
 186             if (GetNVertices() > 0) {\r
 187                 fout <<"                                coord DEF co Coordinate {" << std::endl;\r
 188                 fout <<"                                        point [" << std::endl;\r
 189                 for(size_t v = 0; v < nV; v++)\r
 190                 {\r
 191                     TMMVertex & currentVertex = m_vertices.GetData();\r
 192                     fout <<"                                            " << currentVertex.m_pos.X() << " " \r
 193                                                       << currentVertex.m_pos.Y() << " " \r
 194                                                       << currentVertex.m_pos.Z() << "," << std::endl;\r
 195                     currentVertex.m_id = v;\r
 196                     m_vertices.Next();\r
 197                 }\r
 198                 fout <<"                                        ]" << std::endl;\r
 199                 fout <<"                                }" << std::endl;\r
 200             }\r
 201             if (GetNTriangles() > 0) {\r
 202                 fout <<"                                coordIndex [ " << std::endl;\r
 203                 for(size_t f = 0; f < nT; f++)\r
 204                 {\r
 205                     TMMTriangle & currentTriangle = m_triangles.GetData();\r
 206                     fout <<"                                            " << currentTriangle.m_vertices[0]->GetData().m_id << ", " \r
 207                                                       << currentTriangle.m_vertices[1]->GetData().m_id << ", "                                                  \r
 208                                                       << currentTriangle.m_vertices[2]->GetData().m_id << ", -1," << std::endl;\r
 209                     m_triangles.Next();\r
 210                 }\r
 211                 fout <<"                                ]" << std::endl;\r
 212             }\r
 213             fout <<"                    }" << std::endl;\r
 214             fout <<"            }" << std::endl;\r
 215             fout <<"    ]" << std::endl;\r
 216             fout <<"}" << std::endl;    \r
 217         }\r
 218         return true;\r
 219     }\r
 220     void TMMesh::GetIFS(Vec3<Real> * const points, Vec3<long> * const triangles)\r
 221     {\r
 222         size_t nV = m_vertices.GetSize();\r
 223         size_t nT = m_triangles.GetSize(); \r
 224 \r
 225         for(size_t v = 0; v < nV; v++)\r
 226         {\r
 227             points[v] = m_vertices.GetData().m_pos;\r
 228             m_vertices.GetData().m_id = v;\r
 229             m_vertices.Next();\r
 230         }\r
 231         for(size_t f = 0; f < nT; f++)\r
 232         {\r
 233             TMMTriangle & currentTriangle = m_triangles.GetData();\r
 234             triangles[f].X() = static_cast<long>(currentTriangle.m_vertices[0]->GetData().m_id);\r
 235             triangles[f].Y() = static_cast<long>(currentTriangle.m_vertices[1]->GetData().m_id);\r
 236             triangles[f].Z() = static_cast<long>(currentTriangle.m_vertices[2]->GetData().m_id);\r
 237             m_triangles.Next();\r
 238         }\r
 239     }\r
 240         void TMMesh::Clear()\r
 241     {\r
 242                 m_vertices.Clear();\r
 243                 m_edges.Clear();\r
 244                 m_triangles.Clear();\r
 245         }\r
 246     void TMMesh::Copy(TMMesh & mesh)\r
 247     {\r
 248         Clear();\r
 249         // updating the id's\r
 250         size_t nV = mesh.m_vertices.GetSize();\r
 251         size_t nE = mesh. m_edges.GetSize();\r
 252         size_t nT = mesh.m_triangles.GetSize();\r
 253         for(size_t v = 0; v < nV; v++)\r
 254         {\r
 255             mesh.m_vertices.GetData().m_id = v;\r
 256             mesh.m_vertices.Next();            \r
 257         }\r
 258         for(size_t e = 0; e < nE; e++)\r
 259         {\r
 260             mesh.m_edges.GetData().m_id = e;\r
 261             mesh.m_edges.Next();\r
 262             \r
 263         }        \r
 264         for(size_t f = 0; f < nT; f++)\r
 265         {\r
 266             mesh.m_triangles.GetData().m_id = f;\r
 267             mesh.m_triangles.Next();\r
 268         }\r
 269         // copying data\r
 270         m_vertices  = mesh.m_vertices;\r
 271         m_edges     = mesh.m_edges;\r
 272         m_triangles = mesh.m_triangles;\r
 273  \r
 274         // generating mapping\r
 275         CircularListElement<TMMVertex> ** vertexMap     = new CircularListElement<TMMVertex> * [nV];\r
 276         CircularListElement<TMMEdge> ** edgeMap         = new CircularListElement<TMMEdge> * [nE];\r
 277         CircularListElement<TMMTriangle> ** triangleMap = new CircularListElement<TMMTriangle> * [nT];\r
 278         for(size_t v = 0; v < nV; v++)\r
 279         {\r
 280             vertexMap[v] = m_vertices.GetHead();\r
 281             m_vertices.Next();            \r
 282         }\r
 283         for(size_t e = 0; e < nE; e++)\r
 284         {\r
 285             edgeMap[e] = m_edges.GetHead();\r
 286             m_edges.Next();            \r
 287         }        \r
 288         for(size_t f = 0; f < nT; f++)\r
 289         {\r
 290             triangleMap[f] = m_triangles.GetHead();\r
 291             m_triangles.Next();\r
 292         }\r
 293         \r
 294         // updating pointers\r
 295         for(size_t v = 0; v < nV; v++)\r
 296         {\r
 297             if (vertexMap[v]->GetData().m_duplicate)\r
 298             {\r
 299                 vertexMap[v]->GetData().m_duplicate = edgeMap[vertexMap[v]->GetData().m_duplicate->GetData().m_id];\r
 300             }\r
 301         }\r
 302         for(size_t e = 0; e < nE; e++)\r
 303         {\r
 304             if (edgeMap[e]->GetData().m_newFace)\r
 305             {\r
 306                 edgeMap[e]->GetData().m_newFace = triangleMap[edgeMap[e]->GetData().m_newFace->GetData().m_id];\r
 307             }\r
 308                         if (nT > 0)\r
 309                         {\r
 310                                 for(int f = 0; f < 2; f++)\r
 311                                 {\r
 312                                         if (edgeMap[e]->GetData().m_triangles[f])\r
 313                                         {\r
 314                                                 edgeMap[e]->GetData().m_triangles[f] = triangleMap[edgeMap[e]->GetData().m_triangles[f]->GetData().m_id];\r
 315                                         }\r
 316                                 }            \r
 317                         }\r
 318             for(int v = 0; v < 2; v++)\r
 319             {\r
 320                 if (edgeMap[e]->GetData().m_vertices[v])\r
 321                 {\r
 322                     edgeMap[e]->GetData().m_vertices[v] = vertexMap[edgeMap[e]->GetData().m_vertices[v]->GetData().m_id];\r
 323                 }\r
 324             }\r
 325         }        \r
 326         for(size_t f = 0; f < nT; f++)\r
 327         {\r
 328                         if (nE > 0)\r
 329                         {\r
 330                                 for(int e = 0; e < 3; e++)\r
 331                                 {\r
 332                                         if (triangleMap[f]->GetData().m_edges[e])\r
 333                                         {\r
 334                                                 triangleMap[f]->GetData().m_edges[e] = edgeMap[triangleMap[f]->GetData().m_edges[e]->GetData().m_id];\r
 335                                         }\r
 336                                 }            \r
 337                         }\r
 338             for(int v = 0; v < 3; v++)\r
 339             {\r
 340                 if (triangleMap[f]->GetData().m_vertices[v])\r
 341                 {\r
 342                     triangleMap[f]->GetData().m_vertices[v] = vertexMap[triangleMap[f]->GetData().m_vertices[v]->GetData().m_id];\r
 343                 }\r
 344             }\r
 345         }\r
 346         delete [] vertexMap;\r
 347         delete [] edgeMap;\r
 348         delete [] triangleMap;\r
 349         \r
 350     }\r
 351         long  IntersectRayTriangle(const Vec3<double> & P0, const Vec3<double> & dir, \r
 352                                                            const Vec3<double> & V0, const Vec3<double> & V1, \r
 353                                                            const Vec3<double> & V2, double &t)\r
 354         {\r
 355                 Vec3<double> edge1, edge2, edge3;\r
 356                 double det, invDet;\r
 357                 edge1 = V1 - V2;\r
 358                 edge2 = V2 - V0;\r
 359                 Vec3<double> pvec = dir ^ edge2;\r
 360                 det = edge1 * pvec;\r
 361                 if (det == 0.0)\r
 362                         return 0;\r
 363                 invDet = 1.0/det;\r
 364                 Vec3<double> tvec = P0 - V0;\r
 365                 Vec3<double> qvec = tvec ^ edge1;\r
 366                 t = (edge2 * qvec) * invDet;\r
 367         if (t < 0.0)\r
 368         {\r
 369             return 0;\r
 370         }\r
 371                 edge3 = V0 - V1;\r
 372                 Vec3<double> I(P0 + t * dir);\r
 373                 Vec3<double> s0 = (I-V0) ^ edge3;\r
 374                 Vec3<double> s1 = (I-V1) ^ edge1;\r
 375                 Vec3<double> s2 = (I-V2) ^ edge2;\r
 376                 if (s0*s1 > -1e-9 && s2*s1 > -1e-9)\r
 377                 {\r
 378                         return 1;\r
 379                 }\r
 380                 return 0;\r
 381         }\r
 382 \r
 383     bool IntersectLineLine(const Vec3<double> & p1, const Vec3<double> & p2, \r
 384                           const Vec3<double> & p3, const Vec3<double> & p4,\r
 385                           Vec3<double> & pa, Vec3<double> & pb, \r
 386                           double & mua, double & mub)\r
 387     {\r
 388         Vec3<double> p13,p43,p21;\r
 389         double d1343,d4321,d1321,d4343,d2121;\r
 390         double numer,denom;\r
 391         \r
 392         p13.X() = p1.X() - p3.X();\r
 393         p13.Y() = p1.Y() - p3.Y();\r
 394         p13.Z() = p1.Z() - p3.Z();\r
 395         p43.X() = p4.X() - p3.X();\r
 396         p43.Y() = p4.Y() - p3.Y();\r
 397         p43.Z() = p4.Z() - p3.Z();\r
 398         if (p43.X()==0.0 && p43.Y()==0.0 && p43.Z()==0.0)\r
 399             return false;\r
 400         p21.X() = p2.X() - p1.X();\r
 401         p21.Y() = p2.Y() - p1.Y();\r
 402         p21.Z() = p2.Z() - p1.Z();\r
 403         if (p21.X()==0.0 && p21.Y()==0.0 && p21.Z()==0.0)\r
 404             return false;\r
 405         \r
 406         d1343 = p13.X() * p43.X() + p13.Y() * p43.Y() + p13.Z() * p43.Z();\r
 407         d4321 = p43.X() * p21.X() + p43.Y() * p21.Y() + p43.Z() * p21.Z();\r
 408         d1321 = p13.X() * p21.X() + p13.Y() * p21.Y() + p13.Z() * p21.Z();\r
 409         d4343 = p43.X() * p43.X() + p43.Y() * p43.Y() + p43.Z() * p43.Z();\r
 410         d2121 = p21.X() * p21.X() + p21.Y() * p21.Y() + p21.Z() * p21.Z();\r
 411         \r
 412         denom = d2121 * d4343 - d4321 * d4321;\r
 413         if (denom==0.0)\r
 414             return false;\r
 415         numer = d1343 * d4321 - d1321 * d4343;\r
 416         \r
 417         mua = numer / denom;\r
 418         mub = (d1343 + d4321 * (mua)) / d4343;\r
 419         \r
 420         pa.X() = p1.X() + mua * p21.X();\r
 421         pa.Y() = p1.Y() + mua * p21.Y();\r
 422         pa.Z() = p1.Z() + mua * p21.Z();\r
 423         pb.X() = p3.X() + mub * p43.X();\r
 424         pb.Y() = p3.Y() + mub * p43.Y();\r
 425         pb.Z() = p3.Z() + mub * p43.Z();\r
 426         \r
 427         return true;\r
 428     }\r
 429 \r
 430         long  IntersectRayTriangle2(const Vec3<double> & P0, const Vec3<double> & dir, \r
 431                                                            const Vec3<double> & V0, const Vec3<double> & V1, \r
 432                                                            const Vec3<double> & V2, double &r)\r
 433         {\r
 434                 Vec3<double> u, v, n;          // triangle vectors\r
 435                 Vec3<double> w0, w;          // ray vectors\r
 436                 double     a, b;             // params to calc ray-plane intersect\r
 437 \r
 438                 // get triangle edge vectors and plane normal\r
 439                 u = V1 - V0;\r
 440                 v = V2 - V0;\r
 441                 n = u ^ v;             // cross product\r
 442                 if (n.GetNorm() == 0.0)            // triangle is degenerate\r
 443                         return -1;                 // do not deal with this case\r
 444 \r
 445                 w0 = P0 - V0;\r
 446                 a = - n * w0;\r
 447                 b =   n * dir;\r
 448                 if (fabs(b) <= 0.0) {     // ray is parallel to triangle plane\r
 449                         if (a == 0.0)                // ray lies in triangle plane\r
 450                                 return 2;\r
 451                         else return 0;             // ray disjoint from plane\r
 452                 }\r
 453 \r
 454                 // get intersect point of ray with triangle plane\r
 455                 r = a / b;\r
 456                 if (r < 0.0)                   // ray goes away from triangle\r
 457                         return 0;                  // => no intersect\r
 458                 // for a segment, also test if (r > 1.0) => no intersect\r
 459 \r
 460                 Vec3<double> I = P0 + r * dir;           // intersect point of ray and plane\r
 461 \r
 462                 // is I inside T?\r
 463                 double uu, uv, vv, wu, wv, D;\r
 464                 uu = u * u;\r
 465                 uv = u * v;\r
 466                 vv = v * v;\r
 467                 w  = I - V0;\r
 468                 wu = w * u;\r
 469                 wv = w * v;\r
 470                 D = uv * uv - uu * vv;\r
 471 \r
 472                 // get and test parametric coords\r
 473                 double s, t;\r
 474                 s = (uv * wv - vv * wu) / D;\r
 475                 if (s < 0.0 || s > 1.0)        // I is outside T\r
 476                         return 0;\r
 477                 t = (uv * wu - uu * wv) / D;\r
 478                 if (t < 0.0 || (s + t) > 1.0)  // I is outside T\r
 479                         return 0;\r
 480                 return 1;                      // I is in T\r
 481         }\r
 482     \r
 483     \r
 484         bool TMMesh::CheckConsistancy()\r
 485     {\r
 486         size_t nE = m_edges.GetSize();\r
 487         size_t nT = m_triangles.GetSize();\r
 488         for(size_t e = 0; e < nE; e++)\r
 489         {\r
 490             for(int f = 0; f < 2; f++)\r
 491             {\r
 492                 if (!m_edges.GetHead()->GetData().m_triangles[f])\r
 493                 {\r
 494                     return false;\r
 495                 }\r
 496             }            \r
 497                         m_edges.Next();\r
 498         }        \r
 499 \r
 500         for(size_t f = 0; f < nT; f++)\r
 501         {\r
 502             for(int e = 0; e < 3; e++)\r
 503             {\r
 504                 int found = 0;\r
 505                 for(int k = 0; k < 2; k++)\r
 506                 {\r
 507                     if (m_triangles.GetHead()->GetData().m_edges[e]->GetData().m_triangles[k] == m_triangles.GetHead())\r
 508                     {\r
 509                         found++;\r
 510                     }\r
 511                 }\r
 512                 if (found != 1)\r
 513                 {\r
 514                     return false;\r
 515                 }\r
 516             }            \r
 517                         m_triangles.Next();\r
 518         }\r
 519 \r
 520                 return true;\r
 521     }\r
 522         bool TMMesh::Normalize()\r
 523     {\r
 524         size_t nV = m_vertices.GetSize();\r
 525                 if (nV == 0)\r
 526                 {\r
 527                         return false;\r
 528                 }\r
 529         m_barycenter = m_vertices.GetHead()->GetData().m_pos;\r
 530                 Vec3<Real> min = m_barycenter;\r
 531                 Vec3<Real> max = m_barycenter;\r
 532                 Real x, y, z;\r
 533         for(size_t v = 1; v < nV; v++)\r
 534         {\r
 535                         m_barycenter +=  m_vertices.GetHead()->GetData().m_pos;\r
 536             x = m_vertices.GetHead()->GetData().m_pos.X();\r
 537             y = m_vertices.GetHead()->GetData().m_pos.Y();\r
 538             z = m_vertices.GetHead()->GetData().m_pos.Z();\r
 539             if ( x < min.X()) min.X() = x;\r
 540                         else if ( x > max.X()) max.X() = x;\r
 541             if ( y < min.Y()) min.Y() = y;\r
 542                         else if ( y > max.Y()) max.Y() = y;\r
 543             if ( z < min.Z()) min.Z() = z;\r
 544                         else if ( z > max.Z()) max.Z() = z;\r
 545                         m_vertices.Next();\r
 546         }\r
 547                 m_barycenter /= static_cast<Real>(nV);\r
 548         m_diag = static_cast<Real>(0.001 * (max-min).GetNorm());\r
 549         const Real invDiag = static_cast<Real>(1.0 / m_diag);\r
 550                 if (m_diag != 0.0)\r
 551                 {\r
 552                 for(size_t v = 0; v < nV; v++)\r
 553                     {\r
 554                                 m_vertices.GetHead()->GetData().m_pos = (m_vertices.GetHead()->GetData().m_pos - m_barycenter) * invDiag;\r
 555                                 m_vertices.Next();\r
 556                     }\r
 557                 }\r
 558                 return true;\r
 559         }\r
 560         bool TMMesh::Denormalize()\r
 561         {\r
 562         size_t nV = m_vertices.GetSize();\r
 563                 if (nV == 0)\r
 564                 {\r
 565                         return false;\r
 566                 }\r
 567                 if (m_diag != 0.0)\r
 568                 {\r
 569                 for(size_t v = 0; v < nV; v++)\r
 570                     {\r
 571                                 m_vertices.GetHead()->GetData().m_pos = m_vertices.GetHead()->GetData().m_pos * m_diag + m_barycenter;\r
 572                                 m_vertices.Next();\r
 573                         }\r
 574                 }\r
 575                 return false;\r
 576     }\r
 577 }\r