src/Poly/Poly_Connect.cxx

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