src/QANewModTopOpe/QANewModTopOpe_Tools.cxx

   1 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   2 //
   3 // This file is part of Open CASCADE Technology software library.
   4 //
   5 // This library is free software; you can redistribute it and/or modify it under
   6 // the terms of the GNU Lesser General Public License version 2.1 as published
   7 // by the Free Software Foundation, with special exception defined in the file
   8 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
   9 // distribution for complete text of the license and disclaimer of any warranty.
  10 //
  11 // Alternatively, this file may be used under the terms of Open CASCADE
  12 // commercial license or contractual agreement.
  13
  14 #include <QANewModTopOpe_Tools.ixx>
  15
  16 #include <BRepAlgoAPI_Cut.hxx>
  17 #include <BRepAlgoAPI_Common.hxx>
  18
  19 #include <TopoDS.hxx>
  20 #include <TopoDS_Face.hxx>
  21 #include <TopoDS_Edge.hxx>
  22
  23 #include <BRepTools.hxx>
  24 #include <BRep_Tool.hxx>
  25 #include <BRep_Builder.hxx>
  26 #include <Geom_Surface.hxx>
  27 #include <IntTools_Context.hxx>
  28 #include <TopExp_Explorer.hxx>
  29 #include <TopExp.hxx>
  30 #include <GeomAPI_ProjectPointOnSurf.hxx>
  31 #include <TopTools_IndexedMapOfShape.hxx>
  32 #include <TopTools_DataMapOfIntegerShape.hxx>
  33
  34 #include <TCollection_CompareOfReal.hxx>
  35 #include <SortTools_QuickSortOfReal.hxx>
  36
  37 #include <TColStd_Array1OfReal.hxx>
  38 #include <TColStd_IndexedMapOfReal.hxx>
  39 #include <TColStd_ListOfInteger.hxx>
  40 #include <TColStd_ListIteratorOfListOfInteger.hxx>
  41
  42 #include <BOPAlgo_PaveFiller.hxx>
  43 #include <BOPDS_DS.hxx>
  44 #include <BOPAlgo_Builder.hxx>
  45 #include <BOPAlgo_BOP.hxx>
  46 #include <IntTools_CommonPrt.hxx>
  47 #include <TopTools_ListIteratorOfListOfShape.hxx>
  48 #include <BOPDS_CommonBlock.hxx>
  49 #include <BOPTools_AlgoTools3D.hxx>
  50
  51 static Standard_Boolean AddShapeToHistoryMap(const TopoDS_Shape& theOldShape,
  52                                              const TopoDS_Shape& theNewShape,
  53                                              TopTools_IndexedDataMapOfShapeListOfShape& theHistoryMap);
  54
  55 static void FillEdgeHistoryMap(BRepAlgoAPI_BooleanOperation&              theBOP,
  56                                TopTools_IndexedDataMapOfShapeListOfShape& theHistoryMap);
  57
  58 static void SortVertexOnEdge(const TopoDS_Edge&          theEdge,
  59                              const TopTools_ListOfShape& theListOfVertex,
  60                              TopTools_ListOfShape&       theListOfVertexSorted);
  61
  62 static TopAbs_State GetEdgeState(const BOPDS_PDS& pDS,
  63                                  const Handle(BOPDS_PaveBlock)& aPB);
  64
  65 // ========================================================================================
  66 // function: NbPoints
  67 // purpose:
  68 // ========================================================================================
  69 Standard_Integer QANewModTopOpe_Tools::NbPoints(const BOPAlgo_PPaveFiller& theDSFiller)
  70 {
  71   Standard_Integer i, anbpoints, aNb;
  72   //
  73   const BOPDS_PDS& pDS = theDSFiller->PDS();
  74   anbpoints = 0;
  75
  76   //FF
  77   BOPDS_VectorOfInterfFF& aFFs=pDS->InterfFF();
  78   aNb=aFFs.Extent();
  79   for (i = 0; i < aNb; ++i) {
  80     BOPDS_InterfFF& aFF=aFFs(i);
  81     const BOPDS_VectorOfPoint& aVP=aFF.Points();
  82     anbpoints += aVP.Extent();
  83   }
  84
  85   //EF
  86   BOPDS_VectorOfInterfEF& aEFs=pDS->InterfEF();
  87   aNb = aEFs.Extent();
  88   for (i = 0; i < aNb; ++i) {
  89     BOPDS_InterfEF& aEF=aEFs(i);
  90     IntTools_CommonPrt aCP = aEF.CommonPart();
  91     if(aCP.Type() == TopAbs_VERTEX) {
  92       anbpoints++;
  93     }
  94   }
  95
  96   //EE
  97   BOPDS_VectorOfInterfEE& aEEs=pDS->InterfEE();
  98   aNb = aEEs.Extent();
  99   for (i = 0; i < aNb; ++i) {
 100     BOPDS_InterfEE& aEE=aEEs(i);
 101     IntTools_CommonPrt aCP = aEE.CommonPart();
 102     if(aCP.Type() == TopAbs_VERTEX) {
 103       anbpoints++;
 104     }
 105   }
 106
 107   return anbpoints;
 108 }
 109
 110 // ========================================================================================
 111 // function: NewVertex
 112 // purpose:
 113 // ========================================================================================
 114 TopoDS_Shape QANewModTopOpe_Tools::NewVertex(const BOPAlgo_PPaveFiller& theDSFiller,
 115                                              const Standard_Integer     theIndex)
 116 {
 117   TopoDS_Shape aVertex;
 118   Standard_Integer i, j, anbpoints, aNb, aNbP;
 119   //
 120   const BOPDS_PDS& pDS = theDSFiller->PDS();
 121   anbpoints = 0;
 122
 123   //FF
 124   BOPDS_VectorOfInterfFF& aFFs=pDS->InterfFF();
 125   aNb=aFFs.Extent();
 126   for (i = 0; i < aNb; ++i) {
 127     BOPDS_InterfFF& aFF=aFFs(i);
 128     const BOPDS_VectorOfPoint& aVP=aFF.Points();
 129     aNbP = aVP.Extent();
 130     for(j = 0; j < aNbP; ++j) {
 131       anbpoints++;
 132       //
 133       if (theIndex == anbpoints) {
 134         const BOPDS_Point& aNP = aVP(j);
 135         return pDS->Shape(aNP.Index());
 136       }
 137     }
 138   }
 139
 140   //EF
 141   BOPDS_VectorOfInterfEF& aEFs=pDS->InterfEF();
 142   aNb = aEFs.Extent();
 143   for (i = 0; i < aNb; ++i) {
 144     BOPDS_InterfEF& aEF=aEFs(i);
 145     IntTools_CommonPrt aCP = aEF.CommonPart();
 146     if(aCP.Type() == TopAbs_VERTEX) {
 147       anbpoints++;
 148       //
 149       if (theIndex == anbpoints) {
 150         return pDS->Shape(aEF.IndexNew());
 151       }
 152     }
 153   }
 154
 155   //EE
 156   BOPDS_VectorOfInterfEE& aEEs=pDS->InterfEE();
 157   aNb = aEEs.Extent();
 158   for (i = 0; i < aNb; ++i) {
 159     BOPDS_InterfEE& aEE=aEEs(i);
 160     IntTools_CommonPrt aCP = aEE.CommonPart();
 161     if(aCP.Type() == TopAbs_VERTEX) {
 162       anbpoints++;
 163       //
 164       if (theIndex == anbpoints) {
 165         return pDS->Shape(aEE.IndexNew());
 166       }
 167     }
 168   }
 169
 170   return aVertex;
 171 }
 172
 173
 174 // ========================================================================================
 175 // function: HasDomain
 176 // purpose:
 177 // ========================================================================================
 178 Standard_Boolean QANewModTopOpe_Tools::HasSameDomain(const BOPAlgo_PBOP& theBuilder,
 179                                                      const TopoDS_Shape& theFace)
 180 {
 181   Standard_Integer bRet;
 182   bRet = Standard_False;
 183   //
 184   if(theFace.IsNull() || (theFace.ShapeType() != TopAbs_FACE))
 185     return bRet;
 186
 187   BOPCol_ListIteratorOfListOfShape aIt;
 188   const BOPCol_DataMapOfShapeListOfShape& aImages = theBuilder->Images();
 189   if (!aImages.IsBound(theFace)) {
 190     return bRet;
 191   }
 192   const BOPCol_ListOfShape& aLF=aImages.Find(theFace);
 193
 194   if (aLF.Extent() == 0) {
 195     return bRet;
 196   }
 197   const BOPCol_DataMapOfShapeShape& aShapesSD = theBuilder->ShapesSD();
 198
 199   aIt.Initialize(aLF);
 200   for (; aIt.More(); aIt.Next()) {
 201     const TopoDS_Shape& aFsp = aIt.Value();
 202     if (aShapesSD.IsBound(aFsp)) {
 203       bRet = Standard_True;
 204       break;
 205     }
 206   }
 207
 208   return bRet;
 209 }
 210
 211 // ========================================================================================
 212 // function: SameDomain
 213 // purpose:
 214 // ========================================================================================
 215 void QANewModTopOpe_Tools::SameDomain(const BOPAlgo_PBOP&   theBuilder,
 216                                       const TopoDS_Shape&   theFace,
 217                                       TopTools_ListOfShape& theResultList)
 218 {
 219   theResultList.Clear();
 220
 221   if(theFace.IsNull() || (theFace.ShapeType() != TopAbs_FACE))
 222     return;
 223
 224   BOPCol_ListIteratorOfListOfShape aIt;
 225   const BOPCol_ListOfShape& aLF=theBuilder->Splits().Find(theFace);
 226
 227   if (aLF.Extent() == 0) {
 228     return;
 229   }
 230   const BOPCol_DataMapOfShapeShape& aShapesSD = theBuilder->ShapesSD();
 231   const BOPCol_DataMapOfShapeShape& aOrigins = theBuilder->Origins();
 232
 233   aIt.Initialize(aLF);
 234   for (; aIt.More(); aIt.Next()) {
 235     const TopoDS_Shape& aFSp = aIt.Value();
 236     if (aShapesSD.IsBound(aFSp)) {
 237       const TopoDS_Shape& aFSD = aShapesSD.Find(aFSp);
 238       const TopoDS_Shape& aFOr = aOrigins.Find(aFSD);
 239       if (theFace.IsEqual(aFOr)) {
 240         BOPCol_DataMapIteratorOfDataMapOfShapeShape aItSD;
 241         aItSD.Initialize(aShapesSD);
 242         for (; aItSD.More(); aItSD.Next()) {
 243           const TopoDS_Shape& aS = aItSD.Value();
 244           if (aFSD.IsEqual(aS)) {
 245             const TopoDS_Shape& aSK = aItSD.Key();
 246             const TopoDS_Shape& aSKOr = aOrigins.Find(aSK);
 247             if (!aSKOr.IsEqual(theFace)) {
 248               theResultList.Append(aSKOr);
 249             }
 250           }
 251         }
 252       } else {
 253         theResultList.Append(aFOr);
 254       }
 255     }
 256   }
 257 }
 258
 259 // ========================================================================================
 260 // function: IsSplit
 261 // purpose:
 262 // ========================================================================================
 263 Standard_Boolean QANewModTopOpe_Tools::IsSplit(const BOPAlgo_PPaveFiller& theDSFiller,
 264                                           const TopoDS_Shape&       theEdge,
 265                                           const TopAbs_State        theState)
 266 {
 267   if(theEdge.IsNull() || (theEdge.ShapeType() != TopAbs_EDGE))
 268     return Standard_False;
 269
 270   Standard_Integer index;
 271   //
 272   const BOPDS_PDS& pDS = theDSFiller->PDS();
 273   index = pDS->Index(theEdge);
 274   if (index == -1) {
 275     return Standard_False;
 276   }
 277
 278   const BOPDS_ListOfPaveBlock& aLPB = pDS->PaveBlocks(index);
 279   BOPDS_ListIteratorOfListOfPaveBlock aPBIt;
 280   aPBIt.Initialize(aLPB);
 281   for (; aPBIt.More(); aPBIt.Next()) {
 282     const Handle(BOPDS_PaveBlock)& aPB = aPBIt.Value();
 283
 284     TopAbs_State aSplitState = GetEdgeState(pDS, aPB);
 285
 286     if(aSplitState == theState) {
 287       return Standard_True;
 288     }
 289   }
 290
 291   return Standard_False;
 292 }
 293
 294 // ========================================================================================
 295 // function: Splits
 296 // purpose:
 297 // ========================================================================================
 298 void QANewModTopOpe_Tools::Splits(const BOPAlgo_PPaveFiller& theDSFiller,
 299                              const TopoDS_Shape&       theEdge,
 300                              const TopAbs_State        theState,
 301                              TopTools_ListOfShape&     theResultList)
 302 {
 303   theResultList.Clear();
 304
 305   if(theEdge.IsNull() || (theEdge.ShapeType() != TopAbs_EDGE))
 306     return;
 307
 308   Standard_Integer index, nSp;
 309   //
 310   const BOPDS_PDS& pDS = theDSFiller->PDS();
 311   index = pDS->Index(theEdge);
 312   if (index == -1) {
 313     return;
 314   }
 315
 316   const BOPDS_ListOfPaveBlock& aLPB = pDS->PaveBlocks(index);
 317   BOPDS_ListIteratorOfListOfPaveBlock aPBIt;
 318   aPBIt.Initialize(aLPB);
 319   for (; aPBIt.More(); aPBIt.Next()) {
 320     const Handle(BOPDS_PaveBlock)& aPB = aPBIt.Value();
 321     nSp = aPB->Edge();
 322
 323     TopAbs_State aSplitState = GetEdgeState(pDS, aPB);
 324
 325     if(aSplitState == theState) {
 326       TopoDS_Shape aSplit = pDS->Shape(nSp);
 327       theResultList.Append(aSplit);
 328     }
 329   }
 330 }
 331
 332 // ========================================================================================
 333 // function: SplitE
 334 // purpose:
 335 // ========================================================================================
 336 Standard_Boolean QANewModTopOpe_Tools::SplitE(const TopoDS_Edge&    theEdge,
 337                                          TopTools_ListOfShape& theSplits)
 338 {
 339   // prequesitory : <Eanc> is a valid edge.
 340   TopAbs_Orientation oEanc = theEdge.Orientation();
 341   TopoDS_Shape aLocalShape = theEdge.Oriented(TopAbs_FORWARD);
 342   TopoDS_Edge EFOR = TopoDS::Edge(aLocalShape);
 343   TopTools_ListOfShape aListOfVertex;
 344   TopExp_Explorer exv(EFOR,TopAbs_VERTEX);
 345
 346   for (;exv.More(); exv.Next()) {
 347     const TopoDS_Shape& v = exv.Current();
 348     aListOfVertex.Append(v);
 349   }
 350   Standard_Integer nv = aListOfVertex.Extent();
 351
 352   if (nv <= 2) return Standard_False;
 353   TopTools_ListOfShape aListOfVertexSorted;
 354
 355   SortVertexOnEdge(EFOR, aListOfVertex, aListOfVertexSorted);
 356
 357   TopoDS_Vertex v0;
 358   TopTools_ListIteratorOfListOfShape anIt(aListOfVertexSorted);
 359
 360   if (anIt.More()) {
 361     v0 = TopoDS::Vertex(anIt.Value());
 362     anIt.Next();
 363   }
 364   else return Standard_False;
 365
 366   for (; anIt.More(); anIt.Next()) {
 367     TopoDS_Vertex v = TopoDS::Vertex(anIt.Value());
 368
 369     // prequesitory: par0 < par
 370     Standard_Real par0 = BRep_Tool::Parameter(v0, EFOR);
 371     Standard_Real par  = BRep_Tool::Parameter(v, EFOR);
 372
 373     // here, ed has the same geometries than Ein, but with no subshapes.
 374     TopoDS_Edge ed = TopoDS::Edge(EFOR.EmptyCopied());
 375     BRep_Builder BB;
 376     v0.Orientation(TopAbs_FORWARD);
 377     BB.Add(ed, v0);
 378     v.Orientation(TopAbs_REVERSED);
 379     BB.Add(ed, v);
 380     BB.Range(ed, par0, par);
 381
 382     theSplits.Append(ed.Oriented(oEanc));
 383     v0 = v;
 384   }
 385   return Standard_True;
 386 }
 387
 388
 389 // ========================================================================================
 390 // function: EdgeCurveAncestors
 391 // purpose:
 392 // ========================================================================================
 393  Standard_Boolean QANewModTopOpe_Tools::EdgeCurveAncestors(const BOPAlgo_PPaveFiller& theDSFiller,
 394                                                       const TopoDS_Shape&       theEdge,
 395                                                       TopoDS_Shape&             theFace1,
 396                                                       TopoDS_Shape&             theFace2)
 397 {
 398   theFace1.Nullify();
 399   theFace2.Nullify();
 400   //
 401   Standard_Integer i, j, aNb, aNbC, nE, nF1, nF2;
 402   BOPDS_ListIteratorOfListOfPaveBlock aIt;
 403
 404   const BOPDS_PDS& pDS = theDSFiller->PDS();
 405   BOPDS_VectorOfInterfFF& aFFs=pDS->InterfFF();
 406
 407   aNb=aFFs.Extent();
 408   for (i = 0; i < aNb; ++i) {
 409     BOPDS_InterfFF& aFF=aFFs(i);
 410
 411     const BOPDS_VectorOfCurve& aVC = aFF.Curves();
 412     aNbC = aVC.Extent();
 413     for (j = 0; j < aNbC; ++j) {
 414       const BOPDS_Curve& aNC = aVC(j);
 415       const BOPDS_ListOfPaveBlock& aLPB = aNC.PaveBlocks();
 416       aIt.Initialize(aLPB);
 417       for (; aIt.More(); aIt.Next()) {
 418         const Handle(BOPDS_PaveBlock)& aPB = aIt.Value();
 419         nE = aPB->Edge();
 420         const TopoDS_Shape& aE = pDS->Shape(nE);
 421         if (theEdge.IsSame(aE)) {
 422           aFF.Indices(nF1, nF2);
 423           theFace1 = pDS->Shape(nF1);
 424           theFace2 = pDS->Shape(nF2);
 425           return Standard_True;
 426         }
 427       }
 428     }
 429   }
 430
 431   return Standard_False;
 432 }
 433
 434 // ========================================================================================
 435 // function: EdgeSectionAncestors
 436 // purpose:
 437 // ========================================================================================
 438 Standard_Boolean QANewModTopOpe_Tools::EdgeSectionAncestors(const BOPAlgo_PPaveFiller& theDSFiller,
 439                                                             const TopoDS_Shape&       theEdge,
 440                                                             TopTools_ListOfShape&     LF1,
 441                                                             TopTools_ListOfShape&     LF2,
 442                                                             TopTools_ListOfShape&     LE1,
 443                                                             TopTools_ListOfShape&     LE2)
 444 {
 445   if(theEdge.ShapeType() != TopAbs_EDGE)
 446     return Standard_False;
 447
 448   const BOPDS_PDS& pDS = theDSFiller->PDS();
 449   Standard_Integer i = 0, nb = 0, nF, nE, nEOr;
 450   BOPCol_MapOfInteger aMIF;
 451   nb = pDS->NbSourceShapes();
 452
 453   nE = pDS->Index(theEdge);
 454   const BOPDS_ListOfPaveBlock& aLPB1 = pDS->PaveBlocks(nE);
 455   if (!aLPB1.Extent()) {
 456     return Standard_False;
 457   }
 458
 459   const Handle(BOPDS_PaveBlock)& aPB1 = aLPB1.First();
 460   const Handle(BOPDS_CommonBlock)& aCB=pDS->CommonBlock(aPB1);
 461   if (aCB.IsNull()) {
 462     return Standard_False;
 463   }
 464
 465   const BOPCol_ListOfInteger& aLIF = aCB->Faces();
 466   BOPCol_ListIteratorOfListOfInteger aItLI;
 467   aItLI.Initialize(aLIF);
 468   for ( ; aItLI.More(); aItLI.Next()) {
 469     nF = aItLI.Value();
 470     if(pDS->Rank(nF) == 0)
 471       LF1.Append(pDS->Shape(nF));
 472     else
 473       LF2.Append(pDS->Shape(nF));
 474
 475     aMIF.Add(nF);
 476   }
 477
 478   const BOPDS_ListOfPaveBlock& aLPB = aCB->PaveBlocks();
 479   BOPDS_ListIteratorOfListOfPaveBlock aItPB;
 480   aItPB.Initialize(aLPB);
 481   for (; aItPB.More(); aItPB.Next()) {
 482     const Handle(BOPDS_PaveBlock)& aPB = aItPB.Value();
 483     nEOr = aPB->OriginalEdge();
 484
 485     if(pDS->Rank(nEOr) == 0)
 486       LE1.Append(pDS->Shape(nEOr));
 487     else
 488       LE2.Append(pDS->Shape(nEOr));
 489
 490     //find edge ancestors
 491     for(i = 0; i < nb; ++i) {
 492       const BOPDS_ShapeInfo& aSI = pDS->ShapeInfo(i);
 493       if(aSI.ShapeType() != TopAbs_FACE) {
 494         continue;
 495       }
 496       const BOPCol_ListOfInteger& aSubShapes = aSI.SubShapes();
 497       aItLI.Initialize(aSubShapes);
 498       for (; aItLI.More(); aItLI.Next()) {
 499         if (nEOr == aItLI.Value()) {
 500           if (aMIF.Add(i)) {
 501             if(pDS->Rank(i) == 0) LF1.Append(pDS->Shape(i));
 502             else LF2.Append(pDS->Shape(i));
 503           }//if (aMIF.Add(i)) {
 504         }//if (nEOr == aItLI.Value()) {
 505       }//for (; aItLI.More(); aItLI.Next()) {
 506     }//for(i = 0; i < nb; ++i) {
 507   }
 508
 509   Standard_Boolean r = (!LF1.IsEmpty() && !LF2.IsEmpty());
 510   r = r && (!LE1.IsEmpty() || !LE2.IsEmpty());
 511   return r;
 512 }
 513
 514 // ========================================================================================
 515 // function: BoolOpe
 516 // purpose:
 517 // ========================================================================================
 518 Standard_Boolean QANewModTopOpe_Tools::BoolOpe(const TopoDS_Shape& theFace1,
 519                                                const TopoDS_Shape& theFace2,
 520                                                Standard_Boolean&   IsCommonFound,
 521                                                TopTools_IndexedDataMapOfShapeListOfShape& theHistoryMap)
 522 {
 523   IsCommonFound = Standard_False;
 524   theHistoryMap.Clear();
 525   gp_Dir aDNF1, aDNF2;
 526   Standard_Integer iSenseFlag;
 527
 528   BOPAlgo_PaveFiller aDSFiller;
 529   BOPCol_ListOfShape aLS;
 530   aLS.Append(theFace1);
 531   aLS.Append(theFace2);
 532   aDSFiller.SetArguments(aLS);
 533
 534   aDSFiller.Perform();
 535   if (aDSFiller.ErrorStatus()) {
 536     return Standard_False;
 537   }
 538
 539   const BOPDS_PDS& pDS = aDSFiller.PDS();
 540
 541   Standard_Integer aNb = 0, aNbSps;
 542   Standard_Integer i = 0;
 543   TopTools_IndexedMapOfShape aMapV;
 544
 545   {
 546     BRepAlgoAPI_Common aCommon(theFace1, theFace2, aDSFiller);
 547
 548     if(!aCommon.IsDone()) {
 549       return Standard_False;
 550     }
 551
 552     TopExp_Explorer anExp(aCommon.Shape(), TopAbs_FACE);
 553     if(!anExp.More()) {
 554       IsCommonFound = Standard_False;
 555       return Standard_True;
 556     }
 557
 558     IsCommonFound = Standard_True;
 559     TopExp::MapShapes(aCommon.Shape(), TopAbs_VERTEX, aMapV);
 560     // fill edge history.begin
 561     FillEdgeHistoryMap(aCommon, theHistoryMap);
 562     // fill edge history.end
 563
 564     // fill face history.begin
 565     BOPDS_VectorOfInterfFF& aFFs = pDS->InterfFF();
 566     aNb = aFFs.Extent();
 567     Standard_Boolean bReverseFlag = Standard_True;
 568     Standard_Boolean fillhistory = Standard_True;
 569
 570     for (i=0; i<aNb; ++i) {
 571       BOPDS_InterfFF& aFF = aFFs(i);
 572       Standard_Integer nF1, nF2;
 573       aFF.Indices(nF1, nF2);
 574
 575       const TopoDS_Face& aF1 = *(TopoDS_Face*)(&pDS->Shape(nF1));
 576       const TopoDS_Face& aF2 = *(TopoDS_Face*)(&pDS->Shape(nF2));
 577
 578       BOPCol_ListOfInteger aLSE;
 579       pDS->SharedEdges(nF1, nF2, aLSE, aDSFiller.Allocator());
 580       aNbSps = aLSE.Extent();
 581
 582       if (!aNbSps) {
 583         fillhistory = Standard_False;
 584         continue;
 585       }
 586
 587       Standard_Integer nE = aLSE.First();
 588       const TopoDS_Edge& aSpE = *(TopoDS_Edge*)(&pDS->Shape(nE));
 589
 590       BOPTools_AlgoTools3D::GetNormalToFaceOnEdge (aSpE, aF1, aDNF1);
 591       BOPTools_AlgoTools3D::GetNormalToFaceOnEdge (aSpE, aF2, aDNF2);
 592       iSenseFlag=BOPTools_AlgoTools3D::SenseFlag (aDNF1, aDNF2);
 593
 594       if(iSenseFlag == 1) {
 595         fillhistory = Standard_True;
 596         bReverseFlag = Standard_False;
 597       }
 598       else if(iSenseFlag == -1) {
 599         fillhistory = Standard_True;
 600         bReverseFlag = Standard_True;
 601       }
 602       else
 603         fillhistory = Standard_False;
 604     }
 605
 606     if(fillhistory) {
 607
 608       for(; anExp.More(); anExp.Next()) {
 609         TopoDS_Shape aResShape = anExp.Current();
 610
 611         if(theFace1.Orientation() == aResShape.Orientation()) {
 612           AddShapeToHistoryMap(theFace1, aResShape, theHistoryMap);
 613
 614           if(bReverseFlag)
 615             aResShape.Reverse();
 616           AddShapeToHistoryMap(theFace2, aResShape, theHistoryMap);
 617         }
 618         else if(theFace2.Orientation() == aResShape.Orientation()) {
 619           AddShapeToHistoryMap(theFace2, aResShape, theHistoryMap);
 620
 621           if(bReverseFlag)
 622             aResShape.Reverse();
 623           AddShapeToHistoryMap(theFace1, aResShape, theHistoryMap);
 624         }
 625         else {
 626           aResShape.Orientation(theFace1.Orientation());
 627           AddShapeToHistoryMap(theFace1, aResShape, theHistoryMap);
 628           aResShape.Orientation(theFace2.Orientation());
 629
 630           if(bReverseFlag)
 631             aResShape.Reverse();
 632           AddShapeToHistoryMap(theFace2, aResShape, theHistoryMap);
 633         }
 634       }
 635     }
 636     // fill face history.end
 637   }
 638   {
 639     BRepAlgoAPI_Cut aCut1(theFace1, theFace2, aDSFiller);
 640
 641     if(!aCut1.IsDone())
 642       return Standard_False;
 643     TopExp::MapShapes(aCut1.Shape(), TopAbs_VERTEX, aMapV);
 644     // fill edge history.begin
 645     FillEdgeHistoryMap(aCut1, theHistoryMap);
 646     // fill edge history.end
 647
 648     // fill face history.begin
 649     TopExp_Explorer anExp(aCut1.Shape(), TopAbs_FACE);
 650
 651     for(; anExp.More(); anExp.Next()) {
 652       TopoDS_Shape aResShape = anExp.Current();
 653       aResShape.Orientation(theFace1.Orientation());
 654       AddShapeToHistoryMap(theFace1, aResShape, theHistoryMap);
 655     }
 656     // fill face history.end
 657   }
 658
 659   {
 660     BRepAlgoAPI_Cut aCut2(theFace1, theFace2, aDSFiller, Standard_False);
 661
 662     if(!aCut2.IsDone())
 663       return Standard_False;
 664     TopExp::MapShapes(aCut2.Shape(), TopAbs_VERTEX, aMapV);
 665     // fill edge history.begin
 666     FillEdgeHistoryMap(aCut2, theHistoryMap);
 667     // fill edge history.end
 668
 669     // fill face history.begin
 670     TopExp_Explorer anExp(aCut2.Shape(), TopAbs_FACE);
 671
 672     for(; anExp.More(); anExp.Next()) {
 673       TopoDS_Shape aResShape = anExp.Current();
 674       aResShape.Orientation(theFace2.Orientation());
 675       AddShapeToHistoryMap(theFace2, aResShape, theHistoryMap);
 676     }
 677     // fill face history.end
 678   }
 679
 680   // fill vertex history.begin
 681   BOPDS_VectorOfInterfVV& aVVs = pDS->InterfVV();
 682   aNb = aVVs.Extent();
 683
 684   for (i = 0; i < aNb; ++i) {
 685     BOPDS_InterfVV& aVVi = aVVs(i);
 686     if (!aVVi.HasIndexNew()) {
 687       continue;
 688     }
 689     Standard_Integer aNewShapeIndex = aVVi.IndexNew();
 690
 691     const TopoDS_Shape& aNewVertex = pDS->Shape(aNewShapeIndex);
 692
 693     if(!aMapV.Contains(aNewVertex)) {
 694       continue;
 695     }
 696
 697     const TopoDS_Shape& aV1 = pDS->Shape(aVVi.Index1());
 698     const TopoDS_Shape& aV2 = pDS->Shape(aVVi.Index2());
 699     AddShapeToHistoryMap(aV1, aNewVertex, theHistoryMap);
 700     AddShapeToHistoryMap(aV2, aNewVertex, theHistoryMap);
 701   }
 702
 703   BOPDS_VectorOfInterfVE& aVEs = pDS->InterfVE();
 704   aNb = aVEs.Extent();
 705
 706   for (i = 0; i < aNb; ++i) {
 707     BOPDS_InterfVE& aVEi = aVEs(i);
 708
 709     Standard_Integer anIndex = aVEi.Index1();
 710     const TopoDS_Shape& aNewVertex = pDS->Shape(anIndex);
 711
 712     if(!aMapV.Contains(aNewVertex))
 713       continue;
 714
 715     AddShapeToHistoryMap(aNewVertex, aNewVertex, theHistoryMap);
 716   }
 717
 718   BOPDS_VectorOfInterfVF& aVSs = pDS->InterfVF();
 719   aNb = aVSs.Extent();
 720
 721   for (i = 0; i < aNb; ++i) {
 722     BOPDS_InterfVF& aVSi = aVSs(i);
 723
 724     Standard_Integer anIndex = aVSi.Index1();
 725     const TopoDS_Shape& aNewVertex = pDS->Shape(anIndex);
 726
 727     if(!aMapV.Contains(aNewVertex))
 728       continue;
 729
 730     AddShapeToHistoryMap(aNewVertex, aNewVertex, theHistoryMap);
 731   }
 732   // fill vertex history.end
 733   return Standard_True;
 734 }
 735
 736 // --------------------------------------------------------------------------------------------
 737 // static function: AddShapeToHistoryMap
 738 // purpose:
 739 // --------------------------------------------------------------------------------------------
 740 Standard_Boolean AddShapeToHistoryMap(const TopoDS_Shape& theOldShape,
 741                                       const TopoDS_Shape& theNewShape,
 742                                       TopTools_IndexedDataMapOfShapeListOfShape& theHistoryMap) {
 743
 744   if(!theHistoryMap.Contains(theOldShape)) {
 745     TopTools_ListOfShape aList;
 746     aList.Append(theNewShape);
 747     theHistoryMap.Add(theOldShape, aList);
 748     return Standard_True;
 749   }
 750
 751   Standard_Boolean found = Standard_False;
 752   TopTools_ListOfShape& aList = theHistoryMap.ChangeFromKey(theOldShape);
 753   TopTools_ListIteratorOfListOfShape aVIt(aList);
 754
 755   for(; aVIt.More(); aVIt.Next()) {
 756     if(theNewShape.IsSame(aVIt.Value())) {
 757       found = Standard_True;
 758       break;
 759     }
 760   }
 761
 762   if(!found) {
 763     aList.Append(theNewShape);
 764   }
 765   return !found;
 766 }
 767
 768 // --------------------------------------------------------------------------------------------
 769 // static function: FillEdgeHistoryMap
 770 // purpose:
 771 // --------------------------------------------------------------------------------------------
 772 void FillEdgeHistoryMap(BRepAlgoAPI_BooleanOperation&              theBOP,
 773                         TopTools_IndexedDataMapOfShapeListOfShape& theHistoryMap) {
 774
 775   TopExp_Explorer anExp;
 776   anExp.Init(theBOP.Shape1(), TopAbs_EDGE);
 777
 778   for(; anExp.More(); anExp.Next()) {
 779     const TopTools_ListOfShape& aList = theBOP.Modified(anExp.Current());
 780     TopTools_ListIteratorOfListOfShape anIt(aList);
 781
 782     for(; anIt.More(); anIt.Next()) {
 783       AddShapeToHistoryMap(anExp.Current(), anIt.Value(), theHistoryMap);
 784     }
 785   }
 786
 787   anExp.Init(theBOP.Shape2(), TopAbs_EDGE);
 788
 789   for(; anExp.More(); anExp.Next()) {
 790     const TopTools_ListOfShape& aList = theBOP.Modified(anExp.Current());
 791     TopTools_ListIteratorOfListOfShape anIt(aList);
 792
 793     for(; anIt.More(); anIt.Next()) {
 794       AddShapeToHistoryMap(anExp.Current(), anIt.Value(), theHistoryMap);
 795     }
 796   }
 797 }
 798
 799 // --------------------------------------------------------------------------------------------
 800 // static function: SortVertexOnEdge
 801 // purpose:
 802 // --------------------------------------------------------------------------------------------
 803 void SortVertexOnEdge(const TopoDS_Edge&          theEdge,
 804                       const TopTools_ListOfShape& theListOfVertex,
 805                       TopTools_ListOfShape&       theListOfVertexSorted) {
 806
 807   TopTools_DataMapOfIntegerShape mapiv;// mapiv.Find(iV) = V
 808   TColStd_IndexedMapOfReal mappar;     // mappar.FindIndex(parV) = iV
 809   TopTools_ListIteratorOfListOfShape itlove(theListOfVertex);
 810
 811   for (; itlove.More(); itlove.Next()){
 812     const TopoDS_Vertex& v = TopoDS::Vertex(itlove.Value());
 813     Standard_Real par = BRep_Tool::Parameter(v, theEdge);
 814     Standard_Integer iv = mappar.Add(par);
 815     mapiv.Bind(iv,v);
 816   }
 817   Standard_Integer nv = mapiv.Extent();
 818   TColStd_Array1OfReal tabpar(1,nv);
 819   Standard_Integer i = 0;
 820
 821   for ( i = 1; i <= nv; i++) {
 822     Standard_Real p = mappar.FindKey(i);
 823     tabpar.SetValue(i,p);
 824   }
 825   theListOfVertexSorted.Clear();
 826   TCollection_CompareOfReal compare;
 827   SortTools_QuickSortOfReal::Sort(tabpar, compare);
 828
 829   for (i = 1; i <= nv; i++) {
 830     Standard_Real par = tabpar.Value(i);
 831     Standard_Integer iv = mappar.FindIndex(par);
 832     const TopoDS_Shape& v = mapiv.Find(iv);
 833     theListOfVertexSorted.Append(v);
 834   }
 835 }
 836
 837 // --------------------------------------------------------------------------------------------
 838 // static function: GetEdgeState
 839 // purpose:
 840 // --------------------------------------------------------------------------------------------
 841   static TopAbs_State GetEdgeState(const BOPDS_PDS& pDS,
 842                                    const Handle(BOPDS_PaveBlock)& aPB)
 843 {
 844   Standard_Integer j, aNbFI;
 845   Standard_Boolean bIn;
 846   TopAbs_State aState = TopAbs_ON;
 847   //
 848   const BOPDS_VectorOfFaceInfo& aVFI = pDS->FaceInfoPool();
 849   aNbFI = aVFI.Extent();
 850   //
 851   for (j = 0; j < aNbFI; ++j) {
 852     const BOPDS_FaceInfo& aFI = aVFI(j);
 853     bIn = aFI.PaveBlocksIn().Contains(aPB);
 854     if (bIn) {
 855       aState = TopAbs_IN;
 856       break;
 857     }
 858   }
 859   return aState;
 860 }