0031490: Foundation Classes, Poly_Connect - speed up temporary allocations
[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 <NCollection_IncAllocator.hxx>
20 #include <Poly_Triangle.hxx>
21 #include <Poly_Triangulation.hxx>
22
23 // this structure records one of the edges starting from a node
24 struct polyedge
25 {
26   polyedge* next;         // the next edge in the list
27   Standard_Integer nt[2]; // the two adjacent triangles
28   Standard_Integer nn[2]; // the two adjacent nodes
29   Standard_Integer nd;    // the second node of the edge
30   DEFINE_STANDARD_ALLOC
31 };
32
33 //=======================================================================
34 //function : Poly_Connect
35 //purpose  :
36 //=======================================================================
37 Poly_Connect::Poly_Connect()
38 : mytr    (0),
39   myfirst (0),
40   mynode  (0),
41   myothernode (0),
42   mysense (false),
43   mymore  (false)
44 {
45   //
46 }
47
48 //=======================================================================
49 //function : Poly_Connect
50 //purpose  :
51 //=======================================================================
52 Poly_Connect::Poly_Connect(const Handle(Poly_Triangulation)& theTriangulation)
53 : myTriangulation (theTriangulation),
54   myTriangles (1, theTriangulation->NbNodes()),
55   myAdjacents (1, 6 * theTriangulation->NbTriangles()),
56   mytr    (0),
57   myfirst (0),
58   mynode  (0),
59   myothernode (0),
60   mysense (false),
61   mymore  (false)
62 {
63   Load (theTriangulation);
64 }
65
66 //=======================================================================
67 //function : Load
68 //purpose  :
69 //=======================================================================
70 void Poly_Connect::Load (const Handle(Poly_Triangulation)& theTriangulation)
71 {
72   myTriangulation = theTriangulation;
73   mytr = 0;
74   myfirst = 0;
75   mynode  = 0;
76   myothernode = 0;
77   mysense = false;
78   mymore  = false;
79
80   const Standard_Integer aNbNodes = myTriangulation->NbNodes();
81   const Standard_Integer aNbTris  = myTriangulation->NbTriangles();
82   {
83     const Standard_Integer aNbAdjs = 6 * aNbTris;
84     if (myTriangles.Size() != aNbNodes)
85     {
86       myTriangles.Resize (1, aNbNodes, Standard_False);
87     }
88     if (myAdjacents.Size() != aNbAdjs)
89     {
90       myAdjacents.Resize (1, aNbAdjs, Standard_False);
91     }
92   }
93
94   myTriangles.Init(0);
95   myAdjacents.Init(0);
96
97   // We first build an array of the list of edges connected to the nodes
98   // create an array to store the edges starting from the vertices
99   NCollection_Array1<polyedge*> anEdges (1, aNbNodes);
100   anEdges.Init (NULL);
101   // use incremental allocator for small allocations
102   Handle(NCollection_IncAllocator) anIncAlloc = new NCollection_IncAllocator();
103
104   // loop on the triangles
105   NCollection_Vec3<Standard_Integer> aTriNodes;
106   NCollection_Vec2<Standard_Integer> anEdgeNodes;
107   for (Standard_Integer aTriIter = 1; aTriIter <= aNbTris; ++aTriIter)
108   {
109     // get the nodes
110     myTriangulation->Triangle (aTriIter).Get (aTriNodes[0], aTriNodes[1], aTriNodes[2]);
111
112     // Update the myTriangles array
113     myTriangles.SetValue (aTriNodes[0], aTriIter);
114     myTriangles.SetValue (aTriNodes[1], aTriIter);
115     myTriangles.SetValue (aTriNodes[2], aTriIter);
116
117     // update the edge lists
118     for (Standard_Integer aNodeInTri = 0; aNodeInTri < 3; ++aNodeInTri)
119     {
120       const Standard_Integer aNodeNext = (aNodeInTri + 1) % 3;  // the following node of the edge
121       if (aTriNodes[aNodeInTri] < aTriNodes[aNodeNext])
122       {
123         anEdgeNodes[0] = aTriNodes[aNodeInTri];
124         anEdgeNodes[1] = aTriNodes[aNodeNext];
125       }
126       else
127       {
128         anEdgeNodes[0] = aTriNodes[aNodeNext];
129         anEdgeNodes[1] = aTriNodes[aNodeInTri];
130       }
131
132       // edge from node 0 to node 1 with node 0 < node 1
133       // insert in the list of node 0
134       polyedge* ced = anEdges[anEdgeNodes[0]];
135       for (; ced != NULL; ced = ced->next)
136       {
137         // the edge already exists
138         if (ced->nd == anEdgeNodes[1])
139         {
140           // just mark the adjacency if found
141           ced->nt[1] = aTriIter;
142           ced->nn[1] = aTriNodes[3 - aNodeInTri - aNodeNext];  // the third node
143           break;
144         }
145       }
146
147       if (ced == NULL)
148       {
149         // create the edge if not found
150         ced = (polyedge* )anIncAlloc->Allocate (sizeof(polyedge));
151         ced->next = anEdges[anEdgeNodes[0]];
152         anEdges[anEdgeNodes[0]] = ced;
153         ced->nd = anEdgeNodes[1];
154         ced->nt[0] = aTriIter;
155         ced->nn[0] = aTriNodes[3 - aNodeInTri - aNodeNext];  // the third node
156         ced->nt[1] = 0;
157         ced->nn[1] = 0;
158       }
159     }
160   }
161
162   // now complete the myAdjacents array
163   Standard_Integer anAdjIndex = 1;
164   for (Standard_Integer aTriIter = 1; aTriIter <= aNbTris; ++aTriIter)
165   {
166     // get the nodes
167     myTriangulation->Triangle (aTriIter).Get (aTriNodes[0], aTriNodes[1], aTriNodes[2]);
168
169     // for each edge in triangle
170     for (Standard_Integer aNodeInTri = 0; aNodeInTri < 3; ++aNodeInTri)
171     {
172       const Standard_Integer aNodeNext = (aNodeInTri + 1) % 3;  // the following node of the edge
173       if (aTriNodes[aNodeInTri] < aTriNodes[aNodeNext])
174       {
175         anEdgeNodes[0] = aTriNodes[aNodeInTri];
176         anEdgeNodes[1] = aTriNodes[aNodeNext];
177       }
178       else
179       {
180         anEdgeNodes[0] = aTriNodes[aNodeNext];
181         anEdgeNodes[1] = aTriNodes[aNodeInTri];
182       }
183
184       // edge from node 0 to node 1 with node 0 < node 1
185       // find in the list of node 0
186       const polyedge* ced = anEdges[anEdgeNodes[0]];
187       while (ced->nd != anEdgeNodes[1])
188       {
189         ced = ced->next;
190       }
191
192       // Find the adjacent triangle
193       const Standard_Integer l = ced->nt[0] == aTriIter ? 1 : 0;
194
195       myAdjacents.SetValue (anAdjIndex,     ced->nt[l]);
196       myAdjacents.SetValue (anAdjIndex + 3, ced->nn[l]);
197       ++anAdjIndex;
198     }
199     anAdjIndex += 3;
200   }
201
202   // destroy the edges array - can be skipped when using NCollection_IncAllocator
203   /*for (Standard_Integer aNodeIter = anEdges.Lower(); aNodeIter <= anEdges.Upper(); ++aNodeIter)
204   {
205     for (polyedge* anEdgeIter = anEdges[aNodeIter]; anEdgeIter != NULL;)
206     {
207       polyedge* aTmp = anEdgeIter->next;
208       anIncAlloc->Free (anEdgeIter);
209       anEdgeIter = aTmp;
210     }
211   }*/
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 }