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