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