0030804: Foundation Classes - Poly_Connect crashes due to out-of-range array modification
[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 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 }