1 // Gmsh - Copyright (C) 1997-2021 C. Geuzaine, J.-F. Remacle
2 //
3 // See the LICENSE.txt file in the Gmsh root directory for license information.
4 // Please report all issues on https://gitlab.onelab.info/gmsh/gmsh/issues.
5
6 #include <stdlib.h>
7 #include "GmshMessage.h"
8 #include "MallocUtils.h"
9 #include "GModel.h"
10 #include "TreeUtils.h"
11 #include "ListUtils.h"
12
13 typedef struct {
14 int n, a;
15 } nxa;
16
17 typedef struct {
18 int n;
19 List_T *l;
20 } lnk;
21
freeLink(void * link)22 static void freeLink(void *link)
23 {
24 List_Delete(((lnk *)link)->l);
25 Free(link);
26 }
27
complink(const void * a,const void * b)28 static int complink(const void *a, const void *b)
29 {
30 lnk *q = (lnk *)a;
31 lnk *w = (lnk *)b;
32 return q->n - w->n;
33 }
34
35 // Find all linked edges (note that we use List_ISearchSeq so that the input
36 // lists don't get sorted: it's less efficient, but it allows us to do
37 // multi-level, user-friendly undos in the GUI)
38
recurFindLinkedEdges(int ed,List_T * edges,Tree_T * points,Tree_T * links)39 static void recurFindLinkedEdges(int ed, List_T *edges, Tree_T *points,
40 Tree_T *links)
41 {
42 GEdge *ge = GModel::current()->getEdgeByTag(ed);
43 if(!ge) {
44 Msg::Error("Unknown curve %d", ed);
45 return;
46 }
47 if(!ge->getBeginVertex() || !ge->getEndVertex()) { return; }
48
49 int ip[2];
50 ip[0] = ge->getBeginVertex()->tag();
51 ip[1] = ge->getEndVertex()->tag();
52
53 for(int l = 0; l < 2; l++) {
54 lnk lk;
55 lk.n = ip[l];
56 if(!Tree_Search(points, &lk.n))
57 Tree_Add(points, &lk.n);
58 else
59 Tree_Suppress(points, &lk.n);
60 Tree_Query(links, &lk);
61 if(List_Nbr(lk.l) == 2) {
62 for(int i = 0; i < 2; i++) {
63 nxa na;
64 List_Read(lk.l, i, &na);
65 if(na.a != ed) {
66 if(List_ISearchSeq(edges, &na.a, fcmp_absint) < 0) {
67 List_Add(edges, &na.a);
68 recurFindLinkedEdges(na.a, edges, points, links);
69 }
70 }
71 }
72 }
73 }
74 }
75
createEdgeLinks(Tree_T * links)76 static int createEdgeLinks(Tree_T *links)
77 {
78 GModel *m = GModel::current();
79 for(auto it = m->firstEdge(); it != m->lastEdge(); it++) {
80 GEdge *ge = *it;
81 if(!ge->getBeginVertex() || !ge->getEndVertex()) {
82 Msg::Error("Cannot link curve %d with no begin or end point", ge->tag());
83 return 0;
84 }
85 if(ge->tag() > 0) {
86 nxa na;
87 na.a = ge->tag();
88 int ip[2];
89 ip[0] = ge->getBeginVertex()->tag();
90 ip[1] = ge->getEndVertex()->tag();
91 for(int k = 0; k < 2; k++) {
92 lnk li, *pli;
93 li.n = ip[k];
94 if((pli = (lnk *)Tree_PQuery(links, &li))) { List_Add(pli->l, &na); }
95 else {
96 li.l = List_Create(20, 1, sizeof(nxa));
97 List_Add(li.l, &na);
98 Tree_Add(links, &li);
99 }
100 }
101 }
102 }
103 return 1;
104 }
105
orientAndSortEdges(List_T * edges,Tree_T * links)106 static void orientAndSortEdges(List_T *edges, Tree_T *links)
107 {
108 List_T *temp = List_Create(List_Nbr(edges), 1, sizeof(int));
109 List_Copy(edges, temp);
110 List_Reset(edges);
111
112 int num;
113 List_Read(temp, 0, &num);
114 List_Add(edges, &num);
115
116 GEdge *ge0 = GModel::current()->getEdgeByTag(abs(num));
117 if(!ge0) {
118 Msg::Error("Unknown curve %d", abs(num));
119 List_Delete(temp);
120 return;
121 }
122 if(!ge0->getBeginVertex() || !ge0->getEndVertex()) {
123 Msg::Error("Cannot orient curve %d with no begin or end point", ge0->tag());
124 return;
125 }
126
127 int sign = 1;
128 while(List_Nbr(edges) < List_Nbr(temp)) {
129 lnk lk;
130 if(sign > 0)
131 lk.n = ge0->getEndVertex()->tag();
132 else
133 lk.n = ge0->getBeginVertex()->tag();
134 Tree_Query(links, &lk);
135 for(int j = 0; j < List_Nbr(lk.l); j++) {
136 nxa na;
137 List_Read(lk.l, j, &na);
138 if(ge0->tag() != na.a && List_Search(temp, &na.a, fcmp_absint)) {
139 GEdge *ge1 = GModel::current()->getEdgeByTag(abs(na.a));
140 if(!ge1) {
141 Msg::Error("Unknown curve %d", abs(na.a));
142 List_Delete(temp);
143 return;
144 }
145 if(lk.n == ge1->getBeginVertex()->tag()) {
146 sign = 1;
147 num = na.a;
148 }
149 else {
150 sign = -1;
151 num = -na.a;
152 }
153 List_Add(edges, &num);
154 ge0 = ge1;
155 break;
156 }
157 }
158 }
159
160 List_Delete(temp);
161 }
162
allEdgesLinked(int ed,List_T * edges)163 int allEdgesLinked(int ed, List_T *edges)
164 {
165 Tree_T *links = Tree_Create(sizeof(lnk), complink);
166 Tree_T *points = Tree_Create(sizeof(int), fcmp_int);
167
168 if(!createEdgeLinks(links)) {
169 Tree_Delete(links, freeLink);
170 Tree_Delete(points);
171 return 0;
172 }
173
174 // initialize point tree with all hanging points
175 for(int i = 0; i < List_Nbr(edges); i++) {
176 int num;
177 List_Read(edges, i, &num);
178 GEdge *ge = GModel::current()->getEdgeByTag(abs(num));
179 if(!ge) {
180 Msg::Error("Unknown curve %d", abs(num));
181 Tree_Delete(links, freeLink);
182 Tree_Delete(points);
183 return 0;
184 }
185 if(!ge->getBeginVertex() || !ge->getEndVertex()) {
186 Msg::Error("Cannot link curve %d with no begin or end point", ge->tag());
187 return 0;
188 }
189 int ip[2];
190 ip[0] = ge->getBeginVertex()->tag();
191 ip[1] = ge->getEndVertex()->tag();
192 for(int k = 0; k < 2; k++) {
193 if(!Tree_Search(points, &ip[k]))
194 Tree_Add(points, &ip[k]);
195 else
196 Tree_Suppress(points, &ip[k]);
197 }
198 }
199
200 if(List_ISearchSeq(edges, &ed, fcmp_absint) < 0) {
201 List_Add(edges, &ed);
202 recurFindLinkedEdges(ed, edges, points, links);
203 }
204
205 int found = 0;
206
207 if(!Tree_Nbr(points)) {
208 found = 1;
209 // at this point we can orient all the edges in a curve loop in a consistent
210 // manner (left- or right-oriented, depending on the orientation of the
211 // first edge), and we can sort them so that they form a path (we can only
212 // do this now since we allow to select disconnected parts of the loop in
213 // the GUI)
214 orientAndSortEdges(edges, links);
215 }
216
217 Tree_Delete(links, freeLink);
218 Tree_Delete(points);
219
220 return found;
221 }
222
223 // Find all linked faces
224
recurFindLinkedFaces(int fac,List_T * faces,Tree_T * edges,Tree_T * links)225 static void recurFindLinkedFaces(int fac, List_T *faces, Tree_T *edges,
226 Tree_T *links)
227 {
228 GFace *gf = GModel::current()->getFaceByTag(abs(fac));
229 if(!gf) {
230 Msg::Error("Unknown surface %d", abs(fac));
231 return;
232 }
233
234 std::vector<GEdge *> const &l = gf->edges();
235 for(auto it = l.begin(); it != l.end(); it++) {
236 GEdge *ge = *it;
237 if(ge->degenerate(0)) continue;
238 lnk lk;
239 lk.n = std::abs(ge->tag());
240 if(!Tree_Search(edges, &lk.n))
241 Tree_Add(edges, &lk.n);
242 else
243 Tree_Suppress(edges, &lk.n);
244 Tree_Query(links, &lk);
245 if(List_Nbr(lk.l) == 2) {
246 for(int i = 0; i < 2; i++) {
247 nxa na;
248 List_Read(lk.l, i, &na);
249 if(na.a != fac) {
250 if(List_ISearchSeq(faces, &na.a, fcmp_absint) < 0) {
251 List_Add(faces, &na.a);
252 recurFindLinkedFaces(na.a, faces, edges, links);
253 }
254 }
255 }
256 }
257 }
258 }
259
createFaceLinks(Tree_T * links)260 static void createFaceLinks(Tree_T *links)
261 {
262 GModel *m = GModel::current();
263 for(auto it = m->firstFace(); it != m->lastFace(); it++) {
264 GFace *gf = *it;
265 if(gf->tag() > 0) {
266 nxa na;
267 na.a = gf->tag();
268 std::vector<GEdge *> const &l = gf->edges();
269 for(auto ite = l.begin(); ite != l.end(); ite++) {
270 GEdge *ge = *ite;
271 if(ge->degenerate(0)) continue;
272 lnk li, *pli;
273 li.n = std::abs(ge->tag());
274 if((pli = (lnk *)Tree_PQuery(links, &li))) { List_Add(pli->l, &na); }
275 else {
276 li.l = List_Create(20, 1, sizeof(nxa));
277 List_Add(li.l, &na);
278 Tree_Add(links, &li);
279 }
280 }
281 }
282 }
283 }
284
allFacesLinked(int fac,List_T * faces)285 int allFacesLinked(int fac, List_T *faces)
286 {
287 Tree_T *links = Tree_Create(sizeof(lnk), complink);
288 Tree_T *edges = Tree_Create(sizeof(int), fcmp_int);
289
290 createFaceLinks(links);
291
292 // initialize edge tree with all boundary edges
293 for(int i = 0; i < List_Nbr(faces); i++) {
294 int num;
295 List_Read(faces, i, &num);
296 GFace *gf = GModel::current()->getFaceByTag(abs(num));
297 if(!gf) {
298 Msg::Error("Unknown surface %d", abs(num));
299 Tree_Delete(links, freeLink);
300 Tree_Delete(edges);
301 return 0;
302 }
303 std::vector<GEdge *> const &l = gf->edges();
304 for(auto it = l.begin(); it != l.end(); it++) {
305 GEdge *ge = *it;
306 if(ge->degenerate(0)) continue;
307 int ic = std::abs(ge->tag());
308 if(!Tree_Search(edges, &ic))
309 Tree_Add(edges, &ic);
310 else
311 Tree_Suppress(edges, &ic);
312 }
313 }
314
315 if(List_ISearchSeq(faces, &fac, fcmp_absint) < 0) {
316 List_Add(faces, &fac);
317 // Warning: this is correct only if the surfaces are defined with correct
318 // orientations, i.e., if the hole boundaries are oriented consistently with
319 // the exterior boundaries. There is currently nothing in the code that
320 // checks this!
321 recurFindLinkedFaces(fac, faces, edges, links);
322 }
323
324 int found = 0;
325
326 if(!Tree_Nbr(edges)) {
327 found = 1;
328 // we could orient the faces here, but it's not really necessary...
329 }
330
331 Tree_Delete(links, freeLink);
332 Tree_Delete(edges);
333
334 return found;
335 }
336