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