MeshManipulation.cc 15.2 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
//
// Software License for AMDiS
//
// Copyright (c) 2010 Dresden University of Technology 
// All rights reserved.
// Authors: Simon Vey, Thomas Witkowski et al.
//
// This file is part of AMDiS
//
// See also license.opensource.txt in the distribution.


13
14
#include "parallel/MeshManipulation.h"
#include "Mesh.h"
15
#include "MeshStructure.h"
16
#include "BasisFunction.h"
17
#include "Traverse.h"
18
#include "Debug.h"
19
20
21

namespace AMDiS {

22
23
  MeshManipulation::MeshManipulation(Mesh *m)
    : mesh(m)
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
  {
    switch (mesh->getDim()) {
    case 2:
      refineManager = new RefinementManager2d();
      break;
    case 3:
      refineManager = new RefinementManager3d();
      break;
    default:
      ERROR_EXIT("invalid dim!\n");
    }
  }


  MeshManipulation::~MeshManipulation()
  {
    delete refineManager;
  }


44
  void MeshManipulation::deleteDoubleDofs(vector<const FiniteElemSpace*>& feSpaces,
45
					  std::set<MacroElement*>& newMacroEl, 
46
					  ElementObjects &objects)
47
  {
48
49
    FUNCNAME("MeshManipulation::deleteDoubleDofs()");

50
51
52
53
54
    // Search for the FE space with the highest degree of polynomials. Using this
    // FE space ensures that deleting DOFs defined on it, also DOFs of lower 
    // order FE spaces will be deleted correctly.
    const FiniteElemSpace *feSpace = FiniteElemSpace::getHighest(feSpaces);

55
56
    // Create data structure that maps macro element indices to the 
    // corresponding pointers.
57
    map<int, MacroElement*> macroIndexMap;
58
59
60
61
    for (std::set<MacroElement*>::iterator it = newMacroEl.begin();
	 it != newMacroEl.end(); ++it)
      macroIndexMap[(*it)->getIndex()] = *it;

62
    // === Traverse mesh and put all "old" macro element to macrosProcessed  ===
63
    // === that stores all macro elements which are really connected to the  ===
64
    // === overall mesh structure.                                           ===
65

66
    std::set<int> macrosProcessed;   
67
    TraverseStack stack;
68
    ElInfo *elInfo = stack.traverseFirst(mesh, 0, Mesh::CALL_EL_LEVEL);
69
    while (elInfo) {
70
71
72
73
74
75
76
      if (newMacroEl.count(elInfo->getMacroElement()) == 0) {
	int index = elInfo->getMacroElement()->getIndex();

	macrosProcessed.insert(index);
	macroIndexMap[index] = elInfo->getMacroElement();
      }

77
78
79
80
      elInfo = stack.traverseNext(elInfo);
    }


81
82
83
84
    // === Traverse all new elements and connect them to the overall mesh     ===
    // === structure by deleting all double DOFs on macro element's vertices, ===
    // === edges and faces.                                                   ===

85
86
87
    map<const DegreeOfFreedom*, const DegreeOfFreedom*> mapDelDofs;
    map<const DegreeOfFreedom*, GeoIndex> dofPosIndex;

88
89
    for (std::set<MacroElement*>::iterator it = newMacroEl.begin(); 
	 it != newMacroEl.end(); ++it) {
90

91
92
      // === Traverse all vertices of the new element. ===

93
      for (int i = 0; i < mesh->getGeo(VERTEX); i++) {
94
95
	vector<ElementObjectData> &vertexEl = 
	  objects.getElementsVertex((*it)->getIndex(), i);
96

97
	for (vector<ElementObjectData>::iterator elIt = vertexEl.begin();
98
99
100
	     elIt != vertexEl.end(); ++elIt) {
	  if (elIt->elIndex == (*it)->getIndex())
	    continue;
101

102
103
104
105
106
107
108
109
110
111
112
	  if (macrosProcessed.count(elIt->elIndex) == 1) {
	    TEST_EXIT_DBG(macroIndexMap.count(elIt->elIndex) == 1)
	      ("Should not happen!\n");

	    Element *el0 = (*it)->getElement();
	    Element *el1 = macroIndexMap[elIt->elIndex]->getElement();

	    const DegreeOfFreedom *dof0 = el0->getDof(i);
	    const DegreeOfFreedom *dof1 = el1->getDof(elIt->ithObject);

	    mapDelDofs[dof0] = dof1;
113
114
	    dofPosIndex[dof0] = VERTEX;

115
116
117
118
119
120
121
122
	    break;
	  } 
	}
      }

      for (int i = 0; i < mesh->getGeo(EDGE); i++) {
	ElementObjectData elObj((*it)->getIndex(), i);

123
124
125
126
	vector<ElementObjectData> &edgeEl = 
	  objects.getElementsEdge((*it)->getIndex(), i);

	for (vector<ElementObjectData>::iterator elIt = edgeEl.begin();
127
128
129
130
131
	     elIt != edgeEl.end(); ++elIt) {
	  if (elIt->elIndex == (*it)->getIndex())
	    continue;

	  if (macrosProcessed.count(elIt->elIndex) == 1) {
132
133
	    TEST_EXIT_DBG(macroIndexMap.count(elIt->elIndex))
	      ("Should not happen!\n");
134
135
136
137

	    Element *el0 = (*it)->getElement();	    
	    Element *el1 = macroIndexMap[elIt->elIndex]->getElement();

138
139
140
	    bool reverseMode = objects.getEdgeReverseMode(elObj, *elIt);

	    BoundaryObject b0(el0, 0, EDGE, i, reverseMode);
141
142
143
144
	    BoundaryObject b1(el1, 0, EDGE, elIt->ithObject, false);

	    DofContainer dofs0, dofs1;
	    
145
146
	    el0->getAllDofs(feSpace, b0, dofs0);
	    el1->getAllDofs(feSpace, b1, dofs1);
147
148

#if (DEBUG != 0)
Thomas Witkowski's avatar
Merge    
Thomas Witkowski committed
149
	    debug::testDofsByCoords(feSpace, dofs0, dofs1);
150
151
#endif

152
 	    for (unsigned int i = 0; i < dofs0.size(); i++) {
153
 	      mapDelDofs[dofs0[i]] = dofs1[i];
154
155
	      dofPosIndex[dofs0[i]] = EDGE;
	    }
156
157

	    break;
158
159
160
161
	  }
	}
      }

162

163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
      for (int i = 0; i < mesh->getGeo(FACE); i++) {
	ElementObjectData elObj((*it)->getIndex(), i);

	vector<ElementObjectData> &faceEl = 
	  objects.getElementsFace((*it)->getIndex(), i);

	for (vector<ElementObjectData>::iterator elIt = faceEl.begin();
	     elIt != faceEl.end(); ++elIt) {
	  if (elIt->elIndex == (*it)->getIndex())
	    continue;

	  if (macrosProcessed.count(elIt->elIndex) == 1) {
	    TEST_EXIT_DBG(macroIndexMap.count(elIt->elIndex))("Should not happen!\n");

	    Element *el0 = (*it)->getElement();	    
	    Element *el1 = macroIndexMap[elIt->elIndex]->getElement();

	    bool reverseMode = objects.getFaceReverseMode(elObj, *elIt);

	    BoundaryObject b0(el0, 0, FACE, i, reverseMode);
	    BoundaryObject b1(el1, 0, FACE, elIt->ithObject, false);

	    DofContainer dofs0, dofs1;
	    
187
188
	    el0->getAllDofs(feSpace, b0, dofs0);
	    el1->getAllDofs(feSpace, b1, dofs1);
189
190

#if (DEBUG != 0)
Thomas Witkowski's avatar
Merge    
Thomas Witkowski committed
191
	    debug::testDofsByCoords(feSpace, dofs0, dofs1);
192
193
#endif

194
 	    for (unsigned int i = 0; i < dofs0.size(); i++) {
195
 	      mapDelDofs[dofs0[i]] = dofs1[i];
196
197
	      dofPosIndex[dofs0[i]] = FACE;
	    }
198
199
200
201
202

	    break;
	  }
	}
      }
203
204

      macrosProcessed.insert((*it)->getIndex());
205
206
    }

207

208
209
    // === Remove all DOF replacments of the form A -> B, B -> C by A -> C. ===

210
211
212
    bool changed = false;
    do {
      changed = false;
213
      for (map<const DegreeOfFreedom*, const DegreeOfFreedom*>::iterator it = mapDelDofs.begin();
214
	   it != mapDelDofs.end(); ++it) {
215
	map<const DegreeOfFreedom*, const DegreeOfFreedom*>::iterator findIt = mapDelDofs.find(it->second);
216
	if (findIt != mapDelDofs.end()) {
217
218
219
	  TEST_EXIT_DBG(it->first != findIt->second)
	    ("Cycle %d -> %d and %d -> %d! Should not happen!\n",
	     *(it->first), *(it->second), *(findIt->first), *(findIt->second));
220
221
222
223
224
225
226
	  it->second = findIt->second;   
	  changed = true;
	}
      } 
    } while (changed);


227
228
    // === Set new DOF pointers in all elements of the mesh. ===

229
    elInfo = stack.traverseFirst(mesh, -1, Mesh::CALL_EVERY_EL_PREORDER);
230
    while (elInfo) {
231
      for (int i = 0; i < mesh->getNumberOfNodes(); i++)
232
	if (mapDelDofs.count(elInfo->getElement()->getDof(i)) == 1)
233
	  elInfo->getElement()->setDof(i, const_cast<DegreeOfFreedom*>(mapDelDofs[elInfo->getElement()->getDof(i)]));
234
235
236
237

      elInfo = stack.traverseNext(elInfo);
    }

238

239
240
    // === And delete all double DOFs. ===

241
    for (map<const DegreeOfFreedom*, const DegreeOfFreedom*>::iterator it = mapDelDofs.begin();
242
	 it != mapDelDofs.end(); ++it)
243
244
245
      mesh->freeDof(const_cast<DegreeOfFreedom*>(it->first), VERTEX);
  }

246

247
248
  bool MeshManipulation::fitElementToMeshCode(MeshStructure &code,
					      BoundaryObject &boundEl)
249
  {
250
    FUNCNAME("MeshManipulation::fitElementToMeshCode()");
251

252
    TEST_EXIT_DBG(boundEl.el)("No element given!\n");
253
254
255
256
257
258
259
260
261

    // If the code is empty, the element does not matter and the function can
    // return without chaning the mesh.
    if (code.empty())
      return false;

    // s0 and s1 are the number of the edge/face in both child of the element,
    // which contain the edge/face the function has to traverse through. If the
    // edge/face is not contained in one of the children, s0 or s1 is -1.
262
263
264
265
    int s0 = boundEl.el->getSubObjOfChild(0, boundEl.subObj, 
					  boundEl.ithObj, boundEl.elType);
    int s1 = boundEl.el->getSubObjOfChild(1, boundEl.subObj, 
					  boundEl.ithObj, boundEl.elType);
266
267
268
269
270
271
272
273
274

    TEST_EXIT_DBG(s0 != -1 || s1 != -1)("This should not happen!\n");

    bool meshChanged = false;
    Flag traverseFlag = 
      Mesh::CALL_EVERY_EL_PREORDER | Mesh::FILL_NEIGH | Mesh::FILL_BOUND;

    // Test for reverse mode, in which the left and right children of elements
    // are flipped.
275
    if (boundEl.reverseMode)
276
277
278
279
280
      traverseFlag |= Mesh::CALL_REVERSE_MODE;    


    // === If the edge/face is contained in both children. ===

281
282
    Mesh *mesh = boundEl.el->getMesh();

283
284
285
286
    if (s0 != -1 && s1 != -1) {
      // Create traverse stack and traverse within the mesh until the element,
      // which should be fitted to the mesh structure code, is reached.
      TraverseStack stack;
287
288
      ElInfo *elInfo = stack.traverseFirst(mesh, -1, traverseFlag);
      while (elInfo && elInfo->getElement() != boundEl.el)
289
290
	elInfo = stack.traverseNext(elInfo);      

291
      TEST_EXIT_DBG(elInfo->getElement() == boundEl.el)("This should not happen!\n");
292

293
294
      return fitElementToMeshCode(code, stack, boundEl.subObj, 
				  boundEl.ithObj, boundEl.reverseMode);
295
296
297
298
299
    }


    // === The edge/face is contained in only on of the both children. ===

300
    if (boundEl.el->isLeaf()) {
301
302
303
304
305
306
307

      // If element is leaf and code contains only one leaf element, we are finished.
      if (code.getNumElements() == 1 && code.isLeafElement())
	return false;     

      // Create traverse stack and traverse the mesh to the element.
      TraverseStack stack;
308
309
      ElInfo *elInfo = stack.traverseFirst(mesh, -1, traverseFlag);
      while (elInfo && elInfo->getElement() != boundEl.el)
310
311
312
313
314
	elInfo = stack.traverseNext(elInfo);      

      TEST_EXIT_DBG(elInfo)("This should not happen!\n");

      // Code is not leaf, therefore refine the element.
315
316
      boundEl.el->setMark(1);
      refineManager->setMesh(boundEl.el->getMesh());
317
318
319
320
321
      refineManager->setStack(&stack);
      refineManager->refineFunction(elInfo);
      meshChanged = true;
    }

322
323
324
    Element *child0 = boundEl.el->getFirstChild();
    Element *child1 = boundEl.el->getSecondChild();
    if (boundEl.reverseMode) {
325
326
327
328
329
330
331
332
333
      swap(s0, s1);
      swap(child0, child1);    
    }

    // === We know that the edge/face is contained in only one of the children. ===
    // === Therefore, traverse the mesh to this children and fit this element   ===
    // === To the mesh structure code.                                          ===

    TraverseStack stack;
334
    ElInfo *elInfo = stack.traverseFirst(mesh, -1, traverseFlag);
335
336
337
338
339

    if (s0 != -1) {
      while (elInfo && elInfo->getElement() != child0)
	elInfo = stack.traverseNext(elInfo);     

340
341
      meshChanged |= 
	fitElementToMeshCode(code, stack, boundEl.subObj, s0, boundEl.reverseMode);
342
343
344
345
    } else {
      while (elInfo && elInfo->getElement() != child1) 
	elInfo = stack.traverseNext(elInfo);      

346
347
      meshChanged |= 
	fitElementToMeshCode(code, stack, boundEl.subObj, s1, boundEl.reverseMode);
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
    }


    return meshChanged;
  }


  bool MeshManipulation::fitElementToMeshCode(MeshStructure &code, 
					      TraverseStack &stack,
					      GeoIndex subObj,
					      int ithObj, 
					      bool reverseMode)
  {
    FUNCNAME("MeshManipulation::fitElementToMeshCode()");


    // === Test if there are more elements in stack to check with the code. ===

    ElInfo *elInfo = stack.getElInfo();
    if (!elInfo)
      return false;


    // === Test if code contains a leaf element. If this is the case, the ===
    // === current element is finished. Traverse the mesh to the next     ===
    // === coarser element.                                               ===

    if (code.isLeafElement()) {
      int level = elInfo->getLevel();

      do {
	elInfo = stack.traverseNext(elInfo);
      } while (elInfo && elInfo->getLevel() > level);

      return false;
    }


    bool meshChanged = false;
    Element *el = elInfo->getElement();
388
389
    int s0 = el->getSubObjOfChild(0, subObj, ithObj, elInfo->getType());
    int s1 = el->getSubObjOfChild(1, subObj, ithObj, elInfo->getType());
390
391
392

    // === If element is leaf (and the code is not), refine the element. ===

393
394
    bool elementRefined = true;

395
396
397
    if (el->isLeaf()) {
      TEST_EXIT_DBG(elInfo->getLevel() < 255)("This should not happen!\n");

398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
      // In some situations refinement of an element can be omitted, altough 
      // it is defined in the mesh structure code. One case is when the
      // following holds:
      //   - the code is used to adapt a face of a tetrahedron
      //   - only one of the children of the current element contains this face
      //   - the face to be adapted of the current element is either the
      //     local face 0 or 1
      //   - the next structure code is 0, i.e., we would be finished after
      //     the refinement of this element
      // In this scenario, the element must be refined due to the structure
      // code, but the refinement does not introduce new DOFs on the face,
      // that should be adapted. Thus, we can ommit the refinement.
      if (subObj == FACE) {
  	if (s0 != -1 && s1 == -1 || s0 == -1 && s1 != -1) {
  	  if (ithObj <= 1 && code.lookAhead() == 0) {
  	    elementRefined = false;
 	    code.nextElement();
 	    stack.traverseNext(elInfo);
  	  }
  	}
      }
419

420
421
422
423
424
425
426
427
      if (elementRefined) {
 	MeshStructure t = code;
	el->setMark(1);
	refineManager->setMesh(el->getMesh());
	refineManager->setStack(&stack);
	refineManager->refineFunction(elInfo);
	meshChanged = true;
      } 
428
429
430
    }


431
432
433
434
435
436
437
438
439
440
    if (elementRefined) {
      // === Continue fitting the mesh structure code to the children of the ===
      // === current element.                                                ===
      
      Element *child0 = el->getFirstChild();
      Element *child1 = el->getSecondChild();
      if (reverseMode) {
	swap(s0, s1);
	swap(child0, child1);
      }
441

442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
    
      // === Traverse left child. ===
      
      if (s0 != -1) {
	// The edge/face is contained in the left child, therefore fit this
	// child to the mesh structure code.
	
	stack.traverseNext(elInfo);
	code.nextElement();
	meshChanged |= fitElementToMeshCode(code, stack, subObj, s0, reverseMode);
	elInfo = stack.getElInfo();
      } else {
	// The edge/face is not contained in the left child. Hence we need
	// to traverse through all subelements of the left child until we get
	// the second child of the current element.
	
	do {
	  elInfo = stack.traverseNext(elInfo);
	} while (elInfo && elInfo->getElement() != child1); 
	
	TEST_EXIT_DBG(elInfo != NULL)("This should not happen!\n");
      }  
      
      TEST_EXIT_DBG(elInfo->getElement() == child1)
	("Got wrong child with idx = %d! Searched for child idx = %d\n",
	 elInfo->getElement()->getIndex(), child1->getIndex());
      
      
      // === Traverse right child. ===
      
      if (s1 != -1) {
	// The edge/face is contained in the right child, therefore fit this
	// child to the mesh structure code.
	
	code.nextElement();
	meshChanged |= fitElementToMeshCode(code, stack, subObj, s1, reverseMode);
      } else {
	// The edge/face is not contained in the right child. Hence we need
	// to traverse through all subelements of the right child until we have
	// finished traversing the current element with all its subelements.
	
	int level = elInfo->getLevel();
	
	do {
	  elInfo = stack.traverseNext(elInfo);
	} while (elInfo && elInfo->getLevel() > level);
      }
      
490
    }
491
      
492
493
    return meshChanged;
  }
494
  
495
}