src/Poly/Poly_Connect.cxx

   1 // Created on: 1995-03-06
   2 // Created by: Laurent PAINNOT
   3 // Copyright (c) 1995-1999 Matra Datavision
   4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   5 //
   6 // This file is part of Open CASCADE Technology software library.
   7 //
   8 // This library is free software; you can redistribute it and/or modify it under
   9 // the terms of the GNU Lesser General Public License version 2.1 as published
  10 // by the Free Software Foundation, with special exception defined in the file
  11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  12 // distribution for complete text of the license and disclaimer of any warranty.
  13 //
  14 // Alternatively, this file may be used under the terms of Open CASCADE
  15 // commercial license or contractual agreement.
  16
  17 #include <Poly_Connect.hxx>
  18
  19 #include <NCollection_IncAllocator.hxx>
  20 #include <Poly_Triangle.hxx>
  21 #include <Poly_Triangulation.hxx>
  22
  23 // this structure records one of the edges starting from a node
  24 struct polyedge
  25 {
  26   polyedge* next;         // the next edge in the list
  27   Standard_Integer nt[2]; // the two adjacent triangles
  28   Standard_Integer nn[2]; // the two adjacent nodes
  29   Standard_Integer nd;    // the second node of the edge
  30   DEFINE_STANDARD_ALLOC
  31 };
  32
  33 //=======================================================================
  34 //function : Poly_Connect
  35 //purpose  :
  36 //=======================================================================
  37 Poly_Connect::Poly_Connect()
  38 : mytr    (0),
  39   myfirst (0),
  40   mynode  (0),
  41   myothernode (0),
  42   mysense (false),
  43   mymore  (false)
  44 {
  45   //
  46 }
  47
  48 //=======================================================================
  49 //function : Poly_Connect
  50 //purpose  :
  51 //=======================================================================
  52 Poly_Connect::Poly_Connect(const Handle(Poly_Triangulation)& theTriangulation)
  53 : myTriangulation (theTriangulation),
  54   myTriangles (1, theTriangulation->NbNodes()),
  55   myAdjacents (1, 6 * theTriangulation->NbTriangles()),
  56   mytr    (0),
  57   myfirst (0),
  58   mynode  (0),
  59   myothernode (0),
  60   mysense (false),
  61   mymore  (false)
  62 {
  63   Load (theTriangulation);
  64 }
  65
  66 //=======================================================================
  67 //function : Load
  68 //purpose  :
  69 //=======================================================================
  70 void Poly_Connect::Load (const Handle(Poly_Triangulation)& theTriangulation)
  71 {
  72   myTriangulation = theTriangulation;
  73   mytr = 0;
  74   myfirst = 0;
  75   mynode  = 0;
  76   myothernode = 0;
  77   mysense = false;
  78   mymore  = false;
  79
  80   const Standard_Integer aNbNodes = myTriangulation->NbNodes();
  81   const Standard_Integer aNbTris  = myTriangulation->NbTriangles();
  82   {
  83     const Standard_Integer aNbAdjs = 6 * aNbTris;
  84     if (myTriangles.Size() != aNbNodes)
  85     {
  86       myTriangles.Resize (1, aNbNodes, Standard_False);
  87     }
  88     if (myAdjacents.Size() != aNbAdjs)
  89     {
  90       myAdjacents.Resize (1, aNbAdjs, Standard_False);
  91     }
  92   }
  93
  94   myTriangles.Init(0);
  95   myAdjacents.Init(0);
  96
  97   // We first build an array of the list of edges connected to the nodes
  98   // create an array to store the edges starting from the vertices
  99   NCollection_Array1<polyedge*> anEdges (1, aNbNodes);
 100   anEdges.Init (NULL);
 101   // use incremental allocator for small allocations
 102   Handle(NCollection_IncAllocator) anIncAlloc = new NCollection_IncAllocator();
 103
 104   // loop on the triangles
 105   NCollection_Vec3<Standard_Integer> aTriNodes;
 106   NCollection_Vec2<Standard_Integer> anEdgeNodes;
 107   for (Standard_Integer aTriIter = 1; aTriIter <= aNbTris; ++aTriIter)
 108   {
 109     // get the nodes
 110     myTriangulation->Triangle (aTriIter).Get (aTriNodes[0], aTriNodes[1], aTriNodes[2]);
 111
 112     // Update the myTriangles array
 113     myTriangles.SetValue (aTriNodes[0], aTriIter);
 114     myTriangles.SetValue (aTriNodes[1], aTriIter);
 115     myTriangles.SetValue (aTriNodes[2], aTriIter);
 116
 117     // update the edge lists
 118     for (Standard_Integer aNodeInTri = 0; aNodeInTri < 3; ++aNodeInTri)
 119     {
 120       const Standard_Integer aNodeNext = (aNodeInTri + 1) % 3;  // the following node of the edge
 121       if (aTriNodes[aNodeInTri] < aTriNodes[aNodeNext])
 122       {
 123         anEdgeNodes[0] = aTriNodes[aNodeInTri];
 124         anEdgeNodes[1] = aTriNodes[aNodeNext];
 125       }
 126       else
 127       {
 128         anEdgeNodes[0] = aTriNodes[aNodeNext];
 129         anEdgeNodes[1] = aTriNodes[aNodeInTri];
 130       }
 131
 132       // edge from node 0 to node 1 with node 0 < node 1
 133       // insert in the list of node 0
 134       polyedge* ced = anEdges[anEdgeNodes[0]];
 135       for (; ced != NULL; ced = ced->next)
 136       {
 137         // the edge already exists
 138         if (ced->nd == anEdgeNodes[1])
 139         {
 140           // just mark the adjacency if found
 141           ced->nt[1] = aTriIter;
 142           ced->nn[1] = aTriNodes[3 - aNodeInTri - aNodeNext];  // the third node
 143           break;
 144         }
 145       }
 146
 147       if (ced == NULL)
 148       {
 149         // create the edge if not found
 150         ced = (polyedge* )anIncAlloc->Allocate (sizeof(polyedge));
 151         ced->next = anEdges[anEdgeNodes[0]];
 152         anEdges[anEdgeNodes[0]] = ced;
 153         ced->nd = anEdgeNodes[1];
 154         ced->nt[0] = aTriIter;
 155         ced->nn[0] = aTriNodes[3 - aNodeInTri - aNodeNext];  // the third node
 156         ced->nt[1] = 0;
 157         ced->nn[1] = 0;
 158       }
 159     }
 160   }
 161
 162   // now complete the myAdjacents array
 163   Standard_Integer anAdjIndex = 1;
 164   for (Standard_Integer aTriIter = 1; aTriIter <= aNbTris; ++aTriIter)
 165   {
 166     // get the nodes
 167     myTriangulation->Triangle (aTriIter).Get (aTriNodes[0], aTriNodes[1], aTriNodes[2]);
 168
 169     // for each edge in triangle
 170     for (Standard_Integer aNodeInTri = 0; aNodeInTri < 3; ++aNodeInTri)
 171     {
 172       const Standard_Integer aNodeNext = (aNodeInTri + 1) % 3;  // the following node of the edge
 173       if (aTriNodes[aNodeInTri] < aTriNodes[aNodeNext])
 174       {
 175         anEdgeNodes[0] = aTriNodes[aNodeInTri];
 176         anEdgeNodes[1] = aTriNodes[aNodeNext];
 177       }
 178       else
 179       {
 180         anEdgeNodes[0] = aTriNodes[aNodeNext];
 181         anEdgeNodes[1] = aTriNodes[aNodeInTri];
 182       }
 183
 184       // edge from node 0 to node 1 with node 0 < node 1
 185       // find in the list of node 0
 186       const polyedge* ced = anEdges[anEdgeNodes[0]];
 187       while (ced->nd != anEdgeNodes[1])
 188       {
 189         ced = ced->next;
 190       }
 191
 192       // Find the adjacent triangle
 193       const Standard_Integer l = ced->nt[0] == aTriIter ? 1 : 0;
 194
 195       myAdjacents.SetValue (anAdjIndex,     ced->nt[l]);
 196       myAdjacents.SetValue (anAdjIndex + 3, ced->nn[l]);
 197       ++anAdjIndex;
 198     }
 199     anAdjIndex += 3;
 200   }
 201
 202   // destroy the edges array - can be skipped when using NCollection_IncAllocator
 203   /*for (Standard_Integer aNodeIter = anEdges.Lower(); aNodeIter <= anEdges.Upper(); ++aNodeIter)
 204   {
 205     for (polyedge* anEdgeIter = anEdges[aNodeIter]; anEdgeIter != NULL;)
 206     {
 207       polyedge* aTmp = anEdgeIter->next;
 208       anIncAlloc->Free (anEdgeIter);
 209       anEdgeIter = aTmp;
 210     }
 211   }*/
 212 }
 213
 214 //=======================================================================
 215 //function : Initialize
 216 //purpose  :
 217 //=======================================================================
 218
 219 void Poly_Connect::Initialize(const Standard_Integer N)
 220 {
 221   mynode = N;
 222   myfirst = Triangle(N);
 223   mytr = myfirst;
 224   mysense = Standard_True;
 225   mymore = (myfirst != 0);
 226   if (mymore)
 227   {
 228     Standard_Integer i, no[3];
 229     myTriangulation->Triangle (myfirst).Get (no[0], no[1], no[2]);
 230     for (i = 0; i < 3; i++)
 231       if (no[i] == mynode) break;
 232     myothernode = no[(i+2)%3];
 233   }
 234 }
 235
 236 //=======================================================================
 237 //function : Next
 238 //purpose  :
 239 //=======================================================================
 240
 241 void Poly_Connect::Next()
 242 {
 243   Standard_Integer i, j;
 244   Standard_Integer n[3];
 245   Standard_Integer t[3];
 246   Triangles(mytr, t[0], t[1], t[2]);
 247   if (mysense) {
 248     for (i = 0; i < 3; i++) {
 249       if (t[i] != 0) {
 250         myTriangulation->Triangle (t[i]).Get (n[0], n[1], n[2]);
 251         for (j = 0; j < 3; j++) {
 252           if ((n[j] == mynode) && (n[(j+1)%3] == myothernode)) {
 253             mytr = t[i];
 254             myothernode = n[(j+2)%3];
 255             mymore = (mytr != myfirst);
 256             return;
 257           }
 258         }
 259       }
 260     }
 261     // sinon, depart vers la gauche.
 262     myTriangulation->Triangle (myfirst).Get (n[0], n[1], n[2]);
 263     for (i = 0; i < 3; i++)
 264       if (n[i] == mynode) break;
 265     myothernode = n[(i+1)%3];
 266     mysense = Standard_False;
 267     mytr = myfirst;
 268     Triangles(mytr, t[0], t[1], t[2]);
 269   }
 270   if (!mysense) {
 271     for (i = 0; i < 3; i++) {
 272       if (t[i] != 0) {
 273         myTriangulation->Triangle (t[i]).Get (n[0], n[1], n[2]);
 274         for (j = 0; j < 3; j++) {
 275           if ((n[j] == mynode) && (n[(j+2)%3] == myothernode)) {
 276             mytr = t[i];
 277             myothernode = n[(j+1)%3];
 278             mymore = Standard_True;
 279             return;
 280           }
 281         }
 282       }
 283     }
 284   }
 285   mymore = Standard_False;
 286 }