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