Fix tutorials: coupled/conjugateHeatFoam/conjugateCavity: fix Allrun file
[OpenFOAM-1.6-ext.git] / src / meshTools / polyMeshZipUpCells / polyMeshZipUpCells.C
blob083f110432234cd9b2dfad24f13c19136022d270
1 /*---------------------------------------------------------------------------*\
2   =========                 |
3   \\      /  F ield         | OpenFOAM: The Open Source CFD Toolbox
4    \\    /   O peration     |
5     \\  /    A nd           | Copyright held by original author
6      \\/     M anipulation  |
7 -------------------------------------------------------------------------------
8 License
9     This file is part of OpenFOAM.
11     OpenFOAM is free software; you can redistribute it and/or modify it
12     under the terms of the GNU General Public License as published by the
13     Free Software Foundation; either version 2 of the License, or (at your
14     option) any later version.
16     OpenFOAM is distributed in the hope that it will be useful, but WITHOUT
17     ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
18     FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
19     for more details.
21     You should have received a copy of the GNU General Public License
22     along with OpenFOAM; if not, write to the Free Software Foundation,
23     Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
25 \*---------------------------------------------------------------------------*/
27 #include "polyMeshZipUpCells.H"
28 #include "polyMesh.H"
29 #include "Time.H"
31 // #define DEBUG_ZIPUP 1
32 // #define DEBUG_CHAIN 1
33 // #define DEBUG_ORDER 1
35 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
37 bool Foam::polyMeshZipUpCells(polyMesh& mesh)
39     if (polyMesh::debug)
40     {
41         Info<< "bool polyMeshZipUpCells(polyMesh& mesh) const: "
42             << "zipping up topologically open cells" << endl;
43     }
45     // Algorithm:
46     // Take the original mesh and visit all cells.  For every cell
47     // calculate the edges of all faces on the cells.  A cell is
48     // correctly topologically closed when all the edges are referenced
49     // by exactly two faces.  If the edges are referenced only by a
50     // single face, additional vertices need to be inserted into some
51     // of the faces (topological closedness).  If an edge is
52     // referenced by more that two faces, there is an error in
53     // topological closedness.
54     // Point insertion into the faces is done by attempting to create
55     // closed loops and inserting the intermediate points into the
56     // defining edge
57     // Note:
58     // The algorithm is recursive and changes the mesh faces in each
59     // pass.  It is therefore essential to discard the addressing
60     // after every pass.  The algorithm is completed when the mesh
61     // stops changing.
63     label nChangedFacesInMesh = 0;
64     label nCycles = 0;
66     labelHashSet problemCells;
68     do
69     {
70         nChangedFacesInMesh = 0;
72         const cellList& Cells = mesh.cells();
73         const pointField& Points = mesh.allPoints();
75         faceList newFaces = mesh.allFaces();
77         const faceList& oldFaces = mesh.allFaces();
78         const labelListList& pFaces = mesh.pointFaces();
80         forAll (Cells, cellI)
81         {
82             const labelList& curFaces = Cells[cellI];
83             const edgeList cellEdges = Cells[cellI].edges(oldFaces);
84             const labelList cellPoints = Cells[cellI].labels(oldFaces);
86             // Find the edges used only once in the cell
88             labelList edgeUsage(cellEdges.size(), 0);
90             forAll (curFaces, faceI)
91             {
92                 edgeList curFaceEdges = oldFaces[curFaces[faceI]].edges();
94                 forAll (curFaceEdges, faceEdgeI)
95                 {
96                     const edge& curEdge = curFaceEdges[faceEdgeI];
98                     forAll (cellEdges, cellEdgeI)
99                     {
100                         if (cellEdges[cellEdgeI] == curEdge)
101                         {
102                             edgeUsage[cellEdgeI]++;
103                             break;
104                         }
105                     }
106                 }
107             }
109             edgeList singleEdges(cellEdges.size());
110             label nSingleEdges = 0;
112             forAll (edgeUsage, edgeI)
113             {
114                 if (edgeUsage[edgeI] == 1)
115                 {
116                     singleEdges[nSingleEdges] = cellEdges[edgeI];
117                     nSingleEdges++;
118                 }
119                 else if (edgeUsage[edgeI] != 2)
120                 {
121                     WarningIn("void polyMeshZipUpCells(polyMesh& mesh)")
122                         << "edge " << cellEdges[edgeI] << " in cell " << cellI
123                         << " used " << edgeUsage[edgeI] << " times. " << nl
124                         << "Should be 1 or 2 - serious error "
125                         << "in mesh structure. " << endl;
127 #                   ifdef DEBUG_ZIPUP
128                     forAll (curFaces, faceI)
129                     {
130                         Info<< "face: " << oldFaces[curFaces[faceI]]
131                             << endl;
132                     }
134                     Info<< "Cell edges: " << cellEdges << nl
135                         << "Edge usage: " << edgeUsage << nl
136                         << "Cell points: " << cellPoints << endl;
138                     forAll (cellPoints, cpI)
139                     {
140                         Info<< "vertex create \"" << cellPoints[cpI]
141                             << "\" coordinates "
142                             << Points[cellPoints[cpI]] << endl;
143                     }
144 #                   endif
146                     // Gather the problem cell
147                     problemCells.insert(cellI);
148                 }
149             }
151             // Check if the cell is already zipped up
152             if (nSingleEdges == 0) continue;
154             singleEdges.setSize(nSingleEdges);
156 #           ifdef DEBUG_ZIPUP
157             Info << "Cell " << cellI << endl;
159             forAll (curFaces, faceI)
160             {
161                 Info<< "face: " << oldFaces[curFaces[faceI]] << endl;
162             }
164             Info<< "Cell edges: " << cellEdges << nl
165                 << "Edge usage: " << edgeUsage << nl
166                 << "Single edges: " << singleEdges << nl
167                 << "Cell points: " << cellPoints << endl;
169             forAll (cellPoints, cpI)
170             {
171                 Info<< "vertex create \"" << cellPoints[cpI]
172                     << "\" coordinates "
173                     << points()[cellPoints[cpI]] << endl;
174             }
175 #           endif
177             // Loop through all single edges and mark the points they use
178             // points marked twice are internal to edge; those marked more than
179             // twice are corners
181             labelList pointUsage(cellPoints.size(), 0);
183             forAll (singleEdges, edgeI)
184             {
185                 const edge& curEdge = singleEdges[edgeI];
187                 forAll (cellPoints, pointI)
188                 {
189                     if
190                     (
191                         cellPoints[pointI] == curEdge.start()
192                      || cellPoints[pointI] == curEdge.end()
193                     )
194                     {
195                         pointUsage[pointI]++;
196                     }
197                 }
198             }
200             boolList singleEdgeUsage(singleEdges.size(), false);
202             // loop through all edges and eliminate the ones that are
203             // blocked out
204             forAll (singleEdges, edgeI)
205             {
206                 bool blockedHead = false;
207                 bool blockedTail = false;
209                 label newEdgeStart = singleEdges[edgeI].start();
210                 label newEdgeEnd = singleEdges[edgeI].end();
212                 // check that the edge has not got all ends blocked
213                 forAll (cellPoints, pointI)
214                 {
215                     if (cellPoints[pointI] == newEdgeStart)
216                     {
217                         if (pointUsage[pointI] > 2)
218                         {
219                             blockedHead = true;
220                         }
221                     }
222                     else if (cellPoints[pointI] == newEdgeEnd)
223                     {
224                         if (pointUsage[pointI] > 2)
225                         {
226                             blockedTail = true;
227                         }
228                     }
229                 }
231                 if (blockedHead && blockedTail)
232                 {
233                     // Eliminating edge singleEdges[edgeI] as blocked
234                     singleEdgeUsage[edgeI] = true;
235                 }
236             }
238             // Go through the points and start from the point used twice
239             // check all the edges to find the edges starting from this point
240             // add the 
242             labelListList edgesToInsert(singleEdges.size());
243             label nEdgesToInsert = 0;
245             // Find a good edge
246             forAll (singleEdges, edgeI)
247             {
248                 SLList<label> pointChain;
250                 bool blockHead = false;
251                 bool blockTail = false;
253                 if (!singleEdgeUsage[edgeI])
254                 {
255                     // found a new edge
256                     singleEdgeUsage[edgeI] = true;
258                     label newEdgeStart = singleEdges[edgeI].start();
259                     label newEdgeEnd = singleEdges[edgeI].end();
261                     pointChain.insert(newEdgeStart);
262                     pointChain.append(newEdgeEnd);
264 #                   ifdef DEBUG_CHAIN
265                     Info<< "found edge to start with: "
266                         << singleEdges[edgeI] << endl;
267 #                   endif
269                     // Check if head or tail are blocked
270                     forAll (cellPoints, pointI)
271                     {
272                         if (cellPoints[pointI] == newEdgeStart)
273                         {
274                             if (pointUsage[pointI] > 2)
275                             {
276 #                               ifdef DEBUG_CHAIN
277                                 Info << "start head blocked" << endl;
278 #                               endif
280                                 blockHead = true;
281                             }
282                         }
283                         else if(cellPoints[pointI] == newEdgeEnd)
284                         {
285                             if (pointUsage[pointI] > 2)
286                             {
287 #                               ifdef DEBUG_CHAIN
288                                 Info << "start tail blocked" << endl;
289 #                               endif
291                                 blockTail = true;
292                             }
293                         }
294                     }
296                     bool stopSearching = false;
298                     // Go through the unused edges and try to chain them up
299                     do
300                     {
301                         stopSearching = false;
303                         forAll (singleEdges, addEdgeI)
304                         {
305                             if (!singleEdgeUsage[addEdgeI])
306                             {
307                                 // Grab start and end of the candidate
308                                 label addStart =
309                                     singleEdges[addEdgeI].start();
311                                 label addEnd =
312                                     singleEdges[addEdgeI].end();
314 #                               ifdef DEBUG_CHAIN
315                                 Info<< "Trying candidate "
316                                     << singleEdges[addEdgeI] << endl;
317 #                               endif
319                                 // Try to add the edge onto the head
320                                 if (!blockHead)
321                                 {
322                                     if (pointChain.first() == addStart)
323                                     {
324                                         // Added at start mark as used
325                                         pointChain.insert(addEnd);
327                                         singleEdgeUsage[addEdgeI] = true;
328                                     }
329                                     else if (pointChain.first() == addEnd)
330                                     {
331                                         pointChain.insert(addStart);
333                                         singleEdgeUsage[addEdgeI] = true;
334                                     }
335                                 }
337                                 // Try the other end only if the first end
338                                 // did not add it
339                                 if (!blockTail && !singleEdgeUsage[addEdgeI])
340                                 {
341                                     if (pointChain.last() == addStart)
342                                     {
343                                         // Added at start mark as used
344                                         pointChain.append(addEnd);
346                                         singleEdgeUsage[addEdgeI] = true;
347                                     }
348                                     else if (pointChain.last() == addEnd)
349                                     {
350                                         pointChain.append(addStart);
352                                         singleEdgeUsage[addEdgeI] = true;
353                                     }
354                                 }
356                                 // check if the new head or tail are blocked
357                                 label curEdgeStart = pointChain.first();
358                                 label curEdgeEnd = pointChain.last();
360 #                               ifdef DEBUG_CHAIN
361                                 Info<< "curEdgeStart: " << curEdgeStart
362                                     << " curEdgeEnd: " << curEdgeEnd << endl;
363 #                               endif
365                                 forAll (cellPoints, pointI)
366                                 {
367                                     if (cellPoints[pointI] == curEdgeStart)
368                                     {
369                                         if (pointUsage[pointI] > 2)
370                                         {
371 #                                           ifdef DEBUG_CHAIN
372                                             Info << "head blocked" << endl;
373 #                                           endif
375                                             blockHead = true;
376                                         }
377                                     }
378                                     else if(cellPoints[pointI] == curEdgeEnd)
379                                     {
380                                         if (pointUsage[pointI] > 2)
381                                         {
382 #                                           ifdef DEBUG_CHAIN
383                                             Info << "tail blocked" << endl;
384 #                                           endif
386                                             blockTail = true;
387                                         }
388                                     }
389                                 }
391                                 // Check if the loop is closed
392                                 if (curEdgeStart == curEdgeEnd)
393                                 {
394 #                                   ifdef DEBUG_CHAIN
395                                     Info << "closed loop" << endl;
396 #                                   endif
398                                     pointChain.removeHead();
400                                     blockHead = true;
401                                     blockTail = true;
403                                     stopSearching = true;
404                                 }
406 #                               ifdef DEBUG_CHAIN
407                                 Info<< "current pointChain: " << pointChain
408                                     << endl;
409 #                               endif
411                                 if (stopSearching) break;
412                             }
413                         }
414                     } while (stopSearching);
415                 }
417 #               ifdef DEBUG_CHAIN
418                 Info << "completed patch chain: " << pointChain << endl;
419 #               endif
421                 if (pointChain.size() > 2)
422                 {
423                     edgesToInsert[nEdgesToInsert] = pointChain;
424                     nEdgesToInsert++;
425                 }
426             }
428             edgesToInsert.setSize(nEdgesToInsert);
430 #           ifdef DEBUG_ZIPUP
431             Info << "edgesToInsert: " << edgesToInsert << endl;
432 #           endif
434             // Insert the edges into a list of faces
435             forAll (edgesToInsert, edgeToInsertI)
436             {
437                 // Order the points of the edge
438                 // Warning: the ordering must be parametric, because in
439                 // the case of multiple point insertion onto the same edge
440                 // it is possible to get non-cyclic loops
441                 //
443                 const labelList& unorderedEdge = edgesToInsert[edgeToInsertI];
445                 scalarField dist(unorderedEdge.size());
447                 // Calculate distance
448                 point startPoint = Points[unorderedEdge[0]];
449                 dist[0] = 0;
451                 vector dir =
452                     Points[unorderedEdge[unorderedEdge.size() - 1]]
453                   - startPoint;
455                 for (label i = 1; i < dist.size(); i++)
456                 {
457                     dist[i] = (Points[unorderedEdge[i]] - startPoint) & dir;
458                 }
460                 // Sort points
461                 labelList orderedEdge(unorderedEdge.size(), -1);
462                 boolList used(unorderedEdge.size(), false);
464                 forAll (orderedEdge, epI)
465                 {
466                     label nextPoint = -1;
467                     scalar minDist = GREAT;
469                     forAll (dist, i)
470                     {
471                         if (!used[i] && dist[i] < minDist)
472                         {
473                             minDist = dist[i];
474                             nextPoint = i;
475                         }
476                     }
478                     // Insert the next point
479                     orderedEdge[epI] = unorderedEdge[nextPoint];
480                     used[nextPoint] = true;
481                 }
483 #               ifdef DEBUG_ORDER
484                 Info<< "unorderedEdge: " << unorderedEdge << nl
485                     << "orderedEdge: " << orderedEdge << endl;
486 #               endif
488                 // check for duplicate points in the ordered edge
489                 forAll (orderedEdge, checkI)
490                 {
491                     for
492                     (
493                         label checkJ = checkI + 1;
494                         checkJ < orderedEdge.size();
495                         checkJ++
496                     )
497                     {
498                         if (orderedEdge[checkI] == orderedEdge[checkJ])
499                         {
500                             WarningIn("void polyMeshZipUpCells(polyMesh& mesh)")
501                                 << "Duplicate point found in edge to insert. "
502                                 << nl << "Point: " << orderedEdge[checkI]
503                                 << " edge: " << orderedEdge << endl;
505                             problemCells.insert(cellI);
506                         }
507                     }
508                 }
510                 edge testEdge
511                 (
512                     orderedEdge[0],
513                     orderedEdge[orderedEdge.size() - 1]
514                 );
516                 // In order to avoid edge-to-edge comparison, get faces using
517                 // point-face addressing in two goes.
518                 const labelList& startPF = pFaces[testEdge.start()];
519                 const labelList& endPF = pFaces[testEdge.start()];
521                 labelList facesSharingEdge(startPF.size() + endPF.size());
522                 label nfse = 0;
524                 forAll (startPF, pfI)
525                 {
526                     facesSharingEdge[nfse++] = startPF[pfI];
527                 }
528                 forAll (endPF, pfI)
529                 {
530                     facesSharingEdge[nfse++] = endPF[pfI];
531                 }
533                 forAll (facesSharingEdge, faceI)
534                 {
535                     bool faceChanges = false;
537                     // Label of the face being analysed
538                     const label currentFaceIndex = facesSharingEdge[faceI];
540                     const edgeList curFaceEdges =
541                         oldFaces[currentFaceIndex].edges();
543                     forAll (curFaceEdges, cfeI)
544                     {
545                         if (curFaceEdges[cfeI] == testEdge)
546                         {
547                             faceChanges = true;
548                             break;
549                         }
550                     }
552                     if (faceChanges)
553                     {
554                         nChangedFacesInMesh++;
555                         // In order to avoid loosing point from multiple
556                         // insertions into the same face, the new face
557                         // will be change incrementally.
558                         // 1) Check if all the internal points of the edge
559                         // to add already exist in the face. If so, the
560                         // edge has already been included 2) Check if the
561                         // point insertion occurs on an edge which is
562                         // still untouched. If so, simply insert
563                         // additional points into the face.  3) If not,
564                         // the edge insertion occurs on an already
565                         // modified edge. ???
567                         face& newFace = newFaces[currentFaceIndex];
569                         bool allPointsPresent = true;
571                         forAll (orderedEdge, oeI)
572                         {
573                             bool curPointFound = false;
575                             forAll (newFace, nfI)
576                             {
577                                 if (newFace[nfI] == orderedEdge[oeI])
578                                 {
579                                     curPointFound = true;
580                                     break;
581                                 }
582                             }
584                             allPointsPresent =
585                                 allPointsPresent && curPointFound;
586                         }
588 #                       ifdef DEBUG_ZIPUP
589                         if (allPointsPresent)
590                         {
591                             Info << "All points present" << endl;
592                         }
593 #                       endif
595                         if (!allPointsPresent)
596                         {
597                             // Not all points are already present.  The
598                             // new edge will need to be inserted into the
599                             // face.
601                             // Check to see if a new edge fits onto an
602                             // untouched edge of the face.  Make sure the
603                             // edges are grabbed before the face is
604                             // resized.
605                             edgeList newFaceEdges = newFace.edges();
607 #                           ifdef DEBUG_ZIPUP
608                             Info << "Not all points present." << endl;
609 #                           endif
611                             label nNewFacePoints = 0;
613                             bool edgeAdded = false;
615                             forAll (newFaceEdges, curFacEdgI)
616                             {
617                                 // Does the current edge change?
618                                 if (newFaceEdges[curFacEdgI] == testEdge)
619                                 {
620                                     // Found an edge match
621                                     edgeAdded = true;
623                                     // Resize the face to accept additional
624                                     // points
625                                     newFace.setSize
626                                     (
627                                         newFace.size()
628                                       + orderedEdge.size() - 2
629                                     );
631                                     if
632                                     (
633                                         newFaceEdges[curFacEdgI].start()
634                                      == testEdge.start()
635                                     )
636                                     {
637                                         // insertion in ascending order
638                                         for
639                                         (
640                                             label i = 0;
641                                             i < orderedEdge.size() - 1;
642                                             i++
643                                         )
644                                         {
645                                             newFace[nNewFacePoints] =
646                                                 orderedEdge[i];
647                                             nNewFacePoints++;
648                                         }
649                                     }
650                                     else
651                                     {
652                                         // insertion in reverse order
653                                         for
654                                         (
655                                             label i = orderedEdge.size() - 1;
656                                             i > 0;
657                                             i--
658                                         )
659                                         {
660                                             newFace[nNewFacePoints] =
661                                                 orderedEdge[i];
662                                             nNewFacePoints++;
663                                         }
664                                     }
665                                 }
666                                 else
667                                 {
668                                     // Does not fit onto this edge.
669                                     // Copy the next point into the face
670                                     newFace[nNewFacePoints] =
671                                         newFaceEdges[curFacEdgI].start();
672                                     nNewFacePoints++;
673                                 }
674                             }
676 #                           ifdef DEBUG_ZIPUP
677                             Info<< "oldFace: "
678                                 << oldFaces[currentFaceIndex] << nl
679                                 << "newFace: " << newFace << endl;
680 #                           endif
682                             // Check for duplicate points in the new face
683                             forAll (newFace, checkI)
684                             {
685                                 for
686                                 (
687                                     label checkJ = checkI + 1;
688                                     checkJ < newFace.size();
689                                     checkJ++
690                                 )
691                                 {
692                                     if (newFace[checkI] == newFace[checkJ])
693                                     {
694                                         WarningIn("void polyMeshZipUpCells(polyMesh& mesh)")
695                                             << "Duplicate point found "
696                                             << "in the new face. " << nl
697                                             << "Point: "
698                                             << orderedEdge[checkI]
699                                             << " face: "
700                                             << newFace << endl;
702                                         problemCells.insert(cellI);
703                                     }
704                                 }
705                             }
707                             // Check if the edge is added.
708                             // If not, then it comes on top of an already
709                             // modified edge and they need to be
710                             // merged in together.
711                             if (!edgeAdded)
712                             {
713                                 Info<< "This edge modifies an already modified "
714                                     << "edge.  Point insertions skipped."
715                                     << endl;
716                             }
717                         }
718                     }
719                 }
720             }
721         }
723         if (problemCells.size())
724         {
725             // This cycle has failed.  Print out the problem cells
726             labelList toc(problemCells.toc());
727             sort(toc);
729             FatalErrorIn("void polyMeshZipUpCells(polyMesh& mesh)")
730                 << "Found " << problemCells.size() << " problem cells." << nl
731                 << "Cells: " << toc
732                 << abort(FatalError);
733         }
735         Info<< "Cycle " << ++nCycles
736             << " changed " << nChangedFacesInMesh << " faces." << endl;
739         const polyBoundaryMesh& bMesh = mesh.boundaryMesh();
741         // Reset the polyMesh. Number of points/faces/cells/patches stays the
742         // same, only the faces themselves have changed so clear all derived
743         // (edge, point) addressing.
745         // Collect the patch sizes
746         labelList patchSizes(bMesh.size(), 0);
747         labelList patchStarts(bMesh.size(), 0);
749         forAll (bMesh, patchI)
750         {
751             patchSizes[patchI] = bMesh[patchI].size();
752             patchStarts[patchI] = bMesh[patchI].start();
753         }
755         // Reset the mesh. Number of active faces is one beyond the last patch
756         // (patches guaranteed to be in increasing order)
757         // 1.6.x merge change.  Reconsider.  HJ, 22/Aug/2010
758         mesh.resetPrimitives
759         (
760             Xfer<pointField>::null(),
761             xferMove(newFaces),
762             Xfer<labelList>::null(),
763             Xfer<labelList>::null(),
764             patchSizes,
765             patchStarts,
766             true                // boundary forms valid boundary mesh.
767         );
769         // Clear the addressing
770         mesh.clearOut();
772     } while (nChangedFacesInMesh > 0 || nCycles > 100);
774     // Flags the mesh files as being changed
775     mesh.setInstance(mesh.time().timeName());
777     if (nChangedFacesInMesh > 0)
778     {
779         FatalErrorIn("void polyMeshZipUpCells(polyMesh& mesh)")
780             << "cell zip-up failed after 100 cycles.  Probable problem "
781             << "with the original mesh"
782             << abort(FatalError);
783     }
785     return nCycles != 1;
789 // ************************************************************************* //