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 nbNodes     = myTriangulation->NbNodes();
  80   const Standard_Integer nbTriangles = myTriangulation->NbTriangles();
  81   {
  82     const Standard_Integer aNbAdjs = 6 * nbTriangles;
  83     if (myTriangles.Size() != nbNodes)
  84     {
  85       TColStd_Array1OfInteger aTriArray (1, nbNodes);
  86       myTriangles.Move (std::move (aTriArray));
  87     }
  88     if (myAdjacents.Size() != aNbAdjs)
  89     {
  90       TColStd_Array1OfInteger anAdjArray (1, aNbAdjs);
  91       myAdjacents.Move (std::move (anAdjArray));
  92     }
  93   }
  94
  95   myTriangles.Init(0);
  96   myAdjacents.Init(0);
  97
  98   // We first build an array of the list of edges connected to the nodes
  99   // create an array to store the edges starting from the vertices
 100   Standard_Integer i;
 101   // the last node is not used because edges are stored at the lower node index
 102   polyedge** edges = new polyedge*[nbNodes];
 103   for (i = 0; i < nbNodes; i++) edges[i] = 0;
 104
 105
 106   // loop on the triangles
 107   Standard_Integer j,k,n[3],n1,n2;
 108   const Poly_Array1OfTriangle& triangles = myTriangulation->Triangles();
 109
 110   for (i = 1; i <= nbTriangles; i++) {
 111
 112     // get the nodes
 113     triangles(i).Get(n[0],n[1],n[2]);
 114
 115     // Update the myTriangles array
 116     myTriangles(n[0]) = i;
 117     myTriangles(n[1]) = i;
 118     myTriangles(n[2]) = i;
 119
 120     // update the edge lists
 121     for (j = 0; j < 3; j++) {
 122       k = (j+1) % 3;  // the following node of the edge
 123       if (n[j] <= n[k]) {
 124         n1 = n[j];
 125         n2 = n[k];
 126       }
 127       else {
 128         n1 = n[k];
 129         n2 = n[j];
 130       }
 131
 132       // edge from n1 to n2 with n1 < n2
 133       // insert in the list of n1
 134
 135       polyedge* ced = edges[n1];
 136       while (ced != 0) {
 137         // the edge already exists
 138         if (ced->nd == n2)
 139           break;
 140         else
 141           ced = ced->next;
 142       }
 143
 144       if (ced == 0) {
 145         // create the edge if not found
 146         ced = new polyedge;
 147         ced->next = edges[n1];
 148         edges[n1] = ced;
 149         ced->nd = n2;
 150         ced->nt[0] = i;
 151         ced->nn[0] = n[3-j-k];  // the third node
 152         ced->nt[1] = 0;
 153         ced->nn[1] = 0;
 154       }
 155       else {
 156         // just mark the adjacency if found
 157         ced->nt[1] = i;
 158         ced->nn[1] = n[3-j-k];  // the third node
 159       }
 160     }
 161   }
 162
 163
 164   // now complete the myAdjacents array
 165
 166   Standard_Integer index = 1;
 167   for (i = 1; i <= nbTriangles; i++) {
 168
 169     // get the nodes
 170     triangles(i).Get(n[0],n[1],n[2]);
 171
 172     // fore each edge
 173     for (j = 0; j < 3; j++) {
 174       k = (j+1) % 3;  // the following node of the edge
 175       if (n[j] <= n[k]) {
 176         n1 = n[j];
 177         n2 = n[k];
 178       }
 179       else {
 180         n1 = n[k];
 181         n2 = n[j];
 182       }
 183
 184       // edge from n1 to n2 with n1 < n2
 185       // find in the list of n1
 186
 187       polyedge* ced = edges[n1];
 188       while (ced->nd != n2)
 189         ced = ced->next;
 190
 191       // Find the adjacent triangle
 192       Standard_Integer l = 0;
 193       if (ced->nt[0] == i) l = 1;
 194
 195       myAdjacents(index)   = ced->nt[l];
 196       myAdjacents(index+3) = ced->nn[l];
 197       index++;
 198     }
 199     index += 3;
 200   }
 201
 202   // destroy the edges array
 203   for (i = 0; i < nbNodes; i++) {
 204     polyedge* ced = edges[i];
 205     while (ced != 0) {
 206       polyedge* tmp = ced->next;
 207       delete ced;
 208       ced = tmp;
 209     }
 210   }
 211   delete [] edges;
 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     const Poly_Array1OfTriangle& triangles = myTriangulation->Triangles();
 230     triangles(myfirst).Get(no[0], no[1], no[2]);
 231     for (i = 0; i < 3; i++)
 232       if (no[i] == mynode) break;
 233     myothernode = no[(i+2)%3];
 234   }
 235 }
 236
 237 //=======================================================================
 238 //function : Next
 239 //purpose  :
 240 //=======================================================================
 241
 242 void Poly_Connect::Next()
 243 {
 244   Standard_Integer i, j;
 245   Standard_Integer n[3];
 246   Standard_Integer t[3];
 247   const Poly_Array1OfTriangle& triangles = myTriangulation->Triangles();
 248   Triangles(mytr, t[0], t[1], t[2]);
 249   if (mysense) {
 250     for (i = 0; i < 3; i++) {
 251       if (t[i] != 0) {
 252         triangles(t[i]).Get(n[0], n[1], n[2]);
 253         for (j = 0; j < 3; j++) {
 254           if ((n[j] == mynode) && (n[(j+1)%3] == myothernode)) {
 255             mytr = t[i];
 256             myothernode = n[(j+2)%3];
 257             mymore = (mytr != myfirst);
 258             return;
 259           }
 260         }
 261       }
 262     }
 263     // sinon, depart vers la gauche.
 264     triangles(myfirst).Get(n[0], n[1], n[2]);
 265     for (i = 0; i < 3; i++)
 266       if (n[i] == mynode) break;
 267     myothernode = n[(i+1)%3];
 268     mysense = Standard_False;
 269     mytr = myfirst;
 270     Triangles(mytr, t[0], t[1], t[2]);
 271   }
 272   if (!mysense) {
 273     for (i = 0; i < 3; i++) {
 274       if (t[i] != 0) {
 275         triangles(t[i]).Get(n[0], n[1], n[2]);
 276         for (j = 0; j < 3; j++) {
 277           if ((n[j] == mynode) && (n[(j+2)%3] == myothernode)) {
 278             mytr = t[i];
 279             myothernode = n[(j+1)%3];
 280             mymore = Standard_True;
 281             return;
 282           }
 283         }
 284       }
 285     }
 286   }
 287   mymore = Standard_False;
 288 }