0028824: Possibility to build OCCT 7.1.0 and above using Visual Studio 2008
[occt.git] / 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       myTriangles.Resize (1, nbNodes, 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   Standard_Integer i;
99   // the last node is not used because edges are stored at the lower node index
100   polyedge** edges = new polyedge*[nbNodes];
101   for (i = 0; i < nbNodes; i++) edges[i] = 0;
102
103
104   // loop on the triangles
105   Standard_Integer j,k,n[3],n1,n2;
106   const Poly_Array1OfTriangle& triangles = myTriangulation->Triangles();
107
108   for (i = 1; i <= nbTriangles; i++) {
109
110     // get the nodes
111     triangles(i).Get(n[0],n[1],n[2]);
112
113     // Update the myTriangles array
114     myTriangles(n[0]) = i;
115     myTriangles(n[1]) = i;
116     myTriangles(n[2]) = i;
117
118     // update the edge lists
119     for (j = 0; j < 3; j++) {
120       k = (j+1) % 3;  // the following node of the edge
121       if (n[j] <= n[k]) {
122         n1 = n[j];
123         n2 = n[k];
124       }
125       else {
126         n1 = n[k];
127         n2 = n[j];
128       }
129
130       // edge from n1 to n2 with n1 < n2
131       // insert in the list of n1
132
133       polyedge* ced = edges[n1];
134       while (ced != 0) {
135         // the edge already exists
136         if (ced->nd == n2)
137           break;
138         else
139           ced = ced->next;
140       }
141
142       if (ced == 0) {
143         // create the edge if not found
144         ced = new polyedge;
145         ced->next = edges[n1];
146         edges[n1] = ced;
147         ced->nd = n2;
148         ced->nt[0] = i;
149         ced->nn[0] = n[3-j-k];  // the third node
150         ced->nt[1] = 0;
151         ced->nn[1] = 0;
152       }
153       else {
154         // just mark the adjacency if found
155         ced->nt[1] = i;
156         ced->nn[1] = n[3-j-k];  // the third node
157       }
158     }
159   }
160
161
162   // now complete the myAdjacents array
163   
164   Standard_Integer index = 1;
165   for (i = 1; i <= nbTriangles; i++) {
166     
167     // get the nodes
168     triangles(i).Get(n[0],n[1],n[2]);
169
170     // fore each edge
171     for (j = 0; j < 3; j++) {
172       k = (j+1) % 3;  // the following node of the edge
173       if (n[j] <= n[k]) {
174         n1 = n[j];
175         n2 = n[k];
176       }
177       else {
178         n1 = n[k];
179         n2 = n[j];
180       }
181
182       // edge from n1 to n2 with n1 < n2
183       // find in the list of n1
184
185       polyedge* ced = edges[n1];
186       while (ced->nd != n2)
187         ced = ced->next;
188
189       // Find the adjacent triangle
190       Standard_Integer l = 0;
191       if (ced->nt[0] == i) l = 1;
192       
193       myAdjacents(index)   = ced->nt[l];
194       myAdjacents(index+3) = ced->nn[l];
195       index++;
196     }
197     index += 3;
198   }
199
200   // destroy the edges array
201   for (i = 0; i < nbNodes; i++) {
202     polyedge* ced = edges[i];
203     while (ced != 0) {
204       polyedge* tmp = ced->next;
205       delete ced;
206       ced = tmp;
207     }
208   }
209   delete [] edges;
210 }
211
212 //=======================================================================
213 //function : Initialize
214 //purpose  : 
215 //=======================================================================
216
217 void Poly_Connect::Initialize(const Standard_Integer N)
218 {
219   mynode = N;
220   myfirst = Triangle(N);
221   mytr = myfirst;
222   mysense = Standard_True;
223   mymore = (myfirst != 0);
224   if (mymore)
225   {
226     Standard_Integer i, no[3];
227     const Poly_Array1OfTriangle& triangles = myTriangulation->Triangles();
228     triangles(myfirst).Get(no[0], no[1], no[2]);
229     for (i = 0; i < 3; i++)
230       if (no[i] == mynode) break;
231     myothernode = no[(i+2)%3];
232   }
233 }
234
235 //=======================================================================
236 //function : Next
237 //purpose  : 
238 //=======================================================================
239
240 void Poly_Connect::Next()
241 {
242   Standard_Integer i, j;
243   Standard_Integer n[3];
244   Standard_Integer t[3];
245   const Poly_Array1OfTriangle& triangles = myTriangulation->Triangles();
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         triangles(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     triangles(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         triangles(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 }