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