MeshManipulation.cc 14.7 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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
  MeshManipulation::MeshManipulation(FiniteElemSpace *space)
    : feSpace(space),
      mesh(space->getMesh())
  {
    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;
  }


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

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

    std::set<int> macrosProcessed;
58
    map<const DegreeOfFreedom*, const DegreeOfFreedom*> mapDelDofs;
59

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

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

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

75
76
77
78
      elInfo = stack.traverseNext(elInfo);
    }


79
80
81
82
    // === 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.                                                   ===

83
84
    for (std::set<MacroElement*>::iterator it = newMacroEl.begin(); 
	 it != newMacroEl.end(); ++it) {
85

86
87
      // === Traverse all vertices of the new element. ===

88
      for (int i = 0; i < mesh->getGeo(VERTEX); i++) {
89
90
	vector<ElementObjectData> &vertexEl = 
	  objects.getElementsVertex((*it)->getIndex(), i);
91

92
	for (vector<ElementObjectData>::iterator elIt = vertexEl.begin();
93
94
95
	     elIt != vertexEl.end(); ++elIt) {
	  if (elIt->elIndex == (*it)->getIndex())
	    continue;
96

97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
	  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;
    
	    break;
	  } 
	}
      }

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

117
118
119
120
	vector<ElementObjectData> &edgeEl = 
	  objects.getElementsEdge((*it)->getIndex(), i);

	for (vector<ElementObjectData>::iterator elIt = edgeEl.begin();
121
122
123
124
125
	     elIt != edgeEl.end(); ++elIt) {
	  if (elIt->elIndex == (*it)->getIndex())
	    continue;

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

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

131
132
133
	    bool reverseMode = objects.getEdgeReverseMode(elObj, *elIt);

	    BoundaryObject b0(el0, 0, EDGE, i, reverseMode);
134
135
136
137
	    BoundaryObject b1(el1, 0, EDGE, elIt->ithObject, false);

	    DofContainer dofs0, dofs1;
	    
138
139
	    el0->getAllDofs(feSpace, b0, dofs0);
	    el1->getAllDofs(feSpace, b1, dofs1);
140
141

#if (DEBUG != 0)
Thomas Witkowski's avatar
Merge    
Thomas Witkowski committed
142
	    debug::testDofsByCoords(feSpace, dofs0, dofs1);
143
144
145
146
147
148
#endif

 	    for (unsigned int i = 0; i < dofs0.size(); i++)
 	      mapDelDofs[dofs0[i]] = dofs1[i];

	    break;
149
150
151
152
	  }
	}
      }

153

154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
      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;
	    
178
179
	    el0->getAllDofs(feSpace, b0, dofs0);
	    el1->getAllDofs(feSpace, b1, dofs1);
180
181

#if (DEBUG != 0)
Thomas Witkowski's avatar
Merge    
Thomas Witkowski committed
182
	    debug::testDofsByCoords(feSpace, dofs0, dofs1);
183
184
185
186
187
188
189
190
191
#endif

 	    for (unsigned int i = 0; i < dofs0.size(); i++)
 	      mapDelDofs[dofs0[i]] = dofs1[i];

	    break;
	  }
	}
      }
192
193

      macrosProcessed.insert((*it)->getIndex());
194
195
    }

196

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

199
200
201
    bool changed = false;
    do {
      changed = false;
202
      for (map<const DegreeOfFreedom*, const DegreeOfFreedom*>::iterator it = mapDelDofs.begin();
203
	   it != mapDelDofs.end(); ++it) {
204
	map<const DegreeOfFreedom*, const DegreeOfFreedom*>::iterator findIt = mapDelDofs.find(it->second);
205
	if (findIt != mapDelDofs.end()) {
206
207
208
	  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));
209
210
211
212
213
214
215
	  it->second = findIt->second;   
	  changed = true;
	}
      } 
    } while (changed);


216
217
    // === Set new DOF pointers in all elements of the mesh. ===

218
    elInfo = stack.traverseFirst(mesh, -1, Mesh::CALL_EVERY_EL_PREORDER);
219
220
    while (elInfo) {
      for (int i = 0; i < mesh->getGeo(VERTEX); i++)
221
	if (mapDelDofs.count(elInfo->getElement()->getDof(i)) == 1)
222
	  elInfo->getElement()->setDof(i, const_cast<DegreeOfFreedom*>(mapDelDofs[elInfo->getElement()->getDof(i)]));	
223
224
225
226

      elInfo = stack.traverseNext(elInfo);
    }

227

228
229
    // === And delete all double DOFs. ===

230
    for (map<const DegreeOfFreedom*, const DegreeOfFreedom*>::iterator it = mapDelDofs.begin();
231
	 it != mapDelDofs.end(); ++it)
232
233
234
      mesh->freeDof(const_cast<DegreeOfFreedom*>(it->first), VERTEX);
  }

235

236
237
  bool MeshManipulation::fitElementToMeshCode(MeshStructure &code,
					      BoundaryObject &boundEl)
238
  {
239
    FUNCNAME("MeshManipulation::fitElementToMeshCode()");
240

241
    TEST_EXIT_DBG(boundEl.el)("No element given!\n");
242
243
244
245
246
247
248
249
250

    // 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.
251
252
253
254
    int s0 = 
      boundEl.el->getSubObjOfChild(0, boundEl.subObj, boundEl.ithObj, boundEl.elType);
    int s1 = 
      boundEl.el->getSubObjOfChild(1, boundEl.subObj, boundEl.ithObj, boundEl.elType);
255
256
257
258
259
260
261
262
263

    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.
264
    if (boundEl.reverseMode)
265
266
267
268
269
      traverseFlag |= Mesh::CALL_REVERSE_MODE;    


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

270
271
    Mesh *mesh = boundEl.el->getMesh();

272
273
274
275
    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;
276
277
      ElInfo *elInfo = stack.traverseFirst(mesh, -1, traverseFlag);
      while (elInfo && elInfo->getElement() != boundEl.el)
278
279
	elInfo = stack.traverseNext(elInfo);      

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

282
283
      return fitElementToMeshCode(code, stack, boundEl.subObj, 
				  boundEl.ithObj, boundEl.reverseMode);
284
285
286
287
288
    }


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

289
    if (boundEl.el->isLeaf()) {
290
291
292
293
294
295
296

      // 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;
297
298
      ElInfo *elInfo = stack.traverseFirst(mesh, -1, traverseFlag);
      while (elInfo && elInfo->getElement() != boundEl.el)
299
300
301
302
303
	elInfo = stack.traverseNext(elInfo);      

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

      // Code is not leaf, therefore refine the element.
304
305
      boundEl.el->setMark(1);
      refineManager->setMesh(boundEl.el->getMesh());
306
307
308
309
310
      refineManager->setStack(&stack);
      refineManager->refineFunction(elInfo);
      meshChanged = true;
    }

311
312
313
    Element *child0 = boundEl.el->getFirstChild();
    Element *child1 = boundEl.el->getSecondChild();
    if (boundEl.reverseMode) {
314
315
316
317
318
319
320
321
322
      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;
323
    ElInfo *elInfo = stack.traverseFirst(mesh, -1, traverseFlag);
324
325
326
327
328

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

329
330
      meshChanged |= 
	fitElementToMeshCode(code, stack, boundEl.subObj, s0, boundEl.reverseMode);
331
332
333
334
    } else {
      while (elInfo && elInfo->getElement() != child1) 
	elInfo = stack.traverseNext(elInfo);      

335
336
      meshChanged |= 
	fitElementToMeshCode(code, stack, boundEl.subObj, s1, boundEl.reverseMode);
337
338
339
340
341
342
343
344
345
346
347
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
    }


    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();
377
378
    int s0 = el->getSubObjOfChild(0, subObj, ithObj, elInfo->getType());
    int s1 = el->getSubObjOfChild(1, subObj, ithObj, elInfo->getType());
379
380
381

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

382
383
    bool elementRefined = true;

384
385
386
    if (el->isLeaf()) {
      TEST_EXIT_DBG(elInfo->getLevel() < 255)("This should not happen!\n");

387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
      // 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);
  	  }
  	}
      }
408

409
410
411
412
413
414
415
416
      if (elementRefined) {
 	MeshStructure t = code;
	el->setMark(1);
	refineManager->setMesh(el->getMesh());
	refineManager->setStack(&stack);
	refineManager->refineFunction(elInfo);
	meshChanged = true;
      } 
417
418
419
    }


420
421
422
423
424
425
426
427
428
429
    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);
      }
430

431
432
433
434
435
436
437
438
439
440
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
    
      // === 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);
      }
      
479
    }
480
      
481
482
    return meshChanged;
  }
483
  
484
}