src/BRepMesh/BRepMesh_MeshTool.cxx

   1 // Created on: 2016-08-22
   2 // Copyright (c) 2016 OPEN CASCADE SAS
   3 // Created by: Oleg AGASHIN
   4 //
   5 // This file is part of Open CASCADE Technology software library.
   6 //
   7 // This library is free software; you can redistribute it and/or modify it under
   8 // the terms of the GNU Lesser General Public License version 2.1 as published
   9 // by the Free Software Foundation, with special exception defined in the file
  10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  11 // distribution for complete text of the license and disclaimer of any warranty.
  12 //
  13 // Alternatively, this file may be used under the terms of Open CASCADE
  14 // commercial license or contractual agreement.
  15
  16 #include <BRepMesh_MeshTool.hxx>
  17 #include <BRepMesh_SelectorOfDataStructureOfDelaun.hxx>
  18 #include <stack>
  19
  20 #include <BRepBuilderAPI_MakeFace.hxx>
  21 #include <BRepBuilderAPI_MakePolygon.hxx>
  22 #include <BRep_Builder.hxx>
  23 #include <TopoDS_Compound.hxx>
  24 #include <BRepTools.hxx>
  25 #include <gp_Pln.hxx>
  26
  27 namespace
  28 {
  29   //! Returns index of triangle node opposite to the given link.
  30   inline Standard_Integer findApexIndex(
  31     const Standard_Integer(&aNodes)[3],
  32     const BRepMesh_Edge&   theLink)
  33   {
  34     Standard_Integer i = 0;
  35     for (; i < 3; ++i)
  36     {
  37       if (aNodes[i] != theLink.FirstNode() &&
  38           aNodes[i] != theLink.LastNode())
  39       {
  40         break;
  41       }
  42     }
  43
  44     return i;
  45   }
  46 }
  47
  48 //=======================================================================
  49 // Function: Constructor
  50 // Purpose :
  51 //=======================================================================
  52 BRepMesh_MeshTool::BRepMesh_MeshTool(
  53   const Handle(BRepMesh_DataStructureOfDelaun)& theStructure)
  54   : myStructure(theStructure)
  55 {
  56 }
  57
  58 //=======================================================================
  59 // Function: Destructor
  60 // Purpose :
  61 //=======================================================================
  62 BRepMesh_MeshTool::~BRepMesh_MeshTool()
  63 {
  64 }
  65
  66 //=======================================================================
  67 //function : Legalize
  68 //purpose  :
  69 //=======================================================================
  70 void BRepMesh_MeshTool::Legalize(const Standard_Integer theLinkIndex)
  71 {
  72   std::stack<Standard_Integer> aStack;
  73   aStack.push(theLinkIndex);
  74
  75   IMeshData::MapOfInteger aUsedLinks;
  76   while (!aStack.empty())
  77   {
  78     const Standard_Integer aLinkIndex = aStack.top();
  79     aStack.pop();
  80
  81     aUsedLinks.Add(aLinkIndex);
  82     const BRepMesh_Edge& aLink = myStructure->GetLink(aLinkIndex);
  83     if (aLink.Movability() != BRepMesh_Frontier)
  84     {
  85       const BRepMesh_PairOfIndex& aPair = myStructure->ElementsConnectedTo(aLinkIndex);
  86       if (aPair.Extent() == 2)
  87       {
  88         const BRepMesh_Triangle& aTriangle1 = myStructure->GetElement(aPair.FirstIndex());
  89         const BRepMesh_Triangle& aTriangle2 = myStructure->GetElement(aPair.LastIndex());
  90
  91         Standard_Integer aNodes[2][3];
  92         myStructure->ElementNodes(aTriangle1, aNodes[0]);
  93         myStructure->ElementNodes(aTriangle2, aNodes[1]);
  94
  95         const Standard_Integer aApexIndex[2] = {
  96           findApexIndex(aNodes[0], aLink),
  97           findApexIndex(aNodes[1], aLink)
  98         };
  99
 100         if (checkCircle(aNodes[0], aNodes[1][aApexIndex[1]]) ||
 101             checkCircle(aNodes[1], aNodes[0][aApexIndex[0]]))
 102         {
 103           myStructure->RemoveElement(aPair.FirstIndex());
 104           myStructure->RemoveElement(aPair.LastIndex());
 105           myStructure->RemoveLink(aLinkIndex);
 106
 107           addTriangleAndUpdateStack(
 108             aNodes[0][(aApexIndex[0])],
 109             aNodes[0][(aApexIndex[0] + 1) % 3],
 110             aNodes[1][(aApexIndex[1])],
 111             aUsedLinks, aStack);
 112
 113           addTriangleAndUpdateStack(
 114             aNodes[1][(aApexIndex[1])],
 115             aNodes[1][(aApexIndex[1] + 1) % 3],
 116             aNodes[0][(aApexIndex[0])],
 117             aUsedLinks, aStack);
 118         }
 119       }
 120     }
 121   }
 122 }
 123
 124 //=======================================================================
 125 //function : EraseItemsConnectedTo
 126 //purpose  :
 127 //=======================================================================
 128 void BRepMesh_MeshTool::EraseItemsConnectedTo(
 129   const Standard_Integer theNodeIndex)
 130 {
 131   BRepMesh_SelectorOfDataStructureOfDelaun aSelector(myStructure);
 132   aSelector.NeighboursOfNode(theNodeIndex);
 133
 134   IMeshData::MapOfIntegerInteger aLoopEdges(1, new NCollection_IncAllocator);
 135   EraseTriangles(aSelector.Elements(), aLoopEdges);
 136   EraseFreeLinks(aLoopEdges);
 137   myStructure->RemoveNode(theNodeIndex);
 138 }
 139
 140 //=======================================================================
 141 //function : CleanFrontierLinks
 142 //purpose  :
 143 //=======================================================================
 144 void BRepMesh_MeshTool::CleanFrontierLinks()
 145 {
 146   Handle(NCollection_IncAllocator) aAlloc = new NCollection_IncAllocator;
 147   IMeshData::MapOfInteger aTrianglesToErase;
 148   IMeshData::MapOfIntegerInteger aLoopEdges(1, aAlloc);
 149
 150   Handle(IMeshData::MapOfInteger) aFrontier = GetEdgesByType(BRepMesh_Frontier);
 151   IMeshData::IteratorOfMapOfInteger aFrontierIt(*aFrontier);
 152   for (; aFrontierIt.More(); aFrontierIt.Next())
 153   {
 154     Standard_Integer aFrontierId = aFrontierIt.Key();
 155     const BRepMesh_Edge& aLink = myStructure->GetLink(aFrontierId);
 156
 157     Standard_Boolean isTriangleFound = Standard_False;
 158     const BRepMesh_PairOfIndex& aPair = myStructure->ElementsConnectedTo(aFrontierId);
 159     for (Standard_Integer aElemIt = 1; aElemIt <= aPair.Extent() && !isTriangleFound; ++aElemIt)
 160     {
 161       const Standard_Integer aPriorElemId = aPair.Index(aElemIt);
 162       const BRepMesh_Triangle& aElement = myStructure->GetElement(aPriorElemId);
 163       const Standard_Integer(&e)[3] = aElement.myEdges;
 164       const Standard_Boolean(&o)[3] = aElement.myOrientations;
 165
 166       for (Standard_Integer n = 0; n < 3 && !isTriangleFound; ++n)
 167       {
 168         if (aFrontierId == e[n] && !o[n])
 169         {
 170           // Destruction of external triangles on boundary edges
 171           isTriangleFound = Standard_True;
 172           aTrianglesToErase.Add(aPriorElemId);
 173
 174           collectTrianglesOnFreeLinksAroundNodesOf(aLink, e[(n + 1) % 3], aTrianglesToErase);
 175           collectTrianglesOnFreeLinksAroundNodesOf(aLink, e[(n + 2) % 3], aTrianglesToErase);
 176         }
 177       }
 178     }
 179   }
 180
 181   EraseTriangles(aTrianglesToErase, aLoopEdges);
 182   EraseFreeLinks(aLoopEdges);
 183 }
 184
 185 //=======================================================================
 186 //function : EraseTriangles
 187 //purpose  :
 188 //=======================================================================
 189 void BRepMesh_MeshTool::EraseTriangles(
 190   const IMeshData::MapOfInteger&  theTriangles,
 191   IMeshData::MapOfIntegerInteger& theLoopEdges)
 192 {
 193   IMeshData::IteratorOfMapOfInteger aFreeTriangles(theTriangles);
 194   for (; aFreeTriangles.More(); aFreeTriangles.Next())
 195   {
 196     EraseTriangle(aFreeTriangles.Key(), theLoopEdges);
 197   }
 198 }
 199
 200 //=======================================================================
 201 //function : EraseTriangle
 202 //purpose  :
 203 //=======================================================================
 204 void BRepMesh_MeshTool::EraseTriangle(
 205   const Standard_Integer          theTriangleIndex,
 206   IMeshData::MapOfIntegerInteger& theLoopEdges)
 207 {
 208   const BRepMesh_Triangle& aElement = myStructure->GetElement(theTriangleIndex);
 209   const Standard_Integer(&e)[3] = aElement.myEdges;
 210   const Standard_Boolean(&o)[3] = aElement.myOrientations;
 211
 212   myStructure->RemoveElement(theTriangleIndex);
 213
 214   for (Standard_Integer i = 0; i < 3; ++i)
 215   {
 216     if (!theLoopEdges.Bind(e[i], o[i]))
 217     {
 218       theLoopEdges.UnBind(e[i]);
 219       myStructure->RemoveLink(e[i]);
 220     }
 221   }
 222 }
 223
 224 //=======================================================================
 225 //function : EraseFreeLinks
 226 //purpose  :
 227 //=======================================================================
 228 void BRepMesh_MeshTool::EraseFreeLinks()
 229 {
 230   for (Standard_Integer i = 1; i <= myStructure->NbLinks(); i++)
 231   {
 232     if (myStructure->ElementsConnectedTo(i).IsEmpty())
 233     {
 234       BRepMesh_Edge& anEdge = (BRepMesh_Edge&) myStructure->GetLink(i);
 235       if (anEdge.Movability() == BRepMesh_Deleted)
 236       {
 237         continue;
 238       }
 239
 240       anEdge.SetMovability(BRepMesh_Free);
 241       myStructure->RemoveLink(i);
 242     }
 243   }
 244 }
 245
 246 //=======================================================================
 247 //function : collectTrianglesOnFreeLinksAroundNodesOf
 248 //purpose  :
 249 //=======================================================================
 250 void BRepMesh_MeshTool::collectTrianglesOnFreeLinksAroundNodesOf(
 251   const BRepMesh_Edge&     theConstraint,
 252   const Standard_Integer   theStartLink,
 253   IMeshData::MapOfInteger& theTriangles)
 254 {
 255   IMeshData::MapOfInteger aUsedLinks;
 256   std::stack<Standard_Integer> aStack;
 257   aStack.push(theStartLink);
 258   aUsedLinks.Add(theStartLink);
 259
 260   while (!aStack.empty())
 261   {
 262     const Standard_Integer aLinkIndex = aStack.top();
 263     aStack.pop();
 264
 265     const BRepMesh_Edge& aLink = myStructure->GetLink(aLinkIndex);
 266     if (aLink.Movability() == BRepMesh_Free &&
 267         (aLink.FirstNode() == theConstraint.FirstNode() ||
 268          aLink.LastNode () == theConstraint.FirstNode() ||
 269          aLink.FirstNode() == theConstraint.LastNode () ||
 270          aLink.LastNode () == theConstraint.LastNode ()))
 271     {
 272       const BRepMesh_PairOfIndex& aPair = myStructure->ElementsConnectedTo(aLinkIndex);
 273       for (Standard_Integer aElemIt = 1; aElemIt <= aPair.Extent(); ++aElemIt)
 274       {
 275         const Standard_Integer aIndex = aPair.Index(aElemIt);
 276         theTriangles.Add(aIndex);
 277
 278         const BRepMesh_Triangle& aElement = myStructure->GetElement(aIndex);
 279         const Standard_Integer(&aEdges)[3] = aElement.myEdges;
 280
 281         for (Standard_Integer i = 0; i < 3; ++i)
 282         {
 283           if (aEdges[i] != aLinkIndex && !aUsedLinks.Contains(aEdges[i]))
 284           {
 285             aUsedLinks.Add(aEdges[i]);
 286             aStack   .push(aEdges[i]);
 287           }
 288         }
 289       }
 290     }
 291   }
 292 }
 293
 294 //=======================================================================
 295 //function : EraseFreeLinks
 296 //purpose  :
 297 //=======================================================================
 298 void BRepMesh_MeshTool::EraseFreeLinks(
 299   const IMeshData::MapOfIntegerInteger& theLinks)
 300 {
 301   IMeshData::MapOfIntegerInteger::Iterator aFreeEdges(theLinks);
 302   for (; aFreeEdges.More(); aFreeEdges.Next())
 303   {
 304     if (myStructure->ElementsConnectedTo(aFreeEdges.Key()).IsEmpty())
 305     {
 306       myStructure->RemoveLink(aFreeEdges.Key());
 307     }
 308   }
 309 }
 310
 311 //=======================================================================
 312 //function : GetEdgesByType
 313 //purpose  :
 314 //=======================================================================
 315 Handle(IMeshData::MapOfInteger) BRepMesh_MeshTool::GetEdgesByType(
 316   const BRepMesh_DegreeOfFreedom theEdgeType) const
 317 {
 318   Handle(IMeshData::MapOfInteger) aResult = new IMeshData::MapOfInteger;
 319   IMeshData::IteratorOfMapOfInteger aEdgeIt(myStructure->LinksOfDomain());
 320
 321   for (; aEdgeIt.More(); aEdgeIt.Next())
 322   {
 323     const BRepMesh_Edge& aEdge = myStructure->GetLink(aEdgeIt.Key());
 324     if (aEdge.Movability() == theEdgeType)
 325     {
 326       aResult->Add(aEdgeIt.Key());
 327     }
 328   }
 329
 330   return aResult;
 331 }
 332
 333 //=======================================================================
 334 //function : DumpStruct
 335 //purpose  :
 336 //=======================================================================
 337 void BRepMesh_MeshTool::DumpTriangles(const Standard_CString   theFileName,
 338                                       IMeshData::MapOfInteger* theTriangles)
 339 {
 340   BRep_Builder aBuilder;
 341   TopoDS_Compound aResult;
 342   aBuilder.MakeCompound(aResult);
 343
 344   const IMeshData::MapOfInteger& aTriangles = myStructure->ElementsOfDomain();
 345   for (IMeshData::IteratorOfMapOfInteger aIt(aTriangles); aIt.More(); aIt.Next())
 346   {
 347     if (theTriangles != NULL && !theTriangles->Contains(aIt.Key()))
 348       continue;
 349
 350     Standard_Integer aNodes[3];
 351     const BRepMesh_Triangle& aTri = myStructure->GetElement(aIt.Key());
 352     myStructure->ElementNodes(aTri, aNodes);
 353
 354     const gp_XY& aV1 = myStructure->GetNode(aNodes[0]).Coord();
 355     const gp_XY& aV2 = myStructure->GetNode(aNodes[1]).Coord();
 356     const gp_XY& aV3 = myStructure->GetNode(aNodes[2]).Coord();
 357
 358     BRepBuilderAPI_MakePolygon aPoly(gp_Pnt(aV1.X(), aV1.Y(), 0.),
 359                                      gp_Pnt(aV2.X(), aV2.Y(), 0.),
 360                                      gp_Pnt(aV3.X(), aV3.Y(), 0.),
 361                                      Standard_True);
 362
 363     BRepBuilderAPI_MakeFace aFaceBuilder(gp_Pln(gp::XOY()), aPoly.Wire());
 364     aBuilder.Add(aResult, aFaceBuilder.Shape());
 365   }
 366
 367   BRepTools::Write(aResult, theFileName);
 368 }