src/BOPAlgo/BOPAlgo_Tools.cxx

   1 // Created by: Peter KURNEV
   2 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   3 //
   4 // This file is part of Open CASCADE Technology software library.
   5 //
   6 // This library is free software; you can redistribute it and/or modify it under
   7 // the terms of the GNU Lesser General Public License version 2.1 as published
   8 // by the Free Software Foundation, with special exception defined in the file
   9 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  10 // distribution for complete text of the license and disclaimer of any warranty.
  11 //
  12 // Alternatively, this file may be used under the terms of Open CASCADE
  13 // commercial license or contractual agreement.
  14
  15
  16 #include <BOPAlgo_Tools.hxx>
  17
  18 #include <BOPAlgo_Builder.hxx>
  19 #include <BOPAlgo_BuilderFace.hxx>
  20 #include <BOPDS_CommonBlock.hxx>
  21 #include <BOPDS_DataMapOfPaveBlockListOfPaveBlock.hxx>
  22 #include <BOPDS_DS.hxx>
  23 #include <BOPDS_IndexedMapOfPaveBlock.hxx>
  24 #include <BOPDS_MapOfPaveBlock.hxx>
  25 #include <BOPDS_PaveBlock.hxx>
  26 #include <BOPTools_AlgoTools.hxx>
  27 #include <BOPTools_AlgoTools2D.hxx>
  28 #include <BOPTools_BoxTree.hxx>
  29 #include <BOPTools_Parallel.hxx>
  30 #include <BRep_Builder.hxx>
  31 #include <BRep_Tool.hxx>
  32 #include <BRepAdaptor_Curve.hxx>
  33 #include <BRepBndLib.hxx>
  34 #include <BRepBuilderAPI_MakeFace.hxx>
  35 #include <BRepLib.hxx>
  36 #include <Bnd_Tools.hxx>
  37 #include <GeomAPI_ProjectPointOnCurve.hxx>
  38 #include <GeomAPI_ProjectPointOnSurf.hxx>
  39 #include <gp_Circ.hxx>
  40 #include <gp_Dir.hxx>
  41 #include <gp_Elips.hxx>
  42 #include <gp_Hypr.hxx>
  43 #include <gp_Parab.hxx>
  44 #include <gp_Pln.hxx>
  45 #include <gp_Pnt.hxx>
  46 #include <gp_Vec.hxx>
  47 #include <IntTools_Context.hxx>
  48 #include <NCollection_IncAllocator.hxx>
  49 #include <NCollection_Vector.hxx>
  50 #include <Standard_ErrorHandler.hxx>
  51 #include <Standard_Failure.hxx>
  52 #include <TColStd_IndexedMapOfInteger.hxx>
  53 #include <TopExp.hxx>
  54 #include <TopExp_Explorer.hxx>
  55 #include <TopoDS.hxx>
  56 #include <TopoDS_Edge.hxx>
  57 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
  58 #include <TopTools_IndexedMapOfShape.hxx>
  59 #include <TopTools_MapOfShape.hxx>
  60
  61 #include <algorithm>
  62
  63 typedef NCollection_IndexedDataMap
  64   <TopoDS_Shape, gp_Dir, TopTools_ShapeMapHasher> BOPAlgo_IndexedDataMapOfShapeDir;
  65 typedef NCollection_IndexedDataMap
  66   <TopoDS_Shape, gp_Pln, TopTools_ShapeMapHasher> BOPAlgo_IndexedDataMapOfShapePln;
  67
  68 static
  69   void MakeWires(const TopTools_IndexedMapOfShape& theEdges,
  70                  TopoDS_Compound& theWires,
  71                  const Standard_Boolean theCheckUniquePlane,
  72                  BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
  73                  TopTools_MapOfShape& theMEdgesNoUniquePlane);
  74
  75 static
  76   Standard_Boolean FindPlane(const BRepAdaptor_Curve& theCurve,
  77                              gp_Pln& thePlane);
  78
  79 static
  80   Standard_Boolean FindPlane(const TopoDS_Shape& theWire,
  81                              gp_Pln& thePlane,
  82                              BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
  83                              TopTools_MapOfShape& theMEdgesNoUniquePlane);
  84
  85 static
  86   Standard_Boolean FindEdgeTangent(const TopoDS_Edge& theEdge,
  87                                    BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
  88                                    gp_Dir& theTgt);
  89
  90 static
  91   Standard_Boolean FindEdgeTangent(const BRepAdaptor_Curve& theCurve,
  92                                    gp_Vec& theTangent);
  93
  94 //=======================================================================
  95 //function : FillMap
  96 //purpose  :
  97 //=======================================================================
  98 void BOPAlgo_Tools::FillMap(const Handle(BOPDS_PaveBlock)& aPB,
  99                             const Standard_Integer nF,
 100                             BOPDS_IndexedDataMapOfPaveBlockListOfInteger& aMPBLI,
 101                             const Handle(NCollection_BaseAllocator)& aAllocator)
 102 {
 103   TColStd_ListOfInteger *pLI = aMPBLI.ChangeSeek(aPB);
 104   if (!pLI) {
 105     pLI = &aMPBLI(aMPBLI.Add(aPB, TColStd_ListOfInteger(aAllocator)));
 106   }
 107   pLI->Append(nF);
 108 }
 109 //=======================================================================
 110 //function : PerformCommonBlocks
 111 //purpose  :
 112 //=======================================================================
 113 void BOPAlgo_Tools::PerformCommonBlocks(BOPDS_IndexedDataMapOfPaveBlockListOfPaveBlock& aMPBLPB,
 114                                         const Handle(NCollection_BaseAllocator)& aAllocator,
 115                                         BOPDS_PDS& pDS,
 116                                         const Handle(IntTools_Context)& theContext)
 117 {
 118   Standard_Integer aNbCB;
 119   //
 120   aNbCB=aMPBLPB.Extent();
 121   if (!aNbCB) {
 122     return;
 123   }
 124   // Make Blocks of the pave blocks
 125   NCollection_List<BOPDS_ListOfPaveBlock> aMBlocks(aAllocator);
 126   BOPAlgo_Tools::MakeBlocks<Handle(BOPDS_PaveBlock), TColStd_MapTransientHasher>(aMPBLPB, aMBlocks, aAllocator);
 127
 128   // Use temporary allocator for the local fence map
 129   Handle(NCollection_IncAllocator) anAllocTmp = new NCollection_IncAllocator;
 130
 131   NCollection_List<BOPDS_ListOfPaveBlock>::Iterator aItB(aMBlocks);
 132   for (; aItB.More(); aItB.Next()) {
 133     const BOPDS_ListOfPaveBlock& aLPB = aItB.Value();
 134     Standard_Integer aNbPB = aLPB.Extent();
 135     if (aNbPB < 2)
 136       continue;
 137
 138     // Reset the allocator
 139     anAllocTmp->Reset();
 140     // New common block
 141     Handle(BOPDS_CommonBlock) aCB;
 142     // Faces of the common block
 143     TColStd_ListOfInteger aLFaces;
 144     // Fence map to avoid duplicates in the list of faces of the common block
 145     TColStd_MapOfInteger aMFaces(1, anAllocTmp);
 146
 147     BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
 148     for (; aItLPB.More(); aItLPB.Next())
 149     {
 150       const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
 151       if (pDS->IsCommonBlock(aPB))
 152       {
 153         const Handle(BOPDS_CommonBlock)& aCBx = pDS->CommonBlock(aPB);
 154         // Move all faces to the new common block
 155         TColStd_ListIteratorOfListOfInteger aItLF(aCBx->Faces());
 156         for (; aItLF.More(); aItLF.Next())
 157         {
 158           const Standard_Integer nF = aItLF.Value();
 159           // Append to common list avoiding duplicates
 160           if (aMFaces.Add(nF))
 161             aLFaces.Append(nF);
 162         }
 163         if (aCB.IsNull())
 164           aCB = aCBx;
 165       }
 166     }
 167
 168     if (aCB.IsNull())
 169       aCB = new BOPDS_CommonBlock;
 170
 171     aCB->SetPaveBlocks(aLPB);
 172     aCB->SetFaces(aLFaces);
 173     for (aItLPB.Initialize(aLPB); aItLPB.More(); aItLPB.Next())
 174       pDS->SetCommonBlock(aItLPB.Value(), aCB);
 175
 176     // Compute tolerance for Common Block
 177     Standard_Real aTolCB = BOPAlgo_Tools::ComputeToleranceOfCB(aCB, pDS, theContext);
 178     aCB->SetTolerance(aTolCB);
 179   }
 180 }
 181 //=======================================================================
 182 //function : PerformCommonBlocks
 183 //purpose  :
 184 //=======================================================================
 185 void BOPAlgo_Tools::PerformCommonBlocks(const BOPDS_IndexedDataMapOfPaveBlockListOfInteger& aMPBLI,
 186                                         const Handle(NCollection_BaseAllocator)& ,//aAllocator
 187                                         BOPDS_PDS& pDS,
 188                                         const Handle(IntTools_Context)& theContext)
 189 {
 190   Standard_Integer nF, i, aNb;
 191   TColStd_ListIteratorOfListOfInteger aItLI;
 192   Handle(BOPDS_PaveBlock) aPB;
 193   Handle(BOPDS_CommonBlock) aCB;
 194   //
 195   aNb=aMPBLI.Extent();
 196   for (i=1; i<=aNb; ++i) {
 197     aPB=aMPBLI.FindKey(i);
 198     if (pDS->IsCommonBlock(aPB)) {
 199       aCB=pDS->CommonBlock(aPB);
 200     }
 201     else {
 202       aCB=new BOPDS_CommonBlock;
 203       aCB->AddPaveBlock(aPB);
 204     }
 205     //
 206     const TColStd_ListOfInteger& aLI=aMPBLI.FindFromKey(aPB);
 207     TColStd_ListOfInteger aNewFaces;
 208     const TColStd_ListOfInteger& anOldFaces = aCB->Faces();
 209     aItLI.Initialize(aLI);
 210     for (; aItLI.More(); aItLI.Next()) {
 211       nF=aItLI.Value();
 212       // the both lists aLI and anOldFaces are expected to be short,
 213       // so we can allow to run nested loop here
 214       TColStd_ListIteratorOfListOfInteger it(anOldFaces);
 215       for (; it.More(); it.Next()) {
 216         if (it.Value() == nF)
 217           break;
 218       }
 219       if (!it.More()) {
 220         aNewFaces.Append(nF);
 221       }
 222     }
 223     aCB->AppendFaces(aNewFaces);
 224     pDS->SetCommonBlock(aPB, aCB);
 225     // Compute tolerance for Common Block
 226     Standard_Real aTolCB = BOPAlgo_Tools::ComputeToleranceOfCB(aCB, pDS, theContext);
 227     aCB->SetTolerance(aTolCB);
 228   }
 229 }
 230 //=======================================================================
 231 //function : ComputeToleranceOfCB
 232 //purpose  :
 233 //=======================================================================
 234 Standard_Real BOPAlgo_Tools::ComputeToleranceOfCB
 235                    (const Handle(BOPDS_CommonBlock)& theCB,
 236                     const BOPDS_PDS theDS,
 237                     const Handle(IntTools_Context)& theContext)
 238 {
 239   Standard_Real aTolMax = 0.;
 240   if (theCB.IsNull()) {
 241     return aTolMax;
 242   }
 243   //
 244   const Handle(BOPDS_PaveBlock)& aPBR = theCB->PaveBlock1();
 245   Standard_Integer nE = aPBR->OriginalEdge();
 246   const TopoDS_Edge& aEOr = *(TopoDS_Edge*)&theDS->Shape(nE);
 247   aTolMax = BRep_Tool::Tolerance(aEOr);
 248   //
 249   const BOPDS_ListOfPaveBlock& aLPB = theCB->PaveBlocks();
 250   const TColStd_ListOfInteger& aLFI = theCB->Faces();
 251   //
 252   if ((aLPB.Extent() < 2) && aLFI.IsEmpty()) {
 253     return aTolMax;
 254   }
 255   //
 256   const Standard_Integer aNbPnt = 11;
 257   Standard_Real aTol, aT, aT1, aT2, aDt;
 258   gp_Pnt aP;
 259   //
 260   const Handle(Geom_Curve)& aC3D = BRep_Tool::Curve(aEOr, aT1, aT2);
 261   //
 262   aPBR->Range(aT1, aT2);
 263   aDt = (aT2 - aT1) / (aNbPnt + 1);
 264   //
 265   Handle(IntTools_Context) aCtx = theContext;
 266   if (aCtx.IsNull())
 267     aCtx = new IntTools_Context();
 268
 269   // compute max tolerance for common blocks on edges
 270   if (aLPB.Extent() > 1) {
 271     // compute max distance between edges
 272     BOPDS_ListIteratorOfListOfPaveBlock aItPB;
 273     GeomAPI_ProjectPointOnCurve aProjPC;
 274     //
 275     aItPB.Initialize(aLPB);
 276     for (; aItPB.More(); aItPB.Next()) {
 277       const Handle(BOPDS_PaveBlock)& aPB = aItPB.Value();
 278       if (aPB == aPBR) {
 279         continue;
 280       }
 281       //
 282       nE = aPB->OriginalEdge();
 283       const TopoDS_Edge& aE = *(TopoDS_Edge*)&theDS->Shape(nE);
 284       aTol = BRep_Tool::Tolerance(aE);
 285       //
 286       aProjPC = aCtx->ProjPC(aE);
 287       //
 288       aT = aT1;
 289       for (Standard_Integer i=1; i <= aNbPnt; i++) {
 290         aT += aDt;
 291         aC3D->D0(aT, aP);
 292         aProjPC.Perform(aP);
 293         if (aProjPC.NbPoints()) {
 294           Standard_Real aTolNew = aTol + aProjPC.LowerDistance();
 295           if (aTolNew > aTolMax) {
 296             aTolMax = aTolNew;
 297           }
 298         }
 299       }
 300     }
 301   }
 302   //
 303   // compute max tolerance for common blocks on faces
 304   if (aLFI.Extent()) {
 305     Standard_Integer nF;
 306     GeomAPI_ProjectPointOnSurf aProjPS;
 307     TColStd_ListIteratorOfListOfInteger aItLI;
 308     //
 309     aItLI.Initialize(aLFI);
 310     for (; aItLI.More(); aItLI.Next()) {
 311       nF = aItLI.Value();
 312       const TopoDS_Face& aF = *(TopoDS_Face*)&theDS->Shape(nF);
 313       aTol = BRep_Tool::Tolerance(aF);
 314       //
 315       aProjPS = aCtx->ProjPS(aF);
 316       //
 317       aT = aT1;
 318       for (Standard_Integer i=1; i <= aNbPnt; i++) {
 319         aT += aDt;
 320         aC3D->D0(aT, aP);
 321         aProjPS.Perform(aP);
 322         if (aProjPS.NbPoints()) {
 323           Standard_Real aTolNew = aTol + aProjPS.LowerDistance();
 324           if (aTolNew > aTolMax) {
 325             aTolMax = aTolNew;
 326           }
 327         }
 328       }
 329     }
 330   }
 331   //
 332   return aTolMax;
 333 }
 334
 335 //=======================================================================
 336 //function : EdgesToWires
 337 //purpose  :
 338 //=======================================================================
 339 Standard_Integer BOPAlgo_Tools::EdgesToWires(const TopoDS_Shape& theEdges,
 340                                              TopoDS_Shape& theWires,
 341                                              const Standard_Boolean theShared,
 342                                              const Standard_Real theAngTol)
 343 {
 344   Standard_Integer iErr = 0;
 345   //
 346   // 1. Check the input edges
 347   //
 348   // List of edges to process
 349   TopTools_ListOfShape aLE;
 350   //
 351   TopExp_Explorer aExp(theEdges, TopAbs_EDGE);
 352   for (; aExp.More(); aExp.Next()) {
 353     const TopoDS_Edge& aE = TopoDS::Edge(aExp.Current());
 354     if (!BRep_Tool::Degenerated(aE) && BRep_Tool::IsGeometric(aE)) {
 355       aLE.Append(aExp.Current());
 356     }
 357   }
 358   //
 359   if (aLE.IsEmpty()) {
 360     // no edges to process
 361     iErr = 1;
 362     return iErr;
 363   }
 364   //
 365   BRep_Builder aBB;
 366   TopoDS_Compound aRWires;
 367   aBB.MakeCompound(aRWires);
 368   //
 369   if (aLE.Extent() == 1) {
 370     TopoDS_Wire aWire;
 371     aBB.MakeWire(aWire);
 372     aBB.Add(aWire, aLE.First());
 373     aBB.Add(aRWires, aWire);
 374     theWires = aRWires;
 375     return iErr;
 376   }
 377   //
 378   // 2. Make compound of shared edges
 379   TopoDS_Shape aSEdges;
 380   //
 381   if (!theShared) {
 382     // intersect the edges if necessary
 383     BOPAlgo_Builder aGF;
 384     aGF.SetArguments(aLE);
 385     aGF.Perform();
 386     if (aGF.HasErrors()) {
 387       // unable to share the edges
 388       iErr = 2;
 389       return iErr;
 390     }
 391     //
 392     aSEdges = aGF.Shape();
 393   }
 394   else {
 395     aBB.MakeCompound(TopoDS::Compound(aSEdges));
 396     TopTools_ListIteratorOfListOfShape aItLE(aLE);
 397     for (; aItLE.More(); aItLE.Next()) {
 398       aBB.Add(aSEdges, aItLE.Value());
 399     }
 400   }
 401   //
 402   // 3. Find edges located in the same planes and make wires from them.
 403   // If the plane cannot be found for a single edge, then it is necessary
 404   // to find all pairs of connected edges with the same cross product.
 405
 406   // Try to compute the plane in which the edge is located
 407   BOPAlgo_IndexedDataMapOfShapePln aDMEdgePln;
 408   // Compute the tangent direction for the edges for which the plane is not defined
 409   BOPAlgo_IndexedDataMapOfShapeDir aDMEdgeTgt;
 410   //
 411   // edges for which the plane is not found
 412   TopTools_MapOfShape aMEdgesNoUniquePlane;
 413   //
 414   // edges for which the plane cannot be found on a single edge
 415   TopoDS_Compound aLEdges;
 416   aBB.MakeCompound(aLEdges);
 417   //
 418   aExp.Init(aSEdges, TopAbs_EDGE);
 419   for (; aExp.More(); aExp.Next()) {
 420     const TopoDS_Edge& aE = TopoDS::Edge(aExp.Current());
 421     BRepAdaptor_Curve aBAC(aE);
 422     //
 423     gp_Pln aPln;
 424     if (FindPlane(aBAC, aPln)) {
 425       aDMEdgePln.Add(aE, aPln);
 426     }
 427     else {
 428       gp_Vec aVT;
 429       if (FindEdgeTangent(aBAC, aVT)) {
 430         aDMEdgeTgt.Add(aE, gp_Dir(aVT));
 431         aBB.Add(aLEdges, aE);
 432         aMEdgesNoUniquePlane.Add(aE);
 433       }
 434     }
 435   }
 436   //
 437   typedef NCollection_List<gp_Dir> BOPAlgo_ListOfDir;
 438   //
 439   // to avoid processing of the same edges in the same plane store
 440   // the processed planes into a list and use it as a fence map
 441   BOPAlgo_ListOfDir aLPFence;
 442   //
 443   // used edges
 444   TopTools_MapOfShape aMEFence;
 445   //
 446   // look for a planes on the single edges
 447   Standard_Integer i, j, aNbPlanes = aDMEdgePln.Extent(), aNbEdges = aDMEdgeTgt.Extent();
 448   for (i = 1; i <= aNbPlanes; ++i) {
 449     const TopoDS_Shape& aEI = aDMEdgePln.FindKey(i);
 450     if (!aMEFence.Add(aEI)) {
 451       continue;
 452     }
 453     //
 454     const gp_Pln& aPlnI = aDMEdgePln(i);
 455     const gp_Dir& aDI = aPlnI.Position().Direction();
 456     //
 457     aLPFence.Append(aDI);
 458     //
 459     TopTools_IndexedMapOfShape aMEPln;
 460     aMEPln.Add(aEI);
 461     //
 462     TopTools_IndexedMapOfShape aMV;
 463     TopExp::MapShapes(aEI, TopAbs_VERTEX, aMV);
 464     //
 465     // look for other edges with the plane parallel to current one
 466     for (j = i + 1; j <= aNbPlanes; ++j) {
 467       const gp_Dir& aDJ = aDMEdgePln(j).Position().Direction();
 468       if (aDI.IsParallel(aDJ, theAngTol)) {
 469         const TopoDS_Shape& aEJ = aDMEdgePln.FindKey(j);
 470         aMEPln.Add(aEJ);
 471         aMEFence.Add(aEJ);
 472         TopExp::MapShapes(aEJ, TopAbs_VERTEX, aMV);
 473       }
 474     }
 475     //
 476     // look for all other edges located in the plane parallel to current one
 477     TopoDS_Compound aCEPln;
 478     aBB.MakeCompound(aCEPln);
 479     //
 480     for (j = 1; j <= aNbEdges; ++j) {
 481       const gp_Dir& aDJ = aDMEdgeTgt(j);
 482       if (aDI.IsNormal(aDJ, theAngTol)) {
 483         aBB.Add(aCEPln, aDMEdgeTgt.FindKey(j));
 484       }
 485     }
 486     //
 487     // make blocks of these edges and check blocks to be connected
 488     // to any of the already added edges or forming a wire themselves
 489     TopTools_ListOfShape aLCBE;
 490     BOPTools_AlgoTools::MakeConnexityBlocks(aCEPln, TopAbs_VERTEX, TopAbs_EDGE, aLCBE);
 491     //
 492     // make wire from each block
 493     TopTools_ListIteratorOfListOfShape aItLCB(aLCBE);
 494     for (; aItLCB.More(); aItLCB.Next()) {
 495       const TopoDS_Shape& aCBE = aItLCB.Value();
 496       //
 497       // check connectivity
 498       TopExp_Explorer aExpV(aCBE, TopAbs_VERTEX);
 499       for (; aExpV.More(); aExpV.Next()) {
 500         if (aMV.Contains(aExpV.Current())) {
 501           break;
 502         }
 503       }
 504       //
 505       Standard_Boolean bAddBlock = aExpV.More();
 506       if (!bAddBlock) {
 507         // check if the edges are forming a wire
 508         gp_Pln aPln;
 509         bAddBlock = FindPlane(aCBE, aPln, aDMEdgeTgt, aMEdgesNoUniquePlane);
 510       }
 511       //
 512       if (bAddBlock) {
 513         // add edges
 514         for (TopoDS_Iterator aItE(aCBE); aItE.More(); aItE.Next()) {
 515           aMEPln.Add(aItE.Value());
 516         }
 517       }
 518     }
 519     //
 520     MakeWires(aMEPln, aRWires, Standard_False, aDMEdgeTgt, aMEdgesNoUniquePlane);
 521   }
 522   //
 523   // make connection map from vertices to edges to find the connected pairs
 524   TopTools_IndexedDataMapOfShapeListOfShape aDMVE;
 525   TopExp::MapShapesAndAncestors(aLEdges, TopAbs_VERTEX, TopAbs_EDGE, aDMVE);
 526   //
 527   // find planes for connected edges
 528   Standard_Integer aNbV = aDMVE.Extent();
 529   for (i = 1; i <= aNbV; ++i) {
 530     const TopTools_ListOfShape& aLEI = aDMVE(i);
 531     if (aLEI.Extent() < 2) {
 532       continue;
 533     }
 534     //
 535     TopTools_ListIteratorOfListOfShape aItLEI1(aLEI);
 536     for (; aItLEI1.More(); aItLEI1.Next()) {
 537       const TopoDS_Shape& aEI1 = aItLEI1.Value();
 538       const gp_Dir& aDI1 = aDMEdgeTgt.FindFromKey(aEI1);
 539       //
 540       TopTools_ListIteratorOfListOfShape aItLEI2(aLEI);
 541       for (; aItLEI2.More(); aItLEI2.Next()) {
 542         const TopoDS_Shape& aEI2 = aItLEI2.Value();
 543         if (aEI2.IsSame(aEI1)) {
 544           continue;
 545         }
 546         //
 547         const gp_Dir& aDI2 = aDMEdgeTgt.FindFromKey(aEI2);
 548         //
 549         if (aDI1.IsParallel(aDI2, theAngTol)) {
 550           continue;
 551         }
 552         //
 553         gp_Dir aDNI = aDI1^aDI2;
 554         //
 555         // check if this normal direction has not been checked yet
 556         BOPAlgo_ListOfDir::Iterator aItLPln(aLPFence);
 557         for (; aItLPln.More(); aItLPln.Next()) {
 558           if (aDNI.IsParallel(aItLPln.Value(), theAngTol)) {
 559             break;
 560           }
 561         }
 562         if (aItLPln.More()) {
 563           continue;
 564         }
 565         //
 566         aLPFence.Append(aDNI);
 567         //
 568         // find all other edges in the plane parallel to current one
 569         TopTools_IndexedMapOfShape aMEPln;
 570         aMEPln.Add(aEI1);
 571         aMEPln.Add(aEI2);
 572         //
 573         // iterate on all other edges to find all edges lying in the plane parallel to current one
 574         for (j = 1; j <= aNbEdges; ++j) {
 575           const gp_Dir& aDJ = aDMEdgeTgt(j);
 576           if (aDNI.IsNormal(aDJ, theAngTol)) {
 577             aMEPln.Add(aDMEdgeTgt.FindKey(j));
 578           }
 579         }
 580         //
 581         MakeWires(aMEPln, aRWires, Standard_True, aDMEdgeTgt, aMEdgesNoUniquePlane);
 582       } // for (; aItLEI2.More(); aItLEI2.Next()) {
 583     } // for (; aItLEI1.More(); aItLEI1.Next()) {
 584   } // for (i = 1; i < aNb; ++i) {
 585   //
 586   // 4. Find unused edges and make wires from them
 587   TopTools_IndexedMapOfShape aMEAlone, aMEUsed;
 588   TopExp::MapShapes(aRWires, TopAbs_EDGE, aMEUsed);
 589   //
 590   for (i = 1; i <= aNbEdges; ++i) {
 591     const TopoDS_Shape& aE = aDMEdgeTgt.FindKey(i);
 592     if (!aMEUsed.Contains(aE)) {
 593       aMEAlone.Add(aE);
 594     }
 595   }
 596   //
 597   MakeWires(aMEAlone, aRWires, Standard_False, aDMEdgeTgt, aMEdgesNoUniquePlane);
 598   //
 599   theWires = aRWires;
 600   //
 601   return iErr;
 602 }
 603
 604 //=======================================================================
 605 //function : WiresToFaces
 606 //purpose  :
 607 //=======================================================================
 608 Standard_Boolean BOPAlgo_Tools::WiresToFaces(const TopoDS_Shape& theWires,
 609                                              TopoDS_Shape& theFaces,
 610                                              const Standard_Real theAngTol)
 611 {
 612   BRep_Builder aBB;
 613   TopTools_MapOfShape aMFence;
 614   TopoDS_Compound aRFaces;
 615   aBB.MakeCompound(aRFaces);
 616   //
 617   const Standard_Real aMax = 1.e+8;
 618   //
 619   // map to store the tangent vectors for the edges
 620   BOPAlgo_IndexedDataMapOfShapeDir aDMEdgeTgt;
 621   // maps to store the planes found for the wires
 622   BOPAlgo_IndexedDataMapOfShapePln aDMWirePln;
 623   // map to store the tolerance for the wire
 624   NCollection_DataMap<TopoDS_Shape, Standard_Real, TopTools_ShapeMapHasher> aDMWireTol;
 625   // edges for which the plane is not found
 626   TopTools_MapOfShape aMEdgesNoUniquePlane;
 627   //
 628   // Find planes for the wires
 629   TopExp_Explorer aExpW(theWires, TopAbs_WIRE);
 630   for (; aExpW.More(); aExpW.Next()) {
 631     const TopoDS_Wire& aWire = TopoDS::Wire(aExpW.Current());
 632     gp_Pln aPlane;
 633     if (FindPlane(aWire, aPlane, aDMEdgeTgt, aMEdgesNoUniquePlane)) {
 634       aDMWirePln.Add(aWire, aPlane);
 635       // find tolerance for the wire - max tolerance of its edges
 636       aDMWireTol.Bind(aWire, BRep_Tool::MaxTolerance(aWire, TopAbs_EDGE));
 637     }
 638   }
 639   //
 640   Standard_Integer i, j, aNb = aDMWirePln.Extent();
 641   for (i = 1; i <= aNb; ++i) {
 642     const TopoDS_Shape& aWireI = aDMWirePln.FindKey(i);
 643     if (aMFence.Contains(aWireI)) {
 644       continue;
 645     }
 646     //
 647     const gp_Pln& aPlnI = aDMWirePln(i);
 648     //
 649     TopTools_ListOfShape aLW;
 650     aLW.Append(aWireI);
 651     aMFence.Add(aWireI);
 652     //
 653     Standard_Real aTolI = aDMWireTol.Find(aWireI);
 654     //
 655     // Find other wires in the same plane
 656     for (j = i + 1; j <= aNb; ++j) {
 657       const TopoDS_Shape& aWireJ = aDMWirePln.FindKey(j);
 658       if (aMFence.Contains(aWireJ)) {
 659         continue;
 660       }
 661       //
 662       // check if the planes are the same
 663       const gp_Pln& aPlnJ = aDMWirePln(j);
 664       // check direction of the planes
 665       if (!aPlnI.Position().Direction().IsParallel(aPlnJ.Position().Direction(), theAngTol)) {
 666         continue;
 667       }
 668       // check distance between the planes
 669       Standard_Real aDist = aPlnI.Distance(aPlnJ.Location());
 670       Standard_Real aTolJ = aDMWireTol.Find(aWireJ);
 671       if (aDist > (aTolI + aTolJ)) {
 672         continue;
 673       }
 674       //
 675       aLW.Append(aWireJ);
 676       aMFence.Add(aWireJ);
 677     }
 678     //
 679     // Take the edges to build the face
 680     TopTools_ListOfShape aLE;
 681     TopTools_ListIteratorOfListOfShape aItLW(aLW);
 682     for (; aItLW.More(); aItLW.Next()) {
 683       TopoDS_Iterator aItE(aItLW.Value());
 684       for (; aItE.More(); aItE.Next()) {
 685         aLE.Append(aItE.Value().Oriented(TopAbs_FORWARD));
 686         aLE.Append(aItE.Value().Oriented(TopAbs_REVERSED));
 687       }
 688     }
 689     //
 690     // build planar face
 691     TopoDS_Face aFF = BRepBuilderAPI_MakeFace
 692       (aPlnI, -aMax, aMax, -aMax, aMax).Face();
 693     aFF.Orientation(TopAbs_FORWARD);
 694     //
 695     try {
 696       OCC_CATCH_SIGNALS
 697       //
 698       // build pcurves for edges on this face
 699       BRepLib::BuildPCurveForEdgesOnPlane(aLE, aFF);
 700       //
 701       // split the face with the edges
 702       BOPAlgo_BuilderFace aBF;
 703       aBF.SetShapes(aLE);
 704       aBF.SetFace(aFF);
 705       aBF.Perform();
 706       if (aBF.HasErrors()) {
 707         continue;
 708       }
 709       //
 710       const TopTools_ListOfShape& aLFSp = aBF.Areas();
 711       TopTools_ListIteratorOfListOfShape aItLF(aLFSp);
 712       for (; aItLF.More(); aItLF.Next()) {
 713         const TopoDS_Shape& aFSp = aItLF.ChangeValue();
 714         aBB.Add(aRFaces, aFSp);
 715       }
 716     }
 717     catch (Standard_Failure const&) {
 718       continue;
 719     }
 720   }
 721   //
 722   // fix tolerances of the resulting faces
 723   TopTools_IndexedMapOfShape aMEmpty;
 724   BOPTools_AlgoTools::CorrectTolerances(aRFaces, aMEmpty, 0.05, Standard_False);
 725   BOPTools_AlgoTools::CorrectShapeTolerances(aRFaces, aMEmpty, Standard_False);
 726   //
 727   theFaces = aRFaces;
 728   return theFaces.NbChildren() > 0;
 729 }
 730
 731 //=======================================================================
 732 //function : MakeWires
 733 //purpose  : Makes wires from the separate blocks of the given edges
 734 //=======================================================================
 735 void MakeWires(const TopTools_IndexedMapOfShape& theEdges,
 736                TopoDS_Compound& theWires,
 737                const Standard_Boolean theCheckUniquePlane,
 738                BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
 739                TopTools_MapOfShape& theMEdgesNoUniquePlane)
 740 {
 741   TopoDS_Compound aCE;
 742   BRep_Builder().MakeCompound(aCE);
 743   Standard_Integer i, aNbE = theEdges.Extent();
 744   for (i = 1; i <= aNbE; ++i) {
 745     BRep_Builder().Add(aCE, theEdges(i));
 746   }
 747   //
 748   TopTools_ListOfShape aLCBE;
 749   BOPTools_AlgoTools::MakeConnexityBlocks(aCE, TopAbs_VERTEX, TopAbs_EDGE, aLCBE);
 750   //
 751   // make wire from each block
 752   TopTools_ListIteratorOfListOfShape aItLCB(aLCBE);
 753   for (; aItLCB.More(); aItLCB.Next()) {
 754     const TopoDS_Shape& aCBE = aItLCB.Value();
 755     //
 756     if (theCheckUniquePlane) {
 757       gp_Pln aPln;
 758       if (!FindPlane(aCBE, aPln, theDMEdgeTgt, theMEdgesNoUniquePlane)) {
 759         continue;
 760       }
 761     }
 762     //
 763     TopoDS_Wire aWire;
 764     BRep_Builder().MakeWire(aWire);
 765     for (TopoDS_Iterator aItE(aCBE); aItE.More(); aItE.Next()) {
 766       BRep_Builder().Add(aWire, aItE.Value());
 767     }
 768     //
 769     BRep_Builder().Add(theWires, aWire);
 770   }
 771 }
 772
 773 //=======================================================================
 774 //function : FindEdgeTangent
 775 //purpose  : Finds the tangent for the edge using the map
 776 //=======================================================================
 777 Standard_Boolean FindEdgeTangent(const TopoDS_Edge& theEdge,
 778                                  BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
 779                                  gp_Dir& theTgt)
 780 {
 781   gp_Dir *pDTE = theDMEdgeTgt.ChangeSeek(theEdge);
 782   if (!pDTE) {
 783     gp_Vec aVTE;
 784     BRepAdaptor_Curve aBAC(theEdge);
 785     if (!FindEdgeTangent(aBAC, aVTE)) {
 786       return Standard_False;
 787     }
 788     pDTE = &theDMEdgeTgt(theDMEdgeTgt.Add(theEdge, gp_Dir(aVTE)));
 789   }
 790   theTgt = *pDTE;
 791   return Standard_True;
 792 }
 793
 794 //=======================================================================
 795 //function : FindEdgeTangent
 796 //purpose  : Finds the tangent for the edge
 797 //=======================================================================
 798 Standard_Boolean FindEdgeTangent(const BRepAdaptor_Curve& theCurve,
 799                                  gp_Vec& theTangent)
 800 {
 801   if (!theCurve.Is3DCurve()) {
 802     return Standard_False;
 803   }
 804   // for the line the tangent is defined by the direction
 805   if (theCurve.GetType() == GeomAbs_Line) {
 806     theTangent = theCurve.Line().Position().Direction();
 807     return Standard_True;
 808   }
 809   //
 810   // for other curves take D1 and check for its length
 811   Standard_Real aT, aT1(theCurve.FirstParameter()), aT2(theCurve.LastParameter());
 812   const Standard_Integer aNbP = 11;
 813   const Standard_Real aDt = (aT2 - aT1) / aNbP;
 814   //
 815   for (aT = aT1 + aDt; aT <= aT2; aT += aDt) {
 816     gp_Pnt aP;
 817     theCurve.D1(aT, aP, theTangent);
 818     if (theTangent.Magnitude() > Precision::Confusion()) {
 819       return Standard_True;
 820     }
 821   }
 822   //
 823   return Standard_False;
 824 }
 825
 826 //=======================================================================
 827 //function : FindPlane
 828 //purpose  : Finds the plane in which the edge is located
 829 //=======================================================================
 830 Standard_Boolean FindPlane(const BRepAdaptor_Curve& theCurve,
 831                            gp_Pln& thePlane)
 832 {
 833   if (!theCurve.Is3DCurve()) {
 834     return Standard_False;
 835   }
 836   //
 837   Standard_Boolean bFound = Standard_True;
 838   gp_Vec aVN;
 839   switch (theCurve.GetType()) {
 840     case GeomAbs_Line:
 841       return Standard_False;
 842     case GeomAbs_Circle:
 843       aVN = theCurve.Circle().Position().Direction();
 844       break;
 845     case GeomAbs_Ellipse:
 846       aVN = theCurve.Ellipse().Position().Direction();
 847       break;
 848     case GeomAbs_Hyperbola:
 849       aVN = theCurve.Hyperbola().Position().Direction();
 850       break;
 851     case GeomAbs_Parabola:
 852       aVN = theCurve.Parabola().Position().Direction();
 853       break;
 854     default: {
 855       // for all other types of curve compute two tangent vectors
 856       // on the curve and cross them
 857       bFound = Standard_False;
 858       Standard_Real aT, aT1(theCurve.FirstParameter()), aT2(theCurve.LastParameter());
 859       const Standard_Integer aNbP = 11;
 860       const Standard_Real aDt = (aT2 - aT1) / aNbP;
 861       //
 862       aT = aT1;
 863       gp_Pnt aP1;
 864       gp_Vec aV1;
 865       theCurve.D1(aT, aP1, aV1);
 866       //
 867       for (aT = aT1 + aDt; aT <= aT2; aT += aDt) {
 868         gp_Pnt aP2;
 869         gp_Vec aV2;
 870         theCurve.D1(aT, aP2, aV2);
 871         //
 872         aVN = aV1^aV2;
 873         if (aVN.Magnitude() > Precision::Confusion()) {
 874           bFound = Standard_True;
 875           break;
 876         }
 877       }
 878       break;
 879     }
 880   }
 881   //
 882   if (bFound) {
 883     thePlane = gp_Pln(theCurve.Value(theCurve.FirstParameter()), gp_Dir(aVN));
 884   }
 885   return bFound;
 886 }
 887
 888 //=======================================================================
 889 //function : FindPlane
 890 //purpose  : Finds the plane in which the wire is located
 891 //=======================================================================
 892 Standard_Boolean FindPlane(const TopoDS_Shape& theWire,
 893                            gp_Pln& thePlane,
 894                            BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
 895                            TopTools_MapOfShape& theMEdgesNoUniquePlane)
 896 {
 897   TopExp_Explorer aExpE1(theWire, TopAbs_EDGE);
 898   if (!aExpE1.More()) {
 899     return Standard_False;
 900   }
 901   //
 902   // try to find two not parallel edges in wire to get normal of the plane
 903   for (; aExpE1.More(); aExpE1.Next()) {
 904     // get the first edge in the wire
 905     const TopoDS_Edge& aE1 = TopoDS::Edge(aExpE1.Current());
 906     //
 907     // find tangent for the first edge
 908     gp_Dir aDTE1;
 909     if (!FindEdgeTangent(aE1, theDMEdgeTgt, aDTE1)) {
 910       continue;
 911     }
 912     //
 913     // find the other edge not parallel to the first one
 914     TopExp_Explorer aExpE2(theWire, TopAbs_EDGE);
 915     for (; aExpE2.More(); aExpE2.Next()) {
 916       const TopoDS_Edge& aE2 = TopoDS::Edge(aExpE2.Current());
 917       if (aE1.IsSame(aE2)) {
 918         continue;
 919       }
 920       //
 921       // find tangent for the second edge
 922       gp_Dir aDTE2;
 923       if (!FindEdgeTangent(aE2, theDMEdgeTgt, aDTE2)) {
 924         continue;
 925       }
 926       //
 927       if (aDTE1.IsParallel(aDTE2, Precision::Angular())) {
 928         continue;
 929       }
 930       //
 931       gp_Dir aDN = aDTE1^aDTE2;
 932       //
 933       TopoDS_Iterator aItV(aE1);
 934       thePlane = gp_Pln(BRep_Tool::Pnt(TopoDS::Vertex(aItV.Value())), aDN);
 935       return Standard_True;
 936     }
 937   }
 938   //
 939   // try to compute normal on the single edge
 940   aExpE1.Init(theWire, TopAbs_EDGE);
 941   for (; aExpE1.More(); aExpE1.Next()) {
 942     const TopoDS_Edge& aE = TopoDS::Edge(aExpE1.Current());
 943     if (theMEdgesNoUniquePlane.Contains(aE)) {
 944       continue;
 945     }
 946     BRepAdaptor_Curve aBAC(aE);
 947     if (FindPlane(aBAC, thePlane)) {
 948       return Standard_True;
 949     }
 950     theMEdgesNoUniquePlane.Add(aE);
 951   }
 952   return Standard_False;
 953 }
 954
 955 /////////////////////////////////////////////////////////////////////////
 956 //=======================================================================
 957 //class    : BOPAlgo_PairVerticesSelector
 958 //purpose  :
 959 //=======================================================================
 960 class BOPAlgo_PairVerticesSelector : public BOPTools_BoxPairSelector
 961 {
 962 public:
 963
 964   BOPAlgo_PairVerticesSelector()
 965     : myVertices(NULL),
 966       myFuzzyValue(Precision::Confusion())
 967   {}
 968
 969   //! Sets the map of vertices with tolerances
 970   void SetMapOfVerticesTolerances (const TopTools_IndexedDataMapOfShapeReal& theVertices)
 971   {
 972     myVertices = &theVertices;
 973   }
 974
 975   //! Sets the fuzzy value
 976   void SetFuzzyValue (const Standard_Real theFuzzyValue)
 977   {
 978     myFuzzyValue = theFuzzyValue;
 979   }
 980
 981   //! Checks and accepts the pair of elements.
 982   virtual Standard_Boolean Accept (const Standard_Integer theID1,
 983                                    const Standard_Integer theID2) Standard_OVERRIDE
 984   {
 985     if (!RejectElement (theID1, theID2))
 986     {
 987       const Standard_Integer anID1 = this->myBVHSet1->Element (theID1);
 988       const TopoDS_Vertex& aV1 = TopoDS::Vertex (myVertices->FindKey (anID1));
 989       Standard_Real aTolV1 = BRep_Tool::Tolerance (aV1);
 990       if (aTolV1 < myVertices->FindFromIndex (anID1))
 991         aTolV1 = myVertices->FindFromIndex (anID1);
 992       gp_Pnt aP1 = BRep_Tool::Pnt (aV1);
 993
 994       const Standard_Integer anID2 = this->myBVHSet1->Element (theID2);
 995       const TopoDS_Vertex& aV2 = TopoDS::Vertex (myVertices->FindKey (anID2));
 996       Standard_Real aTolV2 = BRep_Tool::Tolerance (aV2);
 997       if (aTolV2 < myVertices->FindFromIndex (anID2))
 998         aTolV2 = myVertices->FindFromIndex (anID2);
 999       gp_Pnt aP2 = BRep_Tool::Pnt (aV2);
1000
1001       Standard_Real aTolSum2 = aTolV1 + aTolV2 + myFuzzyValue;
1002       aTolSum2 *= aTolSum2;
1003
1004       Standard_Real aD2 = aP1.SquareDistance (aP2);
1005       if (aD2 < aTolSum2)
1006       {
1007         myPairs.push_back (PairIDs (anID1, anID2));
1008         return Standard_True;
1009       }
1010     }
1011     return Standard_False;
1012   }
1013
1014 protected:
1015   const TopTools_IndexedDataMapOfShapeReal * myVertices;
1016   Standard_Real myFuzzyValue;
1017 };
1018 //
1019 /////////////////////////////////////////////////////////////////////////
1020
1021 //=======================================================================
1022 //function : IntersectVertices
1023 //purpose  : Builds the chains of intersecting vertices
1024 //=======================================================================
1025 void BOPAlgo_Tools::IntersectVertices(const TopTools_IndexedDataMapOfShapeReal& theVertices,
1026                                       const Standard_Real theFuzzyValue,
1027                                       TopTools_ListOfListOfShape& theChains)
1028 {
1029   Standard_Integer aNbV = theVertices.Extent();
1030   if (aNbV <= 1) {
1031     if (aNbV == 1) {
1032       theChains.Append(TopTools_ListOfShape()).Append(theVertices.FindKey(1));
1033     }
1034     return;
1035   }
1036
1037   // Additional tolerance for intersection
1038   Standard_Real aTolAdd = theFuzzyValue / 2.;
1039
1040   // Use BVH Tree for sorting the vertices
1041   BOPTools_BoxTree aBBTree;
1042   aBBTree.SetSize (aNbV);
1043
1044   for (Standard_Integer i = 1; i <= aNbV; ++i)
1045   {
1046     const TopoDS_Vertex& aV = TopoDS::Vertex(theVertices.FindKey(i));
1047     Standard_Real aTol = BRep_Tool::Tolerance(aV);
1048     if (aTol < theVertices(i))
1049       aTol = theVertices(i);
1050
1051     // Build bnd box for vertex
1052     Bnd_Box aBox;
1053     aBox.Add(BRep_Tool::Pnt(aV));
1054     aBox.SetGap(aTol + aTolAdd);
1055     aBBTree.Add(i, Bnd_Tools::Bnd2BVH(aBox));
1056   }
1057
1058   aBBTree.Build();
1059
1060   // Perform selection of the interfering vertices
1061   BOPAlgo_PairVerticesSelector aPairSelector;
1062   aPairSelector.SetBVHSets (&aBBTree, &aBBTree);
1063   aPairSelector.SetSame (Standard_True);
1064   aPairSelector.SetMapOfVerticesTolerances (theVertices);
1065   aPairSelector.SetFuzzyValue (theFuzzyValue);
1066   aPairSelector.Select();
1067
1068   // Treat the selected pairs
1069   const std::vector<BOPTools_BoxPairSelector::PairIDs>& aPairs = aPairSelector.Pairs();
1070   const Standard_Integer aNbPairs = static_cast<Standard_Integer> (aPairs.size());
1071
1072   // Collect interfering pairs
1073   Handle(NCollection_IncAllocator) anAlloc = new NCollection_IncAllocator;
1074   NCollection_IndexedDataMap<Standard_Integer, TColStd_ListOfInteger> aMILI (1, anAlloc);
1075
1076   for (Standard_Integer iPair = 0; iPair < aNbPairs; ++iPair)
1077   {
1078     const BOPTools_BoxPairSelector::PairIDs& aPair = aPairs[iPair];
1079     BOPAlgo_Tools::FillMap<Standard_Integer, TColStd_MapIntegerHasher> (aPair.ID1, aPair.ID2, aMILI, anAlloc);
1080   }
1081
1082   NCollection_List<TColStd_ListOfInteger> aBlocks (anAlloc);
1083   BOPAlgo_Tools::MakeBlocks<Standard_Integer, TColStd_MapIntegerHasher> (aMILI, aBlocks, anAlloc);
1084
1085   NCollection_List<TColStd_ListOfInteger>::Iterator itLI (aBlocks);
1086   for (; itLI.More(); itLI.Next())
1087   {
1088     const TColStd_ListOfInteger& aLI = itLI.Value();
1089     TopTools_ListOfShape &aChain = theChains.Append (TopTools_ListOfShape());
1090
1091     for (TColStd_ListOfInteger::Iterator itI (aLI); itI.More(); itI.Next())
1092       aChain.Append (theVertices.FindKey (itI.Value()));
1093   }
1094
1095   // Add not interfered vertices as a chain of 1 element
1096   for (Standard_Integer i = 1; i <= aNbV; ++i)
1097   {
1098     if (!aMILI.Contains (i))
1099     {
1100       TopTools_ListOfShape &aChain = theChains.Append (TopTools_ListOfShape());
1101       aChain.Append (theVertices.FindKey(i));
1102     }
1103   }
1104 }
1105
1106 //=======================================================================
1107 // Classification of the faces relatively solids
1108 //=======================================================================
1109
1110 //=======================================================================
1111 //class     : BOPAlgo_ShapeBox
1112 //purpose   : Auxiliary class defining ShapeBox structure
1113 //=======================================================================
1114 class BOPAlgo_ShapeBox
1115 {
1116 public:
1117   //! Empty constructor
1118   BOPAlgo_ShapeBox() {};
1119   //! Sets the shape
1120   void SetShape(const TopoDS_Shape& theS)
1121   {
1122     myShape = theS;
1123   };
1124   //! Returns the shape
1125   const TopoDS_Shape& Shape() const
1126   {
1127     return myShape;
1128   };
1129   //! Sets the bounding box
1130   void SetBox(const Bnd_Box& theBox)
1131   {
1132     myBox = theBox;
1133   };
1134   //! Returns the bounding box
1135   const Bnd_Box& Box() const
1136   {
1137     return myBox;
1138   };
1139 private:
1140   TopoDS_Shape myShape;
1141   Bnd_Box myBox;
1142 };
1143 // Vector of ShapeBox
1144 typedef NCollection_Vector<BOPAlgo_ShapeBox> BOPAlgo_VectorOfShapeBox;
1145
1146 //=======================================================================
1147 //class : BOPAlgo_FillIn3DParts
1148 //purpose : Auxiliary class for faces classification in parallel mode
1149 //=======================================================================
1150 class BOPAlgo_FillIn3DParts : public BOPAlgo_Algo
1151 {
1152 public:
1153   DEFINE_STANDARD_ALLOC
1154
1155   //! Constructor
1156   BOPAlgo_FillIn3DParts()
1157   {
1158     myBBTree = NULL;
1159     myVShapeBox = NULL;
1160   };
1161
1162   //! Destructor
1163   virtual ~BOPAlgo_FillIn3DParts() {};
1164
1165   //! Sets the solid
1166   void SetSolid(const TopoDS_Solid& theSolid)
1167   {
1168     mySolid = theSolid;
1169   };
1170
1171   //! Returns the solid
1172   const TopoDS_Solid& Solid() const
1173   {
1174     return mySolid;
1175   };
1176
1177   //! Sets the box for the solid
1178   void SetBoxS(const Bnd_Box& theBox)
1179   {
1180     myBoxS = theBox;
1181   };
1182
1183   //! Returns the solid's box
1184   const Bnd_Box& BoxS() const
1185   {
1186     return myBoxS;
1187   };
1188
1189   //! Sets own INTERNAL faces of the solid
1190   void SetOwnIF(const TopTools_ListOfShape& theLIF)
1191   {
1192     myOwnIF = theLIF;
1193   };
1194
1195   //! Returns own INTERNAL faces of the solid
1196   const TopTools_ListOfShape& OwnIF() const
1197   {
1198     return myOwnIF;
1199   };
1200
1201   //! Sets the Bounding Box tree
1202   void SetBBTree(BOPTools_BoxTree* theBBTree)
1203   {
1204     myBBTree = theBBTree;
1205   };
1206
1207   //! Sets the ShapeBox structure
1208   void SetShapeBoxVector(const BOPAlgo_VectorOfShapeBox& theShapeBox)
1209   {
1210     myVShapeBox = (BOPAlgo_VectorOfShapeBox*)&theShapeBox;
1211   };
1212
1213   //! Sets the context
1214   void SetContext(const Handle(IntTools_Context)& theContext)
1215   {
1216     myContext = theContext;
1217   }
1218
1219   //! Returns the context
1220   const Handle(IntTools_Context)& Context() const
1221   {
1222     return myContext;
1223   }
1224
1225   //! Performs the classification
1226   virtual void Perform();
1227
1228   //! Returns the faces classified as IN for solid
1229   const TopTools_ListOfShape& InFaces() const
1230   {
1231     return myInFaces;
1232   };
1233
1234 private:
1235
1236   //! Prepares Edge-Face connection map of the given shape
1237   void MapEdgesAndFaces(const TopoDS_Shape& theF,
1238                         TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1239                         const Handle(NCollection_BaseAllocator)& theAlloc);
1240
1241   //! Makes the connexity block of faces using the connection map
1242   void MakeConnexityBlock(const TopoDS_Face& theF,
1243                           const TopTools_IndexedMapOfShape& theMEToAvoid,
1244                           const TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1245                           TopTools_MapOfShape& theMFDone,
1246                           TopTools_ListOfShape& theLCB,
1247                           TopoDS_Face& theFaceToClassify);
1248
1249   TopoDS_Solid mySolid; //! Solid
1250   Bnd_Box myBoxS; // Bounding box of the solid
1251   TopTools_ListOfShape myOwnIF; //! Own INTERNAL faces of the solid
1252   TopTools_ListOfShape myInFaces; //! Faces classified as IN
1253
1254   BOPTools_BoxTree* myBBTree; //! BVH tree of bounding boxes
1255   BOPAlgo_VectorOfShapeBox* myVShapeBox; //! ShapeBoxMap
1256
1257   TopoDS_Iterator myItF; //! Iterators
1258   TopoDS_Iterator myItW;
1259
1260   Handle(IntTools_Context) myContext; //! Context
1261 };
1262
1263 //=======================================================================
1264 //function : BOPAlgo_FillIn3DParts::Perform
1265 //purpose  :
1266 //=======================================================================
1267 void BOPAlgo_FillIn3DParts::Perform()
1268 {
1269   BOPAlgo_Algo::UserBreak();
1270
1271   myInFaces.Clear();
1272
1273   // 1. Select boxes of faces that are not out of aBoxS
1274   BOPTools_BoxTreeSelector aSelector;
1275   aSelector.SetBox(Bnd_Tools::Bnd2BVH(myBoxS));
1276   aSelector.SetBVHSet (myBBTree);
1277   //
1278   if (!aSelector.Select())
1279     return;
1280
1281   const TColStd_ListOfInteger& aLIFP = aSelector.Indices();
1282
1283   // 2. Fill maps of edges and faces of the solid
1284
1285   Handle(NCollection_BaseAllocator) anAlloc = new NCollection_IncAllocator;
1286
1287   BOPAlgo_VectorOfShapeBox& aVShapeBox = *myVShapeBox;
1288
1289   TopTools_IndexedMapOfShape aMSE(1, anAlloc), aMSF(1, anAlloc);
1290   TopExp::MapShapes(mySolid, TopAbs_EDGE, aMSE);
1291   TopExp::MapShapes(mySolid, TopAbs_FACE, aMSF);
1292
1293   // Check if the Solid contains any faces
1294   Standard_Boolean bIsEmpty = aMSF.IsEmpty();
1295
1296   // Add own internal faces of the solid into aMSF
1297   TopTools_ListIteratorOfListOfShape aItLS(myOwnIF);
1298   for (; aItLS.More(); aItLS.Next())
1299     aMSF.Add(aItLS.Value());
1300
1301   // 3. aIVec - faces to process.
1302   //    Filter the selected faces with faces of the solid.
1303   NCollection_Vector<Standard_Integer> aIVec(256, anAlloc);
1304
1305   TColStd_ListIteratorOfListOfInteger aItLI(aLIFP);
1306   for (; aItLI.More(); aItLI.Next()) {
1307     Standard_Integer nFP = aItLI.Value();
1308     const TopoDS_Shape& aFP = aVShapeBox(nFP).Shape();
1309     if (!aMSF.Contains(aFP))
1310       aIVec.Appended() = nFP;
1311   }
1312
1313   // 4. Classify faces relatively solid.
1314   //    Store faces that are IN mySolid into <myInFaces>
1315
1316   Standard_Integer k, aNbFP = aIVec.Length();
1317   // Sort indices if necessary
1318   if (aNbFP > 1)
1319     std::sort(aIVec.begin(), aIVec.end());
1320
1321   if (bIsEmpty)
1322   {
1323     // The solid is empty as it does not contain any faces.
1324     // It could happen when the input solid consists of INTERNAL faces only.
1325     // Classification of any point relatively empty solid would always give IN status.
1326     // Thus, we consider all selected faces as IN without real classification.
1327     for (k = 0; k < aNbFP; ++k)
1328       myInFaces.Append(aVShapeBox(aIVec(k)).Shape());
1329
1330     return;
1331   }
1332
1333   // Prepare EF map of faces to process for building connexity blocks
1334   TopTools_IndexedDataMapOfShapeListOfShape aMEFP(1, anAlloc);
1335   if (aNbFP > 1)
1336   {
1337     for (k = 0; k < aNbFP; ++k)
1338       MapEdgesAndFaces(aVShapeBox(aIVec(k)).Shape(), aMEFP, anAlloc);
1339   }
1340
1341   // Map of Edge-Face connection, necessary for solid classification.
1342   // It will be filled when first classification is performed.
1343   TopTools_IndexedDataMapOfShapeListOfShape aMEFDS(1, anAlloc);
1344
1345   // Fence map to avoid processing of the same faces twice
1346   TopTools_MapOfShape aMFDone(1, anAlloc);
1347
1348   for (k = 0; k < aNbFP; ++k)
1349   {
1350     Standard_Integer nFP = aIVec(k);
1351     const TopoDS_Face& aFP = (*(TopoDS_Face*)&aVShapeBox(nFP).Shape());
1352     if (!aMFDone.Add(aFP))
1353       continue;
1354
1355     // Make connexity blocks of faces, avoiding passing through the
1356     // borders of the solid. It helps to reduce significantly the
1357     // number of classified faces.
1358     TopTools_ListOfShape aLCBF(anAlloc);
1359     // The most appropriate face for classification
1360     TopoDS_Face aFaceToClassify;
1361     MakeConnexityBlock(aFP, aMSE, aMEFP, aMFDone, aLCBF, aFaceToClassify);
1362
1363     if (!myBoxS.IsWhole())
1364     {
1365       // First, try fast classification of the whole block by additional
1366       // check on bounding boxes - check that bounding boxes of all vertices
1367       // of the block interfere with the box of the solid.
1368       // If not, the faces are out.
1369       Standard_Boolean bOut = Standard_False;
1370       aItLS.Initialize(aLCBF);
1371       for (; aItLS.More() && !bOut; aItLS.Next())
1372       {
1373         TopExp_Explorer anExpV(aItLS.Value(), TopAbs_VERTEX);
1374         for (; anExpV.More() && !bOut; anExpV.Next())
1375         {
1376           const TopoDS_Vertex& aV = TopoDS::Vertex(anExpV.Current());
1377           Bnd_Box aBBV;
1378           aBBV.Add(BRep_Tool::Pnt(aV));
1379           aBBV.SetGap(BRep_Tool::Tolerance(aV));
1380           bOut = myBoxS.IsOut(aBBV);
1381         }
1382       }
1383       if (bOut)
1384         continue;
1385     }
1386
1387     if (aFaceToClassify.IsNull())
1388       aFaceToClassify = aFP;
1389
1390     if (aMEFDS.IsEmpty())
1391       // Fill EF map for Solid
1392       TopExp::MapShapesAndAncestors(mySolid, TopAbs_EDGE, TopAbs_FACE, aMEFDS);
1393
1394     // All vertices are interfere with the solids box, run classification.
1395     Standard_Boolean bIsIN = BOPTools_AlgoTools::IsInternalFace
1396       (aFaceToClassify, mySolid, aMEFDS, Precision::Confusion(), myContext);
1397     if (bIsIN)
1398     {
1399       aItLS.Initialize(aLCBF);
1400       for (; aItLS.More(); aItLS.Next())
1401         myInFaces.Append(aItLS.Value());
1402     }
1403   }
1404 }
1405 //=======================================================================
1406 // function: MapEdgesAndFaces
1407 // purpose:
1408 //=======================================================================
1409 void BOPAlgo_FillIn3DParts::MapEdgesAndFaces(const TopoDS_Shape& theF,
1410                                              TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1411                                              const Handle(NCollection_BaseAllocator)& theAllocator)
1412 {
1413   myItF.Initialize(theF);
1414   for (; myItF.More(); myItF.Next())
1415   {
1416     const TopoDS_Shape& aW = myItF.Value();
1417     if (aW.ShapeType() != TopAbs_WIRE)
1418       continue;
1419
1420     myItW.Initialize(aW);
1421     for (; myItW.More(); myItW.Next())
1422     {
1423       const TopoDS_Shape& aE = myItW.Value();
1424
1425       TopTools_ListOfShape* pLF = theEFMap.ChangeSeek(aE);
1426       if (!pLF)
1427         pLF = &theEFMap(theEFMap.Add(aE, TopTools_ListOfShape(theAllocator)));
1428       pLF->Append(theF);
1429     }
1430   }
1431 }
1432 //=======================================================================
1433 // function: MakeConnexityBlock
1434 // purpose:
1435 //=======================================================================
1436 void BOPAlgo_FillIn3DParts::MakeConnexityBlock(const TopoDS_Face& theFStart,
1437                                                const TopTools_IndexedMapOfShape& theMEAvoid,
1438                                                const TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1439                                                TopTools_MapOfShape& theMFDone,
1440                                                TopTools_ListOfShape& theLCB,
1441                                                TopoDS_Face& theFaceToClassify)
1442 {
1443   // Add start element
1444   theLCB.Append(theFStart);
1445   if (theEFMap.IsEmpty())
1446     return;
1447
1448   TopTools_ListIteratorOfListOfShape aItCB(theLCB);
1449   for (; aItCB.More(); aItCB.Next())
1450   {
1451     const TopoDS_Shape& aF = aItCB.Value();
1452     myItF.Initialize(aF);
1453     for (; myItF.More(); myItF.Next())
1454     {
1455       const TopoDS_Shape& aW = myItF.Value();
1456       if (aW.ShapeType() != TopAbs_WIRE)
1457         continue;
1458
1459       myItW.Initialize(aW);
1460       for (; myItW.More(); myItW.Next())
1461       {
1462         const TopoDS_Edge& aE = TopoDS::Edge(myItW.Value());
1463         if (theMEAvoid.Contains(aE) || BRep_Tool::Degenerated(aE))
1464         {
1465           if (theFaceToClassify.IsNull())
1466             theFaceToClassify = TopoDS::Face(aF);
1467           continue;
1468         }
1469
1470         const TopTools_ListOfShape* pLF = theEFMap.Seek(aE);
1471         if (!pLF)
1472           continue;
1473         TopTools_ListIteratorOfListOfShape aItLF(*pLF);
1474         for (; aItLF.More(); aItLF.Next())
1475         {
1476           const TopoDS_Shape& aFToAdd = aItLF.Value();
1477           if (theMFDone.Add(aFToAdd))
1478             theLCB.Append(aFToAdd);
1479         }
1480       }
1481     }
1482   }
1483 }
1484
1485 // Vector of solid classifiers
1486 typedef NCollection_Vector<BOPAlgo_FillIn3DParts> BOPAlgo_VectorOfFillIn3DParts;
1487
1488 //=======================================================================
1489 //function : ClassifyFaces
1490 //purpose  :
1491 //=======================================================================
1492 void BOPAlgo_Tools::ClassifyFaces(const TopTools_ListOfShape& theFaces,
1493                                   const TopTools_ListOfShape& theSolids,
1494                                   const Standard_Boolean theRunParallel,
1495                                   Handle(IntTools_Context)& theContext,
1496                                   TopTools_IndexedDataMapOfShapeListOfShape& theInParts,
1497                                   const TopTools_DataMapOfShapeBox& theShapeBoxMap,
1498                                   const TopTools_DataMapOfShapeListOfShape& theSolidsIF)
1499 {
1500   Handle(NCollection_BaseAllocator) anAlloc = new NCollection_IncAllocator;
1501
1502   // Fill the vector of shape box with faces and its bounding boxes
1503   BOPAlgo_VectorOfShapeBox aVSB(256, anAlloc);
1504
1505   TopTools_ListIteratorOfListOfShape aItLF(theFaces);
1506   for (; aItLF.More(); aItLF.Next())
1507   {
1508     const TopoDS_Shape& aF = aItLF.Value();
1509     // Append face to the vector of shape box
1510     BOPAlgo_ShapeBox& aSB = aVSB.Appended();
1511     aSB.SetShape(aF);
1512
1513     // Get bounding box for the face
1514     const Bnd_Box* pBox = theShapeBoxMap.Seek(aF);
1515     if (pBox)
1516       aSB.SetBox(*pBox);
1517     else
1518     {
1519       // Build the bounding box
1520       Bnd_Box aBox;
1521       BRepBndLib::Add(aF, aBox);
1522       aSB.SetBox(aBox);
1523     }
1524   }
1525
1526   // Prepare BVH tree of bounding boxes of the faces to classify
1527   // taking the bounding boxes from the just prepared vector
1528   BOPTools_BoxTree aBBTree;
1529   Standard_Integer aNbF = aVSB.Length();
1530   aBBTree.SetSize (aNbF);
1531   for (Standard_Integer i = 0; i < aNbF; ++i)
1532   {
1533     aBBTree.Add(i, Bnd_Tools::Bnd2BVH(aVSB(i).Box()));
1534   }
1535
1536   // Shake tree filler
1537   aBBTree.Build();
1538
1539   // Prepare vector of solids to classify
1540   BOPAlgo_VectorOfFillIn3DParts aVFIP;
1541
1542   TopTools_ListIteratorOfListOfShape aItLS(theSolids);
1543   for (; aItLS.More(); aItLS.Next())
1544   {
1545     const TopoDS_Solid& aSolid = TopoDS::Solid(aItLS.Value());
1546     // Append solid to the vector
1547     BOPAlgo_FillIn3DParts& aFIP = aVFIP.Appended();
1548     aFIP.SetSolid(aSolid);
1549
1550     // Get bounding box for the solid
1551     const Bnd_Box* pBox = theShapeBoxMap.Seek(aSolid);
1552     if (pBox)
1553       aFIP.SetBoxS(*pBox);
1554     else
1555     {
1556       // Build the bounding box
1557       Bnd_Box aBox;
1558       BRepBndLib::Add(aSolid, aBox);
1559       if (!aBox.IsWhole())
1560       {
1561         if (BOPTools_AlgoTools::IsInvertedSolid(aSolid))
1562           aBox.SetWhole();
1563       }
1564       aFIP.SetBoxS(aBox);
1565     }
1566
1567     const TopTools_ListOfShape* pLIF = theSolidsIF.Seek(aSolid);
1568     if (pLIF)
1569       aFIP.SetOwnIF(*pLIF);
1570
1571     aFIP.SetBBTree(&aBBTree);
1572     aFIP.SetShapeBoxVector(aVSB);
1573   }
1574
1575   // Perform classification
1576   //================================================================
1577   BOPTools_Parallel::Perform (theRunParallel, aVFIP, theContext);
1578   //================================================================
1579
1580   // Analyze the results and fill the resulting map
1581
1582   Standard_Integer aNbS = aVFIP.Length();
1583   for (Standard_Integer i = 0; i < aNbS; ++i)
1584   {
1585     BOPAlgo_FillIn3DParts& aFIP = aVFIP(i);
1586     const TopoDS_Shape& aS = aFIP.Solid();
1587     const TopTools_ListOfShape& aLFIn = aFIP.InFaces();
1588     theInParts.Add(aS, aLFIn);
1589   }
1590 }
1591
1592 //=======================================================================
1593 //function : FillInternals
1594 //purpose  :
1595 //=======================================================================
1596 void BOPAlgo_Tools::FillInternals(const TopTools_ListOfShape& theSolids,
1597                                   const TopTools_ListOfShape& theParts,
1598                                   const TopTools_DataMapOfShapeListOfShape& theImages,
1599                                   const Handle(IntTools_Context)& theContext)
1600 {
1601   if (theSolids.IsEmpty() || theParts.IsEmpty())
1602     return;
1603
1604   // Map the solids to avoid classification of the own shapes of the solids
1605   TopTools_IndexedMapOfShape aMSSolids;
1606   TopTools_ListOfShape::Iterator itLS(theSolids);
1607   for (; itLS.More(); itLS.Next())
1608   {
1609     const TopoDS_Shape& aSolid = itLS.Value();
1610     if (aSolid.ShapeType() == TopAbs_SOLID)
1611     {
1612       TopExp::MapShapes(aSolid, TopAbs_VERTEX, aMSSolids);
1613       TopExp::MapShapes(aSolid, TopAbs_EDGE,   aMSSolids);
1614       TopExp::MapShapes(aSolid, TopAbs_FACE,   aMSSolids);
1615     }
1616   }
1617
1618   // Extract BRep elements from the given parts and
1619   // check them for possible splits
1620   TopTools_ListOfShape aLPartsInput = theParts, aLParts;
1621   TopTools_ListOfShape::Iterator itLP(aLPartsInput);
1622   for (; itLP.More(); itLP.Next())
1623   {
1624     const TopoDS_Shape& aPart = itLP.Value();
1625     switch (aPart.ShapeType())
1626     {
1627       case TopAbs_VERTEX:
1628       case TopAbs_EDGE:
1629       case TopAbs_FACE:
1630       {
1631         const TopTools_ListOfShape* pIm = theImages.Seek(aPart);
1632         if (pIm)
1633         {
1634           TopTools_ListOfShape::Iterator itIm(*pIm);
1635           for (; itIm.More(); itIm.Next())
1636           {
1637             const TopoDS_Shape& aPartIm = itIm.Value();
1638             if (!aMSSolids.Contains(aPartIm))
1639               aLParts.Append(aPartIm);
1640           }
1641         }
1642         else if (!aMSSolids.Contains(aPart))
1643           aLParts.Append(aPart);
1644
1645         break;
1646       }
1647       default:
1648       {
1649         for (TopoDS_Iterator it(aPart); it.More(); it.Next())
1650           aLPartsInput.Append(it.Value());
1651         break;
1652       }
1653     }
1654   }
1655
1656   // Classify the given parts relatively solids.
1657   // Add edges and vertices classified as IN into solids instantly,
1658   // and collect faces classified as IN into a list for further shell creation
1659
1660   TopTools_DataMapOfShapeListOfShape anINFaces;
1661   itLS.Initialize(theSolids);
1662   for (; itLS.More(); itLS.Next())
1663   {
1664     const TopoDS_Shape& aSolid = itLS.Value();
1665     if (aSolid.ShapeType() != TopAbs_SOLID)
1666       continue;
1667
1668     TopoDS_Solid aSd = *(TopoDS_Solid*)&aSolid;
1669
1670     itLP.Initialize(aLParts);
1671     for (; itLP.More();)
1672     {
1673       TopoDS_Shape aPart = itLP.Value();
1674       TopAbs_State aState =
1675         BOPTools_AlgoTools::ComputeStateByOnePoint(aPart, aSd, Precision::Confusion(), theContext);
1676       if (aState == TopAbs_IN)
1677       {
1678         if (aPart.ShapeType() == TopAbs_FACE)
1679         {
1680           TopTools_ListOfShape *pFaces = anINFaces.ChangeSeek(aSd);
1681           if (!pFaces)
1682             pFaces = anINFaces.Bound(aSd, TopTools_ListOfShape());
1683           pFaces->Append(aPart);
1684         }
1685         else
1686         {
1687           aPart.Orientation(TopAbs_INTERNAL);
1688           BRep_Builder().Add(aSd, aPart);
1689         }
1690         aLParts.Remove(itLP);
1691       }
1692       else
1693         itLP.Next();
1694     }
1695   }
1696
1697   // Make shells from faces and put them into solids
1698   TopTools_DataMapOfShapeListOfShape::Iterator itM(anINFaces);
1699   for (; itM.More(); itM.Next())
1700   {
1701     TopoDS_Solid aSd = *(TopoDS_Solid*)&itM.Key();
1702     const TopTools_ListOfShape& aFaces = itM.Value();
1703
1704     TopoDS_Compound aCF;
1705     BRep_Builder().MakeCompound(aCF);
1706
1707     TopTools_ListOfShape::Iterator itLF(aFaces);
1708     for (; itLF.More(); itLF.Next())
1709       BRep_Builder().Add(aCF, itLF.Value());
1710
1711     // Build blocks from the faces
1712     TopTools_ListOfShape aLCB;
1713     BOPTools_AlgoTools::MakeConnexityBlocks(aCF, TopAbs_EDGE, TopAbs_FACE, aLCB);
1714
1715     // Build shell from each block
1716     TopTools_ListOfShape::Iterator itCB(aLCB);
1717     for (; itCB.More(); itCB.Next())
1718     {
1719       const TopoDS_Shape& aCB = itCB.Value();
1720
1721       TopoDS_Shell aShell;
1722       BRep_Builder().MakeShell(aShell);
1723       // Add faces of the block to the shell
1724       TopExp_Explorer expF(aCB, TopAbs_FACE);
1725       for (; expF.More(); expF.Next())
1726       {
1727         TopoDS_Face aFInt = TopoDS::Face(expF.Current());
1728         aFInt.Orientation(TopAbs_INTERNAL);
1729         BRep_Builder().Add(aShell, aFInt);
1730       }
1731
1732       BRep_Builder().Add(aSd, aShell);
1733     }
1734   }
1735 }
1736
1737 //=======================================================================
1738 //function : TrsfToPoint
1739 //purpose  :
1740 //=======================================================================
1741 Standard_Boolean BOPAlgo_Tools::TrsfToPoint (const Bnd_Box& theBox1,
1742                                              const Bnd_Box& theBox2,
1743                                              gp_Trsf&       theTrsf,
1744                                              const gp_Pnt&  thePoint,
1745                                              const Standard_Real theCriteria)
1746 {
1747   // Unify two boxes
1748   Bnd_Box aBox = theBox1;
1749   aBox.Add (theBox2);
1750
1751   gp_XYZ aBCenter = (aBox.CornerMin().XYZ() + aBox.CornerMax().XYZ()) / 2.;
1752   Standard_Real aPBDist = (thePoint.XYZ() - aBCenter).Modulus();
1753   if (aPBDist < theCriteria)
1754     return Standard_False;
1755
1756   Standard_Real aBSize = Sqrt (aBox.SquareExtent());
1757   if ((aBSize / aPBDist) > (1. / theCriteria))
1758     return Standard_False;
1759
1760   theTrsf.SetTranslation (gp_Vec (aBox.CornerMin(), thePoint));
1761   return Standard_True;
1762 }