← Back to branch summary

~ubuntu-branches/ubuntu/intrepid/gmsh/intrepid

« back to all changes in this revision

Viewing changes to Geo/ExtractContour.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Emmet Hikory
  • Date: 2007-05-07 10:01:37 UTC
  • mfrom: (1.2.4 upstream)
  • Revision ID: james.westby@ubuntu.com-20070507100137-6j0rzz1ucbn0m2jt
Tags: 2.0.7-1ubuntu1
* Merged with Debian unstable.  Remaining Ubuntu changes:
  - Add .desktop file
  - Add icon
* Added XSBC-Original-Maintainer
* Removed Application Category from gmsh.desktop
* Link against GLU (fixes FTBFS)

Show diffs side-by-side

added added

removed removed

Lines of Context:
Geo/ExtractContour.cpp
1
 
// $Id: ExtractContour.cpp,v 1.8 2006/01/06 00:34:24 geuzaine Exp $
2
 
//
3
 
// Copyright (C) 1997-2006 C. Geuzaine, J.-F. Remacle
4
 
//
5
 
// This program is free software; you can redistribute it and/or modify
6
 
// it under the terms of the GNU General Public License as published by
7
 
// the Free Software Foundation; either version 2 of the License, or
8
 
// (at your option) any later version.
9
 
//
10
 
// This program is distributed in the hope that it will be useful,
11
 
// but WITHOUT ANY WARRANTY; without even the implied warranty of
12
 
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13
 
// GNU General Public License for more details.
14
 
//
15
 
// You should have received a copy of the GNU General Public License
16
 
// along with this program; if not, write to the Free Software
17
 
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
18
 
// USA.
19
 
// 
20
 
// Please report all bugs and problems to <gmsh@geuz.org>.
21
 
 
22
 
#include "Gmsh.h"
23
 
#include "Geo.h"
24
 
#include "GeoUtils.h"
25
 
#include "CAD.h"
26
 
#include "Mesh.h"
27
 
#include "Numeric.h"
28
 
 
29
 
// Note: we use List_ISearchSeq so that the input lists don't get
30
 
// sorted: it's less efficient, but it allows us to do multi-level
31
 
// user-friendly "undo"s...
32
 
 
33
 
extern Mesh *THEM;
34
 
 
35
 
typedef struct{
36
 
  int n, a;
37
 
}nxa;
38
 
 
39
 
typedef struct{
40
 
  int n;
41
 
  List_T *l;
42
 
}lnk;
43
 
 
44
 
int complink(const void *a, const void *b)
45
 
{
46
 
  lnk *q, *w;
47
 
  q = (lnk *) a;
48
 
  w = (lnk *) b;
49
 
  return (q->n - w->n);
50
 
}
51
 
 
52
 
// Find all linked edges
53
 
 
54
 
void recurFindLinkedEdges(int ed, List_T * edges, Tree_T * points, Tree_T * links)
55
 
{
56
 
  lnk lk;
57
 
  nxa na;
58
 
  int ip[2];
59
 
  Curve *c = FindCurve(ed, THEM);
60
 
  if(!c){
61
 
    Msg(GERROR, "Unknown curve %d", ed);
62
 
    return;
63
 
  }
64
 
  
65
 
  ip[0] = c->beg->Num;
66
 
  ip[1] = c->end->Num;
67
 
 
68
 
  for(int l = 0; l < 2; l++) {
69
 
    lk.n = ip[l];
70
 
    if(!Tree_Search(points, &lk.n))
71
 
      Tree_Add(points, &lk.n);
72
 
    else
73
 
      Tree_Suppress(points, &lk.n);
74
 
    Tree_Query(links, &lk);
75
 
    if(List_Nbr(lk.l) == 2) {
76
 
      for(int i = 0; i < 2; i++) {
77
 
        List_Read(lk.l, i, &na);
78
 
        if(na.a != ed) {
79
 
          if(List_ISearchSeq(edges, &na.a, fcmp_absint) < 0){
80
 
            List_Add(edges, &na.a);
81
 
            recurFindLinkedEdges(na.a, edges, points, links);
82
 
          }
83
 
        }
84
 
      }
85
 
    }
86
 
  }
87
 
}
88
 
 
89
 
int createEdgeLinks(Tree_T *links)
90
 
{
91
 
  lnk li, *pli;
92
 
  nxa na;
93
 
  Curve *c;
94
 
 
95
 
  List_T *temp = Tree2List(THEM->Curves);
96
 
 
97
 
  for(int i = 0; i < List_Nbr(temp); i++) {
98
 
    List_Read(temp, i, &c);
99
 
    if(!c->beg || !c->end){
100
 
      List_Delete(temp);
101
 
      Msg(GERROR, "Cannot link curves with no begin or end points");
102
 
      return 0;
103
 
    }
104
 
    if(c->Num > 0) {
105
 
      na.a = c->Num;
106
 
      int ip[2];
107
 
      ip[0] = c->beg->Num;
108
 
      ip[1] = c->end->Num;
109
 
      for(int k = 0; k < 2; k++){
110
 
        li.n = ip[k];
111
 
        if((pli = (lnk *) Tree_PQuery(links, &li))) {
112
 
          List_Add(pli->l, &na);
113
 
        }
114
 
        else {
115
 
          li.l = List_Create(20, 1, sizeof(nxa));
116
 
          List_Add(li.l, &na);
117
 
          Tree_Add(links, &li);
118
 
        }
119
 
      }
120
 
    }
121
 
  }
122
 
  List_Delete(temp);
123
 
  return 1;
124
 
}
125
 
 
126
 
void orientAndSortEdges(List_T *edges, Tree_T *links)
127
 
{
128
 
  // this orients all the edges in a line loop in a consistent manner
129
 
  // (left- or right-oriented, depending on the orientation of the
130
 
  // first edge) *and* sorts them so that they form a path
131
 
  int num;
132
 
  lnk lk;
133
 
  nxa na;
134
 
 
135
 
  List_T *temp = List_Create(List_Nbr(edges), 1, sizeof(int));
136
 
  List_Copy(edges, temp);
137
 
  List_Reset(edges);
138
 
  
139
 
  List_Read(temp, 0, &num);
140
 
  List_Add(edges, &num);
141
 
  Curve *c0 = FindCurve(abs(num), THEM);
142
 
  if(!c0){
143
 
    Msg(GERROR, "Unknown curve %d", abs(num));
144
 
    return;
145
 
  }
146
 
 
147
 
  int sign = 1;
148
 
  while(List_Nbr(edges) < List_Nbr(temp)){
149
 
    if(sign > 0)
150
 
      lk.n = c0->end->Num;
151
 
    else
152
 
      lk.n = c0->beg->Num;
153
 
    Tree_Query(links, &lk);
154
 
    for(int j = 0; j < List_Nbr(lk.l); j++){
155
 
      List_Read(lk.l, j, &na);
156
 
      if(c0->Num != na.a && List_Search(temp, &na.a, fcmp_absint)){
157
 
        Curve *c1 = FindCurve(abs(na.a), THEM);
158
 
        if(!c1){
159
 
          Msg(GERROR, "Unknown curve %d", abs(na.a));
160
 
          return;
161
 
        }
162
 
        if(lk.n == c1->beg->Num){
163
 
          sign = 1;
164
 
          num = na.a;
165
 
        }
166
 
        else{
167
 
          sign = -1;
168
 
          num = -na.a;
169
 
        }
170
 
        List_Add(edges, &num);
171
 
        c0 = c1;
172
 
        break;
173
 
      }
174
 
    }
175
 
  }
176
 
  
177
 
  List_Delete(temp);
178
 
}
179
 
 
180
 
int allEdgesLinked(int ed, List_T * edges)
181
 
{
182
 
  Tree_T *links = Tree_Create(sizeof(lnk), complink);
183
 
  Tree_T *points = Tree_Create(sizeof(int), fcmp_int);
184
 
 
185
 
  if(!createEdgeLinks(links))
186
 
    return 0;
187
 
 
188
 
  // initialize point tree with all hanging points
189
 
  for(int i = 0; i < List_Nbr(edges); i++){
190
 
    int num;
191
 
    List_Read(edges, i, &num);
192
 
    Curve *c = FindCurve(abs(num), THEM);
193
 
    if(!c){
194
 
      Msg(GERROR, "Unknown curve %d", abs(num));
195
 
      return 0;
196
 
    }
197
 
    int ip[2];
198
 
    ip[0] = c->beg->Num;
199
 
    ip[1] = c->end->Num;
200
 
    for(int k = 0; k < 2; k++){
201
 
      if(!Tree_Search(points, &ip[k]))
202
 
        Tree_Add(points, &ip[k]);
203
 
      else
204
 
        Tree_Suppress(points, &ip[k]);
205
 
    }
206
 
  }
207
 
 
208
 
  if(List_ISearchSeq(edges, &ed, fcmp_absint) < 0){
209
 
    List_Add(edges, &ed);
210
 
    recurFindLinkedEdges(ed, edges, points, links);
211
 
  }
212
 
 
213
 
  int found = 0;
214
 
 
215
 
  if(!Tree_Nbr(points)){
216
 
    found = 1;
217
 
    // we can only orient things now since we allow to select
218
 
    // disconnected parts of the loop interactively
219
 
    orientAndSortEdges(edges, links);
220
 
  }
221
 
 
222
 
  Tree_Delete(links);
223
 
  Tree_Delete(points);
224
 
 
225
 
  return found;
226
 
}
227
 
 
228
 
// Find all linked faces
229
 
 
230
 
void recurFindLinkedFaces(int fac, List_T * faces, Tree_T * edges, Tree_T * links)
231
 
{
232
 
  lnk lk;
233
 
  nxa na;
234
 
  Curve *c;
235
 
  Surface *s = FindSurface(abs(fac), THEM);
236
 
  if(!s){
237
 
    Msg(GERROR, "Unknown surface %d", abs(fac));
238
 
    return;
239
 
  }
240
 
 
241
 
  for(int l = 0; l < List_Nbr(s->Generatrices); l++) {
242
 
    List_Read(s->Generatrices, l, &c);
243
 
    lk.n = abs(c->Num);
244
 
    if(!Tree_Search(edges, &lk.n))
245
 
      Tree_Add(edges, &lk.n);
246
 
    else
247
 
      Tree_Suppress(edges, &lk.n);
248
 
    Tree_Query(links, &lk);
249
 
    if(List_Nbr(lk.l) == 2) {
250
 
      for(int i = 0; i < 2; i++) {
251
 
        List_Read(lk.l, i, &na);
252
 
        if(na.a != fac) {
253
 
          if(List_ISearchSeq(faces, &na.a, fcmp_absint) < 0){
254
 
            List_Add(faces, &na.a);
255
 
            recurFindLinkedFaces(na.a, faces, edges, links);
256
 
          }
257
 
        }
258
 
      }
259
 
    }
260
 
  }
261
 
}
262
 
 
263
 
void createFaceLinks(Tree_T * links)
264
 
{
265
 
  lnk li, *pli;
266
 
  nxa na;
267
 
  Surface *s;
268
 
  Curve *c;
269
 
 
270
 
  List_T *temp = Tree2List(THEM->Surfaces);
271
 
 
272
 
  for(int i = 0; i < List_Nbr(temp); i++) {
273
 
    List_Read(temp, i, &s);
274
 
    if(s->Num > 0){
275
 
      na.a = s->Num;
276
 
      for(int k = 0; k < List_Nbr(s->Generatrices); k++) {
277
 
        List_Read(s->Generatrices, k, &c);
278
 
        li.n = abs(c->Num);
279
 
        if((pli = (lnk *) Tree_PQuery(links, &li))) {
280
 
          List_Add(pli->l, &na);
281
 
        }
282
 
        else {
283
 
          li.l = List_Create(20, 1, sizeof(nxa));
284
 
          List_Add(li.l, &na);
285
 
          Tree_Add(links, &li);
286
 
        }
287
 
      }
288
 
    }
289
 
  }
290
 
  List_Delete(temp);
291
 
}
292
 
 
293
 
void recurOrientFace(int face, List_T *faces, List_T *available, Tree_T *links)
294
 
{
295
 
  Surface *s = FindSurface(abs(face), THEM);
296
 
  if(!s){
297
 
    Msg(GERROR, "Unknown surface %d", abs(face));
298
 
    return;
299
 
  }
300
 
  int ori = sign(face);
301
 
 
302
 
  for(int i = 0; i < List_Nbr(s->Generatrices); i++){
303
 
    Curve *c;
304
 
    List_Read(s->Generatrices, i, &c);
305
 
    lnk lk;
306
 
    lk.n = abs(c->Num);
307
 
    Tree_Query(links, &lk);
308
 
    for(int j = 0; j < List_Nbr(lk.l); j++){
309
 
      nxa na;
310
 
      List_Read(lk.l, j, &na);
311
 
      int num = abs(na.a);
312
 
      if(num != abs(s->Num) && List_Search(available, &num, fcmp_absint) &&
313
 
         List_ISearchSeq(faces, &num, fcmp_absint) < 0){
314
 
        Surface *s2 = FindSurface(num, THEM);
315
 
        if(!s2){
316
 
          Msg(GERROR, "Unknown surface %d", num);
317
 
          return;
318
 
        }
319
 
        for(int k = 0; k < List_Nbr(s2->Generatrices); k++){
320
 
          Curve *c2;
321
 
          List_Read(s2->Generatrices, k, &c2);
322
 
          if(abs(c->Num) == abs(c2->Num)){
323
 
            if(c->Num * c2->Num > 0)
324
 
              num *= -ori;
325
 
            else
326
 
              num *= ori;
327
 
            List_Add(faces, &num);
328
 
            recurOrientFace(num, faces, available, links);
329
 
            break;
330
 
          }
331
 
        }
332
 
      }
333
 
    }
334
 
  }
335
 
}
336
 
 
337
 
void orientFaces(List_T *faces, Tree_T *links)
338
 
{
339
 
  // this orients all the faces in a surface loop in a consistent
340
 
  // manner (all normals pointing inside or outside--depending on the
341
 
  // orientation of the first face)
342
 
 
343
 
  List_T *temp = List_Create(List_Nbr(faces), 1, sizeof(int));
344
 
  List_Copy(faces, temp);
345
 
  List_Reset(faces);
346
 
 
347
 
  int num;
348
 
  List_Read(temp, 0, &num);
349
 
  List_Add(faces, &num);
350
 
  recurOrientFace(num, faces, temp, links);
351
 
 
352
 
  List_Delete(temp);
353
 
}
354
 
 
355
 
int allFacesLinked(int fac, List_T * faces)
356
 
{
357
 
  Tree_T *links = Tree_Create(sizeof(lnk), complink);
358
 
  Tree_T *edges = Tree_Create(sizeof(int), fcmp_int);
359
 
  
360
 
  createFaceLinks(links);
361
 
 
362
 
  // initialize edge tree with all boundary edges
363
 
  for(int i = 0; i < List_Nbr(faces); i++){
364
 
    int num;
365
 
    List_Read(faces, i, &num);
366
 
    Surface *s = FindSurface(abs(num), THEM);
367
 
    if(!s){
368
 
      Msg(GERROR, "Unknown surface %d", abs(num));
369
 
      return 0;
370
 
    }
371
 
    for(int k = 0; k < List_Nbr(s->Generatrices); k++) {
372
 
      Curve *c;
373
 
      List_Read(s->Generatrices, k, &c);
374
 
      int ic = abs(c->Num);
375
 
      if(!Tree_Search(edges, &ic))
376
 
        Tree_Add(edges, &ic);
377
 
      else
378
 
        Tree_Suppress(edges, &ic);
379
 
    }
380
 
  }
381
 
 
382
 
  if(List_ISearchSeq(faces, &fac, fcmp_absint) < 0){
383
 
    List_Add(faces, &fac);
384
 
    // Warning: this is correct ONLY if the surfaces are defined
385
 
    // correctly, i.e., if the surface hole boundaries are oriented
386
 
    // consistently with the surface exterior boundaries. There is
387
 
    // currently *nothing* in the code that checks this.
388
 
    recurFindLinkedFaces(fac, faces, edges, links);
389
 
  }
390
 
 
391
 
  int found = 0;
392
 
 
393
 
  if(!Tree_Nbr(edges)){
394
 
    found = 1;
395
 
    // we can only orient things now since we allow to select
396
 
    // disconnected parts of the loop interactively
397
 
    orientFaces(faces, links);
398
 
  }
399
 
 
400
 
  Tree_Delete(links);
401
 
  Tree_Delete(edges);
402
 
 
403
 
  return found;
404
 
}