src/BRepMesh/BRepMesh_IncrementalMesh.cxx

   1 // Created on: 1995-06-20
   2 // Created by: Stagiaire Alain JOURDAIN
   3 // Copyright (c) 1995-1999 Matra Datavision
   4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   5 //
   6 // This file is part of Open CASCADE Technology software library.
   7 //
   8 // This library is free software; you can redistribute it and/or modify it under
   9 // the terms of the GNU Lesser General Public License version 2.1 as published
  10 // by the Free Software Foundation, with special exception defined in the file
  11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  12 // distribution for complete text of the license and disclaimer of any warranty.
  13 //
  14 // Alternatively, this file may be used under the terms of Open CASCADE
  15 // commercial license or contractual agreement.
  16
  17 #include <BRepMesh_IncrementalMesh.hxx>
  18
  19 #include <Precision.hxx>
  20 #include <Standard_ErrorHandler.hxx>
  21
  22 #include <BRepMesh_ShapeTool.hxx>
  23 #include <BRepMesh_Edge.hxx>
  24 #include <BRepMesh_PluginMacro.hxx>
  25
  26 #include <Bnd_Box.hxx>
  27 #include <BRep_Builder.hxx>
  28 #include <BRep_Tool.hxx>
  29 #include <BRepTools.hxx>
  30 #include <BRepLib.hxx>
  31 #include <BRepBndLib.hxx>
  32 #include <BRepAdaptor_Curve.hxx>
  33
  34 #include <Poly_Triangulation.hxx>
  35 #include <Poly_Polygon3D.hxx>
  36 #include <Poly_PolygonOnTriangulation.hxx>
  37
  38 #include <TopoDS.hxx>
  39 #include <TopoDS_Edge.hxx>
  40 #include <TopoDS_Face.hxx>
  41 #include <TopoDS_Shape.hxx>
  42 #include <TopAbs.hxx>
  43 #include <TopExp.hxx>
  44 #include <TopExp_Explorer.hxx>
  45
  46 #include <TopTools_ListIteratorOfListOfShape.hxx>
  47 #include <TColgp_Array1OfPnt.hxx>
  48 #include <TColgp_Array1OfPnt2d.hxx>
  49 #include <TColStd_Array1OfReal.hxx>
  50 #include <TopTools_HArray1OfShape.hxx>
  51 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
  52
  53 #include <GCPnts_TangentialDeflection.hxx>
  54
  55 #ifdef HAVE_TBB
  56   // paralleling using Intel TBB
  57   #include <tbb/parallel_for_each.h>
  58 #endif
  59
  60 namespace
  61 {
  62   //! Default flag to control parallelization for BRepMesh_IncrementalMesh
  63   //! tool returned for Mesh Factory
  64   static Standard_Boolean IS_IN_PARALLEL = Standard_False;
  65 };
  66
  67 IMPLEMENT_STANDARD_HANDLE (BRepMesh_IncrementalMesh, BRepMesh_DiscretRoot)
  68 IMPLEMENT_STANDARD_RTTIEXT(BRepMesh_IncrementalMesh, BRepMesh_DiscretRoot)
  69
  70 //=======================================================================
  71 //function : Default constructor
  72 //purpose  :
  73 //=======================================================================
  74 BRepMesh_IncrementalMesh::BRepMesh_IncrementalMesh()
  75 : myRelative  (Standard_False),
  76   myInParallel(Standard_False),
  77   myMinSize   (Precision::Confusion()),
  78   myInternalVerticesMode(Standard_True),
  79   myIsControlSurfaceDeflection(Standard_True)
  80 {
  81 }
  82
  83 //=======================================================================
  84 //function : Constructor
  85 //purpose  :
  86 //=======================================================================
  87 BRepMesh_IncrementalMesh::BRepMesh_IncrementalMesh(
  88   const TopoDS_Shape&    theShape,
  89   const Standard_Real    theLinDeflection,
  90   const Standard_Boolean isRelative,
  91   const Standard_Real    theAngDeflection,
  92   const Standard_Boolean isInParallel)
  93   : myRelative  (isRelative),
  94     myInParallel(isInParallel),
  95     myMinSize   (Precision::Confusion()),
  96     myInternalVerticesMode(Standard_True),
  97     myIsControlSurfaceDeflection(Standard_True)
  98 {
  99   myDeflection  = theLinDeflection;
 100   myAngle       = theAngDeflection;
 101   myShape       = theShape;
 102
 103   Perform();
 104 }
 105
 106 //=======================================================================
 107 //function : Destructor
 108 //purpose  :
 109 //=======================================================================
 110 BRepMesh_IncrementalMesh::~BRepMesh_IncrementalMesh()
 111 {
 112 }
 113
 114 //=======================================================================
 115 //function : clear
 116 //purpose  :
 117 //=======================================================================
 118 void BRepMesh_IncrementalMesh::clear()
 119 {
 120   myEdges.Clear();
 121   myEdgeDeflection.Clear();
 122   myFaces.Clear();
 123   myMesh.Nullify();
 124 }
 125
 126 //=======================================================================
 127 //function : init
 128 //purpose  :
 129 //=======================================================================
 130 void BRepMesh_IncrementalMesh::init()
 131 {
 132   myStatus   = 0;
 133   myModified = Standard_False;
 134
 135   setDone();
 136   clear();
 137
 138   collectFaces();
 139
 140   Bnd_Box aBox;
 141   BRepBndLib::Add(myShape, aBox, Standard_False);
 142
 143   if (aBox.IsVoid())
 144   {
 145     // Nothing to mesh.
 146     return;
 147   }
 148
 149   BRepMesh_ShapeTool::BoxMaxDimension(aBox, myMaxShapeSize);
 150
 151   myMesh = new BRepMesh_FastDiscret(myDeflection,
 152     myAngle, aBox, Standard_True, Standard_True,
 153     myRelative, Standard_True, myInParallel, myMinSize,
 154     myInternalVerticesMode, myIsControlSurfaceDeflection);
 155
 156   myMesh->InitSharedFaces(myShape);
 157 }
 158
 159 //=======================================================================
 160 //function : collectFaces
 161 //purpose  :
 162 //=======================================================================
 163 void BRepMesh_IncrementalMesh::collectFaces()
 164 {
 165   TopTools_ListOfShape aFaceList;
 166   BRepLib::ReverseSortFaces(myShape, aFaceList);
 167   TopTools_MapOfShape aFaceMap;
 168
 169   // make array of faces suitable for processing (excluding faces without surface)
 170   TopLoc_Location aDummyLoc;
 171   const TopLoc_Location aEmptyLoc;
 172   TopTools_ListIteratorOfListOfShape aFaceIter(aFaceList);
 173   for (; aFaceIter.More(); aFaceIter.Next())
 174   {
 175     TopoDS_Shape aFaceNoLoc = aFaceIter.Value();
 176     aFaceNoLoc.Location(aEmptyLoc);
 177     if (!aFaceMap.Add (aFaceNoLoc))
 178       continue; // already processed
 179
 180     TopoDS_Face aFace = TopoDS::Face(aFaceIter.Value());
 181     const Handle(Geom_Surface)& aSurf = BRep_Tool::Surface(aFace, aDummyLoc);
 182     if (aSurf.IsNull())
 183       continue;
 184
 185     myFaces.Append(aFace);
 186   }
 187 }
 188
 189 //=======================================================================
 190 //function : Perform
 191 //purpose  :
 192 //=======================================================================
 193 void BRepMesh_IncrementalMesh::Perform()
 194 {
 195   init();
 196
 197   if (myMesh.IsNull())
 198     return;
 199
 200   update();
 201 }
 202
 203 //=======================================================================
 204 //function : update()
 205 //purpose  :
 206 //=======================================================================
 207 void BRepMesh_IncrementalMesh::update()
 208 {
 209   // Update edges data
 210   TopExp_Explorer aExplorer(myShape, TopAbs_EDGE);
 211   for (; aExplorer.More(); aExplorer.Next())
 212   {
 213     const TopoDS_Edge& aEdge = TopoDS::Edge(aExplorer.Current());
 214     if(!BRep_Tool::IsGeometric(aEdge))
 215       continue;
 216
 217     update(aEdge);
 218   }
 219
 220   // Update faces data
 221   NCollection_Vector<TopoDS_Face>::Iterator aFaceIt(myFaces);
 222   for (; aFaceIt.More(); aFaceIt.Next())
 223     update(aFaceIt.Value());
 224
 225   // Mesh faces
 226 #ifdef HAVE_TBB
 227   if (myInParallel)
 228   {
 229     tbb::parallel_for_each(myFaces.begin(), myFaces.end(), *myMesh);
 230   }
 231   else
 232   {
 233 #endif
 234     for (aFaceIt.Init(myFaces); aFaceIt.More(); aFaceIt.Next())
 235       myMesh->Process(aFaceIt.Value());
 236 #ifdef HAVE_TBB
 237   }
 238 #endif
 239
 240   commit();
 241   clear();
 242 }
 243
 244 //=======================================================================
 245 //function : discretizeFreeEdges
 246 //purpose  :
 247 //=======================================================================
 248 void BRepMesh_IncrementalMesh::discretizeFreeEdges()
 249 {
 250   TopExp_Explorer aExplorer(myShape ,TopAbs_EDGE, TopAbs_FACE);
 251   for (; aExplorer.More(); aExplorer.Next())
 252   {
 253     const TopoDS_Edge& aEdge = TopoDS::Edge(aExplorer.Current());
 254     if(!BRep_Tool::IsGeometric(aEdge))
 255       continue;
 256
 257     TopLoc_Location aLoc;
 258     Standard_Real aEdgeDeflection  = edgeDeflection(aEdge);
 259     Handle(Poly_Polygon3D) aPoly3D = BRep_Tool::Polygon3D(aEdge, aLoc);
 260     if (!aPoly3D.IsNull() && aPoly3D->Deflection() < 1.1 * aEdgeDeflection)
 261       continue;
 262
 263     BRepAdaptor_Curve aCurve(aEdge);
 264     GCPnts_TangentialDeflection aDiscret(aCurve, aCurve.FirstParameter(),
 265       aCurve.LastParameter(), myAngle, aEdgeDeflection, 2, myMinSize);
 266
 267     Standard_Integer aNodesNb = aDiscret.NbPoints();
 268     TColgp_Array1OfPnt   aNodes  (1, aNodesNb);
 269     TColStd_Array1OfReal aUVNodes(1, aNodesNb);
 270     for (Standard_Integer i = 1; i <= aNodesNb; ++i)
 271     {
 272       aNodes  (i) = aDiscret.Value(i);
 273       aUVNodes(i) = aDiscret.Parameter(i);
 274     }
 275
 276     aPoly3D = new Poly_Polygon3D(aNodes, aUVNodes);
 277     aPoly3D->Deflection(myDeflection);
 278
 279     BRep_Builder aBuilder;
 280     aBuilder.UpdateEdge(aEdge, aPoly3D);
 281   }
 282 }
 283
 284 //=======================================================================
 285 //function : edgeDeflection
 286 //purpose  :
 287 //=======================================================================
 288 Standard_Real BRepMesh_IncrementalMesh::edgeDeflection(
 289   const TopoDS_Edge& theEdge)
 290 {
 291   if (myEdgeDeflection.IsBound(theEdge))
 292     return myEdgeDeflection(theEdge);
 293
 294   Standard_Real aEdgeDeflection;
 295   if (myRelative)
 296   {
 297     Standard_Real aScale;
 298     aEdgeDeflection = BRepMesh_ShapeTool::RelativeEdgeDeflection(theEdge,
 299       myDeflection, myMaxShapeSize, aScale);
 300   }
 301   else
 302     aEdgeDeflection = myDeflection;
 303
 304   myEdgeDeflection.Bind(theEdge, aEdgeDeflection);
 305   return aEdgeDeflection;
 306 }
 307
 308 //=======================================================================
 309 //function : faceDeflection
 310 //purpose  :
 311 //=======================================================================
 312 Standard_Real BRepMesh_IncrementalMesh::faceDeflection(
 313   const TopoDS_Face& theFace)
 314 {
 315   if (!myRelative)
 316     return myDeflection;
 317
 318   Standard_Integer aEdgesNb        = 0;
 319   Standard_Real    aFaceDeflection = 0.;
 320
 321   TopExp_Explorer aEdgeIt(theFace, TopAbs_EDGE);
 322   for (; aEdgeIt.More(); aEdgeIt.Next(), ++aEdgesNb)
 323   {
 324     const TopoDS_Edge& aEdge = TopoDS::Edge(aEdgeIt.Current());
 325     aFaceDeflection += edgeDeflection(aEdge);
 326   }
 327
 328   return (aEdgesNb == 0) ? myDeflection : (aFaceDeflection / aEdgesNb);
 329 }
 330
 331 //=======================================================================
 332 //function : update(edge)
 333 //purpose  :
 334 //=======================================================================
 335 void BRepMesh_IncrementalMesh::update(const TopoDS_Edge& theEdge)
 336 {
 337   if (!myEdges.IsBound(theEdge))
 338     myEdges.Bind(theEdge, BRepMesh::DMapOfTriangulationBool());
 339
 340   Standard_Real aEdgeDeflection = edgeDeflection(theEdge);
 341   // Check that triangulation relies to face of the given shape.
 342   const TopTools_IndexedDataMapOfShapeListOfShape& aMapOfSharedFaces =
 343     myMesh->SharedFaces();
 344
 345   const TopTools_ListOfShape& aSharedFaces =
 346     aMapOfSharedFaces.FindFromKey(theEdge);
 347
 348   TopTools_ListIteratorOfListOfShape aSharedFaceIt(aSharedFaces);
 349   for (; aSharedFaceIt.More(); aSharedFaceIt.Next())
 350   {
 351     TopLoc_Location aLoc;
 352     const TopoDS_Face& aFace = TopoDS::Face(aSharedFaceIt.Value());
 353     const Handle(Poly_Triangulation)& aFaceTriangulation =
 354       BRep_Tool::Triangulation(aFace, aLoc);
 355
 356     if (aFaceTriangulation.IsNull())
 357       continue;
 358
 359     Standard_Boolean isConsistent = Standard_False;
 360     const Handle(Poly_PolygonOnTriangulation)& aPolygon =
 361       BRep_Tool::PolygonOnTriangulation(theEdge, aFaceTriangulation, aLoc);
 362
 363     if (!aPolygon.IsNull())
 364     {
 365       isConsistent = aPolygon->Deflection() < 1.1 * aEdgeDeflection &&
 366         aPolygon->HasParameters();
 367
 368       if (!isConsistent)
 369       {
 370         myModified = Standard_True;
 371         BRepMesh_ShapeTool::NullifyEdge(theEdge, aFaceTriangulation, aLoc);
 372       }
 373     }
 374
 375     myEdges(theEdge).Bind(aFaceTriangulation, isConsistent);
 376   }
 377 }
 378
 379 //=======================================================================
 380 //function : isToBeMeshed
 381 //purpose  :
 382 //=======================================================================
 383 Standard_Boolean BRepMesh_IncrementalMesh::toBeMeshed(
 384   const TopoDS_Face&     theFace,
 385   const Standard_Boolean isWithCheck)
 386 {
 387   TopLoc_Location aLoc;
 388   const Handle(Poly_Triangulation)& aTriangulation =
 389     BRep_Tool::Triangulation(theFace, aLoc);
 390
 391   if (aTriangulation.IsNull())
 392     return Standard_True;
 393
 394   if (isWithCheck)
 395   {
 396     Standard_Real aFaceDeflection = faceDeflection(theFace);
 397     if (aTriangulation->Deflection() < 1.1 * aFaceDeflection)
 398     {
 399       Standard_Boolean isEdgesConsistent = Standard_True;
 400       TopExp_Explorer aEdgeIt(theFace, TopAbs_EDGE);
 401       for (; aEdgeIt.More() && isEdgesConsistent; aEdgeIt.Next())
 402       {
 403         const TopoDS_Edge& aEdge = TopoDS::Edge(aEdgeIt.Current());
 404         if (!myEdges.IsBound(aEdge))
 405           continue;
 406
 407         BRepMesh::DMapOfTriangulationBool& aTriMap = myEdges(aEdge);
 408         isEdgesConsistent &= aTriMap.IsBound(aTriangulation) &&
 409           aTriMap(aTriangulation);
 410       }
 411
 412       if (isEdgesConsistent)
 413       {
 414         // #25080: check that indices of links forming triangles are in range.
 415         Standard_Boolean isTriangulationConsistent = Standard_True;
 416         const Standard_Integer aNodesNb = aTriangulation->NbNodes();
 417         const Poly_Array1OfTriangle& aTriangles = aTriangulation->Triangles();
 418         Standard_Integer i = aTriangles.Lower();
 419         for (; i <= aTriangles.Upper() && isTriangulationConsistent; ++i)
 420         {
 421           const Poly_Triangle& aTriangle = aTriangles(i);
 422           Standard_Integer n[3];
 423           aTriangle.Get(n[0], n[1], n[2]);
 424           for (Standard_Integer j = 0; j < 3 && isTriangulationConsistent; ++j)
 425             isTriangulationConsistent = (n[j] >= 1 && n[j] <= aNodesNb);
 426         }
 427
 428         if (isTriangulationConsistent)
 429           return Standard_False;
 430       }
 431     }
 432   }
 433
 434   // Nullify edges
 435   TopExp_Explorer aEdgeIt(theFace, TopAbs_EDGE);
 436   for (; aEdgeIt.More(); aEdgeIt.Next())
 437   {
 438     const TopoDS_Edge& aEdge = TopoDS::Edge(aEdgeIt.Current());
 439     BRepMesh_ShapeTool::NullifyEdge(aEdge, aTriangulation, aLoc);
 440   }
 441
 442   BRepMesh_ShapeTool::NullifyFace(theFace);
 443   return Standard_True;
 444 }
 445
 446 //=======================================================================
 447 //function : update(face)
 448 //purpose  :
 449 //=======================================================================
 450 void BRepMesh_IncrementalMesh::update(const TopoDS_Face& theFace)
 451 {
 452   if (!toBeMeshed(theFace, Standard_True))
 453     return;
 454
 455   myModified = Standard_True;
 456   Standard_Integer aStatus = myMesh->Add(theFace);
 457
 458   myStatus |= aStatus;
 459   if (aStatus != BRepMesh_ReMesh)
 460     return;
 461
 462   BRepMesh::MapOfShape aUsedFaces;
 463   aUsedFaces.Add(theFace);
 464
 465   const TopTools_IndexedDataMapOfShapeListOfShape& aMapOfSharedFaces =
 466     myMesh->SharedFaces();
 467
 468   TopExp_Explorer aEdgeIt(theFace, TopAbs_EDGE);
 469   for (; aEdgeIt.More(); aEdgeIt.Next())
 470   {
 471     const TopoDS_Edge& aEdge = TopoDS::Edge(aEdgeIt.Current());
 472     if (aMapOfSharedFaces.FindIndex(aEdge) == 0)
 473       continue;
 474
 475     const TopTools_ListOfShape& aSharedFaces = aMapOfSharedFaces.FindFromKey(aEdge);
 476     TopTools_ListIteratorOfListOfShape aSharedFaceIt(aSharedFaces);
 477     for (; aSharedFaceIt.More(); aSharedFaceIt.Next())
 478     {
 479       const TopoDS_Face& aFace = TopoDS::Face(aSharedFaceIt.Value());
 480       if (aUsedFaces.Contains(aFace))
 481         continue;
 482
 483       aUsedFaces.Add(aFace);
 484       toBeMeshed(aFace, Standard_False);
 485
 486       myStatus |= myMesh->Add(aFace);
 487     }
 488   }
 489 }
 490
 491 //=======================================================================
 492 //function : commit
 493 //purpose  :
 494 //=======================================================================
 495 void BRepMesh_IncrementalMesh::commit()
 496 {
 497   NCollection_Vector<TopoDS_Face>::Iterator aFaceIt(myFaces);
 498   for (; aFaceIt.More(); aFaceIt.Next())
 499     commitEdges(aFaceIt.Value());
 500
 501   discretizeFreeEdges();
 502 }
 503
 504 //=======================================================================
 505 //function : commitEdges
 506 //purpose  :
 507 //=======================================================================
 508 void BRepMesh_IncrementalMesh::commitEdges(const TopoDS_Face& theFace)
 509 {
 510   TopoDS_Face aFace = theFace;
 511   aFace.Orientation(TopAbs_FORWARD);
 512
 513   Handle(BRepMesh_FaceAttribute) aFaceAttribute;
 514   if (!myMesh->GetFaceAttribute(aFace, aFaceAttribute))
 515     return;
 516
 517   if (!aFaceAttribute->IsValid())
 518   {
 519     myStatus |= aFaceAttribute->GetStatus();
 520     return;
 521   }
 522
 523   TopLoc_Location aLoc;
 524   Handle(Poly_Triangulation) aTriangulation = BRep_Tool::Triangulation(aFace, aLoc);
 525
 526   if (aTriangulation.IsNull())
 527     return;
 528
 529   try
 530   {
 531     OCC_CATCH_SIGNALS
 532
 533     // Store discretization of edges
 534     BRepMesh::HDMapOfShapePairOfPolygon& aInternalEdges = aFaceAttribute->ChangeInternalEdges();
 535     BRepMesh::DMapOfShapePairOfPolygon::Iterator aEdgeIt(*aInternalEdges);
 536     for (; aEdgeIt.More(); aEdgeIt.Next())
 537     {
 538       const TopoDS_Edge& aEdge = TopoDS::Edge(aEdgeIt.Key());
 539       const BRepMesh_PairOfPolygon& aPolyPair = aEdgeIt.Value();
 540       const Handle(Poly_PolygonOnTriangulation)& aPolygon1 = aPolyPair.First();
 541       const Handle(Poly_PolygonOnTriangulation)& aPolygon2 = aPolyPair.Last();
 542
 543       if (aPolygon1 == aPolygon2)
 544         BRepMesh_ShapeTool::UpdateEdge(aEdge, aPolygon1, aTriangulation, aLoc);
 545       else
 546         BRepMesh_ShapeTool::UpdateEdge(aEdge, aPolygon1, aPolygon2, aTriangulation, aLoc);
 547     }
 548   }
 549   catch (Standard_Failure)
 550   {
 551     myStatus |= BRepMesh_Failure;
 552   }
 553 }
 554
 555 //=======================================================================
 556 //function : Discret
 557 //purpose  :
 558 //=======================================================================
 559 Standard_Integer BRepMesh_IncrementalMesh::Discret(
 560   const TopoDS_Shape&    theShape,
 561   const Standard_Real    theDeflection,
 562   const Standard_Real    theAngle,
 563   BRepMesh_DiscretRoot* &theAlgo)
 564 {
 565   BRepMesh_IncrementalMesh* anAlgo = new BRepMesh_IncrementalMesh();
 566   anAlgo->SetDeflection(theDeflection);
 567   anAlgo->SetAngle     (theAngle);
 568   anAlgo->SetShape     (theShape);
 569   anAlgo->SetParallel  (IS_IN_PARALLEL);
 570   theAlgo = anAlgo;
 571   return 0; // no error
 572 }
 573
 574 //=======================================================================
 575 //function : IsParallelDefault
 576 //purpose  :
 577 //=======================================================================
 578 Standard_Boolean BRepMesh_IncrementalMesh::IsParallelDefault()
 579 {
 580 #ifdef HAVE_TBB
 581   return IS_IN_PARALLEL;
 582 #else
 583   // no alternative parallelization yet - flag has no meaning
 584   return Standard_False;
 585 #endif
 586 }
 587
 588 //=======================================================================
 589 //function : Discret
 590 //purpose  :
 591 //=======================================================================
 592 void BRepMesh_IncrementalMesh::SetParallelDefault(
 593   const Standard_Boolean theInParallel)
 594 {
 595   IS_IN_PARALLEL = theInParallel;
 596 }
 597
 598 //! Export Mesh Plugin entry function
 599 DISCRETPLUGIN(BRepMesh_IncrementalMesh)