src/BRepFill/BRepFill_TrimShellCorner.cxx

   1 // Created on: 2003-10-21
   2 // Created by: Mikhail KLOKOV
   3 // Copyright (c) 2003-2012 OPEN CASCADE SAS
   4 //
   5 // The content of this file is subject to the Open CASCADE Technology Public
   6 // License Version 6.5 (the "License"). You may not use the content of this file
   7 // except in compliance with the License. Please obtain a copy of the License
   8 // at http://www.opencascade.org and read it completely before using this file.
   9 //
  10 // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
  11 // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
  12 //
  13 // The Original Code and all software distributed under the License is
  14 // distributed on an "AS IS" basis, without warranty of any kind, and the
  15 // Initial Developer hereby disclaims all such warranties, including without
  16 // limitation, any warranties of merchantability, fitness for a particular
  17 // purpose or non-infringement. Please see the License for the specific terms
  18 // and conditions governing the rights and limitations under the License.
  19
  20
  21 #include <BRepFill_TrimShellCorner.ixx>
  22
  23 #include <BRepAlgoAPI_Section.hxx>
  24 #include <BRep_Builder.hxx>
  25 #include <BRep_Tool.hxx>
  26 #include <BRepLib_MakeEdge.hxx>
  27 #include <BRepTools_ReShape.hxx>
  28 #include <TopoDS.hxx>
  29 #include <TopoDS_Shell.hxx>
  30 #include <TopoDS_Compound.hxx>
  31
  32 #include <IntTools_BeanFaceIntersector.hxx>
  33 #include <IntTools_Context.hxx>
  34 #include <IntTools_Range.hxx>
  35
  36 #include <BOPTools_Pave.hxx>
  37 #include <BOPTools_DSFiller.hxx>
  38 #include <BOPTools_PaveFiller.hxx>
  39 #include <BOPTools_CArray1OfVVInterference.hxx>
  40 #include <BOPTools_CArray1OfVEInterference.hxx>
  41 #include <BOPTools_CArray1OfEEInterference.hxx>
  42 #include <BOPTools_CArray1OfSSInterference.hxx>
  43 #include <BOPTools_VVInterference.hxx>
  44 #include <BOPTools_VEInterference.hxx>
  45 #include <BOPTools_EEInterference.hxx>
  46 #include <BOPTools_SSInterference.hxx>
  47 #include <BOPTools_InterferencePool.hxx>
  48 #include <BOPTools_Curve.hxx>
  49 #include <BOPTools_SequenceOfCurves.hxx>
  50 #include <BOPTools_PaveBlock.hxx>
  51 #include <BOPTools_CommonBlock.hxx>
  52 #include <BOPTools_ListIteratorOfListOfPaveBlock.hxx>
  53 #include <BOPTools_ListIteratorOfListOfCommonBlock.hxx>
  54 #include <BOPTools_PaveSet.hxx>
  55 #include <BOPTools_ListIteratorOfListOfPave.hxx>
  56 #include <BooleanOperations_ShapesDataStructure.hxx>
  57 #include <BOP_BuilderTools.hxx>
  58
  59 #include <Geom_Curve.hxx>
  60 #include <Geom2d_Curve.hxx>
  61 #include <gp_Pnt2d.hxx>
  62
  63 #include <TopLoc_Location.hxx>
  64 #include <TopExp.hxx>
  65 #include <TopExp_Explorer.hxx>
  66 #include <TopTools_MapOfShape.hxx>
  67 #include <TopTools_ListOfShape.hxx>
  68 #include <TopTools_Array1OfListOfShape.hxx>
  69 #include <TopTools_ListIteratorOfListOfShape.hxx>
  70 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
  71
  72 #include <gp_Pln.hxx>
  73 #include <TopoDS_Iterator.hxx>
  74 #include <TColgp_Array1OfPnt.hxx>
  75 #include <TColgp_Array2OfPnt.hxx>
  76 #include <TColgp_Array1OfDir.hxx>
  77 #include <TColStd_ListOfInteger.hxx>
  78 #include <TColStd_ListIteratorOfListOfInteger.hxx>
  79 #include <GCPnts_UniformAbscissa.hxx>
  80 #include <GeomLib.hxx>
  81 #include <BRepLib_MakeWire.hxx>
  82 #include <TopTools_SequenceOfShape.hxx>
  83 #include <TColStd_Array1OfBoolean.hxx>
  84 #include <TColgp_SequenceOfPnt.hxx>
  85 #include <gce_MakeLin.hxx>
  86
  87 static Standard_Boolean IsFromFirstToSecond(const TopoDS_Edge&   theEdge,
  88                                             const Standard_Real  theParameterOnUEdge,
  89                                             const TopoDS_Edge&   theUEdge1,
  90                                             const TopoDS_Edge&   theUEdge2,
  91                                             const TopoDS_Face&   theFace);
  92
  93 static Standard_Boolean FindParameter(const BOPTools_PaveSet&                     thePaveSet,
  94                                       const BooleanOperations_KindOfInterference& theType,
  95                                       const Standard_Integer                      theInterfIndex,
  96                                       Standard_Real&                              theParam);
  97
  98 static Standard_Boolean FindCommonVertex(const BOPTools_DSFiller& theDSFiller,
  99                                          const Standard_Integer   theEIndex1,
 100                                          const Standard_Integer   theEIndex2,
 101                                          TopoDS_Vertex&           theCommonVertex,
 102                                          Standard_Real&           theParamOnE1,
 103                                          Standard_Real&           theParamOnE2);
 104
 105 static Standard_Boolean MakeFacesNonSec(const Standard_Integer                     theIndex,
 106                                         const Handle(TopTools_HArray2OfShape)&     theUEdges,
 107                                         const Handle(TopTools_HArray2OfShape)&     theBounds,
 108                                         const BOPTools_DSFiller&                   theDSFiller,
 109                                         const Standard_Integer                     theFaceIndex1,
 110                                         const Standard_Integer                     theFaceIndex2,
 111                                         TopTools_DataMapOfShapeListOfShape&        theHistMap);
 112
 113 static Standard_Boolean MakeFacesSec(const Standard_Integer                     theIndex,
 114                                      const Handle(TopTools_HArray2OfShape)&     theUEdges,
 115                                      const Handle(TopTools_HArray2OfShape)&     theBounds,
 116                                      const BOPTools_DSFiller&                   theDSFiller,
 117                                      const Standard_Integer                     theFaceIndex1,
 118                                      const Standard_Integer                     theFaceIndex2,
 119                                      const Standard_Integer                     theSSInterfIndex,
 120                                      const gp_Ax2&                              AxeOfBisPlane,
 121                                      TopTools_DataMapOfShapeListOfShape&        theHistMap);
 122
 123 static Standard_Boolean SplitUEdges(const Handle(TopTools_HArray2OfShape)&     theUEdges,
 124                                     const BOPTools_DSFiller&                   theDSFiller,
 125                                     TopTools_DataMapOfShapeListOfShape&        theHistMap);
 126
 127 static void FindFreeVertices(const TopoDS_Shape&         theShape,
 128                              const TopTools_MapOfShape&  theVerticesToAvoid,
 129                              TopTools_ListOfShape&       theListOfVertex);
 130
 131 static Standard_Boolean CheckAndOrientEdges(const TopTools_ListOfShape&  theOrderedList,
 132                                             const gp_Pnt2d&              theFirstPoint,
 133                                             const gp_Pnt2d&              theLastPoint,
 134                                             const TopoDS_Face&           theFace,
 135                                             TopTools_ListOfShape&        theOrientedList);
 136
 137 static Standard_Boolean FillGap(const TopoDS_Vertex&   theFirstVertex,
 138                                 const TopoDS_Vertex&   theLastVertex,
 139                                 const gp_Pnt2d&        theFirstPoint,
 140                                 const gp_Pnt2d&        theLastPoint,
 141                                 const TopoDS_Face&     theFace,
 142                                 const TopoDS_Compound& theSectionEdges,
 143                                 TopTools_ListOfShape&  theOrderedList);
 144
 145 static Standard_Boolean FindNextEdge(const TopoDS_Vertex&   theFirstVertex,
 146                                      const TopoDS_Vertex&   theLastVertex,
 147                                      const TopTools_IndexedDataMapOfShapeListOfShape& theMapVE,
 148                                      const TopTools_MapOfShape& theMapToAvoid,
 149                                      TopTools_ListOfShape&  theOrderedList);
 150
 151 static Standard_Boolean FindVertex(const TopoDS_Edge&                        theEdge,
 152                                    const Standard_Integer                    theRank,
 153                                    const BOPTools_DSFiller&                  theDSFiller,
 154                                    const TopTools_DataMapOfShapeListOfShape& theHistMap,
 155                                    TopoDS_Vertex&                            theVertex,
 156                                    BOPTools_Pave&                            thePave);
 157
 158 static Standard_Boolean FindNextVertex(const Standard_Integer                    theEdgeIndex,
 159                                        const BOPTools_Pave&                      thePrevPave,
 160                                        const BOPTools_DSFiller&                  theDSFiller,
 161                                        TopoDS_Vertex&                            theNextVertex,
 162                                        BOPTools_Pave&                            thePave);
 163
 164 static Standard_Boolean GetPave(const Standard_Integer   theEdgeIndex,
 165                                 const Standard_Boolean   isFirst,
 166                                 const BOPTools_DSFiller& theDSFiller,
 167                                 BOPTools_Pave&           thePave);
 168
 169 static Standard_Boolean FindFromUEdge(const TopoDS_Edge&                        theUE1Old,
 170                                       const TopoDS_Edge&                        theUE2Old,
 171                                       const TopoDS_Edge&                        theUE1New,
 172                                       const TopoDS_Edge&                        theUE2New,
 173                                       const TopoDS_Face&                        theFace,
 174                                       const TopoDS_Compound&                    theSecEdges,
 175                                       const Standard_Integer                    theRank,
 176                                       const TopoDS_Edge&                        theBoundEdge,
 177                                       const Standard_Integer                    theBoundEdgeIndex,
 178                                       const BOPTools_DSFiller&                  theDSFiller,
 179                                       const TopTools_DataMapOfShapeListOfShape& theHistMap,
 180                                       TopoDS_Compound&                          theSecEdgesNew,
 181                                       TopTools_ListOfShape&                     theListOfWireEdges,
 182                                       BOPTools_Pave&                            theFoundPave,
 183                                       Standard_Boolean&                         isOnUEdge);
 184
 185 static Standard_Boolean FindFromVEdge(const BOPTools_Pave&                      thePrevPave,
 186                                       const Standard_Boolean&                   isOnUEdge,
 187                                       const TopoDS_Edge&                        theUE1Old,
 188                                       const TopoDS_Edge&                        theUE2Old,
 189                                       const TopoDS_Face&                        theFace,
 190                                       const TopoDS_Compound&                    theSecEdges,
 191                                       const Standard_Integer                    theRank,
 192                                       const TopoDS_Edge&                        theBoundEdge,
 193                                       const Standard_Integer                    theBoundEdgeIndex,
 194                                       const BOPTools_DSFiller&                  theDSFiller,
 195                                       const TopTools_DataMapOfShapeListOfShape& theHistMap,
 196                                       TopTools_ListOfShape&                     theListOfWireEdges,
 197                                       Standard_Boolean&                         isSectionFound);
 198
 199 static void RemoveEdges(const TopoDS_Compound&      theSourceComp,
 200                         const TopTools_ListOfShape& theListToRemove,
 201                         TopoDS_Compound&            theResultComp);
 202
 203 static Standard_Boolean FilterSectionEdges(const BOPTools_SequenceOfCurves& theBCurves,
 204                                            const TopoDS_Face&               theSecPlane,
 205                                            const BOPTools_DSFiller&         theDSFiller,
 206                                            TopoDS_Compound&                 theResult);
 207
 208 static Standard_Boolean GetUEdges(const Standard_Integer                     theIndex,
 209                                   const Standard_Integer                     theRank,
 210                                   const Handle(TopTools_HArray2OfShape)&     theUEdges,
 211                                   const TopoDS_Edge&                         theBoundEdge,
 212                                   const TopoDS_Face&                         theFace,
 213                                   TopoDS_Edge&                               theFirstUEdge,
 214                                   TopoDS_Edge&                               theSecondUEdge);
 215
 216 static Standard_Real ComputeAveragePlaneAndMaxDeviation(const TopoDS_Shape& aWire,
 217                                                         gp_Pln& thePlane,
 218                                                         Standard_Boolean& IsSingular);
 219
 220 static Standard_Boolean ChooseSection(const TopoDS_Shape& Comp,
 221                                       const gp_Ax2& bis,
 222                                       TopoDS_Shape& resWire,
 223                                       gp_Pln& resPlane,
 224                                       Standard_Boolean& IsSingular);
 225
 226 static Standard_Boolean ChoosePlane(const TopoDS_Shape& Comp,
 227                                     const gp_Ax2& bis,
 228                                     gp_Pln& resPlane,
 229                                     TopoDS_Compound& NewComp);
 230
 231
 232 // ===========================================================================================
 233 // function: Constructor
 234 // purpose:
 235 // ===========================================================================================
 236 BRepFill_TrimShellCorner::BRepFill_TrimShellCorner(const Handle(TopTools_HArray2OfShape)& theFaces,
 237                                                    const gp_Ax2&                          theAxeOfBisPlane,
 238                                                    const TopoDS_Face&                     theSecPlane) :
 239 myAxeOfBisPlane(theAxeOfBisPlane),
 240 myDone(Standard_False),
 241 myHasSection(Standard_False)
 242 {
 243   myFaces = new TopTools_HArray2OfShape(theFaces->LowerRow(), theFaces->UpperRow(),
 244                                         theFaces->LowerCol(), theFaces->UpperCol());
 245   myFaces->ChangeArray2() = theFaces->Array2();
 246   mySecPln = theSecPlane;
 247 }
 248
 249 // ===========================================================================================
 250 // function: Constructor
 251 // purpose:
 252 // ===========================================================================================
 253 BRepFill_TrimShellCorner::BRepFill_TrimShellCorner(const Handle(TopTools_HArray2OfShape)& theFaces,
 254                                                    const gp_Ax2&                          theAxeOfBisPlane,
 255                                                    const TopoDS_Wire&                     theSpine,
 256                                                    const TopoDS_Face&                     theSecPlane):
 257 myAxeOfBisPlane(theAxeOfBisPlane),
 258 myDone(Standard_False),
 259 myHasSection(Standard_False)
 260 {
 261   myFaces = new TopTools_HArray2OfShape(theFaces->LowerRow(), theFaces->UpperRow(),
 262                                         theFaces->LowerCol(), theFaces->UpperCol());
 263   myFaces->ChangeArray2() = theFaces->Array2();
 264   mySpine = theSpine;
 265   mySecPln = theSecPlane;
 266 }
 267
 268 // ===========================================================================================
 269 // function: SetSpine
 270 // purpose:
 271 // ===========================================================================================
 272 void BRepFill_TrimShellCorner::SetSpine(const TopoDS_Wire& theSpine)
 273 {
 274   mySpine = theSpine;
 275 }
 276
 277 // ===========================================================================================
 278 // function: AddBounds
 279 // purpose:
 280 // ===========================================================================================
 281 void BRepFill_TrimShellCorner::AddBounds(const Handle(TopTools_HArray2OfShape)& theBounds)
 282 {
 283   myBounds = new TopTools_HArray2OfShape(theBounds->LowerRow(), theBounds->UpperRow(),
 284                                          theBounds->LowerCol(), theBounds->UpperCol());
 285   myBounds->ChangeArray2() = theBounds->Array2();
 286 }
 287
 288 // ===========================================================================================
 289 // function: AddUEdges
 290 // purpose:
 291 // ===========================================================================================
 292 void BRepFill_TrimShellCorner::AddUEdges(const Handle(TopTools_HArray2OfShape)& theUEdges)
 293 {
 294   myUEdges = new TopTools_HArray2OfShape(theUEdges->LowerRow(), theUEdges->UpperRow(),
 295                                          theUEdges->LowerCol(), theUEdges->UpperCol());
 296   myUEdges->ChangeArray2() = theUEdges->Array2();
 297 }
 298
 299 // ===========================================================================================
 300 // function: Perform
 301 // purpose:
 302 // ===========================================================================================
 303 void BRepFill_TrimShellCorner::Perform()
 304 {
 305   myDone = Standard_False;
 306   myHistMap.Clear();
 307
 308   if(myFaces->RowLength() != 2)
 309     return;
 310   Standard_Integer ii = 0, jj = 0;
 311   BRep_Builder aBB;
 312
 313   for(jj = myFaces->LowerCol(); jj <= myFaces->UpperCol(); jj++) {
 314     TopoDS_Shell aShell;
 315     aBB.MakeShell(aShell);
 316
 317     for(ii = myFaces->LowerRow(); ii <= myFaces->UpperRow(); ii++) {
 318       aBB.Add(aShell, myFaces->Value(ii, jj));
 319     }
 320
 321     if(jj == myFaces->LowerCol()) {
 322       myShape1 = aShell;
 323     }
 324     else {
 325       myShape2 = aShell;
 326     }
 327   }
 328
 329   BOPTools_DSFiller aDSFiller;
 330   aDSFiller.SetShapes(myShape1, myShape2);
 331
 332   if (!aDSFiller.IsDone()) {
 333     return;
 334   }
 335   aDSFiller.Perform();
 336
 337   BRepAlgoAPI_Section aSectionAlgo(myShape1, myShape2, aDSFiller, Standard_False);
 338   aSectionAlgo.ComputePCurveOn1(Standard_True);
 339   aSectionAlgo.ComputePCurveOn2(Standard_True);
 340   aSectionAlgo.Approximation(Standard_True);
 341   aSectionAlgo.Build();
 342
 343   if(!aSectionAlgo.IsDone())
 344     return;
 345
 346   const BooleanOperations_ShapesDataStructure& aDS = aDSFiller.DS();
 347   const BOPTools_InterferencePool&             anInterfPool = aDSFiller.InterfPool();
 348   BOPTools_InterferencePool* pInterfPool =
 349       (BOPTools_InterferencePool*) &anInterfPool;
 350   BOPTools_CArray1OfSSInterference& aFFs =
 351     pInterfPool->SSInterferences();
 352   Standard_Integer aNbFFs = aFFs.Extent();
 353
 354   if(!SplitUEdges(myUEdges, aDSFiller, myHistMap)) {
 355     return;
 356   }
 357
 358   for(ii = myFaces->LowerRow(); ii <= myFaces->UpperRow(); ii++) {
 359     TopoDS_Shape aF1 = myFaces->Value(ii, myFaces->LowerCol());
 360     TopoDS_Shape aF2 = myFaces->Value(ii, myFaces->UpperCol());
 361     Standard_Integer anIndex1 = aDS.ShapeIndex(aF1, 1);
 362     Standard_Integer anIndex2 = aDS.ShapeIndex(aF2, 2);
 363
 364     if((anIndex1 == 0) || (anIndex2 == 0))
 365       continue;
 366     Standard_Integer i = 0;
 367
 368     for (i=1; i <= aNbFFs; i++) {
 369       BOPTools_SSInterference& aFFi=aFFs(i);
 370       //
 371       Standard_Integer nF1 = aFFi.Index1();
 372       Standard_Integer nF2 = aFFi.Index2();
 373
 374       if((nF1 == anIndex1) && (nF2 == anIndex2)) {
 375         BOPTools_SequenceOfCurves& aBCurves = aFFi.Curves();
 376         Standard_Integer aNbCurves = aBCurves.Length();
 377         Standard_Integer j = 0;
 378         Standard_Boolean bhassec = Standard_False;
 379
 380         for (j = 1; j <= aNbCurves; j++) {
 381           const BOPTools_Curve& aBCurve = aBCurves(j);
 382           const BOPTools_ListOfPaveBlock& aSectEdges = aBCurve.NewPaveBlocks();
 383
 384           if(!aSectEdges.IsEmpty()) {
 385             bhassec = Standard_True;
 386             break;
 387           }
 388         }
 389
 390         if(!bhassec) {
 391           if(!MakeFacesNonSec(ii, myUEdges, myBounds, aDSFiller, anIndex1, anIndex2, myHistMap)) {
 392             myHistMap.Clear();
 393             return;
 394           }
 395         }
 396         else {
 397           if(!MakeFacesSec(ii, myUEdges, myBounds, aDSFiller, anIndex1, anIndex2,
 398                            i, myAxeOfBisPlane, myHistMap)) {
 399             myHistMap.Clear();
 400             return;
 401           }
 402         }
 403         break;
 404       }
 405     }
 406   }
 407   myDone = Standard_True;
 408 }
 409
 410 // ===========================================================================================
 411 // function: IsDone
 412 // purpose:
 413 // ===========================================================================================
 414 Standard_Boolean BRepFill_TrimShellCorner::IsDone() const
 415 {
 416   return myDone;
 417 }
 418
 419 // ===========================================================================================
 420 // function: HasSection
 421 // purpose:
 422 // ===========================================================================================
 423 Standard_Boolean BRepFill_TrimShellCorner::HasSection() const
 424 {
 425   return myHasSection;
 426 }
 427
 428 // ===========================================================================================
 429 // function: Modified
 430 // purpose:
 431 // ===========================================================================================
 432 void BRepFill_TrimShellCorner::Modified(const TopoDS_Shape&   theShape,
 433                                         TopTools_ListOfShape& theModified)
 434 {
 435   theModified.Clear();
 436
 437   if(myHistMap.IsBound(theShape)) {
 438     theModified = myHistMap.Find(theShape);
 439   }
 440 }
 441
 442 // ----------------------------------------------------------------------------------------------------
 443 // static function: MakeFacesNonSec
 444 // purpose:
 445 // ----------------------------------------------------------------------------------------------------
 446 Standard_Boolean MakeFacesNonSec(const Standard_Integer                     theIndex,
 447                                  const Handle(TopTools_HArray2OfShape)&     theUEdges,
 448                                  const Handle(TopTools_HArray2OfShape)&     theBounds,
 449                                  const BOPTools_DSFiller&                   theDSFiller,
 450                                  const Standard_Integer                     theFaceIndex1,
 451                                  const Standard_Integer                     theFaceIndex2,
 452                                  TopTools_DataMapOfShapeListOfShape&        theHistMap)
 453 {
 454
 455   Standard_Boolean bHasNewEdge = Standard_False;
 456   TopoDS_Edge aNewEdge;
 457   const BooleanOperations_ShapesDataStructure& aDS = theDSFiller.DS();
 458   const BOPTools_PaveFiller&           aPaveFiller = theDSFiller.PaveFiller();
 459 //  BOPTools_DSFiller& aDSFiller = (*((BOPTools_DSFiller*)&theDSFiller));
 460 //  BOPTools_InterferencePool* pIntrPool = (BOPTools_InterferencePool*)&aDSFiller.InterfPool();
 461 //  const BOPTools_CArray1OfEEInterference& aEEs = pIntrPool->EEInterfs();
 462   const BOPTools_PavePool& aPavePool = aPaveFiller.PavePool();
 463
 464   BRep_Builder aBB;
 465   const TopoDS_Shape& aE1 = theBounds->Value(theIndex, 1);
 466   const TopoDS_Shape& aE2 = theBounds->Value(theIndex, 2);
 467
 468   // search common vertex between bounds. begin
 469   TopoDS_Vertex aCommonVertex;
 470   Standard_Integer anIndex1 = aDS.ShapeIndex(aE1, 1);
 471   Standard_Integer anIndex2 = aDS.ShapeIndex(aE2, 2);
 472   Standard_Real apar1 = 0., apar2 = 0.;
 473
 474   Standard_Boolean bvertexfound =
 475     FindCommonVertex(theDSFiller, anIndex1, anIndex2, aCommonVertex, apar1, apar2);
 476   // search common vertex between bounds. end
 477
 478   Handle(BRepTools_ReShape) aSubstitutor = new BRepTools_ReShape();
 479
 480   // search common vertices between uedges. begin
 481   TopTools_ListOfShape aCommonVertices;
 482   Standard_Boolean acommonflag = 0; // 0 - no, 1 - first pair, 2 - second pair, 3 - both
 483   Standard_Integer ueit = 0, eindex = 0;
 484
 485   for(ueit = 1, eindex = theIndex; ueit <= 2; ueit++, eindex++) {
 486     const TopoDS_Shape& aShape1 = theUEdges->Value(eindex, theUEdges->LowerCol());
 487     const TopoDS_Shape& aShape2 = theUEdges->Value(eindex, theUEdges->UpperCol());
 488     TopoDS_Edge aUE1 = TopoDS::Edge(aShape1);
 489     TopoDS_Edge aUE2 = TopoDS::Edge(aShape2);
 490
 491     if(theHistMap.IsBound(aShape1)) {
 492       const TopTools_ListOfShape& lst = theHistMap.Find(aShape1);
 493
 494       if(!lst.IsEmpty())
 495         aUE1 = TopoDS::Edge(lst.First());
 496     }
 497
 498     if(theHistMap.IsBound(aShape2)) {
 499       const TopTools_ListOfShape& lst = theHistMap.Find(aShape2);
 500
 501       if(!lst.IsEmpty())
 502         aUE2 = TopoDS::Edge(lst.First());
 503     }
 504
 505     if(!aShape1.IsSame(aUE1))
 506       aSubstitutor->Replace(aShape1.Oriented(TopAbs_FORWARD), aUE1.Oriented(TopAbs_FORWARD));
 507
 508     if(!aShape2.IsSame(aUE2))
 509       aSubstitutor->Replace(aShape2.Oriented(TopAbs_FORWARD), aUE2.Oriented(TopAbs_FORWARD));
 510
 511     TopoDS_Vertex V1 = TopExp::LastVertex(aUE1);
 512     TopoDS_Vertex V2 = TopExp::FirstVertex(aUE2);
 513
 514     if(V1.IsSame(V2)) {
 515       acommonflag = (acommonflag == 0) ? ueit : 3;
 516       aCommonVertices.Append(V1);
 517     }
 518   }
 519   // search common vertices between uedges. end
 520
 521   if(bvertexfound) {
 522     if(aCommonVertices.Extent() != 1)
 523       return Standard_False;
 524
 525     if(acommonflag == 1)
 526       aNewEdge = BRepLib_MakeEdge(TopoDS::Vertex(aCommonVertices.First()), aCommonVertex);
 527     else
 528       aNewEdge = BRepLib_MakeEdge(aCommonVertex, TopoDS::Vertex(aCommonVertices.First()));
 529
 530     bHasNewEdge = Standard_True;
 531   }
 532
 533   if(aCommonVertices.Extent() == 2) {
 534     aNewEdge = BRepLib_MakeEdge(TopoDS::Vertex(aCommonVertices.First()),
 535                                 TopoDS::Vertex(aCommonVertices.Last()));
 536     bHasNewEdge = Standard_True;
 537   }
 538   Standard_Integer fit = 0;
 539
 540   for(fit = 1; fit <= 2; fit++) {
 541     TopoDS_Compound aComp;
 542     TopTools_MapOfShape aMapV;
 543     aBB.MakeCompound(aComp);
 544
 545     for(ueit = 1, eindex = theIndex; ueit <= 2; ueit++, eindex++) {
 546       const TopoDS_Shape& aShape = theUEdges->Value(eindex, theUEdges->LowerCol() + fit - 1);
 547       TopoDS_Shape aUE = aShape;
 548
 549       if(theHistMap.IsBound(aShape)) {
 550         const TopTools_ListOfShape& lst = theHistMap.Find(aShape);
 551
 552         if(!lst.IsEmpty())
 553           aUE = TopoDS::Edge(lst.First());
 554       }
 555       const TopoDS_Shape& aV = (fit == 1) ? TopExp::FirstVertex(TopoDS::Edge(aUE)) : TopExp::LastVertex(TopoDS::Edge(aUE));
 556       aMapV.Add(aV);
 557       aBB.Add(aComp, aUE);
 558     }
 559     if(bHasNewEdge) {
 560       aBB.Add(aComp, aNewEdge);
 561     }
 562     TopTools_ListOfShape alonevertices;
 563     FindFreeVertices(aComp, aMapV, alonevertices);
 564
 565     if(!alonevertices.IsEmpty() && (alonevertices.Extent() != 2))
 566       return Standard_False;
 567
 568     Standard_Integer aFaceIndex = (fit == 1) ? theFaceIndex1 : theFaceIndex2;
 569     TopoDS_Shape aFace          = aDS.Shape(aFaceIndex);
 570     TopAbs_Orientation aFaceOri = aFace.Orientation();
 571     TopAbs_Orientation anEdgeOri = TopAbs_FORWARD;
 572     aFace.Orientation(TopAbs_FORWARD);
 573
 574     TopExp_Explorer anExpE(aFace, TopAbs_EDGE);
 575     const TopoDS_Shape& aCheckEdge = (fit == 1) ? aE1 : aE2;
 576
 577     for(; anExpE.More(); anExpE.Next()) {
 578       if(aCheckEdge.IsSame(anExpE.Current()))
 579         anEdgeOri = anExpE.Current().Orientation();
 580     }
 581
 582     if(bHasNewEdge) {
 583       aNewEdge.Orientation(TopAbs_FORWARD);
 584     }
 585
 586     TopTools_ListOfShape aOrderedList;
 587
 588     if(!alonevertices.IsEmpty()) {
 589       Standard_Integer anEIndex = (fit == 1) ? anIndex1 : anIndex2;
 590       const BOPTools_PaveSet& aPaveSet = aPavePool(aDS.RefEdge(anEIndex));
 591       BOPTools_ListIteratorOfListOfPave anPIt(aPaveSet.Set());
 592       Standard_Boolean bfound1 = Standard_False;
 593       Standard_Boolean bfound2 = Standard_False;
 594       Standard_Real aparam1 = 0., aparam2 = 0.;
 595
 596       for(; anPIt.More(); anPIt.Next()) {
 597         const BOPTools_Pave& aPave = anPIt.Value();
 598         TopoDS_Shape aV = aDS.Shape(aPave.Index());
 599
 600         if(aV.IsSame(alonevertices.First())) {
 601           if(!bfound1) {
 602             aparam1 = aPave.Param();
 603             bfound1 = Standard_True;
 604           }
 605         }
 606
 607         if(aV.IsSame(alonevertices.Last())) {
 608           if(!bfound2) {
 609             aparam2 = aPave.Param();
 610             bfound2 = Standard_True;
 611           }
 612         }
 613       }
 614
 615       if(bfound1 && bfound2) {
 616         TopoDS_Edge aNewBoundE;
 617
 618         if(fit == 1) {
 619           aNewBoundE = TopoDS::Edge(aE1.EmptyCopied());
 620         }
 621         else {
 622           aNewBoundE = TopoDS::Edge(aE2.EmptyCopied());
 623         }
 624         TopoDS_Vertex aV1, aV2;
 625
 626         if(aparam1 < aparam2) {
 627           aV1 = TopoDS::Vertex(alonevertices.First());
 628           aV2 = TopoDS::Vertex(alonevertices.Last());
 629         }
 630         else {
 631           aV1 = TopoDS::Vertex(alonevertices.Last());
 632           aV2 = TopoDS::Vertex(alonevertices.First());
 633           Standard_Real tmp = aparam1;
 634           aparam1 = aparam2;
 635           aparam2 = tmp;
 636         }
 637         aV1.Orientation(TopAbs_FORWARD);
 638         aV2.Orientation(TopAbs_REVERSED);
 639         aBB.Add(aNewBoundE, aV1);
 640         aBB.Add(aNewBoundE, aV2);
 641         aBB.Range(aNewBoundE, aparam1, aparam2);
 642         aNewBoundE.Orientation(TopAbs_FORWARD);
 643
 644         aOrderedList.Append(aNewBoundE);
 645
 646         if(bHasNewEdge) {
 647           TopExp_Explorer anExpV(aNewEdge, TopAbs_VERTEX);
 648           Standard_Boolean bfoundv = Standard_False;
 649
 650           for(; !bfoundv && anExpV.More(); anExpV.Next()) {
 651             if(aV2.IsSame(anExpV.Current()))
 652               bfoundv = Standard_True;
 653           }
 654
 655           if(bfoundv)
 656             aOrderedList.Append(aNewEdge);
 657           else
 658             aOrderedList.Prepend(aNewEdge);
 659         }
 660       }
 661       else {
 662         return Standard_False;
 663       }
 664     }
 665     else {
 666       if(bHasNewEdge) {
 667         aOrderedList.Append(aNewEdge);
 668       }
 669     }
 670
 671     if(!aOrderedList.IsEmpty()) {
 672       TopoDS_Wire aW;
 673       aBB.MakeWire(aW);
 674       TopTools_ListIteratorOfListOfShape anItE(aOrderedList);
 675
 676       for(; anItE.More(); anItE.Next()) {
 677         aBB.Add(aW, anItE.Value());
 678       }
 679       if(fit == 1)
 680         aSubstitutor->Replace(aE1.Oriented(TopAbs_FORWARD), aW);
 681       else
 682         aSubstitutor->Replace(aE2.Oriented(TopAbs_FORWARD), aW);
 683     }
 684
 685     aSubstitutor->Apply(aFace);
 686     TopoDS_Shape aNewFace = aSubstitutor->Value(aFace);
 687     aNewFace.Orientation(aFaceOri);
 688     TopTools_ListOfShape atmpList;
 689     atmpList.Append(aNewFace);
 690     theHistMap.Bind(aFace, atmpList);
 691
 692     anExpE.Init(aFace, TopAbs_EDGE);
 693
 694     for(; anExpE.More(); anExpE.Next()) {
 695       TopoDS_Shape aNewValue = aSubstitutor->Value(anExpE.Current());
 696
 697       if(aNewValue.IsNull() || aNewValue.IsSame(anExpE.Current()))
 698         continue;
 699
 700       if(theHistMap.IsBound(anExpE.Current()))
 701         continue;
 702       TopTools_ListOfShape aListOfNewEdge;
 703       TopExp_Explorer anExpE2(aNewValue, TopAbs_EDGE);
 704
 705       for(; anExpE2.More(); anExpE2.Next()) {
 706         aListOfNewEdge.Append(anExpE2.Current());
 707       }
 708       theHistMap.Bind(anExpE.Current(), aListOfNewEdge);
 709     }
 710   }
 711
 712   return Standard_True;
 713 }
 714
 715 // ----------------------------------------------------------------------------------------------------
 716 // static function: MakeFacesSec
 717 // purpose:
 718 // ----------------------------------------------------------------------------------------------------
 719 Standard_Boolean MakeFacesSec(const Standard_Integer                     theIndex,
 720                               const Handle(TopTools_HArray2OfShape)&     theUEdges,
 721                               const Handle(TopTools_HArray2OfShape)&     theBounds,
 722                               const BOPTools_DSFiller&                   theDSFiller,
 723                               const Standard_Integer                     theFaceIndex1,
 724                               const Standard_Integer                     theFaceIndex2,
 725                               const Standard_Integer                     theSSInterfIndex,
 726                               const gp_Ax2&                              AxeOfBisPlane,
 727                               TopTools_DataMapOfShapeListOfShape&        theHistMap)
 728 {
 729   const BooleanOperations_ShapesDataStructure& aDS = theDSFiller.DS();
 730 //  const BOPTools_PaveFiller&           aPaveFiller = theDSFiller.PaveFiller();
 731   BOPTools_DSFiller& aDSFiller = (*((BOPTools_DSFiller*)&theDSFiller));
 732   BOPTools_InterferencePool* pIntrPool = (BOPTools_InterferencePool*)&aDSFiller.InterfPool();
 733   BOPTools_CArray1OfSSInterference& aFFs = pIntrPool->SSInterferences();
 734 //  const BOPTools_PavePool& aPavePool               = aPaveFiller.PavePool();
 735 //  const BOPTools_SplitShapesPool& aSplitShapesPool = aPaveFiller.SplitShapesPool();
 736
 737   TopoDS_Compound aSecEdges;
 738   BOPTools_SSInterference& aFFi = aFFs(theSSInterfIndex);
 739   BOPTools_SequenceOfCurves& aBCurves = aFFi.Curves();
 740   TopoDS_Face aSecPlane;
 741
 742   if(!FilterSectionEdges(aBCurves, aSecPlane, theDSFiller, aSecEdges))
 743     return Standard_False;
 744
 745   TopoDS_Shape SecWire;
 746   gp_Pln SecPlane;
 747   Standard_Boolean IsSingular;
 748   Standard_Boolean WireFound = ChooseSection( aSecEdges, AxeOfBisPlane, SecWire, SecPlane, IsSingular );
 749
 750   if(WireFound) {
 751     //aSecEdges = SecWire;
 752     TopoDS_Compound aComp;
 753     BRep_Builder BB;
 754     BB.MakeCompound(aComp);
 755     TopExp_Explorer explo( SecWire, TopAbs_EDGE );
 756
 757     for (; explo.More(); explo.Next())
 758       BB.Add( aComp, explo.Current() );
 759     aSecEdges = aComp;
 760   }
 761
 762   TopTools_ListOfShape aCommonVertices;
 763 //  Standard_Boolean acommonflag = 0; // 0 - no, 1 - first pair, 2 - second pair, 3 - both
 764   Standard_Integer fit = 0; //, ueit = 0, eindex = 0, i = 0;
 765   Handle(BRepTools_ReShape) aSubstitutor = new BRepTools_ReShape();
 766
 767   for(fit = 1; fit <= 2; fit++) {
 768     Standard_Integer aFaceIndex = (fit == 1) ? theFaceIndex1 : theFaceIndex2;
 769     TopoDS_Face aFace = TopoDS::Face(aDS.Shape(aFaceIndex));
 770     TopAbs_Orientation aFaceOri = aFace.Orientation();
 771     TopoDS_Face aFaceF = aFace;
 772     aFaceF.Orientation(TopAbs_FORWARD);
 773     TopoDS_Edge aBoundEdge = TopoDS::Edge(theBounds->Value(theIndex, theBounds->LowerCol() + fit - 1));
 774     Standard_Integer aBoundEdgeIndex = aDS.ShapeIndex(aBoundEdge, fit);
 775     TopoDS_Edge aUE1;
 776     TopoDS_Edge aUE2;
 777
 778     if(!GetUEdges(theIndex, fit, theUEdges, aBoundEdge, aFaceF, aUE1, aUE2))
 779       return Standard_False;
 780
 781     TopoDS_Edge aUE1old = aUE1;
 782     TopoDS_Edge aUE2old = aUE2;
 783
 784     if(theHistMap.IsBound(aUE1)) {
 785       const TopTools_ListOfShape& lst = theHistMap.Find(aUE1);
 786
 787       if(!lst.IsEmpty()) {
 788         const TopoDS_Shape& anEdge = lst.First().Oriented(aUE1.Orientation());
 789
 790         if(!aUE1.IsSame(anEdge))
 791           aSubstitutor->Replace(aUE1.Oriented(TopAbs_FORWARD), anEdge.Oriented(TopAbs_FORWARD));
 792         aUE1 = TopoDS::Edge(anEdge);
 793       }
 794     }
 795
 796     if(theHistMap.IsBound(aUE2)) {
 797       const TopTools_ListOfShape& lst = theHistMap.Find(aUE2);
 798
 799       if(!lst.IsEmpty()) {
 800         const TopoDS_Shape& anEdge = lst.First().Oriented(aUE2.Orientation());
 801
 802         if(!aUE2.IsSame(anEdge))
 803           aSubstitutor->Replace(aUE2.Oriented(TopAbs_FORWARD), anEdge.Oriented(TopAbs_FORWARD));
 804         aUE2 = TopoDS::Edge(anEdge);
 805       }
 806     }
 807     TopoDS_Vertex aPrevVertex, aNextVertex;
 808     TopoDS_Compound aCompOfSecEdges = aSecEdges;
 809     TopTools_ListOfShape aListOfWireEdges;
 810     BRep_Builder aBB;
 811     BOPTools_Pave aPave1;
 812     Standard_Boolean isPave1OnUEdge = Standard_True;
 813
 814     if(FindFromUEdge(aUE1old, aUE2old, aUE1, aUE2, aFace, aSecEdges, fit, aBoundEdge, aBoundEdgeIndex,
 815                      theDSFiller, theHistMap, aCompOfSecEdges, aListOfWireEdges, aPave1, isPave1OnUEdge)) {
 816       TopTools_ListOfShape aSecondListOfEdges;
 817       Standard_Boolean bisSectionFound = Standard_False;
 818
 819       if(!FindFromVEdge(aPave1, isPave1OnUEdge, aUE1old, aUE2old, aFace, aCompOfSecEdges, fit, aBoundEdge,
 820                         aBoundEdgeIndex, theDSFiller, theHistMap, aSecondListOfEdges, bisSectionFound)) {
 821         return Standard_False;
 822       }
 823
 824       if(!bisSectionFound && aListOfWireEdges.IsEmpty()) {
 825         return Standard_False;
 826       }
 827       aListOfWireEdges.Append(aSecondListOfEdges);
 828     }
 829     else {
 830       return Standard_False;
 831     }
 832
 833     if(!aListOfWireEdges.IsEmpty()) {
 834       TopoDS_Wire aW;
 835       aBB.MakeWire(aW);
 836       TopTools_ListIteratorOfListOfShape aEIt(aListOfWireEdges);
 837
 838       for(; aEIt.More(); aEIt.Next()) {
 839         if(!aBoundEdge.IsSame(aEIt.Value()))
 840           aBB.Add(aW, aEIt.Value());
 841       }
 842       aSubstitutor->Replace(aBoundEdge.Oriented(TopAbs_FORWARD), aW);
 843     }
 844
 845     aSubstitutor->Apply(aFace);
 846     TopoDS_Shape aNewFace = aSubstitutor->Value(aFace);
 847     aNewFace.Orientation(aFaceOri);
 848     TopTools_ListOfShape atmpList;
 849     atmpList.Append(aNewFace);
 850     theHistMap.Bind(aFace, atmpList);
 851
 852     TopExp_Explorer anExpE(aFace, TopAbs_EDGE);
 853
 854     for(; anExpE.More(); anExpE.Next()) {
 855       TopoDS_Shape aNewValue = aSubstitutor->Value(anExpE.Current());
 856
 857       if(aNewValue.IsNull() || aNewValue.IsSame(anExpE.Current()))
 858         continue;
 859
 860       if(theHistMap.IsBound(anExpE.Current()))
 861         continue;
 862       TopTools_ListOfShape aListOfNewEdge;
 863       TopExp_Explorer anExpE2(aNewValue, TopAbs_EDGE);
 864
 865       for(; anExpE2.More(); anExpE2.Next()) {
 866         aListOfNewEdge.Append(anExpE2.Current());
 867       }
 868       theHistMap.Bind(anExpE.Current(), aListOfNewEdge);
 869     }
 870   }
 871   return Standard_True;
 872 }
 873
 874
 875 // ------------------------------------------------------------------------------------------
 876 // static function: SplitUEdges
 877 // purpose:
 878 // ------------------------------------------------------------------------------------------
 879 Standard_Boolean SplitUEdges(const Handle(TopTools_HArray2OfShape)&     theUEdges,
 880                              const BOPTools_DSFiller&                   theDSFiller,
 881                              TopTools_DataMapOfShapeListOfShape&        theHistMap) {
 882
 883   const BooleanOperations_ShapesDataStructure& aDS = theDSFiller.DS();
 884 //  const BOPTools_PaveFiller&           aPaveFiller = theDSFiller.PaveFiller();
 885 //  const BOPTools_SplitShapesPool& aSplitShapesPool = aPaveFiller.SplitShapesPool();
 886   BOPTools_DSFiller& aDSFiller = (*((BOPTools_DSFiller*)&theDSFiller));
 887   BOPTools_InterferencePool* pIntrPool = (BOPTools_InterferencePool*)&aDSFiller.InterfPool();
 888   //   const BOPTools_CommonBlockPool& aCBPool = aPaveFiller.CommonBlockPool();
 889 //  const BOPTools_PavePool& aPavePool = aPaveFiller.PavePool();
 890 //   const BOPTools_CArray1OfEEInterference& aEEs = pIntrPool->EEInterfs();
 891   const BOPTools_CArray1OfVEInterference& aVEs = pIntrPool->VEInterferences();
 892   const BOPTools_CArray1OfVVInterference& aVVs = pIntrPool->VVInterferences();
 893
 894   BRep_Builder aBB;
 895   Standard_Integer ueit = 0;
 896   TopTools_Array2OfShape aNewVertices(1,2,1,2);
 897
 898   for(ueit = theUEdges->LowerRow(); ueit <= theUEdges->UpperRow(); ueit++) {
 899     const TopoDS_Shape& aE1 = theUEdges->Value(ueit, theUEdges->LowerCol());
 900     const TopoDS_Shape& aE2 = theUEdges->Value(ueit, theUEdges->UpperCol());
 901
 902     if(theHistMap.IsBound(aE1) || theHistMap.IsBound(aE2))
 903       continue;
 904
 905     Standard_Integer anEIndex1 = aDS.ShapeIndex(aE1, 1);
 906     Standard_Integer anEIndex2 = aDS.ShapeIndex(aE2, 2);
 907
 908     TopoDS_Vertex aCommonVertex;
 909     Standard_Real apar1 = 0., apar2 = 0.;
 910     Standard_Boolean bvertexfound =
 911       FindCommonVertex(theDSFiller, anEIndex1, anEIndex2, aCommonVertex, apar1, apar2);
 912
 913     if(!bvertexfound) {
 914       Standard_Integer j = 0;
 915       for(j = 0; j < 2; j++) {
 916         Standard_Integer veit = 0;
 917
 918         for(veit = 1; veit <= aVEs.Extent(); veit++) {
 919
 920         }
 921       }
 922     }
 923
 924     if(!bvertexfound) {
 925       TopoDS_Vertex V1 = TopExp::LastVertex(TopoDS::Edge(aE1));
 926       TopoDS_Vertex V2 = TopExp::FirstVertex(TopoDS::Edge(aE2));
 927       Standard_Integer vindex1 = aDS.ShapeIndex(V1, 1);
 928       Standard_Integer vindex2 = aDS.ShapeIndex(V2, 2);
 929       Standard_Integer vvit = 0;
 930
 931       for(vvit = 1; !bvertexfound && (vvit <= aVVs.Extent()); vvit++) {
 932         const BOPTools_VVInterference& aVV = aVVs(vvit);
 933
 934         if(((vindex1 == aVV.Index1()) && (vindex2 = aVV.Index2())) ||
 935            ((vindex1 == aVV.Index2()) && (vindex2 = aVV.Index1()))) {
 936
 937           if(aVV.NewShape() == 0) {
 938             continue;
 939           }
 940           aCommonVertex = TopoDS::Vertex(aDS.Shape(aVV.NewShape()));
 941           bvertexfound = Standard_True;
 942           apar1 = BRep_Tool::Parameter(V1, TopoDS::Edge(aE1));
 943           apar2 = BRep_Tool::Parameter(V2, TopoDS::Edge(aE2));
 944         }
 945       }
 946     }
 947
 948     if(bvertexfound) {
 949       TopoDS_Vertex aV1, aV2;
 950       Standard_Real f = 0., l = 0.;
 951       //
 952       TopoDS_Edge aNewE1 = TopoDS::Edge(aE1.EmptyCopied());
 953       TopExp::Vertices(TopoDS::Edge(aE1), aV1, aV2);
 954       aNewE1.Orientation(TopAbs_FORWARD);
 955       aV1.Orientation(TopAbs_FORWARD);
 956       aBB.Add(aNewE1, aV1);
 957       aCommonVertex.Orientation(TopAbs_REVERSED);
 958       aBB.Add(aNewE1, aCommonVertex);
 959       BRep_Tool::Range(TopoDS::Edge(aE1), f, l);
 960       aBB.Range(aNewE1, f, apar1);
 961
 962       //
 963       TopoDS_Edge aNewE2 = TopoDS::Edge(aE2.EmptyCopied());
 964       TopExp::Vertices(TopoDS::Edge(aE2), aV1, aV2);
 965       aNewE2.Orientation(TopAbs_FORWARD);
 966       aCommonVertex.Orientation(TopAbs_FORWARD);
 967       aBB.Add(aNewE2, aCommonVertex);
 968       aBB.Add(aNewE2, aV2);
 969       BRep_Tool::Range(TopoDS::Edge(aE2), f, l);
 970       aBB.Range(aNewE2, apar2, l);
 971
 972       TopTools_ListOfShape lst;
 973       lst.Append(aNewE1);
 974       theHistMap.Bind(aE1, lst);
 975       lst.Clear();
 976       lst.Append(aNewE2);
 977       theHistMap.Bind(aE2, lst);
 978     }
 979   }
 980   return Standard_True;
 981 }
 982
 983 // ------------------------------------------------------------------------------------------
 984 // static function: FindFreeVertices
 985 // purpose:
 986 // ------------------------------------------------------------------------------------------
 987 void FindFreeVertices(const TopoDS_Shape&         theShape,
 988                       const TopTools_MapOfShape&  theVerticesToAvoid,
 989                       TopTools_ListOfShape&       theListOfVertex) {
 990
 991   theListOfVertex.Clear();
 992   TopTools_IndexedDataMapOfShapeListOfShape aMap;
 993   TopExp::MapShapesAndAncestors(theShape, TopAbs_VERTEX, TopAbs_EDGE, aMap);
 994   Standard_Integer i = 0;
 995
 996   for(i = 1; i <= aMap.Extent(); i++) {
 997     const TopoDS_Shape& aKey = aMap.FindKey(i);
 998
 999     if(theVerticesToAvoid.Contains(aKey))
1000       continue;
1001     const TopTools_ListOfShape& aList = aMap.FindFromIndex(i);
1002
1003     if(aList.Extent() < 2) {
1004       theListOfVertex.Append(aKey);
1005     }
1006   }
1007 }
1008
1009 // ------------------------------------------------------------------------------------------
1010 // static function: FindParameter
1011 // purpose:
1012 // ------------------------------------------------------------------------------------------
1013 Standard_Boolean FindParameter(const BOPTools_PaveSet&                     thePaveSet,
1014                                const BooleanOperations_KindOfInterference& theType,
1015                                const Standard_Integer                      theInterfIndex,
1016                                Standard_Real&                              theParam) {
1017   BOPTools_ListIteratorOfListOfPave anPIt(thePaveSet.Set());
1018   Standard_Boolean bfound = Standard_False;
1019
1020   for(; anPIt.More(); anPIt.Next()) {
1021     const BOPTools_Pave& aPave = anPIt.Value();
1022
1023     if((aPave.Type() == theType) &&
1024        (aPave.Interference() == theInterfIndex)) {
1025       theParam = aPave.Param();
1026       bfound = Standard_True;
1027       break;
1028     }
1029   }
1030   return bfound;
1031 }
1032
1033 // ------------------------------------------------------------------------------------------
1034 // static function: FindCommonVertex
1035 // purpose:
1036 // ------------------------------------------------------------------------------------------
1037 Standard_Boolean FindCommonVertex(const BOPTools_DSFiller& theDSFiller,
1038                                   const Standard_Integer   theEIndex1,
1039                                   const Standard_Integer   theEIndex2,
1040                                   TopoDS_Vertex&           theCommonVertex,
1041                                   Standard_Real&           theParamOnE1,
1042                                   Standard_Real&           theParamOnE2) {
1043
1044   const BooleanOperations_ShapesDataStructure& aDS = theDSFiller.DS();
1045   const BOPTools_PaveFiller&           aPaveFiller = theDSFiller.PaveFiller();
1046   const BOPTools_PavePool& aPavePool = aPaveFiller.PavePool();
1047   BOPTools_DSFiller& aDSFiller = (*((BOPTools_DSFiller*)&theDSFiller));
1048   BOPTools_InterferencePool* pIntrPool = (BOPTools_InterferencePool*)&aDSFiller.InterfPool();
1049   const BOPTools_CArray1OfEEInterference& aEEs = pIntrPool->EEInterfs();
1050
1051   Standard_Boolean bvertexfound = Standard_False;
1052   TopoDS_Vertex aCommonVertex;
1053   Standard_Integer eeit = 0;
1054
1055   for(eeit = 1; eeit <= aEEs.Extent(); eeit++) {
1056     const BOPTools_EEInterference& aEE = aEEs(eeit);
1057
1058     if((theEIndex1 == aEE.Index1() && theEIndex2 == aEE.Index2()) ||
1059        (theEIndex1 == aEE.Index2() && theEIndex2 == aEE.Index1())) {
1060
1061       if(aEE.NewShape() == 0)
1062         continue;
1063
1064       if(aDS.GetShapeType(aEE.NewShape()) == TopAbs_VERTEX) {
1065         theCommonVertex = TopoDS::Vertex(aDS.Shape(aEE.NewShape()));
1066
1067         bvertexfound = Standard_True;
1068         Standard_Integer i = 0;
1069
1070         for(i = 0; i < 2; i++) {
1071           Standard_Integer anEIndex = (i == 0) ? theEIndex1 : theEIndex2;
1072           const BOPTools_PaveSet& aPaveSet = aPavePool(aDS.RefEdge(anEIndex));
1073           Standard_Boolean bfound = Standard_False;
1074
1075           if(i == 0)
1076             bfound = FindParameter(aPaveSet, BooleanOperations_EdgeEdge, eeit, theParamOnE1);
1077           else
1078             bfound = FindParameter(aPaveSet, BooleanOperations_EdgeEdge, eeit, theParamOnE2);
1079
1080           if(!bfound) {
1081             bvertexfound = Standard_False;
1082             break;
1083           }
1084         }
1085       }
1086       else if(aDS.GetShapeType(aEE.NewShape()) == TopAbs_EDGE) {
1087
1088       }
1089     }
1090   }
1091   return bvertexfound;
1092 }
1093
1094 // ------------------------------------------------------------------------------------------
1095 // static function: IsFromFirstToSecond
1096 // purpose:
1097 // ------------------------------------------------------------------------------------------
1098 Standard_Boolean IsFromFirstToSecond(const TopoDS_Edge&   theEdge,
1099                                      const Standard_Real  theParameterOnUEdge,
1100                                      const TopoDS_Edge&   theUEdge1,
1101                                      const TopoDS_Edge&   theUEdge2,
1102                                      const TopoDS_Face&   theFace) {
1103   TopoDS_Face aFace = theFace;
1104   aFace.Orientation(TopAbs_FORWARD);
1105   TopoDS_Edge E1, E2;
1106   TopExp_Explorer anExp(aFace, TopAbs_EDGE);
1107
1108   for(; anExp.More(); anExp.Next()) {
1109     if(E1.IsNull() && theUEdge1.IsSame(anExp.Current())) {
1110       E1 = TopoDS::Edge(anExp.Current());
1111     }
1112     else if(E2.IsNull() && theUEdge2.IsSame(anExp.Current())) {
1113       E2 = TopoDS::Edge(anExp.Current());
1114     }
1115   }
1116
1117   if(E1.IsNull() || E2.IsNull())
1118     return Standard_True;
1119
1120   gp_Pnt2d PU1, PU2, pf, pl;
1121   Standard_Real f, l;
1122   Handle(Geom2d_Curve) C1 = BRep_Tool::CurveOnSurface(E1, aFace, f, l);
1123   Handle(Geom2d_Curve) C2 = BRep_Tool::CurveOnSurface(E2, aFace, f, l);
1124   Handle(Geom2d_Curve) CC = BRep_Tool::CurveOnSurface(theEdge, aFace, f, l);
1125   PU1 = C1->Value(theParameterOnUEdge);
1126   PU2 = C2->Value(theParameterOnUEdge);
1127   BRep_Tool::Range(theEdge, f, l);
1128   pf = CC->Value(f);
1129   pl = CC->Value(l);
1130   Standard_Real aTolerance = Precision::Confusion();
1131
1132   if(pf.Distance(PU1) < aTolerance)
1133     return Standard_True;
1134
1135   if(pl.Distance(PU2) < aTolerance)
1136     return Standard_True;
1137
1138   return Standard_False;
1139 }
1140
1141 // ----------------------------------------------------------------------------------------------------
1142 // static function: GetUEdges
1143 // purpose:
1144 // ----------------------------------------------------------------------------------------------------
1145 Standard_Boolean GetUEdges(const Standard_Integer                     theIndex,
1146                            const Standard_Integer                     theRank,
1147                            const Handle(TopTools_HArray2OfShape)&     theUEdges,
1148                            const TopoDS_Edge&                         theBoundEdge,
1149                            const TopoDS_Face&                         theFace,
1150                            TopoDS_Edge&                               theFirstUEdge,
1151                            TopoDS_Edge&                               theSecondUEdge) {
1152   const TopoDS_Shape& aUE1 = theUEdges->Value(theIndex, theUEdges->LowerCol() + theRank - 1);
1153   const TopoDS_Shape& aUE2 = theUEdges->Value(theIndex + 1, theUEdges->LowerCol() + theRank - 1);
1154
1155   TopoDS_Face aFace = theFace;
1156   aFace.Orientation(TopAbs_FORWARD);
1157   TopoDS_Edge E1, E2;
1158   TopExp_Explorer anExp(aFace, TopAbs_EDGE);
1159
1160   for(; anExp.More(); anExp.Next()) {
1161     if(E1.IsNull() && aUE1.IsSame(anExp.Current())) {
1162       E1 = TopoDS::Edge(anExp.Current());
1163     }
1164     else if(E2.IsNull() && aUE2.IsSame(anExp.Current())) {
1165       E2 = TopoDS::Edge(anExp.Current());
1166     }
1167   }
1168
1169   if(E1.IsNull() || E2.IsNull())
1170     return Standard_False;
1171
1172   Standard_Real f, l;
1173   Handle(Geom2d_Curve) C1 = BRep_Tool::CurveOnSurface(E1, aFace, f, l);
1174
1175   if(C1.IsNull())
1176      return Standard_False;
1177   gp_Pnt2d PU1 = (theRank == 1) ? C1->Value(l) : C1->Value(f);
1178   Handle(Geom2d_Curve) C2 = BRep_Tool::CurveOnSurface(theBoundEdge, aFace, f, l);
1179
1180   if(C2.IsNull())
1181     return Standard_False;
1182   BRep_Tool::Range(theBoundEdge, f, l);
1183   gp_Pnt2d pf = C2->Value(f);
1184   TopoDS_Vertex aV = (theRank == 1) ? TopExp::LastVertex(E1) : TopExp::FirstVertex(E1);
1185   Standard_Real aTolerance = BRep_Tool::Tolerance(aV);
1186   BRepAdaptor_Surface aBAS(aFace, Standard_False);
1187
1188   if(pf.Distance(PU1) > aBAS.UResolution(aTolerance)) {
1189     TopoDS_Edge atmpE = E1;
1190     E1 = E2;
1191     E2 = atmpE;
1192   }
1193   theFirstUEdge = E1;
1194   theSecondUEdge = E2;
1195   return Standard_True;
1196 }
1197
1198 // ----------------------------------------------------------------------------------------------------
1199 // static function: FillGap
1200 // purpose:
1201 // ----------------------------------------------------------------------------------------------------
1202 Standard_Boolean FillGap(const TopoDS_Vertex&   theFirstVertex,
1203                          const TopoDS_Vertex&   theLastVertex,
1204                          const gp_Pnt2d&        theFirstPoint,
1205                          const gp_Pnt2d&        theLastPoint,
1206                          const TopoDS_Face&     theFace,
1207                          const TopoDS_Compound& theSectionEdges,
1208                          TopTools_ListOfShape&  theOrderedList) {
1209
1210   TopTools_IndexedDataMapOfShapeListOfShape aMap;
1211   TopExp::MapShapesAndAncestors(theSectionEdges, TopAbs_VERTEX, TopAbs_EDGE, aMap);
1212
1213   if(aMap.IsEmpty()) {
1214     return Standard_False;
1215   }
1216
1217   if(!aMap.Contains(theFirstVertex) ||
1218      !aMap.Contains(theLastVertex)) {
1219     return Standard_False;
1220   }
1221   TopTools_ListOfShape aListOfEdge;
1222 //  Standard_Integer i = 0;
1223 //  TopoDS_Vertex aCurVertex = theFirstVertex;
1224   TopTools_MapOfShape aMapToAvoid;
1225
1226   if(FindNextEdge(theFirstVertex, theLastVertex, aMap, aMapToAvoid, aListOfEdge)) {
1227     if(!aListOfEdge.IsEmpty()) {
1228       return CheckAndOrientEdges(aListOfEdge, theFirstPoint, theLastPoint, theFace, theOrderedList);
1229     }
1230   }
1231   return Standard_False;
1232 }
1233
1234 // ----------------------------------------------------------------------------------------------------
1235 // static function: FindNextEdge
1236 // purpose:
1237 // ----------------------------------------------------------------------------------------------------
1238 Standard_Boolean FindNextEdge(const TopoDS_Vertex&   theFirstVertex,
1239                               const TopoDS_Vertex&   theLastVertex,
1240                               const TopTools_IndexedDataMapOfShapeListOfShape& theMapVE,
1241                               const TopTools_MapOfShape& theMapToAvoid,
1242                               TopTools_ListOfShape&  theOrderedList) {
1243   TopoDS_Vertex aCurVertex = theFirstVertex;
1244   TopTools_MapOfShape aMapToAvoid;
1245   aMapToAvoid = theMapToAvoid;
1246   TopTools_ListOfShape aListOfEdge;
1247   Standard_Integer i = 0;
1248
1249   for(i = 1; i <= theMapVE.Extent(); i++) {
1250     if(!theMapVE.Contains(aCurVertex))
1251       break;
1252     const TopTools_ListOfShape& lste = theMapVE.FindFromKey(aCurVertex);
1253     Standard_Boolean befound = Standard_False;
1254
1255     TopTools_ListIteratorOfListOfShape anIt(lste);
1256
1257     for(; anIt.More(); anIt.Next()) {
1258       TopoDS_Shape anEdge = anIt.Value();
1259       TopoDS_Vertex aSaveCurVertex = aCurVertex;
1260
1261       if(!aMapToAvoid.Contains(anEdge)) {
1262         TopoDS_Vertex V1, V2;
1263         TopExp::Vertices(TopoDS::Edge(anEdge), V1, V2);
1264
1265         if(!aCurVertex.IsSame(V1)) {
1266           aCurVertex = V1;
1267         }
1268         else if(!aCurVertex.IsSame(V2)) {
1269           aCurVertex = V2;
1270         }
1271         aMapToAvoid.Add(anEdge);
1272         befound = Standard_True;
1273         aListOfEdge.Append(anEdge);
1274
1275         if(!aCurVertex.IsSame(theLastVertex)) {
1276           TopTools_ListOfShape aListtmp;
1277
1278           if(!FindNextEdge(aCurVertex, theLastVertex, theMapVE, aMapToAvoid, aListtmp)) {
1279             aListOfEdge.Clear();
1280             aCurVertex = aSaveCurVertex;
1281             continue;
1282           }
1283           else {
1284             aListOfEdge.Append(aListtmp);
1285             theOrderedList.Append(aListOfEdge);
1286             return Standard_True;
1287           }
1288         }
1289         break;
1290       }
1291     }
1292
1293     if(aCurVertex.IsSame(theLastVertex))
1294       break;
1295
1296     if(!befound) {
1297       return Standard_False;
1298     }
1299   }
1300
1301   if(aCurVertex.IsSame(theLastVertex)) {
1302     theOrderedList.Append(aListOfEdge);
1303     return Standard_True;
1304   }
1305   return Standard_False;
1306 }
1307
1308 // ----------------------------------------------------------------------------------------------------
1309 // static function: CheckAndOrientEdges
1310 // purpose:
1311 // ----------------------------------------------------------------------------------------------------
1312 Standard_Boolean CheckAndOrientEdges(const TopTools_ListOfShape&  theOrderedList,
1313                                      const gp_Pnt2d&              theFirstPoint,
1314                                      const gp_Pnt2d&              theLastPoint,
1315                                      const TopoDS_Face&           theFace,
1316                                      TopTools_ListOfShape&        theOrientedList) {
1317   TopTools_ListIteratorOfListOfShape anIt(theOrderedList);
1318
1319   if(!anIt.More())
1320     return Standard_True;
1321
1322   Standard_Real f, l;
1323   TopoDS_Edge aEPrev = TopoDS::Edge(anIt.Value());
1324   anIt.Next();
1325
1326   Handle(Geom2d_Curve) aCurve = BRep_Tool::CurveOnSurface(aEPrev, theFace, f, l);
1327   TopoDS_Vertex Vf, Vl;
1328   TopExp::Vertices(aEPrev, Vf, Vl);
1329   BRepAdaptor_Surface aBAS(theFace, Standard_False);
1330
1331   Standard_Real aTolerance1 = (Vf.IsNull()) ? Precision::Confusion() : BRep_Tool::Tolerance(Vf);
1332   Standard_Real aTolerance2 = (Vl.IsNull()) ? Precision::Confusion() : BRep_Tool::Tolerance(Vl);
1333   Standard_Real utol = aBAS.UResolution(aTolerance1);
1334   Standard_Real vtol = aBAS.VResolution(aTolerance1);
1335   aTolerance1 = (utol > vtol) ? utol : vtol;
1336   utol = aBAS.UResolution(aTolerance2);
1337   vtol = aBAS.VResolution(aTolerance2);
1338   aTolerance2 = (utol > vtol) ? utol : vtol;
1339
1340   gp_Pnt2d ap = aCurve->Value(f);
1341   Standard_Boolean bFirstFound = Standard_False;
1342   Standard_Boolean bLastFound = Standard_False;
1343   Standard_Boolean bforward = Standard_True;
1344
1345   if(ap.Distance(theFirstPoint) < aTolerance1) {
1346     bforward = Standard_True;
1347     if(theOrientedList.IsEmpty())
1348       theOrientedList.Append(aEPrev.Oriented(TopAbs_FORWARD));
1349     bFirstFound = Standard_True;
1350   }
1351   else if(ap.Distance(theLastPoint) < aTolerance1) {
1352     bforward = Standard_False;
1353     if(theOrientedList.IsEmpty())
1354       theOrientedList.Append(aEPrev.Oriented(TopAbs_REVERSED));
1355     bLastFound = Standard_True;
1356   }
1357   ap = aCurve->Value(l);
1358
1359   if(ap.Distance(theLastPoint) < aTolerance2) {
1360     bforward = Standard_True;
1361
1362     if(theOrientedList.IsEmpty())
1363       theOrientedList.Append(aEPrev.Oriented(TopAbs_FORWARD));
1364     bLastFound = Standard_True;
1365   }
1366   else if(ap.Distance(theFirstPoint) < aTolerance2) {
1367     bforward = Standard_False;
1368
1369     if(theOrientedList.IsEmpty())
1370       theOrientedList.Append(aEPrev.Oriented(TopAbs_REVERSED));
1371     bFirstFound = Standard_True;
1372   }
1373
1374   for(; anIt.More(); anIt.Next()) {
1375     const TopoDS_Edge& aE = TopoDS::Edge(anIt.Value());
1376     TopoDS_Vertex aV11, aV12;
1377     TopExp::Vertices(aEPrev, aV11, aV12);
1378     TopoDS_Vertex aV21, aV22;
1379     TopExp::Vertices(aE, aV21, aV22);
1380     TopAbs_Orientation anOri = TopAbs_FORWARD;
1381
1382     if(aV12.IsSame(aV21) || aV11.IsSame(aV22)) {
1383       anOri = (bforward) ? TopAbs_FORWARD : TopAbs_REVERSED;
1384     }
1385     else {
1386       anOri = (bforward) ? TopAbs_REVERSED : TopAbs_FORWARD;
1387     }
1388     theOrientedList.Append(aE.Oriented(anOri));
1389     aEPrev = aE;
1390     aTolerance1 = (aV21.IsNull()) ? Precision::Confusion() : BRep_Tool::Tolerance(aV21);
1391     aTolerance2 = (aV22.IsNull()) ? Precision::Confusion() : BRep_Tool::Tolerance(aV22);
1392     utol = aBAS.UResolution(aTolerance1);
1393     vtol = aBAS.VResolution(aTolerance1);
1394     aTolerance1 = (utol > vtol) ? utol : vtol;
1395     utol = aBAS.UResolution(aTolerance2);
1396     vtol = aBAS.VResolution(aTolerance2);
1397     aTolerance2 = (utol > vtol) ? utol : vtol;
1398     aCurve = BRep_Tool::CurveOnSurface(aE, theFace, f, l);
1399     ap = aCurve->Value(f);
1400
1401     if(ap.Distance(theFirstPoint) < aTolerance1) {
1402       bFirstFound = Standard_True;
1403     }
1404     else if(ap.Distance(theLastPoint) < aTolerance1) {
1405       bLastFound = Standard_True;
1406     }
1407     ap = aCurve->Value(l);
1408
1409     if(ap.Distance(theFirstPoint) < aTolerance2) {
1410       bFirstFound = Standard_True;
1411     }
1412     else if(ap.Distance(theLastPoint) < aTolerance2) {
1413       bLastFound = Standard_True;
1414     }
1415   }
1416
1417   if(!bFirstFound || !bLastFound)
1418     return Standard_False;
1419   return Standard_True;
1420 }
1421
1422 // ----------------------------------------------------------------------------------------------------
1423 // static function: FindVertex
1424 // purpose:
1425 // ----------------------------------------------------------------------------------------------------
1426 Standard_Boolean FindVertex(const TopoDS_Edge&                        theEdge,
1427                             const Standard_Integer                    theRank,
1428                             const BOPTools_DSFiller&                  theDSFiller,
1429                             const TopTools_DataMapOfShapeListOfShape& theHistMap,
1430                             TopoDS_Vertex&                            theVertex,
1431                             BOPTools_Pave&                            thePave) {
1432
1433   if(!theHistMap.IsBound(theEdge))
1434     return Standard_False;
1435
1436   const TopTools_ListOfShape& lst = theHistMap.Find(theEdge);
1437
1438   if(lst.IsEmpty())
1439     return Standard_False;
1440   const BooleanOperations_ShapesDataStructure& aDS = theDSFiller.DS();
1441
1442   TopoDS_Edge aNewEdge = TopoDS::Edge(lst.First());
1443   Standard_Real f, l;
1444   BRep_Tool::Range(aNewEdge, f, l);
1445
1446   if(theRank == 1) {
1447     thePave.SetParam(l);
1448     theVertex = TopExp::LastVertex(aNewEdge);
1449   }
1450   else {
1451     thePave.SetParam(f);
1452     theVertex = TopExp::FirstVertex(aNewEdge);
1453   }
1454   Standard_Integer anIndex = aDS.ShapeIndex(theVertex, theRank);
1455
1456   if(anIndex == 0) {
1457     Standard_Integer i = 0;
1458
1459     for(i = aDS.NumberOfSourceShapes() + 1; i <= aDS.NumberOfInsertedShapes(); i++) {
1460       const TopoDS_Shape& aShape = aDS.Shape(i);
1461
1462       if(theVertex.IsSame(aShape)) {
1463         anIndex = i;
1464         break;
1465       }
1466     }
1467   }
1468   thePave.SetIndex(anIndex);
1469
1470   return Standard_True;
1471 }
1472
1473 // ----------------------------------------------------------------------------------------------------
1474 // static function: FindNextVertex
1475 // purpose:
1476 // ----------------------------------------------------------------------------------------------------
1477 Standard_Boolean FindNextVertex(const Standard_Integer                    theEdgeIndex,
1478                                 const BOPTools_Pave&                      thePrevPave,
1479                                 const BOPTools_DSFiller&                  theDSFiller,
1480                                 TopoDS_Vertex&                            theNextVertex,
1481                                 BOPTools_Pave&                            thePave) {
1482
1483   const BooleanOperations_ShapesDataStructure& aDS = theDSFiller.DS();
1484   const BOPTools_PaveFiller&           aPaveFiller = theDSFiller.PaveFiller();
1485   const BOPTools_PavePool& aPavePool = aPaveFiller.PavePool();
1486   const BOPTools_PaveSet& aPaveSet = aPavePool(aDS.RefEdge(theEdgeIndex));
1487   BOPTools_PaveSet aSortedPaveSet;
1488   aSortedPaveSet = aPaveSet;
1489   aSortedPaveSet.SortSet();
1490
1491   BOPTools_ListIteratorOfListOfPave anIt(aSortedPaveSet.Set());
1492   BOPTools_Pave anullpave(0, 0.);
1493   Standard_Boolean btakepave = (thePrevPave.IsEqual(anullpave));
1494   Standard_Boolean bfound = Standard_False;
1495   BOPTools_Pave atmppave;
1496
1497   for(; anIt.More(); anIt.Next()) {
1498     if(btakepave) {
1499       atmppave = anIt.Value();
1500
1501       if(atmppave.Type() != BooleanOperations_UnknownInterference) {
1502         theNextVertex = TopoDS::Vertex(aDS.Shape(atmppave.Index()));
1503         thePave = atmppave;
1504         bfound = Standard_True;
1505         break;
1506       }
1507     }
1508
1509     if(thePrevPave.IsEqual(anIt.Value())) {
1510       btakepave = Standard_True;
1511     }
1512   }
1513
1514   return bfound;
1515 }
1516
1517 // ----------------------------------------------------------------------------------------------------
1518 // static function: GetPave
1519 // purpose:
1520 // ----------------------------------------------------------------------------------------------------
1521 Standard_Boolean GetPave(const Standard_Integer   theEdgeIndex,
1522                          const Standard_Boolean   isFirst,
1523                          const BOPTools_DSFiller& theDSFiller,
1524                          BOPTools_Pave&           thePave) {
1525   const BooleanOperations_ShapesDataStructure& aDS = theDSFiller.DS();
1526   const BOPTools_PaveFiller&           aPaveFiller = theDSFiller.PaveFiller();
1527   const BOPTools_PavePool& aPavePool = aPaveFiller.PavePool();
1528
1529   const BOPTools_PaveSet& aPaveSet = aPavePool(aDS.RefEdge(theEdgeIndex));
1530   BOPTools_PaveSet aSortedPaveSet;
1531   aSortedPaveSet = aPaveSet;
1532   aSortedPaveSet.SortSet();
1533
1534   if(aSortedPaveSet.Set().IsEmpty())
1535     return Standard_False;
1536
1537   if(isFirst) {
1538     thePave = aSortedPaveSet.Set().First();
1539   }
1540   else {
1541     thePave = aSortedPaveSet.Set().Last();
1542   }
1543   return Standard_True;
1544 }
1545
1546
1547 // ----------------------------------------------------------------------------------------------------
1548 // static function: FindFromUEdge
1549 // purpose:
1550 // ----------------------------------------------------------------------------------------------------
1551 Standard_Boolean FindFromUEdge(const TopoDS_Edge&                        theUE1Old,
1552                                const TopoDS_Edge&                        theUE2Old,
1553                                const TopoDS_Edge&                        theUE1New,
1554                                const TopoDS_Edge&                        theUE2New,
1555                                const TopoDS_Face&                        theFace,
1556                                const TopoDS_Compound&                    theSecEdges,
1557                                const Standard_Integer                    theRank,
1558                                const TopoDS_Edge&                        theBoundEdge,
1559                                const Standard_Integer                    theBoundEdgeIndex,
1560                                const BOPTools_DSFiller&                  theDSFiller,
1561                                const TopTools_DataMapOfShapeListOfShape& theHistMap,
1562                                TopoDS_Compound&                          theSecEdgesNew,
1563                                TopTools_ListOfShape&                     theListOfWireEdges,
1564                                BOPTools_Pave&                            theFoundPave,
1565                                Standard_Boolean&                         isOnUEdge) {
1566   theFoundPave.SetIndex(0);
1567   theFoundPave.SetParam(0.);
1568   isOnUEdge = Standard_True;
1569
1570   const BooleanOperations_ShapesDataStructure& aDS = theDSFiller.DS();
1571   const BOPTools_PaveFiller&           aPaveFiller = theDSFiller.PaveFiller();
1572   const BOPTools_PavePool& aPavePool = aPaveFiller.PavePool();
1573
1574   TopoDS_Face aFaceF = theFace;
1575   aFaceF.Orientation(TopAbs_FORWARD);
1576   TopoDS_Vertex aPrevVertex, aNextVertex;
1577   TopoDS_Compound aCompOfSecEdges = theSecEdges;
1578   TopTools_ListOfShape aListOfWireEdges;
1579 //  BRep_Builder aBB;
1580
1581   BOPTools_Pave aPave1(0, 0.), aPave2(0, 0.);
1582   Standard_Real f = 0., l = 0.;
1583   gp_Pnt2d p1, p2;
1584   TopoDS_Vertex aFirstV, aLastV;
1585   BOPTools_Pave atmpPave;
1586
1587   if(!FindVertex(theUE1Old, theRank, theDSFiller, theHistMap, aPrevVertex, atmpPave)) {
1588     return Standard_True;
1589   }
1590
1591   if(aPrevVertex.IsNull()) {
1592     return Standard_False;
1593   }
1594
1595   aFirstV = aPrevVertex;
1596   Standard_Boolean bSecFound = Standard_False;
1597   Handle(Geom2d_Curve) aC1 = BRep_Tool::CurveOnSurface(theUE1New, aFaceF, f, l);
1598   p1 = (theRank == 1) ? aC1->Value(l) : aC1->Value(f);
1599   BOPTools_Pave afoundpave(0, 0.);
1600   const BOPTools_PaveSet& aPaveSet = aPavePool(aDS.RefEdge(theBoundEdgeIndex));
1601   Standard_Integer nbpave = aPaveSet.Set().Extent();
1602   Standard_Integer pit = 0;
1603
1604   while(FindNextVertex(theBoundEdgeIndex, aPave1, theDSFiller, aNextVertex, aPave2) && (pit < nbpave)) {
1605     aLastV = aNextVertex;
1606     Handle(Geom2d_Curve) aC2 = BRep_Tool::CurveOnSurface(theBoundEdge, aFaceF, f, l);
1607     p2 = aC2->Value(aPave2.Param());
1608     TopTools_ListOfShape aOrderedList;
1609
1610     if(FillGap(aFirstV, aLastV, p1, p2, aFaceF, aCompOfSecEdges, aOrderedList)) {
1611       // remove found edges...
1612       TopoDS_Compound aComp;
1613       RemoveEdges(aCompOfSecEdges, aOrderedList, aComp);
1614       aCompOfSecEdges = aComp;
1615       aListOfWireEdges.Append(aOrderedList);
1616       afoundpave = aPave2;
1617       isOnUEdge = Standard_False;
1618       bSecFound = Standard_True;
1619       break;
1620     }
1621     aPrevVertex = aNextVertex;
1622     aPave1 = aPave2;
1623     pit++;
1624   }
1625
1626   if(!bSecFound && FindVertex(theUE2Old, theRank, theDSFiller, theHistMap, aNextVertex, aPave2)) {
1627     aLastV = aNextVertex;
1628     Handle(Geom2d_Curve) aC2 = BRep_Tool::CurveOnSurface(theUE2New, aFaceF, f, l);
1629     p2 = aC2->Value(aPave2.Param());
1630     TopTools_ListOfShape aOrderedList;
1631
1632     if(FillGap(aFirstV, aLastV, p1, p2, aFaceF, aCompOfSecEdges, aOrderedList)) {
1633       // remove found edges...
1634       TopoDS_Compound aComp;
1635
1636       RemoveEdges(aCompOfSecEdges, aOrderedList, aComp);
1637       aCompOfSecEdges = aComp;
1638       aListOfWireEdges.Append(aOrderedList);
1639       afoundpave = aPave2;
1640       bSecFound = Standard_True;
1641       isOnUEdge = Standard_True;
1642     }
1643   }
1644
1645   if(bSecFound) {
1646     theFoundPave = afoundpave;
1647     theListOfWireEdges = aListOfWireEdges;
1648     theSecEdgesNew = aCompOfSecEdges;
1649   }
1650   return Standard_True;
1651 }
1652
1653
1654 // ----------------------------------------------------------------------------------------------------
1655 // static function: FindFromVEdge
1656 // purpose:
1657 // ----------------------------------------------------------------------------------------------------
1658 Standard_Boolean FindFromVEdge(const BOPTools_Pave&                      thePrevPave,
1659                                const Standard_Boolean&                   isOnUEdge,
1660                                const TopoDS_Edge&                        theUE1Old,
1661                                const TopoDS_Edge&                        theUE2Old,
1662                                const TopoDS_Face&                        theFace,
1663                                const TopoDS_Compound&                    theSecEdges,
1664                                const Standard_Integer                    theRank,
1665                                const TopoDS_Edge&                        theBoundEdge,
1666                                const Standard_Integer                    theBoundEdgeIndex,
1667                                const BOPTools_DSFiller&                  theDSFiller,
1668                                const TopTools_DataMapOfShapeListOfShape& theHistMap,
1669                                TopTools_ListOfShape&                     theListOfWireEdges,
1670                                Standard_Boolean&                         isSectionFound) {
1671   theListOfWireEdges.Clear();
1672   isSectionFound = Standard_False;
1673   const BooleanOperations_ShapesDataStructure& aDS = theDSFiller.DS();
1674   const BOPTools_PaveFiller&           aPaveFiller = theDSFiller.PaveFiller();
1675   const BOPTools_SplitShapesPool& aSplitShapesPool = aPaveFiller.SplitShapesPool();
1676   const BOPTools_PavePool& aPavePool = aPaveFiller.PavePool();
1677
1678   TopoDS_Face aFaceF = theFace;
1679   aFaceF.Orientation(TopAbs_FORWARD);
1680   TopoDS_Vertex aPrevVertex, aNextVertex;
1681   TopoDS_Compound aCompOfSecEdges = theSecEdges;
1682   TopTools_ListOfShape aListOfWireEdges;
1683 //  BRep_Builder aBB;
1684
1685   BOPTools_Pave aPave1(0, 0.), aPave2(0, 0.);
1686
1687   if(isOnUEdge) {
1688     TopoDS_Vertex atmpVertex;
1689     BOPTools_Pave aPaveOfE2;
1690
1691     if(FindVertex(theUE2Old, theRank, theDSFiller, theHistMap, atmpVertex, aPaveOfE2)) {
1692       if(thePrevPave.IsEqual(aPaveOfE2))
1693         return Standard_True;
1694     }
1695   }
1696
1697   Standard_Real f = 0., l = 0.;
1698   gp_Pnt2d p1(0., 0.), p2(0., 0.);
1699   TopoDS_Vertex aFirstV, aLastV;
1700   Handle(Geom2d_Curve) aC1 = BRep_Tool::CurveOnSurface(theUE1Old, aFaceF, f, l);
1701   Handle(Geom2d_Curve) aC2 = BRep_Tool::CurveOnSurface(theBoundEdge, aFaceF, f, l);
1702   Standard_Boolean bSecFound = Standard_False;
1703
1704   aPave1 = thePrevPave;
1705
1706   if(isOnUEdge) {
1707     BOPTools_Pave atmpPave;
1708
1709     if(!GetPave(theBoundEdgeIndex, Standard_True, theDSFiller, atmpPave)) {
1710       return Standard_False;
1711     }
1712     aPave1 = atmpPave;
1713   }
1714   p1 = aC2->Value(aPave1.Param());
1715   aPrevVertex = TopoDS::Vertex(aDS.Shape(aPave1.Index()));
1716
1717   const BOPTools_PaveSet& aPaveSet = aPavePool(aDS.RefEdge(theBoundEdgeIndex));
1718   Standard_Integer nbpave = aPaveSet.Set().Extent();
1719   Standard_Integer pit = 0;
1720   TopTools_Array1OfListOfShape anArrayOfListOfSec(1, nbpave);
1721
1722   // by pairs non continuously. begin
1723   Standard_Integer k = 0;
1724   BOPTools_Pave aFirstPave = aPave1;
1725   TopoDS_Vertex aFirstVertex = aPrevVertex;
1726   gp_Pnt2d apfirst = p1;
1727   BOPTools_ListOfPave aFirstPaves, aLastPaves;
1728   TColStd_ListOfInteger aListOfFlags;
1729   Standard_Integer apaircounter = 1;
1730
1731   for(k = 0; k < nbpave; k++) {
1732     aPave1 = aFirstPave;
1733     p1 = apfirst;
1734     aPrevVertex = aFirstVertex;
1735     Standard_Boolean bfound = Standard_False;
1736     pit = 0;
1737
1738     while(FindNextVertex(theBoundEdgeIndex, aPave1, theDSFiller, aNextVertex, aPave2) && (pit < nbpave)) {
1739       aFirstV = aPrevVertex;
1740       aLastV = aNextVertex;
1741       p2 = aC2->Value(aPave2.Param());
1742
1743       TopTools_ListOfShape aOrderedList;
1744
1745       if(FillGap(aFirstV, aLastV, p1, p2, aFaceF, aCompOfSecEdges, aOrderedList)) {
1746         TopoDS_Compound aComp;
1747         RemoveEdges(aCompOfSecEdges, aOrderedList, aComp);
1748         aCompOfSecEdges = aComp;
1749
1750         anArrayOfListOfSec(apaircounter++).Append(aOrderedList);
1751         BOPTools_PaveBlock aPB(theBoundEdgeIndex, aFirstPave, aPave2);
1752         aFirstPaves.Append(aFirstPave);
1753         aLastPaves.Append(aPave2);
1754         aListOfFlags.Append(1);
1755         aFirstPave = aPave2;
1756         aFirstVertex = aNextVertex;
1757         apfirst = p2;
1758         aPrevVertex = aNextVertex;
1759         bSecFound = Standard_True;
1760         bfound = Standard_True;
1761       }
1762       aPave1 = aPave2;
1763       pit++;
1764     }
1765
1766     if(FindVertex(theUE2Old, theRank, theDSFiller, theHistMap, aNextVertex, aPave2)) {
1767       aFirstV = aPrevVertex;
1768       aLastV = aNextVertex;
1769       Handle(Geom2d_Curve) aC3 = BRep_Tool::CurveOnSurface(theUE2Old, aFaceF, f, l);
1770       p2 = aC3->Value(aPave2.Param());
1771
1772       TopTools_ListOfShape aOrderedList;
1773
1774       if(FillGap(aFirstV, aLastV, p1, p2, aFaceF, aCompOfSecEdges, aOrderedList)) {
1775         TopoDS_Compound aComp;
1776         RemoveEdges(aCompOfSecEdges, aOrderedList, aComp);
1777         aCompOfSecEdges = aComp;
1778         anArrayOfListOfSec(apaircounter++).Append(aOrderedList);
1779         BOPTools_PaveBlock aPB(-1, aFirstPave, aPave2);
1780         aFirstPaves.Append(aFirstPave);
1781         aLastPaves.Append(aPave2);
1782         aListOfFlags.Append(0);
1783         bSecFound = Standard_True;
1784         break;
1785       }
1786     }
1787
1788     if(!bfound) {
1789       if(!FindNextVertex(theBoundEdgeIndex, aFirstPave, theDSFiller, aNextVertex, aPave2)) {
1790         break;
1791       }
1792       aFirstPave = aPave2;
1793       apfirst = aC2->Value(aPave2.Param());
1794       aFirstVertex = aNextVertex;
1795     }
1796   }
1797   // by pairs non continuously. end
1798
1799   // by pairs continuously. begin
1800   aPave1 = thePrevPave;
1801
1802   if(isOnUEdge) {
1803     BOPTools_Pave atmpPave;
1804
1805     if(!GetPave(theBoundEdgeIndex, Standard_True, theDSFiller, atmpPave)) {
1806       return Standard_False;
1807     }
1808     aPave1 = atmpPave;
1809   }
1810   p1 = aC2->Value(aPave1.Param());
1811   aPrevVertex = TopoDS::Vertex(aDS.Shape(aPave1.Index()));
1812
1813   pit = 0;
1814
1815   while(FindNextVertex(theBoundEdgeIndex, aPave1, theDSFiller, aNextVertex, aPave2) && (pit < nbpave)) {
1816     aFirstV = aPrevVertex;
1817     aLastV = aNextVertex;
1818     p2 = aC2->Value(aPave2.Param());
1819
1820     Standard_Boolean bisinside = Standard_False;
1821     Standard_Integer apbindex = 0;
1822     Standard_Integer apbcounter = 1;
1823     BOPTools_ListIteratorOfListOfPaveBlock aPBIt;
1824     BOPTools_ListIteratorOfListOfPave aPIt1, aPIt2;
1825     TColStd_ListIteratorOfListOfInteger aFlagIt;
1826
1827     for(aPIt1.Initialize(aFirstPaves), aPIt2.Initialize(aLastPaves), aFlagIt.Initialize(aListOfFlags);
1828         aPIt1.More() && aPIt2.More() && aFlagIt.More();
1829         aPIt1.Next(), aPIt2.Next(), aFlagIt.Next(), apbcounter++) {
1830
1831       Standard_Boolean bfin = Standard_False;
1832       Standard_Boolean blin = Standard_False;
1833
1834       if(aPave1.IsEqual(aPIt1.Value())) {
1835         bfin = Standard_True;
1836       }
1837       else {
1838         bfin = (aPave1.Param() > aPIt1.Value().Param());
1839       }
1840
1841       if(aFlagIt.Value()) {
1842         if(aPave2.IsEqual(aPIt2.Value())) {
1843           blin = Standard_True;
1844         }
1845         else {
1846           blin = (aPave2.Param() < aPIt2.Value().Param());
1847         }
1848       }
1849       else {
1850         if((aPave2.Index() == aPIt2.Value().Index()) && (aPave2.Index() > 0)) {
1851           Handle(Geom2d_Curve) pc = BRep_Tool::CurveOnSurface(theUE2Old, aFaceF, f, l);
1852           gp_Pnt2d p3 = pc->Value(aPIt2.Value().Param());
1853           TopoDS_Vertex aV = TopoDS::Vertex(aDS.Shape(aPave2.Index()));
1854           BRepAdaptor_Surface aBAS(aFaceF, Standard_False);
1855           Standard_Real aTolerance = BRep_Tool::Tolerance(aV);
1856           Standard_Real utol = aBAS.UResolution(aTolerance);
1857           Standard_Real vtol = aBAS.VResolution(aTolerance);
1858           aTolerance = (utol > vtol) ? utol : vtol;
1859
1860           if(p2.Distance(p3) < aTolerance)
1861             blin = Standard_True;
1862         }
1863       }
1864
1865       if(bfin && blin) {
1866         apbindex = apbcounter;
1867         bisinside = Standard_True;
1868         break;
1869       }
1870     }
1871
1872     if(!bisinside) {
1873
1874       TopTools_ListOfShape aOrderedList;
1875
1876       if(FillGap(aFirstV, aLastV, p1, p2, aFaceF, aCompOfSecEdges, aOrderedList)) {
1877         TopoDS_Compound aComp;
1878         RemoveEdges(aCompOfSecEdges, aOrderedList, aComp);
1879         aCompOfSecEdges = aComp;
1880         aListOfWireEdges.Append(aOrderedList);
1881
1882         bSecFound = Standard_True;
1883       }
1884       else {
1885         TopoDS_Edge aESplit;
1886         BOPTools_PaveBlock aPB(theBoundEdgeIndex, aPave1, aPave2);
1887         // get split
1888         aPBIt.Initialize(aSplitShapesPool(aDS.RefEdge(theBoundEdgeIndex)));
1889
1890         for(; aPBIt.More(); aPBIt.Next()) {
1891           if(aPB.IsEqual(aPBIt.Value())) {
1892             if(aPBIt.Value().Edge() > 0) {
1893               aESplit = TopoDS::Edge(aDS.Shape(aPBIt.Value().Edge()));
1894               break;
1895             }
1896           }
1897         }
1898
1899         if(!aESplit.IsNull()) {
1900           aListOfWireEdges.Append(aESplit);
1901         }
1902       }
1903     }
1904     else {
1905       if(apbindex > 0) {
1906         TopTools_ListOfShape& aListOfSec = anArrayOfListOfSec(apbindex);
1907         aListOfWireEdges.Append(aListOfSec);
1908       }
1909     }
1910     aPave1 = aPave2;
1911     aPrevVertex = aNextVertex;
1912     p1 = p2;
1913     pit++;
1914   }
1915
1916   if(FindVertex(theUE2Old, theRank, theDSFiller, theHistMap, aNextVertex, aPave2)) {
1917     aFirstV = aPrevVertex;
1918     aLastV = aNextVertex;
1919     Handle(Geom2d_Curve) aC3 = BRep_Tool::CurveOnSurface(theUE2Old, aFaceF, f, l);
1920     p2 = aC3->Value(aPave2.Param());
1921
1922     Standard_Boolean bisinside = Standard_False;
1923     Standard_Integer apbindex = 0;
1924     Standard_Integer apbcounter = 1;
1925     BOPTools_ListIteratorOfListOfPaveBlock aPBIt;
1926     BOPTools_ListIteratorOfListOfPave aPIt1, aPIt2;
1927     TColStd_ListIteratorOfListOfInteger aFlagIt;
1928
1929     for(aPIt1.Initialize(aFirstPaves), aPIt2.Initialize(aLastPaves), aFlagIt.Initialize(aListOfFlags);
1930         aPIt1.More() && aPIt2.More() && aFlagIt.More();
1931         aPIt1.Next(), aPIt2.Next(), aFlagIt.Next(), apbcounter++) {
1932
1933       Standard_Boolean bfin = Standard_False;
1934       Standard_Boolean blin = Standard_False;
1935
1936       if(aPave1.IsEqual(aPIt1.Value())) {
1937         bfin = Standard_True;
1938       }
1939       else {
1940         bfin = (aPave1.Param() > aPIt1.Value().Param());
1941       }
1942
1943       if(aFlagIt.Value()) {
1944         if(aPave2.IsEqual(aPIt2.Value())) {
1945           blin = Standard_True;
1946         }
1947         else {
1948           blin = (aPave2.Param() < aPIt2.Value().Param());
1949         }
1950       }
1951       else {
1952         blin = Standard_True;
1953       }
1954
1955       if(bfin && blin) {
1956         apbindex = apbcounter;
1957         bisinside = Standard_True;
1958         break;
1959       }
1960     }
1961
1962     if(!bisinside) {
1963
1964       TopTools_ListOfShape aOrderedList;
1965
1966       if(FillGap(aFirstV, aLastV, p1, p2, aFaceF, aCompOfSecEdges, aOrderedList)) {
1967         TopoDS_Compound aComp;
1968         RemoveEdges(aCompOfSecEdges, aOrderedList, aComp);
1969         aCompOfSecEdges = aComp;
1970         aListOfWireEdges.Append(aOrderedList);
1971
1972         bSecFound = Standard_True;
1973       }
1974       else {
1975         //add split
1976         TopoDS_Edge aESplit;
1977         // get split
1978         if(!GetPave(theBoundEdgeIndex, Standard_False, theDSFiller, aPave2))
1979           return Standard_False;
1980         BOPTools_PaveBlock aPB(theBoundEdgeIndex, aPave1, aPave2);
1981         aPBIt.Initialize(aSplitShapesPool(aDS.RefEdge(theBoundEdgeIndex)));
1982
1983         for(; aPBIt.More(); aPBIt.Next()) {
1984           if(aPB.IsEqual(aPBIt.Value())) {
1985             if(aPBIt.Value().Edge() > 0) {
1986               aESplit = TopoDS::Edge(aDS.Shape(aPBIt.Value().Edge()));
1987               break;
1988             }
1989           }
1990         }
1991
1992         if(!aESplit.IsNull()) {
1993           aListOfWireEdges.Append(aESplit);
1994         }
1995       }
1996     }
1997     else {
1998       if(apbindex > 0) {
1999         TopTools_ListOfShape& aListOfSec = anArrayOfListOfSec(apbindex);
2000         aListOfWireEdges.Append(aListOfSec);
2001       }
2002     }
2003   }
2004   else {
2005     //add split
2006     TopoDS_Edge aESplit;
2007     // get split
2008     if(!GetPave(theBoundEdgeIndex, Standard_False, theDSFiller, aPave2))
2009       return Standard_False;
2010     BOPTools_PaveBlock aPB(theBoundEdgeIndex, aPave1, aPave2);
2011     BOPTools_ListIteratorOfListOfPaveBlock aPBIt;
2012     aPBIt.Initialize(aSplitShapesPool(aDS.RefEdge(theBoundEdgeIndex)));
2013
2014     for(; aPBIt.More(); aPBIt.Next()) {
2015       if(aPB.IsEqual(aPBIt.Value())) {
2016         if(aPBIt.Value().Edge() > 0) {
2017           aESplit = TopoDS::Edge(aDS.Shape(aPBIt.Value().Edge()));
2018           break;
2019         }
2020       }
2021     }
2022
2023     if(!aESplit.IsNull()) {
2024       aListOfWireEdges.Append(aESplit);
2025     }
2026   }
2027
2028   // by pairs continuously. end
2029   theListOfWireEdges = aListOfWireEdges;
2030   isSectionFound = bSecFound;
2031   return Standard_True;
2032 }
2033
2034 // ----------------------------------------------------------------------------------------------------
2035 // static function: RemoveEdges
2036 // purpose:
2037 // ----------------------------------------------------------------------------------------------------
2038 void RemoveEdges(const TopoDS_Compound&      theSourceComp,
2039                  const TopTools_ListOfShape& theListToRemove,
2040                  TopoDS_Compound&            theResultComp) {
2041   BRep_Builder aBB;
2042   TopoDS_Compound aComp;
2043   aBB.MakeCompound(aComp);
2044   TopExp_Explorer anExp(theSourceComp, TopAbs_EDGE);
2045
2046   for(; anExp.More(); anExp.Next()) {
2047     Standard_Boolean bfound = Standard_False;
2048     TopTools_ListIteratorOfListOfShape anIt(theListToRemove);
2049
2050     for(; !bfound && anIt.More(); anIt.Next()) {
2051       bfound = anExp.Current().IsSame(anIt.Value());
2052     }
2053
2054     if(!bfound) {
2055       aBB.Add(aComp, anExp.Current());
2056     }
2057   }
2058   theResultComp = aComp;
2059 }
2060
2061 // ----------------------------------------------------------------------------------------------------
2062 // static function: FilterSectionEdges
2063 // purpose:
2064 // ----------------------------------------------------------------------------------------------------
2065 Standard_Boolean FilterSectionEdges(const BOPTools_SequenceOfCurves& theBCurves,
2066                                     const TopoDS_Face&               theSecPlane,
2067                                     const BOPTools_DSFiller&         theDSFiller,
2068                                     TopoDS_Compound&                 theResult) {
2069
2070   theResult.Nullify();
2071   const BooleanOperations_ShapesDataStructure& aDS = theDSFiller.DS();
2072
2073   BRep_Builder aBB;
2074   aBB.MakeCompound(theResult);
2075   Standard_Integer aNbCurves = theBCurves.Length();
2076   Standard_Integer cit = 0;
2077
2078   for(cit = 1; cit <= aNbCurves; cit++) {
2079     const BOPTools_Curve& aBCurve = theBCurves(cit);
2080     const BOPTools_ListOfPaveBlock& aSectEdges = aBCurve.NewPaveBlocks();
2081
2082     BOPTools_ListIteratorOfListOfPaveBlock aPBIt(aSectEdges);
2083
2084     for (; aPBIt.More(); aPBIt.Next()) {
2085       BOPTools_PaveBlock& aPB = aPBIt.Value();
2086       Standard_Integer nSect = aPB.Edge();
2087       const TopoDS_Shape& aS = aDS.GetShape(nSect);
2088       TopoDS_Edge anEdge = TopoDS::Edge(aS);
2089       Standard_Boolean bAddEdge = Standard_True;
2090
2091       if(!theSecPlane.IsNull()) {
2092         IntTools_BeanFaceIntersector anIntersector(anEdge, theSecPlane);
2093         Standard_Real f = 0., l = 0.;
2094         BRep_Tool::Range(anEdge, f, l);
2095         anIntersector.SetBeanParameters(f, l);
2096         //
2097         IntTools_Context aContext;
2098         anIntersector.SetContext(&aContext);
2099         //
2100         anIntersector.Perform();
2101
2102         if(anIntersector.IsDone()) {
2103           bAddEdge = Standard_False;
2104           Standard_Integer r = 0;
2105
2106           for(r = 1; r <= anIntersector.Result().Length(); r++) {
2107             const IntTools_Range& aRange = anIntersector.Result().Value(r);
2108
2109             if(((aRange.First() - f) < Precision::PConfusion()) &&
2110                ((l - aRange.Last()) < Precision::PConfusion())) {
2111               bAddEdge = Standard_True;
2112             }
2113           }
2114         }
2115         else {
2116 //        cout << "not done..."   << endl;
2117         }
2118       }
2119
2120       if(bAddEdge) {
2121         aBB.Add(theResult, aS);
2122       }
2123     }
2124   }
2125   return Standard_True;
2126 }
2127
2128
2129 //=======================================================================
2130 //function : ComputeAveragePlaneAndMaxDeviation
2131 //purpose  :
2132 //=======================================================================
2133 static Standard_Real ComputeAveragePlaneAndMaxDeviation(const TopoDS_Shape& aWire,
2134                                                         gp_Pln& thePlane,
2135                                                         Standard_Boolean& IsSingular)
2136 {
2137   Standard_Integer N = 40, nedges = 0;
2138
2139   TopoDS_Iterator iter( aWire );
2140   for (; iter.More(); iter.Next())
2141     nedges++;
2142
2143   TColgp_Array1OfPnt Pnts( 1, nedges*N );
2144   Standard_Integer ind = 1, i;
2145   for (iter.Initialize(aWire); iter.More(); iter.Next())
2146     {
2147       const TopoDS_Edge& anEdge = TopoDS::Edge( iter.Value() );
2148       BRepAdaptor_Curve aCurve(anEdge);
2149       GCPnts_UniformAbscissa Distribution( aCurve, N+1 );
2150       for (i = 1; i <= N; i++)
2151         {
2152           Standard_Real par = Distribution.Parameter(i);
2153           Pnts( ind++ ) = aCurve.Value(par);
2154         }
2155     }
2156
2157   gp_Ax2 Axe;
2158   GeomLib::AxeOfInertia( Pnts, Axe, IsSingular );
2159   if (IsSingular)
2160     return -1;
2161
2162   thePlane = gp_Pln( Axe );
2163   Standard_Real MaxDeviation = 0;
2164   for (i = 1; i <= Pnts.Length(); i++)
2165     {
2166       Standard_Real dist = thePlane.Distance( Pnts(i) );
2167       if (dist > MaxDeviation)
2168         MaxDeviation = dist;
2169     }
2170   return MaxDeviation;
2171 }
2172
2173 //=======================================================================
2174 //function : ChooseSection
2175 //purpose  :
2176 //=======================================================================
2177 static Standard_Boolean ChooseSection(const TopoDS_Shape& Comp,
2178                                       const gp_Ax2& bis,
2179                                       TopoDS_Shape& resWire,
2180                                       gp_Pln& resPlane,
2181                                       Standard_Boolean& IsSingular)
2182 {
2183   IsSingular = Standard_False;
2184   Standard_Real TolDeviation = 0.01; //, TolConf = 1.e-4, TolAng = 1.e-5;
2185
2186 //  Standard_Integer N = 100;
2187   Standard_Integer ind, i, j;
2188
2189   //Simplest case
2190   TopoDS_Compound OldComp;
2191   BRep_Builder B;
2192   B.MakeCompound( OldComp );
2193   TopoDS_Iterator iter( Comp );
2194   for (; iter.More(); iter.Next())
2195     B.Add( OldComp, iter.Value() );
2196
2197   Standard_Boolean anError = Standard_False;
2198   //TopoDS_Wire NewWire [2];
2199   TopTools_SequenceOfShape Wseq;
2200   for (;;)
2201     {
2202       TopExp_Explorer explo( OldComp, TopAbs_EDGE );
2203       if (!explo.More())
2204         break;
2205       TopoDS_Edge FirstEdge = TopoDS::Edge( explo.Current() );
2206       TopoDS_Wire NewWire = BRepLib_MakeWire( FirstEdge );
2207       B.Remove( OldComp, FirstEdge );
2208       if (NewWire.Closed())
2209         {
2210           Wseq.Append(NewWire);
2211           continue;
2212         }
2213
2214       for (;;)
2215         {
2216           TopoDS_Vertex Extremity [2];
2217           TopExp::Vertices( NewWire, Extremity[0], Extremity[1] );
2218           if (Extremity[0].IsNull() || Extremity[1].IsNull())
2219             {
2220               anError = Standard_True;
2221               break;
2222             }
2223           TopTools_IndexedDataMapOfShapeListOfShape VEmap;
2224           TopExp::MapShapesAndAncestors( OldComp, TopAbs_VERTEX, TopAbs_EDGE, VEmap );
2225           TopTools_ListOfShape Vedges [2];
2226           for (j = 0; j < 2; j++)
2227             if (VEmap.Contains( Extremity[j] ))
2228               Vedges[j] = VEmap.FindFromKey( Extremity[j] );
2229           if (Vedges[0].IsEmpty() && Vedges[1].IsEmpty())
2230             //no more edges in OldComp to continue NewWire
2231             break;
2232           Standard_Boolean Modified = Standard_False;
2233           for (j = 0; j < 2; j++)
2234             {
2235               if (Vedges[j].Extent() == 1)
2236                 {
2237                   const TopoDS_Edge& anEdge = TopoDS::Edge( Vedges[j].First() );
2238                   NewWire = BRepLib_MakeWire( NewWire, anEdge );
2239                   B.Remove( OldComp, anEdge );
2240                   Modified = Standard_True;
2241                 }
2242             }
2243           if (!Modified) //only multiple connections
2244             {
2245               ind = (Vedges[0].IsEmpty())? 1 : 0;
2246               TopTools_SequenceOfShape Edges;
2247               TopTools_ListIteratorOfListOfShape itl( Vedges[ind] );
2248               for (; itl.More(); itl.Next())
2249                 Edges.Append( itl.Value() );
2250               Standard_Integer theind=0;
2251               Standard_Real MinDeviation = RealLast();
2252               for (j = 1; j <= Edges.Length(); j++)
2253                 {
2254                   TopoDS_Wire aWire = BRepLib_MakeWire( NewWire, TopoDS::Edge(Edges(j)) );
2255                   gp_Pln aPlane;
2256                   Standard_Boolean issing;
2257                   Standard_Real Deviation = ComputeAveragePlaneAndMaxDeviation( aWire, aPlane, issing );
2258                   if (Deviation < MinDeviation)
2259                     {
2260                       MinDeviation = Deviation;
2261                       theind = j;
2262                     }
2263                 }
2264               NewWire = BRepLib_MakeWire( NewWire, TopoDS::Edge(Edges(theind)) );
2265               B.Remove( OldComp, Edges(theind) );
2266             }
2267           if (NewWire.Closed())
2268             break;
2269         }
2270       Wseq.Append(NewWire);
2271       if (anError)
2272         break;
2273     }
2274
2275   Standard_Real Deviation=0.;
2276   Standard_Real MinAngle = RealLast();
2277   TopExp_Explorer Explo( OldComp, TopAbs_EDGE );
2278   if (!anError && !Explo.More())
2279     {
2280       if (Wseq.Length() == 1)
2281         {
2282           resWire = Wseq.First();
2283           Deviation = ComputeAveragePlaneAndMaxDeviation( resWire, resPlane, IsSingular );
2284           return Standard_True;
2285         }
2286       else
2287         {
2288           for (i = 1; i <= Wseq.Length(); i++)
2289             {
2290               TopoDS_Wire aWire = TopoDS::Wire( Wseq(i) );
2291               gp_Pln aPln;
2292               Standard_Boolean issing;
2293               Standard_Real aDeviation =
2294                 ComputeAveragePlaneAndMaxDeviation( aWire, aPln, issing );
2295               if (issing)
2296                 continue;
2297
2298               Standard_Real Angle = aPln.Axis().Angle( bis.Axis() );
2299               if (Angle > M_PI/2)
2300                 Angle = M_PI - Angle;
2301
2302               if (Angle < MinAngle)
2303                 {
2304                   MinAngle = Angle;
2305                   resWire = aWire;
2306                   resPlane = aPln;
2307                   Deviation = aDeviation;
2308                 }
2309             }
2310           if (Deviation <= TolDeviation)
2311             return Standard_True;
2312         }
2313     }
2314   return Standard_False;
2315   //end of simplest case
2316 }
2317
2318 //=======================================================================
2319 //function : ChoosePlane
2320 //purpose  :
2321 //=======================================================================
2322 static Standard_Boolean ChoosePlane(const TopoDS_Shape& Comp,
2323                                     const gp_Ax2& bis,
2324                                     gp_Pln& resPlane,
2325                                     TopoDS_Compound& NewComp)
2326 {
2327   Standard_Real TolConf = 1.e-4, TolAng = 1.e-5;
2328
2329   Standard_Integer N = 100;
2330   Standard_Integer Eind, ind, i, j;
2331   TopTools_SequenceOfShape Eseq;
2332   TopExp_Explorer Explo( Comp, TopAbs_EDGE );
2333   for (; Explo.More(); Explo.Next())
2334     Eseq.Append( Explo.Current() );
2335
2336   Standard_Integer NumberOfEdges = Eseq.Length();
2337   TColgp_Array2OfPnt Points( 0, NumberOfEdges*2-1, 1, N/4 );
2338
2339   for (Eind = 0; Eind < NumberOfEdges; Eind++)
2340     {
2341       TopoDS_Edge anEdge = TopoDS::Edge( Eseq(Eind+1) );
2342       BRepAdaptor_Curve aCurve(anEdge);
2343       GCPnts_UniformAbscissa Distribution( aCurve, N+1 );
2344       for (i = 1; i <= N/4; i++)
2345         {
2346           Standard_Real par = Distribution.Parameter(i);
2347           Points( Eind*2, i ) = aCurve.Value(par);
2348         }
2349       for (i = 3*N/4+2; i <= N+1; i++)
2350         {
2351           Standard_Real par = Distribution.Parameter(i);
2352           Points( Eind*2+1, i-3*N/4-1 ) = aCurve.Value(par);
2353         }
2354     }
2355
2356   TColgp_Array1OfPnt Origins( 0, NumberOfEdges*2-1 );
2357   TColgp_Array1OfDir Normals( 0, NumberOfEdges*2-1 );
2358   TColStd_Array1OfBoolean IsSingular( 0, NumberOfEdges*2-1 );
2359   Standard_Real MinAngle = M_PI/2;
2360   Standard_Integer MinInd;
2361   for (ind = 0; ind < NumberOfEdges*2; ind++)
2362     {
2363       TColgp_Array1OfPnt pnts( 1, N/4 );
2364       for (i = 1; i <= N/4; i++)
2365         pnts(i) = Points( ind, i );
2366       gp_Ax2 Axe;
2367       GeomLib::AxeOfInertia( pnts, Axe, IsSingular(ind) );
2368       if (!IsSingular(ind))
2369         {
2370           Origins(ind) = Axe.Location();
2371           Normals(ind) = Axe.Direction();
2372           Standard_Real Angle = bis.Angle( Axe );
2373           if (Angle > M_PI/2)
2374             Angle = M_PI - Angle;
2375           if (Angle < MinAngle)
2376             {
2377               MinAngle = Angle;
2378               MinInd = ind;
2379             }
2380         }
2381     }
2382
2383   gp_Ax2 TheAxe( Origins(MinInd), Normals(MinInd) );
2384   Standard_Real MaxAngleWithPln = M_PI/16;
2385   TColStd_SequenceOfInteger iseq;
2386   TColgp_SequenceOfPnt Pseq;
2387   for (ind = 0; ind < NumberOfEdges*2; ind++)
2388     if (!IsSingular(ind))
2389       {
2390         Standard_Real Angle = Normals(ind).Angle( TheAxe.Direction() );
2391           if (Angle > M_PI/2)
2392             Angle = M_PI - Angle;
2393         if (Angle <= MaxAngleWithPln)
2394           {
2395             iseq.Append(ind);
2396             for (j = 1; j <= N/4; j++)
2397               Pseq.Append( Points(ind,j) );
2398           }
2399       }
2400
2401   TColgp_Array1OfPnt Parray( 1, Pseq.Length() );
2402   for (i = 1; i <= Parray.Length(); i++)
2403     Parray(i) = Pseq(i);
2404   Standard_Boolean issing;
2405   GeomLib::AxeOfInertia( Parray, TheAxe, issing );
2406   resPlane = gp_Pln( TheAxe );
2407
2408   i = 1;
2409   BRep_Builder B;
2410   B.MakeCompound(NewComp);
2411   while (i <= iseq.Length())
2412     {
2413       Standard_Integer ind0 = iseq(i);
2414       if (IsEven(ind0) && i < iseq.Length() && iseq(i+1) == ind0+1) //the whole edge
2415         {
2416           B.Add( NewComp, Eseq(ind0/2+1) );
2417           i += 2;
2418         }
2419       else
2420         i++;
2421     }
2422
2423   Standard_Integer slen = Pseq.Length();
2424   for (ind = 0; ind < NumberOfEdges*2; ind += 2)
2425     {
2426       Standard_Integer IndSing = -1, IndNotSing = -1;
2427       gp_Lin aLine;
2428       if (IsSingular(ind) && IsSingular(ind+1))
2429         {
2430           Standard_Boolean OnPlane0 = Standard_False, OnPlane1 = Standard_False;
2431           aLine = gce_MakeLin( Points(ind, 1), Points(ind, N/4) );
2432           if (resPlane.Contains( aLine, TolConf, TolAng ))
2433             {
2434               for (j = 1; j <= N/4; j++)
2435                 Pseq.Append( Points(ind,j) );
2436               OnPlane0 = Standard_True;
2437             }
2438           aLine = gce_MakeLin( Points(ind+1, 1), Points(ind+1, N/4) );
2439           if (resPlane.Contains( aLine, TolConf, TolAng ))
2440             {
2441               for (j = 1; j <= N/4; j++)
2442                 Pseq.Append( Points(ind+1,j) );
2443               OnPlane1 = Standard_True;
2444             }
2445           if (OnPlane0 && OnPlane1)
2446             B.Add( NewComp, Eseq(ind/2+1) );
2447         }
2448       else if (IsSingular(ind))
2449         {
2450           IndSing    = ind;
2451           IndNotSing = ind+1;
2452         }
2453       else if (IsSingular(ind+1))
2454         {
2455           IndNotSing = ind;
2456           IndSing    = ind+1;
2457         }
2458       if (IndSing != -1 && IndNotSing != -1)
2459         {
2460           aLine = gce_MakeLin( Points(IndSing, 1), Points(IndSing, N/4) );
2461           if (resPlane.Contains( aLine, TolConf, TolAng ))
2462             {
2463               for (j = 1; j <= N/4; j++)
2464                 Pseq.Append( Points(IndSing,j) );
2465
2466               for (i = 1; i <= iseq.Length(); i++)
2467                 if (iseq(i) == IndNotSing)
2468                   break;
2469               if (i <= iseq.Length())
2470                 B.Add( NewComp, Eseq(ind/2+1) );
2471             }
2472         }
2473     }
2474
2475   //Recompute the axe of plane
2476   if (Pseq.Length() > slen)
2477     {
2478       TColgp_Array1OfPnt Parray2( 1, Pseq.Length() );
2479       for (i = 1; i <= Parray2.Length(); i++)
2480         Parray2(i) = Pseq(i);
2481       GeomLib::AxeOfInertia( Parray2, TheAxe, issing );
2482       resPlane = gp_Pln( TheAxe );
2483     }
2484
2485   //Temporary
2486   return Standard_True;
2487 }