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 <limits>
7 #include <sstream>
8 #include <stdlib.h>
9 #include <map>
10 #include "GmshMessage.h"
11 #include "GModel.h"
12 #include "GFace.h"
13 #include "GEdge.h"
14 #include "GVertex.h"
15 #include "GPoint.h"
16 #include "discreteEdge.h"
17 #include "discreteFace.h"
18 #include "MTriangle.h"
19 #include "MQuadrangle.h"
20 #include "MLine.h"
21 #include "MVertex.h"
22 #include "meshGEdge.h"
23 #include "meshGFace.h"
24 #include "meshGFaceBDS.h"
25 #include "meshGFaceDelaunayInsertion.h"
26 #include "meshGFaceBamg.h"
27 #include "meshGFaceOptimize.h"
28 #include "DivideAndConquer.h"
29 #include "BackgroundMesh.h"
30 #include "robustPredicates.h"
31 #include "Numeric.h"
32 #include "BDS.h"
33 #include "qualityMeasures.h"
34 #include "OS.h"
35 #include "MElementOctree.h"
36 #include "HighOrder.h"
37 #include "Context.h"
38 #include "boundaryLayersData.h"
39 #include "filterElements.h"
40 #include "meshGFaceBipartiteLabelling.h"
41 #include "meshTriangulation.h"
42
pointInsideParametricDomain(std::vector<SPoint2> & bnd,SPoint2 & p,SPoint2 & out,int & N)43 bool pointInsideParametricDomain(std::vector<SPoint2> &bnd, SPoint2 &p,
44 SPoint2 &out, int &N)
45 {
46 int count = 0;
47 for(size_t i = 0; i < bnd.size(); i += 2) {
48 SPoint2 p1 = bnd[i];
49 SPoint2 p2 = bnd[i + 1];
50 double a = robustPredicates::orient2d(p1, p2, p);
51 double b = robustPredicates::orient2d(p1, p2, out);
52 if(a * b < 0) {
53 a = robustPredicates::orient2d(p, out, p1);
54 b = robustPredicates::orient2d(p, out, p2);
55 if(a * b < 0) count++;
56 }
57 }
58 N = count;
59 if(count % 2 == 0) return false;
60 return true;
61 }
62
trueBoundary(GFace * gf,std::vector<SPoint2> & bnd,int debug)63 static void trueBoundary(GFace *gf, std::vector<SPoint2> &bnd, int debug)
64 {
65 FILE *view_t = nullptr;
66 if(debug) {
67 char name[245];
68 sprintf(name, "trueBoundary%d.pos", gf->tag());
69 view_t = Fopen(name, "w");
70 if(view_t) fprintf(view_t, "View \"True Boundary\"{\n");
71 }
72 std::vector<GEdge *> edg = gf->edges();
73 std::set<GEdge *> edges(edg.begin(), edg.end());
74
75 for(auto it = edges.begin(); it != edges.end(); ++it) {
76 GEdge *ge = *it;
77 Range<double> r = ge->parBoundsOnFace(gf);
78 SPoint2 p[300];
79 int NITER = ge->isSeam(gf) ? 2 : 1;
80 for(int i = 0; i < NITER; i++) {
81 int count = NITER == 2 ? 300 : 300;
82 for(int k = 0; k < count; k++) {
83 double t = (double)k / (count - 1);
84 double xi = r.low() + (r.high() - r.low()) * t;
85 p[k] = ge->reparamOnFace(gf, xi, i);
86 if(k > 0) {
87 if(view_t) {
88 fprintf(view_t, "SL(%g,%g,%g,%g,%g,%g){%d,%d};\n", p[k - 1].x(),
89 p[k - 1].y(), 0.0, p[k].x(), p[k].y(), 0.0,ge->tag(),ge->tag());
90 }
91 bnd.push_back(p[k - 1]);
92 bnd.push_back(p[k]);
93 }
94 }
95 }
96 }
97 if(view_t) {
98 fprintf(view_t, "};\n");
99 fclose(view_t);
100 }
101 }
102
computeElementShapes(GFace * gf,double & worst,double & avg,double & best,int & nT,int & greaterThan)103 static void computeElementShapes(GFace *gf, double &worst, double &avg,
104 double &best, int &nT, int &greaterThan)
105 {
106 worst = 1.e22;
107 avg = 0.0;
108 best = 0.0;
109 nT = 0;
110 greaterThan = 0;
111 for(std::size_t i = 0; i < gf->triangles.size(); i++) {
112 double q = qmTriangle::gamma(gf->triangles[i]);
113 if(q > .9) greaterThan++;
114 avg += q;
115 worst = std::min(worst, q);
116 best = std::max(best, q);
117 nT++;
118 }
119 avg /= nT;
120 }
121
122 class quadMeshRemoveHalfOfOneDMesh {
123 private:
124 GFace *_gf;
125 std::map<GEdge *, std::vector<MLine *> > _backup;
126 std::map<MEdge, MVertex *, MEdgeLessThan> _middle;
_subdivide()127 void _subdivide()
128 {
129 std::vector<MQuadrangle *> qnew;
130 std::map<MEdge, MVertex *, MEdgeLessThan> eds;
131 for(std::size_t i = 0; i < _gf->triangles.size(); i++) {
132 MVertex *v[3];
133 SPoint2 m[3];
134 for(int j = 0; j < 3; j++) {
135 MEdge E = _gf->triangles[i]->getEdge(j);
136 SPoint2 p1, p2;
137 reparamMeshEdgeOnFace(E.getVertex(0), E.getVertex(1), _gf, p1, p2);
138 auto it = _middle.find(E);
139 auto it2 = eds.find(E);
140 m[j] = p1;
141 if(it == _middle.end() && it2 == eds.end()) {
142 GPoint gp = _gf->point((p1 + p2) * 0.5);
143 double XX = 0.5 * (E.getVertex(0)->x() + E.getVertex(1)->x());
144 double YY = 0.5 * (E.getVertex(0)->y() + E.getVertex(1)->y());
145 double ZZ = 0.5 * (E.getVertex(0)->z() + E.getVertex(1)->z());
146 v[j] = new MFaceVertex(XX, YY, ZZ, _gf, gp.u(), gp.v());
147 _gf->mesh_vertices.push_back(v[j]);
148 eds[E] = v[j];
149 }
150 else if(it == _middle.end()) {
151 v[j] = it2->second;
152 }
153 else {
154 v[j] = it->second;
155 v[j]->onWhat()->mesh_vertices.push_back(v[j]);
156 if(!CTX::instance()->mesh.secondOrderLinear) {
157 // re-push middle vertex on the curve (this can of course lead to an
158 // invalid mesh)
159 double u = 0.;
160 if(v[j]->getParameter(0, u) && v[j]->onWhat()->dim() == 1) {
161 GEdge *ge = static_cast<GEdge *>(v[j]->onWhat());
162 GPoint p = ge->point(u);
163 v[j]->x() = p.x();
164 v[j]->y() = p.y();
165 v[j]->z() = p.z();
166 }
167 }
168 }
169 }
170 GPoint gp = _gf->point((m[0] + m[1] + m[2]) * (1. / 3.));
171 double XX = (v[0]->x() + v[1]->x() + v[2]->x()) * (1. / 3.);
172 double YY = (v[0]->y() + v[1]->y() + v[2]->y()) * (1. / 3.);
173 double ZZ = (v[0]->z() + v[1]->z() + v[2]->z()) * (1. / 3.);
174 MFaceVertex *vmid = new MFaceVertex(XX, YY, ZZ, _gf, gp.u(), gp.v());
175 _gf->mesh_vertices.push_back(vmid);
176 qnew.push_back(
177 new MQuadrangle(_gf->triangles[i]->getVertex(0), v[0], vmid, v[2]));
178 qnew.push_back(
179 new MQuadrangle(_gf->triangles[i]->getVertex(1), v[1], vmid, v[0]));
180 qnew.push_back(
181 new MQuadrangle(_gf->triangles[i]->getVertex(2), v[2], vmid, v[1]));
182 delete _gf->triangles[i];
183 }
184 _gf->triangles.clear();
185 for(std::size_t i = 0; i < _gf->quadrangles.size(); i++) {
186 MVertex *v[4];
187 SPoint2 m[4];
188 for(int j = 0; j < 4; j++) {
189 MEdge E = _gf->quadrangles[i]->getEdge(j);
190 SPoint2 p1, p2;
191 reparamMeshEdgeOnFace(E.getVertex(0), E.getVertex(1), _gf, p1, p2);
192 auto it = _middle.find(E);
193 auto it2 = eds.find(E);
194 m[j] = p1;
195 if(it == _middle.end() && it2 == eds.end()) {
196 GPoint gp = _gf->point((p1 + p2) * 0.5);
197 double XX = 0.5 * (E.getVertex(0)->x() + E.getVertex(1)->x());
198 double YY = 0.5 * (E.getVertex(0)->y() + E.getVertex(1)->y());
199 double ZZ = 0.5 * (E.getVertex(0)->z() + E.getVertex(1)->z());
200 v[j] = new MFaceVertex(XX, YY, ZZ, _gf, gp.u(), gp.v());
201 _gf->mesh_vertices.push_back(v[j]);
202 eds[E] = v[j];
203 }
204 else if(it == _middle.end()) {
205 v[j] = it2->second;
206 }
207 else {
208 v[j] = it->second;
209 v[j]->onWhat()->mesh_vertices.push_back(v[j]);
210 if(!CTX::instance()->mesh.secondOrderLinear) {
211 // re-push middle vertex on the curve (this can of course lead to an
212 // invalid mesh)
213 double u = 0.;
214 if(v[j]->getParameter(0, u) && v[j]->onWhat()->dim() == 1) {
215 GEdge *ge = static_cast<GEdge *>(v[j]->onWhat());
216 GPoint p = ge->point(u);
217 v[j]->x() = p.x();
218 v[j]->y() = p.y();
219 v[j]->z() = p.z();
220 }
221 }
222 }
223 }
224 GPoint gp = _gf->point((m[0] + m[1] + m[2] + m[3]) * 0.25);
225 // FIXME: not exactly correct, but that's the place where we want the
226 // point to reside
227 double XX = 0.25 * (v[0]->x() + v[1]->x() + v[2]->x() + v[3]->x());
228 double YY = 0.25 * (v[0]->y() + v[1]->y() + v[2]->y() + v[3]->y());
229 double ZZ = 0.25 * (v[0]->z() + v[1]->z() + v[2]->z() + v[3]->z());
230 MVertex *vmid = new MFaceVertex(XX, YY, ZZ, _gf, gp.u(), gp.v());
231 _gf->mesh_vertices.push_back(vmid);
232 qnew.push_back(
233 new MQuadrangle(_gf->quadrangles[i]->getVertex(0), v[0], vmid, v[3]));
234 qnew.push_back(
235 new MQuadrangle(_gf->quadrangles[i]->getVertex(1), v[1], vmid, v[0]));
236 qnew.push_back(
237 new MQuadrangle(_gf->quadrangles[i]->getVertex(2), v[2], vmid, v[1]));
238 qnew.push_back(
239 new MQuadrangle(_gf->quadrangles[i]->getVertex(3), v[3], vmid, v[2]));
240 delete _gf->quadrangles[i];
241 }
242 _gf->quadrangles = qnew;
243 }
_restore()244 void _restore()
245 {
246 std::vector<GEdge *> const &edges = _gf->edges();
247 auto ite = edges.begin();
248 while(ite != edges.end()) {
249 for(std::size_t i = 0; i < (*ite)->lines.size(); i++) {
250 delete(*ite)->lines[i];
251 }
252 (*ite)->lines = _backup[*ite];
253 ++ite;
254 }
255 }
256
257 public:
258 // remove one point every two and remember middle points
quadMeshRemoveHalfOfOneDMesh(GFace * gf,bool periodic)259 quadMeshRemoveHalfOfOneDMesh(GFace *gf, bool periodic) : _gf(gf)
260 {
261 // only do it if a full recombination has to (and can) be done
262 if(!CTX::instance()->mesh.recombineAll && !gf->meshAttributes.recombine)
263 return;
264 if(CTX::instance()->mesh.algoRecombine < 2 &&
265 CTX::instance()->mesh.algoRecombine != 4)
266 return;
267 if(gf->compound.size()) return;
268 if(periodic) {
269 Msg::Error("Full-quad recombination not ready yet for periodic surfaces");
270 return;
271 }
272 std::vector<GEdge *> const &edges = gf->edges();
273 auto ite = edges.begin();
274 while(ite != edges.end()) {
275 if((*ite)->meshAttributes.method == MESH_TRANSFINITE) {
276 Msg::Warning("Full-quad recombination only compatible with "
277 "transfinite meshes if those are performed first");
278 }
279 if(!(*ite)->isMeshDegenerated()) {
280 std::vector<MLine *> temp;
281 (*ite)->mesh_vertices.clear();
282 for(std::size_t i = 0; i < (*ite)->lines.size(); i += 2) {
283 if(i + 1 >= (*ite)->lines.size()) {
284 Msg::Error("1D mesh cannot be divided by 2");
285 break;
286 }
287 MVertex *v1 = (*ite)->lines[i]->getVertex(0);
288 MVertex *v2 = (*ite)->lines[i]->getVertex(1);
289 MVertex *v3 = (*ite)->lines[i + 1]->getVertex(1);
290 v2->x() = 0.5 * (v1->x() + v3->x());
291 v2->y() = 0.5 * (v1->y() + v3->y());
292 v2->z() = 0.5 * (v1->z() + v3->z());
293 temp.push_back(new MLine(v1, v3));
294 if(v1->onWhat() == *ite) (*ite)->mesh_vertices.push_back(v1);
295 _middle[MEdge(v1, v3)] = v2;
296 }
297 _backup[*ite] = (*ite)->lines;
298 (*ite)->lines = temp;
299 }
300 ++ite;
301 }
302 CTX::instance()->mesh.lcFactor *= 2.0;
303 }
finish()304 void finish()
305 {
306 if(_backup.empty()) return;
307 // recombine the elements on the half mesh
308 CTX::instance()->mesh.lcFactor /= 2.0;
309 bool blossom = (CTX::instance()->mesh.algoRecombine == 3);
310 int topo = CTX::instance()->mesh.recombineOptimizeTopology;
311 recombineIntoQuads(_gf, blossom, topo, true, 0.1);
312 _subdivide();
313 _restore();
314 recombineIntoQuads(_gf, blossom, topo, true, 1.e-3);
315 computeElementShapes(_gf, _gf->meshStatistics.worst_element_shape,
316 _gf->meshStatistics.average_element_shape,
317 _gf->meshStatistics.best_element_shape,
318 _gf->meshStatistics.nbTriangle,
319 _gf->meshStatistics.nbGoodQuality);
320 }
321 };
322
copyMesh(GFace * source,GFace * target)323 static void copyMesh(GFace *source, GFace *target)
324 {
325 std::map<MVertex *, MVertex *> vs2vt;
326
327 // add principal GVertex pairs
328
329 std::vector<GVertex *> s_vtcs = source->vertices();
330 s_vtcs.insert(s_vtcs.end(), source->embeddedVertices().begin(),
331 source->embeddedVertices().end());
332 for(auto it = source->embeddedEdges().begin();
333 it != source->embeddedEdges().end(); it++) {
334 if((*it)->getBeginVertex()) s_vtcs.push_back((*it)->getBeginVertex());
335 if((*it)->getEndVertex()) s_vtcs.push_back((*it)->getEndVertex());
336 }
337 std::vector<GVertex *> t_vtcs = target->vertices();
338 t_vtcs.insert(t_vtcs.end(), target->embeddedVertices().begin(),
339 target->embeddedVertices().end());
340 for(auto it = target->embeddedEdges().begin();
341 it != target->embeddedEdges().end(); it++) {
342 if((*it)->getBeginVertex()) t_vtcs.push_back((*it)->getBeginVertex());
343 if((*it)->getEndVertex()) t_vtcs.push_back((*it)->getEndVertex());
344 }
345
346 if(s_vtcs.size() != t_vtcs.size()) {
347 Msg::Info("Periodicity imposed on topologically incompatible surfaces"
348 "(%d vs %d points)",
349 s_vtcs.size(), t_vtcs.size());
350 }
351
352 std::set<GVertex *> checkVtcs(s_vtcs.begin(), s_vtcs.end());
353
354 for(auto tvIter = t_vtcs.begin(); tvIter != t_vtcs.end(); ++tvIter) {
355 GVertex *gvt = *tvIter;
356 auto gvsIter = target->vertexCounterparts.find(gvt);
357
358 if(gvsIter == target->vertexCounterparts.end()) {
359 Msg::Error("Periodic meshing of surface %d with surface %d: "
360 "point %d has no periodic counterpart",
361 target->tag(), source->tag(), gvt->tag());
362 }
363 else {
364 GVertex *gvs = gvsIter->second;
365 if(checkVtcs.find(gvs) == checkVtcs.end()) {
366 if(gvs)
367 Msg::Error(
368 "Periodic meshing of surface %d with surface %d: "
369 "point %d has periodic counterpart %d outside of source surface",
370 target->tag(), source->tag(), gvt->tag(), gvs->tag());
371
372 else
373 Msg::Error("Periodic meshing of surface %d with surface %d: "
374 "point %d has no periodic counterpart",
375 target->tag(), source->tag(), gvt->tag());
376 }
377 if(gvs) {
378 MVertex *vs = gvs->mesh_vertices[0];
379 MVertex *vt = gvt->mesh_vertices[0];
380 vs2vt[vs] = vt;
381 target->correspondingVertices[vt] = vs;
382 }
383 }
384 }
385
386 // add corresponding curve nodes assuming curves were correctly meshed already
387
388 std::vector<GEdge *> s_edges = source->edges();
389 s_edges.insert(s_edges.end(), source->embeddedEdges().begin(),
390 source->embeddedEdges().end());
391 std::vector<GEdge *> t_edges = target->edges();
392 t_edges.insert(t_edges.end(), target->embeddedEdges().begin(),
393 target->embeddedEdges().end());
394
395 std::set<GEdge *> checkEdges;
396 checkEdges.insert(s_edges.begin(), s_edges.end());
397
398 for(auto te_iter = t_edges.begin(); te_iter != t_edges.end(); ++te_iter) {
399 GEdge *get = *te_iter;
400
401 auto gesIter = target->edgeCounterparts.find(get);
402 if(gesIter == target->edgeCounterparts.end()) {
403 Msg::Error("Periodic meshing of surface %d with surface %d: "
404 "curve %d has no periodic counterpart",
405 target->tag(), source->tag(), get->tag());
406 }
407 else {
408 GEdge *ges = gesIter->second.first;
409 if(checkEdges.find(ges) == checkEdges.end()) {
410 Msg::Error("Periodic meshing of surface %d with surface %d: "
411 "curve %d has periodic counterpart %d",
412 target->tag(), source->tag(), get->tag(), ges->tag());
413 }
414 if(get->mesh_vertices.size() != ges->mesh_vertices.size()) {
415 Msg::Error("Periodic meshing of surface %d with surface %d: "
416 "curve %d has %d vertices, whereas correspondant %d has %d",
417 target->tag(), source->tag(), get->tag(),
418 get->mesh_vertices.size(), ges->tag(),
419 ges->mesh_vertices.size());
420 }
421 int orientation = gesIter->second.second;
422 int is = orientation == 1 ? 0 : get->mesh_vertices.size() - 1;
423 for(unsigned it = 0; it < get->mesh_vertices.size();
424 it++, is += orientation) {
425 MVertex *vs = ges->mesh_vertices[is];
426 MVertex *vt = get->mesh_vertices[it];
427 vs2vt[vs] = vt;
428 target->correspondingVertices[vt] = vs;
429 }
430 }
431 }
432
433 // transform interior nodes
434 std::vector<double> &tfo = target->affineTransform;
435
436 for(std::size_t i = 0; i < source->mesh_vertices.size(); i++) {
437 MVertex *vs = source->mesh_vertices[i];
438 SPoint2 XXX;
439
440 double ps[4] = {vs->x(), vs->y(), vs->z(), 1.};
441 double res[4] = {0., 0., 0., 0.};
442 int idx = 0;
443 for(int i = 0; i < 4; i++)
444 for(int j = 0; j < 4; j++) res[i] += tfo[idx++] * ps[j];
445
446 SPoint3 tp(res[0], res[1], res[2]);
447 XXX = target->parFromPoint(tp);
448
449 GPoint gp = target->point(XXX);
450 MVertex *vt =
451 new MFaceVertex(gp.x(), gp.y(), gp.z(), target, gp.u(), gp.v());
452 target->mesh_vertices.push_back(vt);
453 target->correspondingVertices[vt] = vs;
454 vs2vt[vs] = vt;
455 }
456
457 // create new elements
458 for(unsigned i = 0; i < source->triangles.size(); i++) {
459 MVertex *v1 = vs2vt[source->triangles[i]->getVertex(0)];
460 MVertex *v2 = vs2vt[source->triangles[i]->getVertex(1)];
461 MVertex *v3 = vs2vt[source->triangles[i]->getVertex(2)];
462 if(v1 && v2 && v3) {
463 target->triangles.push_back(new MTriangle(v1, v2, v3));
464 }
465 else {
466 Msg::Error("Could not find periodic counterpart of triangle nodes "
467 "%lu %lu %lu",
468 source->triangles[i]->getVertex(0)->getNum(),
469 source->triangles[i]->getVertex(1)->getNum(),
470 source->triangles[i]->getVertex(2)->getNum());
471 }
472 }
473
474 for(unsigned i = 0; i < source->quadrangles.size(); i++) {
475 MVertex *v1 = vs2vt[source->quadrangles[i]->getVertex(0)];
476 MVertex *v2 = vs2vt[source->quadrangles[i]->getVertex(1)];
477 MVertex *v3 = vs2vt[source->quadrangles[i]->getVertex(2)];
478 MVertex *v4 = vs2vt[source->quadrangles[i]->getVertex(3)];
479 if(v1 && v2 && v3 && v4) {
480 target->quadrangles.push_back(new MQuadrangle(v1, v2, v3, v4));
481 }
482 else {
483 Msg::Error("Could not find periodic counterpart of quadrangle nodes "
484 "%lu %lu %lu %lu",
485 source->quadrangles[i]->getVertex(0)->getNum(),
486 source->quadrangles[i]->getVertex(1)->getNum(),
487 source->quadrangles[i]->getVertex(2)->getNum(),
488 source->quadrangles[i]->getVertex(3)->getNum());
489 }
490 }
491 }
492
fourthPoint(double * p1,double * p2,double * p3,double * p4)493 void fourthPoint(double *p1, double *p2, double *p3, double *p4)
494 {
495 double c[3];
496 circumCenterXYZ(p1, p2, p3, c);
497 double vx[3] = {p2[0] - p1[0], p2[1] - p1[1], p2[2] - p1[2]};
498 double vy[3] = {p3[0] - p1[0], p3[1] - p1[1], p3[2] - p1[2]};
499 double vz[3];
500 prodve(vx, vy, vz);
501 norme(vz);
502 double R =
503 sqrt((p1[0] - c[0]) * (p1[0] - c[0]) + (p1[1] - c[1]) * (p1[1] - c[1]) +
504 (p1[2] - c[2]) * (p1[2] - c[2]));
505 p4[0] = c[0] + R * vz[0];
506 p4[1] = c[1] + R * vz[1];
507 p4[2] = c[2] + R * vz[2];
508 }
509
remeshUnrecoveredEdges(std::multimap<MVertex *,BDS_Point * > & recoverMultiMapInv,std::set<EdgeToRecover> & edgesNotRecovered,bool all)510 static void remeshUnrecoveredEdges(
511 std::multimap<MVertex *, BDS_Point *> &recoverMultiMapInv,
512 std::set<EdgeToRecover> &edgesNotRecovered, bool all)
513 {
514 deMeshGFace dem;
515
516 auto itr = edgesNotRecovered.begin();
517 for(; itr != edgesNotRecovered.end(); ++itr) {
518 std::vector<GFace *> l_faces = itr->ge->faces();
519 // un-mesh model faces adjacent to the model edge
520 for(auto it = l_faces.begin(); it != l_faces.end(); ++it) {
521 if((*it)->triangles.size() || (*it)->quadrangles.size()) {
522 (*it)->meshStatistics.status = GFace::PENDING;
523 dem(*it);
524 }
525 }
526
527 // add a new point in the middle of the intersecting segment
528 int p1 = itr->p1;
529 int p2 = itr->p2;
530 int N = itr->ge->lines.size();
531 GVertex *g1 = itr->ge->getBeginVertex();
532 GVertex *g2 = itr->ge->getEndVertex();
533 Range<double> bb = itr->ge->parBounds(0);
534
535 std::vector<MLine *> newLines;
536
537 for(int i = 0; i < N; i++) {
538 MVertex *v1 = itr->ge->lines[i]->getVertex(0);
539 MVertex *v2 = itr->ge->lines[i]->getVertex(1);
540
541 auto itp1 = recoverMultiMapInv.lower_bound(v1);
542 auto itp2 = recoverMultiMapInv.lower_bound(v2);
543
544 if(itp1 != recoverMultiMapInv.end() && itp2 != recoverMultiMapInv.end()) {
545 BDS_Point *pp1 = itp1->second;
546 BDS_Point *pp2 = itp2->second;
547 BDS_Point *pp1b = itp1->second;
548 BDS_Point *pp2b = itp2->second;
549 if(recoverMultiMapInv.count(v1) == 2) {
550 itp1++;
551 pp1b = itp1->second;
552 }
553 if(recoverMultiMapInv.count(v2) == 2) {
554 itp2++;
555 pp2b = itp2->second;
556 }
557
558 if((pp1->iD == p1 && pp2->iD == p2) ||
559 (pp1->iD == p2 && pp2->iD == p1) ||
560 (pp1b->iD == p1 && pp2b->iD == p2) ||
561 (pp1b->iD == p2 && pp2b->iD == p1) || all) {
562 double t1;
563 double lc1 = -1;
564 if(v1->onWhat() == g1)
565 t1 = bb.low();
566 else if(v1->onWhat() == g2)
567 t1 = bb.high();
568 else {
569 MEdgeVertex *ev1 = (MEdgeVertex *)v1;
570 lc1 = ev1->getLc();
571 v1->getParameter(0, t1);
572 }
573 double t2;
574 double lc2 = -1;
575 if(v2->onWhat() == g1)
576 t2 = bb.low();
577 else if(v2->onWhat() == g2)
578 t2 = bb.high();
579 else {
580 MEdgeVertex *ev2 = (MEdgeVertex *)v2;
581 lc2 = ev2->getLc();
582 v2->getParameter(0, t2);
583 }
584
585 // periodic
586 if(v1->onWhat() == g1 && v1->onWhat() == g2)
587 t1 =
588 fabs(t2 - bb.low()) < fabs(t2 - bb.high()) ? bb.low() : bb.high();
589 if(v2->onWhat() == g1 && v2->onWhat() == g2)
590 t2 =
591 fabs(t1 - bb.low()) < fabs(t1 - bb.high()) ? bb.low() : bb.high();
592
593 if(lc1 == -1)
594 lc1 = BGM_MeshSize(v1->onWhat(), 0, 0, v1->x(), v1->y(), v1->z());
595 if(lc2 == -1)
596 lc2 = BGM_MeshSize(v2->onWhat(), 0, 0, v2->x(), v2->y(), v2->z());
597 // should be better, i.e. equidistant
598 double t = 0.5 * (t2 + t1);
599 double lc = 0.5 * (lc1 + lc2);
600 GPoint V = itr->ge->point(t);
601 MEdgeVertex *newv =
602 new MEdgeVertex(V.x(), V.y(), V.z(), itr->ge, t, 0, lc);
603 newLines.push_back(new MLine(v1, newv));
604 newLines.push_back(new MLine(newv, v2));
605 delete itr->ge->lines[i];
606 }
607 else {
608 newLines.push_back(itr->ge->lines[i]);
609 }
610 }
611 else {
612 newLines.push_back(itr->ge->lines[i]);
613 }
614 }
615
616 itr->ge->lines = newLines;
617 itr->ge->mesh_vertices.clear();
618 N = itr->ge->lines.size();
619 for(int i = 1; i < N; i++) {
620 itr->ge->mesh_vertices.push_back(itr->ge->lines[i]->getVertex(0));
621 }
622 }
623 }
624
625 static void
remeshUnrecoveredEdges(std::map<MVertex *,BDS_Point * > & recoverMapInv,std::set<EdgeToRecover> & edgesNotRecovered)626 remeshUnrecoveredEdges(std::map<MVertex *, BDS_Point *> &recoverMapInv,
627 std::set<EdgeToRecover> &edgesNotRecovered)
628 {
629 deMeshGFace dem;
630
631 auto itr = edgesNotRecovered.begin();
632 for(; itr != edgesNotRecovered.end(); ++itr) {
633 std::vector<GFace *> l_faces = itr->ge->faces();
634 // un-mesh model faces adjacent to the model edge
635 for(auto it = l_faces.begin(); it != l_faces.end(); ++it) {
636 if((*it)->triangles.size() || (*it)->quadrangles.size()) {
637 (*it)->meshStatistics.status = GFace::PENDING;
638 dem(*it);
639 }
640 }
641
642 // add a new point in the middle of the intersecting segment
643 int p1 = itr->p1;
644 int p2 = itr->p2;
645 int N = itr->ge->lines.size();
646 GVertex *g1 = itr->ge->getBeginVertex();
647 GVertex *g2 = itr->ge->getEndVertex();
648 Range<double> bb = itr->ge->parBounds(0);
649
650 std::vector<MLine *> newLines;
651
652 for(int i = 0; i < N; i++) {
653 MVertex *v1 = itr->ge->lines[i]->getVertex(0);
654 MVertex *v2 = itr->ge->lines[i]->getVertex(1);
655 auto itp1 = recoverMapInv.find(v1);
656 auto itp2 = recoverMapInv.find(v2);
657 if(itp1 != recoverMapInv.end() && itp2 != recoverMapInv.end()) {
658 BDS_Point *pp1 = itp1->second;
659 BDS_Point *pp2 = itp2->second;
660 if((pp1->iD == p1 && pp2->iD == p2) ||
661 (pp1->iD == p2 && pp2->iD == p1)) {
662 double t1;
663 double lc1 = -1;
664 if(v1->onWhat() == g1)
665 t1 = bb.low();
666 else if(v1->onWhat() == g2)
667 t1 = bb.high();
668 else {
669 MEdgeVertex *ev1 = (MEdgeVertex *)v1;
670 lc1 = ev1->getLc();
671 v1->getParameter(0, t1);
672 }
673 double t2;
674 double lc2 = -1;
675 if(v2->onWhat() == g1)
676 t2 = bb.low();
677 else if(v2->onWhat() == g2)
678 t2 = bb.high();
679 else {
680 MEdgeVertex *ev2 = (MEdgeVertex *)v2;
681 lc2 = ev2->getLc();
682 v2->getParameter(0, t2);
683 }
684
685 // periodic
686 if(v1->onWhat() == g1 && v1->onWhat() == g2)
687 t1 =
688 fabs(t2 - bb.low()) < fabs(t2 - bb.high()) ? bb.low() : bb.high();
689 if(v2->onWhat() == g1 && v2->onWhat() == g2)
690 t2 =
691 fabs(t1 - bb.low()) < fabs(t1 - bb.high()) ? bb.low() : bb.high();
692
693 if(lc1 == -1)
694 lc1 = BGM_MeshSize(v1->onWhat(), 0, 0, v1->x(), v1->y(), v1->z());
695 if(lc2 == -1)
696 lc2 = BGM_MeshSize(v2->onWhat(), 0, 0, v2->x(), v2->y(), v2->z());
697 // should be better, i.e. equidistant
698 double t = 0.5 * (t2 + t1);
699 double lc = 0.5 * (lc1 + lc2);
700 GPoint V = itr->ge->point(t);
701 MEdgeVertex *newv =
702 new MEdgeVertex(V.x(), V.y(), V.z(), itr->ge, t, 0, lc);
703 newLines.push_back(new MLine(v1, newv));
704 newLines.push_back(new MLine(newv, v2));
705 delete itr->ge->lines[i];
706 }
707 else {
708 newLines.push_back(itr->ge->lines[i]);
709 }
710 }
711 else {
712 newLines.push_back(itr->ge->lines[i]);
713 }
714 }
715
716 itr->ge->lines = newLines;
717 itr->ge->mesh_vertices.clear();
718 N = itr->ge->lines.size();
719 for(int i = 1; i < N; i++) {
720 itr->ge->mesh_vertices.push_back(itr->ge->lines[i]->getVertex(0));
721 }
722 }
723 }
724
algoDelaunay2D(GFace * gf)725 static bool algoDelaunay2D(GFace *gf)
726 {
727 if(gf->getMeshingAlgo() == ALGO_2D_DELAUNAY ||
728 gf->getMeshingAlgo() == ALGO_2D_BAMG ||
729 gf->getMeshingAlgo() == ALGO_2D_FRONTAL ||
730 gf->getMeshingAlgo() == ALGO_2D_FRONTAL_QUAD ||
731 gf->getMeshingAlgo() == ALGO_2D_PACK_PRLGRMS ||
732 gf->getMeshingAlgo() == ALGO_2D_PACK_PRLGRMS_CSTR ||
733 gf->getMeshingAlgo() == ALGO_2D_BAMG)
734 return true;
735
736 if(gf->getMeshingAlgo() == ALGO_2D_AUTO && gf->geomType() == GEntity::Plane)
737 return true;
738
739 if(gf->getMeshingAlgo() == ALGO_2D_INITIAL_ONLY) return true;
740
741 return false;
742 }
743
recoverEdge(BDS_Mesh * m,GFace * gf,GEdge * ge,std::map<MVertex *,BDS_Point * > & recoverMapInv,std::set<EdgeToRecover> * e2r,std::set<EdgeToRecover> * notRecovered,int pass)744 static bool recoverEdge(BDS_Mesh *m, GFace *gf, GEdge *ge,
745 std::map<MVertex *, BDS_Point *> &recoverMapInv,
746 std::set<EdgeToRecover> *e2r,
747 std::set<EdgeToRecover> *notRecovered, int pass)
748 {
749 BDS_GeomEntity *g = nullptr;
750 if(pass == 2) {
751 m->add_geom(ge->tag(), 1);
752 g = m->get_geom(ge->tag(), 1);
753 }
754
755 bool _fatallyFailed;
756
757 for(std::size_t i = 0; i < ge->lines.size(); i++) {
758 MVertex *vstart = ge->lines[i]->getVertex(0);
759 MVertex *vend = ge->lines[i]->getVertex(1);
760 auto itpstart = recoverMapInv.find(vstart);
761 auto itpend = recoverMapInv.find(vend);
762 if(itpstart != recoverMapInv.end() && itpend != recoverMapInv.end()) {
763 BDS_Point *pstart = itpstart->second;
764 BDS_Point *pend = itpend->second;
765 if(pass == 1)
766 e2r->insert(EdgeToRecover(pstart->iD, pend->iD, ge));
767 else {
768 BDS_Edge *e = m->recover_edge(pstart->iD, pend->iD, _fatallyFailed, e2r,
769 notRecovered);
770 if(e)
771 e->g = g;
772 else {
773 if(_fatallyFailed) {
774 Msg::Error("Unable to recover the edge %d (%d/%d) on curve %d (on "
775 "surface %d)",
776 ge->lines[i]->getNum(), i + 1, ge->lines.size(),
777 ge->tag(), gf->tag());
778 if(Msg::GetVerbosity() == 99) {
779 outputScalarField(m->triangles, "wrongmesh.pos", 0);
780 outputScalarField(m->triangles, "wrongparam.pos", 1);
781 }
782 }
783 return !_fatallyFailed;
784 }
785 }
786 }
787 }
788
789 if(pass == 2 && ge->getBeginVertex()) {
790 MVertex *vstart = *(ge->getBeginVertex()->mesh_vertices.begin());
791 MVertex *vend = *(ge->getEndVertex()->mesh_vertices.begin());
792 auto itpstart = recoverMapInv.find(vstart);
793 auto itpend = recoverMapInv.find(vend);
794 if(itpstart != recoverMapInv.end() && itpend != recoverMapInv.end()) {
795 BDS_Point *pstart = itpstart->second;
796 BDS_Point *pend = itpend->second;
797 if(!pstart->g) {
798 m->add_geom(pstart->iD, 0);
799 BDS_GeomEntity *g0 = m->get_geom(pstart->iD, 0);
800 pstart->g = g0;
801 }
802 if(!pend->g) {
803 m->add_geom(pend->iD, 0);
804 BDS_GeomEntity *g0 = m->get_geom(pend->iD, 0);
805 pend->g = g0;
806 }
807 }
808 }
809
810 return true;
811 }
812
addOrRemove(MVertex * v1,MVertex * v2,std::set<MEdge,MEdgeLessThan> & bedges,std::set<MEdge,MEdgeLessThan> & removed)813 static void addOrRemove(MVertex *v1, MVertex *v2,
814 std::set<MEdge, MEdgeLessThan> &bedges,
815 std::set<MEdge, MEdgeLessThan> &removed)
816 {
817 MEdge e(v1, v2);
818 if(removed.find(e) != removed.end()) return;
819 auto it = bedges.find(e);
820 if(it == bedges.end())
821 bedges.insert(e);
822 else {
823 bedges.erase(it);
824 removed.insert(e);
825 }
826 }
827
modifyInitialMeshForBoundaryLayers(GFace * gf,std::vector<MQuadrangle * > & blQuads,std::vector<MTriangle * > & blTris,std::set<MVertex * > & verts,bool debug)828 static void modifyInitialMeshForBoundaryLayers(
829 GFace *gf, std::vector<MQuadrangle *> &blQuads,
830 std::vector<MTriangle *> &blTris, std::set<MVertex *> &verts, bool debug)
831 {
832 if(!buildAdditionalPoints2D(gf)) return;
833 BoundaryLayerColumns *_columns = gf->getColumns();
834
835 std::set<MEdge, MEdgeLessThan> bedges;
836 std::set<MEdge, MEdgeLessThan> removed;
837
838 std::vector<GEdge *> edges = gf->edges();
839 std::vector<GEdge *> embedded_edges = gf->getEmbeddedEdges();
840 edges.insert(edges.begin(), embedded_edges.begin(), embedded_edges.end());
841 auto ite = edges.begin();
842
843 FILE *ff2 = nullptr;
844 if(debug) ff2 = Fopen("tato.pos", "w");
845 if(ff2) fprintf(ff2, "View \" \"{\n");
846
847 std::vector<MLine *> _lines;
848
849 while(ite != edges.end()) {
850 for(std::size_t i = 0; i < (*ite)->lines.size(); i++) {
851 _lines.push_back((*ite)->lines[i]);
852 MVertex *v1 = (*ite)->lines[i]->getVertex(0);
853 MVertex *v2 = (*ite)->lines[i]->getVertex(1);
854 MEdge dv(v1, v2);
855 addOrRemove(v1, v2, bedges, removed);
856 for(std::size_t SIDE = 0; SIDE < _columns->_normals.count(dv); SIDE++) {
857 std::vector<MElement *> myCol;
858 edgeColumn ec = _columns->getColumns(v1, v2, SIDE);
859 const BoundaryLayerData &c1 = ec._c1;
860 const BoundaryLayerData &c2 = ec._c2;
861 int N = std::min(c1._column.size(), c2._column.size());
862 if(!N) continue;
863 for(int l = 0; l < N; ++l) {
864 MVertex *v11, *v12, *v21, *v22;
865 v21 = c1._column[l];
866 v22 = c2._column[l];
867 if(l == 0) {
868 v11 = v1;
869 v12 = v2;
870 }
871 else {
872 v11 = c1._column[l - 1];
873 v12 = c2._column[l - 1];
874 }
875 MQuadrangle *qq = new MQuadrangle(v11, v21, v22, v12);
876 qq->setPartition(l + 1);
877 myCol.push_back(qq);
878 blQuads.push_back(qq);
879 if(ff2)
880 fprintf(ff2,
881 "SQ(%g,%g,%g,%g,%g,%g,%g,%g,%g,%g,%g,%g){%d,%d,%d,%d};\n",
882 v11->x(), v11->y(), v11->z(), v12->x(), v12->y(), v12->z(),
883 v22->x(), v22->y(), v22->z(), v21->x(), v21->y(), v21->z(),
884 l + 1, l + 1, l + 1, l + 1);
885 }
886 if(c1._column.size() != c2._column.size()) {
887 MVertex *v11, *v12, *v;
888 v11 = c1._column[N - 1];
889 v12 = c2._column[N - 1];
890 v = c1._column.size() > c2._column.size() ? c1._column[N] :
891 c2._column[N];
892 MTriangle *qq = new MTriangle(v11, v12, v);
893 qq->setPartition(N + 1);
894 myCol.push_back(qq);
895 blTris.push_back(qq);
896 if(ff2)
897 fprintf(ff2, "ST(%g,%g,%g,%g,%g,%g,%g,%g,%g){%d,%d,%d};\n",
898 v11->x(), v11->y(), v11->z(), v12->x(), v12->y(), v12->z(),
899 v->x(), v->y(), v->z(), N + 1, N + 1, N + 1);
900 }
901 // int M = std::max(c1._column.size(),c2._column.size());
902 for(std::size_t l = 0; l < myCol.size(); l++)
903 _columns->_toFirst[myCol[l]] = myCol[0];
904 _columns->_elemColumns[myCol[0]] = myCol;
905 }
906 }
907 ++ite;
908 }
909
910 for(auto itf = _columns->beginf(); itf != _columns->endf(); ++itf) {
911 MVertex *v = itf->first;
912 int nbCol = _columns->getNbColumns(v);
913
914 for(int i = 0; i < nbCol - 1; i++) {
915 const BoundaryLayerData &c1 = _columns->getColumn(v, i);
916 const BoundaryLayerData &c2 = _columns->getColumn(v, i + 1);
917 int N = std::min(c1._column.size(), c2._column.size());
918 std::vector<MElement *> myCol;
919 for(int l = 0; l < N; ++l) {
920 MVertex *v11, *v12, *v21, *v22;
921 v21 = c1._column[l];
922 v22 = c2._column[l];
923 if(l == 0) {
924 v11 = v;
925 v12 = v;
926 }
927 else {
928 v11 = c1._column[l - 1];
929 v12 = c2._column[l - 1];
930 }
931 if(v11 != v12) {
932 MQuadrangle *qq = new MQuadrangle(v11, v12, v22, v21);
933 qq->setPartition(l + 1);
934 myCol.push_back(qq);
935 blQuads.push_back(qq);
936 if(ff2)
937 fprintf(ff2,
938 "SQ(%g,%g,%g,%g,%g,%g,%g,%g,%g,%g,%g,%g){%d,%d,%d,%d};\n",
939 v11->x(), v11->y(), v11->z(), v12->x(), v12->y(), v12->z(),
940 v22->x(), v22->y(), v22->z(), v21->x(), v21->y(), v21->z(),
941 l + 1, l + 1, l + 1, l + 1);
942 }
943 else {
944 MTriangle *qq = new MTriangle(v, v22, v21);
945 qq->setPartition(l + 1);
946 myCol.push_back(qq);
947 blTris.push_back(qq);
948 if(ff2)
949 fprintf(ff2, "ST(%g,%g,%g,%g,%g,%g,%g,%g,%g){%d,%d,%d};\n", v->x(),
950 v->y(), v->z(), v22->x(), v22->y(), v22->z(), v21->x(),
951 v21->y(), v21->z(), l + 1, l + 1, l + 1);
952 }
953 }
954 if(myCol.size()) {
955 for(std::size_t l = 0; l < myCol.size(); l++)
956 _columns->_toFirst[myCol[l]] = myCol[0];
957 _columns->_elemColumns[myCol[0]] = myCol;
958 }
959 }
960 }
961
962 if(ff2) {
963 fprintf(ff2, "};\n");
964 fclose(ff2);
965 }
966
967 filterOverlappingElements(_lines, blTris, blQuads, _columns->_elemColumns,
968 _columns->_toFirst);
969 for(std::size_t i = 0; i < blQuads.size(); i++) blQuads[i]->setPartition(0);
970 for(std::size_t i = 0; i < blTris.size(); i++) blTris[i]->setPartition(0);
971
972 for(std::size_t i = 0; i < blQuads.size(); i++) {
973 addOrRemove(blQuads[i]->getVertex(0), blQuads[i]->getVertex(1), bedges,
974 removed);
975 addOrRemove(blQuads[i]->getVertex(1), blQuads[i]->getVertex(2), bedges,
976 removed);
977 addOrRemove(blQuads[i]->getVertex(2), blQuads[i]->getVertex(3), bedges,
978 removed);
979 addOrRemove(blQuads[i]->getVertex(3), blQuads[i]->getVertex(0), bedges,
980 removed);
981 for(int j = 0; j < 4; j++)
982 if(blQuads[i]->getVertex(j)->onWhat() == gf)
983 verts.insert(blQuads[i]->getVertex(j));
984 }
985 for(std::size_t i = 0; i < blTris.size(); i++) {
986 addOrRemove(blTris[i]->getVertex(0), blTris[i]->getVertex(1), bedges,
987 removed);
988 addOrRemove(blTris[i]->getVertex(1), blTris[i]->getVertex(2), bedges,
989 removed);
990 addOrRemove(blTris[i]->getVertex(2), blTris[i]->getVertex(0), bedges,
991 removed);
992 for(int j = 0; j < 3; j++)
993 if(blTris[i]->getVertex(j)->onWhat() == gf)
994 verts.insert(blTris[i]->getVertex(j));
995 }
996
997 discreteEdge ne(gf->model(), 444444, nullptr,
998 (*edges.begin())->getEndVertex());
999 std::vector<GEdge *> hop;
1000 auto it = bedges.begin();
1001
1002 FILE *ff = nullptr;
1003 if(debug) ff = Fopen("toto.pos", "w");
1004 if(ff) fprintf(ff, "View \" \"{\n");
1005 for(; it != bedges.end(); ++it) {
1006 ne.lines.push_back(new MLine(it->getVertex(0), it->getVertex(1)));
1007 if(ff)
1008 fprintf(ff, "SL(%g,%g,%g,%g,%g,%g){1,1};\n", it->getVertex(0)->x(),
1009 it->getVertex(0)->y(), it->getVertex(0)->z(),
1010 it->getVertex(1)->x(), it->getVertex(1)->y(),
1011 it->getVertex(1)->z());
1012 }
1013 if(ff) {
1014 fprintf(ff, "};\n");
1015 fclose(ff);
1016 }
1017 hop.push_back(&ne);
1018
1019 deMeshGFace kil_;
1020 kil_(gf);
1021 meshGenerator(gf, 0, 0, true, false, &hop);
1022 }
1023
improved_translate(GFace * gf,MVertex * vertex,SVector3 & v1,SVector3 & v2)1024 static bool improved_translate(GFace *gf, MVertex *vertex, SVector3 &v1,
1025 SVector3 &v2)
1026 {
1027 double x, y;
1028 double angle;
1029 SPoint2 point;
1030 SVector3 s1, s2;
1031 SVector3 normal;
1032 SVector3 basis_u, basis_v;
1033 Pair<SVector3, SVector3> derivatives;
1034
1035 reparamMeshVertexOnFace(vertex, gf, point);
1036 x = point.x();
1037 y = point.y();
1038
1039 angle = backgroundMesh::current()->getAngle(x, y, 0.0);
1040 derivatives = gf->firstDer(point);
1041
1042 s1 = derivatives.first();
1043 s2 = derivatives.second();
1044 normal = crossprod(s1, s2);
1045
1046 basis_u = s1;
1047 basis_u.normalize();
1048 basis_v = crossprod(normal, basis_u);
1049 basis_v.normalize();
1050
1051 v1 = basis_u * cos(angle) + basis_v * sin(angle);
1052 v2 = crossprod(v1, normal);
1053 v2.normalize();
1054
1055 return 1;
1056 }
1057
directions_storage(GFace * gf)1058 static void directions_storage(GFace *gf)
1059 {
1060 std::set<MVertex *> vertices;
1061 for(std::size_t i = 0; i < gf->getNumMeshElements(); i++) {
1062 MElement *element = gf->getMeshElement(i);
1063 for(std::size_t j = 0; j < element->getNumVertices(); j++) {
1064 MVertex *vertex = element->getVertex(j);
1065 vertices.insert(vertex);
1066 }
1067 }
1068
1069 backgroundMesh::set(gf);
1070
1071 gf->storage1.clear();
1072 gf->storage2.clear();
1073 gf->storage3.clear();
1074 gf->storage4.clear();
1075
1076 for(auto it = vertices.begin(); it != vertices.end(); it++) {
1077 SPoint2 point;
1078 SVector3 v1;
1079 SVector3 v2;
1080 bool ok = improved_translate(gf, *it, v1, v2);
1081 if(ok) {
1082 gf->storage1.push_back(SPoint3((*it)->x(), (*it)->y(), (*it)->z()));
1083 gf->storage2.push_back(v1);
1084 gf->storage3.push_back(v2);
1085 reparamMeshVertexOnFace(*it, gf, point);
1086 gf->storage4.push_back(
1087 backgroundMesh::current()->operator()(point.x(), point.y(), 0.0));
1088 }
1089 }
1090
1091 backgroundMesh::unset();
1092 }
1093
1094 static void
BDS2GMSH(BDS_Mesh * m,GFace * gf,std::map<BDS_Point *,MVertex *,PointLessThan> & recoverMap)1095 BDS2GMSH(BDS_Mesh *m, GFace *gf,
1096 std::map<BDS_Point *, MVertex *, PointLessThan> &recoverMap)
1097 {
1098 auto itt = m->triangles.begin();
1099 while(itt != m->triangles.end()) {
1100 BDS_Face *t = *itt;
1101 if(!t->deleted) {
1102 BDS_Point *n[4];
1103 t->getNodes(n);
1104 MVertex *v[4] = {nullptr, nullptr, nullptr, nullptr};
1105 for(int i = 0; i < 4; i++) {
1106 if(!n[i]) continue;
1107 if(recoverMap.find(n[i]) == recoverMap.end()) {
1108 v[i] =
1109 new MFaceVertex(n[i]->X, n[i]->Y, n[i]->Z, gf, n[i]->u, n[i]->v);
1110 recoverMap[n[i]] = v[i];
1111 gf->mesh_vertices.push_back(v[i]);
1112 }
1113 else
1114 v[i] = recoverMap[n[i]];
1115 }
1116 if(!v[3]) {
1117 // when a singular point is present, degenerated triangles may be
1118 // created, for example on a sphere that contains one pole
1119 if(v[0] != v[1] && v[0] != v[2] && v[1] != v[2])
1120 gf->triangles.push_back(new MTriangle(v[0], v[1], v[2]));
1121 }
1122 else {
1123 gf->quadrangles.push_back(new MQuadrangle(v[0], v[1], v[2], v[3]));
1124 }
1125 }
1126 ++itt;
1127 }
1128 }
1129
_deleteUnusedVertices(GFace * gf)1130 static void _deleteUnusedVertices(GFace *gf)
1131 {
1132 std::set<MVertex *, MVertexPtrLessThan> allverts;
1133 for(std::size_t i = 0; i < gf->triangles.size(); i++) {
1134 for(int j = 0; j < 3; j++) {
1135 if(gf->triangles[i]->getVertex(j)->onWhat() == gf)
1136 allverts.insert(gf->triangles[i]->getVertex(j));
1137 }
1138 }
1139 for(std::size_t i = 0; i < gf->quadrangles.size(); i++) {
1140 for(int j = 0; j < 4; j++) {
1141 if(gf->quadrangles[i]->getVertex(j)->onWhat() == gf)
1142 allverts.insert(gf->quadrangles[i]->getVertex(j));
1143 }
1144 }
1145 for(std::size_t i = 0; i < gf->mesh_vertices.size(); i++) {
1146 if(allverts.find(gf->mesh_vertices[i]) == allverts.end())
1147 delete gf->mesh_vertices[i];
1148 }
1149 gf->mesh_vertices.clear();
1150 gf->mesh_vertices.insert(gf->mesh_vertices.end(), allverts.begin(),
1151 allverts.end());
1152 }
1153
1154 // Builds An initial triangular mesh that respects the boundaries of
1155 // the domain, including embedded points and surfaces
meshGenerator(GFace * gf,int RECUR_ITER,bool repairSelfIntersecting1dMesh,bool onlyInitialMesh,bool debug,std::vector<GEdge * > * replacement_edges)1156 bool meshGenerator(GFace *gf, int RECUR_ITER, bool repairSelfIntersecting1dMesh,
1157 bool onlyInitialMesh, bool debug,
1158 std::vector<GEdge *> *replacement_edges)
1159 {
1160 if(CTX::instance()->debugSurface > 0 &&
1161 gf->tag() != CTX::instance()->debugSurface) {
1162 gf->meshStatistics.status = GFace::DONE;
1163 return true;
1164 }
1165 if(CTX::instance()->debugSurface > 0) debug = true;
1166
1167 BDS_GeomEntity CLASS_F(1, 2);
1168 BDS_GeomEntity CLASS_EXTERIOR(1, 3);
1169 std::map<BDS_Point *, MVertex *, PointLessThan> recoverMap;
1170 std::map<MVertex *, BDS_Point *> recoverMapInv;
1171 std::vector<GEdge *> edges =
1172 replacement_edges ? *replacement_edges : gf->edges();
1173
1174 FILE *fdeb = nullptr;
1175 if(debug && RECUR_ITER == 0) {
1176 char name[245];
1177 sprintf(name, "surface%d-boundary-real.pos", gf->tag());
1178 fdeb = fopen(name, "w");
1179 fprintf(fdeb, "View \"\"{\n");
1180 }
1181
1182 // build a set with all points of the boundaries
1183 std::set<MVertex *, MVertexPtrLessThan> all_vertices, boundary;
1184 auto ite = edges.begin();
1185 while(ite != edges.end()) {
1186 if((*ite)->isSeam(gf)) {
1187 if(fdeb != nullptr) fclose(fdeb);
1188 return false;
1189 }
1190 if(!(*ite)->isMeshDegenerated()) {
1191 for(std::size_t i = 0; i < (*ite)->lines.size(); i++) {
1192 MVertex *v1 = (*ite)->lines[i]->getVertex(0);
1193 MVertex *v2 = (*ite)->lines[i]->getVertex(1);
1194
1195 if(fdeb) {
1196 fprintf(fdeb, "SL(%g,%g,%g,%g,%g,%g){%d,%d};\n", v1->x(), v1->y(),
1197 v1->z(), v2->x(), v2->y(), v2->z(), (*ite)->tag(),
1198 (*ite)->tag());
1199 }
1200
1201 all_vertices.insert(v1);
1202 all_vertices.insert(v2);
1203 if(boundary.find(v1) == boundary.end())
1204 boundary.insert(v1);
1205 else
1206 boundary.erase(v1);
1207 if(boundary.find(v2) == boundary.end())
1208 boundary.insert(v2);
1209 else
1210 boundary.erase(v2);
1211 }
1212 }
1213 else
1214 Msg::Debug("Degenerated mesh on edge %d", (*ite)->tag());
1215 ++ite;
1216 }
1217
1218 if(fdeb) {
1219 fprintf(fdeb, "};\n");
1220 fclose(fdeb);
1221 }
1222
1223 if(boundary.size()) {
1224 Msg::Error("The 1D mesh seems not to be forming a closed loop (%d boundary "
1225 "nodes are considered once)",
1226 boundary.size());
1227 for(auto it = boundary.begin(); it != boundary.end(); it++) {
1228 Msg::Debug("Remaining node %lu", (*it)->getNum());
1229 }
1230 gf->meshStatistics.status = GFace::FAILED;
1231 return false;
1232 }
1233
1234 std::vector<GEdge *> emb_edges = gf->getEmbeddedEdges();
1235 ite = emb_edges.begin();
1236 while(ite != emb_edges.end()) {
1237 if(!(*ite)->isMeshDegenerated()) {
1238 all_vertices.insert((*ite)->mesh_vertices.begin(),
1239 (*ite)->mesh_vertices.end());
1240 if((*ite)->getBeginVertex())
1241 all_vertices.insert((*ite)->getBeginVertex()->mesh_vertices.begin(),
1242 (*ite)->getBeginVertex()->mesh_vertices.end());
1243 if((*ite)->getEndVertex())
1244 all_vertices.insert((*ite)->getEndVertex()->mesh_vertices.begin(),
1245 (*ite)->getEndVertex()->mesh_vertices.end());
1246 }
1247 ++ite;
1248 }
1249
1250 // add embedded vertices
1251 std::vector<GVertex *> emb_vertx = gf->getEmbeddedVertices();
1252 auto itvx = emb_vertx.begin();
1253 while(itvx != emb_vertx.end()) {
1254 all_vertices.insert((*itvx)->mesh_vertices.begin(),
1255 (*itvx)->mesh_vertices.end());
1256 ++itvx;
1257 }
1258
1259 if(all_vertices.size() < 3) {
1260 Msg::Warning("Mesh generation of surface %d skipped: only %d nodes on "
1261 "the boundary",
1262 gf->tag(), all_vertices.size());
1263 gf->meshStatistics.status = GFace::DONE;
1264 return true;
1265 }
1266 else if(all_vertices.size() == 3) {
1267 MVertex *vv[3] = {nullptr, nullptr, nullptr};
1268 int i = 0;
1269 for(auto it = all_vertices.begin(); it != all_vertices.end(); it++) {
1270 vv[i++] = *it;
1271 }
1272 gf->triangles.push_back(new MTriangle(vv[0], vv[1], vv[2]));
1273 gf->meshStatistics.status = GFace::DONE;
1274 return true;
1275 }
1276
1277 // Buid a BDS_Mesh structure that is convenient for doing the actual
1278 // meshing procedure
1279 BDS_Mesh *m = new BDS_Mesh;
1280
1281 std::vector<BDS_Point *> points(all_vertices.size());
1282 SBoundingBox3d bbox;
1283 int count = 0;
1284 for(auto it = all_vertices.begin(); it != all_vertices.end(); it++) {
1285 MVertex *here = *it;
1286 GEntity *ge = here->onWhat();
1287 SPoint2 param;
1288 reparamMeshVertexOnFace(here, gf, param);
1289 BDS_Point *pp = m->add_point(count, param[0], param[1], gf);
1290 m->add_geom(ge->tag(), ge->dim());
1291 BDS_GeomEntity *g = m->get_geom(ge->tag(), ge->dim());
1292 pp->g = g;
1293 recoverMap[pp] = here;
1294 recoverMapInv[here] = pp;
1295 points[count] = pp;
1296 bbox += SPoint3(param[0], param[1], 0);
1297 count++;
1298 }
1299
1300 bbox.makeCube();
1301
1302 // use a divide & conquer type algorithm to create a triangulation.
1303 // We add to the triangulation a box with 4 points that encloses the
1304 // domain.
1305 if(CTX::instance()->mesh.oldInitialDelaunay2D){
1306 // compute the bounding box in parametric space
1307 SVector3 dd(bbox.max(), bbox.min());
1308 double LC2D = norm(dd);
1309 DocRecord doc(points.size() + 4);
1310 for(std::size_t i = 0; i < points.size(); i++) {
1311 double XX = CTX::instance()->mesh.randFactor * LC2D * (double)rand() /
1312 (double)RAND_MAX;
1313 double YY = CTX::instance()->mesh.randFactor * LC2D * (double)rand() /
1314 (double)RAND_MAX;
1315 doc.points[i].where.h = points[i]->u + XX;
1316 doc.points[i].where.v = points[i]->v + YY;
1317 doc.points[i].data = points[i];
1318 doc.points[i].adjacent = nullptr;
1319 }
1320
1321 // increase the size of the bounding box
1322 bbox *= 2.5;
1323
1324 // add 4 points than encloses the domain (use negative number to
1325 // distinguish those fake vertices)
1326 double bb[4][2] = {{bbox.min().x(), bbox.min().y()},
1327 {bbox.min().x(), bbox.max().y()},
1328 {bbox.max().x(), bbox.min().y()},
1329 {bbox.max().x(), bbox.max().y()}};
1330 for(int ip = 0; ip < 4; ip++) {
1331 BDS_Point *pp = m->add_point(-ip - 1, bb[ip][0], bb[ip][1], gf);
1332 m->add_geom(gf->tag(), 2);
1333 BDS_GeomEntity *g = m->get_geom(gf->tag(), 2);
1334 pp->g = g;
1335 doc.points[points.size() + ip].where.h = bb[ip][0];
1336 doc.points[points.size() + ip].where.v = bb[ip][1];
1337 doc.points[points.size() + ip].adjacent = nullptr;
1338 doc.points[points.size() + ip].data = pp;
1339 }
1340
1341 // Use "fast" inhouse recursive algo to generate the triangulation.
1342 // At this stage the triangulation is not what we need
1343 // -) It does not necessary recover the boundaries
1344 // -) It contains triangles outside the domain (the first edge
1345 // loop is the outer one)
1346 Msg::Debug("Meshing of the convex hull (%d points)", points.size());
1347 try {
1348 doc.MakeMeshWithPoints();
1349 } catch(const char *err) {
1350 Msg::Error("%s", err);
1351 }
1352 Msg::Debug("Meshing of the convex hull (%d points) done", points.size());
1353
1354 for(int i = 0; i < doc.numTriangles; i++) {
1355 int a = doc.triangles[i].a;
1356 int b = doc.triangles[i].b;
1357 int c = doc.triangles[i].c;
1358 int n = doc.numPoints;
1359 if(a < 0 || a >= n || b < 0 || b >= n || c < 0 || c >= n) {
1360 Msg::Warning("Skipping bad triangle %d", i);
1361 continue;
1362 }
1363 BDS_Point *p1 = (BDS_Point *)doc.points[doc.triangles[i].a].data;
1364 BDS_Point *p2 = (BDS_Point *)doc.points[doc.triangles[i].b].data;
1365 BDS_Point *p3 = (BDS_Point *)doc.points[doc.triangles[i].c].data;
1366 m->add_triangle(p1->iD, p2->iD, p3->iD);
1367 }
1368 }
1369 else {
1370 // New initial 2D mesher --> it actually does everything
1371 // -- triangulate points
1372 // -- recover edges
1373 // -- color triangles
1374
1375 std::vector<GEdge *> temp;
1376 if(replacement_edges) {
1377 temp = gf->edges();
1378 gf->set(*replacement_edges);
1379 }
1380 // recover and color so most of the code below can go away. Works also for
1381 // periodic faces
1382 PolyMesh *pm = GFaceInitialMesh(gf->tag(), 1);
1383
1384 if(replacement_edges) { gf->set(temp); }
1385
1386 std::map<int, BDS_Point *> aaa;
1387 for(auto it = all_vertices.begin(); it != all_vertices.end(); it++) {
1388 MVertex *here = *it;
1389 aaa[here->getNum()] = recoverMapInv[here];
1390 }
1391
1392 for(int ip = 0; ip < 4; ip++) {
1393 PolyMesh::Vertex *v = pm->vertices[ip];
1394 v->data = -ip - 1;
1395 BDS_Point *pp =
1396 m->add_point(v->data, v->position.x(), v->position.y(), gf);
1397 m->add_geom(gf->tag(), 2);
1398 BDS_GeomEntity *g = m->get_geom(gf->tag(), 2);
1399 pp->g = g;
1400 aaa[v->data] = pp;
1401 }
1402
1403 for(size_t i = 0; i < pm->faces.size(); i++) {
1404 PolyMesh::HalfEdge *he = pm->faces[i]->he;
1405 int a = he->v->data;
1406 int b = he->next->v->data;
1407 int c = he->next->next->v->data;
1408 BDS_Point *p1 = aaa[a];
1409 BDS_Point *p2 = aaa[b];
1410 BDS_Point *p3 = aaa[c];
1411 if(p1 && p2 && p3)
1412 m->add_triangle(p1->iD, p2->iD, p3->iD);
1413 }
1414 delete pm;
1415 }
1416
1417 if(debug && RECUR_ITER == 0) {
1418 char name[245];
1419 sprintf(name, "surface%d-initial-real.pos", gf->tag());
1420 outputScalarField(m->triangles, name, 0, gf);
1421 sprintf(name, "surface%d-initial-param.pos", gf->tag());
1422 outputScalarField(m->triangles, name, 1, gf);
1423 }
1424
1425 // Recover the boundary edges and compute characteristic lenghts using mesh
1426 // edge spacing. If two of these edges intersect, then the 1D mesh have to be
1427 // densified
1428 Msg::Debug("Recovering %d model edges", edges.size());
1429 std::set<EdgeToRecover> edgesToRecover;
1430 std::set<EdgeToRecover> edgesNotRecovered;
1431 ite = edges.begin();
1432 while(ite != edges.end()) {
1433 if(!(*ite)->isMeshDegenerated())
1434 recoverEdge(m, gf, *ite, recoverMapInv, &edgesToRecover,
1435 &edgesNotRecovered, 1);
1436 ++ite;
1437 }
1438 ite = emb_edges.begin();
1439 while(ite != emb_edges.end()) {
1440 if(!(*ite)->isMeshDegenerated())
1441 recoverEdge(m, gf, *ite, recoverMapInv, &edgesToRecover,
1442 &edgesNotRecovered, 1);
1443 ++ite;
1444 }
1445
1446 // effectively recover the medge
1447 ite = edges.begin();
1448 while(ite != edges.end()) {
1449 if(!(*ite)->isMeshDegenerated()) {
1450 if(!recoverEdge(m, gf, *ite, recoverMapInv, &edgesToRecover,
1451 &edgesNotRecovered, 2)) {
1452 delete m;
1453 gf->meshStatistics.status = GFace::FAILED;
1454 return false;
1455 }
1456 }
1457 ++ite;
1458 }
1459
1460 Msg::Debug("Recovering %d mesh edges (%d not recovered)",
1461 edgesToRecover.size(), edgesNotRecovered.size());
1462
1463 if(edgesNotRecovered.size() || gf->meshStatistics.refineAllEdges) {
1464 std::ostringstream sstream;
1465 for(auto itr = edgesNotRecovered.begin(); itr != edgesNotRecovered.end();
1466 ++itr)
1467 sstream << " " << itr->ge->tag();
1468 if(gf->meshStatistics.refineAllEdges) {
1469 Msg::Info("8-| Splitting all edges and trying again");
1470 }
1471 else {
1472 Msg::Info(":-( There are %d intersections in the 1D mesh (curves%s)",
1473 edgesNotRecovered.size(), sstream.str().c_str());
1474 if(repairSelfIntersecting1dMesh)
1475 Msg::Info("8-| Splitting those edges and trying again");
1476 }
1477 if(debug) {
1478 char name[245];
1479 sprintf(name, "surface%d-not_yet_recovered-real-%d.msh", gf->tag(),
1480 RECUR_ITER);
1481 gf->model()->writeMSH(name);
1482 }
1483
1484 if(repairSelfIntersecting1dMesh) {
1485 remeshUnrecoveredEdges(recoverMapInv, edgesNotRecovered);
1486 gf->meshStatistics.refineAllEdges = false;
1487 }
1488 else {
1489 auto itr = edgesNotRecovered.begin();
1490 int I = 0;
1491 for(; itr != edgesNotRecovered.end(); ++itr) {
1492 int p1 = itr->p1;
1493 int p2 = itr->p2;
1494 int tag = itr->ge->tag();
1495 Msg::Error("Edge not recovered: %d %d %d", p1, p2, tag);
1496 I++;
1497 }
1498 }
1499
1500 // delete the mesh
1501 delete m;
1502 if(RECUR_ITER < 10) {
1503 return meshGenerator(gf, RECUR_ITER + 1, repairSelfIntersecting1dMesh,
1504 onlyInitialMesh, debug, replacement_edges);
1505 }
1506 return false;
1507 }
1508
1509 if(RECUR_ITER > 0)
1510 Msg::Info(":-) All edges recovered after %d iteration%s", RECUR_ITER,
1511 (RECUR_ITER > 1) ? "s" : "");
1512
1513 Msg::Debug("Boundary edges recovered for surface %d", gf->tag());
1514
1515 // look for a triangle that has a negative node and recursively tag all
1516 // exterior triangles
1517 {
1518 auto itt = m->triangles.begin();
1519 while(itt != m->triangles.end()) {
1520 (*itt)->g = nullptr;
1521 ++itt;
1522 }
1523 itt = m->triangles.begin();
1524 while(itt != m->triangles.end()) {
1525 BDS_Face *t = *itt;
1526 BDS_Point *n[4];
1527 if(t->getNodes(n)) {
1528 if(n[0]->iD < 0 || n[1]->iD < 0 || n[2]->iD < 0) {
1529 recur_tag(t, &CLASS_EXTERIOR);
1530 break;
1531 }
1532 }
1533 ++itt;
1534 }
1535 }
1536
1537 // now find an edge that has belongs to one of the exterior triangles
1538 {
1539 auto ite = m->edges.begin();
1540 while(ite != m->edges.end()) {
1541 BDS_Edge *e = *ite;
1542 if(e->g && e->numfaces() == 2) {
1543 if(e->faces(0)->g == &CLASS_EXTERIOR) {
1544 recur_tag(e->faces(1), &CLASS_F);
1545 break;
1546 }
1547 else if(e->faces(1)->g == &CLASS_EXTERIOR) {
1548 recur_tag(e->faces(0), &CLASS_F);
1549 break;
1550 }
1551 }
1552 ++ite;
1553 }
1554 auto itt = m->triangles.begin();
1555 while(itt != m->triangles.end()) {
1556 if((*itt)->g == &CLASS_EXTERIOR) (*itt)->g = nullptr;
1557 ++itt;
1558 }
1559 }
1560
1561 {
1562 auto ite = m->edges.begin();
1563 while(ite != m->edges.end()) {
1564 BDS_Edge *e = *ite;
1565 if(e->g && e->numfaces() == 2) {
1566 BDS_Point *oface[2];
1567 e->oppositeof(oface);
1568 if(oface[0]->iD < 0) {
1569 recur_tag(e->faces(1), &CLASS_F);
1570 break;
1571 }
1572 else if(oface[1]->iD < 0) {
1573 recur_tag(e->faces(0), &CLASS_F);
1574 break;
1575 }
1576 }
1577 ++ite;
1578 }
1579 }
1580
1581 ite = emb_edges.begin();
1582 while(ite != emb_edges.end()) {
1583 if(!(*ite)->isMeshDegenerated())
1584 recoverEdge(m, gf, *ite, recoverMapInv, &edgesToRecover,
1585 &edgesNotRecovered, 2);
1586 ++ite;
1587 }
1588
1589 // compute characteristic lengths at vertices
1590 if(CTX::instance()->mesh.algo2d != ALGO_2D_BAMG && !onlyInitialMesh) {
1591 Msg::Debug("Computing mesh size field at mesh nodes %d",
1592 edgesToRecover.size());
1593 auto it = m->points.begin();
1594 for(; it != m->points.end(); ++it) {
1595 BDS_Point *pp = *it;
1596 auto itv = recoverMap.find(pp);
1597 if(itv != recoverMap.end()) {
1598 MVertex *here = itv->second;
1599 GEntity *ge = here->onWhat();
1600 if(ge->dim() == 0) {
1601 pp->lcBGM() = BGM_MeshSize(ge, 0, 0, here->x(), here->y(), here->z());
1602 }
1603 else if(ge->dim() == 1) {
1604 double u;
1605 here->getParameter(0, u);
1606 pp->lcBGM() = BGM_MeshSize(ge, u, 0, here->x(), here->y(), here->z());
1607 }
1608 else
1609 pp->lcBGM() = MAX_LC;
1610 pp->lc() = pp->lcBGM();
1611 }
1612 }
1613 }
1614
1615 // delete useless stuff
1616 auto itt = m->triangles.begin();
1617 while(itt != m->triangles.end()) {
1618 BDS_Face *t = *itt;
1619 if(!t->g) m->del_face(t);
1620 ++itt;
1621 }
1622 m->cleanup();
1623
1624 {
1625 auto ite = m->edges.begin();
1626 while(ite != m->edges.end()) {
1627 BDS_Edge *e = *ite;
1628 if(e->numfaces() == 0)
1629 m->del_edge(e);
1630 else {
1631 if(!e->g) e->g = &CLASS_F;
1632 if(!e->p1->g || e->p1->g->classif_degree > e->g->classif_degree)
1633 e->p1->g = e->g;
1634 if(!e->p2->g || e->p2->g->classif_degree > e->g->classif_degree)
1635 e->p2->g = e->g;
1636 }
1637 ++ite;
1638 }
1639 }
1640 m->cleanup();
1641 m->del_point(m->find_point(-1));
1642 m->del_point(m->find_point(-2));
1643 m->del_point(m->find_point(-3));
1644 m->del_point(m->find_point(-4));
1645
1646 if(debug) {
1647 char name[245];
1648 sprintf(name, "surface%d-recovered-real.pos", gf->tag());
1649 outputScalarField(m->triangles, name, 0, gf);
1650 sprintf(name, "surface%d-recovered-param.pos", gf->tag());
1651 outputScalarField(m->triangles, name, 1, gf);
1652 }
1653
1654 if(1) {
1655 auto itt = m->triangles.begin();
1656 while(itt != m->triangles.end()) {
1657 BDS_Face *t = *itt;
1658 if(!t->deleted) {
1659 BDS_Point *n[4];
1660 if(t->getNodes(n)) {
1661 MVertex *v1 = recoverMap[n[0]];
1662 MVertex *v2 = recoverMap[n[1]];
1663 MVertex *v3 = recoverMap[n[2]];
1664 if(!n[3]) {
1665 if(v1 != v2 && v1 != v3 && v2 != v3)
1666 gf->triangles.push_back(new MTriangle(v1, v2, v3));
1667 }
1668 else {
1669 MVertex *v4 = recoverMap[n[3]];
1670 gf->quadrangles.push_back(new MQuadrangle(v1, v2, v3, v4));
1671 }
1672 }
1673 }
1674 ++itt;
1675 }
1676 }
1677
1678 {
1679 int nb_swap;
1680 Msg::Debug("Delaunizing the initial mesh");
1681 delaunayizeBDS(gf, *m, nb_swap);
1682 }
1683
1684 // only delete the mesh data stored in the base GFace class
1685 gf->GFace::deleteMesh();
1686
1687 Msg::Debug("Starting to add internal nodes");
1688 // start mesh generation
1689 if(!algoDelaunay2D(gf) && !onlyInitialMesh) {
1690 refineMeshBDS(gf, *m, CTX::instance()->mesh.refineSteps, true,
1691 &recoverMapInv, nullptr);
1692 refineMeshBDS(gf, *m, CTX::instance()->mesh.refineSteps, false,
1693 &recoverMapInv, nullptr);
1694 }
1695
1696 gf->meshStatistics.status = GFace::DONE;
1697
1698 // fill the small gmsh structures
1699 BDS2GMSH(m, gf, recoverMap);
1700
1701 std::vector<MQuadrangle *> blQuads;
1702 std::vector<MTriangle *> blTris;
1703 std::set<MVertex *> verts;
1704
1705 bool infty = false;
1706 if(gf->getMeshingAlgo() == ALGO_2D_FRONTAL_QUAD) {
1707 infty = true;
1708 if(!onlyInitialMesh)
1709 buildBackgroundMesh(gf, CTX::instance()->mesh.crossFieldClosestPoint);
1710 }
1711 else if(gf->getMeshingAlgo() == ALGO_2D_PACK_PRLGRMS ||
1712 gf->getMeshingAlgo() == ALGO_2D_PACK_PRLGRMS_CSTR) {
1713 infty = true;
1714 /* New version of PACK / QUADQS use a different background mesh */
1715 // if(!onlyInitialMesh) buildBackgroundMesh(gf, false);
1716 }
1717
1718 if(!onlyInitialMesh)
1719 modifyInitialMeshForBoundaryLayers(gf, blQuads, blTris, verts, debug);
1720
1721 // the delaunay algo is based directly on internal gmsh structures BDS mesh is
1722 // passed in order not to recompute local coordinates of vertices
1723 if(algoDelaunay2D(gf) && !onlyInitialMesh) {
1724 if(gf->getMeshingAlgo() == ALGO_2D_FRONTAL) { bowyerWatsonFrontal(gf); }
1725 else if(gf->getMeshingAlgo() == ALGO_2D_FRONTAL_QUAD) {
1726 bowyerWatsonFrontalLayers(gf, true);
1727 }
1728 else if(gf->getMeshingAlgo() == ALGO_2D_PACK_PRLGRMS) {
1729 bowyerWatsonParallelograms(gf);
1730 }
1731 else if(gf->getMeshingAlgo() == ALGO_2D_PACK_PRLGRMS_CSTR) {
1732 Msg::Error("ALGO_2D_PACK_PRLGRMS_CSTR deprecated");
1733 // bowyerWatsonParallelogramsConstrained(gf, gf->constr_vertices);
1734 }
1735 else if(gf->getMeshingAlgo() == ALGO_2D_DELAUNAY ||
1736 gf->getMeshingAlgo() == ALGO_2D_AUTO) {
1737 bowyerWatson(gf);
1738 }
1739 else {
1740 bowyerWatson(gf, 15000);
1741 meshGFaceBamg(gf);
1742 }
1743
1744 if(!infty ||
1745 !(CTX::instance()->mesh.recombineAll || gf->meshAttributes.recombine))
1746 laplaceSmoothing(gf, CTX::instance()->mesh.nbSmoothing, infty);
1747 }
1748
1749 if(debug) {
1750 char name[256];
1751 // sprintf(name, "trueBoundary%d.pos", gf->tag());
1752 // std::vector<SPoint2> bnd;
1753 // trueBoundary(name, gf,bnd);
1754 sprintf(name, "real%d.pos", gf->tag());
1755 outputScalarField(m->triangles, name, 0, gf);
1756 sprintf(name, "param%d.pos", gf->tag());
1757 outputScalarField(m->triangles, name, 1, gf);
1758 }
1759
1760 delete m;
1761
1762 gf->quadrangles.insert(gf->quadrangles.begin(), blQuads.begin(),
1763 blQuads.end());
1764 gf->triangles.insert(gf->triangles.begin(), blTris.begin(), blTris.end());
1765 gf->mesh_vertices.insert(gf->mesh_vertices.begin(), verts.begin(),
1766 verts.end());
1767
1768 splitElementsInBoundaryLayerIfNeeded(gf);
1769
1770 if((CTX::instance()->mesh.recombineAll || gf->meshAttributes.recombine) &&
1771 (CTX::instance()->mesh.algoRecombine <= 1 ||
1772 CTX::instance()->mesh.algoRecombine == 4)) {
1773 bool blossom = (CTX::instance()->mesh.algoRecombine == 1);
1774 int topo = CTX::instance()->mesh.recombineOptimizeTopology;
1775 bool nodeRepositioning = true;
1776 if(CTX::instance()->mesh.algoRecombine == 4)
1777 meshGFaceQuadrangulateBipartiteLabelling(gf->tag());
1778 else
1779 recombineIntoQuads(gf, blossom, topo, nodeRepositioning, 0.1);
1780 }
1781
1782 computeElementShapes(gf, gf->meshStatistics.worst_element_shape,
1783 gf->meshStatistics.average_element_shape,
1784 gf->meshStatistics.best_element_shape,
1785 gf->meshStatistics.nbTriangle,
1786 gf->meshStatistics.nbGoodQuality);
1787
1788 if(CTX::instance()->mesh.algo3d == ALGO_3D_RTREE) { directions_storage(gf); }
1789
1790 // remove unused vertices, generated e.g. during background mesh
1791 _deleteUnusedVertices(gf);
1792
1793 return true;
1794 }
1795
1796 // this function buils a list of BDS points that are consecutive in one given
1797 // edge loop, taking care of periodic surfaces with seams; it also fills the
1798 // recoverMap to link BDS points with mesh nodes
1799
buildConsecutiveListOfVertices(GFace * gf,GEdgeLoop & gel,std::vector<BDS_Point * > & result,SBoundingBox3d & bbox,BDS_Mesh * m,std::map<BDS_Point *,MVertex *,PointLessThan> & recoverMap,int & count,int countTot,double tol,bool seam_the_first=false)1800 static bool buildConsecutiveListOfVertices(
1801 GFace *gf, GEdgeLoop &gel, std::vector<BDS_Point *> &result,
1802 SBoundingBox3d &bbox, BDS_Mesh *m,
1803 std::map<BDS_Point *, MVertex *, PointLessThan> &recoverMap, int &count,
1804 int countTot, double tol, bool seam_the_first = false)
1805 {
1806 result.clear();
1807 count = 0;
1808
1809 // building the list of nodes in the parametric space for periodic surfaces is
1810 // tricky:
1811 // 1) both reparametrizations of the seams must be tested, as the topological
1812 // representation does not know which one to use
1813 // 2) both orientations of curves must be tested, as the topological
1814 // representation of periodic curves cannot distinguish them
1815 // 3) reparametrization of curves on surfaces can lead to slightly different
1816 // parametric coordinates, especially with OpenCASCADE - so a tolerance is
1817 // needed
1818 std::vector<GEdgeSigned> signedEdges(gel.begin(), gel.end());
1819 std::vector<SPoint2> coords;
1820 std::vector<MVertex*> verts;
1821
1822 #if 0 // for debugging - don't remove
1823 printf("curve loop for surface %d\n", gf->tag());
1824 for(std::size_t i = 0; i < signedEdges.size(); i++) {
1825 GEdge *ge = signedEdges[i].getEdge();
1826 bool seam = ge->isSeam(gf);
1827 Range<double> range = ge->parBoundsOnFace(gf);
1828 printf(" curve %d: ", ge->tag());
1829 SPoint2 p;
1830 p = ge->reparamOnFace(gf, range.low(), 1);
1831 printf("beg (%g,%g) ", p.x(), p.y());
1832 if(seam) {
1833 p = ge->reparamOnFace(gf, range.low(), -1);
1834 printf("beg_alt (%g,%g) ", p.x(), p.y());
1835 }
1836 p = ge->reparamOnFace(gf, range.high(), 1);
1837 printf("end (%g,%g) ", p.x(), p.y());
1838 if(seam) {
1839 p = ge->reparamOnFace(gf, range.high(), -1);
1840 printf("end_alt (%g,%g) ", p.x(), p.y());
1841 }
1842 printf("\n");
1843 }
1844 #endif
1845
1846 for(int initial_dir = 0; initial_dir < 2; initial_dir++) {
1847
1848 if(coords.size()) break; // we succeeded with initial_dir == 0
1849
1850 for(std::size_t i = 0; i < signedEdges.size(); i++) {
1851 std::vector<SPoint2> p, p_alt, p_rev, p_alt_rev;
1852 std::vector<MVertex*> v, v_rev;
1853 GEdge *ge = signedEdges[i].getEdge();
1854 bool seam = ge->isSeam(gf);
1855 Range<double> range = ge->parBoundsOnFace(gf);
1856
1857 // get parametric coordinates of curve nodes on the surface, with both
1858 // possible values for seams
1859 if(ge->getBeginVertex()) {
1860 p.push_back(ge->reparamOnFace(gf, range.low(), 1));
1861 if(seam) p_alt.push_back(ge->reparamOnFace(gf, range.low(), -1));
1862 v.push_back(ge->getBeginVertex()->mesh_vertices[0]);
1863 }
1864 for(std::size_t j = 0; j < ge->mesh_vertices.size(); j++) {
1865 double u;
1866 ge->mesh_vertices[j]->getParameter(0, u);
1867 p.push_back(ge->reparamOnFace(gf, u, 1));
1868 if(seam) p_alt.push_back(ge->reparamOnFace(gf, u, -1));
1869 v.push_back(ge->mesh_vertices[j]);
1870 }
1871 if(ge->getEndVertex()) {
1872 p.push_back(ge->reparamOnFace(gf, range.high(), 1));
1873 if(seam) p_alt.push_back(ge->reparamOnFace(gf, range.high(), -1));
1874 v.push_back(ge->getEndVertex()->mesh_vertices[0]);
1875 }
1876
1877 // get the reverse mesh
1878 p_rev = p;
1879 std::reverse(p_rev.begin(), p_rev.end());
1880 if(seam) {
1881 p_alt_rev = p_alt;
1882 std::reverse(p_alt_rev.begin(), p_alt_rev.end());
1883 }
1884 v_rev = v;
1885 std::reverse(v_rev.begin(), v_rev.end());
1886
1887 if(i == 0) {
1888 // choose which mesh to consider for the first curve in the loop
1889 if(initial_dir == 0) {
1890 if(seam && seam_the_first)
1891 coords = p_alt;
1892 else
1893 coords = p;
1894 verts = v;
1895 }
1896 else {
1897 if(seam && seam_the_first)
1898 coords = p_alt_rev;
1899 else
1900 coords = p_rev;
1901 verts = v_rev;
1902 }
1903 }
1904 else{
1905 // detect which mesh variant to use for the next curve by selecting the
1906 // mesh that starts with the node at the smallest distance, within the
1907 // prescribed tolerance
1908 double dist1 = coords.back().distance(p.front());
1909 double dist2 = coords.back().distance(p_rev.front());
1910 if(!seam) {
1911 if(dist1 < dist2 && dist1 < tol) {
1912 coords.pop_back();
1913 coords.insert(coords.end(), p.begin(), p.end());
1914 verts.pop_back();
1915 verts.insert(verts.end(), v.begin(), v.end());
1916 }
1917 else if(dist2 < dist1 && dist2 < tol) {
1918 coords.pop_back();
1919 coords.insert(coords.end(), p_rev.begin(), p_rev.end());
1920 verts.pop_back();
1921 verts.insert(verts.end(), v_rev.begin(), v_rev.end());
1922 }
1923 else{
1924 Msg::Debug("Distances (%g, %g) in parametric space larger than "
1925 "tolerance (%g) between end of curve %d and "
1926 "begining of curve %d...", dist1, dist2, tol,
1927 signedEdges[i - 1].getEdge()->tag(), ge->tag());
1928 if(initial_dir == 0){
1929 Msg::Debug("... will try with alternate initial orientation");
1930 coords.clear();
1931 verts.clear();
1932 break;
1933 }
1934 else{
1935 Msg::Debug("... will try with larger tolerance");
1936 return false;
1937 }
1938 }
1939 }
1940 else {
1941 double dist3 = coords.back().distance(p_alt.front());
1942 double dist4 = coords.back().distance(p_alt_rev.front());
1943 if(dist1 < dist2 && dist1 < dist3 && dist1 < dist4 && dist1 < tol) {
1944 coords.pop_back();
1945 coords.insert(coords.end(), p.begin(), p.end());
1946 verts.pop_back();
1947 verts.insert(verts.end(), v.begin(), v.end());
1948 }
1949 else if(dist2 < dist1 && dist2 < dist3 && dist2 < dist4 && dist2 < tol) {
1950 coords.pop_back();
1951 coords.insert(coords.end(), p_rev.begin(), p_rev.end());
1952 verts.pop_back();
1953 verts.insert(verts.end(), v_rev.begin(), v_rev.end());
1954 }
1955 else if(dist3 < dist1 && dist3 < dist2 && dist3 < dist4 && dist3 < tol) {
1956 coords.pop_back();
1957 coords.insert(coords.end(), p_alt.begin(), p_alt.end());
1958 verts.pop_back();
1959 verts.insert(verts.end(), v.begin(), v.end());
1960 }
1961 else if(dist4 < dist1 && dist4 < dist2 && dist4 < dist3 && dist4 < tol) {
1962 coords.pop_back();
1963 coords.insert(coords.end(), p_alt_rev.begin(), p_alt_rev.end());
1964 verts.pop_back();
1965 verts.insert(verts.end(), v_rev.begin(), v_rev.end());
1966 }
1967 else {
1968 Msg::Debug("Distances (%g, %g, %g, %g) in parametric space larger "
1969 "than tolerance (%g) between end of curve %d and "
1970 "begining of seam curve %d...", dist1, dist2, dist3, dist4,
1971 tol, signedEdges[i - 1].getEdge()->tag(), ge->tag());
1972 if(initial_dir == 0){
1973 Msg::Debug("... will try with alternate initial orientation");
1974 coords.clear();
1975 verts.clear();
1976 break;
1977 }
1978 else{
1979 Msg::Debug("... will try with larger tolerance");
1980 return false;
1981 }
1982 }
1983 }
1984 }
1985 }
1986 }
1987
1988 if(verts.size() != coords.size()) {
1989 Msg::Error("Wrong number of parametric coordinates for boundary nodes "
1990 "on surface %d", gf->tag());
1991 return false;
1992 }
1993 if(verts.empty()) {
1994 Msg::Debug("No nodes in 1D mesh on surface %d", gf->tag());
1995 return true;
1996 }
1997 double dist = coords.back().distance(coords.front());
1998 if(dist < tol) {
1999 coords.pop_back();
2000 verts.pop_back();
2001 }
2002 else {
2003 Msg::Debug("Distance %g between first and last node in 1D mesh of surface "
2004 "%d exceeds tolerance %g", dist, gf->tag(), tol);
2005 return false;
2006 }
2007
2008 std::map<BDS_Point *, MVertex *, PointLessThan> recoverMapLocal;
2009
2010 for(std::size_t i = 0; i < verts.size(); i++) {
2011 MVertex *here = verts[i];
2012 GEntity *ge = here->onWhat();
2013 BDS_Point *pp = nullptr;
2014 if(ge->dim() == 0) {
2015 // point might already be part of another loop in the same surface
2016 for(auto it = recoverMap.begin(); it != recoverMap.end(); ++it) {
2017 if(it->second == here) {
2018 SPoint2 param(it->first->u, it->first->v);
2019 double dist = coords[i].distance(param);
2020 if(dist < tol) {
2021 pp = it->first;
2022 break;
2023 }
2024 }
2025 }
2026 }
2027 if(pp == nullptr) {
2028 double U, V;
2029 SPoint2 param = coords[i];
2030 U = param.x();
2031 V = param.y();
2032 pp = m->add_point(count + countTot, U, V, gf);
2033 if(ge->dim() == 0) {
2034 pp->lcBGM() = BGM_MeshSize(ge, 0, 0, here->x(), here->y(), here->z());
2035 }
2036 else if(ge->dim() == 1) {
2037 double u;
2038 here->getParameter(0, u);
2039 pp->lcBGM() = BGM_MeshSize(ge, u, 0, here->x(), here->y(), here->z());
2040 }
2041 else {
2042 pp->lcBGM() = MAX_LC;
2043 }
2044 pp->lc() = pp->lcBGM();
2045 m->add_geom(ge->tag(), ge->dim());
2046 BDS_GeomEntity *g = m->get_geom(ge->tag(), ge->dim());
2047 pp->g = g;
2048 bbox += SPoint3(U, V, 0);
2049 }
2050 //printf("node %d coord %g %g\n", here->getNum(), pp->u, pp->v);
2051 result.push_back(pp);
2052 recoverMapLocal[pp] = here;
2053 count++;
2054 }
2055
2056 // we're all set!
2057 recoverMap.insert(recoverMapLocal.begin(), recoverMapLocal.end());
2058
2059 return true;
2060 }
2061
getGEdge(GFace * gf,MVertex * v1,MVertex * v2)2062 static GEdge *getGEdge(GFace *gf, MVertex *v1, MVertex *v2)
2063 {
2064 std::vector<GEdge *> e = gf->edges();
2065 for(size_t i = 0; i < e.size(); i++) {
2066 GEdge *ge = e[i];
2067 for(size_t j = 0; j < ge->lines.size(); j++) {
2068 MLine *l = ge->lines[j];
2069 if(l->getVertex(0) == v1 && l->getVertex(1) == v2) return ge;
2070 if(l->getVertex(1) == v1 && l->getVertex(0) == v2) return ge;
2071 }
2072 }
2073 return nullptr;
2074 }
2075
meshGeneratorPeriodic(GFace * gf,int RECUR_ITER,bool repairSelfIntersecting1dMesh,bool debug=true)2076 static bool meshGeneratorPeriodic(GFace *gf, int RECUR_ITER,
2077 bool repairSelfIntersecting1dMesh,
2078 bool debug = true)
2079 {
2080 if(CTX::instance()->debugSurface > 0 &&
2081 gf->tag() != CTX::instance()->debugSurface) {
2082 gf->meshStatistics.status = GFace::DONE;
2083 return true;
2084 }
2085 if(CTX::instance()->debugSurface > 0) debug = true;
2086
2087 // TEST !!!
2088 // PolyMesh * pm = GFaceInitialMesh(gf->tag(), 1);
2089
2090 std::map<BDS_Point *, MVertex *, PointLessThan> recoverMap;
2091 std::multimap<MVertex *, BDS_Point *> recoverMultiMapInv;
2092
2093 std::vector<SPoint2> true_boundary;
2094 trueBoundary(gf, true_boundary, debug);
2095
2096 Range<double> rangeU = gf->parBounds(0);
2097 Range<double> rangeV = gf->parBounds(1);
2098
2099 double du = rangeU.high() - rangeU.low();
2100 double dv = rangeV.high() - rangeV.low();
2101
2102 const double LC2D = std::sqrt(du * du + dv * dv);
2103
2104 // Buid a BDS_Mesh structure that is convenient for doing the actual meshing
2105 // procedure
2106 BDS_Mesh *m = new BDS_Mesh;
2107
2108 std::vector<std::vector<BDS_Point *> > edgeLoops_BDS;
2109 SBoundingBox3d bbox;
2110 int nbPointsTotal = 0;
2111 {
2112 for(auto it = gf->edgeLoops.begin(); it != gf->edgeLoops.end(); it++) {
2113 std::vector<BDS_Point *> edgeLoop_BDS;
2114 int nbPointsLocal;
2115 const double fact[5] = {1.e-12, 1.e-9, 1.e-6, 1.e-3, 1.e-1};
2116 bool ok = false;
2117 for(int i = 0; i < 5; i++) {
2118 if(buildConsecutiveListOfVertices(gf, *it, edgeLoop_BDS, bbox, m,
2119 recoverMap, nbPointsLocal,
2120 nbPointsTotal, fact[i] * LC2D)) {
2121 ok = true;
2122 break;
2123 }
2124 if(buildConsecutiveListOfVertices(
2125 gf, *it, edgeLoop_BDS, bbox, m, recoverMap, nbPointsLocal,
2126 nbPointsTotal, fact[i] * LC2D, true)) {
2127 ok = true;
2128 break;
2129 }
2130 }
2131 if(!ok) {
2132 gf->meshStatistics.status = GFace::FAILED;
2133 Msg::Error("The 1D mesh seems not to be forming a closed loop");
2134 delete m;
2135 return false;
2136 }
2137 nbPointsTotal += nbPointsLocal;
2138 edgeLoops_BDS.push_back(edgeLoop_BDS);
2139 }
2140 }
2141
2142 {
2143 auto it = recoverMap.begin();
2144 std::map<MVertex *, BDS_Point *> INV;
2145 for(; it != recoverMap.end(); ++it) {
2146 recoverMultiMapInv.insert(std::make_pair(it->second, it->first));
2147
2148 auto it2 = INV.find(it->second);
2149 if(it2 != INV.end()) {
2150 it->first->_periodicCounterpart = it2->second;
2151 it2->second->_periodicCounterpart = it->first;
2152 }
2153 INV[it->second] = it->first;
2154 }
2155 }
2156
2157 if(nbPointsTotal < 3) {
2158 Msg::Warning("Mesh generation of surface %d skipped: only %d nodes on "
2159 "the boundary",
2160 gf->tag(), nbPointsTotal);
2161 gf->meshStatistics.status = GFace::DONE;
2162 delete m;
2163 return true;
2164 }
2165 else if(nbPointsTotal == 3) {
2166 MVertex *vv[3] = {nullptr, nullptr, nullptr};
2167 int i = 0;
2168 for(auto it = recoverMap.begin(); it != recoverMap.end(); it++) {
2169 vv[i++] = it->second;
2170 }
2171 if(vv[0] && vv[1] && vv[2])
2172 gf->triangles.push_back(new MTriangle(vv[0], vv[1], vv[2]));
2173 gf->meshStatistics.status = GFace::DONE;
2174 delete m;
2175 return true;
2176 }
2177
2178 // Use a divide & conquer type algorithm to create a triangulation. We add to
2179 // the triangulation a box with 4 points that encloses the domain.
2180
2181 std::vector<int> edgesEmbedded;
2182
2183 {
2184 int count = 0;
2185
2186 // Embedded Vertices
2187 // add embedded vertices
2188 std::vector<GVertex *> emb_vertx = gf->getEmbeddedVertices();
2189 auto itvx = emb_vertx.begin();
2190
2191 std::map<MVertex *, std::set<BDS_Point *> > invertedRecoverMap;
2192 for(auto it = recoverMap.begin(); it != recoverMap.end(); it++) {
2193 invertedRecoverMap[it->second].insert(it->first);
2194 }
2195
2196 int pNum = m->MAXPOINTNUMBER;
2197 nbPointsTotal += emb_vertx.size();
2198 {
2199 std::vector<GEdge *> emb_edges = gf->getEmbeddedEdges();
2200 std::set<MVertex *> vs;
2201 auto ite = emb_edges.begin();
2202 while(ite != emb_edges.end()) {
2203 for(std::size_t i = 0; i < (*ite)->lines.size(); i++) {
2204 for(std::size_t j = 0; j < 2; j++) {
2205 MVertex *v = (*ite)->lines[i]->getVertex(j);
2206 if(invertedRecoverMap.find(v) == invertedRecoverMap.end() &&
2207 vs.find(v) == vs.end()) {
2208 vs.insert(v);
2209 }
2210 }
2211 }
2212 ++ite;
2213 }
2214 nbPointsTotal += vs.size();
2215 }
2216 DocRecord doc(nbPointsTotal + 4);
2217
2218 while(itvx != emb_vertx.end()) {
2219 MVertex *v = (*itvx)->mesh_vertices[0];
2220 double uv[2] = {0, 0};
2221 GPoint gp = gf->closestPoint(SPoint3(v->x(), v->y(), v->z()), uv);
2222 BDS_Point *pp = m->add_point(++pNum, gp.u(), gp.v(), gf);
2223 m->add_geom(-(*itvx)->tag(), 0);
2224 pp->g = m->get_geom(-(*itvx)->tag(), 0);
2225 pp->lcBGM() = BGM_MeshSize(*itvx, 0, 0, v->x(), v->y(), v->z());
2226 pp->lc() = pp->lcBGM();
2227 recoverMap[pp] = v;
2228 double XX = CTX::instance()->mesh.randFactor * LC2D * (double)rand() /
2229 (double)RAND_MAX;
2230 double YY = CTX::instance()->mesh.randFactor * LC2D * (double)rand() /
2231 (double)RAND_MAX;
2232 doc.points[count].where.h = pp->u + XX;
2233 doc.points[count].where.v = pp->v + YY;
2234 doc.points[count].adjacent = nullptr;
2235 doc.points[count].data = pp;
2236 count++;
2237 ++itvx;
2238 }
2239
2240 std::vector<GEdge *> emb_edges = gf->getEmbeddedEdges();
2241 std::set<MVertex *> vs;
2242 std::map<MVertex *, BDS_Point *> facile;
2243 auto ite = emb_edges.begin();
2244 while(ite != emb_edges.end()) {
2245 m->add_geom(-(*ite)->tag(), 1);
2246 for(std::size_t i = 0; i < (*ite)->lines.size(); i++) {
2247 for(std::size_t j = 0; j < 2; j++) {
2248 MVertex *v = (*ite)->lines[i]->getVertex(j);
2249 BDS_Point *pp = nullptr;
2250 const auto it = invertedRecoverMap.find(v);
2251 if(it != invertedRecoverMap.end()) {
2252 if(it->second.size() > 1) {
2253 const GEdge *edge = (*ite);
2254 const Range<double> parBounds = edge->parBoundsOnFace(gf);
2255 GPoint firstPoint = edge->point(parBounds.low());
2256 GPoint lastPoint = edge->point(parBounds.high());
2257 double param;
2258 if(v->point().distance(
2259 SPoint3(firstPoint.x(), firstPoint.y(), firstPoint.z())) <
2260 v->point().distance(
2261 SPoint3(lastPoint.x(), lastPoint.y(), lastPoint.z()))) {
2262 // Vertex lies on first point of edge
2263 param = parBounds.low();
2264 }
2265 else {
2266 // Vertex lies on last point of edge
2267 param = parBounds.high();
2268 }
2269 SPoint2 pointOnSurface = edge->reparamOnFace(gf, param, 1);
2270
2271 const std::set<BDS_Point *> &possiblePoints = it->second;
2272 for(auto pntIt = possiblePoints.begin();
2273 pntIt != possiblePoints.end(); ++pntIt) {
2274 if(pointOnSurface.distance(SPoint2((*pntIt)->u, (*pntIt)->v)) <
2275 1e-10) {
2276 pp = (*pntIt);
2277 break;
2278 }
2279 }
2280 if(pp == nullptr) {
2281 Msg::Error("Embedded edge node %d is on the seam edge of "
2282 "surface %d and no appropriate point could be "
2283 "found!",
2284 v->getNum(), gf->tag());
2285 }
2286 }
2287 else {
2288 pp = *(it->second.begin());
2289 }
2290 facile[v] = pp;
2291 }
2292 if(pp == nullptr && vs.find(v) == vs.end()) {
2293 vs.insert(v);
2294 double uv[2] = {0, 0};
2295 GPoint gp = gf->closestPoint(SPoint3(v->x(), v->y(), v->z()), uv);
2296 BDS_Point *pp = m->add_point(++pNum, gp.u(), gp.v(), gf);
2297 pp->g = m->get_geom(-(*ite)->tag(), 1);
2298 if(v->onWhat()->dim() == 0)
2299 pp->lcBGM() =
2300 BGM_MeshSize(v->onWhat(), 0, 0, v->x(), v->y(), v->z());
2301 else {
2302 double uu;
2303 v->getParameter(0, uu);
2304 pp->lcBGM() = BGM_MeshSize(*ite, uu, 0, v->x(), v->y(), v->z());
2305 }
2306 pp->lc() = pp->lcBGM();
2307 recoverMap[pp] = v;
2308 facile[v] = pp;
2309 double XX = CTX::instance()->mesh.randFactor * LC2D *
2310 (double)rand() / (double)RAND_MAX;
2311 double YY = CTX::instance()->mesh.randFactor * LC2D *
2312 (double)rand() / (double)RAND_MAX;
2313 doc.points[count].where.h = pp->u + XX;
2314 doc.points[count].where.v = pp->v + YY;
2315 doc.points[count].adjacent = nullptr;
2316 doc.points[count].data = pp;
2317 count++;
2318 }
2319 }
2320 }
2321 for(std::size_t i = 0; i < (*ite)->lines.size(); i++) {
2322 BDS_Point *p0 = facile[(*ite)->lines[i]->getVertex(0)];
2323 BDS_Point *p1 = facile[(*ite)->lines[i]->getVertex(1)];
2324 edgesEmbedded.push_back(p0->iD);
2325 edgesEmbedded.push_back(p1->iD);
2326 }
2327 ++ite;
2328 }
2329
2330 for(std::size_t i = 0; i < edgeLoops_BDS.size(); i++) {
2331 std::vector<BDS_Point *> &edgeLoop_BDS = edgeLoops_BDS[i];
2332 for(std::size_t j = 0; j < edgeLoop_BDS.size(); j++) {
2333 BDS_Point *pp = edgeLoop_BDS[j];
2334 double XX = CTX::instance()->mesh.randFactor * LC2D * (double)rand() /
2335 (double)RAND_MAX;
2336 double YY = CTX::instance()->mesh.randFactor * LC2D * (double)rand() /
2337 (double)RAND_MAX;
2338 doc.points[count].where.h = pp->u + XX;
2339 doc.points[count].where.v = pp->v + YY;
2340 doc.points[count].adjacent = nullptr;
2341 doc.points[count].data = pp;
2342 count++;
2343 }
2344 }
2345
2346 // Increase the size of the bounding box, add 4 points that enclose
2347 // the domain, use negative number to distinguish those fake
2348 // vertices
2349
2350 if(du / dv < 1200 && dv / du < 1200) {
2351 // Fix a bug here if the size of the box is zero
2352 bbox.makeCube();
2353 }
2354
2355 bbox *= 3.5;
2356 GPoint bb[4] = {GPoint(bbox.min().x(), bbox.min().y(), 0),
2357 GPoint(bbox.min().x(), bbox.max().y(), 0),
2358 GPoint(bbox.max().x(), bbox.min().y(), 0),
2359 GPoint(bbox.max().x(), bbox.max().y(), 0)};
2360 for(int ip = 0; ip < 4; ip++) {
2361 BDS_Point *pp = m->add_point(-ip - 1, bb[ip].x(), bb[ip].y(), gf);
2362 m->add_geom(gf->tag(), 2);
2363 BDS_GeomEntity *g = m->get_geom(gf->tag(), 2);
2364 pp->g = g;
2365 doc.points[nbPointsTotal + ip].where.h = bb[ip].x();
2366 doc.points[nbPointsTotal + ip].where.v = bb[ip].y();
2367 doc.points[nbPointsTotal + ip].adjacent = nullptr;
2368 doc.points[nbPointsTotal + ip].data = pp;
2369 }
2370
2371 // Use "fast" inhouse recursive algo to generate the triangulation
2372 // At this stage the triangulation is not what we need
2373 // -) It does not necessary recover the boundaries
2374 // -) It contains triangles outside the domain (the first edge
2375 // loop is the outer one)
2376 Msg::Debug("Meshing of the convex hull (%d nodes)", nbPointsTotal);
2377
2378 try {
2379 doc.MakeMeshWithPoints();
2380 } catch(const char *err) {
2381 Msg::Error("%s", err);
2382 }
2383
2384 for(int i = 0; i < doc.numTriangles; i++) {
2385 int a = doc.triangles[i].a;
2386 int b = doc.triangles[i].b;
2387 int c = doc.triangles[i].c;
2388 int n = doc.numPoints;
2389 if(a < 0 || a >= n || b < 0 || b >= n || c < 0 || c >= n) {
2390 Msg::Warning("Skipping bad triangle %d", i);
2391 continue;
2392 }
2393 BDS_Point *p1 = (BDS_Point *)doc.points[doc.triangles[i].a].data;
2394 BDS_Point *p2 = (BDS_Point *)doc.points[doc.triangles[i].b].data;
2395 BDS_Point *p3 = (BDS_Point *)doc.points[doc.triangles[i].c].data;
2396 m->add_triangle(p1->iD, p2->iD, p3->iD);
2397 }
2398 }
2399
2400 // Recover the boundary edges and compute characteristic lenghts using mesh
2401 // edge spacing
2402 BDS_GeomEntity CLASS_F(1, 2);
2403 BDS_GeomEntity CLASS_E(1, 1);
2404 BDS_GeomEntity CLASS_EXTERIOR(3, 2);
2405
2406 if(debug) {
2407 char name[245];
2408 sprintf(name, "surface%d-initial-real.pos", gf->tag());
2409 outputScalarField(m->triangles, name, 0, gf);
2410 sprintf(name, "surface%d-initial-param.pos", gf->tag());
2411 outputScalarField(m->triangles, name, 1, gf);
2412 }
2413
2414 bool _fatallyFailed;
2415
2416 for(std::size_t i = 0; i < edgesEmbedded.size() / 2; i++) {
2417 BDS_Edge *e = m->recover_edge(edgesEmbedded[2 * i],
2418 edgesEmbedded[2 * i + 1], _fatallyFailed);
2419 if(!e) {
2420 Msg::Error("Impossible to recover the edge %d %d", edgesEmbedded[2 * i],
2421 edgesEmbedded[2 * i + 1]);
2422 gf->meshStatistics.status = GFace::FAILED;
2423 delete m;
2424 return false;
2425 }
2426 else
2427 e->g = &CLASS_E;
2428 }
2429
2430 std::set<EdgeToRecover> edgesNotRecovered;
2431
2432 bool doItAgain = gf->meshStatistics.refineAllEdges;
2433 for(std::size_t i = 0; i < edgeLoops_BDS.size(); i++) {
2434 std::vector<BDS_Point *> &edgeLoop_BDS = edgeLoops_BDS[i];
2435 for(std::size_t j = 0; j < edgeLoop_BDS.size(); j++) {
2436 int num1 = edgeLoop_BDS[j]->iD;
2437 int num2 = edgeLoop_BDS[(j + 1) % edgeLoop_BDS.size()]->iD;
2438 BDS_Edge *e = m->find_edge(num1, num2);
2439 if(!e) {
2440 // printf("recovering %d %d\n",num1,num2);
2441 e = m->recover_edge(num1, num2, _fatallyFailed);
2442 BDS_Point *p1 = m->find_point(num1);
2443 BDS_Point *p2 = m->find_point(num2);
2444 MVertex *v1 = recoverMap[p1];
2445 MVertex *v2 = recoverMap[p2];
2446 GEdge *ge = getGEdge(gf, v1, v2);
2447 // if (!ge){
2448 // Msg::Error("cannot find GEdge with mesh edge %d %d (%d %d)\n",
2449 // num1, num2, v1->getNum(), v2->getNum());
2450 // }
2451 if(ge) edgesNotRecovered.insert(EdgeToRecover(num1, num2, ge));
2452 if(!e) {
2453 // what is before does not seem to work properly
2454 // Msg::Warning("ITER %d Impossible to recover the edge %d %d",
2455 // RECUR_ITER, num1, num2);
2456 // Msg::Warning("Will split model edge %d and try again", ge->tag());
2457 doItAgain = true;
2458 // gf->meshStatistics.status = GFace::FAILED;
2459 // delete m;
2460 // return false;
2461 }
2462 else {
2463 // Msg::Warning("ITER %d edge %d %d RECOVERED",RECUR_ITER, num1,num2);
2464 e->g = &CLASS_E;
2465 }
2466 }
2467 else
2468 e->g = &CLASS_E;
2469 }
2470 }
2471
2472 if(doItAgain) {
2473 // this block is not thread safe. 2D mesh will be serialized for surfaces
2474 // that have their 1D mesh self-intersect
2475 if(Msg::GetNumThreads() != 1) {
2476 gf->meshStatistics.status = GFace::PENDING;
2477 delete m;
2478 Msg::Info("Surface %d has self-intersections in its 1D mesh: serializing "
2479 "this one",
2480 gf->tag());
2481 return true;
2482 }
2483
2484 if(!gf->meshStatistics.refineAllEdges) {
2485 std::ostringstream sstream;
2486 for(auto itr = edgesNotRecovered.begin(); itr != edgesNotRecovered.end();
2487 ++itr)
2488 sstream
2489 << " " << itr->ge->tag() << "("
2490 << (itr->ge->getBeginVertex() ? itr->ge->getBeginVertex()->tag() : -1)
2491 << ","
2492 << (itr->ge->getEndVertex() ? itr->ge->getEndVertex()->tag() : -1)
2493 << ")";
2494 Msg::Info(":-( There are %d intersections in the 1D mesh (curves%s)",
2495 edgesNotRecovered.size(), sstream.str().c_str());
2496 }
2497 if(repairSelfIntersecting1dMesh) {
2498 Msg::Info("8-| Splitting those edges and trying again");
2499 if(gf->meshStatistics.refineAllEdges) {
2500 std::vector<GEdge *> eds = gf->edges();
2501 edgesNotRecovered.clear();
2502 for(size_t i = 0; i < eds.size(); i++) {
2503 const std::size_t NN = eds[i]->lines.size() ? 1 : 0;
2504 for(size_t j = 0; j < NN; j++) {
2505 MVertex *v1 = eds[i]->lines[j]->getVertex(0);
2506 MVertex *v2 = eds[i]->lines[j]->getVertex(1);
2507 auto itp1 = recoverMultiMapInv.lower_bound(v1);
2508 auto itp2 = recoverMultiMapInv.lower_bound(v2);
2509 if(itp1 != recoverMultiMapInv.end() &&
2510 itp2 != recoverMultiMapInv.end())
2511 edgesNotRecovered.insert(
2512 EdgeToRecover(itp1->second->iD, itp2->second->iD, eds[i]));
2513 }
2514 }
2515 }
2516 remeshUnrecoveredEdges(recoverMultiMapInv, edgesNotRecovered,
2517 gf->meshStatistics.refineAllEdges);
2518 gf->meshStatistics.refineAllEdges = false;
2519 }
2520 // delete the mesh
2521 // getchar();
2522 if(debug) {
2523 char name[245];
2524 sprintf(name, "surface%d-initial-real-afterITER%d.pos", gf->tag(),
2525 RECUR_ITER);
2526 outputScalarField(m->triangles, name, 0, gf);
2527 sprintf(name, "surface%d-initial-param-afterITER%d.pos", gf->tag(),
2528 RECUR_ITER);
2529 outputScalarField(m->triangles, name, 1, gf);
2530 }
2531 delete m;
2532 if(RECUR_ITER < 10) {
2533 return meshGeneratorPeriodic(gf, RECUR_ITER + 1,
2534 repairSelfIntersecting1dMesh, debug);
2535 }
2536 return false;
2537 }
2538
2539 if(RECUR_ITER > 0)
2540 Msg::Info(":-) All edges recovered after %d iteration%s", RECUR_ITER,
2541 (RECUR_ITER > 1) ? "s" : "");
2542
2543 // look for a triangle that has a negative node and recursively tag all
2544 // exterior triangles
2545 {
2546 auto itt = m->triangles.begin();
2547 while(itt != m->triangles.end()) {
2548 (*itt)->g = nullptr;
2549 ++itt;
2550 }
2551 itt = m->triangles.begin();
2552 while(itt != m->triangles.end()) {
2553 BDS_Face *t = *itt;
2554 if(t->deleted) {
2555 // If triangle is deleted, it won't have the correct neighbours
2556 // to tag recursively
2557 ++itt;
2558 continue;
2559 }
2560 BDS_Point *n[4];
2561 if(t->getNodes(n)) {
2562 if(n[0]->iD < 0 || n[1]->iD < 0 || n[2]->iD < 0) {
2563 recur_tag(t, &CLASS_EXTERIOR);
2564 break;
2565 }
2566 }
2567 ++itt;
2568 }
2569 }
2570
2571 // now find an edge that has belongs to one of the exterior triangles
2572 {
2573 auto ite = m->edges.begin();
2574 while(ite != m->edges.end()) {
2575 BDS_Edge *edge = *ite;
2576 if(edge->g && edge->numfaces() == 2) {
2577 if(edge->faces(0)->g == &CLASS_EXTERIOR) {
2578 recur_tag(edge->faces(1), &CLASS_F);
2579 break;
2580 }
2581 else if(edge->faces(1)->g == &CLASS_EXTERIOR) {
2582 recur_tag(edge->faces(0), &CLASS_F);
2583 break;
2584 }
2585 }
2586 ++ite;
2587 }
2588 auto itt = m->triangles.begin();
2589 while(itt != m->triangles.end()) {
2590 if((*itt)->g == &CLASS_EXTERIOR) (*itt)->g = nullptr;
2591 ++itt;
2592 }
2593 }
2594
2595 // delete useless stuff
2596 {
2597 auto itt = m->triangles.begin();
2598 while(itt != m->triangles.end()) {
2599 BDS_Face *t = *itt;
2600 if(!t->g) { m->del_face(t); }
2601 ++itt;
2602 }
2603 }
2604
2605 m->cleanup();
2606
2607 {
2608 auto ite = m->edges.begin();
2609 while(ite != m->edges.end()) {
2610 BDS_Edge *edge = *ite;
2611 if(edge->numfaces() == 0)
2612 m->del_edge(edge);
2613 else {
2614 if(!edge->g) edge->g = &CLASS_F;
2615 if(!edge->p1->g ||
2616 edge->p1->g->classif_degree > edge->g->classif_degree)
2617 edge->p1->g = edge->g;
2618 if(!edge->p2->g ||
2619 edge->p2->g->classif_degree > edge->g->classif_degree)
2620 edge->p2->g = edge->g;
2621 }
2622 ++ite;
2623 }
2624 }
2625 m->cleanup();
2626 m->del_point(m->find_point(-1));
2627 m->del_point(m->find_point(-2));
2628 m->del_point(m->find_point(-3));
2629 m->del_point(m->find_point(-4));
2630
2631 if(debug) {
2632 char name[245];
2633 sprintf(name, "surface%d-recovered-real.pos", gf->tag());
2634 outputScalarField(m->triangles, name, 0, gf);
2635 sprintf(name, "surface%d-recovered-param.pos", gf->tag());
2636 outputScalarField(m->triangles, name, 1, gf);
2637 }
2638
2639 if(algoDelaunay2D(gf)) {
2640 // Call this function to untangle elements in Cartesian space
2641 Msg::Debug("Delaunizing the initial mesh");
2642 int nb_swap;
2643 delaunayizeBDS(gf, *m, nb_swap);
2644 }
2645 else {
2646 // tag points that are degenerated
2647 modifyInitialMeshToRemoveDegeneracies(gf, *m, &recoverMap);
2648
2649 Msg::Debug("Delaunizing the initial mesh");
2650 int nb_swap;
2651 delaunayizeBDS(gf, *m, nb_swap);
2652
2653 refineMeshBDS(gf, *m, CTX::instance()->mesh.refineSteps, true, nullptr,
2654 &recoverMap, &true_boundary);
2655 if(debug) {
2656 char name[245];
2657 sprintf(name, "surface%d-phase1-real.pos", gf->tag());
2658 outputScalarField(m->triangles, name, 0, gf);
2659 sprintf(name, "surface%d-phase1-param.pos", gf->tag());
2660 outputScalarField(m->triangles, name, 1, gf);
2661 }
2662 if(debug) {
2663 char name[245];
2664 sprintf(name, "surface%d-phase2-real.pos", gf->tag());
2665 outputScalarField(m->triangles, name, 0, gf);
2666 sprintf(name, "surface%d-phase2-param.pos", gf->tag());
2667 outputScalarField(m->triangles, name, 1, gf);
2668 }
2669 refineMeshBDS(gf, *m, -CTX::instance()->mesh.refineSteps, false, nullptr,
2670 &recoverMap, &true_boundary);
2671 if(debug) {
2672 char name[245];
2673 sprintf(name, "surface%d-phase3-real.pos", gf->tag());
2674 outputScalarField(m->triangles, name, 0);
2675 sprintf(name, "surface%d-phase3-param.pos", gf->tag());
2676 outputScalarField(m->triangles, name, 1, gf);
2677 }
2678 if(debug) {
2679 char name[245];
2680 sprintf(name, "surface%d-phase4-real.pos", gf->tag());
2681 outputScalarField(m->triangles, name, 0);
2682 sprintf(name, "surface%d-phase4-param.pos", gf->tag());
2683 outputScalarField(m->triangles, name, 1, gf);
2684 }
2685
2686 if(gf->meshStatistics.status == GFace::FAILED) {
2687 // splitall
2688 gf->meshStatistics.status = GFace::PENDING;
2689 gf->meshStatistics.refineAllEdges = true;
2690 delete m;
2691 Msg::Info("Serializing surface %d and refining all its bounding edges",
2692 gf->tag());
2693 return true;
2694 }
2695 else {
2696 gf->meshStatistics.status = GFace::DONE;
2697 }
2698
2699 if(debug) {
2700 char name[245];
2701 sprintf(name, "surface%d-just-real.pos", gf->tag());
2702 outputScalarField(m->triangles, name, 0, gf);
2703 }
2704 }
2705
2706 // This is a structure that we need only for periodic cases. We will duplicate
2707 // the vertices (MVertex) that are on seams
2708
2709 std::map<MVertex *, MVertex *> equivalence;
2710 std::map<MVertex *, SPoint2> parametricCoordinates;
2711 if(algoDelaunay2D(gf)) {
2712 std::map<MVertex *, BDS_Point *> invertMap;
2713 auto it = recoverMap.begin();
2714 while(it != recoverMap.end()) {
2715 // we have twice vertex MVertex with 2 different coordinates
2716 MVertex *mv1 = it->second;
2717 BDS_Point *bds = it->first;
2718 auto invIt = invertMap.find(mv1);
2719 if(invIt != invertMap.end()) {
2720 // create a new "fake" vertex that will be destroyed afterwards
2721 MVertex *mv2 = nullptr;
2722 if(mv1->onWhat()->dim() == 1) {
2723 double t;
2724 mv1->getParameter(0, t);
2725 mv2 = new MEdgeVertex(mv1->x(), mv1->y(), mv1->z(), mv1->onWhat(), t,
2726 0, ((MEdgeVertex *)mv1)->getLc());
2727 }
2728 else if(mv1->onWhat()->dim() == 0) {
2729 mv2 = new MVertex(mv1->x(), mv1->y(), mv1->z(), mv1->onWhat());
2730 }
2731 else
2732 Msg::Error("Could not reconstruct seam");
2733 if(mv2) {
2734 it->second = mv2;
2735 equivalence[mv2] = mv1;
2736 parametricCoordinates[mv2] = SPoint2(bds->u, bds->v);
2737 invertMap[mv2] = bds;
2738 }
2739 }
2740 else {
2741 parametricCoordinates[mv1] = SPoint2(bds->u, bds->v);
2742 invertMap[mv1] = bds;
2743 }
2744 ++it;
2745 }
2746 }
2747
2748 // Msg::Info("%d points that are duplicated for Delaunay meshing",
2749 // equivalence.size());
2750
2751 // fill the small gmsh structures
2752 BDS2GMSH(m, gf, recoverMap);
2753
2754 if(debug) {
2755 char name[245];
2756 sprintf(name, "surface%d-final-real.pos", gf->tag());
2757 outputScalarField(m->triangles, name, 0, gf);
2758 sprintf(name, "surface%d-final-param.pos", gf->tag());
2759 outputScalarField(m->triangles, name, 1, gf);
2760 }
2761
2762 bool infty = false;
2763 if(gf->getMeshingAlgo() == ALGO_2D_FRONTAL_QUAD) {
2764 infty = true;
2765 buildBackgroundMesh(gf, CTX::instance()->mesh.crossFieldClosestPoint,
2766 &equivalence, ¶metricCoordinates);
2767 }
2768 else if(gf->getMeshingAlgo() == ALGO_2D_PACK_PRLGRMS ||
2769 gf->getMeshingAlgo() == ALGO_2D_PACK_PRLGRMS_CSTR) {
2770 infty = true;
2771 /* New version of PACK / QUADQS use a different background mesh */
2772 // buildBackgroundMesh(gf, false, &equivalence, ¶metricCoordinates);
2773 }
2774
2775 bool onlyInitialMesh = (gf->getMeshingAlgo() == ALGO_2D_INITIAL_ONLY);
2776
2777 if(!onlyInitialMesh) {
2778 // boundary layer
2779 std::vector<MQuadrangle *> blQuads;
2780 std::vector<MTriangle *> blTris;
2781 std::set<MVertex *> verts;
2782 modifyInitialMeshForBoundaryLayers(gf, blQuads, blTris, verts, debug);
2783 gf->quadrangles.insert(gf->quadrangles.begin(), blQuads.begin(),
2784 blQuads.end());
2785 gf->triangles.insert(gf->triangles.begin(), blTris.begin(), blTris.end());
2786 gf->mesh_vertices.insert(gf->mesh_vertices.begin(), verts.begin(),
2787 verts.end());
2788 }
2789
2790 if(algoDelaunay2D(gf) && !onlyInitialMesh) {
2791 if(gf->getMeshingAlgo() == ALGO_2D_FRONTAL)
2792 bowyerWatsonFrontal(gf, &equivalence, ¶metricCoordinates,
2793 &true_boundary);
2794 else if(gf->getMeshingAlgo() == ALGO_2D_FRONTAL_QUAD)
2795 bowyerWatsonFrontalLayers(gf, true, &equivalence, ¶metricCoordinates);
2796 else if(gf->getMeshingAlgo() == ALGO_2D_PACK_PRLGRMS)
2797 bowyerWatsonParallelograms(gf, &equivalence, ¶metricCoordinates);
2798 else if(gf->getMeshingAlgo() == ALGO_2D_PACK_PRLGRMS_CSTR) {
2799 Msg::Error("ALGO_2D_PACK_PRLGRMS_CSTR deprecated");
2800 // bowyerWatsonParallelogramsConstrained(
2801 // gf, gf->constr_vertices, &equivalence, ¶metricCoordinates);
2802 }
2803 else if(gf->getMeshingAlgo() == ALGO_2D_DELAUNAY ||
2804 gf->getMeshingAlgo() == ALGO_2D_AUTO)
2805 bowyerWatson(gf, 1000000000, &equivalence, ¶metricCoordinates);
2806 else
2807 meshGFaceBamg(gf);
2808 if(!infty ||
2809 !(CTX::instance()->mesh.recombineAll || gf->meshAttributes.recombine))
2810 laplaceSmoothing(gf, CTX::instance()->mesh.nbSmoothing, infty);
2811 }
2812
2813 if(debug) {
2814 char name[256];
2815 sprintf(name, "real%d.pos", gf->tag());
2816 outputScalarField(m->triangles, name, 0, gf);
2817 sprintf(name, "param%d.pos", gf->tag());
2818 outputScalarField(m->triangles, name, 1, gf);
2819 }
2820
2821 // remove fake duplicate nodes on seams
2822 for(auto eq : equivalence) delete eq.first;
2823
2824 // delete the mesh
2825 delete m;
2826
2827 if((CTX::instance()->mesh.recombineAll || gf->meshAttributes.recombine) &&
2828 (CTX::instance()->mesh.algoRecombine <= 1 ||
2829 CTX::instance()->mesh.algoRecombine == 4)) {
2830 bool blossom = (CTX::instance()->mesh.algoRecombine == 1);
2831 int topo = CTX::instance()->mesh.recombineOptimizeTopology;
2832 bool nodeRepositioning = true;
2833 if(/*CTX::instance()->mesh.algo2d == ALGO_2D_PACK_PRLGRMS ||*/
2834 CTX::instance()->mesh.algo2d == ALGO_2D_QUAD_QUASI_STRUCT) {
2835 nodeRepositioning = false;
2836 }
2837 if(CTX::instance()->mesh.algoRecombine == 4)
2838 meshGFaceQuadrangulateBipartiteLabelling(gf->tag());
2839 else {
2840 recombineIntoQuads(gf, blossom, topo, nodeRepositioning, 0.1);
2841 }
2842 }
2843
2844 computeElementShapes(gf, gf->meshStatistics.worst_element_shape,
2845 gf->meshStatistics.average_element_shape,
2846 gf->meshStatistics.best_element_shape,
2847 gf->meshStatistics.nbTriangle,
2848 gf->meshStatistics.nbGoodQuality);
2849 gf->meshStatistics.status = GFace::DONE;
2850
2851 // Remove unused vertices, generated e.g. during background mesh
2852 _deleteUnusedVertices(gf);
2853
2854 return true;
2855 }
2856
operator ()(GFace * gf)2857 void deMeshGFace::operator()(GFace *gf)
2858 {
2859 if(gf->isFullyDiscrete()) return;
2860 gf->deleteMesh();
2861 gf->meshStatistics.status = GFace::PENDING;
2862 gf->meshStatistics.nbTriangle = gf->meshStatistics.nbEdge = 0;
2863 }
2864
TRIANGLE_VALIDITY(GFace * gf,MTriangle * t)2865 static double TRIANGLE_VALIDITY(GFace *gf, MTriangle *t)
2866 {
2867 SPoint2 p1, p2, p3;
2868 reparamMeshVertexOnFace(t->getVertex(0), gf, p1);
2869 reparamMeshVertexOnFace(t->getVertex(1), gf, p2);
2870 reparamMeshVertexOnFace(t->getVertex(2), gf, p3);
2871 SVector3 N1 = gf->normal(p1);
2872 SVector3 N2 = gf->normal(p2);
2873 SVector3 N3 = gf->normal(p3);
2874 SVector3 N = N1 + N2 + N3;
2875 N.normalize();
2876 SVector3 d1(t->getVertex(1)->x() - t->getVertex(0)->x(),
2877 t->getVertex(1)->y() - t->getVertex(0)->y(),
2878 t->getVertex(1)->z() - t->getVertex(0)->z());
2879 SVector3 d2(t->getVertex(2)->x() - t->getVertex(0)->x(),
2880 t->getVertex(2)->y() - t->getVertex(0)->y(),
2881 t->getVertex(2)->z() - t->getVertex(0)->z());
2882 SVector3 c = crossprod(d1, d2);
2883 return dot(N, c);
2884 }
2885
isMeshValid(GFace * gf)2886 static bool isMeshValid(GFace *gf)
2887 {
2888 size_t invalid = 0;
2889 for(size_t i = 0; i < gf->triangles.size(); i++) {
2890 double v = TRIANGLE_VALIDITY(gf, gf->triangles[i]);
2891 if(v < 0) invalid++;
2892 }
2893 if(invalid == 0 || invalid == gf->triangles.size()) return true;
2894
2895 return false;
2896 }
2897
2898 // for debugging, change value from -1 to -100;
2899 int debugSurface = -1; //-100;
2900
operator ()(GFace * gf,bool print)2901 void meshGFace::operator()(GFace *gf, bool print)
2902 {
2903 gf->model()->setCurrentMeshEntity(gf);
2904
2905 if(gf->meshAttributes.method == MESH_NONE) return;
2906 if(CTX::instance()->mesh.meshOnlyVisible && !gf->getVisibility()) return;
2907 if(CTX::instance()->mesh.meshOnlyEmpty && gf->getNumMeshElements()) return;
2908
2909 // destroy the mesh if it exists
2910 deMeshGFace dem;
2911 dem(gf);
2912
2913 if(MeshTransfiniteSurface(gf)) return;
2914 if(MeshExtrudedSurface(gf)) return;
2915 if(gf->getMeshMaster() != gf) {
2916 GFace *gff = dynamic_cast<GFace *>(gf->getMeshMaster());
2917 if(gff) {
2918 if(gff->meshStatistics.status != GFace::DONE) {
2919 gf->meshStatistics.status = GFace::PENDING;
2920 return;
2921 }
2922 Msg::Info("Meshing surface %d (%s) as a copy of surface %d", gf->tag(),
2923 gf->getTypeString().c_str(), gf->getMeshMaster()->tag());
2924 copyMesh(gff, gf);
2925 gf->meshStatistics.status = GFace::DONE;
2926 return;
2927 }
2928 else
2929 Msg::Warning("Unknown mesh master surface %d",
2930 gf->getMeshMaster()->tag());
2931 }
2932
2933 /* The ALGO_2D_QUAD_QUASI_STRUCT is using ALGO_2D_PACK_PRLGRMS
2934 * to generate a initial quad-dominant mesh */
2935 bool quadqs = false;
2936 if(CTX::instance()->mesh.algo2d == ALGO_2D_QUAD_QUASI_STRUCT) {
2937 quadqs = true;
2938 CTX::instance()->mesh.algo2d = ALGO_2D_PACK_PRLGRMS;
2939 }
2940
2941 const char *algo = "Unknown";
2942
2943 switch(gf->getMeshingAlgo()) {
2944 case ALGO_2D_MESHADAPT: algo = "MeshAdapt"; break;
2945 case ALGO_2D_AUTO:
2946 algo = (gf->geomType() == GEntity::Plane) ? "Delaunay" : "MeshAdapt";
2947 break;
2948 case ALGO_2D_INITIAL_ONLY: algo = "Initial Mesh Only"; break;
2949 case ALGO_2D_DELAUNAY: algo = "Delaunay"; break;
2950 case ALGO_2D_FRONTAL: algo = "Frontal-Delaunay"; break;
2951 case ALGO_2D_BAMG: algo = "Bamg"; break;
2952 case ALGO_2D_FRONTAL_QUAD: algo = "Frontal-Delaunay for Quads"; break;
2953 case ALGO_2D_PACK_PRLGRMS: algo = "Packing of Parallelograms"; break;
2954 case ALGO_2D_PACK_PRLGRMS_CSTR:
2955 algo = "Packing of Parallelograms Constrained";
2956 break;
2957 }
2958
2959 if(print)
2960 Msg::Info("Meshing surface %d (%s, %s)", gf->tag(),
2961 gf->getTypeString().c_str(), algo);
2962
2963 bool singularEdges = false;
2964 auto ite = gf->edges().begin();
2965 while(ite != gf->edges().end()) {
2966 if((*ite)->isSeam(gf)) singularEdges = true;
2967 ite++;
2968 }
2969
2970 bool periodic = (gf->getNativeType() != GEntity::GmshModel) &&
2971 (gf->periodic(0) || gf->periodic(1) || singularEdges);
2972
2973 quadMeshRemoveHalfOfOneDMesh halfmesh(gf, periodic);
2974
2975 if(periodic) {
2976 if(!meshGeneratorPeriodic(gf, 0, repairSelfIntersecting1dMesh,
2977 debugSurface >= 0 || debugSurface == -100)) {
2978 Msg::Error("Impossible to mesh periodic surface %d", gf->tag());
2979 gf->meshStatistics.status = GFace::FAILED;
2980 }
2981 }
2982 else {
2983 meshGenerator(gf, 0, repairSelfIntersecting1dMesh,
2984 gf->getMeshingAlgo() == ALGO_2D_INITIAL_ONLY,
2985 debugSurface >= 0 || debugSurface == -100);
2986 }
2987
2988 Msg::Debug("Type %d %d triangles generated, %d internal nodes",
2989 gf->geomType(), gf->triangles.size(), gf->mesh_vertices.size());
2990
2991 halfmesh.finish();
2992
2993 if(gf->getNumMeshElements() == 0 &&
2994 gf->meshStatistics.status == GFace::DONE) {
2995 Msg::Warning("Surface %d consists of no elements", gf->tag());
2996 }
2997
2998 // test validity for non-Gmsh models (currently we cannot reliably evaluate
2999 // the normal on the boundary of surfaces with the Gmsh kernel)
3000 if(CTX::instance()->mesh.algoSwitchOnFailure &&
3001 gf->getNativeType() != GEntity::GmshModel &&
3002 gf->geomType() != GEntity::Plane && algoDelaunay2D(gf) &&
3003 !isMeshValid(gf)) {
3004 Msg::Debug(
3005 "Delaunay-based mesher failed on surface %d -> moving to MeshAdapt",
3006 gf->tag());
3007 deMeshGFace killer;
3008 killer(gf);
3009 gf->setMeshingAlgo(1);
3010 (*this)(gf, print);
3011 gf->unsetMeshingAlgo();
3012 }
3013
3014 if(quadqs) CTX::instance()->mesh.algo2d = ALGO_2D_QUAD_QUASI_STRUCT;
3015 }
3016
getGFaceNormalFromVert(GFace * gf,MElement * el,SVector3 & nf)3017 static bool getGFaceNormalFromVert(GFace *gf, MElement *el, SVector3 &nf)
3018 {
3019 bool found = false;
3020 for(std::size_t iElV = 0; iElV < el->getNumVertices(); iElV++) {
3021 MVertex *v = el->getVertex(iElV);
3022 SPoint2 param;
3023 if(v->onWhat() == gf && v->getParameter(0, param[0]) &&
3024 v->getParameter(1, param[1])) {
3025 nf = gf->normal(param);
3026 found = true;
3027 break;
3028 }
3029 }
3030 return found;
3031 }
3032
getGFaceNormalFromBary(GFace * gf,MElement * el,SVector3 & nf)3033 static bool getGFaceNormalFromBary(GFace *gf, MElement *el, SVector3 &nf)
3034 {
3035 SPoint2 param(0., 0.);
3036 bool ok = true;
3037 for(std::size_t j = 0; j < el->getNumVertices(); j++) {
3038 SPoint2 p;
3039 // FIXME: use inexact reparam because some vertices might not be exactly on
3040 // the surface after the 3D Delaunay
3041 ok = reparamMeshVertexOnFace(el->getVertex(j), gf, p, false);
3042 if(!ok) break;
3043 param += p;
3044 }
3045 if(ok) {
3046 param *= 1.0 / el->getNumVertices();
3047 nf = gf->normal(param);
3048 }
3049 return ok;
3050 }
3051
getGFaceOrientation(GFace * gf,BoundaryLayerColumns * blc,bool existBL,bool fromVert,int & orientNonBL,int & orientBL)3052 static void getGFaceOrientation(GFace *gf, BoundaryLayerColumns *blc,
3053 bool existBL, bool fromVert, int &orientNonBL,
3054 int &orientBL)
3055 {
3056 for(std::size_t iEl = 0; iEl < gf->getNumMeshElements(); iEl++) {
3057 MElement *e = gf->getMeshElement(iEl);
3058 const bool isBLEl =
3059 existBL && (blc->_toFirst.find(e) != blc->_toFirst.end());
3060 SVector3 nf;
3061 // Check only if orientation of BL/non-BL el. not already known
3062 if((!isBLEl && orientNonBL == 0) || (isBLEl && orientBL == 0)) {
3063 const bool found = fromVert ? getGFaceNormalFromVert(gf, e, nf) :
3064 getGFaceNormalFromBary(gf, e, nf);
3065 if(found) {
3066 SVector3 ne = e->getFace(0).normal();
3067 const int orient = (dot(ne, nf) > 0.) ? 1 : -1;
3068 if(isBLEl)
3069 orientBL = orient;
3070 else
3071 orientNonBL = orient;
3072 }
3073 }
3074 // Stop when orientation found for non-BL and BL el.
3075 if((orientNonBL != 0) && (orientBL != 0)) break;
3076 }
3077 }
3078
operator ()(GFace * gf)3079 void orientMeshGFace::operator()(GFace *gf)
3080 {
3081 if(!gf->getNumMeshElements()) return;
3082
3083 gf->model()->setCurrentMeshEntity(gf);
3084
3085 if(gf->getMeshMaster() != gf) {
3086 // It's not clear if periodic meshes should be orientated according to the
3087 // orientation of the underlying CAD surface. Since we don't reorient
3088 // periodic curve meshes, let's also not reorient surface meshes for
3089 // now. This has implications for high-order periodic meshes: see comment in
3090 // FixPeriodicMesh().
3091 }
3092 else if(gf->isFullyDiscrete() ||
3093 gf->geomType() == GEntity::BoundaryLayerSurface) {
3094 // Don't do anything
3095 }
3096 else {
3097 // In old versions we checked the orientation by comparing the orientation
3098 // of a line element on the boundary w.r.t. its connected surface
3099 // element. This is probably better than what follows, but
3100 // * it failed when the 3D Delaunay changes the 1D mesh (since we don't
3101 // recover it yet)
3102 // * it failed with OpenCASCADE geometries, where surface orientions do not
3103 // seem to be consistent with the orientation of the bounding edges
3104
3105 // Now: orient surface elements w.r.t. normal to geometric model.
3106 // Assumes that originally, orientation is consistent among boundary layer
3107 // (BL) elements, and orientation is consistent among non-BL elements, but
3108 // BL and non-BL elements can be oriented differently
3109
3110 // Determine whether there is a boundary layer (BL)
3111 BoundaryLayerColumns *blc = gf->getColumns();
3112 const bool existBL = !blc->_toFirst.empty();
3113
3114 // Get orientation of BL and non-BL elements.
3115 // First, try to get normal to GFace from vertices.
3116 // If it fails, try to get normal to GFace from element barycenter
3117 int orientNonBL = 0, orientBL = existBL ? 0 : 1;
3118 getGFaceOrientation(gf, blc, existBL, true, orientNonBL, orientBL);
3119 if((orientNonBL == 0) || (orientBL == 0))
3120 getGFaceOrientation(gf, blc, existBL, false, orientNonBL, orientBL);
3121
3122 // Exit if could not determine orientation of both non-BL el. and BL el.
3123 if((orientNonBL == 0) && (orientBL == 0)) {
3124 Msg::Warning("Could not orient mesh in surface %d", gf->tag());
3125 return;
3126 }
3127
3128 // Reverse BL and non-BL elements if needed
3129 if(existBL) { // If there is a BL, test BL/non-BL elements
3130 if((orientNonBL == -1) || (orientBL == -1)) {
3131 for(std::size_t iEl = 0; iEl < gf->getNumMeshElements(); iEl++) {
3132 MElement *e = gf->getMeshElement(iEl);
3133 // If el. outside of BL...
3134 if(blc->_toFirst.find(e) == blc->_toFirst.end()) {
3135 // ... reverse if needed
3136 if(orientNonBL == -1) e->reverse();
3137 }
3138 else { // If el. in BL ... reverse if needed
3139 if(orientBL == -1) e->reverse();
3140 }
3141 }
3142 }
3143 }
3144 else { // If no BL, reverse all elements if needed
3145 if(orientNonBL == -1) {
3146 for(std::size_t iEl = 0; iEl < gf->getNumMeshElements(); iEl++)
3147 gf->getMeshElement(iEl)->reverse();
3148 }
3149 }
3150 }
3151
3152 // Apply user-specified mesh orientation constraints
3153 if(gf->meshAttributes.reverseMesh) {
3154 for(std::size_t k = 0; k < gf->getNumMeshElements(); k++)
3155 gf->getMeshElement(k)->reverse();
3156 }
3157 }
3158