0031490: Foundation Classes, Poly_Connect - speed up temporary allocations
[occt.git] / src / Poly / Poly_Connect.cxx
CommitLineData
b311480e 1// Created on: 1995-03-06
2// Created by: Laurent PAINNOT
3// Copyright (c) 1995-1999 Matra Datavision
973c2be1 4// Copyright (c) 1999-2014 OPEN CASCADE SAS
b311480e 5//
973c2be1 6// This file is part of Open CASCADE Technology software library.
b311480e 7//
d5f74e42 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
973c2be1 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.
b311480e 13//
973c2be1 14// Alternatively, this file may be used under the terms of Open CASCADE
15// commercial license or contractual agreement.
7fd59977 16
42cf5bc1 17#include <Poly_Connect.hxx>
450c83ad 18
8f08e231 19#include <NCollection_IncAllocator.hxx>
42cf5bc1 20#include <Poly_Triangle.hxx>
21#include <Poly_Triangulation.hxx>
450c83ad 22
23// this structure records one of the edges starting from a node
24struct polyedge
25{
26 polyedge* next; // the next edge in the list
450c83ad 27 Standard_Integer nt[2]; // the two adjacent triangles
28 Standard_Integer nn[2]; // the two adjacent nodes
8f08e231 29 Standard_Integer nd; // the second node of the edge
450c83ad 30 DEFINE_STANDARD_ALLOC
31};
7fd59977 32
7fd59977 33//=======================================================================
34//function : Poly_Connect
450c83ad 35//purpose :
7fd59977 36//=======================================================================
450c83ad 37Poly_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//=======================================================================
52Poly_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}
7fd59977 65
450c83ad 66//=======================================================================
67//function : Load
68//purpose :
69//=======================================================================
70void Poly_Connect::Load (const Handle(Poly_Triangulation)& theTriangulation)
7fd59977 71{
450c83ad 72 myTriangulation = theTriangulation;
73 mytr = 0;
74 myfirst = 0;
75 mynode = 0;
76 myothernode = 0;
77 mysense = false;
78 mymore = false;
79
841aa8c4 80 const Standard_Integer aNbNodes = myTriangulation->NbNodes();
81 const Standard_Integer aNbTris = myTriangulation->NbTriangles();
450c83ad 82 {
841aa8c4 83 const Standard_Integer aNbAdjs = 6 * aNbTris;
84 if (myTriangles.Size() != aNbNodes)
450c83ad 85 {
841aa8c4 86 myTriangles.Resize (1, aNbNodes, Standard_False);
450c83ad 87 }
88 if (myAdjacents.Size() != aNbAdjs)
89 {
71c810df 90 myAdjacents.Resize (1, aNbAdjs, Standard_False);
450c83ad 91 }
92 }
93
7fd59977 94 myTriangles.Init(0);
95 myAdjacents.Init(0);
7fd59977 96
97 // We first build an array of the list of edges connected to the nodes
7fd59977 98 // create an array to store the edges starting from the vertices
841aa8c4 99 NCollection_Array1<polyedge*> anEdges (1, aNbNodes);
100 anEdges.Init (NULL);
8f08e231 101 // use incremental allocator for small allocations
102 Handle(NCollection_IncAllocator) anIncAlloc = new NCollection_IncAllocator();
7fd59977 103
104 // loop on the triangles
841aa8c4 105 NCollection_Vec3<Standard_Integer> aTriNodes;
106 NCollection_Vec2<Standard_Integer> anEdgeNodes;
107 for (Standard_Integer aTriIter = 1; aTriIter <= aNbTris; ++aTriIter)
108 {
7fd59977 109 // get the nodes
841aa8c4 110 myTriangulation->Triangle (aTriIter).Get (aTriNodes[0], aTriNodes[1], aTriNodes[2]);
7fd59977 111
112 // Update the myTriangles array
841aa8c4 113 myTriangles.SetValue (aTriNodes[0], aTriIter);
114 myTriangles.SetValue (aTriNodes[1], aTriIter);
115 myTriangles.SetValue (aTriNodes[2], aTriIter);
7fd59977 116
117 // update the edge lists
841aa8c4 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];
7fd59977 125 }
841aa8c4 126 else
127 {
128 anEdgeNodes[0] = aTriNodes[aNodeNext];
129 anEdgeNodes[1] = aTriNodes[aNodeInTri];
7fd59977 130 }
131
841aa8c4 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 }
7fd59977 145 }
146
841aa8c4 147 if (ced == NULL)
148 {
149 // create the edge if not found
8f08e231 150 ced = (polyedge* )anIncAlloc->Allocate (sizeof(polyedge));
841aa8c4 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;
7fd59977 158 }
159 }
160 }
161
7fd59977 162 // now complete the myAdjacents array
841aa8c4 163 Standard_Integer anAdjIndex = 1;
164 for (Standard_Integer aTriIter = 1; aTriIter <= aNbTris; ++aTriIter)
165 {
7fd59977 166 // get the nodes
841aa8c4 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];
7fd59977 177 }
841aa8c4 178 else
179 {
180 anEdgeNodes[0] = aTriNodes[aNodeNext];
181 anEdgeNodes[1] = aTriNodes[aNodeInTri];
7fd59977 182 }
183
841aa8c4 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 }
7fd59977 191
192 // Find the adjacent triangle
841aa8c4 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;
7fd59977 198 }
841aa8c4 199 anAdjIndex += 3;
7fd59977 200 }
201
8f08e231 202 // destroy the edges array - can be skipped when using NCollection_IncAllocator
203 /*for (Standard_Integer aNodeIter = anEdges.Lower(); aNodeIter <= anEdges.Upper(); ++aNodeIter)
841aa8c4 204 {
205 for (polyedge* anEdgeIter = anEdges[aNodeIter]; anEdgeIter != NULL;)
206 {
207 polyedge* aTmp = anEdgeIter->next;
8f08e231 208 anIncAlloc->Free (anEdgeIter);
841aa8c4 209 anEdgeIter = aTmp;
7fd59977 210 }
8f08e231 211 }*/
7fd59977 212}
213
214//=======================================================================
7fd59977 215//function : Initialize
216//purpose :
217//=======================================================================
218
219void Poly_Connect::Initialize(const Standard_Integer N)
220{
221 mynode = N;
222 myfirst = Triangle(N);
223 mytr = myfirst;
7fd59977 224 mysense = Standard_True;
446e11f3
A
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 }
7fd59977 235}
236
237//=======================================================================
238//function : Next
239//purpose :
240//=======================================================================
241
242void Poly_Connect::Next()
243{
244 Standard_Integer i, j;
9dfd7287
RK
245 Standard_Integer n[3];
246 Standard_Integer t[3];
7fd59977 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}