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